Navigation for a team of agents

「エージェント群のナビゲーション」
招待講演(2h)@組合せ遷移・第27回セミナー資料
https://core.dais.is.tohoku.ac.jp/report/event/detail/---id-124.html

Transcript

1. !" #$ !"#$%& '()#&* ౦ژ޻ۀେֶ 5PLZP
   *OTUJUVUF
   PG
   5FDIOPMPHZ !"#$%&'()*+",-% Jul. 11th, 2022 27th CoRe Seminar
2. /123 2 !"#$%& '()#&* +,-. (2020–) /01234DEFAGO Xavier 15 https://kei18.github.io/ @_kei18 !"#$%&' ()*+,-./0123456789 AI & Robotics / Multi-Agent Planning / Multi-Robot Coordination Keisuke Okumura | !"#$ JSPS DC1 (20–) YKK Doctor21 (20–) Miyake Lab, TokyoTech (16–20) NEC R&D (18) OMRON SINIC X (21) LIP6, Sorbonne Univ. (22) career / intern Next…?
3. /123 3 Opening
4. /123 4 !"#$%&'()*&+, -./01234 YouTube/Mind Blowing Videos :,;<=>; YouTube/WIRED ?@ABC+DE. YouTube/Tokyo 2020 *.FG (+,-./)
5. /123 5 67 89 :; <=>?@ AB CD !"#$ 5+6789"&:";<% EFGHGI><=>JKLMNO>&P>QRSTUVWGX>YZ[G\]ULMGI^_ %&
6. /123 6 `a %&'( TUVWGX )*+,+- .#/0 HIJK !"#$%&=>8?@%A%B & CD
7. /123 7 `a1 %&'( `a2 LMNOP QR'SP !"#$%&'()*+",-% )*+,+- .#/0 HIJK T#P U2VWXYZ
8. /123 8 ./!"#$%&'0 123456789:;<=>?@ bcRdef>gGhQGi>jkAl^m nop>%qr>sta uGvJuwxN>JyOX>zVbTGX … [\]^ _`.a.b Jcde 1 2
9. /123 9 [Zhang 18] {|}b~U•€G YouTube/StarCraft •hg‚Uf [van den Berg+ ISRR-11] NFƒi•w]zU•€G [Song+ ICCBB-01] „… [Flatland Challenge, AIcrowd] †‡ YouTube/Mind Blowing Videos JVOLMNO [Zhang+ SIGGRAPH-20] ˆ‰R [Le Goc+ UIST-16] eGdU{WUO '()*+,-./0123(4%56789 :;<=0>*.?*@A-B0
10. /123 10 EFGHIJKLMN 3456786, 9:;.<=>, ?@ABCD+EFGHI>FGJB KLMN+OPEQRSLTU+V WXYZ / C[\]^_:`aVbcB8d efg:`hij)CLklmZ>FGJB
11. /123 11 Outline C[nOP>E.# opqr>E)*+,+- DskKLMN+Otuvw MAPF; Multi-Agent Path Finding /123
12. /123 12 Outline C[nOP>E.# opqr>E)*+,+- DskKLMN+Otuvw MAPF; Multi-Agent Path Finding /123
13. /123 14 MAPF: Multi-Agent Path Finding given agents (starts) graph goals solution paths without collisions
14. /123 15 OPQ8RS T CDUVR fgb`?hSJcijk1lm%&'no# NP pq [Nebel ICAPS-20] rgb`?hS pebble motion problem sktu7 k#$vw O(n^3) xs)ysJcijk1z{hy% [Kornhauser 84, Röger+ SOCS-12, Yu+ WAFR-15] n: |}~, F•/ €•‚ƒZhk„%* …†S 3-SAT ‡ˆs‰Šu7 (‹Œ) wikipedia *0123 8•Ž••‘’“fgb`?h$vw€•‚ƒZhk„% [Boeta+ JAIR-18]
15. /123 16 wikipedia NxN ”•–s—˜d~slkSNPpq [Ratner+ AAAI-86] WXY,Z[\] qŽ™š, 8•Ž (M›) MAPF Sxœ1•ž
16. /123 17 WXY8^_`a length: k ring makespan: k+1, sum-of-costs: 2k+3 ƒŸx7 makespan: k+2, sum-of-costs: k+6 ƒŸx7 k > 3 h¡ƒ—¢£SHi [Yu+ AAAI-13] ¤. 1. last arrival time (aka. makespan) 2. total arrival time (aka. sum-of-costs, flowtime) 3. total distance G,¥+ 4. max distance
17. /123 18 OPQ8RS T WXY 456 3-SAT 789:;<= makespan sum-of-costs total distance max distance [Surynek AAAI-10, Yu+ AAAI-13, Yu RA-L-15, Ma+ AAAI-16] —¦£Sž§¨ NP pq bB©ª«h makespan, sum-of-costs, total distance —¦£S NP pq [Banfi+ RA-L-17, Geft+ AAMAS-22] makespan —¦£5¬Ž¨ 4/3 -«s®¯k1°%&'S NP pq [Ma+ AAAI-16]
18. /123 19 (xy=;V) bcd/ MAPF 2 eLRfghMN,iJL
19. /123 20 CjkZ[RLlLm\n
20. /123 21 opqrstuvwx y"yz"{ |}z"{ ~•z"{ +z{|L_
21. /123 22 opqrstuvwx; PP: Prioritized Planning D._–, ±9, ™&™&²9k, J³´, Ž‡ŽHµ¶ *+,-./5·¸¹º1»¼¨% 1. ·¸¹º¹5½¾¿ÀÁŸà nÄu7Å9·¸¹º1ÆÀ*+,-./sÁÂ'sÇÈ1É„% 2. ÊËV¹ÌÍ„hÆk„V9 Î]¤: HCA*: Hierarchical Cooperative A* [Silver AIIDE-05] >?@AB3CDEFGH (A* @IJKLMN )@OPQRSTUVWX3YZN Ïд5ѳÒv%&'Æ€9 [Wang+ JAIR-11, Bnaya+ ICRA-14] Ó—¢ÔHµ¶Ôű [Erdmann+ 87] ÕÖ
22. /123 23 ·¸¹ºs»¼s×Ø Ù¼7, ÚÛ7e, ÜÝ+B;<=©>, Þ»¼¨, »¼no1ß+à, áâãä, etc [Azarm+ ICRA-97, Bennewitz+ 02, van Den Berg+ ICRA-05, Andreychuk+ AAMAS-18, Ma+ AAAI-19] RPP: Revisit Prioritized Planning [Cap+ T-ASE-15] well-formed V•.;F.;h$vwµ¶K1å… opqrstuvwx PP 8€*?{ Ðæ´V_`.a.b'sçK#²9 [Velagapudi+ IROS-10, Cap+ T-ASE-15] well-formed ill-formed è*+,-./s;F+/Ôé+–1 MˆV9ÁÂ#êVë'ƽÀSìíž%
23. /123 24 y"yz"{ ’“•‘b`?s–+_Ðk1ѳ: BIBOX [Surynek ICRA-09, Surynek FLAIRS-09] ••‘Ô’“•‘Vfgb`?îsïð [Botea+ JAIR-18] Ó—¢Ôµ¶ÔñűÔ8•ŽÁÂsòS🤔 b`?1óô£, 9ëÀ‡sõ.ö+÷./5Ðk [Ryan JAIR-08] ¶øùsѳ [Peasgood T-RO-08] Push&Swap, Push&Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] _©DÝ6úh*+,-./11¾¿Àé+–5g‡û¨)‡ž üÖ5ýþ¨;ÿ©_6úh2¾s*+,-./sº!1"v#$% %~≥3s&+ª +Ys'(&+ªx2 )*: +,Jc [Sajid+ SOCS-12], ÐæJc [Wiktor+ IROS-14, Wei+ 14, Zhang+ DARS-16, Wang+ RA-L-20, etc] TASS: Tree-based Agent Swapping Strategy [Khorshid+ SOCS-11] Æ¡þušV-•.-
24. /123 25 ~•z"{ —¢Ôµ¶ uëNˆv¨9%/0î12Ž¨3³4–5hkë CSP: 6789/0 [Ryan ICRA-10] SAT: 89ijK/0 [Surynek PRICAI-12, Surynek+ ECAI-16, Surynek+ IJCAI-19] ILP: :~ŸÃ/0 [Yu+ T-RO-16] ASP: k;<_:b`=.b [Erdem+ IJCAI-13] BCP: Branch-and-cut-and-price [Lam+ COR-22]
25. /123 26 |}z"{ —¢Ôµ¶ >?V@$: A* 1¢ýÒA% 1ÀsWX&+ª1 { ž§¨s*+,-./sº! } 5BýÒAvw99 8•ŽWXYZ#2yžC¨d5D$V9 A* with Operator Decomposition & Independent Detection [Standley AAAI-10] MAPF EFsGÍ„H I"Ž9JZKL1M" + ÏÐ/0îsл ^ƒ}h—ÆEFÒv¨9% & N9Od#99s# CBS: Conflict-based Search [Sharon+ AIJ-15]
26. /123 27 CBS: Conflict-based Search[Sharon+ AIJ-15] —¢k! cost: 5 P*+,-./# “9ÀÔÊ&” 1Nû¨9„Vs‡1WXž% 2QRsWX constraint tree sST high-level: low-level: 675Uš—˜ÁÂ1WX t=1 cost: 5 replan stay t=1 cost: 6 replan t=1 t=2 stay cost: 6 replan t=1 t=2 stay cost: 6 replan >?9[\]^_` [Boyarski+ IJCAI-15, Boyarski+ AAAI-21] abcd2OPQRSTUVW [Felner+ ICAPS-18, Li+ IJCAI-19] efgh [Gange+ ICAPS-19] ijk9lm [Li+ AIJ-21] nopq [Boyarski+ IJCAI-20] ML X9rstRVu [Huang+ AAAI-21] vwxDyz{|9}~ (E)ECBS [Barer+ SoCS-14, Li+ AAAI-21] ”ÿ?–Vïð#ìí, e.g., •L€C•‚ƒ„……
27. /123 28 •‚z"{ Ó—¢ÔHµ¶ ès4–5+1Nû¨VW.+F1;m% 1. *+,-./sX)1ãä PF•Y;<©_, %s->DE.1Z[ž%öBD+1ú% 2. öBD+1P*+,-./5¢³Ž¨_`.a.b 3. [Damani+ RA-L-21] A. "\.+Fs]Ÿ B. ãä^.–Ô ?:+s]Ÿ Š‹&P [Sartoretti1+ RA-L-19] GNN [Qingbiao+ IROS-20] … ÕÖ
28. /123 29 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B- with MAPF Benchmark [Stern+ SOCS-19] example, 194x194; 13,214 *•L€%†L„…‡vˆ2‰Š‹` ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
29. /123 30 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
30. /123 31 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
31. /123 32 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B Push & Swap/Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
32. /123 33 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B Push & Swap/Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] & s ` • . 1 _ 78 9 ` ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
33. /123 34 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B Push & Swap/Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] PIBT [Okumura+ AIJ-22] my work! ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
34. /123 35 Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding planning KO, Manao Machida, Xavier Defago & Yasumasa Tamura https://kei18.github.io/pibt2 IJCAI-19 => AIJ-22 MAPF 1abŽkë;C+`A–VÓ—¢-–éB•Y (PIBT) ¶*+,-./#c´d5efž%&'1å… ≥500TUVWGX>50msŒ• Ž•••bg‘’“ gGFeG”•
35. /123 36 locations at t=1 t=2 t=3 repeat one-timestep prioritized planning high low mid How PIBT works – 1/8 … 1 2 3 4 5 6 7 8 9 decision order time-window
36. /123 37 How PIBT works – 2/8 simple prioritized planning is incomplete high low mid stuck
37. /123 38 How PIBT works – 3/8 high low mid as high priority inheritance [Sha+ IEEE Trans Comput-90]
38. /123 39 high low mid How PIBT works – 4/8 1 3 2 decision order … …
39. /123 40 How PIBT works – 5/8 high as high as high as high as high stuck but still not feasible
40. /123 41 How PIBT works – 6/8 invalid valid re-plan re-plan valid You can move invalid You must re-plan, I will stay introduce backtracking
41. /123 42 Proof sketch. highest as high as high ›9œsW{6•žŸ ‚¡… ¢£Y9¤¥¦Qu@Ÿ §L¨“C”©ª œsW{9 D«9¦Qu invalid valid ¬QTQ-®•6¯L°±² How PIBT works – 7/8 +,³ g0: ’“•‘b`?hhS—Å·¸¹ºs*+,-./#ijs'(&+ª5()ij
42. /123 43 g0: ’“•‘b`?hhS—Å·¸¹ºs*+,-./#ijs'(&+ª5()ij How PIBT works – 8/8 kl: (reachability) ž§¨s*+,-./#fmƒZhc´d5efž% +)´V·¸¹º»¼ n•é+–5eŠŽ¨9V9*+,-./#Å9·¸o1ÆÀuš5ž% 9À‡—Å·¸¹º1ÆÀ => g0s¢³
43. /123 44 25!"#$"#, %&'(30), *!+#,"-./01232, 194x19445678 PIBT(+) PIBT (+) PIBT (+) PIBT(+) S'¨Æ;C+`A– & ™&™&²9k !"#$%&'( )!"#*'*&'( !"#+,&'( )!"#$%&'( )!"#-./0 ksò ŸpƒZ {qr PIBT8QV
44. /123 45 Multi-agent Pickup & Delivery Sushi
45. /123 46 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B Push & Swap/Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] PIBT [Okumura+ AIJ-22] ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
46. /123 47 Dy %&'()*+, ƒ„y…†‡ˆ8‰#;<A%B Push & Swap/Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] PIBT [Okumura+ AIJ-22] iterative refinement [Okumura+ IROS-21] large neighborhood search [Li+ IJCAI-21] my work! ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
47. /123 48 planning IROS-21 Iterative Refinement for Real-Time Multi-Robot Path Planning KO, Yasumasa Tamura & Xavier Defago ijsk1"\5'û¨s%tu1cš?v+Yÿ+> wìs MAPF -–éB•Y1xy´5z³ https://kei18.github.io/mapf-IR 300*+,-./ ŸpƒZ ({) õ;/ / «|
48. /123 49 Concept – 1/4 }a4E5~;8d•€•Gh ‚ƒ„gJB …†E‡sˆa~‰6Š~ }‹0 }~k1Ó—¢4–5hű5lm% 1. - 9ëÀ‡*+,-./1Z[ - —¢4–51Nû¨Z[Òv8 *+,-./sÁÂ1tu -«1abž: 2. agent goal
49. /123 50 Concept – 2/4 agent goal wait }~k1Ó—¢4–5hű5lm% 1. - 9ëÀ‡*+,-./1Z[ - —¢4–51Nû¨Z[Òv8 *+,-./sÁÂ1tu -«1abž: 2. }a4E5~;8d•€•Gh ‚ƒ„gJB …†E‡sˆa~‰6Š~ }‹0
50. /123 51 Concept – 3/4 agent goal wait }~k1Ó—¢4–5hű5lm% 1. }a4E5~;8d•€•Gh ‚ƒ„gJB …†E‡sˆa~‰6Š~ }‹0 - 9ëÀ‡*+,-./1Z[ - —¢4–51Nû¨Z[Òv8 *+,-./sÁÂ1tu -«1abž: 2.
51. /123 52 Concept – 4/4 agent goal –—˜™Yš›^kœ•’MAPFcRžb‰fœŸ ¡¢£¤¥¦ }~k1Ó—¢4–5hű5lm% 1. }a4E5~;8d•€•Gh ‚ƒ„gJB …†E‡sˆa~‰6Š~ }‹0 - 9ëÀ‡*+,-./1Z[ - —¢4–51Nû¨Z[Òv8 *+,-./sÁÂ1tu -«1abž: 2.
52. /123 53 Dy %&'()*+, Push & Swap/Rotate [Luna+ IJCAI-11, de Wilde+ AAMAS-13] EECBS [Li+ AAAI-21] HCA* [Silver AIIDE-05] BCP [Lam+ COR-22] CBS [Sharon+ AIJ-15, Li+ AIJ-21] PIBT [Okumura+ AIJ-22] iterative refinement [Okumura+ IROS-21] large neighborhood search [Li+ IJCAI-21] Š‹"Œ/ MAPF 8W•Ž ~•¾34sbB©ª€5mkž%Vˆ 10{Æ$vw•Ms`©_/©_h‡V7²9k#°ˆv% ./01*+, ~100ŒQ•Ž••-‘’ %“”•–—€˜™Ll`… ≥1000ŒQ•Ž••-‘š
53. /123 54 MAPF 8••‘’
54. /123 55 MAPD: Multi-agent Pickup & Delivery delivery loc. pickup loc. given agents graph package ‚ƒs„…†‡14Ž8/0]k [Ma+ AAMAS-17] solution paths without collisions task assignment PIBThˆ5k„% / Æ'Æ'S‰.`•.s]k•#‰?`•.s]kÆ [Liu+ AAMAS-19]
55. /123 57 Unlabeled/Anonymous MAPF given agents (starts) graph targets solution paths without collisions target assignment
56. /123 58 Unlabeled-MAPF ,C,Rt“”L G•>;”.—¢£S—2?:+/0îsŠ‹5u7€•‚ƒZhk„%?! [Yu+ WAFR-13] unlabeled-MAPF •.;F.; source sink t=0 t=1 time expanded network512 Œs •ŽS ž§¨1 ¤$w Ford-Fulkerson s-–éB•Yh—2?:+/01kë' O( *+,-./~ x |}~ x G•>;”.) —2?:+: 1 Jcijk#V9 source sink t=0 t=1 t=2 —2?:+: 2 makespan—¢Vk
57. /123 59 Unlabeled-MAPF f•–N—kRtKL ŸpShy%#ƒZ'G^B1•š *assuming |𝐸| = 𝑂(|𝑉|) MAPF benchmarks [Stern+ SOCS-19] 418x530 43,151 257x256 28,178 194x194 14,784 |𝑉| [Yu+ WAFR-13] G•>;”.—¢kS 𝑂( 𝐴 ⋅ 𝑉 ()* hln%
58. /123 60 planning execution Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution KO & Xavier Defago ˆdUG§¨ ©ªt«¬ ≥1000TUVWGX 1-Œ• F+•©/»¼'ÁŸÃ1¡ƒ5këÓ—¢Ôµ¶V-–éB•Y(TSWAP) ‰?`•.Ô‰.`•.ŸÃs‘’hN$% https://kei18.github.io/tswap The Best Student Paper Award! ICAPS-22
59. /123 61 Proposed Algorithm: TSWAP ijsF+•©/»¼1lm% Step 1. dU‚xX®8¯m^°±1OLxEkEFGHGI®²³´ Step 2. 𝑂( 𝐴 ( ⋅ 𝑑𝑖𝑎𝑚 𝐺 ⋅ (𝛼 + 𝛽)) ´µgh+¶Vu¬VW·) ÕÖ 2000 agents [Yu+ WAFR-13] optimal algorithm TSWAP 56.3 89.8 230.2 0.4 0.4 1.1 1.36 1.17 1.02 ŸpƒZ({) Ó—¢K (makespan) lak303d den520d brc202d “”¤
60. /123 62 swap targets rotate targets shortest path move shortest path TSWAP F+•©/1•2ŽV#ˆ1;<©_s_`.a.b1abž Step 2. stay currently assigned target stay (otherwise) 456¸T•-¹{º‘@Z», XY€-•¼{½
61. /123 63 2y9*+,-./ [Thomas+ 15, Li+ AAAI-19, Atzmon+ SOCS-19] Any-angle MAPF [Yakovlev&Andreychuk ICAPS-17] Multi-Goal [Surynek AAAI-21, Zhang+ AAMAS-22] ˜8™8 MAPF 8š›Kœ (un)-labeled MAPF1 ½–£: TAPF [Ma+ AAMAS-16] *+,-./# —v%‡ÆŽvV9MAPF [Atzmon+ JAIR-20, Atzmon+ ICAPS-20, Shahar+ JAIR-21] 1 2 1, 2 3 4 ()ƒZ5Ir1M" [Peltzer+ 19] MAPFR : Œ5“˜1M" [Walker+ IJCAI-18] 3 2 •™ƒZ: Continuous MAPF [Andreychuk+ AIJ-22] VÊVÊ
62. /123 64 http://mapf.info/ ¬•ž%š›œ• IJCAI, AAAI AAMAS ICAPS ICRA, IROS, WAFR SOCS general AI ž–à*+,-./ AI_`.a.b :Ÿ<=>; <AWX … š¡sõ=Ýa<= 8¢ËìíŽV9… £Ñß•/ •–N•žKL] https://github.com/Kei18 5¤¥¦§Ž¨nž ¤¥¨Ëh˜89
63. /123 65 Outline C[nOP>E.# opqr>E)*+,+- DskKLMN+Otuvw MAPF; Multi-Agent Path Finding /123
64. /123 66 Failure Demo of PIBT
65. /123 67 access:. 6th Jun. 2022 https://www.ft.com/content/aaddf4b1-a78b-4289-b42f-fd3f5cd7f176 “appears to have been caused by the collision of three bots on the grid” “more than 1,000 robots buzz around a grid, stopping to grab crates of food” CDEF9GDH
66. /123 68 IJK./F078 LM-N-O PQPRSTUKL µ¶, ObxE, ·G¸UTFU, 9¹º», yxLbU¼½, OdxNgUyU{JU, @¾, JKxX¿kÀÁÂ, ÃÄÅk^˜yI, etc VWG78XYZ[\
67. /123 69 MAPF-POST[Hönig+ ICAPS-16] 2 moves 2 moves +1 turn model: execution: J:Ÿ©/sX)1r© MAPF plan 1ª«l †)ã´671¬8ž;C,Ý+–1z{ A B C D E B C F C D ƒZ´¹Ì¬-1ó® A B C D E B C F C D 5 0 0 16 25 32 48 29 33 64 —˜J^ƒZ1lm% E D A B B C … 0 0 0 0 -1 ∞ -2 -1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0 0 -4 -8 -4 ∞ ¯°b`?512 E D A B B C … [1,∞] source sink [0,0] [0,0] [1,∞] [2,∞] [8,∞] [4,∞] [4,∞] [0,∞] [0,∞ ] [0,∞ ] )ú5Öž%ƒZ1-&<+DE. c.f., STN: simple temporal network [Dechter+ AIJ-91] ¾¿LÀ¢… [DÁ™Â, D%™Â] t=1 t=2 t=3 t=4 t=0 "\: MAPF plan A B C F D E
68. /123 70 2•(Ÿ{&/CD2,/L ¡] 2(34356789:;<=>?@AB ACDEFGH? or IDIDJK
69. /123 71 1 2 1 2 3 4 Planning Execution Delay
70. /123 72 1 2 1 2 3 4 Planning Execution ¢£/„?("€ – ¤¥¦§ wait arrival time: 3 †ˆ‡5r±#€™š… —²Ž8*+,-./1¶*+,-./#³À
71. /123 73 •[¨J©£/ª« – q¬`-8®¯ [Cap+ IROS-16, Ma+ AAAI-17] Œr=•Ž••akNn^ 1 2 1 2 3 4 => ‘’, GO arrival time: 2 1 2 1 2 3 4 Planning Execution 1 2 3 4 0 1 2 3 4 progress )Æ Ä« ´^/µ+
72. /123 74 E°k©£\] 1 2 1 2 3 4 1 2 3 4 5 6 delay negative effect 60 agents, solved by PIBT ¶·´V MAPF •.;F.; LMNOGPQH agents actions
73. /123 75 Raspberry Pi x8 32 robots Bluetooth ABCD(EF8G HI&J77<K 1000¾34s:Ÿ©/0s8ms ¸kŽ8÷©/ÿ+>[\…? nû8ën†hSV9
74. /123 76 CD±k²()*&f ³A´†%B'µ¶·¸”h¹«,ºL
75. /123 77 ?@%A%B28 »¼k`”h½¾f”¿l Àl6Á L82,]
76. /123 78 »¼ÂÃÄ/ Åy€!"#$%&uvwx @ÇbÈÉÊ>ˆb /121
77. /123 79 OTIMAPP solution multi-agent pathfinding solution 2 1 4 3 0 0 1 2 —²5¹9 Offline Time-Independent Multi-Agent Path Planning KO, Froncios Bonnet, Yasumasa Tamura & Xavier Defago planning execution https://kei18.github.io/otimapp IJCAI-22 ºŽ9/0 OTIMAPP sk»£, kt, ke )ÃÄ4‚¡CÅÆÇ0¨
78. /123 80 given start goal graph solution path Problem Def. – OTIMAPP s.t. RGSTUVWXYHCD Z[G\'];^S:_`
79. /123 81 Æ‹‡'RÇh] OdUX žUR
80. /123 82 CDUVR8RS no reachable cyclic deadlock no reachable terminal deadlock abcdefB2g efHijV.©ª:©>Æìí, …†Sö<.D¥–¬~1Nš
81. /123 83 OPQ8RS OTIMAPP B hiGjkHlm *3-SAT‡ˆsŠ‹h…† }l†“•Gh? (‹”•I) => NP –7 —˜}h™ (š›) => co-NP œ• ¼‘y
82. /123 84 Solvers agents 0 20 40 60 80 100 0 20 40 60 80 100 random-32-32-10 32x32 0 40 80 120 160 200 0 20 40 60 80 100 random-64-64-10 64x64 0 40 80 120 160 200 0 20 40 60 80 100 den520d 257x256 success rate (%) ≤ 5 min MAPF avoids collisions OTIMAPP avoids deadlocks prioritized planning deadlock-based search extending conflict-based search [Sharon+ AIJ-15] extending conventional PP [Erdmann+ Algorithmica-87] $%½o2y9/0hÆ^J´VƒZhk„% MAPF ske1 OTIMAPP 5¢ý
83. /123 85 Execution Demo no synchronization only local interactions centralized style with toio robots decentralized style with AFADA [Kameyama+ ICRA-21; our work!] ž§¨s:Ÿ©/#c´d5efž%&'1å…
84. /123 86 Planning Stage Acting Stage inspired by “Automated Planning and Acting,” Ghallab+ 2016 M6È2ÉIltK ?@%A%BNCD8`- Offline / Deliberative
85. /123 87 Planning Stage Acting Stage Online / Reactive Ê/h„?("€• ÉIlËh
86. /123 88 Collision Avoidance Based Ÿp#`•/, ;C+`A– ¾~A¿®ÀÁ5Æ ýhy% ÐæÔMÂVŽ…P <= ÃŽ9 B©àÔB-–F•YVÄÅ#üÖ .©ª:©>?B+5SVvV9 —ÆVc)S'vV9 JS¡~´ 2. ¢À‡ˆV9 & é+–5g‡š->DE.1Ÿp => c) 1. ÇÈs*+,-./sÄÅ1"d -«1˜9Ç~habž ÕÖ [Şenbaşlar+ DARS-18] https://youtu.be/LbWRvLfdwTA Optimal Reciprocal Collision Avoidance (ORCA) 1Sþm'Ž¨r~sde#ìí [van den Berg+ ISRR-11] ÉÊS±o
87. /123 89 »¼ÂÃÄ8ÉI¹f XÌ2t/LÍÎ[\] PIBT / TSW AP Again!
88. /123 90 Online Time-Independent Unlabeled-MAPF given: start target graph or Policy µ¶K: T#ÊËV¹Ìh)9¨Æ ¶Ë#é+–58Ê7Šë [Okumura+ ICAPS-22] *+,-./Ss%´5 -/=©>V->DE.1Jcž% ¹ÌSõ./:+–hyV9
89. /123 91 Online TSWAP *›¡6ÈÉÊËÌ ÕÖ* compute arbitrary initial target assignment 1. offline phase 2. online phase when is activated: ‰?`•.sÌ<'¡þ` &s-–éB•YSµ¶` nopXKqgr/<=Gst [Okumura+ ICAPS-22]
90. /123 92 »¼ÂÃÄQ8ϳ ƒZ5¬ž%HIJK5Bý ÍÎV¡~d™y#9ˆV9
91. /123 93 ϳÐ
92. /123 94 •œÎÑ9%@‹%'@zyÒž8 »¼ÂÃÄ/uvwx•ÒžÈ”
93. /123 95 planning execution Time-Independent Planning for Multiple Moving Agents KO, Yasumasa Tamura & Xavier Defago AAAI-21 PIBT s‰.`•.ƒZÏÐì5+,E.h$% Causal-PIBTs ÑÒ *+,-./1n)´5c)ž%KLÓ(Ô'Ž¨kÕ 1 2 1 2 3 execution (online) planning (offline) delay necessity to address timing uncertainties https://kei18.github.io/time-independent-planning/
94. /123 96 Planning Stage Acting Stage žŸ •¡¢…™ )*+,+-B.#Er;V £j£\]¤¥n)l†“•G Œr;••G¦§.Aa ¨©•Gª0 CDÓ"&ÈNÔ
95. /123 97 Outline C[nOP>E.# opqr>E)*+,+- DskKLMN+Otuvw MAPF; Multi-Agent Path Finding /121
96. /123 98 MAPF 8B@Õ,‘’8 “¸Ö” NJl Œ@*Æ)*Æ{×L2LL8\]
97. /123 99 bB©ª5л lÖ´VÁÂ
98. /123 100 kVŽ ×Ø… bB©ª5л lÖ´VÁÂ
99. /123 101 .u?vrwxG.uU`U? y/z{.|}B~S•H.k|€}•UH ØÙ8ÚÛY8ÜÝÞ ßàá¼28uvwxf â–M8ãä\åÉIhæçÒž
100. /123 102 artificial potential field sampling-based rule-based goal start LMNO4!"#$%&PQ(RS%T%U
101. /123 103 SBMP: Sampling-Based Motion Planning Ùûë7ÕÖ: 2. :+ªž©_(b`?)1Úº 1. configuration space ‡ˆKL1`.ÛYß._B.b -«sabŽ ÊšÜû¨ß._B.bž%‡, ÊšÜû¨:+ªž©_1Úºž%‡5À9¨ .Ý•.àE•;#ìí, ~€s-–éB•Y#ÑÒÒv¨y8 RRT: Rapidly-exploring Random Tree [Lavalle 98] PRM: Probabilistic Roadmap [Kavraki+ 96] Images are from Wikipedia
102. /123 104 Configuration Space & Motion Planning :Ÿ©/sKLS (x, y) h]Òv% &sYZh ÁŸÃ1kë Å%‹5Vû¨Æ¡þ` 1. :Ÿ©/sKL1kÕ 2. efhyV9Þø1Oß 3. ÁŸÃ1àðû¨kë (x, y) S&sÞø¡5 án%üÖ#$%
103. /123 105 artificial potential field sampling-based rule-based 趕á¼28?@%A%B N«¬>-®xV¯b°l…™ ‚ƒ„
104. /123 106 ßàá¼28?@%A%BfRmKÔ8 Š‹"Œ/„?("€ 1. SBMP >±KLMN+OECL²Dn)a³G 2. ´µ¶·¸CL²Dn)¹> MAPF a}6 [Hönig+ TR-O-18] https://youtu.be/7KIa9FlmbRc
105. /123 107 …†‡U.6ˆ‰Š‹HŒ•Ž•(•'‘’“2)6”:^H produced by PRM [Kavraki+ 96] KÍJéNJêëÒh â ã 2 ¦ WXsä\ Å å ksò ž–à*+,-./[\hSæç´
106. /123 108 ìÌí •–'—˜3™;AšC ›bUœ•;žxkC •'‘’“26Ÿ >•¡¢H ^£k¤¥/–'—˜3™A/ ¦§D¨©?abGª? ’4«¬]/]']X›bUœ•6 -x>?/B®<„XBUH…
107. /123 109 ìÌí •–'—˜3™;AšC ›bUœ•;žxkC •'‘’“26Ÿ >•¡¢H ¯°±²G³©I´ ´µ`Hš^2(34356¶·;¸¹C ›bUœ•6±²‹º•¡¢H (»¼ª:±²)
108. /123 110 <½;lm6.`¾˜'¿ MAPF algorithm new instance 𝐹!"#$ random walk sampling module next locations for all agents starts path generation compositing solution … t=0 t=1 t=2 CTRMs ÀÁ¾˜'¿ 𝐹!"#$ model training instances & solutions predict next locations CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces representation KO*, Ryo Yonetani, Mai Nishimura & Asako Kanezaki .+Fè)·:+ªž©_z{, _`.a.bsä\1éê https://omron-sinicx.github.io/ctrm AAMAS-22 *work done as an intern at OMRON SINIC X
109. /123 111 SPARS [Dobson+ IJRR-14] simplified PRM [Karaman+ IJRR-11] square as agent-specific roadmaps grid as used in MAPF studies CTRMs8QV CTRMs sparse dense ksò1åû8nn WXä\1éê
110. /123 112 Œ•ÂÃ;ÄÅCabUd£u •'‘’“26ÆÇ>•¡HH/XBÈ ÉÊË®(•'‘’“2)6ÌÍ>?A 2(3435GÎ;U?@AGÏ|š^
111. /123 113 Quick Multi-Robot Motion Planning by Combining Sampling & Search KO & Xavier Defago planning representation ž–à:Ÿ©/^+DE._`.a.b1ű5kë-–éB•YSSSP :+ªž©_ST'ÁŸÃ1¡ƒ5cš https://kei18.github.io/sssp
112. /123 114 Proposed Algorithm: SSSP 0 1 2 0 1 2 3 0 1 2 3 4 5 0 1 2 2 3 5 0 1 2 3 4 0 1 4 00 +9:;:<=> 00 10 20 40 50 00 50 51 53 54 00 10 20 40 50 00 vertex expansion search-node expansion & goals new vertices closed next action `.ÛYëì+>hß._B.b & JZKL1M"Ž8íîß+à [Standley AAAI-10] [Hsu+ ICRA-97]
113. /123 115 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) PRM RRT RRT-C PP CBS SSSP Point2d DOF: 2N 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) PRM RRT RRT-C PP CBS SSSP Point3d DOF: 3N 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) PRM RRT-C RRT CBS PP SSSP Line2d DOF: 3N 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) PRM RRT PP CBS RRT-C SSSP Capsule3d DOF: 6N 0 200 400 600 800 1000 olved in tance 0 100 200 300 runtime ( ec) PRM PP/CBS RRT-C RRT SSSP Arm22 DOF: 2N 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) PRM PP CBS RRT RRT-C SSSP Arm33 DOF: 6N 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) PRM RRT RRT-C PP CBS SSSP Dubins2d DOF: 3N 0 200 400 600 800 1000 solved ins ances 0 100 200 300 run ime (sec) RRT-C CBS PP/RRT SSSP Snake2d DOF: 6N SSSP8QV '¨Æfï
114. /123 116 MRMP: Multi-Robot Motion Planning P*+,-./SðfsKLYZ1ÆÀ ñ95òóŽV9ôõ1ŸpŽ89 MAPF S MRMP sö÷C+; 8•ŽøùV]khÆÏ›5qŽ9 [Hopcroft+ IJRR-84] [Zhang+ SIGGRAPH-20] (123456*7'895:) >?-ÍÎ2Ï ú~‰A,->/1)‡ž/0ûž§¨ü5ý³#$% ¤: AGV/AMR, •M6ý, :Ÿ©/-+Y, Nþsÿ, CG, !" Ð)KL6
115. /123 117 MAPF Multi-Agent Path Finding SBMP Sampling-Based Motion Planning ML Machine Learning as Heuristics integration VW MRMP 8XYZR["\]^_`ab@ MRMP sEF1#Ž$m¨9„w %Á&'s‰+/G+DE.£5ÀV#%‡Æ…P 🤔
116. /123 118 Closing
117. /123 119 EFGHIJK\–KMN 3456786, 9:;.<=>, ?@ABCD+EFGHI>FGJB KLMN+OPEQRSLTU+V WXYZ / C[\]^_:`aVbcB8d efg:`hij)CLklmZ>FGJB
118. /123 120 Summary C[nOP>E.# opqr>E)*+,+- DskKLMN+Otuvw MAPF; Multi-Agent Path Finding
119. /123 121 representation planning execution !"#$%&+8Šîï";<%k æç/ðñ8çò integration
120. /123 122 !"#$%&'()*+ ,-./0123456789:;< Wókô
121. /123 More Info? => Check My Website! https://kei18.github.io/ Thank You for Listening! º*[»¼>•½
122. /123 124 Reference
123. /123 125 KO ;<'= [Okumura+ AIJ-22] Okumura, K., Machida M., Défago, X. & Tamura, Y. “Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding.” AIJ. 2022. [Okumura+ IROS-21] Okumura, K., Tamura, Y. & Défago, X. “Iterative Refinement for Real-Time Multi-Robot Path Planning.” IROS-21. 2021. [Okumura+ ICAPS-22] Okumura, K., & Défago, X. “Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution.” ICAPS. 2022. [Okumura+ IJCAI-22] Okumura, K., Bonnet, F., Tamura, Y. & Défago, X. “Offline Time-Independent Multi-Agent Path Planning.” IJCAI. 2022. [Okumura+ AAAI-21] Okumura, K., Tamura, Y. & Défago, X. “Time-Independent Planning for Multiple Moving Agents.” AAAI. 2021. [Kameyama+ ICRA-21] Kameyama, S., Okumura, K., Tamura, Y. & Défago, X. “Active Modular Environment for Robot Navigation.” ICRA. 2022. [Okumura+ AAMAS-22] 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. [Okumura+ preprint-22] Okumura, K., & Défago, X. “Quick Multi-Robot Motion Planning by Combining Sampling and Search.” arXiv. 2022. >, ?@AB (CD/) [Zhang+ SIGGRAPH-20] Zhang, X., Belfer, R., Kry, P. G., & Vouga, E. “C-Space tunnel discovery for puzzle path planning. “ SIGGRAPH. 2020. [Zhang+ 18] Zhang, X., Li, M., Lim, J. H., Weng, Y., Tay, Y. W. D., Pham, H., & Pham, Q. C. “Large-scale 3D printing by a team of mobile robots.” Automation in Construction. 2018. [Le Goc+ UIST-16] Le Goc, M., Kim, L. H., Parsaei, A., Fekete, J. D., Dragicevic, P., & Follmer, S. “Zooids: Building blocks for swarm user interfaces.” UIST. 2016. [van den Berg+ ISRR-11] Berg, J. V. D., Guy, S. J., Lin, M., & Manocha, D. “Reciprocal n-body collision avoidance. “ ISRR. 2011. [Song+ ICCBB-01] Song, G., & Amato, N. M. “Using motion planning to study protein folding pathways.” ICCBB. 2001. [Kornhauser 84] Kornhauser, D. M., Miller, G., & Spirakis, P. “Coordinating pebble motion on graphs, the diameter of permutation groups, and applications.” Master's thesis at M.I.T. 1984. [Röger+ SOCS-12] Röger, G., & Helmert, M. “Non-optimal multi-agent pathfinding is solved (since 1984).” SOCS. 2012. [Yu+ WAFR-15] “Yu, J. & Rus, D. “Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms.” WAFR. 2015. [Nebel ICAPS-20] Nebel, B. “On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs.” ICAPS. 2020. [Boeta+ JAIR-18] Botea, A., Bonusi, D., & Surynek, P. “Solving multi-agent path finding on strongly biconnected digraphs.” JAIR. 2018. [Ratner+ AAAI-86] Ratner, D., & Warmuth, M. K. “Finding a Shortest Solution for the N× N Extension of the 15-PUZZLE Is Intractable.” AAAI. 1986. [Yu&LaValle [Yu+ AAAI-13] Yu, J., & LaValle, S. “Structure and intractability of optimal multi-robot path planning on graphs.” AAAI. 2013. [Surynek AAAI-10] Surynek, P. “An optimization variant of multi-robot path planning is intractable.” AAAI. 2010. [Yu RA-L-15] Yu, J. “Intractability of Optimal Multi-Robot Path Planning on Planar Graphs.” RA-L. 2015.
124. /123 126 [Ma+ AAAI-16] Ma.,H., Tovey, C., Sharon, G., Kumar, T. S., & Koenig, S. “Multi- agent path finding with payload transfers and the package-exchange robot-routing problem.” AAAI. 2016. [Banfi+ RA-L-17] Banfi, J., Basilico, N., & Amigoni, F. “Intractability of time-optimal multirobot path planning on 2d grid graphs with holes.” RA-L. 2017. [Geft+ AAMAS-22] Geft, T., & Halperin, D. “Refined Hardness of Distance-Optimal Multi-Agent Path Finding.” AAMAS. 2022. [Erdmann+ 87] Erdmann, M., & Lozano-Perez, T. “On multiple moving objects.” Algorithmica. 1987. [Silver AIIDE-05] Silver, D. “Cooperative pathfinding.” AIIDE. 2005. [Wang+ JAIR-11] Wang, K. H. C., & Botea, A. “MAPP: a scalable multi-agent path planning algorithm with tractability and completeness guarantees.” JAIR. 2011. [Bnaya+ ICRA-14] Bnaya, Z., & Felner, A. “Conflict-oriented windowed hierarchical cooperative A∗.” ICRA. 2014. [Azarm+ ICRA-97] Azarm, K., & Schmidt, G. “Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation.” ICRA. 1997. [Bennewitz+ 02] Bennewitz, M., Burgard, W., & Thrun, S. “Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots.” Robot. Auton. Syst. 2002. [van Den Berg+ ICRA-05] Van Den Berg, J. P., & Overmars, M. H. “Prioritized motion planning for multiple robots.” ICRA. 2005. [Andreychuk+ AAMAS-18] Andreychuk, A., & Yakovlev, K. “Two techniques that enhance the performance of multi-robot prioritized path planning.”AAMAS. 2018. [Ma+ AAAI-19] Ma, H., Harabor, D., Stuckey, P. J., Li, J., & Koenig, S. “Searching with consistent prioritization for multi-agent path finding.” AAAI. 2019 [Cap+ T-ASE-15] Čáp, M., Novák, P., Kleiner, A., & Selecký, M. “Prioritized planning algorithms for trajectory coordination of multiple mobile robots.” T-ASE. 2015 [Velagapudi+ IROS-10] Velagapudi, P., Sycara, K., & Scerri, P. “Decentralized prioritized planning in large multirobot teams.” IROS. 2010. [Ryan JAIR-08] Ryan, M. R. K. “Exploiting subgraph structure in multi-robot path planning.” JAIR. 2008. [Peasgood+ T-RO-08] Peasgood, M., Clark, C. M., & McPhee, J. “A complete and scalable strategy for coordinating multiple robots within roadmaps.” T-RO. 2008. [Surynek ICRA-09] Surynek, P. “A novel approach to path planning for multiple robots in bi-connected graphs.” ICRA. 2009. [Surynek FLAIRS-09] Surynek, P. “Towards Shorter Solutions for Problems of Path Planning for Multiple Robots in Theta-like Environments.” FLAIRS. 2009. [Luna+ IJCAI-11] Luna, R., & Bekris, K. E. “Push and swap: Fast cooperative path-finding with completeness guarantees.” IJCAI. 2011. [de Wilde+ AAMAS-13] de Wilde, B., ter Mors, A. W., & Witteveen, C. “Push and rotate: cooperative multi-agent path planning.” AAMAS. 2013. [Sajid+ SOCS-12] Sajid, Q., Luna, R., & Bekris, K. E. “Multi-Agent Pathfinding with Simultaneous Execution of Single-Agent Primitives.” SOCS. 2012. [Wiktor+ IROS-14] Wiktor, A., Scobee, D., Messenger, S., & Clark, C. “Decentralized and complete multi-robot motion planning in confined spaces.” IROS. 2010. [Wei+ 14] Wei, C., Hindriks, K. V., & Jonker, C. M. “Multi-robot cooperative pathfinding: A decentralized approach.” IEA/AIE. 2014. [Chouhan& Niyogi AJCAI-15] Chouhan, S. S., & Niyogi, R. “DMAPP: A distributed multi-agent path planning algorithm.” AJCAI. 2015. [Zhang+ DARS-16] Zhang, Y., Kim, K., & Fainekos, G. “Discof: Cooperative pathfinding in distributed systems with limited sensing and communication range. ” DARS. 2016. [Wang+ RA-L-20] Wang, H., & Rubenstein, M. “Walk, stop, count, and swap: decentralized multi-agent path finding with theoretical guarantees.” RA-L. 2020.
125. /123 127 [Ryan ICRA-10] Ryan, M. “Constraint-based multi-robot path planning.” ICRA. 2010 [Surynek PRICAI-12] Surynek, P. “Towards optimal cooperative path planning in hard setups through satisfiability solving.” PRICAI. 2012. [Surynek+ ECAI-16] Surynek, P., Felner, A., Stern, R., & Boyarski, E. “Efficient SAT approach to multi-agent path finding under the sum of costs objective.” ECAI. 2016 [Yu+ T-RO-16] Yu, J., & LaValle, S. “Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics.” T-RO. 2016. [Erdem+ IJCAI-13] Erdem, E., Kisa, D., Oztok, U., & Schüller, P. “A general formal framework for pathfinding problems with multiple agents.” IJCAI. 2013. [Lam+ COR-22] Lam, E., Le Bodic, P., Harabor, D. D., & Stuckey, P. J. “Branch-and-Cut-and-Price for Multi-Agent Pathfinding.” COR. 2022. [Standley AAAI-10] Standley, T. “Finding optimal solutions to cooperative pathfinding problems.” AAAI. 2010. [Shraon+ AIJ-15] Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. “Conflict-based search for optimal multi-agent pathfinding.” AIJ. 2015. [Boyarski+ IJCAI-15] Boyarski, E., Felner, A., Stern, R., Sharon, G., Betzalel, O., Tolpin, D., & Shimony, E. “ICBS: improved conflict-based search algorithm for multi- agent pathfinding.” IJCAI. 2015. [Boyarski+ AAAI-21] Boyarski, E., Felner, A., Le Bodic, P., Harabor, D., Stuckey, P. J., & Koenig, S. “f-Aware Conflict Prioritization & Improved Heuristics for Conflict- Based Search.” AAAI. 2021. [Felner+ ICAPS-18] Felner, A., Li, J., Boyarski, E., Ma, H., Cohen, L., Kumar, T. S., & Koenig, S. “Adding heuristics to conflict-based search for multi-agent path finding.” ICAPS. 2018. [Li+ IJCAI-19] Li, J., Felner, A., Boyarski, E., Ma, H., & Koenig, S. “Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search.” IJCAI. 2019. [Li+ AIJ-21] Li, J., Harabor, D., Stuckey, P. J., Ma, H., Gange, G., & Koenig, S. “Pairwise symmetry reasoning for multi-agent path finding search.” AIJ. 2021. [Gange+ ICAPS-19] Gange, G., Harabor, D., & Stuckey, P. J. “Lazy CBS: Implicit conflict-based search using lazy clause generation.” ICAPS. 2019. [Huang+ AAAI-21] Huang, T., Dilkina, B., & Koenig, S. “Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search.” AAAI. 2021. [Boyarski+ IJCAI-20] Boyarski, E., Felner, A., Harabor, D., Stuckey, P. J., Cohen, L., Li, J., & Koenig, S. “Iterative-Deepening Conflict-Based Search.” IJCAI. 2020. [Barer+ SOCS-14] Barer, M., Sharon, G., Stern, R., & Felner, A. “Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem.” SOCS. 2014. [Li+ AAAI-21] Li, J., Ruml, W., & Koenig, S. “EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding.” AAAI. 2021 [Sartoretti+ RA-L-19] Sartoretti, G., Kerr, J., Shi, Y., Wagner, G., Kumar, T. S., Koenig, S., & Choset, H. “Primal: Pathfinding via reinforcement and imitation multi-agent learning.” RA-L. 2019. [Li+ IROS-20] Li, Q., Gama, F., Ribeiro, A., & Prorok, A. “Graph Neural Networks for Decentralized Multi-Robot Path Planning.” IROS. 2020. [Damani+ RA-L-21] Damani, M., Luo, Z., Wenzel, E., & Sartoretti, G. “PRIMAL2: Pathfinding Via Reinforcement and Imitation Multi-Agent Learning-Lifelong.” RA-L. 2021. [Li+ IJCAI-21] Li, J., Chen, Z., Harabor, D., Stuckey, P., & Koenig, S. “Anytime Multi-Agent Path Finding via Large Neighborhood Search.” IJCAI. 2021. [Ma+ AAMAS-17] Ma, H., Li, J., Kumar, T. K., & Koenig, S. “Lifelong multi-agent path finding for online pickup and delivery tasks.” AAMAS. 2017.
126. /123 128 [Liu+ AAMAS-19] Liu, M., Ma, H., Li, J., & Koenig, S. “Task and path planning for multi-agent pickup and delivery.” AAMAS. 2019. [Atzmon+ JAIR-20] Atzmon, D., Stern, R., Felner, A., Wagner, G., Barták, R., & Zhou, N. F. “Robust multi-agent path finding and executing.” JAIR. 2020. [Atzmon+ ICAPS-20] Atzmon, D., Stern, R., Felner, A., Sturtevant, N. R., & Koenig, S. “Atzmon, D., Stern, R., Felner, A., Sturtevant, N. R., & Koenig, S. “Probabilistic robust multi-agent path finding.” ICAPS. 2020. [Shahar+ JAIR-21] Shahar, T., Shekhar, S., Atzmon, D., Saffidine, A., Juba, B., & Stern, R. “Safe Multi-Agent Pathfinding with Time Uncertainty.” JAIR. 2021. [Ma+ AAMAS-16] Ma, H., & Koenig, S. “Optimal target assignment and path finding for teams of agents.” AAMAS. 2016. [Thomas+ 15] Thomas, S., Deodhare, D., & Murty, M. N. “Extended conflict-based search for the convoy movement problem”. IEEE Intelligent Systems. 2015. [Li+ AAAI-19] Li, J., Surynek, P., Felner, A., Ma, H., Kumar, T. S., & Koenig, S. “Multi-agent path finding for large agents.” AAAI. 2019. [Atzmon+ SOCS-19] Atzmon, D., Diei, A., & Rave, D. “Multi-Train Path Finding”. SOCS. 2019 [Yakovlev+ ICAPS-17] Yakovlev, K., & Andreychuk, A. “Any-angle pathfinding for multiple agents based on SIPP algorithm.” ICAPS. 2017. [Surynek AAAI-21] Surynek, P. “Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering.” AAAI. 2021. [Peltzer+ 2019] Peltzer, O., Brown, K., Schwager, M., Kochenderfer, M. J., & Sehr, M. “STT-CBS: A Conflict-Based Search Algorithm for Multi-Agent Path Finding with Stochastic Travel Times.” arXiv preprint. 2019. [Walker+ IJCAI-18] Walker, T. T., Sturtevant, N. R., & Felner, A. “Extended Increasing Cost Tree Search for Non-Unit Cost Domains.” IJCAI. 2018. [Andreychuk+ IJCAI-19] Andreychuk, A., Yakovlev, K., Atzmon, D., & Stern, R. “Multi-agent pathfinding with continuous time.” IJCAI. 2019. [Zhang+ AAMAS-22] Zhang, H., Chen, J., Li, J., Williams, B. C., & Koenig, S. “Multi-Agent Path Finding for Precedence-Constrained Goal Sequences.” AAMAS. 2022. [Hönig ICAPS-16] Hönig, W., Kumar, T. K., Cohen, L., Ma, H., Xu, H., Ayanian, N., & Koenig, S. “Multi-agent path finding with kinematic constraints.” ICAPS. 2016. [Čáp+ IROS-16] Čáp, M., Gregoire, J., & Frazzoli, E. “Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances.” IROS. 2016. [Ma+ AAAI-17] Ma, H., Kumar, T. S., & Koenig, S. “Multi-agent path finding with delay probabilities.” AAAI. 2017. [Şenbaşlar+ DARS-18] Şenbaşlar, B., Hönig, W., & Ayanian, N. “Robust trajectory execution for multi-robot teams using distributed real-time replanning.” DARS. 2018. [Hopcroft+ IJRR-84] 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. [Kavraki+ 96] Kavraki, L. E., Svestka, P., Latombe, J. C., & Overmars, M. H. “Probabilistic roadmaps for path planning in high-dimensional configuration spaces.” IEEE transactions on Robotics and Automation. 1996. [LaValle 98] LaValle, S. M. “Rapidly-exploring random trees: A new tool for path planning.” 1998. [Hönig TR-O-18] Hönig, W., Preiss, J. A., Kumar, T. S., Sukhatme, G. S., & Ayanian, N. “Trajectory planning for quadrotor swarms.” TR-O. 2018.