Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding

IJCAI-23
https://kei18.github.io/lacam2/

Transcript

1. Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding Keisuke Okumura Macao, 19th – 25th Aug. 2023 IJCAI-23 https://kei18.github.io/lacam2 National Institute of Advanced Industrial Science and Technology (AIST) University of Cambridge
2. /31 2 MAPF: Multi-Agent Path Finding given agents (starts) graph goals solution paths without collisions cost total travel time, distance, makespan, etc
3. /31 3 solvability & quality high low effort small large speed & scalability complete optimal incomplete suboptimal Tradeoff in MAPF Algorithms
4. /31 4                runtime (sec) solved instances (%) Evaluation on Benchmark - 13,900 instances - 33 grid maps - every 50 agents, up to max. (1000) - tested on standard desktop PC [Stern+ SOCS-19] 33 grid maps e.g., random-32-32-20, 200 agents 00.0% A* [Hart+ 68] complete optimal
5. /31 5                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] complete optimal
6. /31 6                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] 08.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] complete solution complete optimal optimal (unable to identify unsolvable instances)
7. /31 7                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] 08.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% ODrM*-5 [Wagner+ AIJ-15] complete solution complete complete bounded suboptimal optimal optimal (unable to identify unsolvable instances)
8. /31 8                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] 08.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% ODrM*-5 [Wagner+ AIJ-15] 50.5% EECBS-5 [Li+ AAAI-21] complete solution complete complete solution complete bounded suboptimal bounded suboptimal optimal optimal (unable to identify unsolvable instances)
9. /31 9                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] 08.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% ODrM*-5 [Wagner+ AIJ-15] 50.5% EECBS-5 [Li+ AAAI-21] 61.4% PP [Silver AIIDE-05] 80.9% LNS2 [Li+ AAAI-22] 67.4% PIBT [Okumura+ AIJ-22] 90.5% PIBT+ [Okumura+ AIJ-22] complete solution complete complete solution complete incomplete bounded suboptimal suboptimal bounded suboptimal optimal optimal (unable to identify unsolvable instances)
10. /31 10                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] 08.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% ODrM*-5 [Wagner+ AIJ-15] 50.5% EECBS-5 [Li+ AAAI-21] 61.4% PP [Silver AIIDE-05] 80.9% LNS2 [Li+ AAAI-22] 67.4% PIBT [Okumura+ AIJ-22] 90.5% PIBT+ [Okumura+ AIJ-22] complete solution complete complete solution complete incomplete bounded suboptimal suboptimal bounded suboptimal optimal optimal (unable to identify unsolvable instances) 85.6% LaCAM [Okumura+ AAAI-23] complete suboptimal
11. /31 11                runtime (sec) solved instances (%) 00.0% A* [Hart+ 68] 00.4% ODrM* [Wagner+ AIJ-15] 08.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% ODrM*-5 [Wagner+ AIJ-15] 50.5% EECBS-5 [Li+ AAAI-21] 61.4% PP [Silver AIIDE-05] 80.9% LNS2 [Li+ AAAI-22] 67.4% PIBT [Okumura+ AIJ-22] 90.5% PIBT+ [Okumura+ AIJ-22] 85.6% LaCAM [Okumura+ AAAI-23] 99.0% LaCAM* (initial solution) complete solution complete complete solution complete incomplete complete complete eventually optimal bounded suboptimal suboptimal bounded suboptimal optimal optimal suboptimal (unable to identify unsolvable instances) this study
12. /31 12 [Okumura AAAI-23] contributions of this study: two enhancements over LaCAM 1. LaCAM*: eventually optimal version for accumulative transition costs 2. successor generation tuning for obtaining initial solutions quickly
13. /31 13 [Okumura AAAI-23] contributions of this study: two enhancements over LaCAM 1. LaCAM*: eventually optimal version for accumulative transition costs 2. successor generation tuning for obtaining initial solutions quickly
14. /31 14 … … … … … search node (configuration) goal configuration Vanilla A* for MAPF complete but very slow greedy search: 44 nodes in general: (5^N)xT nodes N: agents, T: depth intractable even with perfect heuristics
15. /31 15 PIBT PIBT PIBT repeat one-timestep planning until termination use PIBT to guide exhaustive search initial configuration PIBT goal configuration [Okumura+ AIJ-22] quick but incomplete greedy search: 44 nodes only 4 configurations
16. /31 16 … … … … … LaCAM [Okumura AAAI-23] lazy constraints addition search for MAPF; complete greedy: 44 nodes LaCAM: 4 nodes => quick & complete MAPF lazy successor generation using other MAPF algorithms PIBT PIBT PIBT not generated no quality guarantee
17. /31 17 configuration & cost (makespan) 1 2 3 4 6 5 0 initial config. 5 goal config. LaCAM stops the search when finding the goal config. search tree parent – children other neighbors LaCAM*
18. /31 18 1 2 3 4 5 6 0 5 LaCAM* continues the search after finding the goal config. LaCAM* parent – children other neighbors initial config. goal config. search tree configuration & cost (makespan) 1
19. /31 19 1 2 3 4 5 6 0 5 1 LaCAM* new edge when finding new connections,
20. /31 20 1 2 3 3 2 3 0 4 1 LaCAM* This is an anytime algorithm, and eventually optimal if the solution cost is accumulative transition costs when finding new connections, rewrite the tree by Dijkstra
21. /31 21 [Okumura AAAI-23] contributions of this study: two enhancements over LaCAM 1. LaCAM*: eventually optimal version for accumulative transition costs 2. successor generation tuning for obtaining initial solutions quickly
22. /31 22                runtime (sec) solved instances (%) 99.0% LaCAM* improvement on successor generation 85.6% LaCAM [Okumura+ AAAI-23] poor performance in graphs with narrow corridors search iterations (until finding initial solutions) 128 23,907 287,440 Too much! optimal solution length = 5
23. /31 23 … … … … … LaCAM with PIBT lazy successor generation using other MAPF algorithms PIBT PIBT PIBT performance heavily relies on the underlying algorithm
24. /31 24 Pitfall in PIBT PIBT tries to assign each agent to the vertex closest to the goal
25. /31 25 Incorporating Swap PIBT tries to assign each agent to the vertex closest to the goal reverse this in specific situations - check the paper for details - inspired by Push and Swap/Rotate [Luna+ IJCAI-11; de Wilde+ JAIR-14]
26. /31 26 128 23,907 287,440 6 8 8 search iterations until finding initial solutions original with reversing
27. /31 27 What can the current LaCAM* do?
28. /31 28 optimally solve small congested MAPF instances within a second
29. /31 29 suboptimally solve MAPF for 10,000 agents in a warehouse-style map with narrow corridors, in a few seconds on my laptop
30. /31 30                runtime (sec) solved instances (%; 13900) suboptimally solve 99% of MAPF benchmark instances within 10 seconds remaining 1%: only maze-128-128-1             agents success rate in 30sec LaCAM* other algorithms LaCAM* 33 grid maps
31. /31 31 Concluding Remarks https://kei18.github.io/lacam2 improving covergence speed (current: very slow) improving initial solution quality (current: not excellent) LaCAM* is just a graph pathfinding algorithm; other applications? LaCAM* realization of quick, scalable, complete, and eventually optimal MAPF algorithm future directions