Nuzhet Atay,Burchan Bayazit

Multi-robot systems require efficient and accurate planning in order to perform mission-critical tasks. However, algorithms that find the optimal solution are usually computationally expensive and may require a large number of messages between the robots as the robots need to be aware of the global spatiotemporal information. In this project, we introduce an emergent task allocation approach for mobile robots. Each robot uses only the information obtained from its immediate neighbors in its decision. Our technique is general enough to be applicable to any task allocation scheme as long as a utilization criteria is given. We demonstrate that our approach performs similar to the integer linear programming technique which finds the global optimal solution at the fraction of its cost. The tasks we are interested in are detecting and controlling multiple regions of interest in an unknown environment in the presence of obstacles and intrinsic constraints. The objective function contains four basic requirements of a multi-robot system serving this purpose: control regions of interest, provide communication between robots, control maximum area and detect regions of interest. Our solution determines optimal locations of the robots to maximize the objective function for small problem instances while efficiently satisfying some constraints such as avoiding obstacles and staying within the speed capabilities of the robots, and finds an approximation to global optimal solution by correlating solutions of small problems.

In order to find a good approximation to the global optimal solution using only local information, the content of the information exchanged between the neighbor robots need to be designed carefully. We proposed and studied four strategies: Intentions, Directives, Intentions and Directives, and Intentions, Directives and Target Information.

Robots send their intented locations to neighbors, then each robot assumes that these locations are final finds its optimal	Robots send expected locations of neighbors, then each robot chooses the best among them	Robots send both their and neigbors' computed locations, then each robot finds the best location using options	Robots send their and their neighbors' locations with possible target assignments, then each robot decides a target assignment and finds the best location using options
Figure 1: Information Exchange Policies

The information exchange step can be iterated several times updating the solution each time with updated information about the neighbor robots and environment. In the technical report, we show that as the number of iterations of information exchange increases, the local emergent solution converges to the global optimal solution.

Global Optimal Solution :

Click on the image above to see flash animation (require Macromedia flash installed on your system). Quicktime and WMV formats are also available.

Emergent Approach

Click on the image above to see flash animation (require Macromedia flash installed on your system). Quicktime and WMV formats are also available.

Emergent approach with 20 robots and 10 targets:

Click on the image above to see flash animation (require Macromedia flash installed on your system). Quicktime and WMV formats are also available.

Emergent approach with 30 robots and 15 targets:

Click on the image above to see flash animation (require Macromedia flash installed on your system). Quicktime and WMV formats are also available.