Robot-Size Aware Coverage Path Planning

Abstract

Coverage Path Planning (CPP) algorithms are fundamental for autonomous robot applications including inspection, surveillance, and cleaning. While existing CPP algorithms achieve good theoretical coverage, they treat robots as point agents, ignoring physical dimensions, turning radius constraints, and safety clearances. This simplification produces paths that are theoretically complete but physically infeasible for real robots. We propose a robot-size aware CPP framework that explicitly parameterizes robot geometry relative to grid cell resolution, enabling adaptive planning for robots of different sizes. Our approach modifies two representative CPP algorithms—Spanning Tree Coverage (STC) and Boustrophedon Cell Decomposition (BCD)—to incorporate geometric constraints. Experimental results on 17 diverse test maps show that baseline algorithms generate paths with 1400–1900 turns assuming point robots, while our size-aware variants reduce turns by 6–12% and correctly identify 10% of cenarios as infeasible, preventing deployment failures. Size-aware algorithms achieve 96.5% coverage on executable paths while eliminating all width constraint violations (Fwidth=1.0). The framework enables practical deployment on physical platforms and efficient coordination of heterogeneous robot teams.