# Distributed Online Rollout for Multivehicle Routing in Unmapped Environments

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 49 references that are in the map.
- First posted on arXiv 24 May 2023.

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

- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Multiagent Rollout and Policy Iteration for POMDP with Application to Multi-Robot Repair Problems](https://mlsanity.com/paper/2011.04222/) (2020)
- [Planning for Decentralized Control of Multiple Robots Under Uncertainty](https://mlsanity.com/paper/1402.2871/) (2014)
- [Active Self-Assembly of Algorithmic Shapes and Patterns in Polylogarithmic Time](https://mlsanity.com/paper/1301.2626/) (2013)

## Built on by (most cited first, 2 of 2)

- [Model Predictive Control and Reinforcement Learning: A Unified Framework Based on Dynamic Programming](https://mlsanity.com/paper/2406.00592/) (2024)
- [An Approximate Dynamic Programming Framework for Occlusion-Robust Multi-Object Tracking](https://mlsanity.com/paper/2405.15137/) (2024)

## Abstract (arXiv)

In this work we consider a generalization of the well-known multivehicle routing problem: given a network, a set of agents occupying a subset of its nodes, and a set of tasks, we seek a minimum cost sequence of movements subject to the constraint that each task is visited by some agent at least once. The classical version of this problem assumes a central computational server that observes the entire state of the system perfectly and directs individual agents according to a centralized control scheme. In contrast, we assume that there is no centralized server and that each agent is an individual processor with no a priori knowledge of the underlying network (including task and agent locations). Moreover, our agents possess strictly local communication and sensing capabilities (restricted to a fixed radius around their respective locations), aligning more closely with several real-world multiagent applications. These restrictions introduce many challenges that are overcome through local information sharing and direct coordination between agents. We present a fully distributed, online, and scalable reinforcement learning algorithm for this problem whereby agents self-organize into local clusters and independently apply a multiagent rollout scheme locally to each cluster. We demonstrate empirically via extensive simulations that there exists a critical sensing radius beyond which the distributed rollout algorithm begins to improve over a greedy base policy. This critical sensing radius grows proportionally to the log^* function of the size of the network, and is, therefore, a small constant for any relevant network. Our decentralized reinforcement learning algorithm achieves approximately a factor of two cost improvement over the base policy for a range of radii bounded from below and above by two and three times the critical sensing radius, respectively.