A General Framework for Dynamic MAPF using Multi-Shot ASP and Tunnels

AYSU BOGATARKAN, ESRA ERDEM · 2025

Read A General Framework for Dynamic MAPF using Multi-Shot ASP and Tunnels by AYSU BOGATARKAN, ESRA ERDEM (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-2507-20703.txt.

Introduction

Aysu Bogatarkan and Esra Erdem give a broad frame for dynamic multi agent path finding, where robots must reach goals with no crashes as the world shifts. Agents can join or leave, and blocks can move or vanish mid plan, as in warehouses with people near.

Their frame states the dynamic task in a form that fits many variants. It solves it in shots and lets unlike solvers plug in. A logic based method blends replan and repair with tunnels that bound where agents may roam. Tests weigh speed against plan quality for the new method.

Catalog record

CREATORAYSU BOGATARKAN, ESRA ERDEM
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20703

Browse the full library · About the Tower of Babel

Full text

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

A General Framework for Dynamic MAPF using Multi-Shot ASP and Tunnels AYSU BOGATARKAN, ESRA ERDEM Abstract MAPF problem aims to find plans for multiple agents in an environment within a given time, such that the agents do not collide with each other or obstacles. Motivated by the execution and monitoring of these plans, we study Dynamic MAPF (D-MAPF) problem, which allows changes such as agents entering/leaving the environment or obstacles being removed/moved. Considering the requirements of real-world applications in warehouses with the presence of humans, we introduce 1) a general definition for D-MAPF (applicable to variations of D-MAPF), 2) a new framework to solve D-MAPF (utilizing multi-shot computation, and allowing different methods to solve D-MAPF), and 3) a new ASP-based method to solve D-MAPF (combining advantages of replanning and repairing methods, with a novel concept of tunnels to specify where agents can move). We have illustrated the strengths and weaknesses of this method by experimental evaluations, from the perspectives of computational performance and quality of solutions. keywords multi-agent path finding, answer set programming, multi-shot computation 1 Introduction The multi-agent path finding (MAPF) problem aims to find plans for multiple agents in a shared environment such that the agents do not collide with each other or obstacles, subject to constraints on the total/maximum plan length. The dynamic MAPF (D-MAPF) problem considers the changes that occur in the environment or in the team during the execution of a MAPF plan (e.g., new agents joining the team, existing agents leaving the environment, new obstacles being added, existing obstacles being removed or moved) and aims to find a new plan for agents to reach their goals. The existing approaches to solving D-MAPF consider different objective functions (e.g., minimizing the makespan or the sum of costs) and changes (e.g., team or environment changes), make different assumptions on entrances and departures of agents (e.g., agents immediately or later appear at their initial locations, agents stay or disappear when they reach their destinations), and investigate different methods to solve D-MAPF. For instance, Lifelong MAPF ( Wan et al., 2018 ; Li et al., 2021 ) considers assignment of new goal locations to the agents who have completed their plans, which can be viewed as adding a new agent. An incremental version of CBS algorithm was introduced by Wan et al., 2018 such that solutions for new agents are computed while re-using the solutions for the existing agents and they are adjusted only if needed at each time step. The idea of Windowed MAPF was used by Li et al., 2021 , where the instance is splitted into a sequence of instances, replanning is done periodically after a specific number of steps, and the collisions are resolved only for the steps within a given window. Online MAPF ( Svancara et al., 2019 ) considers the addition of new agents as a dynamic change, and allows the agents to appear from a garage after some waiting and disappear from the environment once it reaches its goal. Different methods were introduced for solving this problem with SAT based and search based solvers and these methods are further investigated by Morag et al., 2022 in terms of their quality. One of the methods introduced for solving Online MAPF is the Replan-All method, that discards the existing plan and re-solves MAPF for all agents considering the changes. Ma, 2021 investigates Online MAPF problem theoretically, gives complexity results and provides a classification for online MAPF algorithms. Ho et al., 2019 consider an online and 3-dimensional setting, with heterogeneous agents being added during execution and solves the problem using modified versions of CBS and ECBS algorithms. Different from these studies, in terms of changes, Bogatarkan et al., 2019 consider leaving agents and changes in obstacles as well. Their Revise-and-Augment method reuses the existing plan: when a change occurs, the plans of existing agents are revised by rescheduling their waiting times, while plans are computed for the new agents. Atiq et al., 2020 consider a similar problem. When a change occurs in the environment, a minimal subset of agents having conflicts are identified and replanning is applied to resolve conflicts. In this study, we investigate D-MAPF further with the following motivations, and theoretical and practical contributions. \bullet To be able to study rich variations of D-MAPF mentioned above, on a common ground, we introduce a rigorous definition for D-MAPF, that is general enough to cover 1) various changes in the environment and the team of agents over time, 2) different objective functions on plans, and 3) different assumptions on appearances/disappearances of agents, and that is not specifically oriented towards a particular method. \bullet We introduce a new framework to solve D-MAPF, that is general and flexible enough to allow different replanning and/or repairing methods. With the motivation of a modular architecture and efficient computations, our framework utilizes multi-shot computation ( Gebser et al., 2019 ) based on ASP ( Lifschitz, 2008 ; Gelfond and Lifschitz, 1991 ) . Recall that multi-shot solving allows changes to the input ASP program in time, by introducing an external control to the ASP system. The external control allows operations, such as adding and grounding new programs, assigning truth values of some atoms, and solving the updated program, while the ASP system is running. Our earlier studies ( Bogatarkan et al., 2019 ) utilize single-shot computation. \bullet We design and implement the Replan-All and Revise-and-Augment methods using multi-shot ASP, and integrate them in the general D-MAPF framework. We empirically observe that multi-shot Replan-All is computationally more efficient but sometimes dramatic changes in the paths of the existing agents occur in the recomputed plans. Such changes are not desired from the perspective of real-world applications. For instance, in a warehouse where robots collaborate with human workers, changes in the routes of robots might be unexpected, distracting, unsafe, and inefficient for human workers. \bullet We introduce a new method for D-MAPF, called Revise-and-Augment-in-Tunnels , that combines the advantages of these two methods. Unlike revise-augment, this method does not require that every existing agent follow their existing paths while revising their plans. Instead, 1) it creates a “tunnel” for each existing agent, that consists of the agent’s existing path and the neighboring locations within a specified “width”, and 2) it allows every existing agent to follow a path within their own tunnel while it revises their plans. So the existing agents do not have to follow their previously computed paths. While revising the plans of existing agents within their tunnels, 3) the Revise-and-Augment-in-Tunnels method computes plans for the new agents and augments these plans with the revised plans, respecting the collision constraints. Note that as the tunnel width gets larger (resp. smaller), the Revise-and-Augment-in-Tunnels method gets closer to the Replan-All method (resp. the Revise-and-Augment method). \bullet We implement the Revise-and-Augment-in-Tunnels method using multi-shot ASP, and integrate it in our D-MAPF framework. We design and perform experiments to better understand the strengths and the weaknesses of this new method, considering computational performance (in time) and quality of solutions (in terms of plan changes). 2 Preliminaries: Paths, Traversals, Plans We introduce a more general definition for MAPF problem, compared to the earlier definitions ( Erdem et al., 2013 ; Stern et al., 2019 ) ,

Read the complete text