Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds Yimin Tang, Zhenghong Yu, Jiaoyang Li, Sven Koenig Abstract Multi-Agent Path Finding (MAPF) involves finding collision-free paths for multiple agents while minimizing a cost function—an NP-hard problem. Bounded suboptimal methods like Enhanced Conflict-Based Search (ECBS) and Explicit Estimation CBS (EECBS) balance solution quality with computational efficiency using focal search mechanisms. While effective, traditional focal search faces a limitation: the lower bound (LB) value determining which nodes enter the FOCAL list often increases slowly in early search stages, resulting in a constrained search space that delays finding valid solutions. In this paper, we propose a novel bounded suboptimal algorithm, double-ECBS (DECBS), to address this issue by first determining the maximum LB value and then employing a best-first search guided by this LB to find a collision-free path. Experimental results demonstrate that DECBS outperforms ECBS in most test cases and is compatible with existing optimization techniques. DECBS can reduce nearly 30% high-level CT nodes and 50% low-level focal search nodes. When agent density is moderate to high, DECBS achieves a 23.5% average runtime improvement over ECBS with identical suboptimality bounds and optimizations. I INTRODUCTION Automated warehouses represent a multi-billion-dollar industry dominated by companies. These facilities employ hundreds of robots to transport goods between locations [ 1 ] . A key aspect of their operation is designing collision-free plans for these robots, a challenge that can be formulated as a Multi-Agent Path Finding (MAPF) problem [ 2 ] . MAPF focuses on finding collision-free paths for multiple agents moving from their start locations to designated goal locations in a known environment while optimizing a specified cost function. Many optimal algorithms have been proposed to solve this problem, including M^{*} [ 3 ] , Conflict-Based Search (CBS) [ 4 ] , ICBS [ 5 ] , and CBSH2-RTC [ 6 ] . Solving the MAPF problem optimally is known to be NP-hard [ 7 ] , creating significant challenges for optimal solvers regarding scalability and efficiency. In contrast, suboptimal MAPF solvers—including Prioritized Planning (PP) [ 8 , 9 ] , PBS [ 10 ] , and their variants [ 11 , 12 ] —offer improved computational performance but lack the theoretical guarantees on solution quality. Bounded-suboptimal approaches like Enhanced CBS (ECBS) [ 13 ] and EECBS [ 14 ] provide a trade-off between efficiency and solution quality, guaranteeing collision-free solutions’ costs are within a user-defined suboptimality factor of the optimal cost. The key idea behind bounded-suboptimal MAPF solvers lies in relaxing the best-first search requirement while incorporating additional heuristic functions to select the next node for expansion effectively. ECBS [ 13 ] achieves bounded suboptimality by replacing CBS’s best-first search strategy at both the high and low levels of CBS with focal search [ 15 , 16 ] . Focal search operates through two queues: an OPEN list containing all unexpanded nodes sorted by cost, a FOCAL list containing a subset of these nodes. The algorithm selects expansion candidates from the FOCAL list using an auxiliary heuristic to accelerate finding bounded-suboptimal solutions. In our implementation, we use collision minimization as the FOCAL heuristic function at both search levels, explicitly employing the negative count of collisions in paths or complete solutions. During focal search, since the optimal cost is unknown until an optimal solution is found, focal search uses the lowest cost in the OPEN list as a lower bound (LB) value to estimate the optimal cost and define FOCAL list eligibility. However, when the LB value is small, the FOCAL list contains fewer nodes, causing focal search to behave similarly to standard best-first search. This constraint also leads to unbalanced search tree expansion [ 14 ] . In this paper, we introduce double-ECBS (DECBS), a novel bounded-suboptimal variant of ECBS. DECBS modifies the original focal search used in low-level path planning by incorporating an optimized search manner, what we call double search . This approach is inspired by ITA-ECBS [ 17 ] , a bounded-suboptimal version of ITA-CBS [ 18 ] . However, ITA-ECBS primarily focuses on integrating ECBS and ITA-CBS, and it has not been developed as a universal optimization applicable to other methods. The double search operates in two phases: first, a shortest path search determines the optimal cost, the upper bound for the LB value; second, DECBS employs a best-first search guided by the FOCAL list auxiliary heuristic function using this LB value to find a path with fewer collisions. Importantly, paths returned during the low-level search are not necessarily collision-free—they need only to satisfy the constraints specified in the corresponding high-level CT node. This maximum LB value offers three benefits: (1) by accurately reflecting the optimal cost, it enables more nodes to enter the FOCAL list. This increases the likelihood of selecting a path with fewer collisions, thereby reducing both high-level node expansion and low-level node expansion; (2) The node of focal search is more expensive than A^{*} because it requires computing an additional heuristic. In double search, we first perform an A^{*} search to obtain a larger LB. This larger LB, in turn, reduces the number of nodes generated by the focal search. Although the A^{*} search introduces additional nodes, these nodes are cheaper to compute than the focal search nodes. (3) Candidate nodes with costs exceeding the suboptimality can be pruned, saving memory during search operations. In summary, although DECBS performs two path searches for each low-level search, the double search is faster than executing a single focal search. Our empirical evaluation confirms these benefits, showing that DECBS reduces nearly 30% high-level CT nodes and 50% low-level focal search nodes, and achieves a 23.5% average runtime improvement over ECBS with identical optimizations when agent density is moderate to high. II Problem Definition The Multi-Agent Path Finding (MAPF) problem is defined as follows: Given a set of agents I=\{1,2,\cdots,N\} and an undirected graph G=(V,E) , where vertices v\in V represent possible agent locations and edges e\in E represent unit-cost movements between two locations. Self-loop edges are allowed which represent “wait-in-place” actions. Each agent i\in I has a unique start location s_{i}\in V and a unique goal location g_{i}\in V , such that s_{i}\neq s_{j} and g_{i}\neq g_{j} for all i\neq j . The task is to find collision-free paths for all agents i\in I from their start locations s_{i} to their goal locations g_{i} . All agent actions–including waiting in place and moving to an adjacent vertex–take one time unit. Let v^{i}_{t}\in V be the location of agent i at timestep t , and \pi_{i}=[v_{0}^{i},v_{1}^{i},...,v_{T^{i}}^{i}] denote a path of agent i from its start location v_{0}^{i} to its target v_{T^{i}}^{i} . We assume that agents rest at their targets after completion, i.e., v_{t}^{i}=v_{T^{i}}^{i},\forall t>T^{i} . The cost of agent i ’s path is defined as T^{i} , with the minimum cost path referred to as the shortest path. We consider two types of agent-agent collisions: vertex collisions , where two agents occupy the same vertex simultaneously. and edge collision , where two agents move in opposite directions along the same edge. We denote both collision types as (i,j,t) , a vertex collision between agents i and j at timestep t or an edge collision between agents i and j at timestep t to t+1 . The collision-free requirement implicitly requires that all agent goals must be distinct. Formally, the objective of the MAPF problem is to find a set of paths \{\pi_{i}|i\in I\} for all agents that satisfies the following conditions: 1. Each agent i begins at its start location (i.e., v_{0}^{i}=s_{i} ) and reaches its target location g_{j} (i.e., v_{t}^{i}=g_{j},\forall t\geq T^{i} ); 2. Every pair of adjacent vertices on path \pi_{i} is connected by an edge (i.e., (v_{t}^{i},v_{t+1}^{i})\in E,\forall 0\leq t\leq T^{i} ); 3. The complete solution is collision-free while minimizing the total flowtime \sum_{i=1}^{N}T^{i} . III Related work III-A Focal Search Focal search is a bounded-suboptimal search algorithm that balances efficiency and solution quality [ 15 , 16 ] . Given a user-defined suboptimality factor w\geq 1 , the algorithm guarantees a solution \pi with cost c^{val} satisfying c^{val}\leq w\cdot c^{opt} , with c^{opt} representing the optimal solution cost. To achieve this, focal search maintains two queues: OPEN and FOCAL. 1 1 1 Since OPEN and FOCAL are used for sorting and FOCAL is a subset of OPEN, candidate node pointers are typically stored in both. If a node appears in both queues, only one instance is maintained, with two pointers referencing it. The OPEN list stores all candidate nodes awaiting expansion, sorted by the function f(n)=g(n)+h(n) , where g(n) is the cost-so-far and h(n) is an admissible heuristic estimate of cost-to-go, similar to A^{*} search. The FOCAL queue contains only those nodes n from OPEN satisfying f(n)\leq w\cdot f_{front} , where f_{front} is the minimum f value in OPEN. Nodes in FOCAL are sorted according to an additional heuristic function d(n) that guides the search toward promising regions of the search space. Focal search always expands the front node in the FOCAL list. When a solution with cost c^{val} is found, the algorithm sets the lower bound (LB) c^{g}=f_{front} . We can observe that f_{front}\leq c^{opt} and f_{front}\leq c^{val}\leq wf_{front}\leq wc^{opt} . Finally, focal search returns two outputs: the LB c^{g} and the solution with cost c^{val} . If no solution exists, both c^{g} and c^{val} are set to \infty . III-B Multi-Agent Path Finding (MAPF) Multi-Agent Path Finding (MAPF) has a long history [ 9 ] . Many algorithms have been developed to solve it or its variants. Decoupled algorithms [ 9 , 19 , 20 ] plan paths for each agent independently and combine these paths into a single solution. Coupled algorithms [ 21 , 22 ] plan simultaneously for all agents. There also exist dynamically-coupled algorithms [ 4 , 23 ] initially generate individual paths and re-plan for multiple agents together when resolving collisions. Among these approaches, Conflict-Based Search (CBS) [ 4 ] is a basic centralized optimal MAPF algorithm. Some bounded-suboptimal algorithms, such as ECBS [ 13 ] and EECBS [ 14 ] , are based on it. CBS Conflict-Based Search (CBS) is an optimal two-level search algorithm. The low-level computes shortest paths for individual agents from their start locations to goals, while the high-level searches a binary Constraint Tree (CT). Each CT node H=(c,\Omega,\pi) includes a constraint set \Omega , a solution \pi containing shortest paths satisfying \Omega for all agents, and the solution cost c . When a solution \pi or a path does not include any agent actions or positions that are restricted by a \Omega , we say this solution or path satisfies the \Omega . Importantly, a solution \pi satisfying \Omega may still contain collisions; we consider \pi a valid solution pnly when it is collision-free. When expanding a node H , CBS selects a collision in H.\pi and formulates two constraints, each prohibiting one agent from either occupying the colliding location or performing the conflicting action at the colliding timestep. We have two types of constraints: vertex constraint (i,v,t) that prohibits agent i from occupying vertex v at timestep t and edge constraint (i,u,v,t) that prohibits agent i from moving from vertex u to vertex v at timestep t . CBS then generates two successor nodes identical to H , adding one of the new constraints to each successor node’s constraint set. After adding a new constraint, the affected agent’s apth must be re-planned to satisfy the updated constraint set. By maintaining a priority queue OPEN ordered by solution cost, CBS repeats this process until expanding a collision-free node, which represents the optimal valid solution. CBS guarantees optimality for flowtime minimization [ 4 ] . BCBS and ECBS BCBS [ 13 ] and ECBS [ 13 ] build upon CBS by incorporating focal search. In ECBS low-level search, focal search returns both an LB value c^{g}_{i} and a valid path \pi_{i} , with cost c_{i} for agent i , satisfying: c^{g}_{i}\leq c_{i}^{opt}\leq c_{i}\leq w\cdot c^{g}_{i} , where c_{i}^{opt} represents the optimal path cost of agent i under constraints \Omega . At the high-level search, ECBS extends the CT node structure to H=(c,\Omega,\pi,L,c_{L}) , adding an array L , that stores all LB values c^{g}_{i} for paths in \pi , and cost c_{L} represents the sum of these lower bounds. ECBS’s high-level search maintains two priority queues: FOCAL and OPEN. OPEN sorts all CT nodes by ascending c_{L} , while FOCAL contains nodes H from OPEN satisfying H.c\leq w\cdot H_{front}.c_{L} , where H_{front} is the front CT node in OPEN. FOCAL is ordered by a user-defined heuristic function d(H) . ECBS guarantees that the returned solution H^{sol}.\pi satisfies H^{sol}.c\leq w\cdot c^{opt} , with c^{opt} being the optimal valid solution cost. BCBS similarly employs focal search at both levels but defines the high-level CT node LB value as the sum of the low-level path costs. BCBS is typically denoted as BCBS (w_{1},w_{2}) , where w_{1} and w_{2} are the suboptimality factors for high- and low-level search. When w_{1}w_{2}=w , BCBS (w_{1},w_{2}) returns a solution that is bounded-suboptimal with factor w . Notably, BCBS (w,1) is equivalent to using A^{*} in low-level and focal search in high-level. Fig. 1 : A ideal case to explain how double search is faster than focal search: Let’s assume L_{i} are different low-level path candidate nodes, and L_{0}.c=L_{1}.c=L_{2}.c=10 , L_{4}.c=L_{5}.c=11 , L_{3}.c=12 and c^{opt}=11 . We also assume w=1.1 , L_{3} is the goal candidate node and the others are not. We have d(L_{0})