Improving Learnt Local MAPF Policies with Heuristic Search

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-03 21:23:33

Abstract: Multi-agent path finding (MAPF) is the problem of finding collision-free paths for a team of agents to reach their goal locations. 
State-of-the-art classical MAPF solvers typically employ heuristic search to find solutions for hundreds of agents but are typically centralized and can struggle to scale to larger numbers of agents.
Machine learning (ML) approaches that learn policies for each agent are appealing as these could be decentralized systems and scale well while maintaining good solution quality. Current ML approaches to MAPF have proposed methods that have started to scratch the surface of this potential. However, state-of-the-art ML approaches produce "local" policies that only plan for a single timestep and have poor success rates and scalability. Our main idea is that we can improve a ML local policy by using heuristic search methods on the output probability distribution to resolve deadlocks and enable full horizon planning. We show several model-agnostic ways to use heuristic search with ML that significantly improves the local ML policy's success rate and scalability. 
To our best knowledge, we demonstrate the first time ML-based MAPF approaches have scaled to similar high congestion (e.g. 40% agent density) as state-of-the-art heuristic search methods.

Main paper: 
 introduction: 
 The increasing availability of robotic hardware has increased the importance of planning for robotic teams instead of individual agents. These multi-agent robotic systems will enable a multitude of capabilities like rapid search and rescue, exploration on Mars, and efficient warehouse management. Multi-agent systems are appealing as each robot can be cheap and relatively simple while the entire system is scalable and can achieve complex goals.A fundamental problem with multiple robots is figuring out how each robot should move. Without careful consideration, robots could be stuck in a deadlock or collide with each other. Multi-agent path finding (MAPF) research focuses on developing algorithms for finding collision-free paths for a team of agents to reach their target locations in an efficient and safe manner. Although there are several possible approaches to tackle MAPF, the vast majority of these MAPF methods are heuristic search-based methods. These methods have optimality or bounded suboptimality solution guarantees and can solve long-horizon MAPF problems. However these methods typically trade off solution quality with compute time and require a centralized planner. We compare running MAGAT (Li et al. 2021) with its default collision shielding (blue) vs running MA-GAT with our PIBT collision shielding (orange). MAGAT is a learnt local policy that predicts a one-step policy per agent that could lead to collisions and therefore requires collision shielding to prevent collisions. PIBT (Okumura et al. 2022 ) is a heuristic search technique for solving MAPF. We see that using the exact same learnt model with our PIBT-based collision shielding dramatically improves performance and scalability without any additional training or information.Machine learning (ML) approaches which learn policies 45 for each agent are appealing as these could be decentralized systems which scale well while maintaining good solution quality. Current ML-based MAPF work methods are starting to scratch the beginning of this potential. State-of-theart ML MAPF approaches learn "local" policies that take 50 in local observations and output a 1-step action distribution. However ML in general struggles with long-horizon planning and low-error situations; both are critical in MAPF which requires long-horizon planning across many agents with very little room for errors which can cause collisions 55 or deadlock. Thus recent ML-based MAPF works have been proposed for grid-worlds but currently do not reach the standards of state-of-the-art heuristic MAPF solvers.Our main idea is that we can boost learnt MAPF approaches by using it with heuristic search methods. When 60 using learnt policies that could predict actions which cause agents to collide, current ML approaches use a naive "collision shield" that replaces collisions with deadlock (see . We instead show how we can use PIBT (Okumura et al. 2022 ) (a heuristic search method) as a smart collision shield during execution. We demonstrate this approach significantly boosts performance rather than solely using the learnt policy. We then show how we can more closely integrate learnt local MAPF policies with LaCAM (Okumura 2022) (another heuristic search method) to further improve performance. We explore other neural network agnostic approaches of combining a learnt policy with PIBT and La-CAM and show significant improvement in success rate and costs over the learnt policy by itself.Our goal in this paper is not to show that ML approaches for MAPF are superior to classical heuristic search approaches. Our objective instead is to show that given a learnt local policy, we can use heuristic search based model-agnostic methods to significantly improve the performance of these policies. In regards to whether ML-based approaches or heuristic search approaches are better, we offer a more nuanced view. We demonstrate in our experiments that given existing strong 2D heuristics (i.e. backward Dijkstra's), current classical heuristic search approaches are extremely strong and will likely outperform ML approaches in 2D MAPF. However given imperfect heuristics, we see that ML approaches can actually outperform certain heuristic search methods. Section 4.4 discusses in further detail where learning may be applicable given our findings.Overall, the main point we attempt to show in this paper is that ML methods for MAPF should fully leverage heuristic search. Doing so can substantially boost success rates and scalability. Succinctly stated, our main contributions are:1. Creating a "smart" collision shield using PIBT that postprocesses learnt policy conflicts instead of freezing conflicting agents. 2. Showing a neural-network agnostic framework for using a learnt 1-step policy with PIBT/LaCAM for full horizon planning to enable theoretical completeness and boost success rate, and experimenting with several variants. 
related works: 
 There are many different approaches for MAPF which range from optimization, heuristic search, and machine learning. We first define MAPF and then focus on the relevant heuristic search and machine learning approaches.We describe the classic single-shot 2D MAPF. Here, we are given a known gridworld with free space and obstacles, and a single start-goal pair for each agent. Each agent can move in its 4 cardinal directions or wait for a total of 5 different actions per discretized timestep. Our objective is to find a collision free space-time path for all the agents to reach their goals without obstacle conflicts, vertex conflicts (two agents at the same location at the same time), or edge conflicts (two agents swapping locations across consecutive timesteps). In addition to finding a collision-free path, we hope to find efficient collision-free paths which minimize the total flowtime (sum of each agent's path until they rest at the goal). Single-shot MAPF is harder than lifelong (where agents immediately move to a different goal if they reach their first goal) or disappear-at-goal MAPF variants as agents need to rest at the goal location. Agents waiting at the goal requires tough reasoning for learnt models as naively stopping these agents at the goal can block later agents from reaching their goal locations. Our framework is applicable to other MAPF 125 variants too but we choose to evaluate it on the more difficult single-shot MAPF scenario.Heuristic search methods aim to tackle the exponentially growing search space by intelligently leveraging the semi-130 independence of agents. Conflict-Based Search is a popular state-of-the-art complete and optimal framework for MAPF (Sharon et al. 2015) . This technique plans for each agent individually and then resolves conflicts iteratively by applying constraints and replanning. Improvements on this founda-135 tional technique have been shown to scale up to solving hundreds of agents optimally or bounded-suboptimally (Barer et al. 2014; Boyrasky et al. 2015; Li, Ruml, and Koenig 2021; Sharon et al. 2013; Li et al. 2020a Li et al. , 2019)) . These methods typically have good solution quality but computationally 140 scale poorly as the number of agents increases.PIBT Recently, PIBT and its extensions (Okumura et al. 2022; Okumura 2022 ) have shown how greedy heuristic search methods can scale extremely well at the expense of solution cost. At its core, at each timestep, PIBT has each 145 agent greedily attempt its best action by following its individual best path. If two agents have actions that would lead to conflicts, the higher priority agent has precedence and the lower priority agent must attempt its second-best action. This procedure repeats until a conflict-free set of actions is 150 found, if not the first agent is forced to attempt its secondbest action (and logic repeats accordingly). PIBT interleaves greedy 1-step planning and execution but is still effective in long horizon MAPF tasks. PIBT uses backward Dijkstra's heuristic estimates to determine what actions are best (i.e. 155 the action leading to the state with the least heuristic estimate is the best).LaCAM LaCAM (Okumura 2022) builds on PIBT by using it as a successor generator within a Depth-First Search (DFS) of the joint-configuration space. We describe LaCAM 160 in a simplified way to get the main idea across, but note that LaCAM is more nuanced. Given N agents, imagine running a "joint-configuration" space DFS. Specifically, given the initial configuration, we generate all possible valid neighboring joint-configuration successors, pick one we haven't 165 seen, and repeat. Note that a valid joint-configuration successor will move agents by only one step (or wait) and will not have vertex, edge, or obstacle collisions. In 2D MAPF with each agent having 5 actions, this means N agents can generate up to 5 N -1 new successors (the minus 1 as all 170 agents waiting will not results in a new configuration). This approach is clearly not scalable to many agents due to the exponential number of successors.LaCAM intelligently bypasses this issue by generating an exponential number of successors lazily. The key insight is 175 that given a joint-configuration J A , we must generate all possible successors, but we can do this sequentially as we encounter them rather than all at once. They do this by employing lazy constraints where each constraint specifies that an agent should be at a specific location. Therefore, if we encounter J A multiple times when back-tracking in the DFS, we will require different agents to be at different locations and generate different joint-configuration successors that satisfy these constraints. Figure 2 shows an example where DFS goes to the left, exhausts successors, and then revisits the start configuration and lazily generates a new successor to the right (e.g. by constraining the orange agent to be in the middle). In the limit of time and memory, LaCAM explores all possible successors of J A . It is therefore crucial that the configuration generator be fast while satisfying the constraints. LaCAM found that PIBT performed well as a configuration generator compared to other MAPF methods. Since LaCAM eventually explores all configurations, LaCAM is theoretically complete. In practice, LaCAM improves success rate over PIBT as the DFS over configurations allows getting out of local minima (e.g. deadlock). La-CAM is extremely effective on existing 2D benchmarks.Machine learning approaches typically attempt to learn local 1-step policies for each agent which they then execute in parallel to solve the MAPF instance. Each local policy is fed a local field-of-view of the map, nearby agents, and goal representations, and outputs a probability distribution over the 5 possible actions.PRIMAL (Sartoretti et al. 2019 ) is a foundational machine learning method that uses reinforcement learning and supervised learning to learn local policies. PRIMAL2 (Damani et al. 2021 ) improves the observation inputs from PRIMAL to handle mazes by automatically annotating potential bottlenecks. SCRIMP (Wang et al. 2023 ) uses the same framework but replaces the complicated PRIMAL2 inputs with extremely small 3x3 observations and inter-agent communication via a modified transformer. GNN (Li et al. 2020b ) is a popular approach that solely uses supervised learning to learn a local policy. They use a Graph Neural Network (Gama et al. 2019) for communication and symmetry breaking across agents. MAGAT (Li et al. 2021 ) improves upon the message-passing neural network architecture in GNN. GNN introduces (and MAGAT also uses) a "collision shield" which takes each agent's preferred action and executes it if collision-free or freezes the agent if it would cause a collision. Other works, e.g. PRI-MAL and PRIMAL2, do not explicitly define their collision shield but use similar implicit shielding.A key problem highlighted by most ML works is deadlock between agents. PRIMAL's results show how deadlock can commonly occur when agents rest at their goal location. PRIMAL2 specifically aims to learn conventions to decrease deadlock in maze structures. SCRIMP uses their learnt statevalues (an additional output of their model apart from their local policy) to calculate agent priorities that they use to prioritize agents in deadlock, and show that this improves performance over naive collision shielding. We qualitatively noticed how MAGAT encounters deadlock as well. Our insight is that we can resolve local deadlock using heuristic search methods on top of the learnt policy predictions. 
improving learnt local policies with heuristic search: 
 Machine learning MAPF policy methods aim to learn a local policy that each agent runs in a decentralized manner. Theo-240 retically, these techniques should be able to scale well to an increasing number of agents as the time should be roughly constant regardless of the number of agents. However existing learnt methods iteratively plan and execute 1-step policies that get stuck in deadlock or live-lock, lack full hori-245 zon planning and theoretical completeness guarantees, and in practice struggle with poor success rates and scalability.One fundamental issue with using learnt 1-step policies is 250 that it is possible for the agents' learnt policies to choose actions that lead to collisions. Figure 2 shows how two agents could choose to move into the same empty cell and lead to a collision if unchecked. Existing 1-step MAPF ML works avoid this by post-processing the outputs to check if the ac-255 tions are collision-free, and freeze agents that propose conflicting actions. GNN (Li et al. 2020b ) introduces this process as "collision shielding".Algorithm 1: Collision Shield PIBT ("CS-PIBT") Parameters: Current state s i , action probability distribution p i 1:5 for each action agent i. Note ∥p i ∥ is 5 as in 2D MAPF we have 4 movements along with waiting. p i 1:5 can be from an arbitrary learnt model. Output: Collision free actions and successor states ∀i1: procedure GETSTRICTACTIONORDERING(p i 1:5 ) 2:return action ordering sorted by decreasing p i 1:53: procedure GETSAMPLEDACTIONORDERING(p i 1:5 ) 4:return reorder action orders by p i 1:5 biased sampling without replacement 5: procedure CS-PIBT(s i , p i , ∀i ∈ [1, N ]) 6:a i 1:5 ← GetSampledActionOrdering(p i ) ∀i 7: (s 1:N new , a 1:N best ) ← PIBT(s 1:N , a 1:N 1:5 ) 8: return (s i new , a i best ) ∀iFormally, collision shielding is a function that takes in the current configuration and proposed action distribution 260 and returns the next valid configuration that avoids vertex, edge, and obstacle collisions. Li et al. (2020b) describes the following collision shielding process we term "CS-Naive". Given N agents in a joint-configuration s 1:N and actions a 1:N , we simulate (s i , a i ) → s i new and detect collisions. 265 All agents with collisions are told to wait at their current location. As the authors write themselves, this can cause deadlock if multiple agents repeatedly propose actions that lead to conflicts. Figure 2 shows an instance where collision shielding is necessary, and how two agents colliding 270 can cause other agents to be stuck in deadlock.One critical observation is that this collision checking does not take the full probability distribution of the agents' proposed actions. Specifically, we either take the chosen action or we wait, we never consider the other actions. Sup-275 pose we have two agents at different locations proposing to which agent needs to try its second action. Priority-based techniques naturally solve this question by assigning priority to agents and having the better priority agent have precedence. We thus want a single-step priority-based approach that takes in a preference of actions and returns a valid con-285 figuration. PIBT does exactly this.Concretely, instead of solely taking in the single proposed action per agent, we propose feeding the entire probability distribution into PIBT along with agent priorities. PIBT naturally resolves obstacle, vertex, and edge conflicts using agent priorities, backtracking, and the full action set. We term this use of PIBT as a collision shield for a learnt policy as "CS-PIBT". CS-PIBT will always return a valid configuration as all agents waiting is a valid collision-free option. PIBT can be decentralized (Okumura et al. 2022 ) and CS-PIBT is decentralized similarly to CS-Naive in that only colliding agents need to coordinate. We maintain the same iterative 1-step planning and execution process as before.One small detail is that PIBT does not take in an action distribution but rather a strict action ordering (e.g. which action to try 1st, 2nd, ... 5th). We can easily convert an action probability distribution to an action ordering by just preferring actions in order of highest probability. Interestingly, as discussed later in our experiments, we found that although this can significantly improve performance over CS-Naive, this strict ordering is a large bottleneck. We can get much larger performance benefits by converting our action distribution into an action ordering by biased sampling. Algorithm 1 describes CS-PIBT with the two possible variants.The previous section describes a PIBT-based "collision shield" that handles 1-step conflicts. However, using a learnt 1-step policy with this collision shield does not enable any theoretical guarantees as the 1-step policy can still get stuck in deadlock or be arbitrarily bad. Ideally, we would like to use a learnt 1-step policy in a manner that maintains theoretical solution guarantees.Section 2.2 describes in depth how normal LaCAM works. The key observation is that LaCAM requires a fast configuration generator that can satisfy lazily added constraints, and that PIBT satisfies this. We observe that a learnt local MAPF policy with CS-PIBT can be modified to be a valid configuration generator. Specifically, in order to work with LaCAM, our learnt model with collision shielding needs to handle constraints that get lazily added. Given constraints on agents, we can easily do this by invalidating proposed actions that violate constraints and having our collision shielding only consider the valid subset (the same way as is done in PIBT within regular LaCAM). Another perspective is that instead of LaCAM using PIBT informed by a normal cost-to-goal heuristic, we can use PIBT informed by the learnt local policy action distribution.Since the learnt policy in this approach only reorders action preferences, it only alters the order in which configurations are searched and does not prune out any configurations. Thus using a local 1-step learnt policy with CS-PIBT within LaCAM enables full horizon planning with the same completeness guarantee as LaCAM. Using LaCAM does require a centralized search effort wrapping over the decentralized model with CS-PIBT, but this centralized structure is significantly weaker than other MAPF methods like EECBS (Li, Ruml, and Koenig 2021) or MAPF-LNS2 (Li et al. 2022 ) which requires iterations of sequential replanning of agents. We note there currently exists no decentralized MAPF method that ensures completeness.As mentioned, one perspective of using a learnt model with CS-PIBT as a configuration generator in LaCAM is that we are using regular PIBT informed by the learnt local policy π instead of by a cost-to-goal heuristic h(s). This perspective implies that some middle ground is possible; we can use PIBT informed by both the heuristic as well as the learnt local policy. This can be done in various manners.Concretely, normal PIBT from s picks the action min a h(s ′ ) where s ′ is a successor state of s after applying a. In 2D MAPF, there are many instances where two actions are tied for the minimum, and Okumura et al. (2022) shows that tie-breaking randomly is important for good performance. On the other hand, our local policy with PIBT collision shielding picks the action max a p π (s). Note that there is a unit mismatch, i.e. heuristic values vs probabilities between the two objectives.Our first observation is that instead of tie-breaking randomly in PIBT between two equally good h(s ′ ) states, we can tie-break using the learnt policy action preferences. This bypasses the unit mismatch and we thus pick the lexicographic best action min a (h(s ′ ), 1 -p π (a)). However, this tie-breaking mechanism is not satisfactory as it only uses the learnt policy sparingly in ties. We can generalize the utility of the learnt policy by picking min a h(s′ ) + R × (1 -p π (a))where R is a hyper-parameter that fixes the unit mismatch as well as serves as a weight on how much we want to follow our policy over the heuristic.Altogether we have four possible ways of combining the local policy with a heuristic: EQUATIONEQUATIONO tie-breaking = lexmin a (h(s ′ ), 1 -p π (a)) (3) O combined (R) = min a h(s ′ ) + R × (1 -p π (a)) (4) Note, O combined (R = 0) equals O h and O combined (R → ∞) is identical to O π .(s ′ ) ∈ {h BD (s) - 1, h BD (s), h BD (s) + 1}. By definition, p π (s) ∈ [0, 1]. Thus O combined (R) with R ∈ (0, 1] is equivalent to O tie-breaking . 
experimental results: 
 We have described multiple techniques to boost the performance of a learnt local MAPF policy with heuristic search.3. What is the best way of combining a learnt policy with heuristic information?All of our techniques are agnostic to the methodology or architecture of the learnt policy. Implementing and incorporating PIBT collision shielding is straightforward given an arbitrary learnt policy as it is just a post-processing technique, so we were able to evaluate it on the state-of-the-art pre-trained MAGAT neural network. However, it is more complex to implement the LaCAM framework and we were unable to incorporate MAGAT's policy with its existing implementation. We instead trained a significantly simpler network ourselves that we were able to use within the more complex LaCAM framework. We evaluate our results on the standard random-32-32-10 map (Stern et al. 2019) The objective of this simple learnt policy is to see how our techniques can improve relatively weak models. We intentionally train a simple policy to contrast MAGAT and avoid extra hyper-parameters and hyperparameter tuning. We trained our simple policy π s similar using supervised learning. Concretely, we ran EECBS on the random-32-32-10 map for 20-200 agents and collected each state-action pair as a training example. For each agent a i with (state, action), we fed in 6 local 9x9 fields of view centered at the state. The first 9x9 was the local map (0's free space, 1 obstacle) and the 2nd 9x9 was a local backward Dijkstra's heatmap (similar to PRIMAL2) guiding a i to its goal. The other four 9x9 channels were the backward Dijkstra's heatmap of the four closest agents within the field of view, with all-zero heatmaps if not enough agents. This is fairly in line with existing work.The main changes are that our neural network is significantly smaller than all existing work (just 1 CNN layer, 2 MLP layers) and critically has no inter-agent graph neural network or communication structure. After the CNN encoding, we also add in the relative coordinates of the four closest agents within the field of view (or pad with zeros accordingly). Due to its small nature, the model we trained was PIBT) . We see that CS-PIBT dramatically improves MAGAT's success rate and scalability from under 100 agents to succeeding over 70% with the maximum number of agents in the benchmark. CS-PIBT similarly significantly boosts our simple policy π s to 200 agents while π s with CS-Naive only succeeded up to 10 agents. The last two columns also show the significant performance benefit of incorporating a learnt policy with LaCAM. Note that π s + LaCAM doubles scalability over π s with CS-PIBT and is still only driven by the simple policy and has no access to additional information. The bottom table shows the average path cost per agent over successful instances that all methods were able to solve. We finally evaluate how combining the learnt policy with h BD affects performance. Note MAGAT O tie is MAGAT with CS-PIBT with actions ordered by O tie-breaking , while the corresponding column for π s uses LaCAM with O tie-breaking . We see that combining both together leads to better costs than using just the policies themselves.unable to generalize to new maps so we just trained on the same map we tested on with a subset of agents and startgoals. As seen later on, the simple policy cannot succeed past 10 agents with CS-Naive. However, with CS-PIBT and our LaCAM framework, our policy can scale up to 200 and 400 agents respectively. This implicitly reveals how integrating heuristic search can potentially allow ML practitioners to learn simpler models (with potential computational benefits) rather than existing larger models. 4.2 Improving Scalability and Success Rate CS-PIBT Table 1 evaluates the effectiveness of the collision shield, comparing CS-Naive to CS-PIBT on MAGAT and our simple policy. All the methods were given a 60second timeout except for MAGAT which used the maximum makespan limit described in their paper. MAGAT with CS-Naive has reasonable success at 50 agents (≈ agent density 0.05) consistent with MAGAT's results, but is unable to scale to more agents. Using the same model predictions with CS-PIBT, we see that it is able to have good success rate on 450 agents (the max number of agents in that benchmark). This is an almost 10x improvement in agent density scalability with the exact same model. Likewise, our simple policy is unable to solve 50 agents, and upon inspection can only solve up to 10 agents well. With CS-PIBT, it can scale up to 200 agents (over a 10x improvement in scalability). These results convincingly demonstrate that CS-PIBT can significantly improve success rates and scalability in congestion. When visualizing the different collision shields, we noticed that CS-PIBT has two main strengths over CS-Naive.First, CS-PIBT allows robust movement when several agents are grouped up in the same area, while in CS-Naive mainly agents on the borders moved while the internal ones took longer to get out. Second, CS-PIBT allows agents to more easily go through agents resting on their goal, which was common in most failures in CS-Naive for a low number of agents and CS-PIBT at higher numbers. Both these behaviors are direct results of CS-PIBT's usage of priority inheritance and taking the full action probability distribution into account. A small but crucial detail for using CS-PIBT as discussed in the next section is that the action probability should employ randomness. One note on runtime is that the overhead of CS-PIBT is heavily dependent on the programming language and implementation of other processes. For π s , CS-PIBT was implemented in C++ and took 0.05 milliseconds per CS-PIBT call for 200 agents and had a negligible impact on overall runtime which was dominated by neural network input and inference time. However, CS-PIBT in Python for MAGAT took about 0.05 seconds per call for 200 agents which translates to 40% of total runtime.The Importance of Randomness The authors of PIBT mention how random tie-breaking plays an important part in improving performance (which we also found when testing out baseline PIBT). Interestingly, we find that employing randomness for converting the policy's action distribution into an action ordering is crucial to our CS-PIBT. Figure 3 shows the effect of using CS-PIBT using strict ordering vs sampled action ordering (see Algorithm 1) . We see that strict ordering is strictly worse than sampling and that its performance boost degrades fast as the number of agents increases.One hypothesis to explain this difference is that the model could be biased and certain actions' probabilities could consistently be higher than another, e.g. prob(up)=0.55 > prob(down)=0.45. In this case, strict ordering will always try up before down, but with biased sampling we will try up before down only 55% of the time, matching the intended distribution. However, we quantitatively analyzed the action ordering distributions induced by strict action orderings and sampled action orderings and found they had very similar distributions. Qualitatively, we observed that failure instances for CS-PIBT without sampling had many livelocks where two agents alternated back and forth between the same few states, and got stuck around obstacles. We did not notice this as often with CS-PIBT with sampling, implying that sampling helps the agent overcome local minima by trying out different actions instead of repeating the same ones.Full Horizon Planning with LaCAM Table 1 shows the result of running the same simple policy π s within the La-CAM framework. We see that LaCAM improves both the success rate and scalability over π with CS-PIBT. LaCAM's overall framework allows searching over multiple options which enables the search to overcome local minima (e.g. deadlock) and boost success rate. These results are consistent with LaCAM's original results improving PIBT's 1-step planning. We highlight how π s + LaCAM significantly improves scalability as it solves 200 agents nearly perfectly while π s with CS-PIBT has a 59% success rate, and π s by itself cannot solve 15 agents.Figure 4 explores the different methods of combining a policy with a heuristic. We compare LaCAM solution cost against MAGAT w/CS-PIBT with action preferences sorted as described in Section 3.3. Results are percent cost increases with respect to LaCAM on successful runs, thus negative values denote cost improvements. We included an additional LaCAM baseline denoted LaCAM2 which, when given two equally good h bd (s ′ ), will tie-break to avoid agent collisions, which was shown in Okumura et al. (2022) to im-550 prove cost at the expense of success rate. Note that LaCAM performs full horizon planning while all the MAGAT results are iteratively 1-step planning and executing using CS-PIBT.We observe that using just MAGAT's policy (black) leads to worse solutions than LaCAM. However tie-breaking 555 (red), which primarily uses h BD and tie-breaks using MA-GAT's predictions, leads to a consistent cost improvement of around 10%. Using O combined (R) with different R interpolates between the two behaviors, with low values of R performing better. One possible hypothesis for O tie-breaking 's 560 better performance is that MAGAT's model simply prefers to avoid 1-step collisions. However, LaCAM2's tie-breaking mechanism does exactly this but O tie-breaking is still better than LaCAM2 by about 5%, with the performance improvement increasing as the number of agents increases. This im-565 plies that MAGAT is learning something more nuanced than a simple rule to get performance benefits.We observed similar trends with our simple policy π s with respect to using O tie-breaking and O combining (R), except since π s is much simpler all costs are shifted up. 570 π s with O tie-breaking still improves cost compared to La-CAM from 1% to around 4% with larger benefits as the number of agents increases, but it is worse than LaCAM2. O combining (R) with π s showed similar interpolation behavior as with MAGAT and similarly leads to worse perfor-575 mance than O tie-breaking . (red) hBD -imperfect settings. We additionally plot MAGAT which does not use h BD and is thus independent of the heuristic imperfections. From the success rate, we see that PIBT completely fails starting at K = 10 (hidden by red triangle) and LaCAM fails at K = 20. However, the solution cost in (b) reveals a worse picture; even though LaCAM succeeds with K = 10 or 20, the solutions are extremely suboptimal with LaCAM finding 100 times worse solutions. (c) highlights that LaCAM can be extremely brittle with it performing okay at 6% but producing substantially worse solutions at 7%.One observation with Table 1 is that LaCAM serves as an extremely strong baseline. LaCAM with the backward Dijkstra's heuristic (h BD ) has perfect success rate, good cost, 580 and is extremely fast. LaCAM requires no complex training, hyper-parameters, and works on arbitrary 2D maps. All learnt MAPF works require non-trivial data collection and complex models but perform worse than LaCAM.Our solution quality results in Section 4.3 show one possible benefit of using learnt models; we can use them with heuristic search to improve path costs. In scenarios where cost is important, these 5-10% percentage improvements could be worth the complications of learning a policy. But what if small solution cost differences are not worth 590 the infrastructure required for learning a MAPF policy, and we primarily care about success rate? LaCAM seems clearly superior to existing learnt MAPF models in this case. However, one crucial assumption in 2D MAPF heuristic search methods is that we have access to an extremely strong 595 single-agent heuristic, the backward Dijkstra's heuristic. Given no inter-agent interactions, this heuristic is perfect. Figure 5 shows that PIBT and LaCAM are extremely reliant on this heuristic. We compute a "K%" imperfect heuristic hBD (s) = e × h BD (s) where e ∼ [1 -K/100, 1]. Note this 600 heuristic is still admissible. Figure 5a shows that with 10% imperfections, PIBT fails (bottom left covered by red triangle) and 5b shows LaCAM outputs extremely suboptimal to the extent of non-usable solutions. A finer manipulation into K in Figure 5c shows that LaCAM is extremely brit-605 tle to heuristic imperfections as it succeeds reasonably with K = 6 but produces highly suboptimal paths with K = 7, 8. Table 1 's PIBT and LaCAM results with h M anhattan show similar results when using a Manhattan distance heuristic. MAGAT is not reliant on h BD and outperforms PIBT and 610 LaCAM for K ≥ 7 or h M anhattan .Thus in 2D MAPF, given a perfect backward Dijkstra's heuristic, LaCAM's success rates are impressive and it seems very hard for a learnt local policy to beat it. However, in scenarios where we cannot obtain a perfect or nearlyperfect backward Dijkstra's heuristic, learnt policies have the potential to outperform heuristic search algorithms. The particular 2D MAPF scenarios where we think learnt policies may be useful are instances where h BD cannot be computed, such as in partially observable MAPF (where only part of the map is observed), or in extreme lifelong MAPF where goals are frequently changing and the overhead for computing h BD becomes prohibitively expensive.Learnt policies instead will likely excel in high dimensional state-space problems required for more realistic robot models. For example, 2D warehouse agents are constrained to move in grids at unit velocity in standard 2D MAPF formulation, but in reality, can move at angles and nonunit velocities. Realistic MAPF would then need to solve at least a 4-dimensional problem (x,y,θ,velocity). Computing a perfect backward Dijkstra's heuristic or other heuristics within 6% imperfections will likely be impossible here. Learnt MAPF policies, combined with CS-PIBT or LaCAM, would be promising in these situations. 
conclusion: 
 We showed several model-agnostic methods of improving learnt local MAPF policies with heuristic search. We first introduced CS-PIBT which is a collision shield using PIBT that takes in a policy's 1-step probability distribution and outputs valid collision-free steps. We demonstrated how this significantly improves scalability and success rate without changing the model. We then showed how we can use a learnt model with LaCAM to enable full horizon planning with theoretical completeness and in practice further boosts success and scalability. From our literature review, we have shown results for the first time where a MAPF learnt policy scales to similar agent densities (40%) of classical heuristic search methods. We hope future methods that learn local MAPF policies utilize these methods, and that more broadly, researchers work more on improving learning with heuristic search techniques. 
 
 Appendix:  


Decision: This paper has received one accept, one weak accept and one weak reject. All agree that the paper is well-written, the proposed techniques to improve current learnt local policies are interesting, and the experiments were nicely conducted. While the rebuttals answered most of the questions raised by the reviewers, one reviewer pointed out after the rebuttal that the paper assumes local policies are learnt under full observability but used with partial-observability maps. It is not clear why the size of the local inputs can be enforced to be not bigger that the observability by construction. If the local input includes information that is not observable, it seems that the learnt policy cannot be used (unless the policy was explicitly learned for partially-observable maps). The authors should clarify this point in the final version of their paper.

Reviews: review: strength_weakness: strength_weakness: The paper mostly talks about specific scenarios, so it's unclear how well the method works in settings that aren't predictable or based on grids. Because of this, it might not work as well in real life, where things aren't as controlled or expected as in the tests.

The method depends a lot on predictive methods already out there, such as PIBT and LaCAM. Even though it's new and different, this dependence could make finding new strategies for pathfinding harder.

Combining machine learning rules with heuristic search methods might make the computations more complex and time-consuming. This makes me wonder if the technique can be used in real life, especially when making a choice quickly is essential.
questions: questions: How does the method adapt to dynamic environments with high stochasticity, commonly seen in real-world applications?

How does the performance of the proposed hybrid approach compare with approaches that use solely deep reinforcement learning in MAPF scenarios?

What are the computational requirements of the proposed method, and how does it scale with the complexity and size of the environment?

Dynamic Environment Scenario: In a search and rescue operation in a disaster-struck area, the environment can change rapidly (e.g., new obstacles due to ongoing aftershocks). How would the proposed method perform in such highly dynamic and unpredictable scenarios?

Pure Deep Learning Comparison: In a complex warehouse environment with numerous autonomous robots, a pure deep reinforcement learning approach might discover novel navigation strategies not bound by the constraints of traditional heuristic methods. How does the proposed method fare against such a scenario?
strength_weakness: strength_weakness: Overall, the proposed techniques are not as much effective as the state-of-the-art LaCAM using h_BD. As shown in the experiment of Figure 5, a  possible advantage for the new techniques regards solution quality. This seems limited to 5-10% and under the assumption that only an approximation of the h_BD heuristic is available. Quality of presentation should be improved. In particular Figure 1 appears at page 1 without being referred/commented.
I am not fully convincing by the discussion in section 4.4; I would have liked to see a more detailed study on cases in which h_BD cannot be exactly computed. The paper mentions 4-dimensional problems but there is no experiment in this context supporting the claim that using of learned policies performs better than standard LaCAM. Similarly for partially-observable 2D maps.
questions: questions: The experiments considers 10% randomly sampled obstacles and 25 provided scenarios.
Do you expect similar results with lower/higher percentages of obstacles?
I also wonder how the experimental results generalise to other types of maps that are not purely random but have some structure.
In section 4.4 the paper mentions partially-observable maps as a context in which h_BD cannot be perfectly computed. Isn't the case that partially-observable maps could also affect the learnt local policies possibly making them less accurate?
strength_weakness: strength_weakness: •	Some details are not well explained or missing. 
•	Some terms are misused or used without definition.
questions: questions: Major: 
•	In Abstract: 
-	It sounds contradictory to me that classical solvers can find solutions for hundreds of agents but still struggle to scale to larger numbers of agents. Could you elaborate what applications and how many agents this paper is talking about. The two examples: exploration on Mars and warehouse management in Introduction seem not need so many agents. 
•	In Introduction: 
-	Please clarify why deadlock is a bad thing. For instance, does it affect mission planning or energy consumption? 
-	‘ML in general struggles with long-horizon planning and low-error situations’ I don't agree that ML in general struggles with long-horizon planning. Reinforcement learning models consider long-horizon planning by maximizing the Q/V values. Could you elaborate a bit? 
-	Please clarify what is a collision shield. 
-	Please clarify why you specifically chose the two heuristic methods: PIBT and LaCAM. 
-	Please clarify if the shield is generated by heuristic method instead of ML models, why it is 'smart'?
•	In Related Work: 
1)	For PIBT: What if the second-best path also didn't work? In the worst case, what if all of its solutions don't work? 
2)	For LaCAM: 
-	Please define ‘find successors lazily’ what do you mean by lazily? 
-	‘but we can do this sequentially as we encounter them rather than all at once’ Why are you sure you will encounter them later? Is it possible that in some cases, some states will never be visited? 
-	In the situation above, how can you guarantee ‘In the limit of time and memory, LaCAM explores all possible successors of JA’
-	Please clarify why did you constrain the orange agent to be in the middle in Figure 2. 
3)	For Machine Learning Approaches: 
-	What is implicit shielding? Does it mean penalty in reward signals? Please clarify. 
•	In Section 3: 
-	‘However existing learnt methods iteratively plan and execute 1-step policies that get stuck in deadlock or live-lock’ In my understanding, the agents in ML methods are trained to tackle various scenarios, including escaping from deadlock. Please elaborate why getting stuck in deadlock is a problem for ML methods. 
-	 ‘PIBT does not take in an action distribution but rather a strict action ordering’ please briefly explain why action ordering is needed, and what are the benefits of doing this. 
-	‘We note there currently exists no decentralized MAPF method that ensures completeness’ It is unclear to me how LaCAM ensures completeness. 
-	It is unclear to me what do 'action ties' and 'tie-breaking' (line 355) mean.
-	It is unclear to me how the unit mismatch is bypassed (line 365). 
-	The definition of p is inconsistent. Please make sure it's p(a) or p(s). In my understanding, the correct expression should be p(s, a=a*), meaning the probability of taking action a* under state s. Please double check and modify. 
•	In Experimental Results: 
1)	For Simple Learnt Policy: 
-	Why did you choose EECBS to generate labels? 
-	‘After the CNN encoding, we also add in the relative coordinates …’ It is unclear to me what are the inputs, and how they are fed into the network. 
2)	For Table 1: 
-	What is the difference between 0 and failure (-)? 
-	If the CS-Naive CS-PIBT did't use O_tie, which way of combining local policy and heuristics did they use?
-	Why the success rates of 400 and 300 agents are higher than that of 200 agents? And why the success rate of 400 agents is higher than that of 300 agents? 
-	From Section 3.2, I understand that LaCAM is used together with policies and CS-PIBT. But it seems here that LaCAM and CS-PIBT are used separately in Table 1. Please clarify. 
-	It is unclear to me what are the costs. 
-	Why the average costs for 100 and 450 agents are not shown? 
-	‘Note that πs + LaCAM doubles scalability over πs with CS-PIBT and is still only driven by the simple policy’ Can't see from Table 1. How could we rule out the possibility that the improvement is caused by heuristic search or LaCAM? 
3)	For Section 4.1, 4.2, and 4.3: 
-	Could you also show the time consumption for each step? 
-	 ‘In this case, strict ordering will always try up before down, but with biased sampling we will try up before down only 55% of the time, matching the intended distribution.’ I'm really not sure about this part. If the model is trained to behave like this, it means going up can avoid collisions. Usually we add noise in action selection only in training, not in execution. Maybe adding noise in action selection can find better actions sometimes (when the model is not well trained), but will it also increase the probability of collision?  
-	It is not clear to me why CS-PIBT: Tie and CS-PIBT: R1.5 are worse than LaCAM in Figure 4. 
4)	For Section 4.4: this section is interesting, and I enjoyed reading this part. 
-	‘we can use them with heuristic search to improve path costs.’ I understand heuristic methods find solutions by minimizing a cost function, how can ML models further improve the path costs? 
-	It is unclear what is imperfect heuristic and how it is defined (line 600). 



Manor: 
•	In Introduction: 
-	Figure 1 is not ever referenced. 
-	‘Showing a neural-network agnostic’ Why the hyphen? 
•	In Section 3: 
-	 ‘works avoid this’ is a typo. 
-	‘for each action agent i’ is a typo. 
-	‘by assigning priority to agents’ I see you explained this part in the experiments, but it is better to briefly mention how you assign the priorities here as well. 
-	The value of hyper parameter R is defined too late. 
-	‘when R approaches to infinity, O_combine is identical to O_\pi’ I don’t agree with this statement. It is not rigorous to define importance of terms using infinity. 
•	In Experimental Results: 
1)	For Section 4.1, 4.2, and 4.3: 
-	‘prob(down)=0.45’ please use proper notation. 
-	Please define ‘percent cost increases’.