Allocating tasks in extreme teams

ABSTRACT

Extreme teams, large-scale agent teams operating in dynamic environments, are on the horizon. Such environments are problematic for current task allocation algorithms due to the lack of locality in agent interactions. We propose a novel distributed task allocation algorithm for extreme teams, called LA-DCOP, that incorporates three key ideas. First, LA-DCOP's task allocation is based on a dynamically computed minimum capability threshold which uses approximate knowledge of overall task load. Second, LA-DCOP uses tokens to represent tasks and further minimize communication. Third, it creates potential tokens to deal with inter-task constraints of simultaneous execution. We show that LA-DCOP convincingly outperforms competing distributed task allocation algorithms while using orders of magnitude fewer messages, allowing a dramatic scale-up in extreme teams, upto a fully distributed, proxybased team of 200 agents. Varying threshold are seen as a key to outperforming competing distributed algorithms in the domain of simulated disaster rescue.

REFERENCES

• 1: William Agassounon , Alcherio Martinoli, Efficiency and robustness of threshold-based distributed allocation algorithms in multi-agent systems, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545077]
• 2: M. Campos, E. Bonabeau, G. Therauluz, and J.-L. Deneubourg. Dynamic scheduling and division of labor in social insects. Adaptive Behavior, 2001.
• 3: C. Castelpietra, L. Iocchi, D. Nardi, M. Piaggio, A. Scalzo, and A. Sgorbissa. Coordination among heterogenous robotic soccer players. In Proceedings of IROS'02, 2002.
• 4: Stephen Fitzpatrick , Lambert G. L. T. Meertens, An Experimental Assessment of a Stochastic, Anytime, Decentralized, Soft Colourer for Sparse Graphs, Proceedings of the International Symposium on Stochastic Algorithms: Foundations and Applications, p.49-64, December 13-14, 2001
• 5: Dani Goldberg, Vincent Cicirello, M Bernardine Dias, Reid Simmons, Stephen Smith, and Anthony (Tony) Stentz. Market-based multi-robot planning in a distributed layered architecture. In Multi-Robot Systems: From Swarms to Intelligent Automata: Proceedings from the 2003 International Workshop on Multi-Robot Systems, volume 2, pages 27--38. Kluwer Academic Publishers, 2003.
• 6: Henry Hexmoor , Xin Zhang, Socially Intelligent Aerial Combat Simulator, Proceedings of the 7th Pacific Rim International Conference on Artificial Intelligence: Trends in Artificial Intelligence, p.365-374, August 18-22, 2002
• 7: L. Hunsberger and B. Grosz. A combinatorial auction for collaborative planning, 2000.
• 8: Hiraoki Kitano, Minoru Asada, Yasuo Kuniyoshi, Itsuki Noda, Eiichi Osawa,, and Hitoshi Matsubara. RoboCup: A challenge problem for AI. AI Magazine, 18(1):73--85, Spring 1997.
• 9: Rajiv T. Maheswaran , Milind Tambe , Emma Bowring , Jonathan P. Pearce , Pradeep Varakantham, Taking DCOP to the Real World: Efficient Complete Solutions for Distributed Multi-Event Scheduling, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.310-317, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.257]
• 10: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 11: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, An asynchronous complete method for distributed constraint optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860602]
• 12: Ranjit Nair , Takayuki Ito , Milind Tambe , Stacy Marsella, Task Allocation in the RoboCup Rescue Simulation Domain: A Short Note, RoboCup 2001: Robot Soccer World Cup V, p.751-754, January 2002
• 13: Ranjit Nair , Milind Tambe , Stacy Marsella, Role allocation and reallocation in multiagent teams: towards a practical analysis, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860664]
• 14: Steven Okamoto. Dcop in la: Relaxed. Master's thesis, University of Southern California, 2003.
• 15: Committee on Visionary Manufacturing Challenges. Visionary manufacturing challenges for 2020. National Research Council.
• 16: Massimo Paolucci , Takahiro Kawamura , Terry R. Payne , Katia P. Sycara, Semantic Matching of Web Services Capabilities, Proceedings of the First International Semantic Web Conference on The Semantic Web, p.333-347, June 09-12, 2002
• 17: Pedro V. Sander , Denis Peleshchuk , Barbara J. Grosz, A scalable, distributed algorithm for efficient task allocation, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 3, July 15-19, 2002, Bologna, Italy [doi>10.1145/545056.545098]
• 18: P. Scerri, E. Liao, Yang. Xu, M. Lewis, G. Lai, and K. Sycara. Theory and Algorithms for Cooperative Systems, chapter Coordinating very large groups of wide area search munitions. World Scientific Publishing, 2004.
• 19: Paul Scerri , David Pynadath , Lewis Johnson , Paul Rosenbloom , Mei Si , Nathan Schurr , Milind Tambe, A prototype infrastructure for distributed robot-agent-person teams, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860645]
• 20: Nathan Schurr , Janusz Marecki , Milind Tambe , Paul Scerri, Demonstration of DEFACTO: training tool for incident commanders, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082825]
• 21: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 22: G. Tidhar, A. S. Rao, and E. A. Sonenberg. Guided team selection. In Proceedings of the Second International Conference on Multi-Agent Systems, 1996.
• 23: Weixiong Zhang , Lars Wittenburg, Distributed breakout revisited, Eighteenth national conference on Artificial intelligence, p.352-357, July 28-August 01, 2002, Edmonton, Alberta, Canada

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms

Keywords:
distributed constraint optimization, task allocation