An Auction-Based Algorithm Considering Path-Cost Computation
Akihiro Kishimoto (Future University, Hakodate, Japan)
NICTA KRR SEMINARDATE: 2008-02-19
TIME: 14:00:00 - 15:00:00
LOCATION: Seminar room, ground floor of NICTA building, 7 London crt
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Auction methods have been used as approximation methods for the effective coordination of teams of robots. In particular, they have been applied to the multi-robot routing problem, a representative domain for multi-agent coordination. Solutions to this problem typically use bids computed by the shortest distance among various locations. But, the cost of this shortest-distance computation has not been considered in previous research.
This talk combines an auction-based algorithm with map abstraction, a state-of-the-art technique in pathfinding. The presented algorithm can effectively approximate the shortest distances used to bid, while preserving benefits of the auction-based algorithm. Experiments are performed in simulations of the multi-robot routing problem with large maps, and results demonstrate that using map abstraction improves the execution time by a large margin, with only a small degradation in solution quality.
