Bringing Multi-agent Path Finding Closer to Reality

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.