Shao-Hung Chan, Thomy Phan, Jiaoyang Li, Sven Koenig

New Mechanisms in Flex Distribution for Bounded Suboptimal Multi-Agent Path Finding

Introduction

New mechanisms in flex distribution for bounded suboptimal multi-agent path finding. New flex distribution mechanisms for EECBS improve bounded-suboptimal Multi-Agent Path Finding (MAPF). Enhances efficiency, outperforms prior greedy methods, and includes redesigned Focal-A*.

Abstract

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths, one for each agent in a shared environment. Its objective is to minimize the sum of path costs (SOC), where the path cost of each agent is defined as the travel time from its start location to its target location. Explicit Estimation Conflict-Based Search (EECBS) is the leading algorithm for bounded-suboptimal MAPF, with the SOC of the solution being at most a user-specified factor w away from optimal. EECBS maintains sets of paths and a lower bound LB on the optimal SOC. Then, it iteratively selects a set of paths whose SOC is at most w times LB and introduces constraints to resolve collisions. For each path in a set, EECBS maintains a lower bound on its optimal path that satisfies constraints. By finding a path with cost at most its threshold, defined as w times its lower bound, EECBS guarantees to find a bounded-suboptimal solution. To speed up EECBS, previous work uses flex distribution to relax the requirement that each path needs to be at most its threshold. Though EECBS with flex distribution guarantees to find a bounded-suboptimal solution, increasing the thresholds may increase the SOC beyond w times LB, forcing EECBS to switch among different sets of paths (whose SOC are still at most w times LB), and thus reducing efficiency. To address this issue, we propose Conflict-Based Flex Distribution that distributes flex in proportion to the number of collisions. We also estimate the extra travel time (i.e., delays) needed to satisfy constraints and propose Delay-Based Flex Distribution. On top of that, we propose Mixed-Strategy Flex Distribution, combining both in a hierarchical framework. We prove that EECBS with our new flex distribution mechanisms is complete and bounded-suboptimal. The experiments show that our approaches outperform the original (greedy) flex distribution. Also, we redesign Focal-A* search from the previous work to improve LB for a congested environment.

Review

This paper presents a significant advancement in the efficiency of Explicit Estimation Conflict-Based Search (EECBS), a leading algorithm for bounded-suboptimal Multi-Agent Path Finding (MAPF). The core problem addressed is finding collision-free paths for multiple agents to minimize the sum of path costs (SOC) within a user-specified suboptimality factor `w`. The authors correctly identify a key efficiency bottleneck in the current EECBS framework: the existing "flex distribution" mechanisms, while guaranteeing bounded-suboptimality, can lead to frequent switching between sets of paths and reduced efficiency when thresholds are increased. This sets a clear and relevant context for the proposed research, aiming to enhance an already state-of-the-art algorithm. To address the identified limitations, the paper introduces three novel flex distribution mechanisms: Conflict-Based Flex Distribution, Delay-Based Flex Distribution, and a combined Mixed-Strategy Flex Distribution. Conflict-Based Flex Distribution intelligently distributes "flex" (slack in path cost thresholds) in proportion to the number of collisions, while Delay-Based Flex Distribution estimates the additional travel time required to resolve conflicts. The Mixed-Strategy approach further refines this by integrating both in a hierarchical manner. Crucially, the authors provide theoretical proofs that EECBS, when augmented with these new mechanisms, remains complete and bounded-suboptimal, thus maintaining the critical guarantees of the original algorithm while striving for improved performance. The experimental results demonstrate that these proposed approaches empirically outperform the original (greedy) flex distribution, validating their practical utility and efficiency gains. This robust experimental backing, coupled with the theoretical proofs, strengthens the paper's contributions considerably. Furthermore, the paper notes an additional improvement through the redesign of Focal-A* search, aimed at enhancing lower bound (LB) estimation in congested environments, which synergistically contributes to overall algorithm performance. This work offers a valuable contribution to the MAPF community by providing a more efficient and intelligent way to manage suboptimality guarantees within complex multi-agent systems, paving the way for more scalable and practical applications.

Full Text

Comments

You need to be logged in to post a comment.