20:
1039:
2181:
all equal to 1. Other works focus on eliminating the discrete time assumptions and that the duration of actions is exactly equal to one time step. Another assumption that does not reflect reality is that agents occupy exactly one cell of the environment in which they are: some studies have been conducted to overcome this hypothesis. It is interesting to note that the shape and geometry of agents may introduce new types of conflicts, since agents may crash with one another even if they are not completely overlapped.
2172:
In a MAPD setting, agents have to complete a stream of tasks, where each task is composed by a pick-up a location and a delivery location. When planning for the completion of a task, the path has to start from the current position of the robot and to end in the delivery position of the task, passing through the pick-up point. MAPD is considered a "lifelong" version of MAPF in which tasks arrive incrementally.
2180:
The assumptions that the agents are in a grid environment, that their speed is constant and that time is discrete are simplifying hypotheses. Many works take into account the kinematic constraints of agents, such as velocity and orientation, or go past the assumption that the weights of the arcs are
2171:
MAPF problem is not able to capture some aspects relative to real world applications. For example, in automated warehouses it happens that robots have to complete several tasks one after the other. For this reason, an extended MAPF version is proposed, called Multi-Agent Pick-up and
Delivery (MAPD).
2144:
Bounded suboptimal algorithms offer a trade-off between the optimality and the cost of the solution. They are said to be bounded by a certain factor because they return solutions with a cost at most equal to the optimal solution cost times the factor. MAPF bounded suboptimal solvers can be divided
305:
It is assumed that time is discrete, and that each agent can perform one action at each time step. There are two possible types of actions: the wait action, in which the agent remains in its node, and the move action, that allows the agent to move to an adjacent node. An action is formalized as a
2162:
It is a version of MAPF in which there is a set of target locations but agents are not assigned a specific target. It does not matter whether the agent that reaches the target, the important thing is that targets are completed. A slight modification of this version is the one in which agents are
2117:
Increasing Cost Tree Search: a novel formalization of the MAPF problem is proposed, that comprehends an increasing search tree and the corresponding algorithm. The algorithm is composed by two levels and relies on the assumption that a valid solution for the MAPF problem is composed by a set of
1361:
Cycle conflict: a cycle conflict happens whenever a set of agents (at least three) move as if they are spinning in a cycle. It means that each agent takes the position that was previously occupied by the other agent one step-ahead in the cycle. If following conflicts are forbidden, then cycle
58:
Several algorithms have been proposed to solve the MAPF problem. Due to its complexity, it happens that optimal approaches are infeasible on big environments and with a high number of agents. However, given the applications in which MAPF is involved such as automated warehouses and airport
1854:
that corresponds to the priority given to the agent. Then, following the priority order, for each agent a plan is computed to reach the target location. When planning, agents have to avoid collisions with paths of other agents with a higher priority that have already computed their plans.
2093:
The drawback of prioritized planning is that, even if it is a sound approach (it returns valid solutions), it is neither optimal nor complete. This means that it is not assured that the algorithm will return a solution and, even in that case, the solution may not be optimal.
1497:
When formalizing a MAPF problem, it is possible to decide which conflicts are allowed and which are forbidden. A unified standard about permitted and denied conflicts does not exist, however vertex and edge conflicts are usually not allowed.
2153:
The way in which MAPF problems are defined allows to change various aspects, for example the fact of being in a grid environment or the assumption that time is discrete. This section reports some variations of the classical MAPF problem.
1293:
Following conflict: a following conflict happens when at a certain time step an agent occupies a location that was occupied by another agent in the previous time step. Mathematically, a following conflict is described as
43:, since the aim is to find those paths that optimize a given objective function, usually defined as the number of time steps until all agents reach their goal cells. MAPF is the multi-agent generalization of the
2199:
Airport operations: MAPF algorithms can be employed in crowded airports to coordinate towing vehicles that transport aircraft. Being able to optimize this kind of problems provides also a benefit to the
1766:. Optimal MAPF solvers return high quality solutions, but their efficiency is low. Instead, bounded-suboptimal and suboptimal solvers are more efficient, but their solutions are less effective. Also
649:
2265:
Stern, Roni; Sturtevant, Nathan R.; Felner, Ariel; Koenig, Sven; Ma, Hang; Walker, Thayne; Li, Jiaoyang; Atzmon, Dor; Cohen, Liron; Kumar, T. K. Satish; Boyarski, Eli; Barták, Roman (2019).
1737:, or graphs similar to grids. For what concerns bounded suboptimal solutions, it is shown that it is NP-hard to find a makespan-optimal solution with a factor of suboptimality smaller than
1365:
Swapping conflict: a swapping conflict is the case in which two agents exchange their position, passing on the same edge at the same time in two different directions. It is expressed as
823:
single-agent plans (one for each agent), such that the plans do not collide one another. Once an agent has reached its target, it can either remain in the target location or disappear.
2121:
Conflict-Based Search: this algorithm computes paths as when solving single-agent pathfinding problems, and then it adds constraints in an incremental way in order to avoid collisions.
1656:
1561:
2450:
Ma, Hang; Tovey, Craig; Sharon, Guni; Kumar, T. K.; Koenig, Sven (5 March 2016). "Multi-Agent Path
Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem".
1491:
1427:
1356:
1288:
1218:
1157:
1506:
When computing single-agent plans, the aim is to maximize a user-defined objective function. There is not a standard objective function to adopt, however the most common are:
1764:
1600:
125:
1852:
376:
1716:
maximization of reached targets given a deadline: the aim is to find a valid solution that maximizes the number of agents that reach their target given a time deadline.
542:
1683:
1099:
1072:
1033:
1006:
979:
912:
876:
781:
754:
336:
299:
264:
2207:: service robots are automated agents that perform dangerous and repetitive tasks for humans in a non-industrial environment. Their main goal is to help human beings.
2002:
1711:
491:
446:
421:
189:
2196:: warehouse logistics represents the main industrial application of MAPF. It has been shown that automation in warehouses manages to increase the productivity level.
1964:
1892:
727:
698:
2088:
2062:
2042:
2022:
1932:
1912:
1796:
952:
932:
849:
821:
801:
669:
565:
511:
466:
396:
229:
209:
145:
2730:
Bartak, Roman; Zhou, Neng-Fa; Stern, Roni; Boyarski, Eli; Surynek, Pavel (November 2017). "Modeling and
Solving the Multi-agent Pathfinding Problem in Picat".
2415:
Banfi, Jacopo; Basilico, Nicola; Amigoni, Francesco (October 2017). "Intractability of Time-Optimal
Multirobot Path Planning on 2D Grid Graphs with Holes".
2937:
Li, Jiaoyang; Surynek, Pavel; Felner, Ariel; Ma, Hang; Kumar, T. K. Satish; Koenig, Sven (17 July 2019). "Multi-Agent Path
Finding for Large Agents".
2210:
Video games: the usefulness of MAPF in such settings can be found when the player has to move a team of agents in a congested video game environment.
2830:
Ma, Hang; Li, Jiaoyang; Kumar, T. K. Satish; Koenig, Sven (30 May 2017). "Lifelong Multi-Agent Path
Finding for Online Pickup and Delivery Tasks".
2968:
Wurman, Peter R.; D'Andrea, Raffaello; Mountz, Mick (20 March 2008). "Coordinating
Hundreds of Cooperative, Autonomous Vehicles in Warehouses".
2892:
Andreychuk, Anton; Yakovlev, Konstantin; Surynek, Pavel; Atzmon, Dor; Stern, Roni (April 2022). "Multi-agent pathfinding with continuous time".
2127:: with this kind of approach, MAPF problems are transformed into a set of constraints and then solved using specific constraint solvers such as
1042:
Types of conflicts: (a) is an edge conflict, (b) a vertex conflict, (c) a following conflict, (d) a cycle conflict, and (e) a swapping conflict.
1862:
in a time-expansion graph. A time-expansion graph is a graph that takes into account the passing of time. Each node is composed by two entries
2695:
Sharon, Guni; Stern, Roni; Felner, Ariel; Sturtevant, Nathan R. (February 2015). "Conflict-based search for optimal multi-agent pathfinding".
231:
is the edge set. The nodes represent the possible locations of the agents, while the arcs are the possible connections between such positions;
1510:
flowtime: this measure is obtained by summing the time steps employed by each agent to reach their target location. Formally, it is equal to
2314:
Ma, Hang; Wagner, Glenn; Felner, Ariel; Li, Jiaoyang; Kumar, T. K. Satish; Koenig, Sven (2018). "Multi-Agent Path
Finding with Deadlines".
547:
The agents perform sequences of actions to go from their starting point to their target location. A sequence of action performed by agent
1778:
One possible approach to face the computational complexity is prioritized planning. It consists in decoupling the MAPF problem into
39:
and consists in the computation of collision-free paths for a group of agents from their location to an assigned target. It is an
2481:
Sartoretti, Guillaume; Kerr, Justin; Shi, Yunfei; Wagner, Glenn; Kumar, T. K. Satish; Koenig, Sven; Choset, Howie (July 2019).
1162:
Edge conflict: an edge conflict occurs whenever two agents cross the same edge in the same direction at the same time, that is
3039:
2747:
2638:
570:
2266:
59:
management, it is important to reach a trade-off between the efficiency of the solution and its effectiveness.
1608:
1513:
2851:
Hoenig, Wolfgang; Kumar, T. K. Satish; Cohen, Liron; Ma, Hang; Xu, Hong; Ayanian, Nora; Koenig, Sven (2016).
19:
3113:
2771:
Kloder, S.; Hutchinson, S. (August 2006). "Path planning for permutation-invariant multirobot formations".
151:
2852:
831:
In order to have a valid solution for a MAPF problem, it is necessary that the single-agent plans of the
1101:
when the two agents occupy the same location at the same time. Formally, a vertex conflict happens when
3008:
2533:
1432:
1368:
1297:
1223:
1165:
1104:
1605:
makespan: the number of time steps necessary so that all the agents complete theirs tasks, defined as
2132:
1740:
1566:
1038:
74:
2857:
Proceedings of the Twenty-Sixth
International Joint Conference on Artificial Intelligence (IJCAI-17)
2300:
3061:
Proceedings of the AAAI Conference on
Artificial Intelligence and Interactive Digital Entertainment
2587:
Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment
2370:
Yu, Jingjin (January 2016). "Intractability of Optimal Multirobot Path Planning on Planar Graphs".
1807:
2806:
Ma, Hang; Koenig, Sven (2016). "Optimal Target Assignment and Path Finding for Teams of Agents".
2582:
2124:
1661:
1077:
1050:
1011:
984:
957:
881:
854:
759:
732:
309:
272:
237:
3004:
2287:
2235:
1969:
1859:
1687:
341:
156:
48:
2879:
Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems
2872:"A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs"
2225:
1937:
1865:
40:
36:
3056:
703:
674:
516:
8:
2193:
2111:
2107:
2067:
1725:
Several algorithms have been proposed to solve the MAPF problem. The issue is that it is
471:
426:
401:
3068:
2985:
2950:
2919:
2901:
2831:
2807:
2788:
2753:
2712:
2644:
2598:
2563:
2545:
2534:"Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots"
2514:
2494:
2463:
2432:
2397:
2379:
2352:
2315:
2273:
2220:
2047:
2027:
2007:
1917:
1897:
1781:
937:
917:
834:
806:
786:
654:
550:
496:
451:
381:
214:
194:
130:
3057:"Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments"
3035:
3032:
IJCAI'15: Proceedings of the 24th International Conference on Artificial Intelligence
2923:
2743:
2732:
2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI)
2648:
2634:
981:. It is possible to distinguish five different types of collisions between two plans
3007:; Luckow, Kasper; Malik, Waqar; Ma, Hang; Kumar, T. K. Satish; Koenig, Sven (2016).
2989:
2954:
2792:
2602:
2518:
2436:
2401:
2356:
3078:
2977:
2942:
2911:
2780:
2757:
2735:
2716:
2704:
2675:
2626:
2590:
2555:
2504:
2467:
2455:
2424:
2389:
2344:
1767:
3055:
Ma, Hang; Yang, Jingxing; Cohen, Liron; Kumar, T. K. Satish; Koenig, Sven (2017).
2567:
3027:
2946:
2915:
2708:
2680:
2663:
2336:
2102:
It is possible to distinguish four different categories of optimal MAPF solvers:
2630:
3082:
3026:
Veloso, Manuela; Biswas, Joydeep; Coltin, Brian; Rosenthal, Stephanie (2015).
2559:
3107:
2981:
2739:
2594:
2509:
2482:
2459:
2428:
2393:
2337:"Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs"
2204:
2784:
2662:
Sharon, Guni; Stern, Roni; Goldenberg, Meir; Felner, Ariel (February 2013).
2532:
Cap, Michal; Novak, Peter; Kleiner, Alexander; Selecky, Martin (July 2015).
2348:
3098:
1858:
Finding a solution for the MAPF problem in such setting corresponds to the
1734:
52:
2871:
2483:"PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning"
2230:
1798:
1726:
44:
1290:. If vertex conflicts are not allowed, then edge conflicts cannot exist.
2625:. Lecture Notes in Computer Science. Vol. 11866. pp. 96–115.
2128:
2145:
following the same categorization presented for optimal MAPF solvers.
2664:"The increasing cost tree search for optimal multi-agent pathfinding"
3009:"Planning, Scheduling and Monitoring for Airport Surface Operations"
2163:
divided into groups and each group has to perform a set of targets.
3073:
2906:
2836:
2812:
2499:
2384:
2320:
2278:
2550:
1730:
2267:"Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks"
2891:
2621:
Stern, Roni (2019). "Multi-Agent Path Finding – an Overview".
2110:: algorithms in this category employ modified versions of the
67:
The elements of a classical MAPF problem are the following:
2939:
Proceedings of the AAAI Conference on Artificial Intelligence
2452:
Proceedings of the AAAI Conference on Artificial Intelligence
2341:
Proceedings of the AAAI Conference on Artificial Intelligence
3028:"CoBots: Robust Symbiotic Autonomous Mobile Service Robots"
3025:
2694:
2661:
2264:
3002:
1804:
The first step is to assign to each agent a unique number
1047:
Vertex conflict: there is a vertex conflict between plans
23:
Example of Multi-Agent Path Finding in a grid environment.
1770:
approaches have been proposed to solve the MAPF problem.
2967:
2729:
2538:
IEEE Transactions on Automation Science and Engineering
2480:
1733:
makespan or flow-time solutions, also when considering
2531:
1745:
2853:"Multi-Agent Path Finding with Kinematic Constraints"
2070:
2050:
2030:
2010:
1972:
1940:
1920:
1900:
1868:
1810:
1784:
1743:
1690:
1664:
1611:
1569:
1516:
1435:
1371:
1300:
1226:
1168:
1107:
1080:
1053:
1014:
987:
960:
940:
920:
884:
857:
837:
809:
789:
762:
735:
706:
677:
657:
573:
553:
519:
499:
474:
454:
429:
404:
384:
344:
312:
275:
240:
217:
197:
159:
133:
77:
2414:
2189:
MAPF can be applied in several real case scenarios:
803:. A valid solution for the MAPF problem is a set of
2166:
266:
that associates each agent with its starting point;
2870:Barták, Roman; Švancara, Jiří; Vlk, Marek (2018).
2850:
2449:
2139:
2082:
2056:
2036:
2016:
1996:
1958:
1926:
1906:
1886:
1846:
1790:
1758:
1705:
1677:
1650:
1594:
1555:
1485:
1421:
1350:
1282:
1212:
1151:
1093:
1066:
1027:
1000:
973:
946:
926:
906:
870:
843:
815:
795:
775:
748:
721:
692:
663:
643:
559:
536:
505:
485:
460:
440:
415:
390:
370:
330:
293:
258:
223:
203:
183:
139:
119:
2936:
2869:
301:that associates each agent with its target point.
3105:
3054:
2770:
2313:
1613:
644:{\displaystyle \pi _{i}=(a_{1},a_{2},...,a_{n})}
2829:
851:agents do not collide one another. Given plan
1841:
1811:
114:
84:
2825:
2823:
2616:
2614:
2612:
3013:AAAI Workshop: Planning for Hybrid Systems
2844:
1602:are single-agent plans without collisions;
47:problem, and it is closely related to the
3072:
2905:
2835:
2811:
2679:
2549:
2508:
2498:
2383:
2334:
2319:
2277:
2885:
2820:
2805:
2609:
2335:Yu, Jingjin; LaValle, Steven M. (2013).
2175:
1651:{\displaystyle \max _{i\in A}|\pi _{i}|}
1556:{\displaystyle \sum _{i\in A}|\pi _{i}|}
1037:
62:
18:
2996:
2307:
2260:
2258:
2256:
2254:
2252:
2250:
2097:
1773:
3106:
3019:
2580:
1501:
826:
783:is called single-agent plan for agent
2620:
2363:
2328:
378:represents the action of moving from
2961:
2941:. Vol. 33. pp. 7627–7634.
2863:
2487:IEEE Robotics and Automation Letters
2417:IEEE Robotics and Automation Letters
2372:IEEE Robotics and Automation Letters
2343:. Vol. 27. pp. 1443–1449.
2247:
2723:
2688:
2525:
700:and arrives to its target location
13:
2369:
14:
3125:
3092:
2589:. Vol. 1. pp. 117–122.
2474:
2157:
1486:{\displaystyle \pi _{j}=\pi _{i}}
1422:{\displaystyle \pi _{i}=\pi _{j}}
1351:{\displaystyle \pi _{i}=\pi _{j}}
1283:{\displaystyle \pi _{i}=\pi _{j}}
1213:{\displaystyle \pi _{i}=\pi _{j}}
1152:{\displaystyle \pi _{i}=\pi _{j}}
2167:Multi-Agent Pick-up and Delivery
2118:solutions for the single agents.
3048:
2930:
2799:
2764:
2655:
2184:
2140:Bounded Suboptimal MAPF Solvers
1759:{\displaystyle {\tfrac {4}{3}}}
1595:{\displaystyle \pi _{i},i\in A}
651:and is called a plan. If agent
120:{\displaystyle A=\{1,2,...,k\}}
2574:
2443:
2408:
1991:
1973:
1953:
1941:
1881:
1869:
1644:
1629:
1549:
1534:
1480:
1474:
1458:
1446:
1416:
1410:
1394:
1382:
1345:
1339:
1323:
1311:
1277:
1265:
1249:
1237:
1207:
1201:
1185:
1179:
1146:
1140:
1124:
1118:
914:denotes the position of agent
901:
895:
716:
710:
687:
681:
638:
587:
354:
348:
322:
285:
250:
178:
166:
1:
2773:IEEE Transactions on Robotics
2241:
2148:
2064:is not occupied at time step
1847:{\displaystyle \{1,2,...,k\}}
1720:
1713:are part of a valid solution;
2947:10.1609/aaai.v33i01.33017627
2916:10.1016/j.artint.2022.103662
2709:10.1016/j.artint.2014.11.006
2681:10.1016/j.artint.2012.11.006
1934:is the time step. Each node
7:
2631:10.1007/978-3-030-33274-7_6
2214:
10:
3130:
3083:10.1609/aiide.v13i1.12919
2583:"Cooperative Pathfinding"
2560:10.1109/TASE.2015.2445780
2133:Mixed Integer Programming
671:starts from its location
2982:10.1609/aimag.v29i1.2082
2740:10.1109/ICTAI.2017.00147
2595:10.1609/aiide.v1i1.18726
2510:10.1109/LRA.2019.2903261
2460:10.1609/aaai.v30i1.10409
2429:10.1109/LRA.2017.2715406
2394:10.1109/LRA.2015.2503143
1799:single-agent pathfinding
1678:{\displaystyle \pi _{i}}
1362:conflicts cannot happen.
1094:{\displaystyle \pi _{j}}
1067:{\displaystyle \pi _{i}}
1028:{\displaystyle \pi _{j}}
1001:{\displaystyle \pi _{i}}
974:{\displaystyle \pi _{i}}
907:{\displaystyle \pi _{i}}
871:{\displaystyle \pi _{i}}
776:{\displaystyle \pi _{i}}
749:{\displaystyle \pi _{i}}
331:{\displaystyle a:V\to V}
294:{\displaystyle t:A\to V}
259:{\displaystyle s:A\to V}
2894:Artificial Intelligence
2785:10.1109/TRO.2006.878952
2697:Artificial Intelligence
2668:Artificial Intelligence
2623:Artificial Intelligence
2349:10.1609/aaai.v27i1.8541
2125:Constraints programming
1997:{\displaystyle (u,t+1)}
1966:is linked to the nodes
1706:{\displaystyle ,i\in A}
934:after having performed
371:{\displaystyle a(v)=v'}
184:{\displaystyle G=(V,E)}
29:Multi-Agent Pathfinding
3034:. pp. 4423–4429.
2581:Silver, David (2021).
2295:Cite journal requires
2084:
2058:
2038:
2018:
1998:
1960:
1928:
1908:
1888:
1848:
1792:
1760:
1707:
1679:
1652:
1596:
1557:
1487:
1423:
1352:
1284:
1214:
1153:
1095:
1068:
1043:
1029:
1002:
975:
948:
928:
908:
872:
845:
817:
797:
777:
750:
723:
694:
665:
645:
561:
538:
507:
487:
462:
442:
417:
392:
372:
332:
295:
260:
225:
205:
185:
141:
121:
24:
2236:Shortest path problem
2176:Beyond Classical MAPF
2085:
2059:
2039:
2019:
1999:
1961:
1959:{\displaystyle (v,t)}
1929:
1914:is the node name and
1909:
1889:
1887:{\displaystyle (v,t)}
1860:shortest path problem
1849:
1793:
1761:
1708:
1680:
1653:
1597:
1558:
1488:
1424:
1353:
1285:
1215:
1154:
1096:
1069:
1041:
1030:
1003:
976:
949:
929:
909:
873:
846:
818:
798:
778:
751:
724:
695:
666:
646:
562:
539:
508:
493:, or to stay in node
488:
463:
443:
418:
393:
373:
333:
296:
261:
226:
211:is the node set, and
206:
186:
142:
122:
63:Problem Formalization
49:shortest path problem
22:
3005:Pasareanu, Corina S.
2734:. pp. 959–966.
2226:Multi-agent planning
2194:Automated warehouses
2098:Optimal MAPF Solvers
2068:
2048:
2028:
2008:
1970:
1938:
1918:
1898:
1866:
1808:
1782:
1774:Prioritized Planning
1741:
1688:
1662:
1609:
1567:
1514:
1433:
1369:
1298:
1224:
1166:
1105:
1078:
1051:
1012:
985:
958:
938:
918:
882:
855:
835:
807:
787:
760:
733:
722:{\displaystyle t(i)}
704:
693:{\displaystyle s(i)}
675:
655:
571:
551:
537:{\displaystyle v=v'}
517:
497:
472:
452:
427:
402:
382:
342:
310:
273:
238:
215:
195:
157:
131:
75:
41:optimization problem
37:multi-agent planning
35:) is an instance of
3114:Multi-agent systems
2881:. pp. 748–756.
2221:Multi-agent systems
2083:{\displaystyle t+1}
1502:Objective Functions
827:Types of Collisions
468:and different than
16:Pathfinding problem
2203:Autonomous mobile
2080:
2054:
2034:
2014:
1994:
1956:
1924:
1904:
1884:
1844:
1788:
1756:
1754:
1703:
1675:
1648:
1627:
1592:
1563:, where the plans
1553:
1532:
1483:
1419:
1348:
1280:
1210:
1149:
1091:
1064:
1044:
1025:
998:
971:
944:
924:
904:
868:
841:
813:
793:
773:
746:
719:
690:
661:
641:
557:
534:
503:
486:{\displaystyle v'}
483:
458:
441:{\displaystyle v'}
438:
416:{\displaystyle v'}
413:
388:
368:
328:
291:
256:
221:
201:
181:
137:
117:
51:in the context of
25:
3041:978-1-57735-738-4
2749:978-1-5386-3876-7
2640:978-3-030-33273-0
2057:{\displaystyle u}
2037:{\displaystyle v}
2017:{\displaystyle u}
1927:{\displaystyle t}
1907:{\displaystyle v}
1791:{\displaystyle k}
1753:
1612:
1517:
947:{\displaystyle x}
927:{\displaystyle i}
878:, the expression
844:{\displaystyle k}
816:{\displaystyle k}
796:{\displaystyle i}
664:{\displaystyle i}
560:{\displaystyle i}
506:{\displaystyle v}
461:{\displaystyle v}
391:{\displaystyle v}
224:{\displaystyle E}
204:{\displaystyle V}
140:{\displaystyle k}
3121:
3087:
3086:
3076:
3052:
3046:
3045:
3023:
3017:
3016:
3003:Morris, Robert;
3000:
2994:
2993:
2965:
2959:
2958:
2934:
2928:
2927:
2909:
2889:
2883:
2882:
2876:
2867:
2861:
2860:
2848:
2842:
2841:
2839:
2827:
2818:
2817:
2815:
2803:
2797:
2796:
2768:
2762:
2761:
2727:
2721:
2720:
2692:
2686:
2685:
2683:
2659:
2653:
2652:
2618:
2607:
2606:
2578:
2572:
2571:
2553:
2529:
2523:
2522:
2512:
2502:
2493:(3): 2378–2385.
2478:
2472:
2471:
2454:. Vol. 30.
2447:
2441:
2440:
2423:(4): 1941–1947.
2412:
2406:
2405:
2387:
2367:
2361:
2360:
2332:
2326:
2325:
2323:
2311:
2305:
2304:
2298:
2293:
2291:
2283:
2281:
2271:
2262:
2089:
2087:
2086:
2081:
2063:
2061:
2060:
2055:
2043:
2041:
2040:
2035:
2023:
2021:
2020:
2015:
2003:
2001:
2000:
1995:
1965:
1963:
1962:
1957:
1933:
1931:
1930:
1925:
1913:
1911:
1910:
1905:
1893:
1891:
1890:
1885:
1853:
1851:
1850:
1845:
1797:
1795:
1794:
1789:
1768:machine learning
1765:
1763:
1762:
1757:
1755:
1746:
1712:
1710:
1709:
1704:
1684:
1682:
1681:
1676:
1674:
1673:
1657:
1655:
1654:
1649:
1647:
1642:
1641:
1632:
1626:
1601:
1599:
1598:
1593:
1579:
1578:
1562:
1560:
1559:
1554:
1552:
1547:
1546:
1537:
1531:
1492:
1490:
1489:
1484:
1473:
1472:
1445:
1444:
1428:
1426:
1425:
1420:
1409:
1408:
1381:
1380:
1357:
1355:
1354:
1349:
1338:
1337:
1310:
1309:
1289:
1287:
1286:
1281:
1264:
1263:
1236:
1235:
1219:
1217:
1216:
1211:
1200:
1199:
1178:
1177:
1158:
1156:
1155:
1150:
1139:
1138:
1117:
1116:
1100:
1098:
1097:
1092:
1090:
1089:
1073:
1071:
1070:
1065:
1063:
1062:
1034:
1032:
1031:
1026:
1024:
1023:
1007:
1005:
1004:
999:
997:
996:
980:
978:
977:
972:
970:
969:
953:
951:
950:
945:
933:
931:
930:
925:
913:
911:
910:
905:
894:
893:
877:
875:
874:
869:
867:
866:
850:
848:
847:
842:
822:
820:
819:
814:
802:
800:
799:
794:
782:
780:
779:
774:
772:
771:
755:
753:
752:
747:
745:
744:
729:performing plan
728:
726:
725:
720:
699:
697:
696:
691:
670:
668:
667:
662:
650:
648:
647:
642:
637:
636:
612:
611:
599:
598:
583:
582:
566:
564:
563:
558:
543:
541:
540:
535:
533:
512:
510:
509:
504:
492:
490:
489:
484:
482:
467:
465:
464:
459:
447:
445:
444:
439:
437:
422:
420:
419:
414:
412:
397:
395:
394:
389:
377:
375:
374:
369:
367:
337:
335:
334:
329:
300:
298:
297:
292:
265:
263:
262:
257:
230:
228:
227:
222:
210:
208:
207:
202:
190:
188:
187:
182:
146:
144:
143:
138:
126:
124:
123:
118:
3129:
3128:
3124:
3123:
3122:
3120:
3119:
3118:
3104:
3103:
3095:
3090:
3053:
3049:
3042:
3024:
3020:
3001:
2997:
2966:
2962:
2935:
2931:
2890:
2886:
2874:
2868:
2864:
2849:
2845:
2828:
2821:
2804:
2800:
2769:
2765:
2750:
2728:
2724:
2693:
2689:
2660:
2656:
2641:
2619:
2610:
2579:
2575:
2530:
2526:
2479:
2475:
2448:
2444:
2413:
2409:
2368:
2364:
2333:
2329:
2312:
2308:
2296:
2294:
2285:
2284:
2269:
2263:
2248:
2244:
2217:
2187:
2178:
2169:
2160:
2151:
2142:
2100:
2069:
2066:
2065:
2049:
2046:
2045:
2029:
2026:
2025:
2024:is adjacent to
2009:
2006:
2005:
1971:
1968:
1967:
1939:
1936:
1935:
1919:
1916:
1915:
1899:
1896:
1895:
1867:
1864:
1863:
1809:
1806:
1805:
1783:
1780:
1779:
1776:
1744:
1742:
1739:
1738:
1723:
1689:
1686:
1685:
1669:
1665:
1663:
1660:
1659:
1643:
1637:
1633:
1628:
1616:
1610:
1607:
1606:
1574:
1570:
1568:
1565:
1564:
1548:
1542:
1538:
1533:
1521:
1515:
1512:
1511:
1504:
1468:
1464:
1440:
1436:
1434:
1431:
1430:
1404:
1400:
1376:
1372:
1370:
1367:
1366:
1333:
1329:
1305:
1301:
1299:
1296:
1295:
1259:
1255:
1231:
1227:
1225:
1222:
1221:
1195:
1191:
1173:
1169:
1167:
1164:
1163:
1134:
1130:
1112:
1108:
1106:
1103:
1102:
1085:
1081:
1079:
1076:
1075:
1058:
1054:
1052:
1049:
1048:
1019:
1015:
1013:
1010:
1009:
992:
988:
986:
983:
982:
965:
961:
959:
956:
955:
939:
936:
935:
919:
916:
915:
889:
885:
883:
880:
879:
862:
858:
856:
853:
852:
836:
833:
832:
829:
808:
805:
804:
788:
785:
784:
767:
763:
761:
758:
757:
740:
736:
734:
731:
730:
705:
702:
701:
676:
673:
672:
656:
653:
652:
632:
628:
607:
603:
594:
590:
578:
574:
572:
569:
568:
552:
549:
548:
526:
518:
515:
514:
498:
495:
494:
475:
473:
470:
469:
453:
450:
449:
448:is adjacent to
430:
428:
425:
424:
405:
403:
400:
399:
383:
380:
379:
360:
343:
340:
339:
338:, meaning that
311:
308:
307:
274:
271:
270:
239:
236:
235:
216:
213:
212:
196:
193:
192:
158:
155:
154:
132:
129:
128:
76:
73:
72:
65:
27:The problem of
17:
12:
11:
5:
3127:
3117:
3116:
3102:
3101:
3094:
3093:External links
3091:
3089:
3088:
3067:(1): 270–272.
3047:
3040:
3018:
2995:
2960:
2929:
2884:
2862:
2843:
2819:
2798:
2779:(4): 650–665.
2763:
2748:
2722:
2687:
2654:
2639:
2608:
2573:
2544:(3): 835–849.
2524:
2473:
2442:
2407:
2362:
2327:
2306:
2297:|journal=
2245:
2243:
2240:
2239:
2238:
2233:
2228:
2223:
2216:
2213:
2212:
2211:
2208:
2205:service robots
2201:
2197:
2186:
2183:
2177:
2174:
2168:
2165:
2159:
2158:Anonymous MAPF
2156:
2150:
2147:
2141:
2138:
2137:
2136:
2135:(MIP) solvers.
2122:
2119:
2115:
2106:Extensions of
2099:
2096:
2079:
2076:
2073:
2053:
2033:
2013:
1993:
1990:
1987:
1984:
1981:
1978:
1975:
1955:
1952:
1949:
1946:
1943:
1923:
1903:
1883:
1880:
1877:
1874:
1871:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1787:
1775:
1772:
1752:
1749:
1722:
1719:
1718:
1717:
1714:
1702:
1699:
1696:
1693:
1672:
1668:
1646:
1640:
1636:
1631:
1625:
1622:
1619:
1615:
1603:
1591:
1588:
1585:
1582:
1577:
1573:
1551:
1545:
1541:
1536:
1530:
1527:
1524:
1520:
1503:
1500:
1495:
1494:
1482:
1479:
1476:
1471:
1467:
1463:
1460:
1457:
1454:
1451:
1448:
1443:
1439:
1418:
1415:
1412:
1407:
1403:
1399:
1396:
1393:
1390:
1387:
1384:
1379:
1375:
1363:
1359:
1347:
1344:
1341:
1336:
1332:
1328:
1325:
1322:
1319:
1316:
1313:
1308:
1304:
1291:
1279:
1276:
1273:
1270:
1267:
1262:
1258:
1254:
1251:
1248:
1245:
1242:
1239:
1234:
1230:
1209:
1206:
1203:
1198:
1194:
1190:
1187:
1184:
1181:
1176:
1172:
1160:
1148:
1145:
1142:
1137:
1133:
1129:
1126:
1123:
1120:
1115:
1111:
1088:
1084:
1061:
1057:
1022:
1018:
995:
991:
968:
964:
954:steps of plan
943:
923:
903:
900:
897:
892:
888:
865:
861:
840:
828:
825:
812:
792:
770:
766:
743:
739:
718:
715:
712:
709:
689:
686:
683:
680:
660:
640:
635:
631:
627:
624:
621:
618:
615:
610:
606:
602:
597:
593:
589:
586:
581:
577:
567:is denoted by
556:
532:
529:
525:
522:
502:
481:
478:
457:
436:
433:
411:
408:
387:
366:
363:
359:
356:
353:
350:
347:
327:
324:
321:
318:
315:
303:
302:
290:
287:
284:
281:
278:
267:
255:
252:
249:
246:
243:
232:
220:
200:
180:
177:
174:
171:
168:
165:
162:
150:an undirected
148:
136:
116:
113:
110:
107:
104:
101:
98:
95:
92:
89:
86:
83:
80:
64:
61:
15:
9:
6:
4:
3:
2:
3126:
3115:
3112:
3111:
3109:
3100:
3097:
3096:
3084:
3080:
3075:
3070:
3066:
3062:
3058:
3051:
3043:
3037:
3033:
3029:
3022:
3014:
3010:
3006:
2999:
2991:
2987:
2983:
2979:
2975:
2971:
2964:
2956:
2952:
2948:
2944:
2940:
2933:
2925:
2921:
2917:
2913:
2908:
2903:
2899:
2895:
2888:
2880:
2873:
2866:
2858:
2854:
2847:
2838:
2833:
2826:
2824:
2814:
2809:
2802:
2794:
2790:
2786:
2782:
2778:
2774:
2767:
2759:
2755:
2751:
2745:
2741:
2737:
2733:
2726:
2718:
2714:
2710:
2706:
2702:
2698:
2691:
2682:
2677:
2673:
2669:
2665:
2658:
2650:
2646:
2642:
2636:
2632:
2628:
2624:
2617:
2615:
2613:
2604:
2600:
2596:
2592:
2588:
2584:
2577:
2569:
2565:
2561:
2557:
2552:
2547:
2543:
2539:
2535:
2528:
2520:
2516:
2511:
2506:
2501:
2496:
2492:
2488:
2484:
2477:
2469:
2465:
2461:
2457:
2453:
2446:
2438:
2434:
2430:
2426:
2422:
2418:
2411:
2403:
2399:
2395:
2391:
2386:
2381:
2377:
2373:
2366:
2358:
2354:
2350:
2346:
2342:
2338:
2331:
2322:
2317:
2310:
2302:
2289:
2280:
2275:
2268:
2261:
2259:
2257:
2255:
2253:
2251:
2246:
2237:
2234:
2232:
2229:
2227:
2224:
2222:
2219:
2218:
2209:
2206:
2202:
2198:
2195:
2192:
2191:
2190:
2182:
2173:
2164:
2155:
2146:
2134:
2130:
2126:
2123:
2120:
2116:
2113:
2109:
2105:
2104:
2103:
2095:
2091:
2077:
2074:
2071:
2051:
2031:
2011:
1988:
1985:
1982:
1979:
1976:
1950:
1947:
1944:
1921:
1901:
1878:
1875:
1872:
1861:
1856:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1814:
1802:
1800:
1785:
1771:
1769:
1750:
1747:
1736:
1735:planar graphs
1732:
1728:
1715:
1700:
1697:
1694:
1691:
1670:
1666:
1638:
1634:
1623:
1620:
1617:
1604:
1589:
1586:
1583:
1580:
1575:
1571:
1543:
1539:
1528:
1525:
1522:
1518:
1509:
1508:
1507:
1499:
1477:
1469:
1465:
1461:
1455:
1452:
1449:
1441:
1437:
1413:
1405:
1401:
1397:
1391:
1388:
1385:
1377:
1373:
1364:
1360:
1342:
1334:
1330:
1326:
1320:
1317:
1314:
1306:
1302:
1292:
1274:
1271:
1268:
1260:
1256:
1252:
1246:
1243:
1240:
1232:
1228:
1204:
1196:
1192:
1188:
1182:
1174:
1170:
1161:
1143:
1135:
1131:
1127:
1121:
1113:
1109:
1086:
1082:
1059:
1055:
1046:
1045:
1040:
1036:
1020:
1016:
993:
989:
966:
962:
941:
921:
898:
890:
886:
863:
859:
838:
824:
810:
790:
768:
764:
741:
737:
713:
707:
684:
678:
658:
633:
629:
625:
622:
619:
616:
613:
608:
604:
600:
595:
591:
584:
579:
575:
554:
545:
530:
527:
523:
520:
500:
479:
476:
455:
434:
431:
409:
406:
385:
364:
361:
357:
351:
345:
325:
319:
316:
313:
288:
282:
279:
276:
268:
253:
247:
244:
241:
233:
218:
198:
175:
172:
169:
163:
160:
153:
149:
134:
111:
108:
105:
102:
99:
96:
93:
90:
87:
81:
78:
70:
69:
68:
60:
56:
54:
50:
46:
42:
38:
34:
30:
21:
3064:
3060:
3050:
3031:
3021:
3012:
2998:
2973:
2969:
2963:
2938:
2932:
2897:
2893:
2887:
2878:
2865:
2856:
2846:
2801:
2776:
2772:
2766:
2731:
2725:
2700:
2696:
2690:
2671:
2667:
2657:
2622:
2586:
2576:
2541:
2537:
2527:
2490:
2486:
2476:
2451:
2445:
2420:
2416:
2410:
2378:(1): 33–40.
2375:
2371:
2365:
2340:
2330:
2309:
2288:cite journal
2200:environment.
2188:
2185:Applications
2179:
2170:
2161:
2152:
2143:
2101:
2092:
1857:
1803:
1777:
1724:
1505:
1496:
830:
546:
304:
66:
57:
53:graph theory
32:
28:
26:
2970:AI Magazine
2674:: 470–495.
2231:Pathfinding
45:pathfinding
3074:1710.01447
2907:1901.05506
2900:: 103662.
2837:1705.10868
2813:1612.05693
2500:1809.03531
2385:1504.02072
2321:1806.04216
2279:1906.08291
2242:References
2149:Variations
2004:such that
1801:problems.
1721:Algorithms
3099:MAPF.info
2924:207791641
2703:: 40–66.
2649:204832267
2551:1409.2399
2114:approach.
1698:∈
1667:π
1635:π
1621:∈
1587:∈
1572:π
1540:π
1526:∈
1519:∑
1466:π
1438:π
1402:π
1374:π
1331:π
1303:π
1257:π
1229:π
1193:π
1171:π
1132:π
1110:π
1083:π
1056:π
1017:π
990:π
963:π
887:π
860:π
765:π
738:π
576:π
323:→
306:function
286:→
251:→
3108:Category
2990:10475273
2976:(1): 9.
2955:53687939
2793:62805494
2603:17714238
2519:52191178
2437:36801258
2402:10275469
2357:11655439
2215:See also
1894:, where
1729:to find
1658:, where
531:′
480:′
435:′
410:′
365:′
191:, where
2758:7819470
2717:3809045
2468:1585005
1731:optimal
1727:NP-hard
756:, then
147:agents;
3038:
2988:
2953:
2922:
2791:
2756:
2746:
2715:
2647:
2637:
2601:
2568:347488
2566:
2517:
2466:
2435:
2400:
2355:
269:a map
234:a map
71:a set
3069:arXiv
2986:S2CID
2951:S2CID
2920:S2CID
2902:arXiv
2875:(PDF)
2832:arXiv
2808:arXiv
2789:S2CID
2754:S2CID
2713:S2CID
2645:S2CID
2599:S2CID
2564:S2CID
2546:arXiv
2515:S2CID
2495:arXiv
2464:S2CID
2433:S2CID
2398:S2CID
2380:arXiv
2353:S2CID
2316:arXiv
2274:arXiv
2270:(PDF)
152:graph
3036:ISBN
2744:ISBN
2635:ISBN
2301:help
2131:and
2044:and
1429:and
1220:and
1074:and
1008:and
33:MAPF
3079:doi
2978:doi
2943:doi
2912:doi
2898:305
2781:doi
2736:doi
2705:doi
2701:219
2676:doi
2672:195
2627:doi
2591:doi
2556:doi
2505:doi
2456:doi
2425:doi
2390:doi
2345:doi
2129:SAT
1614:max
513:if
423:if
398:to
127:of
3110::
3077:.
3065:13
3063:.
3059:.
3030:.
3011:.
2984:.
2974:29
2972:.
2949:.
2918:.
2910:.
2896:.
2877:.
2855:.
2822:^
2787:.
2777:22
2775:.
2752:.
2742:.
2711:.
2699:.
2670:.
2666:.
2643:.
2633:.
2611:^
2597:.
2585:.
2562:.
2554:.
2542:12
2540:.
2536:.
2513:.
2503:.
2489:.
2485:.
2462:.
2431:.
2419:.
2396:.
2388:.
2374:.
2351:.
2339:.
2292::
2290:}}
2286:{{
2272:.
2249:^
2112:A*
2108:A*
2090:.
1035:.
544:.
55:.
3085:.
3081::
3071::
3044:.
3015:.
2992:.
2980::
2957:.
2945::
2926:.
2914::
2904::
2859:.
2840:.
2834::
2816:.
2810::
2795:.
2783::
2760:.
2738::
2719:.
2707::
2684:.
2678::
2651:.
2629::
2605:.
2593::
2570:.
2558::
2548::
2521:.
2507::
2497::
2491:4
2470:.
2458::
2439:.
2427::
2421:2
2404:.
2392::
2382::
2376:1
2359:.
2347::
2324:.
2318::
2303:)
2299:(
2282:.
2276::
2078:1
2075:+
2072:t
2052:u
2032:v
2012:u
1992:)
1989:1
1986:+
1983:t
1980:,
1977:u
1974:(
1954:)
1951:t
1948:,
1945:v
1942:(
1922:t
1902:v
1882:)
1879:t
1876:,
1873:v
1870:(
1842:}
1839:k
1836:,
1833:.
1830:.
1827:.
1824:,
1821:2
1818:,
1815:1
1812:{
1786:k
1751:3
1748:4
1701:A
1695:i
1692:,
1671:i
1645:|
1639:i
1630:|
1624:A
1618:i
1590:A
1584:i
1581:,
1576:i
1550:|
1544:i
1535:|
1529:A
1523:i
1493:.
1481:]
1478:x
1475:[
1470:i
1462:=
1459:]
1456:1
1453:+
1450:x
1447:[
1442:j
1417:]
1414:x
1411:[
1406:j
1398:=
1395:]
1392:1
1389:+
1386:x
1383:[
1378:i
1358:.
1346:]
1343:x
1340:[
1335:j
1327:=
1324:]
1321:1
1318:+
1315:x
1312:[
1307:i
1278:]
1275:1
1272:+
1269:x
1266:[
1261:j
1253:=
1250:]
1247:1
1244:+
1241:x
1238:[
1233:i
1208:]
1205:x
1202:[
1197:j
1189:=
1186:]
1183:x
1180:[
1175:i
1159:.
1147:]
1144:x
1141:[
1136:j
1128:=
1125:]
1122:x
1119:[
1114:i
1087:j
1060:i
1021:j
994:i
967:i
942:x
922:i
902:]
899:x
896:[
891:i
864:i
839:k
811:k
791:i
769:i
742:i
717:)
714:i
711:(
708:t
688:)
685:i
682:(
679:s
659:i
639:)
634:n
630:a
626:,
623:.
620:.
617:.
614:,
609:2
605:a
601:,
596:1
592:a
588:(
585:=
580:i
555:i
528:v
524:=
521:v
501:v
477:v
456:v
432:v
407:v
386:v
362:v
358:=
355:)
352:v
349:(
346:a
326:V
320:V
317::
314:a
289:V
283:A
280::
277:t
254:V
248:A
245::
242:s
219:E
199:V
179:)
176:E
173:,
170:V
167:(
164:=
161:G
135:k
115:}
112:k
109:,
106:.
103:.
100:.
97:,
94:2
91:,
88:1
85:{
82:=
79:A
31:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
