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 agents do not collide one another. Given plan , the expression denotes the position of agent after having performed steps of plan . It is possible to distinguish five different types of collisions between two plans and . Vertex conflict: there is a vertex conflict between plans and when the two agents occupy the same location at the same time. Formally, a vertex conflict happens when . Edge conflict: an edge conflict occurs whenever two agents cross the same edge in the same direction at the same time, that is and . If vertex conflicts are not allowed, then edge conflicts cannot exist. Following conflict: a following conflict happens when at a certain time step an agent occupies a location that was occupied by another agent in the previous time step. Mathematically, a following conflict is described as . Cycle conflict: a cycle conflict happens whenever a set of agents (at least three) move as if they are spinning in a cycle. It means that each agent takes the position that was previously occupied by the other agent one step-ahead in the cycle. If following conflicts are forbidden, then cycle conflicts cannot happen. Swapping conflict: a swapping conflict is the case in which two agents exchange their position, passing on the same edge at the same time in two different directions. It is expressed as and . 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 udually 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: flowtime: this measure is obtained by summing the time steps employed by each agent to reach their target location. Formally, it is equal to , where the plans are single-agent plans without collisions; makespan: the number of time steps necessary so that all the agents complete theirs tasks, defined as , where are part of a valid solution; maximization of reached targets given a deadline: the aim is to find a valid solution that maximizes the number of agents