Iterative Refinement for Real-Time Multi-Robot Path Planning

IROS-21
https://kei18.github.io/mapf-IR/

Transcript

1. Iterative Refinement for Real-Time Multi-Robot Path Planning Keisuke Okumura, Yasumasa Tamura & Xavier Defago Tokyo Institute of Technology, Japan ౦ژ޻ۀେֶ 5PLZP
   *OTUJUVUF
   PG
   5FDIOPMPHZ Sep. 27th – Oct. 1st, 2021 virtual conf. (Prague) IROS-21
2. /20 2 MAPF: Multi-Agent Path Finding given agents/robots graph goals solution paths without collisions metric sum of traveling time (aka. sum-of-costs)
3. /20 3 Applications YouTube/Mind Blowing Videos Twitter/@PDChina Twitter/@knaohiro1 required: real-time planning with severe deadlines for deliberation time
4. /20 4 Motivation existence of fast and scalable sub-optimal solvers [Wang&Botea ICAPS-08, Surynek ICRA-09, Luna&Bekris IJCAI-11, de Wilde+ AAMAS-13, Okumura+ IJCAI-19, etc] Optimization is intractable in various criteria [Surynek AAAI-10, Yu&LaValle AAAI-13, Yu RA-L-15, Banfi+ RA-L-17, Ma+ AAAI-16] Even with SOTA optimal solvers, still challenging to find good solutions for ≥100 robots within acceptable time [Sharon+ AIJ-15, Lam+ IJCAI-19, etc] Practical scenarios need real-time planning work with ≥1000 robots Iterative refinement of known solutions is promising it is also anytime planning
5. /20 5 Concept – 1/4 how to improve known solutions non-trivial effectively using existing solvers our approach Get initial solutions by sub-optimal solvers 1. - Pickup a subset of robots - Use optimal solvers to refine their paths Repeat: 2. agent goal
6. /20 6 Concept – 2/4 Get initial solutions by sub-optimal solvers 1. - Pickup a subset of robots - Use optimal solvers to refine their paths Repeat: 2. agent goal wait how to improve known solutions non-trivial effectively using existing solvers our approach
7. /20 7 Concept – 3/4 Get initial solutions by sub-optimal solvers 1. - Pickup a subset of robots - Use optimal solvers to refine their paths Repeat: 2. agent goal wait how to improve known solutions non-trivial effectively using existing solvers our approach
8. /20 8 Concept – 4/4 Get initial solutions by sub-optimal solvers 1. - Pickup a subset of robots - Use optimal solvers to refine their paths Repeat: 2. agent goal how to improve known solutions non-trivial effectively using existing solvers our approach *each refinement is completed quickly because sub-problems are much smaller
9. /20 9 before: inefficient planned by Push&Swap [Luna&Bekris IJCAI-11] after our method Example 1/2
10. /20 10 Example 2/2 planning time (sec) cost / lower bond random-64-64-20, 300 robots initial solver: PIBT+ (43ms) [modified version of Okumura+ IJCAI-19] optimal solver: ICBS [Boyarski+ IJCAI-15]
11. /20 11 Limitation: local minimum optimal: 3 + 3 length: k≥6 length: k≥6 initial: 1 + k Corollary 2 Depending on initial solutions, it may be impossible to reach optimal solutions unless selecting all robots as a modification set. Proof sketch. i.e., solving original problem modif.: modif.:
12. /20 12 Design of Modification Set ideal: as small as possible, with great potential for improvements
13. /20 13 Selecting rule: focusing-at-goals – 1/3 original plan refined plan -2 cost effective for inefficient solutions intuition: extracting a set of robots that prevent earlier arrival of one robot modification set = { robots who use ’s goal at timestep t, ideal cost of ≤ t < real cost of }
14. /20 14 Selecting rule: using-MDD – 2/3 effective for efficient solutions t=0 t=1 t=2 t=3 MDD for by t=2 stay turn out to be invalid MDD Multi-valued Decision Diagram [Srinivasan+ ICCAD-90] intuition: extracting a set of robots that prevent earlier arrival of one robot MDD for by t=3 If ‘s MDD is updated by ‘s path => two robots are interacting modification set = { robots that update MDD for by timestep t, ideal cost of ≤ t < real cost of }
15. /20 15 Selecting rule: composition – 3/3 effective for efficient solutions using-MDD effective for inefficient solutions focus-at-goals e.g., focusing-at-goals => using-MDD => random composite these rules switching: when no improvement is achieved for all robots *for other rules, check the paper
16. /20 16 Evaluation
17. /20 17 v.s. Optimal Solutions 1.00 1.05 1.10 1.15 1.20 1.25 1.00 1.05 1.10 1.15 1.20 1.25 50 instance 50 instance cost / optimal cost init ≤ 3ms 0.1s 1.0s 30 agents random-32-32-20 50 agents random-32-32-10 obtained by CBSH [Li+ IJCAI-19] 740ms for 30 agents, 1743ms for 50 agents initial solver: PIBT+ refine rule: composition refinement solver: ICBS refinement timeout: 100ms the refinement converges to the optimal in a very short time
18. /20 18 v.s. Anytime MAPF Solver initial solver: PIBT+ refine rule: composition refinement solver: ICBS refinement timeout: 100ms ave. of 25 instances Iterative Refinement Anytime Focal Search [Cohen+ IJCAI-18] 50 robots 70 robots 90 robots 0 2 4 6 8 10 0 1 2 runtime (sec) sum-of-cost random-32-32-20 10^3 get better results earlier
19. /20 19 with Different Initial Solvers refine rule: composition refinement solver: ICBS refinement timeout: 500ms ave. of 25 instances 0 10 20 30 40 50 60 70 80 90 1.0 1.1 1.2 runtime (sec) cost / lower bound 300 agents random-64-64-20 PIBT+ WHCA* [Silver AIIDE-05] HCA* [Silver AIIDE-05] ECBS [Barer+ SoCS-14] RPP [Cap+ T-ASE-15] not so different
20. /20 20 Concluding Remarks *This work is parallel to MAPF-LNS [Li+ IJCAI-21] framework of iterative refinement our approach target real-time path planning for multiple robots design good selection rules with theoretical guarantee future directions using optimal solvers to refine solutions further analysis of local minimum