Minimising Revisits in Dubins-Constrained Grid Coverage

[FPM26b] Sarah Frenkel, David Parker and Masoumeh Mansouri. Minimising Revisits in Dubins-Constrained Grid Coverage. In Proc. IEEE 22nd International Conference on Automation Science and Engineering (CASE'26). To appear. August 2026. pdf bib

Downloads
PDF 1.56 MBBibTeX
Search for this paper
Google · Google Scholar

Abstract

We study Dubins-constrained coverage on grids in applications where visiting a cell triggers an irreversible local action, such as painting or drilling. In these settings, re- entering treated cells destroys the initial action and is therefore undesirable, even if doing so would shorten the overall path. However, the motion constraints of a Dubins vehicle force entries into neighbouring cells during turns or when connecting distant regions. We refer to entries into previously treated cells as revisits. Motivated by this, we define the Dubins Coverage with Minimal Revisits (DCMR) problem: find a trajectory that covers every cell while minimising the number of revisits. We derive theoretical bounds on the number of revisits and boundary violations, and complement these results with a configurable solver supporting various decomposition and coverage pattern choices. We then experimentally evaluate how these choices affect the number of revisits and boundary violations.