Search papers, labs, and topics across Lattice.
This paper introduces Adaptive-Horizon Conflict-Based Search (ACCBS), a closed-loop multi-agent path finding algorithm that addresses the limitations of open-loop planners and closed-loop heuristics in MAPF. ACCBS employs a finite-horizon CBS variant with a horizon-changing mechanism inspired by iterative deepening MPC, dynamically adjusting the planning horizon based on computational budget. The algorithm reuses a single constraint tree to enable seamless transitions between horizons, achieving anytime behavior and asymptotic optimality.
Bridging the gap between theoretical optimality and practical robustness, ACCBS offers a closed-loop MAPF solution that dynamically adapts its planning horizon for efficient and reliable robot coordination.
MAPF is a core coordination problem for large robot fleets in automated warehouses and logistics. Existing approaches are typically either open-loop planners, which generate fixed trajectories and struggle to handle disturbances, or closed-loop heuristics without reliable performance guarantees, limiting their use in safety-critical deployments. This paper presents ACCBS, a closed-loop algorithm built on a finite-horizon variant of CBS with a horizon-changing mechanism inspired by iterative deepening in MPC. ACCBS dynamically adjusts the planning horizon based on the available computational budget, and reuses a single constraint tree to enable seamless transitions between horizons. As a result, it produces high-quality feasible solutions quickly while being asymptotically optimal as the budget increases, exhibiting anytime behavior. Extensive case studies demonstrate that ACCBS combines flexibility to disturbances with strong performance guarantees, effectively bridging the gap between theoretical optimality and practical robustness for large-scale robot deployment.
