Optimal Partitioning of Non-Convex Environments for Minimum Turn Coverage Planning
- 18 July 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Robotics and Automation Letters
- Vol. 7 (4) , 9731-9738
Abstract
In this letter, 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
Funding Information
- Canadian Mitacs Accelerate (IT16435)
- Avidbots Corp., Kitchener, ON, Canada
This publication has 28 references indexed in Scilit:
- Mapping, Planning, and Sample Detection Strategies for Autonomous ExplorationJournal of Field Robotics, 2013
- A survey on coverage path planning for roboticsRobotics and Autonomous Systems, 2013
- Intelligent Coverage Path Planning for Agricultural Robots and Autonomous Machines on Three-Dimensional TerrainJournal of Intelligent & Robotic Systems, 2013
- Optimal Coverage Path Planning for Arable Farming on 2D SurfacesTransactions of the ASABE, 2010
- Integral Boundary Points of Convex Polyhedra2009
- On the representability of totally unimodular matrices on bidirected graphsDiscrete Mathematics, 2009
- Optimal Covering Tours with Turn CostsSIAM Journal on Computing, 2005
- Coverage Path Planning: The Boustrophedon Cellular Decomposition1998
- Path planning and guidance techniques for an autonomous mobile cleaning robotRobotics and Autonomous Systems, 1995
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984