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

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.

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

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

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.

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

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)

(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.

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

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

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

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

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.

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

[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

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

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

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

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

– 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

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.

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: