The Minimal Sum of Altitudes Decomposition for Coverage Algorithms

Wesley H. Huang
Rensselaer Polytechnic Institute, Department of Computer Science
Technical Report 00-3, June 2000.
[pdf]

Abstract

The coverage problem in the field of robotics is the problem of moving a sensor or actuator over all points in a given region. Example applications of this problem are lawn mowing, spray painting, and aerial or underwater mapping. In this paper, I consider the single-robot offline version of this problem, i.e. given a map of the region to be covered, plan an efficient path for a single robot that sweeps the sensor or actuator over all points.

One basic approach to this problem is to decompose the region into subregions, select a sequence of those subregions, and then generate a path that covers each subregion in turn. This paper addresses the problem of creating a good decomposition. Under certain assumptions, the cost to cover a polygonal subregion is proportional to its minimum altitude. An optimal decomposition then minimizes the sum of subregion altitudes.

This paper describes an algorithm to find the minimal sum of altitudes (MSA) decomposition of a region with a polygonal boundary and polygonal holes. This algorithm creates an initial decomposition based upon multiple line sweeps and then applies dynamic programming to find the optimal decomposition. This paper describes the algorithm and reports results from an implementation. Several appendices give details and proofs regarding line sweep algorithms.

BibTeX entry

@TechReport{Huang00c,
  author = 	 {Wesley H. Huang},
  title = 	 {The Minimal Sum of Altitudes Decomposition for Coverage Algorithms},
  institution =  {Rensselaer Polytechnic Institute Department of Computer Science},
  year = 	 2000,
  number =	 3,
  month =	 {June}
}