TLDR: This research paper introduces novel budget allocation policies for Real-Time Multi-Agent Path Finding (RT-MAPF), a problem where multiple agents must plan their movements within strict time constraints. The authors propose methods like the ‘Fixed budget allocation policy’ for Prioritized Planning (PrP) and the ‘ConflictProportion’ policy for MAPF-LNS2, which intelligently distribute computational resources among agents. Experimental results show that these budget-aware policies, particularly ConflictProportion, significantly improve problem-solving efficiency and reduce makespan compared to traditional shared budget approaches, especially when combined with fast algorithms like PIBT.
Multi-Agent Path Finding (MAPF) is a fundamental challenge in robotics and artificial intelligence, involving the coordination of multiple agents to reach their destinations without colliding. While many MAPF solutions are designed for offline use, where paths are fully generated before execution, real-time applications demand a different approach. This is where Real-Time MAPF (RT-MAPF) comes into play, requiring agents to plan and execute their movements simultaneously within strict time limits, known as the planning budget.
The core issue in RT-MAPF is how to effectively manage this planning budget. Traditional methods often involve running windowed versions of MAPF algorithms, but they don’t explicitly consider the size of the available budget. This can lead to inefficiencies, especially in complex situations where a planner might exhaust its budget trying to solve a difficult path for one agent, leaving others stranded.
This research addresses this critical gap by exploring various policies for allocating the planning budget within standard MAPF algorithms, specifically Prioritized Planning (PrP) and MAPF-LNS2. The authors highlight that a common baseline approach, where all agents draw from a shared budget pool, proves ineffective in highly constrained environments. Instead, policies that distribute the planning budget among agents demonstrate a superior ability to solve more problems with a shorter makespan (the time it takes for all agents to reach their targets).
For Prioritized Planning (PrP), the paper introduces a ‘Fixed budget allocation policy’. This policy involves splitting the budget evenly among agents. If an agent fails to find a path within its allocated budget, the system moves on to the next agent, ensuring that resources aren’t wasted on a single, intractable problem. This approach allows easier-to-solve agents to still find their paths, leading to more useful partial solutions. Any unused budget can then be redistributed to agents that haven’t yet planned.
For MAPF-LNS2, a more advanced algorithm, the researchers explored two types of budget allocation policies: neighborhood budget policies and intra-neighborhood budget policies. The ‘Shared neighborhood budget policy’ (the baseline) allocates all available budget to the current group of agents being planned for. However, the paper proposes a more effective non-parametric policy called ‘ConflictProportion’. This innovative policy allocates budget to a neighborhood of agents proportionally to the number of conflicts those agents are involved in, ensuring that more problematic areas receive adequate attention. This method also includes a lower bound to ensure a minimum budget for any neighborhood, preventing situations where the allocated budget is too small to be effective.
The experimental results, conducted on various standard MAPF benchmark grids, clearly demonstrate the advantages of these proposed budget allocation policies. For MAPF-LNS2, the neighborhood budget policies, particularly ConflictProportion, consistently yielded much better results than the baseline shared policy, especially as the number of agents increased. The research also shows that combining PIBT (Priority Inherence Backtracking), an extremely fast MAPF algorithm, with MAPF-LNS2 and the ConflictProportion policy, often leads to superior performance, leveraging the complementary strengths of both algorithms.
Also Read:
- Enhancing Multi-Agent Pathfinding Efficiency with New Flex Distribution Strategies
- Navigating the Future: How Deep Reinforcement Learning is Reshaping Autonomous Path Planning
In conclusion, this paper underscores the importance of intelligently allocating planning budgets in Real-Time MAPF. The proposed methods, especially the ConflictProportion policy, significantly improve the efficiency and success rate of multi-agent navigation in time-constrained environments. This work paves the way for future research into adaptive online learning mechanisms for budget allocation and the application of these policies in lifelong MAPF settings. You can read the full research paper for more technical details at arXiv:2507.16874.
