Multi-agent pathfinding
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.
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.
The agents perform sequences of actions to go from their starting point to their target location.
[1] In order to have a valid solution for a MAPF problem, it is necessary that the single-agent plans of the
[1] When formalizing a MAPF problem, it is possible to decide which conflicts are allowed and which are forbidden.
[1] 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:[1] 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,[3] also when considering planar graphs,[4] or graphs similar to grids.
[5] 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
[6] 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.
[7] One possible approach to face the computational complexity is prioritized planning.
Then, following the priority order, for each agent a plan is computed to reach the target location.
The drawback of prioritized planning is that, even if it is a sound approach (it returns valid solutions), it is neither optimal nor complete.
It is possible to distinguish four different categories of optimal MAPF solvers:[10] Bounded suboptimal algorithms offer a trade-off between the optimality and the cost of the solution.
[10] 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.
[15] MAPF problem is not able to capture some aspects relative to real world applications.
For this reason, an extended MAPF version is proposed, called Multi-Agent Pick-up and Delivery (MAPD).
[16] 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.
[16] 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,[17] such as velocity and orientation, or go past the assumption that the weights of the arcs are all equal to 1.
[19] 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.
MAPF can be applied in several real case scenarios:
