MRSimEx-DSTC: A Dynamic Spanning Tree Coverage Approach for Multi-Robot Exploration and Coverage Path Planning

Abstract

This paper presents MRSimEx-DSTC, a decentralized and adaptive framework for multi-robot coverage path planning in unknown and dynamic environments. The proposed method integrates frontier-based exploration with Dynamic Spanning Tree Coverage (DSTC), allowing each robot to incrementally map the environment while dynamically replanning its coverage path in response to both static and moving obstacles detected via onboard LiDAR. To enable decentralized execution and prevent task redundancy, the workspace is partitioned using Manhattan-distance-based Voronoi decomposition, ensuring disjoint task allocation and collision-free parallel operation without centralized coordination. The framework is validated through simulations in Python and Gazebo across varying obstacle densities and robot–obstacle speed scenarios. Experimental results show that MRSimEx-DSTC achieves high coverage efficiency (up to 99.5%), minimal overlap, and robust real-time adaptability. Compared to state-of-the-art methods such as MR-SimExCoverage and MAC-Planner, the proposed approach demonstrates superior performance, lower planning overhead, and greater resilience under real-world constraints.