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. 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.

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. a set A = \{1,2,...,k\} of k agents; an undirected graph G=(V,E) , where V is the node set, and E 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 s: A \to V that associates each agent with its starting point; a map t: A \to V 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 a : V \to V , meaning that a(v) = v' represents the action of moving from v to v' if v' is adjacent to v and different than v' , or to stay in node v if v = v' . The agents perform sequences of actions to go from their starting point to their target location. A sequence of action performed by agent i is denoted by \pi_i = (a_1, a_2,..., a_n) and is called a plan. If agent i starts from its location s(i) and arrives to its target location t(i) performing plan \pi_i , then \pi_i is called single-agent plan for agent i . A valid solution for the MAPF problem is a set of k 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. Vertex conflict: there is a vertex conflict between plans \pi_i and \pi_j when the two agents occupy the same location at the same time. Formally, a vertex conflict happens when \pi_i[x] = \pi_j[x] . Edge conflict: an edge conflict occurs whenever two agents cross the same edge in the same direction at the same time, that is \pi_i[x] = \pi_j[x] and \pi_i[x+1] = \pi_j[x+1] . 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 \pi_i[x+1] = \pi_j[x] . 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 \pi_i[x+1] = \pi_j[x] and \pi_j[x+1] = \pi_i[x] . 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. === 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366762780 under CC BY-SA 4.0; modifications have been made.