On minimizing turns in robot coverage path planning
- 17 November 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1237-1242
Abstract
In this paper we study sweep coverage path planning, in which a robot must cover all points in a workspace with its footprint. In many coverage applications, including cleaning and monitoring, it is beneficial to use coverage paths with minimal robot turns. To address this, we provide an efficient method to compute the minimum altitude of a non-convex polygonal region, which captures the number of parallel line segments, and thus turns, needed to cover the region. Then, given a non-convex polygon, we provide a method to cut the polygon into two pieces that minimizes the sum of their altitudes. Given an initial convex decomposition of a workspace, we apply this method to iteratively re-optimize and delete cuts of the decomposition. Finally, we compute a coverage path of the workspace by placing parallel line segments in each region, and then computing a tour of the segments of minimum cost. We present simulation results on several workspaces with obstacles, which demonstrate improvements in both the number of turns in the final coverage path and runtime.Keywords
This publication has 20 references indexed in Scilit:
- Efficient complete coverage of a known arbitrary environment with applications to aerial operationsAutonomous Robots, 2013
- An Optimized Field Coverage Planning Approach for Navigation of Agricultural Robots in Fields Involving Obstacle AreasInternational Journal of Advanced Robotic Systems, 2013
- BA*: an online complete coverage algorithm for cleaning robotsApplied Intelligence, 2012
- On the Dubins Traveling Salesman ProblemIEEE Transactions on Automatic Control, 2011
- Coverage path planning algorithms for agricultural field machinesJournal of Field Robotics, 2009
- Uniform Coverage of Automotive Surface PatchesThe International Journal of Robotics Research, 2005
- Path Planning for Robotic Demining: Robust Sensor-Based Coverage of Unstructured Environments and Probabilistic MethodsThe International Journal of Robotics Research, 2003
- Approximation algorithms for lawn mowing and milling☆☆A preliminary version of this paper was entitled “The lawnmower problem” and appears in the Proc. 5th Canad. Conf. Comput. Geom., Waterloo, Canada, 1993, pp. 461–466.Computational Geometry, 2000
- An effective implementation of the Lin–Kernighan traveling salesman heuristicEuropean Journal of Operational Research, 2000
- The power of non-rectilinear holes1982