In the multi-agent path finding problem (MAPF) initial and final position of agents are provided. We find a path for agents with no collisions. Here we present the Conflict Based Search (CBS), it is a two-level algorithm that does not convert the problem into the single ‘joint agent’ model. A Conflict Tree (CT) is a tree based on conflicts between individual agents, each node represents a set of constraints on the path of agents, search is done on this tree at high level. At the low level, single agent searches are performed to eradicate constraints given by the high level CT node. Also we have Meta-Agent CBS (MA-CBS) algorithm. MA-CBS is a generalization of CBS. Unlike basic CBS, MA-CBS is not restricted to single-agent searches at the low level. Instead, MA-CBS allows agents to be merged into small groups of joint agents. This reduces some of the cons of basic CBS and further improves performance. On experimenting, this algorithm produces better results and performance.
Single-agent path finding is the problem of finding a path between two vertices in a graph. It is commonly done with algorithms that perform a best-first search. The multi-agent path finding (MAPF) problem is a generalization of the single-agent path finding problem for k > 1 agents. It consists of a graph and a number of agents. For each agent, a unique initial state and a unique final state is given, and the task is to find paths for all agents from their start or initial states to their goal that is final states, but it is to be made sure that agents don’t collide during their movements, also the cost of path is to be minimum. MAPF has practical applications in video games, traffic control and robotics. Finding an optimal solution for the MAPF problem is NP-hard, as the state space grows exponentially with the number of agents. Optimal solvers are usually applied when the number of agents is relatively small and the task is to find an optimal, minimal-cost solution.
A node in the search tree consists of the set of locations for all the agents at time t. The start state and goal state consist of the initial and goal locations of the different agents, respectively. Given a graph with branching factor b, there are O(b) possible moves for any single agent and thus the branching factor for an A* search is O(bk), which may run for a very long time or exhaust the available memory.
First, we present a new conflict-based formalization for MAPF and a corresponding new algorithm called Conflict Based Search (CBS). We study the results of our CBS algorithm and discuss its advantages and drawbacks when compared to A*-based approaches as well as other approaches. Based on characteristics of the problem, we show cases where CBS will be significantly more efficient than the previous approaches. We also discuss the limitations of CBS and show circumstances where CBS is inferior to the A*-based approaches. Experimental results are provided which support our theoretical understandings.
In MA-CBS the number of conflicts allowed between any pair of agents is limited to a predefined parameter B. When the number of conflicts exceeds B, the conflicting agents are merged into a meta-agent and then treated as a joint composite agent by the low-level solver. In the low-level search, MA-CBS uses any possible complete MAPF solver to find paths for the meta-agent. Different merge policies give rise to different special cases. The original CBS algorithm corresponds to the case
where
B = ∞ (never merge agents), and the Independence Detection (ID) framework is the case
where
B = 0 (always merge agents when conflicts occur).
Finally, we present experimental results for MA-CBS that show the superiority of MA-CBS over the other approaches on all domains.
Problem definition and terminology:
Path:
Each of the single agents uses a path to reach end position from start position.
Conflict:
When in a predicted path two or more agents collide(reach/access/arrive at a particular address at same time), it is said that there is a conflict. This can be solved by either allocating a different path to agent(s) or by halting agent(s). It is said to be resolved when no two agents share the same address at a time in the predicted output path.
It is denoted by a tuple (agent-x,agent-y, vertex-v, time-t) where agent-x and agent-y occupy vertex-v at time point t. A solution (of k paths) is valid if all its paths have no conflicts.
Constraint:
A constraint is a tuple (agent x,vertex v,time t) where current agent-x can’t occupy vertex-v at time-t.
Conflict based search algorithm (CBS):
CBS solves MAPF by breaking problems into a large number of constrained single-agent path finding problems. Each of these path solutions can be solved linearly (proportional to the size of the map and length of the solution), but there may be an exponential number of such single-agent problems.
The key idea of CBS is to get a set of constraints and find paths that no longer have any of these constraints. If these paths still have conflicts, the conflicts are resolved by adding new constraints.
CBS works in two levels.
At the high level, programs search for conflicts and make constraints.
At the low level program finds paths for individual agents that are consistent with the new constraints.
High level
CBS makes a constraint tree (CT) and then searches for minimum cost. A CT is a binary tree. Each node N in the CT consists of A set of constraints (N.constraints). Each of these constraints belongs to a single agent.
The root of the CT is an empty set of constraints. The child of a node in the CT inherits the constraints of the parent and adds one new constraint for one agent. The solution also stores a set of k paths, one path for each agent. The path for agent-x must be consistent with the constraints of x. Such paths are found by the low-level search.
The total cost of the current solution (the agent with max cost is considered). Node N in the CT is an end node when the set of paths for all agents has no conflicts.
The high level performs a best-first search on the CT where nodes are ordered by their costs. Ties were broken in a FIFO manner the node with fewer conflicts was processed first.
When the list of constraints for a node N of the CT is ready, the low-level search is invoked. The low-level search returns one shortest path for each agent-x , that is consistent with all the constraints associated with x in node N. Once a consistent path has been found we iterate through each step of new path, if no two agents plan to be at the same location at the same time, this CT node N is declared as the goal node, and the current solution (N.solution) that contains this set of paths is returned. Otherwise the process is repeated.
Handling a conflict: When a non-goal CT node N whose solution includes a conflict
Cn = (agent-x, agent-y, vertex-v, time-t)
we know that in any valid solution, at most one of the conflicting agents (x and y) may occupy vertex v at time t. Therefore, we add at least one of the constraints so that new paths are obtained. Now to test all possible cases we make two child nodes each of which adds a different constraint (x,v,t) and (y,v,t). For each node we don't save all its previous constraints, only save current constraint and otter constraint can be accessed by traversing parent nodes till root node.
Conflicts of k > 2 agents
Method 1: We generate k children, each of which adds a constraint to k − 1 agents (i.e., each child allows only one agent to occupy the conflicting vertex v at time t).
Method 2: We only focus on the first two agents that are found to conflict, and only branch according to their conflict. This leaves further conflicts for deeper levels of the tree. The complexity of the two approaches is similar, as they both will end up with k nodes, each with k − 1 new constraints. For simplicity we implemented and describe only the second option.
Multi-Agent Path Finding (MAPF)
The multi agent path finding is problem is defined by map with the end locations and the set of agents each with the starting go locations.
Example:
The starting go locations of the green agents are A and F and the starting go locations of blue agents are D and E. At each time step an agent can either move to an adjacent location or wait in its current location. The task is to find the path for each agent such that the agent do not conflict while minimizing the sum of travel costs.
Explanation:
We can see a possible solution for this example , at cost 0 both the agents are either start locations, then there agents move to location D and H at this point one of the agents must wait to avoid the conflict and only the blue agent moves. The agents now move to locations C and E and then only the green agents move to the end location F and its cost is achieved.
MULTI AGENT path finding is applicable in many problems such as Traffic Control, Robotics, Video games etc. However in MAPF the agents occupy on each particular location at each time step while in reality agents can have different sizes and thus they can occupy more then one location at each time step.
CODE
Figure (i) MAPF example (ii) CT (iii) A case where A* outperforms CBS
ALGORITHM: high-level of CBS (and MA-CBS)
MAPF instance
Root.constraints = ∅
Root.solution = find individual paths by the low level()
Root.cost = SIC(Root.solution)
insert Root to OPEN
while OPEN not empty do
P ← best node from OPEN // lowest solution cost
Validate the paths in P until a conflict occurs.
if P has no conflict then
return P.solution // P is goal
C ← first conflict (ai, a j, v, t) in P
if shouldMerge(ai, a j) // Optional, MA-CBS only then
a{i, j} = merge(ai, a j, v, t)
Update P.constraints(external constraints).
Update P.solution by invoking low level(a{i, j} )
Update P.cost
if P.cost < ∞ // A solution was found then
Insert P to OPEN
continue // go back to the while statement
foreach agent ai in C do
A ← new node
A.constraints ← P.constraints + (ai, v, t)
A.solution ← P.solution
Update A.solution by invoking low level(ai )
A.cost = SIC(A.solution)
if A.cost < ∞ // A solution was found then
Insert A to OPEN
Note that for a given CT node N one does not have to save all its cumulative constraints. Instead, it can save only its latest constraint and extract the other constraints by traversing the path from N to the root via its ancestors. Similarly, with the exception of the root node, the low-level search should only be performed for agent ai which is associated with the newly added constraint. The paths of other agents remain the same as no new constraint was added for them.
CBS Example
Pseudo-code for CBS is shown in Algorithm . We note that lines (11-16) are to be ignored for basic CBS (that is, the should-merge() function (Line 11) always returns false for basic CBS). These lines will be added later for MA-CBS. CBS has the structure of a best-first search. We cover it using the example in Figure (i), where the mice need to get to their respective pieces of cheese. The corresponding CT is shown in Figure (ii). The root contains an empty set of constraints. In line 2 the low-level now returns an optimal solution for each agent, < S1, A1, C, G1 > for a1 and < S2, B1, C, G2 > for a2. Thus, the total cost of this node is 6. All this information is kept inside this node.
The root is then inserted into the sorted OPEN list and will be expanded next. When validating the two-agent solution given by the two individual paths (line 7), a conflict is found when both agents arrive to vertex C at time step 2. This creates the conflict (a1, a2, C, 2). As a result, the root is declared as non-goal and two children are generated in order to resolve the conflict (Line 17). The left child adds the constraint (a1, C, 2) while the right child adds the constraint (a2, C, 2). The low level search is now invoked (Line 21) for the left child to find an optimal path that also satisfies the new constraint. For this, a1 must wait one time step either at S1 (or at A1) and the path < S1, A1, A1, C, G1 > is returned for a1.
The path for a2, < S2, B1, C, G2 > remains unchanged in the left child. The total cost for the left child is now 7. In a similar way, the right child is generated, also with cost 7. Both children are added to OPEN (Line 23). In the final step the left child is chosen for expansion, and the underlying paths are validated. Since no conflicts exist, the left child is declared as a goal node (Line 9) and its solution is returned as an optimal solution. It may be the case that while performing the validation (Line 7) between the different paths a k-agent conflict is found for k > 2.
There are two ways to handle such kagent conflicts. We can generate k children, each of which adds a constraint to k −1 agents (i.e., each child allows only one agent to occupy the conflicting vertex v at time t). Or, an equivalent formalization is to only focus on the first two agents that are found to conflict, and only branch according to their conflict. This leaves further conflicts for deeper levels of the tree. For simplicity of description we chose the second option.
Low level: find paths for CT nodes
We take an agent x and the set of constraints associated with x. We find the path for current agents for given constraints ignoring other agents for the current process. Any single-agent path finding algorithm can be used to find the path for agent x , while making sure that the constraints are satisfied. We implemented the low-level search of CBS with A* which handled the constraints as follows:
Whenever a state (v,t) is generated where v is a location and time t and there exists a constraint (x, v, t) in the current CT (high-level) node, this state is discarded. For cases where two low-level A* states have the same cost, we used a tie-breaking policy based on Standley’s tie-breaking conflict avoidance table (CAT) . In it states that contain a conflict with a smaller number of other agents are preferred. For example, if states s1 = (x,t1) and s2 = (y,t2) have the same cost, but x is used by two other agents at time t1 while y is not used by any other agent at time t2, then s2 will be expanded first.
In this section we studied the Conflict-based Search for Multi-agent Path Finding. In this paper we deal with the multi-agent path finding problem (MAPF). We provided a short survey on previous work on the MAPF problem. Next, the CBS algorithm was introduced. CBS is a novel optimal MAPF solver. CBS is unique in that all low-level searches are performed as single-agent searches, yet it produces optimal solutions. The performance of CBS depends on the structure of the problem. We analyzed and explained cases and how they affect CBS’s performance.
MACBS is a faster algorithm which takes very less time to predict the optimal path for the given number of agents. It breaks the problem in two parts high level and low level and uses a conflict tree to solve the problem.This algorithm outperforms other algorithms if conflicts are less and map is dense or maps with large open spaces and few bottlenecks are there, or if more conflicts are there and weak MAPF solver (e.g., plain A*) is used for the low-level search.
Authors:
Rutuja Doiphode,
Ramrao Adik Institute of Technology Nerul,
Tushar Tripathi
ABES Engineering College
References :
https://arxiv.org/abs/2006.03280#:~:text=We%20study%20a%20variant%20of,and%20to%20a%20designated%20base.
aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5062/5239
https://www.researchgate.net/publication/278400742_Conflict-based_search_for_optimal_multi-agent_pathfinding
https://paperswithcode.com/task/multi-agent-path-finding/codeless
Comentarios