Proceedings

Generalized Reaction Functions for Solving Complex-Task Allocation Problems

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 478-482.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

We study distributed task-allocation problems wherecooperative agents need to perform some tasks simultaneously. Examples are multi-agent routing problems where several agents need to visit some targets simultaneously, for example, to move obstacles out of the way cooperatively. In this paper, we first generalize the concept of reaction functions proposed in the literature to characterize the agent costs of performing multiple complex tasks. Second, we show how agents can construct and approximate reaction functions in a distributed way. Third, we show how reaction functions can be used by an auction-like algorithm to allocate tasks to agents. Finally, we show empirically that the team costs of our algorithms are substantially smaller than those of an existing state-of-the-art allocation algorithm for complex tasks.

  1. [Desrosiers et al., 1995] J. Desrosiers, Y. Dumas, M. Solomon, and F. Soumis. Time constrained routing and scheduling. In Network Routing, volume 8 of Handbooks in Operations Research and Management Science, chapter 2, pages 35-139. 1995.
  2. [Dias et al., 2006] M. Dias, R. Zlot, N. Kalra, and A. Stentz. Market-based multirobot coordination: a survey and analysis. Proceedings of the IEEE, Special Issue on Multirobot Coordi- nation, 94(7):1257 -1270, 2006.
  3. [Koenig et al., 2007] S. Koenig, C. Tovey, X. Zheng, and I. Sungur. Sequential bundle-bid single-sale auction algorithms for decen- tralized control. In Proceedings of the International Joint Con- ference on Artificial Intelligence, pages 1359-1365, 2007. IJCAI
  4. [Or, 1976] I. Or. Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. PhD thesis, Northwestern University, Evanston, Illinois, 1976.
  5. [Zheng and Koenig, 2008] X. Zheng and S. Koenig. Reaction func- tions for task allocation to cooperative agents. In Proceedings of the International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 559-566, 2008.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards