skip to main content
10.5555/1402298.1402303acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Reaction functions for task allocation to cooperative agents

Published: 12 May 2008 Publication History

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]
V. Dang and N. Jennings. Generating coalition structures with finite bound from the optimal guarantees. In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 564--571, 2004.
[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]
S. Kraus, O. Shehory, and G. Taase. Coalition formation with uncertain heterogeneous information. In Proceedings of the International Joint Conference on Autonomous Agents and Multi-Agent Systems, pages 1--8, 2003.
[7]
H. Lau and L. Zhang. Task allocation via multi-agent coalition formation: Taxonomy, algorithms and complexity. In Proceedings of the International Conference on Tools with Artificial Intelligence, pages 346--350, 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]
T. Sandholm and V. Lesser. Coalitions among computationally bounded agents. Artificial Intelligence, 94(1--2):99--137, 1997.
[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]
O. Shehory and S. Kraus. Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1--2):165--200, 1998.
[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.

Cited By

View all
  • (2016)Controlling growing tasks with heterogeneous agentsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060686(461-467)Online publication date: 9-Jul-2016
  • (2016)Exploiting Spatial Locality and Heterogeneity of Agents for Search and Rescue Teamwork*Journal of Field Robotics10.1002/rob.2160133:7(877-900)Online publication date: 1-Oct-2016
  • (2014)Tasks with cost growing over time and agent reallocation delaysProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2615794(381-388)Online publication date: 5-May-2014
  • Show More Cited By

Index Terms

  1. Reaction functions for task allocation to cooperative agents

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
    May 2008
    673 pages
    ISBN:9780981738116

    Sponsors

    In-Cooperation

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 12 May 2008

    Check for updates

    Author Tags

    1. agent coordination
    2. coalition formation
    3. teamwork

    Qualifiers

    • Research-article

    Conference

    AAMAS08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2016)Controlling growing tasks with heterogeneous agentsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060686(461-467)Online publication date: 9-Jul-2016
    • (2016)Exploiting Spatial Locality and Heterogeneity of Agents for Search and Rescue Teamwork*Journal of Field Robotics10.1002/rob.2160133:7(877-900)Online publication date: 1-Oct-2016
    • (2014)Tasks with cost growing over time and agent reallocation delaysProceedings of the 2014 international conference on Autonomous agents and multi-agent systems10.5555/2615731.2615794(381-388)Online publication date: 5-May-2014
    • (2013)Distributed problem solving in geometrically-structured constraint networksProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485152(1221-1222)Online publication date: 6-May-2013
    • (2011)Multi-agent Cooperative Cleaning of Expanding DomainsInternational Journal of Robotics Research10.1177/027836491037724530:8(1037-1071)Online publication date: 1-Jul-2011
    • (2011)Static and expanding grid coverage with ant robotsTheoretical Computer Science10.1016/j.tcs.2011.05.001412:35(4661-4674)Online publication date: 1-Aug-2011
    • (2009)Negotiation with reaction functions for solving complex task allocation problemsProceedings of the 2009 IEEE/RSJ international conference on Intelligent robots and systems10.5555/1732643.1732832(4811-4816)Online publication date: 10-Oct-2009

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media