 |
Complexity of coverage path planning problems for tethered robots in nonconvex environments
1 : CITI Centre of Innovation in Telecommunications and Integration of services
Institut National des Sciences Appliquées de Lyon
2 : CITI Centre of Innovation in Telecommunications and Integration of services
(CITI)
INRIA, Institut National des Sciences Appliquées [INSA] - Lyon : EA3720
CITI Laboratory, INSA Lyon Domaine Scientifique de la Doua Batiment Claude Chappe 6 avenue des Arts 69621 Villeurbanne Cedex Phone +33 4 7243 6415 Fax +33 4 7243 6227 E-Mail citi@insa-lyon.fr -
France
3 : Institut national des sciences appliquées de Lyon
(INSA Lyon)
Institut National des Sciences Appliquées (INSA) - Lyon, Institut National des Sciences Appliquées [INSA] - Lyon
The tethered robots are widely applied in the underwater and disaster recovery missions. In this work, we study the coverage path planning problem for tethered robot, when adding two constraints related to the cable: a limit on the cable length and the presence of forbidden areas in the environment. We propose to adapt the spanning tree coverage based algorithm to approximately solve this new problem. An algorithm based on Dijkstra algorithm is introduced to compute in polynomial time an approximate solution that satisfies the cable length constraint. We also prove that the problem becomes NP-complete in case of forbidden areas by a reduction form planar 3-SAT.
