Multi-robot task allocation for exploration

Abstract

The problem of allocating a number of exploration tasks to a team of mobile robots in dynamic environments was studied. The team mission is to visit several distributed targets. The path cost of target is proportional to the distance that a robot has to move to visit the target. The team objective is to minimize the average path cost of target over all targets. Finding an optimal allocation is strongly NP-hard. The proposed algorithm can produce a near-optimal solution to it. The allocation can be cast in terms of a multi-round single-item auction by which robots bid on targets. In each auction round, one target is assigned to a robot that produces the lowest path cost of the target. The allocated targets form a forest where each tree corresponds a robot’s exploring targets set. Each robot constructs an exploring path through depth-first search in its target tree. The time complexity of the proposed algorithm is polynomial. Simulation experiments show that the allocating method is valid.

Keywords

multi-robot systems / task allocation / average path cost / multi-round single-item auction / target tree

References

[1] MishkinA, MorrisonJ, NguyenT, et al.. Experiences with operations and autonomy of the mars pathfinder microrover [C]. 1998 IEEE Aerospace Conference Proceedings, 1998, Piscataway, IEEE: 337-351

[2] Thrun S, Burgard W, Fox D. A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA). San Francisco, 2000: 321–328.

[3] MurphyR. Rescue robotics for homeland security[J]. Communications of the ACM, Special Issue on Homeland Security, 2004, 27(3): 66-69

[4] Hougen D. A miniature robotic system for reconnaissance and surveillance[C]// Proceedings of IEEE International Conference on Robotics and Automation (ICRA). San Francisco, 2000: 501–507.

[5] Kalra N, Ferguson D, Stentz A. Hoplites: a marketbased framework for planned tight coordination in multirobot teams[C]// Proceedings of the International Conference on Robotics and Automation. Barcelona, 2005: 1182–1189.

[6] ParkerL. Lifelong adaptation in heterogeneous multirobot teams: response to continual variation in individual robot performance[J]. Autonomous Robots, 2000, 8(3): 239-267

[7] GerkeyB, MataricM. A formal analysis and taxonomy of task allocation in multi-robot systems [J]. Intl J of Robotics Research, 2004, 23(9): 939-954

[8] StoneP, VelosoM. Task decomposition, dynamic role assignment, and low-bandwidth communication for real-time strategic teamwork [J]. Artificial Intelligence, 1999, 110(2): 241-273

[9] Mataric M, Sukhatme G. Task-allocation and coordination of multiple robots for planetary exploration[C] // Proceedings of the International Conference on Advanced Robotics. Buda, 2001: 61–70.

[10] Zlot R, Stentz A, Dias M, et al. Multi-robot exploration controlled by a market economy[C]// Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). Washington, 2002: 3016–3023.

[11] BurgardW, MoorsM, StachnissC, et al.. Coordinated multi-robot exploration[J]. IEEE Transaction on Robotics, 2005, 21(3): 376-386

[12] ZhangFei, ChenWei-dong, XiYu-geng. Improved market-based approach to collaborative multirobot exploration[J]. Control and Decision, 2005, 20(5): 516-524(in Chinese)

[13] ToveyC, LagoudakisM, JainS, et al.ParkerL, ScheiderF, SchultzA, et al.. The generation of bidding rules for auction-based robot coordination[C]. Multirobot Systems: From Swarms to Intelligent Automata, 2005, Berlin, Springer: 3-14

[14] SittersR. The minimum latency problem is Np-hard for weighted trees [C]. Proceedings of the Ninth Conference on Integer Programming and Combinatorial Optimization, 2002, Cambridge, MA, Springer: 230-239

[15] Lagoudakis M, Berhault M, Koenig S, et al. Simple auction with performance guarantees for multi-robot task allocation[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Sendai, 2004: 698–705.

[16] Dias M B, Zlot N, Kalra R, et al. Market-based multirobot coordination: a survey and analysis[R]. CMU - RI - TR - 05 - 13, Robotics Institute, Carnegie Mellon University, 2005.