Distributed Auction-Based Initialization of Mobile Robot Formations
The problem of initializing a formation of robots from a swarm of robots is one that presents an obvious area for improvement of the CATALST (Mead 2008) architecture. A distinction must be made between robot swarms and robot formations. A swarm is a group of individuals within relative proximity of one another, which maintain no overall order. In contrast with the idea of a swarm of robots is the concept of a formation. The distinguishing feature of a formation is that the individual constituents have a rigid relationship to one another and have a fixed overall volume and shape. The use of robot formations in the above mentioned applications is rendered much more useful by increasing the degree of autonomy under which the system can operate. The implementation of CATALST required that the neighboring robot ID’s be manually set. This works well enough for small numbers of robots, but presents an increasingly difficult problem as the number of robots increases. We present our approach to solving this problem, to dynamically assign positions within the formation to robots as the formation is being formed, in situ.
The Simulator
A simulator which implements the CATALST architecture, described in our previous work (Mead et al 2009) has been augmented to allow for distributed auctioning of positions within the formation to bidders, or, robots not yet in the formation. In our implementation, an auction consists of a broadcast announcement to all robots in the simulation by the auctioneer (the robot holding the auction and located next to the empty cell), which contains the position of the empty cell being auctioned, a waiting period during which bidders calculate and then transmit their bids back to the auctioneer, and a response by the auctioneer, notifying the winning bidder. The bids are sorted so that the lowest is selected as the winner. This ensures that the robot which is selected for each empty cell will be the best possible.
A series of screen captures from the simulator can be seen in fig 1. These images show the initial state of the simulator
 |
Heading3
Text3.
 |
