LSRP* turns asynchronous multi-agent planning into anytime refinement: up to 25% more agents and 40% lower solution cost
Synopsis
Multi-agent path finding has long assumed that all agents start together and every edge takes the same time, an assumption that fails under asynchronous actions. LSRP* adds an anytime search on top of LSRP's push-and-swap rule-based planning, producing a feasible solution quickly and then improving it within the runtime budget. On benchmark maps with up to 1000 agents, it handles up to 25% more agents than LSRP and reduces LSRP's solution cost by up to 40%.
Interpretation
Multi-agent path finding with asynchronous actions can now keep improving after the first solution instead of stopping there. The earlier LSRP scales to many agents but is an unbounded suboptimal planner and cannot use extra runtime to improve solution quality. Across four MAPF benchmark maps with 20 instances each and agent counts up to 1000, LSRP* handles up to 25% more agents than LSRP and reduces the cost of LSRP's solutions by up to 40%.
The improvement comes from putting arrival times into the search and repeatedly restarting search paths through a dominance rule and re-initialization. LSRP* keeps LSRP's push and swap rules to complete actions, but turns the search into a depth-first, lazy expansion that generates one successor per iteration. The search runs over a time-augmented state space, dominance compares both cost and each agent's arrival time, and re-initialization periodically expands the root after as many iterations as the last improvement took.
On instances where an optimal solution can be computed, the refined solutions come close to optimal. Within a 60-second budget, LSRP* refines the initial LSRP solution cost by up to about 35%, narrowing the gap to the optimum to a few percent. Against CBS-AA, an optimal solver for asynchronous actions, LSRP*-SWAP stays within about a few percent of the optimum in solution cost.
Perspective
The demonstrated setting is point agents on four MAPF benchmark maps, with action durations drawn per agent and edge and per-instance time limits of 30 or 60 seconds; the authors propose extending to large agents that occupy multiple vertices and differ in size and speed, and validating on physical multi-robot platforms.
LSRP* alone only matches baselines on cluttered maps, and the scalability advantage appears mainly with the swap rule in LSRP*-SWAP; Flip gives little improvement with few agents and matters more at larger scale; at larger agent counts, refinement within 60 seconds is limited and the first-solution and final curves converge.
