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.