ARMS Workshop at AAMAS 2024 · Auckland, New Zealand
Multi-Agent Path Finding Using Time-Extended Graphs with Auctions
Many robots, each with its own goal, share one floor. Every robot bids for its shortest route; the auction decides who plans first, and each winner reserves its path in space and time, so the paths can never collide.
Expand the map in time
The floor plan is copied once per time step. Moving to a neighboring cell or waiting in place both go one step forward in time, so a route becomes a path that only climbs upward.
Robots bid
Each robot still waiting finds its shortest path in that graph and bids its length. The auctioneer picks a winner: the lowest bid, the highest bid, or at random.
Reserve, repeat
The winner's cells at each moment, and the swaps that would cross it, are removed from the graph. The remaining robots bid again on what is left, until everyone has a path.
What the paper found
- No collisions in any solution, by construction, on random 20 × 20 grids with 20 robots and warehouse-like 30 × 30 grids with 30 robots.
- The bid-minimizer auctioneer gave the lowest average flowtime; the bid-maximizer gave the lowest average makespan; random ordering was worse on both.
- The time-extended graph is a DAG, so shortest paths can be found with a label-setting algorithm in linear time.
This demo runs a browser port of the authors' code: the warehouse layout, the time-expanded search and the three auctioneers. Results vary from map to map; try a few.
Read the paper