skip to main content
10.1145/1282100.1282161acmotherconferencesArticle/Chapter ViewAbstractPublication PagesicecConference Proceedingsconference-collections
Article

Decentralized task allocation using magnet: an empirical evaluation in the logistics domain

Published: 19 August 2007 Publication History

Abstract

This paper presents a decentralized task allocation method that can handle allocation of tasks with time and precedence constraints in a multi-agent setting where not all information needed for a centralized approach is shared.
In our MAGNET-based approach agents distribute tasks via first-price reverse combinatorial auctions, where the auctioneer is whatever agent has tasks to be allocated. The choice of MAGNET is based on its uniqueness to handle auctions for allocation of tasks which include time windows and precedence constraints.
Empirical evaluations based on real data obtained from a logistics company show that the system performs well. The costs of the allocations obtained by our approach are on average within 5% from the optimal allocation. The computation time is linear in the number of tasks, while computing the optimal allocation is an NP-hard problem.

References

[1]
A. Babanov, J. Collins, and M. Gini. Asking the right question: Risk and expectation in multi-agent contracting. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 17(4):173--186, September 2003.
[2]
P. Briggs. The hand-off: the future of outsourced logistics may be found in the latest buzzword {fourth party logistics}. Canadian Transportation Logistics, 102(5):18, 1999.
[3]
M. Charikar and B. Raghavachari. The finite capacity dial-a-ride problem. In 39th Annual Symposium on Foundations of Computer Science, page 458, Los Alamitos, CA, USA, 1998. IEEE Computer Society.
[4]
S. Chien, A. Barrett, T. Estlin, and G. Rabideau. A comparison of coordinated planning methods for cooperating rovers. In Proc. of the Fourth Int'l Conf. on Autonomous Agents, pages 100--101. ACM Press, 2000.
[5]
J. Collins. Solving Combinatorial Auctions with Temporal Constraints in Economic Agents. PhD thesis, University of Minnesota, June 2002.
[6]
J. Collins, G. Demir, and M. Gini. Bidtree ordering in IDA* combinatorial auction winner-determination with side constraints. In J. Padget, O. Shehory, D. Parkes, N. Sadeh, and W. Walsh, editors, Agent Mediated Electronic Commerce IV, volume LNAI2531, pages 17--33. Springer-Verlag, 2002.
[7]
J. Collins, W. Ketter, and M. Gini. A multi-agent negotiation testbed for contracting tasks with temporal and precedence constraints. Int'l Journal of Electronic Commerce, 7(1):35--57, 2002.
[8]
J. Cordeau and G. Laporte. The dial-a-ride problem (darp): Variants, modeling issues and algorithms. 4OR, 1, 2003.
[9]
J. S. Cox, E. H. Durfee, and T. Bartold. A distributed framework for solving the multiagent plan coordination problem. In Autonomous Agents and Multi-Agent Systems, pages 821--827, 2005.
[10]
M. Desrochers, J. Desrosiers, and M. Solomon. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 40(2):342--354, 1992.
[11]
M. B. Dias, R. M. Zlot, N. Kalra, and A. T. Stentz. Market-based multirobot coordination: A survey and analysis. Technical Report CMU-RI-TR-05-13, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, April 2005.
[12]
K. Dorer and M. Calisti. An adaptive solution to dynamic transport optimization. In Proc. of AAMAS05, pages 45--51, 2005.
[13]
E. H. Durfee. Scaling up agent coordination strategies. IEEE Computer, 34(7):39--46, July 2001.
[14]
A. Glass and B. J. Grosz. Socially conscious decision-making. In Proc. of the Fourth Int'l Conf. on Autonomous Agents, pages 217--224, June 2000.
[15]
M. Hoogendoorn and C. M. Jonker. Formation of virtual organizations through negotiation. In Proceedings of the Fourth German Conference on Multiagent Technologies (MATES 2006), pages 135--146. Springer, 2006.
[16]
L. Hunsberger and B. J. Grosz. A combinatorial auction for collaborative planning. In Proc. of 4th Int'l Conf on Multi-Agent Systems, pages 151--158, Boston, MA, 2000. IEEE Computer Society Press.
[17]
J. J. Jaw, A. Odoni, H. Psaraftis, and N. Wilson. Heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research Part B, 20B:243--257, 1986.
[18]
R. Kasilingam. Logistics and Transportation: Design and Planning. Springer, 1999.
[19]
R. E. Korf. Depth-first iterative deepening: An optimal admissible tree search. Artificial Intelligence, 27:97--109, 1985.
[20]
V. Krishna. Auction Theory. Academic Press, London, UK, 2002.
[21]
T. Magnanti. Combinatorial optimization and vehicle fleet planning: Perspectives and prospects. Networks, 11:179--214, 1981.
[22]
R. Mailler and V. Lesser. Solving distributed constraint optimization problems using cooperative mediation. In Proc. of AAMAS04, 2004.
[23]
P. J. Modi, W.-M. Shen, M. Tambe, and M. Yokoo. An asynchronous complete method for distributed constraint optimization. In Proc. of AAMAS03, 2003.
[24]
T. A. Moehlman, V. R. Lesser, and B. L. Buteau. Decentralized negotiation: An approach to the distributed planning problem. Group Decision and Negotiation, 1:161--191, 1992.
[25]
T. Notteboom. Container shipping and ports: An overview. Review of Network Economics, 3(2):86--106, 2004.
[26]
P. Scerri, A. Farinelli, S. Okamoto, and M. Tambe. Allocating tasks in extreme teams. In Proc. of AAMAS05, pages 727--734, 2005.
[27]
M. C. Schut, M. Kentrop, M. Leenaarts, M. Melis, and I. Miller. Approach: Decentralised rotation planning for container barges. In Proceedings of the 16th European Conference on Artificial Intelligence, pages 755--759, 2004.
[28]
R. G. Smith. The contract net protocol: High level communication and control in a distributed problem solver. IEEE Trans. Computers, 29(12):1104--1113, December 1980.
[29]
W. E. Walsh, M. Wellman, and F. Ygge. Combinatorial auctions for supply chain formation. In Proc. of ACM Conf on Electronic Commerce (EC-00), pages 260--269, October 2000.
[30]
M. Wellman, J. MacKie-Mason, D. Reeves, and S. Swaminathan. Exploring bidding strategies for market-based scheduling. In Proc. of Fourth ACM Conf on Electronic Commerce, 2003.
[31]
M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35:271--303, 2001.

Index Terms

  1. Decentralized task allocation using magnet: an empirical evaluation in the logistics domain

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Other conferences
      ICEC '07: Proceedings of the ninth international conference on Electronic commerce
      August 2007
      482 pages
      ISBN:9781595937001
      DOI:10.1145/1282100
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      In-Cooperation

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 19 August 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. automated auctions
      2. logistics
      3. multi-agent contracting

      Qualifiers

      • Article

      Conference

      ICEC07

      Acceptance Rates

      Overall Acceptance Rate 150 of 244 submissions, 61%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • 0
        Total Citations
      • 172
        Total Downloads
      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      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