Pathfinding problem
The problem of Multi-Agent Pathfinding (MAPF) is an instance of multi-agent planning and consists in the computation of collision-free paths for a group of agents from their location to an assigned target. It is an optimization problem, 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 pathfinding problem, and it is closely related to the shortest path problem in the context of graph theory.
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 management, it is important to reach a trade-off between the efficiency of the solution and its effectiveness.
Problem Formalization.
The elements of a classical MAPF problem are the following:
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 function formula_8, meaning that formula_9 represents the action of moving from formula_10 to formula_11 if formula_11 is adjacent to formula_10 and different than formula_11, or to stay in node formula_10 if formula_16.
The agents perform sequences of actions to go from their starting point to their target location. A sequence of action performed by agent formula_17 is denoted by formula_18 and is called a plan. If agent formula_17 starts from its location formula_20 and arrives to its target location formula_21 performing plan formula_22, then formula_22 is called single-agent plan for agent formula_17. A valid solution for the MAPF problem is a set of formula_2 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.
Types of Collisions.
In order to have a valid solution for a MAPF problem, it is necessary that the single-agent plans of the formula_2 agents do not collide one another. Given plan formula_22, the expression formula_28 denotes the position of agent formula_17 after having performed formula_30 steps of plan formula_22. It is possible to distinguish five different types of collisions between two plans formula_22 and formula_33.
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.
Objective Functions.
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:
Algorithms.
Several algorithms have been proposed to solve the MAPF problem. The issue is that it is NP-hard to find optimal makespan or flow-time solutions, also when considering planar graphs, 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 formula_47. 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 machine learning approaches have been proposed to solve the MAPF problem.
Prioritized Planning.
One possible approach to face the computational complexity is prioritized planning. It consists in decoupling the MAPF problem into formula_2 single-agent pathfinding problems.
The first step is to assign to each agent a unique number formula_49 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.
Finding a solution for the MAPF problem in such setting corresponds to the shortest path problem 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 formula_50, where formula_10 is the node name and formula_52 is the time step. Each node formula_50 is linked to the nodes formula_54 such that formula_55 is adjacent to formula_10 and formula_55 is not occupied at time step formula_58.
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.
Optimal MAPF Solvers.
It is possible to distinguish four different categories of optimal MAPF solvers:
Bounded Suboptimal MAPF Solvers.
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 following the same categorization presented for optimal MAPF solvers.
Variations.
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.
Anonymous MAPF.
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 divided into groups and each group has to perform a set of targets.
Multi-Agent Pick-up and Delivery.
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). 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.
Beyond Classical MAPF.
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 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.
Applications.
MAPF can be applied in several real case scenarios: