Online Multi-Robot Coverage Path Planning in Dynamic Environments Through Pheromone-Based Reinforcement Learning

摘要

Two promising approaches to coverage path planning are reward-based and pheromone-based methods. Reward-based methods allow heuristics to be learned automatically, often yielding a superior performance to hand-crafted rules. On the other hand, pheromone-based methods leverage stimgergy to achieve superior generalization and adaptation in unknown or nonstationary environments. To obtain the best of both worlds, we introduce Greedy Entropy Maximization (GEM), a hybrid approach that aims to maximize the entropy of a pheromone deposited by a swarm of homogeneous ant-like agents. We begin by establishing a sharp upper-bound on achievable entropy and show that this corresponds to optimal dynamic coverage path planning. Next, we demonstrate that GEM closely approaches this upper-bound despite depriving agents of typical necessities such as memory and explicit communication. Finally, we show that GEM can be executed asynchronously in constant-time through distillation into a shallow neural network, making our approach highly scalable.