Multi-robot Exploration and Coverage: Entropy-based Adaptive Maps with Adjacency Control Laws

Abstract

Prior works have sought to improve exploration-coverage algorithms by developing multi-agent control techniques that either account for the states of neighboring agents, or utilize information-theoretic concepts to explore regions of high information content. In addition, variably-sized grid maps have been investigated to reduce computational expense. However, to the authors' knowledge, these three aspects have not been effectively harnessed together. In this paper, we present a multi-agent exploration and coverage mission which uses an entropy grid to effectively guide agents to explore and cover regions of high uncertainty, while also adaptively re-sizing and discretizing the grid world representation in real time. The adaptive grid presented is an improvement over constant-sized grids due to lower memory and processing requirements while still containing comparable information content. The entropy grid, when combined with adjacency-based control, allows the multi-agent system to effectively explore and cover environments that have time-varying target densities. The effectiveness of our approach is demonstrated through a real-time simulation with 75 agents.