![[2507.16874] Budget Allocation Policies for Real-Time Multi-Agent Path Finding](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2507.16874] Budget Allocation Policies for Real-Time Multi-Agent Path Finding
Summary
This article presents a study on budget allocation policies for real-time multi-agent path finding (RT-MAPF), focusing on improving efficiency in robotics applications by intelligently distributing planning budgets among agents.
Why It Matters
The research addresses a critical gap in real-time multi-agent path finding, which is essential for practical robotics applications. By optimizing budget allocation, the findings can enhance the performance of robotic systems in dynamic environments, making them more effective in real-world scenarios.
Key Takeaways
- Real-time multi-agent path finding (RT-MAPF) requires efficient planning under time constraints.
- Existing methods often fail due to ineffective shared budget allocation among agents.
- Intelligent distribution of planning budgets leads to better problem-solving in challenging scenarios.
- The study explores various budget allocation policies to optimize agent performance.
- Findings can significantly impact robotics applications like automated warehouses and drone swarms.
Computer Science > Multiagent Systems arXiv:2507.16874 (cs) [Submitted on 22 Jul 2025 (v1), last revised 23 Feb 2026 (this version, v2)] Title:Budget Allocation Policies for Real-Time Multi-Agent Path Finding Authors:Raz Beck, Roni Stern View a PDF of the paper titled Budget Allocation Policies for Real-Time Multi-Agent Path Finding, by Raz Beck and Roni Stern View PDF HTML (experimental) Abstract:Multi-Agent Path finding (MAPF) is the problem of finding paths for a set of agents such that each agent reaches its desired destination while avoiding collisions with the other agents. This problem arises in many robotics applications, such as automated warehouses and swarms of drones. Many MAPF solvers are designed to run offline, that is, first generate paths for all agents and then execute them. In real-world scenarios, waiting for a complete solution before allowing any robot to move is often impractical. Real-time MAPF (RT-MAPF) captures this setting by assuming that agents must begin execution after a fixed planning period, referred to as the planning budget, and execute a fixed number of actions, referred to as the execution window. This results in an iterative process in which a short plan is executed, while the next execution window is planned concurrently. Existing solutions to RT-MAPF iteratively call windowed versions of MAPF algorithms in every planning period, without explicitly considering the size of the planning budget. We address this gap and explore different ...