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

🌈 Abstract

The article discusses Adaptive Delay-based Destroy-and-Repair Enhanced with Success-based Self-Learning (ADDRESS), a simplified variant of the state-of-the-art anytime Multi-Agent Path Finding (MAPF) approach called MAPF-LNS. The key points are:

• MAPF-LNS uses an adaptive selection mechanism to choose among multiple destroy heuristics, but this requires considerable exploration time. The performance bottleneck caused by the non-adaptive destroy heuristics cannot be overcome by the adaptive selection alone.

• ADDRESS applies restricted Thompson Sampling to the top-k set of the most delayed agents to select a seed agent for adaptive LNS neighborhood generation. This overcomes the limitations of the original agent-based destroy heuristic.

• Experiments show that ADDRESS can achieve cost improvements of at least 50% in large-scale scenarios with up to a thousand agents, compared to the original MAPF-LNS and other state-of-the-art methods.

🙋 Q&A

[01] Adaptive Delay-Based Destroy-and-Repair Enhanced with Success-based Self-Learning (ADDRESS)

1. What is the key idea behind the ADDRESS heuristic? The key idea of the ADDRESS heuristic is to use restricted Thompson Sampling to select a seed agent from the top-k set of the most delayed agents for the LNS neighborhood generation. This overcomes the limitations of the original agent-based destroy heuristic used in MAPF-LNS.

2. How does the ADDRESS heuristic work? The ADDRESS heuristic first sorts all agents by their delays to determine the top-k set of the most delayed agents. It then applies restricted Thompson Sampling to the parameters (success and failure counters) of the agents in the top-k set to select a seed agent. An LNS neighborhood is then generated via random walks, adding agents whose paths are crossed by the random walk.

3. How does the ADDRESS heuristic improve upon the original agent-based destroy heuristic? The original agent-based destroy heuristic greedily selects the agent with the maximum delay as the seed agent, which can be time-consuming in large-scale scenarios as it requires iterating through all agents. In contrast, the ADDRESS heuristic uses Thompson Sampling to efficiently select a seed agent from the top-k set of the most delayed agents, overcoming the performance bottleneck of the original heuristic.

4. What are the key components that enable the effectiveness of the ADDRESS heuristic? The key components are:

• Restricting the seed agent selection to the top-k set of the most delayed agents to ease exploration
• Using Thompson Sampling to adaptively select the seed agent based on the success and failure counters, which represent the potential of each agent to improve the solution

[02] Experiment Results

1. How does ADDRESS perform compared to the original MAPF-LNS and other state-of-the-art methods? The experiments show that ADDRESS significantly outperforms the original MAPF-LNS, MAPF-LNS2, BALANCE, and LaCAM* in large-scale scenarios with up to a thousand agents. ADDRESS achieves cost improvements of at least 50% compared to these state-of-the-art methods.

2. How does the choice of k (size of the top-k set) affect the performance of ADDRESS? The experiments show that both ADDRESS variants with Thompson Sampling and ε-Greedy perform best when k = 10. Thompson Sampling is more robust to the choice of k compared to ε-Greedy.

3. How does the search progress of ADDRESS compare to the original agent-based heuristic in MAPF-LNS? The results demonstrate that both ADDRESS variants with Thompson Sampling and ε-Greedy consistently outperform the original agent-based heuristic in MAPF-LNS in terms of solution cost and cost improvement speed (lower AUC values).

4. How does the performance of ADDRESS compare to MAPF-LNS with the ADDRESS heuristic included as one of the destroy heuristics? The results show that the standalone ADDRESS outperforms the MAPF-LNS variant that includes the ADDRESS heuristic along with the other non-adaptive destroy heuristics. This is because ADDRESS can focus its runtime on optimizing the seed agent selection without spending time on less effective destroy heuristics.