Adaptive Spanning Tree-Based Coverage Path Planning for Autonomous Mobile Robots in Dynamic Environments

Abstract

In this study, a unique approach is presented to improve autonomous robots’ path planning abilities, especially in dynamic environments. We propose a Dynamic Spanning Tree Coverage (D-STC) algorithm designed to handle both stationary and moving obstacles using a depth-first search (DFS) methodology. The workspace is partitioned into cells, and a spanning tree guides the robot’s motion to ensure full coverage while dynamically avoiding obstacles detected using onboard LIDAR sensors. The effectiveness of D-STC was evaluated across three dynamic scenarios based on relative speeds of the robot and obstacles. Simulation results show that the proposed method achieves a coverage efficiency of up to 98.25% when the robot is faster, with a minimal overlap rate of 3.06% and only 412 steps required to cover a workspace of 20×20 grid. Even in more challenging scenarios with faster-moving obstacles, D-STC maintains robust performance with 96.52% coverage and 11.2% overlap. These results demonstrate that the proposed approach significantly enhances coverage quality, reduces redundancy, and adapts effectively to dynamic environments, making it suitable for real-world applications such as surveillance, cleaning, and agricultural robotics.