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

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: Alexander Babanov , John Collins , Maria Gini, Asking the right question: Risk and expectation in multiagent contracting, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.17 n.3, p.173-186, June 2003 [doi>10.1017/S0890060403173027]
• 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: Moses Charikar , Balaji Raghavachari, The Finite Capacity Dial-A-Ride Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.458, November 08-11, 1998
• 4: Steve Chien , Anthony Barrett , Tara Estlin , Gregg Rabideau, A comparison of coordinated planning methods for cooperating rovers, Proceedings of the fourth international conference on Autonomous agents, p.100-101, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337057]
• 5: John Edgar Collins , Maria L. Gini, Solving combinatorial auctions with temporal constraints in economic agents, University of Minnesota, 2002
• 6: John Collins , Güleser Demir , Maria Gini, Bidtree Ordering in IDA* Combinatorial Auction Winner-Determination with Side Constraints, Revised Papers from the Workshop on Agent Mediated Electronic Commerce on Agent-Mediated Electronic Commerce IV, Designing Mechanisms and Systems, p.17-33, July 16, 2002
• 7: John Collins , Wolfgang Ketter , Maria Gini, A Multi-Agent Negotiation Testbed for Contracting Tasks with Temporal and Precedence Constraints, International Journal of Electronic Commerce, v.7 n.1, p.35-57, Number 1/Fall 2002
• 8: J. Cordeau and G. Laporte. The dial-a-ride problem (darp): Variants, modeling issues and algorithms. 4OR, 1, 2003.
• 9: Jeffrey S. Cox , Edmund H. Durfee , Thomas Bartold, A distributed framework for solving the Multiagent Plan Coordination Problem, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082598]
• 10: Martin Desrochers , Jacques Desrosiers , Marius Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, v.40 n.2, p.342-354, March–April 1992 [doi>10.1287/opre.40.2.342]
• 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: Klaus Dorer , Monique Calisti, An adaptive solution to dynamic transport optimization, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082803]
• 13: Edmund H. Durfee, Scaling Up Agent Coordination Strategies, Computer, v.34 n.7, p.39-46, July 2001 [doi>10.1109/2.933502]
• 14: Alyssa Glass , Barbara Grosz, Socially conscious decision-making, Proceedings of the fourth international conference on Autonomous agents, p.217-224, June 03-07, 2000, Barcelona, Spain [doi>10.1145/336595.337385]
• 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: A Combinatorial Auction for Collaborative Planning, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.151, July 10-12, 2000
• 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: Richard E. Korf, Depth-first iterative-deepening: an optimal admissible tree search, Artificial Intelligence, v.27 n.1, p.97-109, Sept. 1985 [doi>10.1016/0004-3702(85)90084-0]
• 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: Roger Mailler , Victor Lesser, Solving Distributed Constraint Optimization Problems Using Cooperative Mediation, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.438-445, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.249]
• 23: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, An asynchronous complete method for distributed constraint optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860602]
• 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: Paul Scerri , Alessandro Farinelli , Steven Okamoto , Milind Tambe, Allocating tasks in extreme teams, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082584]
• 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 Transactions on Computers, v.29 n.12, p.1104-1113, December 1980 [doi>10.1109/TC.1980.1675516]
• 29: William E. Walsh , Michael P. Wellman , Fredrik Ygge, Combinatorial auctions for supply chain formation, Proceedings of the 2nd ACM conference on Electronic commerce, p.260-269, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352900]
• 30: Michael P. Wellman , Jeffrey K. MacKie-Mason , Daniel M. Reeves , Sowmya Swaminathan, Exploring bidding strategies for market-based scheduling, Proceedings of the 4th ACM conference on Electronic commerce, p.115-124, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779943]
• 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

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Algorithms, Economics, Theory

Keywords:
automated auctions, logistics, multi-agent contracting