# Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning

arXiv: https://arxiv.org/abs/2105.01225 · HTML: https://mlsanity.com/paper/2105.01225/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 61 references that are in the map.
- First posted on arXiv 4 May 2021.

## Builds on (most cited first, 9 of 9)

- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Robust Finite-State Controllers for Uncertain POMDPs](https://mlsanity.com/paper/2009.11459/) (2020)
- [Qualitative Controller Synthesis for Consumption Markov Decision Processes](https://mlsanity.com/paper/2005.07227/) (2020)
- [Percentile Queries in Multi-Dimensional Markov Decision Processes](https://mlsanity.com/paper/1410.4801/) (2014)
- [Algorithms for Routing of Unmanned Aerial Vehicles with Mobile Recharging Stations](https://mlsanity.com/paper/1704.00079/) (2017)
- [Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time](https://mlsanity.com/paper/1901.03615/) (2019)
- [Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem](https://mlsanity.com/paper/1508.05968/) (2015)
- [Multi-UAV Routing for Persistent Intelligence Surveillance & Reconnaissance Missions](https://mlsanity.com/paper/1702.08494/) (2017)
- [POMDPs under Probabilistic Semantics](https://mlsanity.com/paper/1408.2058/) (2014)

## Abstract (arXiv)

We study the problem of minimizing the resource capacity of autonomous agents cooperating to achieve a shared task. More specifically, we consider high-level planning for a team of homogeneous agents that operate under resource constraints in stochastic environments and share a common goal: given a set of target locations, ensure that each location will be visited infinitely often by some agent almost surely. We formalize the dynamics of agents by consumption Markov decision processes. In a consumption Markov decision process, the agent has a resource of limited capacity. Each action of the agent may consume some amount of the resource. To avoid exhaustion, the agent can replenish its resource to full capacity in designated reload states. The resource capacity restricts the capabilities of the agent. The objective is to assign target locations to agents, and each agent is only responsible for visiting the assigned subset of target locations repeatedly. Moreover, the assignment must ensure that the agents can carry out their tasks with minimal resource capacity. We reduce the problem of finding target assignments for a team of agents with the lowest possible capacity to an equivalent graph-theoretical problem. We develop an algorithm that solves this graph problem in time that is polynomial in the number of agents, target locations, and size of the consumption Markov decision process. We demonstrate the applicability and scalability of the algorithm in a scenario where hundreds of unmanned underwater vehicles monitor hundreds of locations in environments with stochastic ocean currents.