--- title: "Bringing Multi-agent Path Finding Closer to Reality" authors: - "Jiří Švancara" doi: "10.24963/ijcai.2018/837" url: "https://ijcai.org/proceedings/2018/837" pdf: "https://ijcai.org/proceedings/2018/0837.pdf" venue: "Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence" year: 2018 pages: "5787-5788" track: "Doctoral Consortium" keywords: - "Agent-based and Multi-agent Systems: Multi-agent Planning" - "Robotics and Vision: Motion and Path Planning" --- # Bringing Multi-agent Path Finding Closer to Reality Jiří Švancara *Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence*, pages 5787-5788. DOI: [10.24963/ijcai.2018/837](https://doi.org/10.24963/ijcai.2018/837) ## Abstract Multi-agent path finding is the problem of navigating multiple agents from their current locations to their goal locations in such a way that there are no collisions between the agents. The classical definition of the problem assumes that the set of agents is unchangeable, and that the distances in the graph are homogeneous. We propose to add to the problem specification a set of new attributes to bring it closer to the real world. These attributes include varying distances, number of agents that can occupy an edge or node, and dynamic appearance of new agents. ## Full text ## 1 Introduction Multi-agent Path Finding (MAPF) is the task to navigate a set of mobile agents from their current locations to their desired locations while avoiding collisions with other agents. In recent years, this problem received much attention in theoretical computer science with applications ranging from robotics, traffic optimization, and warehouse management, to computer games and more [Sharon et al., 2011]. An abstraction where the environment is represented by a graph is often used in literature [Ryan, 2008]. However, this graph does not include lengths for the edges and therefore all of them are treated as unit-length edges. Furthermore, all of the agents share the same properties, specifically, all of the agents have the same speed and dimensions. Another thing to mention is that the set of the agents is unchangeable. In this paper, we propose to add new attributes to the classical MAPF problem. The attributes mainly include varying lengths for the edges over which the agents move as well as allowing new agents to dynamically appear in the graph. We also briefly study the implications of such new attributes. ## 2 Definition Formally a classical MAPF instance can be written as a pair (G, A), where G = (V, E) is a graph and A is a set of agents. Each agent ai ∈ A is associated with starting location si ∈ V and desired goal location gi ∈ V . This means that every agent is also a pair ai = (si, gi). The time is discretized and in each time step every agent can perform either a move action to a neighboring node or stay in its current location. Let πi denote a plan for agent ai, then πi(j) denotes a location where agent ai is present at time step j. A valid solution of MAPF problem is a plan π = ⋃ ai∈A πi such that the following constraints are satisfied: 1. The plan for each agent is a valid path. I.e. if πi(j) = v and πi(j +1) = u then (v, u) ∈ E or πi(j) = πi(j +1). 2. No two agents occupy one node at the same time. I.e. for all pairs of agents ai1 and ai2 at all time steps j it holds that πi1 (j) ̸= πi2 (j). 3. No two agents occupy one edge at the same time. I.e. for all pairs of agents ai1 and ai2 at all time steps j it holds that πi1 (j) ̸= πi2 (j + 1) ∨ πi1 (j + 1) ̸= πi2 (j). Note that this definition allows agents to move along a fully occupied cycle as long as it contains 3 or more nodes. In addition to having a valid solution, it is often required to find an optimal solution in terms of some cost function. The two most often used functions are Sum of Costs (SOC) [Sharon et al., 2011] and Makespan [Surynek, 2014]. ## 3 RelatedWork The algorithms that solve the MAPF problem can be in general divided into two categories - suboptimal and optimal. The former are computationally faster but do not provide optimal solutions, the latter on the other hand do provide optimal solutions but are computationally hard [Surynek, 2010]. To solve the MAPF problem optimally, one may use search algorithms [Sharon et al., 2011] including some heuristic functions [Svancara and Surynek, 2017] or reduce the problem to some other formalism as a satisfiability problem [Surynek, 2014]. ## 4 Distances and Occupancy The first extension to consider is to add lengths to the edges of the graph G. Now formally the graph is a triplet G = (V,E,w), where w is a function w : V → N+ that assigns each edge a positive number. This number represents the number of time steps it takes an agent to move along this edge. We shall denote this extension as a weighted MAPF. If the function w assigns a unit-weight to each edge, then it is equivalent to the original MAPF problem. One can argue that this extension can be reduced to the original problem by simply splitting the non-unit edges into an appropriate amount of new edges with new nodes inbetween. However, these two approaches are not equal as once an agent enters an edge, it must go through the whole edge without stopping or turning around. If the long edge is split into several unit edges, the agent can stop at any time or even turn around and go back. This is not corresponding with the real world as, for example, a car cannot turn around on highway at any time it wishes. Our paper on weighted MAPF will be published on AAMAS 2018 [Bart´ak et al., 2018]. A new issue that arises with weighted MAPF is how many agents can use one edge at one time. In the original definition, it is forbidden for more than one agent to be present to forbid swapping of two neighboring agents (two agents using the same edge in the opposite direction). In the original MAPF, it is impossible for more than one agent to go in the same direction over one edge, because there could not be more agents present at the node to use the same edge in time. However, this is possible in weighted MAPF. If we leave the occupancy of an edge as a unit, this can lead to very different solutions than if we allow more agents to share the edge. ## 5 Online Version Another extension is to consider that the environment (graph) is constant and unchangeable, but the set of agents can change in a way that new agents can appear at some time steps. Formally this change agent ai into a triplet ai = (si, gi, ti), where ti is a time step when agent ai appears in node si. However, ai is revealed to the solver only at the time step ti, thus making the problem on-line. We shall denote this extension as online MAPF. One can again argue that this extension can be reduced to the original one by changing the graph. We add a directed path of length ti that the agent needs to traverse before entering the original graph. For further reference, we will call this reduction offline MAPF planner. This is not equivalent to the online MAPF because offline MAPF planner does know in advance all of the agents, which is not an on-line problem. There are two things to consider with regard to what happens with the new agent when it enters the graph and what happens when it reaches its goal. If the agent ai appears exactly at the time step ti in the node si, this can lead to unavoidable collisions, as there may be some agent already present at node si. To solve this problem, we propose that the agent will appear in some meta location and is required to perform one move action to enter the graph at node si. It is also allowed to wait in the meta location for as long as required. If the agent remains staying in the goal node, after reaching its destination, it is easy to find an example that makes the instance of online MAPF unsolvable, however, it would be solvable by an offline MAPF planner that knows in advance when and where are the new agents going to appear. To solve this problem, we expect the agents to disappear from the graph after reaching their goal locations. If we consider the two properties of appearance and disappearance of agents, it can be proven that every online MAPF problem can be solved iff there are paths from si to gi for every ai ∈ A. On the other hand, it can also be shown that there can not be any online MAPF solver that will guarantee as good solution as offline MAPF solver can produce. This is due to the fact that we do not know where the new agents will appear. This extension has been also studied and a paper is under review for IJCAI 2018. ## Conclusion The mentioned extensions of the MAPF problem are studied in the Ph.D. thesis as well as different approaches to solving them. Mainly we are focused on SAT reduction solvers and search based solvers. As it turns out, if we add different attributes to the original problem, some solvers become less efficient and others may surpass them. ## References 1. [Barták et al., 2018] Roman Barták, J. Svancara, and M. Vlk. A scheduling-based approach to multi-agent path finding with weighted and capacitated arcs. In To appear in Proceedings of AAMAS 2018, Stockholm, Sweden, July 11-13, 2018, 2018. 2. [Ryan, 2008] Malcolm Ross Kinsella Ryan. Exploiting sub- graph structure in multi-robot path planning. J. Artif. In- tell. Res., 31:497-542, 2008. 3. [Sharon et al., 2011] Guni Sharon, Roni Stern, Meir Gold- enberg, and Ariel Felner. The increasing cost tree search for optimal multi-agent pathfinding. In Toby Walsh, ed- itor, IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 662-667. 4. IJ- CAI/AAAI, 2011. 5. [Surynek, 2010] Pavel Surynek. An optimization variant of multi-robot path planning is intractable. In Maria Fox and David Poole, editors, Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, Georgia, USA, July 11-15, 2010. AAAI Press, 2010. 6. [Surynek, 2014] Pavel Surynek. Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs. In 26th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2014, Limas- sol, Cyprus, November 10-12, 2014, pages 875-882. IEEE Computer Society, 2014. 7. [Svancara and Surynek, 2017] Jiri Svancara and Pavel Surynek. New flow-based heuristic for search algorithms solving multi-agent path finding. In H. Jaap van den Herik, Ana Paula Rocha, and Joaquim Filipe, editors, Pro- ceedings of the 9th International Conference on Agents and Artificial Intelligence, ICAART 2017, Volume 2, Porto, Portugal, February 24-26, 2017., pages 451-458. 8. SciTePress, 2017.