Publications
Publications › References ›
2026
Journal papers
Coverage with Self-Induced Obstacles on Grids
[FPM26]
Sarah Frenkel, David Parker and Masoumeh Mansouri.
Coverage with Self-Induced Obstacles on Grids.
IEEE Robotics and Automation Letters (RA-L), 11(3), pages 3454-3461.
March 2026.
pdf bib
- Downloads
PDF 867 KB
BibTeX
- Search for this paper
- Google · Google Scholar
Abstract
Modelling environments as grids is a common approach in robotics, particularly for coverage path planning
tasks, where the goal is to fully traverse an area or visit key
points. In this paper, we introduce a new variant of coverage
planning, inspired by applications such as open-pit mining,
harvesting, and painting, where the robot’s own actions modify
the environment. Specifically, self-induced obstacles arise as a
result of task execution, e.g. piles of rubble from drilling, and
must be avoided in all future motion planning. We formally model
these constraints by assuming that once a vertex is visited, it
becomes non-traversable, and define an obstacle as self-induced
if its existence depends on the set of previously visited vertices.
This situation has not been addressed in existing formulations,
which assume static obstacle placement. We provide a formal
analysis of how the existence of solutions is affected by geometric
constraints, such as vertex distances and robot turning radius,
as defined by the Dubins vehicle. We also propose modelling the
problem using self-deleting graphs based on the line graph of
the grid. This provides a sufficient representation that captures
the problem’s dynamics and enables the use of general graph
search algorithms. Our experimental evaluation demonstrates
that our approach outperforms classical coverage path