Generalized Reaction Functions for Solving Complex-Task Allocation Problems

Zheng, Xiaoming; Koenig, Sven

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

Generalized Reaction Functions for Solving Complex-Task Allocation Problems

Xiaoming Zheng, Sven Koenig

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

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.

Xiaoming Zheng, and Sven Koenig. 2011. Generalized Reaction Functions for Solving Complex-Task Allocation Problems. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 478–482. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087

@inproceedings{ijcai2011p87,
  title     = {Generalized Reaction Functions for Solving Complex-Task Allocation Problems},
  author    = {Zheng, Xiaoming and Koenig, Sven},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {478--482},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-087},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087},
}

TY  - CPAPER
TI  - Generalized Reaction Functions for Solving Complex-Task Allocation Problems
AU  - Zheng, Xiaoming
AU  - Koenig, Sven
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 478
EP  - 482
DO  - 10.5591/978-1-57735-516-8/IJCAI11-087
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-087
ER  -