Organizations: Dachuan Liu, Shizhe Zhao, and Zhongqiang Ren are with Shanghai Jiao Tong University, Shanghai, China · Shuai Zhou is with the South China University of Technology, Guangzhou, China
Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit the use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-based Planning (LSRP) was proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSRP* and test it against several baselines with up to 1000 agents on various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.
Figures & tables
Fig. 1: Motivation for MAPF-AA. Robots may have different speeds due to payload and safety reasons, which leads to the asynchronous actions as considered in this work. † † footnotemark:
Fig. 2: A toy example: each search node owns an action tree. The orange search node is generated from a partial assignment completed by the rule-based procedure; the gray one from a leaf that assigns every idle agent.
Fig. 3: Dominance between search nodes with the same joint edge. Left: n1≻n2 ; right: n3 and n4 are incomparable because an earlier goal arrival gives agent 2 a lower cost in n4 despite its later action end time.
Fig. 4: Illustration of re-init. Circled numbers count iterations c : Path A reaches the first goal n1∗ at c=4 , so cmax=4 . When Path B reaches no goal by c=cmax , re-init (orange) expands n0 instead of the next popped node, and Path C reaches a cheaper goal n2∗ .
Fig. 5: Rule-based completion and the action cache Φ . Left: completions from the root θ0 (orange) and a non-root action node θ (blue); only the root call reads the inherited Φ , and only the orange successor is shown. Right: an example at τ=3 .
Fig. 6: Single-agent action assignment by AsyPush . Left: a successful recursive push makes the processing agent wait and store its deferred move in Φ . Right: an example in a corridor.
Fig. 7: Flip breaks a distance tie using simulated push delays. The illustrated delays of 6s for D and 2s for G place G first, while F remains a candidate.
Fig. 8: Benchmark maps used in the experiments, with their grid sizes. Obstacles are shown in black.
Fig. 9: Success rate results. Our methods (LSRP*, LSRP*-SWAP) scale better than the baselines. LSRP*-SWAP scales the best, reaching the upper limit of every benchmark.
Fig. 10: SOC ratio of LSRP*-SWAP over a baseline, computed on instances solved by both. The baseline is LSRP-SWAP, CBS-AA, or PP-SIPP. LSRP*-SWAP finds solutions up to about 40% cheaper than LSRP-SWAP and stays within about 25% of the optimum.
Fig. 11: Effect of the proposed re-init on anytime refinement. Solid lines show the mean SOC normalized by the first-solution SOC over instances, and shaded bands show ±1 standard deviation. For N=10 , the red dashed line marks the CBS-AA optimum. It verifies that the re-init technique helps improve solution quality over time, especially on large instances ( N=200 ).
Fig. 12: Effect of the proposed Flip technique on anytime refinement. Solid lines show the mean SOC normalized by the first-solution SOC over instances, and shaded bands show ±1 standard deviation. For N=10 , the red dashed line marks the CBS-AA optimum. Flip improves solution quality mainly on large instances ( N=200 ).
Fig. 13: Asynchronous first- and final-solution SOC relative to the first-solution SOC of the constant-duration-5 baseline. Solid lines show the mean over instances and shaded bands show ±1 standard deviation. Planning with asynchronous actions yields solutions about 35–45% cheaper than conservative synchronization.
Fig. 14: Top left: agent 1 (red) moves from S to B and agent 2 (blue) from X to A ; stars mark goals and edge labels are durations. Bottom: states s1 and s2 , with (tp,tv) next to each move; both have the end joint vertex (B,S) but different joint edges. Top right: s1 has smaller arrival times tv , so LSS prunes s2 , yet only s2 leads to the optimal SOC 13 . Definition 1 does not compare them, so both are kept.