The problem of Multi-Agent Path Finding (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: a set of agents; an undirected graph , where is the node set, and is the edge set. The nodes represent the possible locations of the agents, while the arcs are the possible connections between such positions; a map that associates each agent with its starting point; a map that associates each agent with its target point. 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 , meaning that represents the action of moving from to if is adjacent to and different than , or to stay in node if . The agents perform sequences of actions to go from their starting point to their target location. A sequence of action performed by agent is denoted by and is called a plan. If agent starts from its location and arrives to its target location performing plan , then is called single-agent plan for agent . A valid solution for the MAPF problem is a set of 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