Multi-Robot Exploration and Line Coverage in Unknown Environments

Abstract

This paper studies online multi-robot exploration and line coverage in unknown environments, where robots must explore the environment and service features without prior topology knowledge. The main challenge is that the feature graph is revealed incrementally, causing routing structure and workload allocation to update during execution. To address this, we propose an iterative hierarchical cyclic merging regulation (iHCMR). iHCMR is a coupled exploration-coverage framework that constructs the feature graph from local sensing, generates local exploration and servicing trajectories, and replans coverage tasks as new features are discovered. iHCMR preserves Morse-bounded tours throughout graph discovery, enabling newly detected features to be integrated without introducing coverage discontinuities. We prove coverage completeness and bounded competitiveness relative to the offline optimum. Simulations show improved workload balance and reduced makespan, compared with the graph-based and greedy online strategies.