Edward Lam, Peter J. Stuckey

Low-Level Search on Time Intervals in Branch-and-Cut-and-Price for Multi-Agent Path Finding

Introduction

Low-level search on time intervals in branch-and-cut-and-price for multi-agent path finding. New BCP2-MAPF: optimal multi-agent path finding. Branch-and-cut-and-price with novel time interval low-level path finder. Outperforms state-of-the-art algorithms.

Abstract

Multi-agent path finding is the problem of navigating a set of agents from their starting locations to their target locations while avoiding collisions. A leading method for optimal multi-agent path finding is branch-and-cut-and-price, a framework based on mathematical optimization. The reference implementation, named BCP-MAPF, shows highly competitive results against AI-based search. This paper presents BCP2-MAPF, a new implementation of branch-and-cut-and-price paired with a novel low-level path finder based on time intervals. Experimental results demonstrate that BCP2-MAPF significantly outperforms the other state-of-the-art optimal algorithms BCP-MAPF, Lazy CBS and CBSH2-RTC.

Review

This paper addresses the challenging problem of Multi-Agent Path Finding (MAPF), a crucial area in robotics and AI where multiple agents must navigate a shared environment without collisions. The authors situate their work within the context of optimal MAPF solutions, specifically building upon the successful branch-and-cut-and-price (BCP) framework, exemplified by the competitive BCP-MAPF implementation. This problem is of significant practical interest, given its applications in warehouse automation, air traffic control, and autonomous driving. The core contribution of this work is BCP2-MAPF, a novel implementation of branch-and-cut-and-price that integrates a new low-level pathfinder utilizing time intervals. This particular approach aims to enhance the efficiency and scalability of optimal MAPF solutions by refining how individual agent paths are generated and coordinated within the broader BCP framework. The novelty lies in the specific design of this time-interval-based low-level search, which is a critical component influencing the overall performance of such decomposition methods. The experimental results presented claim a significant performance improvement, with BCP2-MAPF outperforming leading state-of-the-art optimal algorithms including BCP-MAPF, Lazy CBS, and CBSH2-RTC. This assertion, if thoroughly validated, marks a substantial advancement in the field of optimal MAPF, offering a more efficient method for solving complex instances. The successful integration of a specialized low-level pathfinder within a sophisticated mathematical optimization framework like BCP suggests a promising direction for future research in combinatorial optimization problems.

Full Text

Comments

You need to be logged in to post a comment.