Optimized Algorithms for Multi-Agent Routing

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 multirobot 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.

Authors

• Akihiro Kishimoto IBM Research - Tokyo
• Nathan Sturtevant

Keywords

• Auction
• multi-robot routing
• shortest-distance computation
• pathfinding
• clique abstraction
• Dijkstra’s algorithm
• A∗