Minimising revisits in Dubins-constrained grid coverage

Conference item

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, reentering 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.

Authors: Frenkel, S; Parker, D; Mansouri, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Acceptance date: 2026-05-27
• Event title: IEEE 22nd International Conference on Automation Science and Engineering (CASE 2026)
• Event location: Shenyang, China
• Event website: https://2026.ieeecase.org/
• Event start date: 2026-08-17
• Event end date: 2026-08-21
• Language: English