Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic

We focus on maps as undirected unweighted graphs $G=\langle\mathcal{V},\mathcal{E}\rangle$, where vertex set $\mathcal{V}$ contains all possible locations and edge set $\mathcal{E}$ contains all possible transitions or movements between adjacent locations. An instance $I$ consists of a map $G$ and a set of agents $\mathcal{A}=\{a_{1},...,a_{m}\}$ with each agent $a_{i}$ having a start location $s_{i}\in\mathcal{V}$ and a goal location $g_{i}\in\mathcal{V}$. At every time step $t$, all agents can move along the edges in $\mathcal{E}$ or wait at their current location (Stern et al. 2019).

MAPF aims to find a collision-free plan for all agents. A plan $P=\{p_{1},...,p_{m}\}$ consists of individual paths $p_{i}=\langle p_{i,1},...,p_{i,l(p_{i})}\rangle$ per agent $a_{i}$, where $\langle p_{i,t},p_{i,t+1}\rangle=\langle p_{i,t+1},p_{i,t}\rangle\in\mathcal{E}$, $p_{i,1}=s_{i}$, $p_{i,l(p_{i})}=g_{i}$, and $l(p_{i})$ is the length or travel distance of path $p_{i}$. The delay $\textit{del}(p_{i})$ of path $p_{i}$ is defined by the difference of path length $l(p_{i})$ and the length of the shortest path from $s_{i}$ to $g_{i}$ w.r.t. map $G$.

In this paper, we consider vertex conflicts $\langle a_{i},a_{j},v,t\rangle$ that occur when two agents $a_{i}$ and $a_{j}$ occupy the same location $v\in\mathcal{V}$ at time step $t$ and edge conflicts $\langle a_{i},a_{j},u,v,t\rangle$ that occur when two agents $a_{i}$ and $a_{j}$ traverse the same edge $\langle u,v\rangle\in\mathcal{E}$ in opposite directions at time step $t$ (Stern et al. 2019). A plan $P$ is a solution, i.e., feasible when it does not have any vertex or edge conflicts. Our goal is to find a feasible solution by minimizing the flowtime $\sum_{p\in P}l(p)$ equivalent to minimizing the sum of delays or (total) cost $c(P)=\sum_{p\in P}\textit{del}(p)$. In the context of anytime MAPF, we also consider the Area Under the Curve (AUC) as a measure of how quickly we approach the quality of our final solution.

Anytime MAPF searches for solutions within a given time budget. The solution quality monotonically improves with increasing time budget (Cohen et al. 2018; Li et al. 2021).

MAPF-LNS based on Large Neighborhood Search (LNS) is the current state-of-the-art approach to anytime MAPF and shown to scale up to large-scale scenarios with hundreds of agents (Huang et al. 2022; Li et al. 2021). Starting with an initial feasible plan $P$, e.g., found via prioritized planning (PP) from (Silver 2005), MAPF-LNS iteratively modifies $P$ by destroying $N<m$ paths of the neighborhood $A_{N}\subset\mathcal{A}$. The destroyed paths $P^{-}\subset P$ are then repaired or replanned using PP to quickly generate new paths $P^{+}$. If the new cost $c(P^{+})$ is lower than the previous cost $c(P^{-})$, then $P$ is replaced by $(P\backslash P^{-})\cup P^{+}$, and the search continues until the time budget runs out. The result of MAPF-LNS is the last accepted solution $P$, with the lowest cost so far.

MAPF-LNS uses a set of three destroy heuristics, namely a random uniform selection of $N$ agents, an agent-based heuristic, and a map-based heuristic (Li et al. 2021). The agent-based heuristic generates a neighborhood, including a seed agent $a_{j}$ with the current maximum delay and other agents, determined via random walks, that prevent $a_{j}$ from achieving a lower delay. The map-based heuristic randomly chooses a vertex $v\in\mathcal{V}$ with a degree greater than 2 and generates a neighborhood of agents moving around $v$. All heuristics are randomized but stationary since they do not adapt their rules and degree of randomization, i.e., the distributions, based on prior improvements made to the solution.

The original MAPF-LNS uses an adaptive selection mechanism $\pi$ by maintaining selection weights to choose destroy heuristics $P$ (Li et al. 2021; Ropke and Pisinger 2006).

Multi-armed bandits (MABs) or simply bandits are fundamental decision-making problems, where an MAB or selection algorithm $\pi$ repeatedly chooses an arm $j$ among a given set of arms or options $\{1,...,K\}$ to maximize an expected reward of a stochastic reward function $\mathcal{R}(j):=X_{j}$, where $X_{j}$ is a random variable with an unknown distribution $f_{X_{j}}$ (Auer, Cesa-Bianchi, and Fischer 2002). To solve an MAB, one has to determine an optimal arm $j^{*}$, which maximizes the expected reward $\mathbb{E}\big{[}X_{j}\big{]}$. The MAB algorithm $\pi$ has to balance between exploring all arms $j$ to accurately estimate $\mathbb{E}\big{[}X_{j}\big{]}$ and exploiting its knowledge by greedily selecting the arm $j$ with the currently highest estimate of $\mathbb{E}\big{[}X_{j}\big{]}$. This is known as the exploration-exploitation dilemma, where exploration can find arms with higher rewards but requires more time for trying them out, while exploitation can lead to fast convergence but possibly gets stuck in a poor local optimum. We will focus on Thompson Sampling and $\epsilon$-Greedy as MAB algorithms and explain them in Section 4.2.

In recent years, MABs have been used to tune learning and optimization algorithms on the fly (Badia et al. 2020; Hendel 2022; Schaul et al. 2019). UCB1 and $\epsilon$-Greedy are commonly used for LNS destroy heuristic selection in traveling salesman problems (TSP), mixed integer linear programming (MILP), and vehicle routing problems (VRP) (Chen et al. 2016; Hendel 2022). In most cases, a heavily engineered reward function with several weighted terms is used for training the MAB. Recently, a MAPF-LNS variant, called BALANCE, has been proposed to adapt the neighborhood size $N$ along with the destroy heuristic choice using a bi-level Thompson Sampling approach (Phan et al. 2024b).

Instead of adapting the destroy heuristic selection, we propose a single adaptive destroy heuristic, thus simplifying the high-level MAPF-LNS procedure (Figure 1). Our destroy heuristic uses restricted Thompson Sampling with simple binary rewards to select a seed agent from the top-$K$ set of the most delayed agents for LNS neighborhood generation, which can also be applied to other problem classes, such as TSP, MILP, or VRP (Pisinger and Ropke 2019).

Machine learning has been used in MAPF to directly learn collision-free path finding, to guide the node selection in search trees, or to select appropriate MAPF algorithms for certain maps (Alkazzi and Okumura 2024; Huang, Dilkina, and Koenig 2021; Kaduri, Boyarski, and Stern 2020; Phan et al. 2024a, 2025; Sartoretti et al. 2019). (Huang et al. 2022; Yan and Wu 2024) propose machine learning-guided variants of MAPF-LNS, where neighborhoods are generated by stationary procedures, e.g., the destroy heuristics of (Li et al. 2021). The neighborhoods are then selected via an offline trained model. Such methods cannot adapt during the search and require extensive prior efforts like data acquisition, model training, and feature engineering.

We focus on adaptive approaches to MAPF-LNS using online learning via MABs. Our destroy heuristic can adjust on the fly via binary reward signals, indicating a successful or failed improvement of the solution quality. The rewards are directly obtained from the LNS without any prior data acquisition or expensive feature engineering.

Our adaptive destroy heuristic is inspired by the agent-based heuristic of (Li et al. 2021), which is empirically confirmed to be the most effective standalone heuristic in most maps (Li et al. 2021; Phan et al. 2024b).

The idea is to select a seed agent $a_{j}\in\mathcal{A}$, whose path $p_{j}\in P$ has a high potential to be shortened, indicated by its delay $\textit{del}(p_{j})$. A random walk is performed from a random position in $p_{j}$ to collect $N-1$ other agents $a_{i}$ whose paths $p_{i}$ are crossed by the random walk, indicating their contribution to the delay $\textit{del}(p_{j})$, to generate a neighborhood $A_{N}\subset\mathcal{A}$ of size $|A_{N}|=N<m$ for LNS destroy-and-repair.

The original destroy heuristic of (Li et al. 2021) greedily selects the seed agent with the maximum delay $\textit{max}_{p_{i}\in P}\textit{del}(p_{i})$. To avoid repeated selection of the same agent, the original heuristic maintains a tabu list, which is emptied when all agents have been selected or when the current seed agent $a_{j}$ has no delay, i.e., $\textit{del}(p_{j})=0$. Therefore, the heuristic has to iterate over all agents $a_{i}\in\mathcal{A}$ in the worst case, which is time-consuming for large-scale scenarios with many agents, introducing a potential performance bottleneck. The original MAPF-LNS cannot overcome this bottleneck because it only adapts the high-level heuristic selection via $\pi$, as shown in Figure 1, and thus can only switch to other (less effective) destroy heuristics as an alternative.

Our goal is to overcome the limitation of the original agent-based destroy heuristic, and consequently of MAPF-LNS, using MABs. We model each agent $a_{i}\in\mathcal{A}$ as an arm $i$ and maintain two counters per agent, namely $\alpha_{i}>0$ for successful cost improvements, and $\beta_{i}>0$ for failed cost improvements. Both counters represent the parameters of a Beta distribution $\textit{Beta}(\alpha_{i},\beta_{i})$, which estimates the potential of an agent $a_{i}\in\mathcal{A}$ to improve the solution as a seed agent. $\textit{Beta}(\alpha_{i},\beta_{i})$ has a mean of $\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}}$ and is initialized with $\alpha_{i}=1$ and $\beta_{i}=1$, corresponding to an initial 50:50 chance estimate that an agent $a_{i}$ could improve the solution if selected as a seed agent (Chapelle and Li 2011).

Since the number of agents $m$ can be large, a naive MAB would need to explore an enormous arm space, which poses a similar bottleneck as the tabu list approach of the original agent-based heuristic (Section 4.1). Thus, we restrict the agent selection to the top-$K$ set $\mathcal{A}_{K}\subseteq\mathcal{A}$ of the most delayed agents with $K\leq m$ to ease exploration.

The simplest MAB is $\epsilon$-Greedy, which selects a random seed agent $a_{i}\in\mathcal{A}_{K}$ with a probability of $\epsilon\in[0,1]$, and the agent with the highest expected success rate $\frac{\alpha_{i}}{\alpha_{i}+\beta_{i}}$ with the complementary probability of $(1-\epsilon)$.

We propose a restricted Thompson Sampling approach to select a seed agent from $\mathcal{A}_{K}$. For each agent $a_{i}\in\mathcal{A}_{K}$ within the top-$K$ set, we sample an estimate $q_{i}\sim\textit{Beta}(\alpha_{i},\beta_{i})$ of the solution improvement rate and select the agent with the highest sampled estimate $q_{i}$. Thompson Sampling is a Bayesian approach with $\textit{Beta}(1,1)$ being the prior distribution of the improvement success rate and $\textit{Beta}(\alpha_{i},\beta_{i})$ with updated parameters $\alpha_{i}$ and $\beta_{i}$ being the posterior distribution (Chapelle and Li 2011; Thompson 1933).

Our destroy heuristic, called ADDRESS heuristic, first sorts all agents w.r.t. their delays to determine the top-$K$ set $\mathcal{A}_{K}\subseteq\mathcal{A}$ of the most delayed agents. Restricted Thompson Sampling is then applied to the parameters $\alpha_{i}$ and $\beta_{i}$ of all agents $a_{i}\in\mathcal{A}_{K}$ to select a seed agent $a_{j}$. An LNS neighborhood $A_{N}\subset\mathcal{A}$ is generated via random walks, according to (Li et al. 2021), by adding agents $a_{i}\in\mathcal{A}$ whose paths are crossed by the random walk. Note that these agents $a_{i}\in A_{N}\backslash\{a_{j}\}$ are not necessarily part of the top-$K$ set $\mathcal{A}_{K}$.

The full formulation of our ADDRESS heuristic with Thompson Sampling is provided in Algorithm 1, where $I$ represents the instance to be solved, $P$ represents the current solution, $K$ restricts the seed agent selection, and $\langle\alpha_{i},\beta_{i}\rangle_{1\leq i\leq m}$ represent the parameters for the corresponding Beta distributions per agent for Thompson Sampling.

We now integrate our ADDRESS heuristic into the MAPF-LNS algorithm (Li et al. 2021). For a more focused search, we propose a simplified variant, called ADDRESS, which only uses our adaptive destroy heuristic instead of determining a promising stationary heuristic via time-consuming exploration, as illustrated in Figure 1.

ADDRESS iteratively invokes our proposed destroy heuristic of Algorithm 1 with the parameters $\langle\alpha_{i},\beta_{i}\rangle_{1\leq i\leq m}$ to select a seed agent $a_{j}\in\mathcal{A}$ and generate an LNS neighborhood $A_{N}\subset\mathcal{A}$ using the random walk procedure of the original MAPF-LNS (Li et al. 2021). Afterward, the standard destroy-and-repair operations of MAPF-LNS are performed on the neighborhood $A_{N}$ to produce a new solution $P^{\prime}=(P\backslash P^{-})\cup P^{+}$. If the new solution $P^{\prime}$ has a lower cost than the previous solution $P$, then $\alpha_{j}$ is incremented and $P$ is replaced by $P^{\prime}$. Otherwise, $\beta_{j}$ is incremented. The whole procedure is illustrated in Figure 2.

The full formulation of ADDRESS is provided in Algorithm 2, where $I$ represents the instance to be solved and $K$ restricts the seed agent selection. The parameters $\langle\alpha_{i},\beta_{i}\rangle_{1\leq i\leq m}$ are all initialized with 1 as a uniform prior.

ADDRESS is a simple and adaptive approach to scalable anytime MAPF. The adaptation is controlled by the learnable parameters $\alpha_{i}$ and $\beta_{i}$ per agent $a_{i}$, and the top-$K$ ranking of potential seed agents. Our ADDRESS heuristic can significantly improve MAPF-LNS, overcoming the performance bottleneck of the original agent-based heuristic of (Li et al. 2021) by selecting seed agents via MABs instead of greedily, and restricting the selection to the top-$K$ set of the most delayed agents $\mathcal{A}_{K}$ to ease exploration.

The parameters $\alpha_{i}$ and $\beta_{i}$ enable the seed agent selection via Thompson Sampling, which considers the improvement success rate under uncertainty via Bayesian inference (Thompson 1933). Unlike prior MAB-enhanced LNS approaches, ADDRESS only uses binary rewards denoting success or failure, thus greatly simplifying our approach compared to alternative MAB approaches (Chen et al. 2016; Chmiela et al. 2023; Hendel 2022; Phan et al. 2024b).

The top-$K$ set enables efficient learning by reducing the number of options for Thompson Sampling, which otherwise would require exhaustive exploration of all agents $a_{i}\in\mathcal{A}$. The top-$K$ set supports fast adaptation by filtering out seed agent candidates whose paths were significantly shortened earlier. While the top-$K$ ranking causes some overhead due to sorting agents, our experiments in Section 5 suggest that the sorting overhead is outweighed by the performance gains regarding cost and AUC in large-scale scenarios.

Our single-destroy-heuristic approach enables a more focused search toward high-quality solutions without time-consuming exploration of stationary (and less effective) destroy heuristics. Due to its simplicity, our ADDRESS heuristic can be easily applied to other problem classes, such as TSP, MILP, or VRP, when using so-called worst or critical destroy heuristics, focusing on high-cost variables that “spoil” the structure of the solution (Pisinger and Ropke 2019). We defer such applications to future work.