Optimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning
Preprint
Abstract
In this paper, we tackle the problem of planning an optimal coverage path for a robot operating indoors. Many existing approaches attempt to discourage turns in the path by covering the environment along the least number of coverage lines, i.e., straight-line paths. This is because turning not only slows down the robot but also negatively affects the quality of coverage, e.g., tools like cameras and cleaning attachments commonly have poor performance around turns. The problem of minimizing coverage lines however is typically solved using heuristics that do not guarantee optimality. In this work, we propose a turn-minimizing coverage planning method that computes the optimal number of axis-parallel (horizontal/vertical) coverage lines for the environment in polynomial time. We do this by formulating a linear program (LP) that optimally partitions the environment into axis-parallel ranks (non-intersecting rectangles of width equal to the tool width). We then generate coverage paths for a set of real-world indoor environments and compare the results with state-of-the-art coverage approaches.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Online coverage and inspection planning for 3D modelingAutonomous Robots, 2020
- Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robotAutomation in Construction, 2020
- GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman ProblemComputers & Operations Research, 2017
- Coverage path planning with unmanned aerial vehicles for 3D terrain reconstructionExpert Systems with Applications, 2016
- A survey on coverage path planning for roboticsRobotics and Autonomous Systems, 2013
- Integral Boundary Points of Convex Polyhedra2009
- On the representability of totally unimodular matrices on bidirected graphsDiscrete Mathematics, 2009
- Spanning-tree based coverage of continuous areas by a mobile robotAnnals of Mathematics and Artificial Intelligence, 2001
- Path Planning and Guidance Techniques for an Autonomous Mobile Cleaning Robot1995
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984