Shuai Zhou, Shizhe Zhao, Zhongqiang Ren

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions (Extended Abstract)

Introduction

Lsrp*: scalable and anytime planning for multi-agent path finding with asynchronous actions (extended abstract). Discover LSRP*, a scalable and anytime planner for Multi-Agent Path Finding (MAPF) with asynchronous actions. It improves solution quality, handles more agents, and reduces path costs for complex systems.

Abstract

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-Based Planning (LSRP) is proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSPR* and test it against several baselines with up to 1000 agents in various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.

Review

This extended abstract introduces LSRP*, a novel approach to Multi-Agent Path Finding (MAPF) that specifically addresses the restrictive assumption of synchronized actions prevalent in much of the existing literature. While conventional MAPF algorithms typically assume all agents act simultaneously and with uniform duration, the authors correctly identify this as a significant barrier to real-world applicability. Building upon Loosely Synchronized Rule-Based Planning (LSRP), which previously offered a way to handle asynchronous actions but with often-poor solution quality, this work presents a timely and relevant advancement for making MAPF more practical. The core contribution of this paper is LSRP*, an anytime planner designed to iteratively improve solution quality after an initial solution is found, continuing until a predefined computational budget is exhausted. This "anytime" characteristic is crucial for practical deployment, allowing planners to adapt to varying time constraints while still striving for better outcomes. The abstract highlights that LSRP* aims to rectify the unbounded sub-optimality issues of its predecessor, LSRP, through its continuous refinement process. The authors indicate they have analyzed its properties and conducted empirical evaluations against several baselines. The preliminary results presented are promising, suggesting LSRP* offers substantial improvements over LSRP. Specifically, it is reported to handle up to 25% more agents and achieve up to a 40% reduction in solution cost compared to LSRP, demonstrating significant gains in both scalability and solution quality. Tested with up to 1000 agents across various map configurations, LSRP* appears to be a robust and efficient solution for large-scale, asynchronous MAPF problems. Given this is an extended abstract, a full paper detailing the algorithmic specifics, property analyses, and comprehensive experimental results would be highly anticipated to further validate these impressive claims and explore the broader implications for the field.

Full Text

Comments

You need to be logged in to post a comment.