C*: A Coverage Path Planning Algorithm for Unknown Environments using Rapidly Covering Graphs

This article presents a novel sample-based algorithm, called C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula>, for real-time coverage path planning (CPP) of unknown environments. C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> is built upon the concept of a rapidly covering graph (RCG), which is incrementally constructed during robot navigation via progressive sampling of the search space. By using efficient sampling and pruning techniques, the RCG is constructed to be a minimum-sufficient graph, where its nodes and edges form the potential waypoints and segments of the coverage trajectory, respectively. The RCG tracks the coverage progress, generates the coverage trajectory, and helps the robot escape from the dead-end situations. To minimize coverage time, C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> produces the desired back-and-forth coverage pattern, while adapting to the traveling salesman problem-based optimal coverage of local isolated regions, called coverage holes, which are surrounded by obstacles and covered regions. It is analytically proven that C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> provides complete coverage of unknown environments. The algorithmic simplicity and low computational complexity of C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> make it easy to implement and suitable for real-time on-board applications. The performance of C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> is validated by, first, extensive high-fidelity simulations and, second, laboratory experiments using an autonomous robot. C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> yields near optimal trajectories, and a comparative evaluation with seven existing CPP methods demonstrates significant improvements in performance in terms of coverage time, number of turns, trajectory length, and overlap ratio, while preventing the formation of coverage holes. Finally, C<inline-formula><tex-math notation="LaTeX">$^{*}$</tex-math></inline-formula> is comparatively evaluated on two different CPP applications using, first, energy-constrained robots and, second, multirobot teams.