Spanning-tree based coverage for a tethered robot

Tethered robots find widespread application in underwater and disaster recovery missions. This study focuses on the coverage path planning (CPP) problem for a tethered robot, considering cable constraints and the presence of forbidden areas in the environment. We propose adapting the spanning tree-...

Full description

Saved in:
Bibliographic Details
Published in:IEEE robotics and automation letters 2025-02, Vol.10 (2), p.1-8
Main Authors: Peng, Xiao, Schwarzentruber, Francois, Simonin, Olivier, Solnon, Christine
Format: Article
Language:English
Subjects:
Cables
Complexity theory
Computational Complexity
Coverage Path Planning
Integer linear programming
Mobile robots
Object recognition
Path planning
Polynomials
Robots
Shape
Solids
Tethered Robot
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Tethered robots find widespread application in underwater and disaster recovery missions. This study focuses on the coverage path planning (CPP) problem for a tethered robot, considering cable constraints and the presence of forbidden areas in the environment. We propose adapting the spanning tree- based coverage algorithm to address CPP. Theoretical complexity analysis reveals NP-completeness in cases involving forbidden areas. We show how to solve CPP by searching for a tree in a configuration graph, and how to reduce the size of this graph to compute approximate solutions faster. We introduce Integer Linear Programming (ILP) models corresponding to these approximations and experimentally compare them on various instances.
ISSN:2377-3766
2377-3766
DOI:10.1109/LRA.2025.3526564