Optimized algorithms for multi-agent routing

ABSTRACT

Auction methods have been successfully used for coordinating teams of robots in the multi-robot routing problem, a representative domain for multi-agent coordination. Solutions to this problem typically use bids computed using the shortest distance between various locations on a map. But, the cost of this shortest-distance computation has not been considered in previous research. This paper presents a new auction-based algorithm, FASTBID, that works to reduce the computational costs associated with bidding in the multi-robot routing problem. We also analyze how a small modification in the bidding algorithm can reduce the computational load of the bidding process. Experiments demonstrate that FASTBID not only scales much better than previous approaches, but does so with little or no loss in solution quality.

REFERENCES

• 1: V. Bulitko, N. Sturtevant, J. Lu, and T. Yau. Graph Abstraction in Real-time Heuristic Search. Journal of Artificial Intelligence Research, 30:51--100, 2007.
• 2: S. Koenig, C. A. Tovey, M. G. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, A. J. Kleywegt, A. Meyerson, and S. Jain. The power of sequential single-item auctions for agent coordination. In Twenty-First National Conference on Artificial Intelligence. AAAI Press, 2006.
• 3: M. Lagoudakis, V. Markakis, D. Kempe, P. Keskinocak, S. Koenig, A. Kleywegt, C. Tovey, A. Meyerson, and S. Jain. Auction-based multi-robot routing. In International Conference on Robotics: Science and Systems, pages 343--350, 2005.
• 4: M. G. Lagoudakis, M. Berhault, S. Koenig, P. Keskinocak., and A. J. Kleywegt. Simple auctions with performance guarantees for multi-robot task allocation. In IEEE International Conference on Intelligent Robots and Systems (IROS 2004), volume 1, pages 1957--1962, 2004.
• 5: E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, and D. B. Shmoys. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley Series in Discrete Mathematics and Optimization, 1985.
• 6: R. C. Prim. Shortest connection networks and some generalizations. Bell Systems Tech. Journals, pages 1389--1401, 1957.
• 7: N. Sturtevant. Hog - hierarchical open graph. http://www.cs.ualberta.ca/~nathanst/hog.html, 2005.
• 8: N. Sturtevant and M. Buro. Partial pathfinding using map abstraction and refinement. In AAAI, pages 1392--1397. AAAI Press, 2005.
• 9: C. Tovey, M. Lagoudakis, S. Jain, and S. Koenig. The generation of bidding rules for auction-based robot coordination. In Multi-Robot Sys.: From Swarms to Intel. Automata, volume 3, pages 3--14. Springer, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms

Keywords:
A*, Dijkstra's algorithm, auction, clique abstraction, multi-robot routing, pathfinding, shortest-distance computation