Remove Assumptions in Multi-Agent Pathfinding

Keisuke Okumura | 奥村圭祐

February 13, 2024

Tweet Share

Transcript

1. Scalability Assumptions Keisuke Okumura1,2 12th Feb. 2024, idealworks, Munich 1University

   of Cambridge 2National Institute of Advanced Industrial Science and Technology (AIST), Japan kei18 https://kei18.github.io[email protected] Remove Assumptions in Multi-Agent Pathfinding Image by Gordon Johnson from Pixabay

2. /92 2 AP Photo/Ross D. Franklin Ross D. Franklin /

   AP Photo "Swarm" automation is ubiquitous

3. /92 4 underlying common problem: Okumura & Defago. IJCAI-23 collision-free

   pathfinding for multiple agents

4. /92 5 given agents graph goals solution paths without collisions

   cost total travel time, distance, makespan, etc MAPF: Multi-Agent Path Finding

5. /92 6 CBS Sharon+ AAAI-12 -> AIJ-15 ICTS Sharon+ IJCAI-11

   -> AIJ-12 two-level search HCA* Silver AIIDE-05 Prioritized Planning Erdmann+ 87 decoupled planning A*+ID+OD Standley AAAI-10 M* Wagner+ IROS-11 -> AIJ-15 search for joint state space Push & Swap Luna+ IJCAI-11 Push & Rotate De Wilde+ AAMAS-13 -> JAIR-14 rule-based SAT-based Surynek+ ECAI-16 multiflow-based Yu+ WAFR-12 -> T-RO-16 reduction-based Sorry but I cannot list everything… PBS Ma+ AAAI-19 BCP Lam+ IJCAI-19 -> COR-22 extending two-level LNS Li+ IJCAI-21, AAAI-22 LaCAM* Okumura AAAI-23, IJCAI-23 meta-algo. PIBT Okumura+ IJCAI-19 -> AIJ-22 extremely scalable EECBS Li+ AAAI-21. CBSH Felner+ ICAPS-18 ICBS Boyarski+ IJCAI-15 ECBS Barer+ SoCS-14 CBS family +various enhancements on CBS MAPF Algorithm Forest 2012 1st Workshop on MAPF 2010 2019 3rd WoFMAPF 2023 5th WoMAPF my Ph.D.

6. /92 7 Recent methods can solve MAPF for 10k agents

   in 5 seconds on my laptop Okumura, K., Machida, M., Défago, X., & Tamura, Y. Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding. AIJ. 2022. Okumura, K. Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding. IJCAI. 2023.

7. /92 8 But are MAPF algorithms deploy-ready? MAPF's development is

   remarkable.

8. /92 9 Real world is more complicated typical research rotation

   aggressive moves sometimes unavailable task interaction what the industry expects asynchrony heterogeneity continuous space imperfect execution, sometimes crash com m . delay algorithms work with X agents with Y (≪ X) real agents

9. /92 10 to keep MAPF alive increase X decrease ||X

   – Y|| algorithms work with X agents with Y (≪ X) real agents lab research real world strategy-1: strategy-2:

10. /92 11 to keep MAPF alive increase X decrease ||X

    – Y|| algorithms work with X agents with Y (≪ X) real agents lab research real world strategy-1: strategy-2:

11. /92 12 One Reason for Strategy-1: Feedback Control system (e.g.,

    warehouse) query MAPF plan state e.g., 1~10s uncertainties

12. /92 13 ~2023 2024 random-32-32-20, 409 agents, 30s timeout Okumura,

    K. Engineering LaCAM∗: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding. AAMAS. 2024. There are sufficiently scalable methods

13. /92 14 to keep MAPF alive increase X decrease ||X

    – Y|| algorithms work with X agents with Y (≪ X) real agents lab research real world strategy-1: strategy-2: Lets’ remove assumptions in MAPF!

14. /92 15 Outline Remove assumptions of: synchronized actions without crashes

    execution pre-defined discrete space homogeneous agents representation

15. /92 16 Outline Remove assumptions of: synchronized actions without crashes

    execution pre-defined discrete space homogeneous agents representation

16. /92 17 Failure Demo of Synchronous Execution

17. /92 18 Financial Times, https://www.ft.com Miscoordination triggers tragedy We need

    safe methods Let’s think about timing uncertainties

18. /92 19 1 2 1 2 3 4 Planning Execution

    Delay Imperfect Execution

19. /92 20 1 2 1 2 3 4 Planning Execution

    wait make agents wait for delayed ones arrival time: 3 Conservative: Synchronize Forcibly

20. /92 21 Čáp, M., Gregoire, J., & Frazzoli, E. Provably

    safe and deadlock-free execution of multi-robot plans under delaying disturbances. IROS. 2016. Ma, H., Kumar, T. S., & Koenig, S. Multi-agent path finding with delay probabilities. AAAI. 2017. check temporal dependencies 1 2 1 2 3 4 => preserved, go arrival time: 2 1 2 1 2 3 4 Planning Execution Progressive: Preserve Temporal Dependencies

21. /92 22 1 2 1 2 3 4 1 2

    3 4 5 6 delay delay propagation Typical MAPF agents actions complicated dependencies Really Smart?

22. /92 23 Raspberry Pi x8 32 robots Bluetooth Expensive Communication

    Cost stable network / monitoring systems for ≥1000 agents…? NON-TRIVIAL!!

23. /92 24 online intervention at runtime to preserve timing-property abandon

    all timing assumptions

24. /92 25 at Dalí Paris Time-Independent Multi-Agent Path Planning

25. /92 26 Okumura, K., Bonnet, F., Tamura, Y., & Défago,

    X. Offline Time-Independent Multiagent Path Planning. T-RO. 2023. (extended from IJCAI-22) OTIMAPP solution 2 1 4 3 0 0 1 2 MAPF solution weak to timing uncertainties OTIMAPP: Planning with Timing Uncertainties

26. /92 27 given start goal graph solution path s.t. all

    agents eventually reach goals regardless of action orders Problem Def. OTIMAPP

27. /92 28 no reachable* cyclic deadlock no reachable* terminal deadlock

    *non-reachable deadlocks exist two conditions are necessary & sufficient Solution Analysis

28. /92 29 Computational Complexity 1. finding solutions is NP-hard 2.

    verification is co-NP-complete main observations OTIMAPP is computationally intractable the proofs are reductions from 3-SAT

29. /92 30 MAPF avoids collisions OTIMAPP avoids deadlocks MAPF algorithms

    are applicable How to solve OTIMAPP? prioritized planning deadlock-based search extending conflict-based search [Sharon+ AIJ-15] extending conventional PP [Erdmann+ Algorithmica-87] agents             random-32-32-10 32x32             random-64-64-10 64x64             den520d 257x256 success rate (%) ≤ 5 min Both methods can solve large OTIMAPP instances to some extent

30. /92 31 centralized style decentralized style no synchronization only local

    interactions Execution Demo all robots are guaranteed to reach their goals with AFADA [Kameyama+ ICRA-21] with toio obots

31. /92 32 planning stage execution stage Conventional MAPF Solution Concept

32. /92 33 eventually reaching goal status agents reactively switch executing

    plan OTIMAPP Solution Concept

33. /92 34 timing uncertainties crash faults

34. /92 35 goal start graph solution Conventional Solution Concept 0

35. /92 36 with Unforeseen Crash 1 crash detected => then?

    crashed (forever stop) online replanning offline approach: preparing backup paths from the beginning or

36. /92 37 Fault-Tolerant Solution Concept 0 primary path backup path

    when is detected transition rule &

37. /92 38 1 Fault-Tolerant Solution Concept

38. /92 39 2 Fault-Tolerant Solution Concept

39. /92 40 3 Fault-Tolerant Solution Concept done! more than two

    agents may crash => backup path of backup path

40. /92 41 Okumura, K., Tixeuil, S. Fault-Tolerant Offline Multi-Agent Path

    Planning. AAAI. 2023. MAPPCF: Planning with Crash Faults fault solution multiple paths assuming crashes change executing path on-demand

41. /92 42 Problem Definition of MAPPCF centralized planning followed by

    decentralized execution given solution s.t. all non-crashed agents eventually reach their destination, regardless of crashes (up to f ) & transition rules & maximum number of crashes f defined with failure detector & execution model Check the paper for details.

42. /92 43 Failure Detectors c.f., Chandra+ JACM-96 oracle that tells

    status of neighbor vertices response: 1. no agent query 2. non-crashed agent named FD 3. crashed agent anonymous FD unable to identify who crashes

43. /92 44 Execution Models synchronous model all agents act simultaneously

    solutions avoid collisions MAPF: multi-agent pathfinding Stern+ SOCS-19 solution solutions avoid deadlocks each agent acts spontaneously while locally avoiding collisions offline time-independent MAPP Okumura+ T-RO-23 sequential model (async) solution possible schedule how agents are scheduled at runtime

44. /92 45 Model Power Analyses synchronous model sequential model named

    failure detector anonymous FD SYN SEQ NFD AFD solvable in SYN unsolvable in SEQ SYN + AFD SYN + NFD SEQ + NFD SEQ + AFD weakly stronger SYN+AFD SYN+NFD SYN+AFD SYN+NFD or strictly stronger SEQ+AFD SYN+AFD solvable instances

45. /92 46 Computational Complexity 1. finding solutions is NP-hard 2.

    verification is co-NP-complete regardless of FD types or execution models MAPPCF is computationally intractable the proofs are reductions from 3-SAT

46. /92 47 Solver / Empirical Results MAPPCF provides better solution

    concept than finding disjoint paths random-32-32-10 32x32 (|V|=922) from [Stern+ SOCS-19] 30sec timeout with named FD         success rate #agents DCRF/SYN disjoint paths fixed #crashes: f =1 adapted from CBS [Sharon+ AIJ-15] v.s. finding vertex disjoint paths         costs / lower bound #agents DCRF/SYN disjoint paths traveling time when no crashes We develop DCRF (decoupled crash faults resolution framework) to solve MAPPCF

47. /92 48 Summary in Execution planning execution reality gaps new

    solution concept: offline planning with reactive execution in practice? => hybrid of (relaxed) offline & online planning

48. /92 49 Outline Remove assumptions of: synchronized actions without crashes

    execution pre-defined discrete space homogeneous agents representation

49. /92 50 MAPF Definition Again given agents (starts) graph goals

    solution paths without collisions reality is continuous

50. /92 51 Why not move diagonally? Robots follow grid Cool

    coordination but not efficient! Okumura, K., & Défago, X. Solving simultaneous target assignment and path planning efficiently with time-independent execution. AIJ. 2023. (extended from ICAPS-22; best student paper)

51. /92 52 obstacle Unsolvable Instance?

52. /92 53 Multi-Agent Path Planning in Continuous Spaces given agents

    (starts) workspace goals solution paths without collisions Finding solutions itself is tremendously challenging Spirakis, P., & Yap, C. K. Strong NP-hardness of moving many discs. IPL. 1984. Hopcroft, J. E., Schwartz, J. T., & Sharir, M. On the Complexity of Motion Planning for Multiple Independent Objects; PSPACE-Hardness of the" Warehouseman's Problem". IJRR. 1984.

53. /92 54 artificial potential field sampling-based rule-based goal start constructing

    roadmap Strategies to Solve Single-Agent Path Planning in Continuous Spaces

54. /92 55 state of robot: (x, y) (x, y) should

    be in this region configuration space random sampling & construct roadmap pathfinding on roadmap same scheme even in high-dimension SBMP: Sampling-Based Motion Planning

55. /92 56 Naïve Strategy to Solve Multi-Agent Path Planning in

    Continuous Spaces 1. 2. two-phase planning Construct agent-wise roadmaps by some means, e.g., SBMP (sampling-based motion planning) Solve MAPF on those roadmaps ready for heterogeneity between agents

56. /92 57 Pitfall – There is a trade-off quality &

    solvability planning effort small large speed & scalability complete optimal incomplete suboptimal dense representation sparse representation produced by PRM [Kavraki+ 96] ideal: small but promising representation for planning

57. /92 58 Countermeasure biased sampling sampling from important region of

    each agent how to identify? agent-specific features + interactions between agents 🤔 design manually?

58. /92 59 Countermeasure This is machine learning problem! supervised learning:

    planning demonstration as training data biased sampling sampling from important region of each agent how to identify? agent-specific features + interactions between agents

59. /92 60 offline training: predict next locations from planning demo

    online inference: generate agent-specific roadmaps use ML-model as an interaction-aware vertex sampler MAPF CTRMs: Data-Driven Roadmap Construction 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.

60. /92 61 new instance 𝐹!"#$ random walk sampling module next

    locations starts path generation compositing solution MAPF algorith m … t=0 t=1 t=2 CTRMs 𝐹!"#$ model training instances & solutions predict next locations Online Inference Offline Training CVAE: Conditional Variational Autoencoder [Sohn+ NeurIPS-15] +importance sampling [Salzmann+ ECCV-20] +multi-agent attention [Hoshen NeurIPS-17] 𝐹!"#$ : *independent from map size and #agent, not limited to homo-agents Pipeline

61. /92 62 new instance 𝐹!"#$ random walk sampling module next

    locations starts path generation compositing solution MAPF algorith m … t=0 t=1 t=2 CTRMs 𝐹!"#$ model training instances & solutions predict next locations Online Inference Offline Training CVAE: Conditional Variational Autoencoder [Sohn+ NeurIPS-15] +importance sampling [Salzmann+ ECCV-20] +multi-agent attention [Hoshen NeurIPS-17] 𝐹!"#$ : *independent from map size and #agent, not limited to homo-agents Pipeline

62. /92 63 occupancy cost-to-go env. info Offline Training & Model

    Arch. – 1/5 𝐹!"#$ next position generative model CVAE [Sohn+ NeurIPS-15] features ?

63. /92 64 + + relative positions, size, speeds, etc goal-driven

    features Offline Training & Model Arch. – 2/5

64. /92 65 + + communication features learning interactions with nearby

    agents m ultiple agents multi-agent attention [Sohn+ NeurIPS-15] Offline Training & Model Arch. – 3/5

65. /92 66 go right [0,0,1] indicator feature Offline Training &

    Model Arch. – 4/5

66. /92 67 + + + + go right [0,0,1] 𝐹!"#$

    next position goal-driven features comm. features indicator feature instance & solution occupancy cost-to-go env. info relative positions, size, speeds, etc attention Offline Training & Model Arch. – 5/5

67. /92 68 new instance 𝐹!"#$ random walk sampling module next

    locations starts path generation compositing solution MAPF algorith m … t=0 t=1 t=2 CTRMs 𝐹!"#$ model training instances & solutions predict next locations Online Inference Offline Training CVAE: Conditional Variational Autoencoder [Sohn+ NeurIPS-15] +importance sampling [Salzmann+ ECCV-20] +multi-agent attention [Hoshen NeurIPS-17] 𝐹!"#$ : *independent from map size and #agent, not limited to homo-agents Pipeline

68. /92 69 observations for agent-i next predicted location for agent-i

    trained model likely to be used by planners Online Inference – 1/4

69. /92 70 timestep t timestep t+1 next predicted locations for

    all agents observations for all agents Online Inference – 2/4

70. /92 71 t=0 t=1 t=2 t=T t=T-1 … initial locations

    timed path for agent-i each path is agent-specific and cooperative hyperparameter Online Inference – 3/4

71. /92 72 … … … … compositing t=0 t=1 t=2

    t=T t=T-1 timed roadmap for agent-i each roadmap is agent-specific and cooperative hyperparameter: #(path generation) Online Inference – 4/4

72. /92 73 SPARS [Dobson & Bekris, IJRR-14] (random) simplified PRM

    [Karaman & Frazzoli, IJRR-11] square as agent-specific roadmaps grid as used in MAPF studies CTRMs 20-30 homogeneous agents corresponding to 32x32 grids CTRMs produce small but effective roadmaps specific to each agent Roadmap Visualization

73. /92 74 S R P R R R 50 RP

    3 5 T 20-30 homogeneous agents corresponding to 32x32 grids 100 instances solved by prioritized planning [Silver, AIIDE-05, Van Den Berg & Overmars IROS-05, etc] CTRMs reduce planning effort while keeping solution qualities params of CTRMs: #(path generations) denser denser Quantitative Results

74. /92 75 quality & solvability planning effort small large speed

    & scalability building representation from learning building representation while planning Yet Another Strategy for Representation

75. /92 76 Recap: Naïve Strategy to Solve Multi-Agent Path Planning

    in Continuous Spaces Construct agent-wise roadmaps by some means, e.g., SBMP (sampling-based motion planning) Solve MAPF on those roadmaps 1. 2. two-phase planning

76. /92 77 Pitfall Construct agent-wise roadmaps by some means Solve

    MAPF on those roadmaps 1. 2. two-phase planning Roadmaps truly used in planning process? decoupled

77. /92 78 Advanced Strategy Construct agent-wise roadmaps by some means

    Solve MAPF on those roadmaps 1. 2. develop agent-wise roadmaps according to MAPF search progress coupled

78. /92 79 SSSP: simultaneous sampling-and-search planning Okumura, K., & Défago,

    X. Quick Multi-Robot Motion Planning by Combining Sampling and Search. IJCAI. 2023. solve various types of MRMP rapidly

79. /92 80 Each robot operates in its own configuration space

    Each robot has initial and goal configurations solution: collision-free trajectories in continuous spaces allowing heterogeneity allowing kinematics/dynamics* constraints extremely challenging! MRMP: Multi-Robot Motion Planning *not addressed in this study

80. /92 81 How to Solve MRMP? Construct agent-wise roadmaps by

    SBMP Solve MAPF on those roadmaps 1. 2. coupled

81. /92 82 quick MRMP multi-robot motion planning PRM [Kavraki+ 96]

    EST [Hsu+ ICRA-97] RRT [LaValle 98] RRT-Connect [Kuffner+ ICRA-00] PRM*/RRT* [Karaman+ IJRR-11] SPARS [Dobson+ IJRR-14] FMT* [Jason+ IJRR-15] + SBMP: sampling-based motion planning A*+OD [Standley AAAI-10] CBS [Sharon+ AIJ-15] M* [Wagner+ AIJ-15] PBS [Ma+ AAAI-19] BCP [Lam+ COR-22] LNS [Li+ IJCAI-21; AAAI-22] LaCAM* [Okumura AAAI-23; IJCAI-23] + MAPF: multi-agent pathfinding search roadmap seamless integration Algorithm Design

82. /92 83 PRM [Kavraki+ 96] EST [Hsu+ ICRA-97] RRT [LaValle

    98] RRT-Connect [Kuffner+ ICRA-00] PRM*/RRT* [Karaman+ IJRR-11] SPARS [Dobson+ IJRR-14] FMT* [Jason+ IJRR-15] + SBMP: sampling-based motion planning A*+OD [Standley AAAI-10] CBS [Sharon+ AIJ-15] M* [Wagner+ AIJ-15] PBS [Ma+ AAAI-19] BCP [Lam+ COR-22] LNS [Li+ IJCAI-21; AAAI-22] LaCAM* [Okumura AAAI-23; IJCAI-23] + MAPF: multi-agent pathfinding Algorithm Design seamless integration search roadmap example algorithm: SSSP Please check the paper for details! building representation while planning

83. /92 84        

      runtime (sec) solved instances (%) Point2d DOF: 2N - 100 instances with 10 random seeds - each instance is randomly generated - number of robots: 2–10 - heterogeneous robots Comparison with Standard Approaches

84. /92 85 RRT-Connect [Kuffner+ ICRA-00] RRT [LaValle 98] PRM [Kavraki+

    96] CBS [Sharon+ AIJ-15] on PRMs (with adjusted heuristics) PP [Silver AIIDE-05] on PRMs SSSP two-phase planning direct application of SBMP           runtime (sec) solved instances (%) Point2d DOF: 2N - 100 instances with 10 random seeds - each instance is randomly generated - number of robots: 2–10 - heterogeneous robots Comparison with Standard Approaches

85. /92 86        

      runtime (sec) solved instances (%) Point2d DOF: 2N Point3d DOF: 3N Line2d DOF: 3N Capsule3d DOF: 6N Arm22 DOF: 2N Arm33 DOF: 6N Dubins2d DOF: 3N Snake2d DOF: 6N

86. /92 87        

      runtime (sec) solved instances (%) SSSP can quickly solve various MRMP

87. /92 88

88. /92 89 Summary in Representation quality & solvability planning effort

    small large speed & scalability building representation from learning building representation while planning

89. /92 90 to keep MAPF alive increase X decrease ||X

    – Y|| lab research real world strategy-1: strategy-2: Lets’ remove assumptions in MAPF! Specifically: synchrony, without faults, continuous spaces, heterogeneity Overall Summary algorithms work with X agents with Y (≪ X) real agents

90. /92 91 Takeaways + Personal Feelings Scalable MRMP methods have

    not appeared. But we have some clues from LaCAM* and SSSP. I believe the last piece is learning. Even when assumptions are removed, basic MAPF algorithms serve as the foundation. Adding robustness/resilience is expensive, but worth investigating because MAPF systems will be future infrastructure; this area is still primitive.

91. /92 92 Thank you for listening! Acknowledgements to mentors /

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