ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding

Introduction and Overview

A Multi-Agent Path Finding (MAPF) problem is defined by a graph, G = (V,E) and a set of k agents labeled a1 . . . ak, where each agent ai has a start position si ∈ V and a goal position gi ∈ V . At each time step an agent can either move to an adjacent location or wait in its current location. The task is to plan a sequence of move/wait actions for each agent ai, moving it from si to gi such that agents do not conflict, i.e., occupy the same location at the same time, while aiming to minimize a cumulative cost function. MAPF has practical applications in video games, traffic control, robotics etc. (see Sharon et al. 2013; 2015 for a survey).

In this paper we focus on solving MAPF problems optimally, i.e., where the cost of the resulting plan must be minimized. There is a range of algorithms that optimally solve different variants of MAPF using various search techniques [Standley, 2010; Wagner and Choset, 2011; Sharon et al., 2013] or by compiling it into other known NP-hard problems [Surynek, 2012; Yu and LaValle, 2013; Erdem et al., 2013]. Each of these solvers has pros and cons, with no universal winner. Which algorithm performs best under what circumstances is an open research question.

Conflict-Based Search (CBS) [Sharon et al., 2012a; 2015], is a very effective optimal MAPF solver. CBS has two-levels. The low-level finds optimal paths for the individual agents. If the paths include conflicts, the high level, via a split action (described below), imposes constraints on the conflicting agents to avoid these conflicts.

Two improvements to CBS were suggested. First, Metaagent CBS (MA-CBS) [Sharon et al., 2012b; 2015] generalizes CBS by merging small groups of agents into meta-agents David Tolpin Oded Betzalel Eyal Shimony CS Department Ben-Gurion University shimony@cs.bgu.ac.il when beneficial. The main merge policy is to merge agents for which the number of conflicts seen so far exceeds a given threshold B; for good choices of B, MA-CBS reduces the runtime. Second, the bypass (BP) improvement to (MA)CBS (i.e., CBS with or without applying the optional merge action) was recently suggested [Boyarski et al., 2015]. (MA)CBS arbitrarily chooses paths in the low-level. When BP is added on top of (MA)CBS we first try to find an alternative path (bypass) for one of the conflicting agents thus avoiding the need to perform a split and to add new constraints. (MA)CBS+BP further reduces the running time. A variant of CBS that solves MAPF suboptimally also appeared [Barer et al., 2014].

In this paper we introduce Improved-CBS (ICBS) which further adds two new improvements to (MA)CBS+BP. Each of these improvements is strongly tied to one of the former improvements (MA and BP) as follows:

• (1) Merge and restart. (MR) In MA-CBS, agents are merged locally at each node of the search tree. Instead, when a decision to merge is made, we suggest to restart the search from scratch, with the new merged meta-agent treated as a single agent for the entire search tree.
• (2) Prioritizing conflicts. (PC) (MA)CBS (even with BP added) arbitrarily chooses which conflict to split. Poor choices may increase the size of the high-level search tree. To remedy this, we prioritize the conflicts according to three types: cardinal, semi-cardinal and non-cardinal. Cardinal conflicts always cause an increase in the solution cost, so ICBS chooses to split cardinal conflicts first. Additionally, bypasses to cardinal conflict cannot exist. Therefore, the optional BP improvement [Boyarski et al., 2015] should only be applied for semi- or non-cardinal conflicts.

All four enhancements to CBS (i.e., MA-CBS, BP, PC and MR) are optional and can be added separately or in conjunction with the others, except for MR which is only relevant to MA-CBS. In this paper we show how to combine them all into a coherent improved version of CBS, namely ICBS.

Experimental results show that MR and PC each provide a significant speedup over the previous best CBS variant, namely (MA)CBS+BP [Boyarski et al., 2015]. Even further speedup is achieved when both improvements are combined and ICBS outperforms other related algorithms in many cases where previous variants of CBS performed poorly.

Algorithm 1: High-level of ICBS

1 Main(MAPF problem instance) 2 Init R with low-level paths for the individual agents 3 insert R into OPEN 4 while OPEN not empty do 5 N ←best node from OPEN // lowest solution cost 6 Simulate the paths in N and find all conflicts. 7 if N has no conflict then 8 return N.solution // N is goal 9 C ←find-cardinal/semi-cardinal-conflict(N) // (PC) 10 if C is not cardinal then 11 if Find-bypass(N, C) then // (BP) 12 Continue 13 if should-merge(ai, aj) then // Optional, MA-CBS: 14 aij = merge(ai,aj) 15 if MR active then // (MR) 16 Restart search 17 Update N.constraints() 18 Update N.solution by invoking low-level(aij) 19 Insert N back into OPEN 20 continue // go back to the while statement 21 foreach agent ai in C do 22 A ← Generate Child(N, (ai, s, t)) 23 Insert A into OPEN 24 Generate Child(Node N, Constraint C = (ai, s, t)) 25 A.constraints ←N.constraints + (ai, s, t) 26 A.solution←N.solution 27 Update A.solution by invoking low level(ai) 28 A.cost ←SIC(A.solution) 29 return A

The Conflict Based Search Algorithm (CBS)

A sequence of individual agent move/wait actions leading an agent from si to gi is referred to as a path, and the term solution refers to a set of k paths, one for each agent. A conflict between two paths is a tuple 〈ai, aj, v, t〉 where agent ai and agent aj are planned to occupy vertex v at time point t. A solution is valid if it is conflict-free. The cost of a path is the number of actions in it (including wait), and the cost of a solution is the sum of the costs of its constituent paths.

In CBS, agents are associated with constraints. A constraint for agent ai is a tuple 〈ai, v, t〉 where agent ai is prohibited from occupying vertex v at time step t. A consistent path for agent ai is a path that satisfies all of ai's constraints, and a consistent solution is a solution composed of only consistent paths. Note that a consistent solution can be invalid if despite the fact that the paths are consistent with the individual agent constraints, they still have inter-agent conflicts.

The high-level of CBS searches the constraint tree (CT). The CT is a binary tree, in which each node N contains: (1) A set of constraints imposed on the agents (N.constraints), (2) A single solution (N.solution) consistent with these constraints, (3) The cost of N.solution (N.cost).

The root of the CT contains an empty set of constraints. A successor of a node in the CT inherits the constraints of the parent and adds a single new constraint for a single agent.

N.solution is found by the low-level search described below. A CT node N is a goal node when N.solution is valid, i.e., the set of paths for all agents has no conflicts. The high-level of CBS performs a best-first search on the CT where nodes are ordered by their costs (N.cost).

Processing a node in the CT: Given a CT node N, the low-level search is invoked for individual agents to return an optimal path that is consistent with their individual constraints in N. Any optimal single-agent path-finding algorithm can be used by the low level of CBS. We used A* with the true shortest distance heuristic (ignoring constraints). 1

Once a consistent path has been found (by the low level) for each agent, these paths are validated with respect to the other agents by simulating the movement of the agents along their planned paths (N.solution). If all agents reach their goal without any conflict, N is declared as the goal node, and N.solution is returned. If, however, while performing the validation, a conflict is found for two (or more) agents, the validation halts and the node is declared as non-goal.

Resolving a conflict - the split action: Given a non-goal CT node, N, whose solution, N.solution, includes a conflict, 〈ai, aj, v, t〉, we know that in any valid solution at most one of the conflicting agents, ai or aj, may occupy vertex v at time t. Therefore, at least one of the constraints, 〈ai, v, t〉 or 〈aj , v, t〉, must be satisfied. Consequently, CBS splits N and generates two new CT nodes as children of N, each adding one of these constraints to the previous set of constraints, N.constraints. Note that for each (non-root) CT node the low-level search is activated only for one agent - the agent for which the new constraint was added.

CBS Example: Pseudo-code for CBS is shown in Algorithm 1. It is explained by the example in Figure 1(I). The mice need to get to their respective pieces of cheese. The shaded lines (9-20) are all optional (except for part of line 9; find-conflict is mandatory) and include: the merge action for the optional MA-CBS (lines 13-20), the BP improvement (lines 11-12) as well as the two new improvements (PC: lines 9-10, MR: 15-16), each discussed in its own section below. The corresponding CT is shown in Figure 1(II). The root (R1) contains an empty set of constraints and the lowlevel returns path P1 = 〈S1,A,C,G1〉 for agent a1 and path P2 = 〈S2,B,C,G2〉 for agent a2 (line 2). Thus, the total cost of R1 is 6. R1 is then inserted into OPEN and will be expanded next. When validating the two-agents solution (line 6), a conflict 〈a1, a2,C, 2〉 is found. As a result, R1 is declared as non-goal. R1 is split and two children are generated (via the generate-child() function, also shown in Algorithm 1) to resolve the conflict (line 22). The left child U adds the constraint 〈a1,C, 2〉 while the right child V adds the constraint 〈a2,C, 2〉. The low-level search is now invoked (line 27) for U to find an optimal path for agent a1 that also satisfies the new constraint. For this, a1 must wait one time step at S1 and the path 〈S1, S1, A, C, G1〉 is returned for a1. The path for a2, 〈S2, B, C, G2〉, remains unchanged in U. Since the cost of a1 increased from 3 to 4 the cost of U is now 7. In a similar way, the right child V is generated, also with cost 7. Both children are added to OPEN (line 23). In the final step U is chosen for expansion, and the underlying paths are validated. Since no conflicts exist, U is declared as a goal node (lines 6-8) and its solution is returned.

1 Ties between low-level nodes are broken using a conflictavoidance table (CAT) [Standley, 2010] which keeps track of the conflicts between agents. Paths with fewer conflicts are preferred.

Meta-agent merging improvements

In this section we deal with improvements that are based on merging agents into a meta-agent. We first describe the basic merge operation and then provide our new improvement.

Previous work: MA-CBS

MA-CBS(B) [Sharon et al., 2012b; 2015] generalizes CBS by adding the option to merge the conflicting agents ai and aj into a meta-agent (Lines 13-20) instead of the split action. A meta-agent is logically treated as a single composite agent, whose state consists of a vector of locations, one for each individual agent. A meta-agent is never split in the subtree of the CT below the current node; it may, however, be merged with other (meta)agents into new meta-agents. The following actions are performed for a new meta-agent. (1) The constraints from the two merged agents are unified (Line 17, see [Sharon et al., 2012b; 2015] for details). (2) We now call the low-level search again for this new meta-agent only (Line 18), as nothing has changed for the other agents that were not merged. In fact, the low-level search for a meta-agent of size M faces an optimal MAPF problem for M agents, and is solved with any coupled MAPF solver (e.g., A*).

Merge policy: The optional merge action is performed only if the should-merge() function returns True (Line 13). Many merging policies are possible for the should-merge() function. [Sharon et al., 2012b; 2015] presented a simple, experimentally-effective merge policy. Two agents ai and aj are merged into a meta-agent aij if the number of conflicts between ai and aj seen so far during the search exceeds a predefined parameter B. Otherwise, a regular split is performed. This merge policy is denoted by MA-CBS(B). MA-CBS was shown to outperform CBS (without the merge option).

ICBS Improvement 1: Merge and Restart

Drawback

Merging agents into meta agents reduces the size of the CT at the cost of higher computational effort by the low-level solver. In MA-CBS this tradeoff is handled ad-hoc by requiring B splits before performing a merge. Nevertheless, MACBS may still duplicate much search effort.

As an example, consider a problem with only two agents (a1, a2). Suppose the agents were merged after encountering B conflicts and performing B split actions. At this point OPEN contains B + 1 CT nodes. A merge action may now be activated in all these nodes as the number of seen conflicts between these agents already exceeds B. As a result, exactly the same merge action (with the same meta-agent low-level searches) will be duplicated B + 1 times for all these nodes when they appear at the top of OPEN. Each of these merges produces identical CT nodes, i.e., one meta-agent a1,2 and no constraints (as all internal constraints between a1 and a2 are deleted; see [Sharon et al., 2015] on merge action details). 2

Remedy

Had we known that a pair of agents are due to be merged, significant computational effort would have been saved by performing the merge ab-initio, at the root node of the CT. This "clairvoyant" merging policy is clearly observed to dominate MA-CBS(B) in auxiliary experiments we performed for various values of B. Naturally, "clairvoyant" is not realizable. Instead, we suggest a simple ad-hoc merge policy with a good balance between simplicity and effectiveness. Once a merge decision has been reached inside a CT node N, discard the current CT and restart the search from a new root node, where these agents are merged into a meta agent at the beginning of the search. We call this the merge and restart (MR) scheme. It is optionally applied in lines 15-16 of Algorithm 1.

MR is simple to implement, and saves much effort duplicated in the multiple CT nodes. In our example we would initially still generate B + 1 copies of the same problem, but then restart and only solve one instance of the problem for the meta-agent, thereby reducing the low-level effort for meta-agent a1,2 by a factor of B. In contrast, MR might lose information when more agents are considered. For example, if our problem also contained a third agent a3, which already conflicted with a1 before the formation of meta-agent a1,2 then split actions between a1 and a3 were also performed. Once a1 and a2 are merged, the entire process restarts and all constraints imposed on a3 may have to be rediscovered.

Nevertheless, in most cases the gains outweigh the additional overhead. As it is very hard to model these quantities theoretically, we tested MR empirically (Section ), and indeed it speeds up the search by a significant factor.

Improvements on the split action

CBS is very sensitive to the paths found by the low level and to the conflicts chosen for the splits. To this end we first summarize a previously published improvement (BP) and then introduce the new improvement (PC).

2 Duplicate detection and pruning can be applied in this extreme example because it only includes agents a1 and a2. But in general, when other agents exist this is not possible.

Previous work: the bypass improvement (BP)

[Boyarski et al., 2015] introduced the bypass improvement (BP), which improves the low-level paths in a number of ways, thereby reducing the CT size. Here, we summarize the simplest variant and use it to build the final Improved-CBS.

Drawback

Consider Figure 2(I). Suppose that at the root of the CT (R1) the low-level is first activated for a2 and that path P2 = 〈S2,B,D, F,G2〉 is found. a1 uses the conflict avoidance table (CAT, described above) and finds path P1 = 〈S1,A,C,E,G1〉. There are no conflicts between these two paths and R1 is declared as the goal as shown in Figure 2(II).

Now suppose that a1 goes first and finds path P ′1 = 〈S1,B,D, F,G1〉. Suppose that a2 then finds path P ′2 = 〈S2,B,D,E,G2〉 as shown in the root (R2) of Figure 2(III). At R2 two conflicts are found C1 = 〈a1, a2, B, 1〉 and C2 = 〈a1, a2, D, 2〉. Suppose that C1 is chosen for a split at R2. The left child M is generated with path P1 = 〈S1,A,C,E,G1〉 (cost 8) and both conflicts (C1 and C2) are resolved. But M includes another conflict C3 = 〈a1, a2, E, 3〉. Since a1 must be at E at time step 3 then in its left child O, a1 is forced to wait and a cost of 9 is achieved. In its right child P a2 will choose path P2 = 〈S2, B, D, F, G2〉 which is the goal node.

We showed two scenarios. In the first, a single CT node was generated while in the second scenario 5 CT nodes were generated only due to poor choices of the paths at the root.

Remedy: Bypassing Conflicts

It is sometimes possible to prevent a split action and bypass the conflict by modifying the chosen path of one of the agents. For this we first make the following definitions.

(1) For each CT node N we use N.NC to denote the total number of conflicts of the form 〈ai, aj , v, t〉 between the paths in N.solution. Calculating N.NC is trivial.

(2) A path P ′ i is a valid bypass to path Pi for agent ai with respect to a conflict C = 〈ai, aj, v, t〉 and a CT node N, if the following conditions are satisfied: (i) Unlike Pi, P ′ i does not include conflict C, (ii) cost(P ′ i ) = cost(Pi) and (iii) Pi and P ′ i are both consistent with N.constraints.

1. Adopting path P ′ i by a CT node N means replacing Pi with a valid bypass P ′ i for agent ai.
2. Adopting a valid bypass may introduce more conflicts compared to the original path and potentially lead to worse overall runtime. Thus, we only allow adopting bypasses that reduce N.NC. These are called helpful bypasses.

Bypassing conflicts (BP): For a given CT node N, BP peeks at either of the immediate children of N in the CT (by invoking generate-child(), presented in Algorithm1). If the path of a child includes a helpful bypass for the conflict of N this path is adopted by N without the need to split N and add new nodes to the CT. This can potentially save a significant amount of search due to a smaller size CT. BP is optionally added to the CBS pseudo code (lines 11-12 in Algorithm 1).

Example: consider again the root R2 of Figure 2(III). R2 is split into two nodes as described above. In the left child M agent a1 finds path P1 = 〈S1,A,C,E,G1〉. However, R2 can adopt path P1 for agent a1. P1 is a valid bypass because it does not include conflict C1 = 〈a1, a2, B, 1〉 which caused the split. In addition, it is a helpful bypass because R2.NC = 2 (conflicts C1 and C2) but after adopting the path fromM, R2.NC will decrease to 1 (conflict C3). Now, instead of a CT with 5 nodes we get a CT with only 3 nodes.

While processing a node N, BP incurs no extra overhead due to peek operations. Basic CBS generates both children and adds both to OPEN. In the worst case when both peek operations fail, BP does exactly the same as CBS, i.e., generates and adds these children to OPEN. But if one of these nodes is found helpful then BP adds no new nodes to OPEN and might even avoid the need to generate and run a low-level search for the 2nd child if the first child includes a helpful bypass.

Additionally, note that node N in its "new suit", i.e., after adopting a path, will now be the best node in OPEN and will be chosen for expansion next. 3 Therefore, if it has a helpful child again then BP will be repeated here. In fact, the next real split will occur only when a bypass call fails.

ICBS Improvement 2: Prioritize Conflicts (PC)

Drawbacks of (MA)CBS and (MA)CBS+BP

To guarantee optimality, CBS expands nodes in a best-first order according to the cost function. While A* expands all nodes with f < C ∗ (= the optimal solution cost) to guarantee optimality of the solution no such mandatory nodes are known for CBS. Consequently, CBS (even with BP) is very sensitive to the conflicts chosen to split on, as these can significantly influence the number of CT nodes. In its basic form, CBS arbitrarily picks a conflict for splitting (e.g., the first one seen). This can lead to poor performance and CBS can be stuck in an area with similar cost as demonstrated below.

Remedy: Splitting cardinal conflicts first

To address this drawback we distinguish between three types of conflicts and show that prioritizing them may immediately increase the solution cost in the sub-tree below the current node thereby significantly reducing the size of the CT.

3 A mechanism like immediate expand [Stern et al., 2010] which bypasses OPEN can be efficiently activated here.

• (1) Cardinal conflict. A conflict C = 〈a1, a2, v, t〉 is cardinal for a CT node N if adding any of the two constraints derived from C (〈a1, v, t〉, 〈a2, v, t〉) to N and invoking the low-level on the constrained agent, the cost of its path is increased when compared to its cost in N. An equivalent definition is that C is cardinal if all the consistent optimal paths for both a1 and a2 include location v at time step t. For example, in Figure 1(I) the conflict 〈a1, a2, C, 2〉 is cardinal. None of the agents has a path to its goal of length 3 which doesn't pass through C in time step 2. Therefore, one of these agents must travel more than three steps in order to resolve this conflict.
• (2) Semi-cardinal conflict. A conflict C = 〈a1, a2, v, t〉 is semi-cardinal for a CT node N if adding one of the two constraints derived from C increases N.cost but adding the other leaves N.cost unchanged. Equivalently, C is semi-cardinal if all the consistent optimal paths of one agent include location v at time step t, but the other agent has such a path that does not include v at time step t. For example, the conflict 〈a1, a2,B, 1〉 in Figure 1(I) is semi-cardinal (assuming the paths are P1 = 〈S1,B,C,G1〉 and P2 = 〈S2,B,C,G2〉). a2 must use B at time step 2, but a1 can choose A instead.
• (3) Non-cardinal conflict. A conflict C = 〈a1, a2, v, t〉 is non cardinal for a CT node N if neither of the two constraints derived from C causes an increase of N.cost. For example, in Figure 1(I), if the dotted lines (path through D) are enabled then the conflict 〈a1, a2,B, 1〉 is non-cardinal. Now agent a2 can choose to go via node D at the same cost.

We now make the following observations: (1) If a cardinal conflict exists for CT node N then the cost of a valid solution below N must be greater than N.cost. (2) In any best-first search increasing a lower bound of a node in OPEN is beneficial as this lower bound is more informed.

Prioritization of conflicts (PC):

This new improvement works as follows. When a node N with N.cost = c is chosen for expansion by CBS, we examine all its conflicts. If a cardinal conflict is encountered, it is immediately chosen for the split action. This generates two children with cost > c. In this case if another node N ′ in OPEN has cost c, then N ′ can be immediately chosen for expansion next without further developing nodes below N. 4 In contrast, if a cardinal conflict exists but instead we choose a semi-cardinal or a non-cardinal conflict, we may generate a large subtree below N with the same cost c. Furthermore, the cardinal conflict will reappear in all of the nodes in the subtree belowN until it is chosen and resolved.

To illustrate this, consider again Figure 1(I) (assuming the paths chosen at R1 are P ′1 = 〈S1,B,C,G1〉 and P2 = 〈S2,B,C,G2〉). Two conflicts exist in the root node: a semicardinal conflict C1 = 〈a1, a2,B, 1〉 and a cardinal conflict C2 = 〈a1, a2,C, 2〉. If C2 were chosen (Figure 1(II)) the costs increase immediately and the left child is declared as the goal. In contrast, Figure 1(III) illustrates the case where C1 is chosen. In a simple implementation, it will be chosen as it is seen first. In its left child M the constraint (a1,B, 1) is added and a1 will choose the path P1 = 〈S1,A,C,G1〉. However, the cardinal conflict C2 still exists and will be again chosen for a split. There are 5 nodes in the corresponding CT (Figure 1(III)). In contrast, the CT of Figure 1(II) has 3 nodes.

4 Based on this, our optimized implementation pushes N back into OPEN with the new cost without even generating the two children. This proved beneficial in our experiments.

If no cardinal conflicts exist, the next preference is to choose semi-cardinal conflicts. Here, we know that the cost of at least one child will immediately increase. Finally, if only non-cardinal conflicts exist, one of them is chosen arbitrarily.

PC is shown in line 9, where we seek a cardinal/semicardinal conflict. [Boyarski et al., 2015] suggested to apply BP for every conflict. However, in this paper we note that valid bypasses (with the same cost) can only be found for semi- or non-cardinal conflicts but not for cardinal conflicts. Therefore, in ICBS BP is applied more conservatively: with a cardinal conflict, we jump to line 13 and BP is not activated. Otherwise (only semi- or non-cardinal conflicts were found) we continue with the pseudo code allowing to perform BP on the chosen conflict.

Identifying a cardinal conflict using MDDs

The multi-value decision diagram MDDc i [Sharon et al., 2013] is a DAG which compactly stores all possible paths of given cost c for a given agent ai while completely ignoring the other agents. Nodes of the MDD can be distinguished by their depth below the source node. Every node at depth t of MDDc i corresponds to a possible location of ai at time t that is on a path of cost c from si to gi. MDDc i has a single source node at level 0, corresponding to agent ai located at si at time t0, and a single sink node at level c, which corresponds to agent ai located at gi at time tc. The nodes of MDD3 1 which corresponds to paths of length 3 for agent a1 have a small black circle in their lower part in Figure 1(I). Observation: If, for a CT node N with N.cost = c, there exists a cardinal conflict C of the form 〈ai, aj , D, t〉, then the

widths of MDDci i andMDDcj j at time-step t must be 1.

Therefore, to find cardinal conflicts in CT node N we iterate over all conflicts C in N and test each conflict C = 〈ai, aj,D, t〉 for cardinality by building MDDci i and MDDcj j (ci is the cost of path of ai in N.cost) and checking whether their width at depth t is 1. This is repeated until a cardinal conflict is found or all the conflicts in N have been checked. If no cardinal conflict is found, a semi cardinal conflict is chosen if it was encountered during the iteration. Otherwise, a non-cardinal conflict is arbitrarily chosen.

Maintaining and checking all MDDs incurs an overhead per CT node. But, this pays off in dense environments with many bottlenecks where many cardinal conflicts exist. 5

Meta-agent conflicts. Building an MDD for meta-agents is expensive. Therefore in our implementation for MA-CBS we first build MDDs for meta-agents of size 1 (individual agents) which participate in a conflict. If a cardinal conflict was not found, we then try to find cardinal or semi-cardinal conflicts for larger meta-agents. We do this by logically generating the two children of the conflict and observing their costs.

5 In a practical implementation MDDs can be reused from parents when applicable. In addition, to find a cardinal conflict quickly, we check MDDs of agents in decreasing order of the number of conflicts in which they participate.

Experimental Results

We performed extensive experiments on many possible parameter settings of the environment and of internal algorithmic parameters. We report representative results. First, we concentrate on each of our improvement alone compared to previous CBS solvers. We then take our best CBS variant (ICBS) and compare it to other known MAPF solvers.

The code for all the experiments was written in C# and all our experiments were conducted on Amazon Elastic Compute Cloud C4 servers running Microsoft Windows Server 2012 R2. Each High frequency Intel Xeon E5-2666 v3 (Haswell) processor operates at 2.9GHz, and has 3.33GB of RAM.

Each improvement vs. baseline

Our first experiment compares PC and MR against the corresponding baseline, i.e., CBS+BP and MA-CBS+BP, respectively. 6 Figure 3(a) shows the success rate (=number of instances solved by each algorithm within 5 minutes) for CBS, CBS+BP, CBS+PC and CBS+PC+BP (both improvements) on 8x8 4-connected grids with 15% obstacles averaged on 100 random instances. 7 CBS+PC clearly outperforms CBS+BP [Boyarski et al., 2015], the previous best CBS variant. CBS+PC+BP even further increases the success rate. Figure 3(b) presents a table with the runtime (in ms) and number of generated CT nodes averaged over those instances that were solved by all the algorithms (=success rate of CBS). CBS+BP (=previous state-of-the-art CBS solver) serves as the baseline (the 'BP' column) and the other columns present percentages (%) relative to CBS+BP . Clearly CBS+PC and CBS+PC+BP outperform CBS+BP by up to a factor of 5 on this set. The improvement in nodes is nicely reflected in the runtime (e.g., 17% vs. 21%). This suggests that the overhead per node for PC and for BP is minor.

6 We followed Sharon et al. [2013; 2015] and for this experiment we activate the Independence Detection framework [Standley, 2010] in a preprocessing level and identify problem instances for which the agents are dependent. These were called type 1 experiments by Sharon et al. [2013; 2015].

7 The starting positions for agents were chosen randomly and their goal positions were chosen by a 100000-step random walk from the starting position.

Figure 3(c,d) shows the success rate and runtime/nodes results when comparing MA-CBS(64)+BP to MA-CBS(64), MA-CBS(64)+MR and MA-CBS(64)+BP+MR on a 20x20 empty grid. Here too, the percentages are relative to MACBS(64)+BP. Again, the advantage of adding MR can be clearly seen in all measures. Importantly, note that here, the runtime improvement of MR is larger than the improvement in nodes. This is because by restarting, MR cancels many CT nodes that have heavy computations.

Comparison with other algorithms

Finally, based on extensive experiments we fine-tuned a number of leading algorithms with the best parameters. We compare ICBS(25) (=MA-CBS(25)+BP+PC+MR), to the following other MAPF solvers: (1) MA-CBS(25)+BP, the best former CBS variant. (2) MA-CBS(25) (3) EPEA* [Felner et al., 2012; Goldenberg et al., 2014], an enhanced version of A* designed for cases with large branching factors, the best A* variant. (4) ICTS+p [Sharon et al., 2013; 2011], the best ICTS variant.

Figure 4 presents the success rate (left) and runtime (right) for the three standard benchmark maps (brc202d:top, ost003d:middle, den520d:bottom) of the game Dragon Age: Origins (DAO) [Sturtevant, 2012] that were used by Sharon et al. [2013; 2015], 100 instances per map. 8

In all three maps, ICBS is clearly the best CBS variant and it clearly outperforms the previous best CBS variant, namely MA-CBS+BP. ICBS is also the best algorithm amongst the ones compared here in runtime. ICBS is also the best in success rate for brc202d and for den520d. In ost003d there is a tie between ICBS, EPEA* and ICTS in the success rate. In this map the number of conflicts is very large due to open spaces (see [Sharon et al., 2015]). Thus, the previous CBS variants spawn a very large CT in this map and were worse than the other algorithms. But, ICBS provides a great improvement and was able to tie with the other algorithms on this map. It is important to note that no MAPF solver is best across all circumstances and all topologies.

Conclusions and Future Work

When CBS is used, adding all our improvements proved beneficial. ICBS is the best or ties with other solvers as demonstrated empirically on standard benchmarks. Future work will: (1) Further study the attributes and the relations between these enhancements. (2) Find a better merge policy than a fixed B parameter. (3) Compare and better understand the pros and cons of the various MAPF algorithms under different circumstances.

Acknowledgements

The research was supported by the Israeli Science Foundation (ISF) under grant #417/13 to Ariel Felner and Eyal Shimony.