Distributed Online Rollout for Multivehicle Routing in Unmapped Environments

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 the locations of tasks and other agents. Moreover, our agents possess strictly local communication and sensing capabilities (restricted to a fixed radius), aligning more closely with several real-world multiagent applications. We present a fully distributed, online, and scalable reinforcement learning algorithm for this problem whereby agents self-organize into local clusters to which they independently apply a multiagent rollout scheme. 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 in practice. Our decentralized reinforcement learning algorithm achieves approximately a factor of two cost improvement over the base policy for a range of radii between two and three times the critical sensing radius. In addition, we observe in simulations that our distributed algorithm requires exponentially fewer computational resources than the centralized approach, at only a small constant factor detriment in cost. We validate our algorithm through physical robot experiments in continuous space and show that the resulting behavior reflects the discrete simulations.