Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds

Yimin Tang, Zhenghong Yu, Jiaoyang Li, Sven Koenig · 2025

Read Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds by Yimin Tang, Zhenghong Yu, Jiaoyang Li, Sven Koenig (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-03779.txt.

Introduction

Coordinating many robots or agents without collisions is a hard search problem, and bounded methods trade a little quality for speed. Yimin Tang and co-authors improve in 2025 the focal search at the heart of a leading method. The snag they target: the lower bound that admits nodes into the search list climbs slowly early on, starving the search.

Their double method first pins down the highest useful lower bound, then runs a best-first search guided by it. Across tests it beat the standard method in most cases, cutting high-level search nodes by nearly thirty percent and low-level ones by half. Runtime fell by about a quarter at busier agent densities.

Catalog record

CREATORYimin Tang, Zhenghong Yu, Jiaoyang Li, Sven Koenig
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-03779

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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

Read the complete text