Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding

1 Introduction

The multi-agent pathfinding (MAPF) problem aims to assign collision-free paths for multiple agents on a graph. To date, various MAPF algorithms have been developed, motivated by various applications such as warehouse automation [Wurman et al., 2008]. Ideal MAPF algorithms will be complete, optimal, quick, and scalable. However, there is generally a tradeoff between the former two and the latter two. Conversely, the primary challenge of developments in MAPF algorithms is to guarantee solvability and solution quality, while suppressing planning efforts to secure speed and scalability.

To break this tradeoff, we present two enhancements to the recently-developed algorithm called LaCAM (lazy constraints addition search for MAPF) [Okumura, 2023]. It is complete, sub-optimal, and search-based (akin to A∗ search) that uses lazy successor generation. The first enhancement is its anytime version called LaCAM∗ that eventually converges to optima, provided that solution costs are accumulated transition costs. Since solving MAPF optimally is computationally intractable [Yu and LaValle, 2013], one practical approach to large instances is obtaining sub-optimal solutions and then refining their quality as time allows. LaCAM∗ meets such demands. The second enhancement is for the successor generation, i.e., tuning of the PIBT algorithm [Okumura et al., 2022], so as to quickly obtain initial solutions.

With these enhancements, we empirically demonstrate that LaCAM∗ can break the trade-off. For instance, it suboptimally solved 99% of the instances retrieved from the MAPF benchmark [Stern et al., 2019] within ten seconds while guaranteeing the eventual optimality, on a standard desktop PC. As illustrated in Fig. 1, this result is beyond frontiers of existing MAPF algorithms. In what follows, we present preliminaries, LaCAM∗ , improved successor generation, empirical results, and discussion in order. The appendix and code are available at https://kei18.github.io/lacam2/.

expanded

0 1 2 3

3 4

4

5

5 4 3 4 5 6

5 4 5 6

2 Preliminaries

2.1 Notation, ProblemDefinition, and Assumption

Notations. S[k] denotes the k-th element of the sequence S, where the index starts at one. For convenience, we use ⊥ as an "undefined" or "not found" sign.

Instance. An MAPF instance is defined by a graph G = (V,E), a set of agents A = {1, . . . , n}, a tuple of distinct starts S = (si ∈ V )i∈A and goals G = (gi ∈ V )i∈A.

Configuration. A configuration is a tuple of locations for all agents. For instance, Q = (v1, v2, . . . , vn) ∈ V |A| is a configuration, where Q[i] = vi is the location of agent i ∈ A. The start and goal configurations are S and G, respectively.

Collision and Connectivity. A configuration Q has a vertex collision when there is a pair of agents i, j ∈ A, i ̸= j, such that Q[i] = Q[j]. Two configurations X and Y have an edge collision when there is a pair of agents i, j ∈ A, i ̸= j, such that X[i] = Y [j]∧Y [i] = X[j]. Let neigh(v) be a set of vertices adjacent to v ∈ V . Two configurations X and Y are connected when Y [i] ∈ neigh(X[i]) ∪ {X[i]} for all i ∈ A, and, there are neither vertex nor edge collisions in X and Y .

Decision Problem. Given an MAPF instance, an MAPF problem is a decision problem that asks existence of a sequence of configurations Π = (Q0,Q1, . . . ,Qk), such that Q0 = S, Qk = G, and any two consecutive configurations in Π are connected. A solution to MAPF is a Π that satisfies the conditions. To align with the literature, the index of Π exceptionally starts at zero (i.e., Π[0] = Q0). An algorithm is said to be complete when it returns solutions for solvable instances and reports non-existence for unsolvable instances. Otherwise, it is called incomplete.

Optimization Problems. Given a transition (or edge) cost between two configurations, coste : V |A| × V |A| ↦→ R≥0, we aim at minimizing accumulated transition costs of a solution Π, denoted as cost(Π) := ∑k-1 t=0 coste (Π[t], Π[t + 1]). This notation can represent various optimization metrics. For instance, cost is called makespan when coste(X, Y ) := 1. It is called sum-of-fuels (aka. total travel distance) when cost(X, Y ) := |{i ∈ A;X[i] ̸= Y [i]}|. Sum-of-loss counts actions of non-staying at goals, defined by coste(X, Y ) := |{i ∈ A | ¬(X[i] = Y [i] = gi)}|. A solution Π is optimal when there is no solution Π′ such that cost(Π′ ) < cost(Π).

Remarks for Flowtime. Another common metric of MAPF is flowtime (aka. sum-of-costs): ∑i∈A ti, where ti ≤ k is the earliest timestep such that Π[ti][i] = Π[ti +

no constraint

not go up

1][i] = . . . = Π[k][i] = gi. The difference from sumof-loss is cost contribution of agents who once reach their goal and leave there temporarily. The flowtime is historydependent on paths of each agent; hence, it is impossible to represent as it is with accumulative costs. 1 Instead, this paper considers sum-of-loss as seen in [Standley, 2010; Wagner and Choset, 2015].

Admissible Heuristic. We assume an admissible heuristic h : V |A| ↦→ R≥0, such that h(Q) is always the optimal cost from Q to G or less; e.g., h(Q) := ∑i∈A dist(Q[i], gi) is available for the sum-of-{loss, fuels}, where dist : V ×V ↦→ N≥0 is the shortest path length on G.

UnderstandingMAPF asGraphPathfinding. Using configurations, consider a graph H comprising vertices that represent configurations, and edges that represent the connectivity of configurations. Then, by regarding S and G as start and goal vertices respectively, optimal MAPF is equivalent to the shortest pathfinding problem on H. This is a key perspective to understand LaCAM(∗) .

2.2 LaCAM

LaCAM [Okumura, 2023] was originally developed as a suboptimal complete MAPF algorithm. In a nutshell, it is a graph pathfinding algorithm, like A∗ , but some parts are specific to MAPF. Below, we provide the essence of the graph pathfinding part, using an example of single-agent grid pathfinding. The details of the MAPF-specific part are delivered in the appendix.

Classical Search. See Fig. 2a that illustrates how a typical search scheme solves grid pathfinding. Specifically, we show the greedy best-first search with a heuristic of the Manhattan distance. Here, a location of the agent corresponds to a configuration (aka. state) of the search. From the start configuration, the search generates three successor nodes: left, up, and right. Each node corresponds to one configuration. The search then takes one of the generated nodes according to the heuristic, and generates successors. This procedure continues until finding the goal configuration.

Branching Factor. Consider how many nodes are generated to estimate the search effort. Though the solution length is 8, 22 nodes are generated. This number is related to the number of connected configurations (i.e., branching factor). It is four in grid pathfinding, therefore, the number of node

1 However, it is worth noting that flowtime can be defined by introducing virtual goals, where once an agent has arrived there, it cannot move anywhere in the future.

not go

right generations remains acceptable. However, the branching factor of MAPF is exponential for the number of agents. Consequently, the generation itself becomes intractable. This is why a vanilla A∗ is hopeless to solve large MAPF instances.

Configuration Generator. LaCAM tries to relieve this huge-branching-factor issue when a configuration generator is available. Given a configuration and constraints, it generates a connected configuration following constraints. Constraints should be embodied by each domain. In this example, consider a constraint as a prohibition of direction, such as not moving up, left, right, or down.

Constraint Tree. Each search node of LaCAMcontains not only a configuration but also constraints, taking the form of a tree structure. For each node invoke, LaCAM gradually develops the tree by low-level search, implemented by, e.g., breadth-first search (BFS). A node on the tree has a constraint and represents several constraints by tracing a path to the root.

Search Flow. We now explain LaCAM using Fig. 2b-e, with a depth-first search (DFS) style. The attempt to find a sequence of configurations is called high-level search. At first, a search node of the start is examined (Fig. 2b). The node poses no constraints for the first invoke, meaning that the configuration generator can output any connected configuration. Suppose that the generator outputs an "up" configuration, following the Manhattan distance guide, illustrated by the pink arrow. Preparing for the second invoke, the node expands a constraint tree with new constraints (e.g., "not go up"). The high-level search does not discard the examined node immediately, rather, it discards when all connected configurations have been generated (i.e., when the low-level search completes). Next, Fig. 2c-d show an example of the second invoke of nodes. In Fig. 2c, the generator outputs an alreadyknown configuration. Since this example assumes DFS, LaCAM examines the blue-colored node again in Fig. 2d. This time, the generator must follow a constraint "not go right" and its parent "no constraint." The example then generates a "left" configuration. The search continues until finding the goal (Fig. 2e) and obtains a solution path by backtracking.

Adaptation to MAPF. With appropriate designs of constraints and tree construction, LaCAM can be an exhaustive search and guarantees completeness for graph pathfinding problems. In [Okumura, 2023], such an example is shown for MAPF by letting a constraint specify which agent is where in the next configuration. Moreover, LaCAM can greatly decrease the number of node generations if the configuration generator is promising in outputting configurations that are close to the goal. This reduction could be a silver bullet to achieve quick planning, especially in planning problems where the branching factor is huge like MAPF. The remaining question is a realization of good configuration generators. In the original paper, PIBT (priority inheritance with backtracking) [Okumura et al., 2022] served as it, explained in Sec. 2.3.

Pseudocode. Algorithm1 shows DFS-based LaCAM. Each search node N stores (i) a configuration, (ii) a constraint tree embodied by a queue (assuming BFS) and (iii) a pointer to a parent node (see Line 2). Nodes are stored in an Open list and

Algorithm 1 LaCAM. Cinit means "no constraint."

input: MAPF instance output: solution or NO_SOLUTION 1: initialize Open, Explored ▷ stack, hash table 2: N init ← 〈 config : S, tree : � C init �, parent : ⊥ 〉 3: Open.push (N init ); Explored[S] =N init 4: while Open ̸= ∅ do 5: N ←Open.top() 6: if N.config = G then return backtrack(N) 7: if N.tree = ∅ then Open.pop(); continue ▷ discard node 8: C ←N.tree.pop() ▷ get constraint 9: low_level_expansion(N , C) ▷ proceed low-level search 10: Qnew ← configuration_generator(N, C) 11: if Qnew = ⊥ then continue ▷ generator may fail 12: if Explored [Qnew ] ̸= ⊥ then continue 13: N new ← ⟨ config : Qnew , tree : � C init � , parent : N 〉 14: Open.push (N new ); Explored [Qnew ] =N new 15: return NO_SOLUTION

Algorithm 2 PIBT

input: configuration Qfrom , agents A, goals (g1, . . . gn)

output: configuration Qto (each element is initialized with ⊥) 1: for i ∈ A do; if Qto [i] = ⊥ then PIBT(i) 2: return Qto 3: procedure PIBT(i) ▷ return VALID or INVALID 4: C ← neigh (Qfrom [i]) ∪ {Qfrom [i]} ▷ candidate vertices 5: sort C in ascending order of dist(u, gi) where u ∈ C 6: for v ∈ C do 7: if collisions in Qto supposing Qto [i] = v then continue 8: Qto [i] ← v 9: if ∃j ∈ A s.t. j ̸= i ∧ Qfrom [j] = v ∧ Qto [j] = ⊥ then 10: if PIBT(j) = INVALID then continue 11: return VALID ▷ assignment done 12: Qto [i] ←Qfrom [i]; return INVALID

Explored table, akin to general search schema, and are processed one by one. We abstract how to create constraint trees for MAPF by Line 9, which is elaborated in the appendix.

2.3 PIBT

PIBT [Okumura et al., 2022] was originally developed to solve MAPF iteratively. In a nutshell, it is a configuration generator, which generates a new connected configuration (Qto ), given another (Qfrom ) as input. By continuously generating configurations, PIBT can generate a solution for MAPF.

Concept. To determine Qto , PIBT sequentially assigns a vertex to each agent while avoiding assignments that trigger collisions. This assignment order adaptively changes. Specifically, before fixing Qto [i] to v ∈ neigh(Qfrom[i])∪{Qfrom[i]}, PIBT first checks the existence of j ∈ A such that Qfrom[j] = v. If such j exists, j may have no candidate vertex for Qto [j], due to collision avoidance (see Fig. 3a). Therefore, PIBT next determines Qto [j] prior to locations of other agents (e.g., k in Fig. 3). This scheme is called priority inheritance. If Qto [j] is successfully assigned, Qto [i] is fixed to v (Fig. 3b); otherwise, Qto [i] needs to take another vertex other than v.

Pseudocode. Algorithm 2 implements the concept above, by recursively calling a procedure PIBT (Line 3-), which takes an agent i and eventually assigns Qto [i]. The assignment attempts of Lines 6-11 are performed for candidate vertices regarding Qfrom[i], in ascending order of the distance toward gi. The attempts continue until Qto [i] is determined, resulting in VALID outcome (Line 11). When all attempts failed, PIBT(i) assigns Qfrom[i] to Qto [i] and returns INVALID (Line 12). Priority inheritance is triggered as necessary, taking the form of calling PIBT for another agent j (Line 10). The success of priority inheritance triggers receipt of VALID; otherwise, INVALID is backed, and then i continues the assignment attempts.

Dynamic Priorities. In addition to priority inheritance, PIBT prioritizes assignments for agents that are not on their goal, which is done by sorting A of Line 1 in that way. This scheme is convenient for lifelong scenarios wherein all agents are not necessarily being goals simultaneously.

3 LaCAM∗ : Eventually Optimal Algorithm

Algorithm 3 presents LaCAM∗ . The same lines as LaCAM (Alg. 1) are grayed out. The blue-colored lines are not necessary from the theoretical side but are effective in speeding up the search. The main differences from LaCAM are two: (i) it continues the search when finding the goal configuration G, and, (ii) it rewrites parent relations between search nodes as necessary. For convenience, the transition cost coste and admissible heuristic h can take nodes as arguments, instead of configurations. Below, the updated parts are explained.

KeepingGoal Node. LaCAM∗ retains the goal nodeN goal , rather than immediately returning solutions when first finding the goal G (Line 6). The search terminates when there is no remaining node in Open; otherwise, there is an interruption from users such as timeout (Line 4). A solution is then constructed by backtracking from N goal (Lines 27-28). Doing so makes LaCAM∗ an anytime algorithm, that is, after finding the goal node, it is interruptible whenever a solution is required, while gradually refining solution quality as time allows.

Search Node Ingredients. Each high-level node contains a set neigh that stores connected configurations (i.e., nodes) and g-value that represents cost-to-come from the start S (Line 2). They are initialized and updated appropriately when finding a new configuration (Lines 24-26).

Updating Parents and Costs. To maintain the optimality, when finding an already known configuration, LaCAM∗ updates neigh (Line 14). This is followed by updates of g-value and parent, performed by Dijkstra's algorithm (Lines 1521). Figure 4 illustrates the update.

Algorithm 3 LaCAM∗ . Cinit means "no constraint."

input: MAPF instance, edge cost coste, admissible heuristic h output: solution, NO_SOLUTION, or FAILURE notation: f(N) :=N.g +h(N); ♠ := (N goal ̸= ⊥) 1: initialize Open, Explored; N goal ←⊥ 2: N init ←〈config : S, tree : �C init �, parent : ⊥, neigh : ∅, g : 0〉 3: Open.push (N init ); Explored[S] =N init 4: while Open ̸= ∅ ∧ ¬interrupt() do 5: N ←Open.top() 6: if N .config = G then N goal ← N 7: if ♠ ∧ f (N goal ) ≤ f (N) then Open.pop(); continue 8: if N.tree = ∅ then Open.pop(); continue 9: C ←N.tree.pop() 10: low_level_expansion(N , C) 11: Qnew ← configuration_generator(N, C) 12: if Qnew = ⊥ then continue 13: if Explored [Qnew ] ̸= ⊥ then 14: N.neigh.append (Explored [Qnew ]) 15: D← � N � ▷ Dijkstra, priority queue of g-value 16: while D ̸= ∅ do 17: N from ← D.pop() 18: for N to ∈ N from .neigh do 19: g ← N from .g + coste (N from , N to ) 20: if g < N to .g then 21: N to .g ← g; N to .parent ← N from ; D.push(N to ) 22: if ♠∧ f (N to ) < f (N goal ) then Open.push (N to ) 23: else 24: N new ←〈config : Qnew , tree : �C init �, parent : N, neigh : ∅, g : N.g + coste (N,Qnew ) 〉 25: Open.push (N new ); Explored [Qnew ] =N new 26: N.neigh.append (N new ) 27: if ♠∧Open = ∅ then return backtrack (N goal ) ▷ optimal 28: else if ♠ then return backtrack (N goal ) ▷ sub-optimal 29: else if Open = ∅ then return NO_SOLUTION 30: else return FAILURE

Discarding Redundant Nodes. Once the goal node is found, LaCAM∗ discards nodes that do not contribute to improving solution quality (Line 7). It also revives nodes as necessary when their g-values are updated (Line 22).

Theorem 1. LaCAM∗ (Alg. 3) is complete and optimal.

Proof. Consider Alg. 3 without blue lines (Lines 7 and 22); they just speed up the search without breaking the optimal search structure. In this proof, the term "path" refers to a sequence of connected configurations.

First, we introduce a directed graph H, where its vertex corresponds to a configuration. Initially, H has only a start vertex S. Then, the search iterations gradually develop H. When a new node is created (Line 24), its configuration is added to H. An arc (X, Y ) of H occurs when the search finds a connection fromX to Y , i.e., N Y ∈ N X .neigh.

We now prove that: (♣) for any configuration Q in H, a path from S to Q constructed by backtracking (i.e., by following N.parent) is the shortest path in H, regarding accumulative transition costs, at the beginning of each search iteration. This is proven by induction. Initially, H comprises only S, satisfying ♣. Assume now that ♣ is satisfied in the previous iteration of Lines 4-26. In the next iteration, H is updated by: (i) generating a new configuration (Lines 24-26), or (ii) finding a known configuration (Lines 14-21). Case (i) holds ♣ because only a new vertex and an arc toward the vertex are added to H. Case (ii) holds ♣ because only an arc is added for the node N (Line 14), and then Lines 15-21 perform Dijkstra's algorithm starting from N that maintains the tree structure of the shortest paths.

The search space of LaCAM∗ is finite (see [Okumura, 2023]); the search terminates in finite time. Each node eventually examines all connected configurations. Consequently, when terminated, H includes all possible paths from S to G for solvable instances. Together with ♣, LaCAM∗ returns an optimal solution, otherwise, reports the non-existence.

Implementation Tips. Following [Okumura, 2023], when finding an already known configuration at Line 13, our implementation reinserts the corresponding node to Open. Moreover, with a small probability (e.g., 0.1%), the implementation reinserts a node of S instead of the found one. Doing so enables the search to "escape" from configurations being bottlenecks. Such techniques relying on non-determinism have been seen in other search problems [Kautz et al., 2002] and MAPF studies [Cohen et al., 2018b; Andreychuk and Yakovlev, 2018]. Indeed, we informally observed that this random replacement slightly improved the success rate. Note that the optimality still holds with these modifications.

4 Improving Configuration Generator

The performance of LaCAM heavily relies on a configuration generator, therefore, the development of good generators is critical. The implementation in [Okumura, 2023] uses a vanilla PIBT of Alg. 2, resulting in poor performances in several scenarios, especially in instances with narrow corridors. This is because PIBT itself often fails such scenarios, hence being an ineffective guide for LaCAM. This section elaborates on this phenomenon and presents an improved version.

4.1 Failure Analysis of PIBT

As seen in Sec. 2.3, PIBT sequentially assigns the next locations for agents. Since this order prioritizes agents being not on their goals, livelock situations might be triggered. See Fig. 5; two agents reach their goal vertex periodically but PIBT never reaches the goal configuration.

Algorithm 4 procedure PIBT with swap

LaCAM can break such livelocks by posing constraints. However, it may require significant effort because appropriate combinations of constraints should be explored. Even worse, with more agents, the search effort dramatically increases, as demonstrated in Table 1.

4.2 Enhancing PIBT by Swap

Livelocks in PIBT can be resolved by swap operation, originally developed in rule-based MAPF algorithms [Luna and Bekris, 2011; De Wilde et al., 2014]. In short, this operation swaps locations of two agents using a vertex with a degree of three or more. Figure 6 shows an example. Here, we extract its essence and incorporate it into PIBT. Specifically, this is done by adjusting vertex scoring at Line 5 in Alg. 2.

Algorithm 4 extends the PIBT procedure of Alg. 2. The modification is simple; if an agent i and neighboring agent j are judged to require swapping locations (Line 3), i reverses the order of candidate vertices C (Line 4); that is, i tries to be apart from gi. Then, if i successfully moves to the first vertex in the candidates C, i pulls j to the current occupying vertex (Line 7). With an appropriate implementation of the function swap_required_and_possible, PIBT does not fall into the livelock of Fig. 5, rather, it can generate a sequence of configurations shown in Fig. 6.

The swap_required_and_possible function is a pattern detector and implementation-depending. We do not aim at designing complete detectors because pitfalls of the detectors can be complemented by LaCAM. However, a well-tuned implementation can relax the search effort of LaCAM. Below, we illustrate our example implementation, while omitting tiny fine-tunings.

Pattern Detector Implementation

Assume that the detector is called for i. Assume further that another agent j is on C[1] for i at Line 2 of Alg. 4, such that the degree is 2 or less. Our detector uses two emulations.

The first emulation asks about the necessity of the swap. This is done by continuously moving i to j's location while moving j to another vertex not equal to i's location, ignoring the other agents. The emulation stops in two cases: (i) The swap is not required when j's location has a degree of more than two. (ii) The swap is required when j's location has a degree of one, or, when i reaches gi while j's nearest neighboring vertex toward its goal is gi.

If the swap is required, the second emulation asks about the possibility of the swap. This is done by reversing the emulation direction; that is, continuously moving j to i's location while moving i to another vertex. It stops in two cases: (i) The swap is possible when i's location has a degree of more than two. (ii) The swap is impossible when i is on a vertex with degree of one.

The function returns j when the swap is required and possible. For instance, in configurations of Fig. 6(a,b), the swap is required for both agents. However, the swap is possible only for agent-1, then, the order of candidate vertices is reversed for agent-1 (Line 4). Consequently, Alg. 4 generates configurations of Fig. 6(b,c). An exception is the case of Fig. 6c, where agent-2 needs to reverse its candidates to generate a configuration of Fig. 6d. We note that this case is also possible to be detected by applying the two emulations.

5 Evaluation

This section empirically assesses the two improvements, comprising: (i) how the improved configuration generator reduces planning effort, (ii) how LaCAM∗ refines solution, (iii) how discarding redundant nodes speeds up the convergence, (iv) evaluation with small complicated instances, (v) evaluation with the MAPF benchmark, (vi) comparison with another anytime MAPF algorithm, and (vii) evaluation with extremely dense scenarios.

Setup. The experiments were run on a desktop PC with Intel Core i7-7820X 3.6GHz CPU and 32GB RAM. A maximum of 16 different instances were run in parallel using multi-threading. LaCAM∗ was coded in C++. All experiments used four-connected grid maps retrieved from the MAPF benchmark [Stern et al., 2019]. Unless mentioned, this section uses a timeout of 30 s for solving MAPF. Baseline MAPF algorithms are summarized in Fig. 1. Their implementation details are available in the appendix.

Effect of Improved Configuration Generator. Table 1 presents the number of search iterations of LaCAM on an instance that requires "swap," using a vanilla PIBT (Alg. 2) and the improved one (Alg. 4) as a configuration generator. Table 2 further compares the generators with larger instances. The results show that Alg. 4 dramatically reduced the search iterations of LaCAM, contributing to smaller computation time in large instances. Note however that the pattern detector has runtime overhead, as seen in |A| = 100 of Table 2.

Refinement of LaCAM∗ . Figure 7 shows how LaCAM∗ refines solutions. As baselines, we used scores of a complete and optimal algorithm called (I-)ODrM∗ [Wagner and Choset, 2015]. In the small instances, LaCAM∗ quickly found initial solutions and converged to optimal ones. Meanwhile, the convergence speed was slow in large instances with many agents. This is due to finding new connections between known configurations becoming rare, hence reducing the chance of rewriting the search tree.

Effect of Discarding Redundant Nodes. Table 3 shows how discarding redundant search nodes (blue lines of Alg. 3) affects the search to identify optimal solutions. Regardless of the generators, the discarding dramatically reduced the search effort. The reduction was larger with Alg. 4 because initial solutions can be found with smaller search iterations than Alg. 2. Note that without the discarding, the numbers of search iterations are equivalent between Alg. 2 and Alg. 4 because the search spaces are identical. In the remaining, LaCAM∗ uses Alg. 4 while LaCAM denotes the original implementation that uses Alg. 2.

Small Complicated Instances. Table 4 shows the results of LaCAM∗ with instances retrieved from [Luna and Bekris, 2011]. Overall, it immediately found not only initial solutions but also (near-)optimal ones. In contrast, the baselines failed some instances or returned low-quality solutions.

MAPF Benchmark. We tested LaCAM∗ on the MAPF benchmark that includes 33 maps, each having 25 "random scenarios" which specify start-goal pairs. From each scenario, we extracted instances by increasing the number of agents by 50 up to the maximum (1,000 in most cases) and obtained 13,900 instances in total. The percentage of solved instances is summarized in Fig. 1. Figure 8 presents partial results for each map. LaCAM∗ only failed in the instances of maze-128-128-1 and sub-optimally solved all the other instances within 10 s, outperforming the other algorithms. The failures might be reduced by improving the pattern detector; however, we consider such implementations are too optimized for the benchmark. As shown in Fig. 9, the refinement was steady but not dramatic due to the same reason of Fig. 7. Further discussions are available in the appendix.

Comparison with Anytime MAPF Solver. We compared LaCAM∗ with AFS [Cohen et al., 2018a], a CBS-based anytime MAPF solver that guarantees to converge optima. Table 5 summarizes the results. Contrary to LaCAM∗ , AFS can obtain plausible solutions from the beginning, however, it compromises scalability. We consider this quality gap can be overcome by developing better generators other than PIBT.

Extremely Dense Scenarios. Table 6 reports LaCAM∗ in very congested scenarios that existing solvers mostly fail. Even with such challenging cases, LaCAM∗ solved many instances, demonstrating its excellent scalability.

6 Conclusion and Discussion

The primary challenge of MAPF is to maintain solvability and solution quality while suppressing planning efforts. To break this tradeoff, this paper presented two enhancements to LaCAM, namely, LaCAM∗ which eventually converges to optima and an effective configuration generator. The enhancements were thoroughly assessed, achieving remarkable results. From the empirical evidence, we believe that LaCAM∗ has developed a new frontier in MAPF.

Related Work. LaCAM(∗) relates to partial successor expansion during the search, as seen in [Goldenberg et al., 2014; Wagner and Choset, 2015], because it also generates a subset of successors, but differs in the use of constraints and a configuration generator. Anytime MAPF algorithms that converge to optima have been studied [Standley and Korf, 2011; Cohen et al., 2018a; Vedder and Biswas, 2021]. However, their scalability is limited; they often fail to derive initial solutions, as we empirically saw. Techniques to refine arbitrary MAPF solutions have also been studied [Surynek, 2013; De Wilde et al., 2014; Okumura et al., 2021; Li et al., 2021a] but they do not ensure optimality. Rewriting the search tree structure is popular in optimal motion planning [Karaman and Frazzoli, 2011; Shome et al., 2020], by which LaCAM∗ is partially inspired. Incorporating swap into PIBT is inspired by sub-optimal rule-based MAPF algorithms [Luna and Bekris, 2011; De Wilde et al., 2014]. Meanwhile, the solution quality of rule-based approaches themselves is often severely compromised.

FutureDirections. We are interested inmore effective configuration generators than PIBT variants which can output near-optimal initial solutions. Improving the convergence speed of LaCAM∗ is also important. Moreover, LaCAM∗ in MAPF variants, e.g., multi-robot motion planning [Okumura and Défago, 2023], is worth to be studied. Other than MAPF, since LaCAM∗ is just a graph pathfinding algorithm, applying its concept to other planning domains might be exciting.

Acknowledgments

I am grateful to Yasumasa Tarmura for his comments on the initial manuscript. This work was partly supported by JSPS KAKENHI Grant Numbers 20J23011 and JST ACT-X Grant Table 6: Results on extremely dense scenarios. |A| was adjusted so that |A|/|V | = 0.9. For each scenario, 25 instances were prepared while randomly placing starts and goals. "%" is the success percentage by LaCAM∗ with timeout of 60 s. "time" is the median runtime to obtain initial solutions. We also tested the other solvers in Fig. 1 and report solvers that solved in at least one instance.

Number JPMJAX22A1. I thank the support of the Yoshida Scholarship Foundation when I was a Ph.D. student.