Reaction functions for task allocation to cooperative agents

ABSTRACT

In this paper, we present ARF, our initial effort at solving task-allocation problems where cooperative agents need to perform tasks simultaneously. An example is multi-agent routing problems where several agents need to visit targets simultaneously, for example, to move obstacles out of the way cooperatively. First, we propose reaction functions as a novel way of characterizing the costs of agents in a distributed way. Second, we show how to approximate reaction functions so that their computation and communication times are polynomial. Third, we show how reaction functions can be used by a central planner to allocate tasks to agents. Finally, we show experimentally that the resulting task allocations are better than those of other greedy methods that do not use reaction functions.

REFERENCES

• 1: Viet Dung Dang , Nicholas R. Jennings, Generating Coalition Structures with Finite Bound from the Optimal Guarantees, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.564-571, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.132]
• 2: J. Desrosiers, Y. Dumas, M. Solomon, and F. Soumis. Time constrained routing and scheduling. In M. Ball, T. Magnanti, C. Monma, and G. Nemhauser, editors, Network Routing, volume 8 of Handbooks in Operations Research and Management Science, chapter 2, pages 35--139. North-Holland, 1995.
• 3: B. Dias and A. Stentz. Opportunistic optimization for market-based multirobot control. In Proceedings of the International Conference on Intelligent Robots and Systems, pages 2714--2720, 2002.
• 4: J. Kahan and A. Rapoport. Theories of coalition formation. Lawrence Erlbaum Associates, 1984.
• 5: S. Koenig, C. Tovey, X. Zheng, and I. Sungur. Sequential bundle-bid single-sale auction algorithms for decentralized control. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 1359--1365, 2007.
• 6: Sarit Kraus , Onn Shehory , Gilad Taase, Coalition formation with uncertain heterogeneous information, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860577]
• 7: Hoong Chuin Lau , Lei Zhang, Task Allocation via Multi-Agent Coalition Formation: Taxonomy, Algorithms and Complexity, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p.346, November 03-05, 2003
• 8: I. Or. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD thesis, Northwestern University, Evanston, Illinois, 1976.
• 9: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 10: S. Sariel and T. Balch. Real time auction based allocation of tasks for multi-robot exploration problem in dynamic environments. In Proceedings of the AAAI-05 Workshop on Integrating Planning into Scheduling, pages 27--33, 2005.
• 11: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 12: C. Tovey, M. Lagoudakis, S. Jain, and S. Koenig. The generation of bidding rules for auction-based robot coordination. In L. Parker, F. Schneider, and A. Schultz, editors, Multi-Robot Systems: From Swarms to Intelligent Automata, pages 3--14. Springer, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms

Keywords:
agent coordination, coalition formation, teamwork