Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Pathfinding for 10k agents

Pathfinding for 10k agents

Used in a seminar talk in Cambridge
https://talks.cam.ac.uk/talk/index/204508

Keisuke Okumura | 奥村圭祐

November 01, 2023
Tweet

More Decks by Keisuke Okumura | 奥村圭祐

Other Decks in Research

Transcript

  1. /73 Pathfinding for 10k agents Keisuke Okumura1,2 1st Nov. 2023,

    Wednesday Seminar, Dept. of Computer Science and Technology, Univ. of Cambridge 1University of Cambridge 2National Institute of Advanced Industrial Science and Technology (AIST), Japan kei18 https://kei18.github.io [email protected]
  2. /73 3 Le Goc+ UIST-16 Flatland Challenge / AIcrowd Li+

    AAAI-23 StarCraft / YouTube Zhang+ Automation in Construction. 2018
  3. /73 4 underlying common problem: Okumura & Defago. IJCAI-23 collision-free

    pathfinding for multiple agents • quick, real-time • scalable • fewer redundant motions (optimality)
  4. /73 7 Intel Newsroom / YouTube Intel’s Automated Material-Handling System

    (semi-)decentralization is the only way? Demands for 1k-10k scale
  5. /73 8 Drone Addicts / YouTube Port of Amsterdam @tuidelescribano

    / X Shibuya Scramble Crossing, Tokyo Decentralization is powerful
  6. /73 9 @yr_6001_as / X Skylark Channel / YouTube Delivery

    Robots in Restaurants deadlock but with possibility of miscoordination
  7. /73 10 Radio BandNews FM / Facebook São Paulo, gridlocked

    intersection Miscoordination triggers tragedy
  8. /73 12 Varambally, S., Li, J., & Koenig, S. Which

    MAPF Model Works Best for Automated Warehousing? SoCS. 2022. simulation for warehouse automation (not my work) multi-agent path finding algorithm Centralization also improves system performance semi-decentralized
  9. /73 14 given agents graph goals solution paths without collisions

    cost total travel time, distance, makespan, etc MAPF: Multi-Agent Path Finding
  10. /73 15 1. Okumura, K., Yonetani, R., Nishimura, M., &

    Kanezaki, A. CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces. AAMAS. 2022. 2. Okumura, K., Machida, M., Défago, X., & Tamura, Y. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. AIJ. 2022. 3. Okumura, K., &Defago, X. Quick Multi-Robot Motion Planning by Combining Sampling and Search. IJCAI. 2023. 4. Okumura, K., Bonnet, F., Tamura, Y., & Défago, X. Offline Time-Independent Multi-Agent Path Planning. T-RO. 2023. Extended from IJCAI-22. 5. Okumura, K. & Defago, X. Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution. AIJ. 2023. ICAPS-22 Best Student Paper 6. Okumura, K., & Tixeuil, S. Fault-Tolerant Offline Multi-Agent Path Planning. AAAI. 2023. crash tolerance6 asynchronous execution4 with target assignment5 continuous spaces1 lifelong planning2 arbitrary shapes3 Solving MAPF is the foundation of:
  11. /73 17 Hart, P. E., Nilsson, N. J., & Raphael,

    B. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. on Systems Science and Cybernetics. 1968. start goal A* search start goal f = g + h search tree
  12. /73 18 … … … … … search node (configuration)

    goal configuration Vanilla A* for MAPF
  13. /73 19 Completealgorithms return solutions for solvable instances in finite

    time; otherwise, they report the non-existence. Optimalalgorithms always return solutions having minimum costs. Algorithm properties A* is complete. It is optimal with admissible heuristics.
  14. /73 20 runtime (sec) solved instances (%)   

                - 13,900 instances - 33 grid maps - every 50 agents, up to max. (1000) - tested on standard desktop PC Stern, R. et al. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks. SoCS. 2019. 33 grid maps e.g., random-32-32-20, 200 agents Evaluation on MAPF benchmark maze-32-32-2, 100 agents 00.0% A* [Hart+ 68] complete optimal algorithm properties computation time
  15. /73 21 Reason for poor performance of A* start goal

    search tree branching factor (number of successor nodes) O(5^N) N: #agents MAPF has a huge branching factor: 3,125 9,765,625 95,367,431,640,625 931,322,574,615,478,515,625 9,094,947,017,729,282,379,150,390,625 88,817,841,970,012,523,233,890,533,447,265,625 5^5 5^10 5^20 5^30 5^40 5^50 For 10k agents? Ridiculous!
  16. /73 22        

           runtime (sec) solved instances (%) 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] complete optimal algorithm properties A* variant Complete and optimal algorithms are hopeless in scalability. Finding optimal solutions is NP-hard. Yu, J., & LaValle, S. Structure and intractability of optimal multi-robot path planning on graphs. AAAI. 2013. Banfi, J., Basilico, N., & Amigoni, F. Intractability of time-optimal multirobot path planning on 2D grid graphs with holes. RA-L. 2017.
  17. /73 24 Relaxing completness Optimalalgorithms always return solutions having minimum

    costs. Completealgorithms return solutions for solvable instances in finite time; otherwise, they report the non-existence. unable to identify unsolvable instances
  18. /73 25 CBS: Conflict-based Search Sharon, G., Stern, R., Felner,

    A., & Sturtevant, N. R. Conflict-based search for optimal multi-agent pathfinding. AIJ. 2015. high-level search Image by GraphicMama-team from Pixabay identify conflicts in solution candidates low-level search find a path satisfying constraints (e.g., A*) query a single-agent path that avoids detected conflicts return a path satisfying constraints
  19. /73 26 opt. cost: 5 t=1 cost: 5 replan t=1

    cost: 6 replan t=1 t=2 cost: 6 replan t=1 t=2 cost: 6 replan stay Many powerful extensions are available of CBS, e.g., • Boyarski, E. et al. ICBS: improved conflict-based search algorithm for multi- agent pathfinding. IJCAI. 2015. • Felner, A. et al. Adding heuristics to conflict-based search for multi-agent path finding. ICAPS. 2018 • Li, J. et al. Pairwise symmetry reasoning for multi-agent path finding search. AIJ. 2021. • … search when and where each agent cannot use it Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. Conflict-based search for optimal multi-agent pathfinding. AIJ. 2015. How CBS works high-level low-level
  20. /73         

                         27 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] complete optimal runtime (sec) solved instances (%) 8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] solution complete optimal (unable to identify unsolvable instances) two-level, but with mathematical optimization at high-level
  21. /73 28 Relaxing Optimality Optimalalgorithms always return solutions having minimum

    costs. Completealgorithms return solutions for solvable instances in finite time; otherwise, they report the non-existence. allowing bounded suboptimal solutions: obtained solution cost ≤ w*(optimal solution cost) where w ≥ 1
  22. /73 not explored => reducing search effort 29 Intuition of

    finding bounded suboptimal solutions goal search tree to be optimal: expand a node with minimum f-value, fmin to be bounded suboptimal: allowing to expand nodes with f ≤ w*fmin (w ≥ 1) applicable where search schemes exist, e.g., A*-based and CBS
  23. /73         

                         30 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] 8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] complete solution complete optimal optimal (unable to identify unsolvable instances) runtime (sec) solved instances (%) 30.9% I-ODrM*-5 [Wagner+ AIJ-15] complete bounded suboptimal A* variant
  24. /73 31 Relaxing Completeness and Optimality Optimalalgorithms always return solutions

    having minimum costs. Completealgorithms return solutions for solvable instances in finite time; otherwise, they report the non-existence. allowing bounded suboptimal solutions
  25. /73 32 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15]

    8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-ODrM*-5 [Wagner+ AIJ-15] complete solution complete complete bounded suboptimal optimal optimal (unable to identify unsolvable instances) runtime (sec) solved instances (%)                50.5% EECBS-5 [Li+ AAAI-21] solution complete bounded suboptimal CBS variant
  26. /73 33 Give up everything Optimalalgorithms always return solutions having

    minimum costs. Completealgorithms return solutions for solvable instances in finite time; otherwise, they report the non-existence.
  27. /73 34 PP: Prioritized Planning Erdmann, M., & Lozano-Perez, T.

    On multiple moving objects. Algorithmica. 1987; Silver, D. Cooperative pathfinding. AIIDE. 2005. simple, quick, scalable, reasonable solution quality 1 stay 2 2. Perform single-agent pathfinding for each agent according to priorities, while avoiding collisions with already competed paths. 1 2 1. Assign priorities to each agent.
  28. /73 35 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15]

    8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-ODrM*-5 [Wagner+ AIJ-15] complete solution complete complete bounded suboptimal optimal optimal (unable to identify unsolvable instances) runtime (sec) solved instances (%)                50.5% EECBS-5 [Li+ AAAI-21] solution complete bounded suboptimal 61.4% PP [Silver AIIDE-05] incomplete suboptimal
  29. /73 36 MAPF-LNS2: Large Neighborhood Search Li, J., Chen, Z.,

    Harabor, D., Stuckey, P. J., & Koenig, S. MAPF-LNS2: fast repairing for multi-agent path finding via large neighborhood search. AAAI. 2022. high-level search low-level search query paths for the subset of agents return paths identify subset of agents (e.g., random selection) find paths for the subset with a smaller number of collisions with others (e.g., PP)
  30. /73 37 runtime (sec) solved instances (%)   

                0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] 8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-ODrM*-5 [Wagner+ AIJ-15] complete solution complete complete bounded suboptimal optimal optimal (unable to identify unsolvable instances) 50.5% EECBS-5 [Li+ AAAI-21] solution complete bounded suboptimal 61.4% PP [Silver AIIDE-05] incomplete suboptimal 80.9% LNS2 [Li+ AAAI-22] capable of addressing hundreds of agents
  31. /73 39 Summary so far complete optimal incomplete suboptimal My

    research part begins, finally! holy grail state-of-the-art studies theoretical guarantees planning effort small large speed & scalability
  32. /73 40 Unblock Me / Google Play DavidPlays / YouTube

    goal planning stage acting stage Two styles to solve puzzle long-horizon (deliberative, offline) short-horizon (reactive, online)
  33. /73 41 theoretical guarantees planning effort small large speed &

    scalability complete optimal incomplete suboptimal long-horizon (deliberative, offline) short-horizon (reactive, online) Planning Horizon planning stage acting stage
  34. /73 42 theoretical guarantees planning effort small large speed &

    scalability Strategy to overcome the tradeoff short-horizon planning pulls long-horizon planning integration
  35. /73 43 This is just a metaphor.. Image by OpenClipart-Vectors

    from Pixabay PIBT Okumura+ AIJ-22 LaCAM* Okumura AAAI-23, IJCAI-23
  36. /73 44 This is just a metaphor.. Image by OpenClipart-Vectors

    from Pixabay PIBT Okumura+ AIJ-22 LaCAM* Okumura AAAI-23, IJCAI-23
  37. /73 45 PIBT: Priority Inheritance with Backtracking Okumura, K., Machida,

    M., Défago, X., & Tamura, Y. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. AIJ. 2022. (extended from IJCAI-19*) collision-free configuration while reflecting preferences PIBT 1 desired 2 3 4 5 4 2 1 desired 3 *originally developed for lifelong pathfinding scenarios preference & priority + configuration High Low
  38. /73 48 high low mid as high priority inheritance Sha+

    IEEE Trans Comput-90 How PIBT works – 2/4
  39. /73 49 high as high as high as high as

    high stuck but still not feasible How PIBT works – 3/4
  40. /73 50 invalid valid re-plan re-plan valid You can move

    invalid You must re-plan, I will stay introduce backtracking How PIBT works – 4/4 always generate collision-free configurations
  41. /73 52 Performance of PIBT random-32-32-20 32x32 30sec timeout 

              #agents success rate EECBS PP LNS2 0% PIBT runtime (sec)          #agents EECBS PP ost003d 194x194 four-connected grid LNS2 blazing fast! worst: 550ms PIBT quick but shortsighted
  42. /73         

          53 runtime (sec) solved instances (%)                0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] 8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-ODrM*-5 [Wagner+ AIJ-15] complete solution complete complete bounded suboptimal optimal optimal (unable to identify unsolvable instances) 50.5% EECBS-5 [Li+ AAAI-21] solution complete bounded suboptimal 61.4% PP [Silver AIIDE-05] incomplete suboptimal 80.9% LNS2 [Li+ AAAI-22] 67.4% PIBT [Okumura+ AIJ-22] PIBT is convenient, blazing fast, but…
  43. /73 54 This is just a metaphor.. Image by OpenClipart-Vectors

    from Pixabay PIBT Okumura+ AIJ-22 LaCAM* Okumura AAAI-23, IJCAI-23
  44. /73 55 … … … … … search node (configuration)

    goal configuration Recap: A* exponential number of node generation greedy search: 44 nodes
  45. /73 56 PIBT initial configuration Recap: PIBT use PIBT to

    guide exhaustive search only 4 configurations PIBT goal configuration PIBT
  46. /73 57 … … PIBT initial configuration … … PIBT

    goal configuration Okumura, K. LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding. AAAI. 2023 LaCAM: Lazy Constraints Addition Search for MAPF … PIBT not generated immediately 1. Configurations are generated in a lazy manner exhaustive search with two tricks 2. Use other MAPF algorihtms to generate a promising configuration greedy: 44 nodes LaCAM: 4 nodes => quick & complete MAPF
  47. /73 must go left in the next config. 58 constraint

    tree (maintained implicitly) invoked multiple times during the search Lazy constraints addition – 1/4
  48. /73 61 e.g., breadth-first search 24th invoke configuration generation with

    Lazy constraints addition – 4/4 completeness proof: Each configuration eventually generates all neighbor configurations.
  49. /73 62        

                  EECBS PP LNS2 PIBT worst: 11sec LaCAM #agents success rate random-32-32-20, 32x32, 30sec timeout, 400 agents Performance of LaCAM
  50. /73         

          63                runtime (sec) solved instances (%) 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] 8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-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] complete solution complete complete solution complete bounded suboptimal bounded suboptimal optimal optimal (unable to identify unsolvable instances) incomplete suboptimal 85.6% LaCAM [Okumura AAAI-23] complete suboptimal Start breaking the tradeoff!
  51. /73 64 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15]

    8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-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] 85.6% LaCAM [Okumura AAAI-23] complete solution complete complete solution complete complete bounded suboptimal bounded suboptimal optimal optimal suboptimal (unable to identify unsolvable instances) incomplete suboptimal Before LaCAM: scalability ≠ solvability
  52. /73         

          65                runtime (sec) solved instances (%) 85.6% LaCAM [Okumura+ AAAI-23] complete suboptimal 99.0% LaCAM* (initial solution) complete eventually optimal Okumura, K. Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding. IJCAI. 2023. LaCAM* with fine-tuned PIBT
  53. /73 66        

           runtime (sec) solved instances (%) 99.0% LaCAM* (initial solution) complete eventually optimal LaCAM* establishes a landmark result! Okay, it’s too crazy... remaining 1%: only maze-128-128-1
  54. /73 67        

           runtime (sec) solved instances (%) 0.0% A* [Hart+ 68] 0.4% ODrM* [Wagner+ AIJ-15] 8.3% CBS [Sharon+ AIJ-15; Li+ AIJ-21] 10.7% BCP [Lam+ COR-22] 30.9% I-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] complete solution complete complete solution complete bounded suboptimal bounded suboptimal optimal optimal (unable to identify unsolvable instances) incomplete suboptimal 85.6% LaCAM [Okumura AAAI-23] 99.0% LaCAM* [Okumura IJCAI-23] complete complete eventually optimal suboptimal lose nice props.
  55. /73 68 LaCAM* suboptimally solves MAPF for 10kagents in a

    warehouse-style map with many narrow corridors, in 5 secondson my laptop
  56. /73 71 Jan. 2021. When I was a 1st-year PhD

    student: Centralized pathfinding for 10k agents? You’re a dreamer! To be honest, I agreed at the time.
  57. /73 72 Jan. 2021. When I was a 1st-year PhD

    student: Centralized pathfinding for 10k agents? You’re a dreamer! To be honest, I agreed at the time. LaCAM* 2023 Image by naobimfrom Pixabay
  58. /73 74 Thank you for listening! Acknowledgements to mentors /

    collaborators: X. Defago, Y. Tamura, F. Bonnet, M. Machida, R. Yonetani, M. Nishimura, A. Kanezaki, S. Tixeuil Funding: JSPS DC & Overseas Research Fellowship, JST ACT-X, Yoshida Scholarship Foundation And, A. Prorok + members of PROROK Lab for hosting me at Cambridge! kei18 https://kei18.github.io [email protected] Questions / research collaboration proposals are more than welcome: