Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields
Arseniy Pertzovsky, Roni Stern, Ariel Felner, Roie Zivan · 2025
Read Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields by Arseniy Pertzovsky, Roni Stern, Ariel Felner, Roie Zivan (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-2505-22753.txt.
Introduction
Arseniy Pertzovsky, Roni Stern, Ariel Felner, and Roie Zivan wrote a 2025 paper on moving many agents without crashes. In their task, each agent must reach a goal, and in the lifelong form new goals keep coming. The authors test whether fields that pull and push agents can help.
The team added these fields to three known planning methods, from simple ranked planning to a more advanced search method. Tests showed no gain for the one-off task. For the lifelong task, though, throughput rose by up to seven times. The result points to a cheap add-on that helps most when goals keep renewing.
Catalog record
| CREATOR | Arseniy Pertzovsky, Roni Stern, Ariel Felner, Roie Zivan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-22753
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields Arseniy Pertzovsky, Roni Stern, Ariel Felner, Roie Zivan Abstract We explore the use of Artificial Potential Fields (APFs) to solve Multi-Agent Path Finding (MAPF) and Lifelong MAPF (LMAPF) problems. In MAPF, a team of agents must move to their goal locations without collisions, whereas in LMAPF, new goals are generated upon arrival. We propose methods for incorporating APFs in a range of MAPF algorithms, including Prioritized Planning, MAPF-LNS2, and Priority Inheritance with Backtracking (PIBT). Experimental results show that using APF is not beneficial for MAPF but yields up to a 7-fold increase in overall system throughput for LMAPF. † † paperid: 7341 1 Introduction Artificial Potential Fields (APFs) [ Khatib(1986) ] can be used to improve the deployment of mobile agents in an environment with obstacles. When using this physics-inspired approach, each agent is considered a particle that is moved on the basis of the attraction and repulsion forces that are applied to it. Typically, obstacles and other agents generate repulsive forces, while targets and destination goals apply attractive forces [ Koren and Borenstein(1991) ] . APFs have been used to solve many motion planning problems [ Mac et al.(2016)Mac, Copot, Tran, and De Keyser , Hagelback and Johansson(2009) , Daily and Bevly(2008) ] , with successful applications in obstacle avoidance of an unmanned aircraft [ Rezaee and Abdollahi(2012) ] , collision avoidance systems for automated vehicles [ Wahid et al.(2017)Wahid, Zamzuri, Rahman, Kuroda, and Raksincharoensak ] and more [ Mac et al.(2016)Mac, Copot, Tran, and De Keyser ] . Multi-agent Pathfinding (MAPF) is the problem of finding paths for a group of agents such that they reach their goals without colliding with each other [ Stern et al.(2019)Stern, Sturtevant, Felner, Koenig, Ma, Walker, Li, Atzmon, Cohen, Kumar, Boyarski, and Bartak ] . Instances of MAPF exist in robotics [ Barták et al.(2019)Barták, Švancara, Škopková, Nohejl, and Krasičenko ] , automated warehouses [ Wurman et al.(2008)Wurman, D’Andrea, and Mountz , Salzman and Stern(2020) ] , digital entertainment [ Ma et al.(2017)Ma, Yang, Cohen, Kumar, and Koenig ] and more [ Morris et al.(2016)Morris, Pasareanu, Luckow, Malik, Ma, Kumar, and Koenig ] . Solving MAPF is computationally difficult since the number of possible actions at every time point is exponential in the number of agents. In fact, for common optimization criteria, finding an optimal solution for MAPF is NP-hard [ Yu and LaValle(2013) , Surynek(2010) ] . Popular optimal and suboptimal algorithms, such as Prioritized Planning (PrP) [ Silver(2005) ] , Conflict-Based Search (CBS) [ Sharon et al.(2015)Sharon, Stern, Felner, and Sturtevant ] , and Large Neighborhood Search for MAPF (MAPF-LNS) [ Li et al.(2021a)Li, Chen, Harabor, Stuckey, and Koenig ] , mitigate this combinatorial challenge by planning a path for each agent individually and imposing different forms of constraints to avoid collisions. Alternatively, algorithms such as PIBT, LaCAM, and LaCAM ∗ [ Okumura et al.(2022)Okumura, Machida, Défago, and Tamura , Okumura(2023) , Okumura(2023) ] , directly search the space of configurations , where a configuration is a set of all agents’ locations in a given time step. However, using existing algorithms often results in congestion occurring in areas of the environment that are shared by the shortest paths of multiple agents. This congestion problem is exacerbated when solving lifelong MAPF (LMAPF) [ Li et al.(2021a)Li, Chen, Harabor, Stuckey, and Koenig , Švancara et al.(2019)Švancara, Vlk, Stern, Atzmon, and Barták ] , where an agent receives a new goal location whenever it reaches its current goal location. In LMAPF, congested areas tend to become more and more congested over time, resulting in a decrease in overall system efficiency. The use of APFs is a natural approach to encourage agents to avoid congested areas, adding repulsion forces not only to avoid obstacles but also to avoid the paths of other agents. In this paper, we explore the potential of this approach. We first investigate using APFs to solve MAPF problems by following a simple, myopic approach: each agent plans its next move based on the forces of APFs of the other agents. The resulting MAPF algorithm (Direct APF) compares poorly with existing MAPF algorithms on standard MAPF benchmarks. Apparently, relying only on attraction and repulsion forces in MAPF is too myopic, and longer-horizon path planning is needed. We, therefore, explore the addition of APFs into existing MAPF solvers. We integrate APFs into Temporal A ∗ (TA ∗ ) [ Silver(2005) ] and Safe Interval Path Planning with Soft constraints (SIPPS) [ Li et al.(2022)Li, Chen, Harabor, Stuckey, and Koenig ] , which are single-agent pathfinding algorithms that plan for individual agents under different types of constraints. We modify the cost of agents’ actions to consider the APFs created by other agents who have already planned their paths. Consequently, the path returned for an agent not only optimizes fast arrival at the goal but also avoids areas congested by other agents. We also integrate APFs in a similar way in PIBT, LaCAM, and LaCAM ∗ . Experimental results on a range of standard MAPF benchmark problems show that our APF-augmented algorithms are not effective for classical MAPF. However, they are very effective when solving LMAPF, yielding up to a 7-fold increase in throughput. 2 Definition and Background A classic MAPF problem is defined by a tuple \langle k,G,s,g\rangle where k is the number of agents, G=(V,E) is an undirected graph, s:[1,...,k]\rightarrow V maps an agent to a start vertex, and g:[1,...,k]\rightarrow V maps an agent to a goal vertex. Time is discretized into time-steps. In every time-step, each agent occupies a single vertex and performs a single action . There are two types of actions: wait and move . The result of a wait action of an agent located in some vertex v at some time-step is that the agent will stay at the same vertex v at the next time-step. The result of a move action is that the agent moves to an adjacent vertex v^{\prime} on the graph (i.e., (v,v^{\prime})\in E ). A single-agent path for agent a_{i} , denoted \pi_{i} , is a sequence of actions that start from s_{i} and end in g_{i} . A solution to a MAPF is a set of single agent paths \pi=\{\pi_{1},\ldots,\pi_{k}\} , one per agent, that do not conflict . Two single-agent paths have a vertex conflict if they aim to occupy the same vertex at the same time and a swapping conflict if they aim to traverse the same edge at the same time from opposing directions. The sum-of-costs (SOC) of a MAPF solution \pi is the sum over the lengths of its constituent single-agent paths. It is often desirable to find minimal SOC solutions. Some MAPF algorithms are complete and SOC-optimal , i.e., guaranteed to return a valid optimal SOC solution if such exists. Primary examples of such algorithms are CBS [ Sharon et al.(2015)Sharon, Stern, Felner, and Sturtevant ] , ICTS [ Sharon et al.(2013)Sharon, Stern, Goldenberg, and Felner ] , A ∗ +OD+ID [ Standley(2010) ] , M* [ Wagner and Choset(2011) ] , BCP [ Lam et al.(2022)Lam, Le Bodic, Harabor, and Stuckey ] , and SAT-MDD [ Surynek et al.(2016)Surynek, Felner, Stern, and Boyarski ] . Other MAPF