Coverage Planning
Imagine automating the motion of a lawnmower for an estate that has many obsta- cles, such as a house, trees, garage, and a complicated property boundary. What are the best zig-zag motions for the lawnmower? Can the amount of redundant traversals be minimized? Can the number of times the lawnmower needs to be stopped and rotated be minimized? This is one example of coverage planning, which is motivated by applications such as lawn mowing, automated farming, painting, vacuum cleaning, and mine sweeping. A survey of this area appears in
[217]. Even for a region in = R2, finding an optimal-length solution to coverage planning is NP-hard, by reduction to the closely related Traveling Salesman Prob-
W
lem [36, 709]. Therefore, we are willing to tolerate approximate or even heuristic solutions to the general coverage problem, even in R2.
Boustrophedon decomposition One approach to the coverage problem is to decompose free into cells and perform boustrophedon (from the Greek “ox turn-
C
ing”) motions in each cell as shown in Figure 7.35 [222]. It is assumed that the robot is a point in W = R2, but it carries a tool of thickness ǫ that hangs evenly
over the sides of the robot. This enables it to paint or mow part of free up to distance ǫ/2 from either side of the robot as it moves forward. Such motions are often used in printers to reduce the number of carriage returns.
C
If obs is polygonal, a reasonable decomposition can be obtained by adapting the vertical decomposition method of Section 6.2.2. In that algorithm, critical events were defined for several cases, some of which are not relevant for the boustrophedon motions. The only events that need to be handled are shown in Figure 7.36a [216]. This produces a decomposition that has fewer cells, as shown in Figure 7.36b. Even though the cells are nonconvex, they can always be sliced nicely into vertical strips, which makes them suitable for boustrophedon motions. The original vertical decomposition could also be used, but the extra cell boundaries
C
- COVERAGE PLANNING 355
Figure 7.35: An example of the ox plowing motions.
- (b)
Figure 7.36: (a) Only the first case from Figure 6.2 is needed: extend upward and downward. All other cases are neglected. (b) The resulting decomposition is shown, which has fewer cells than that of the vertical decomposition in Figure 6.3.
would cause unnecessary repositioning of the robot. A similar method, which furthermore optimizes the number of robot turns, is presented in [468].
Spanning tree covering An interesting approximate method was developed by Gabriely and Rimon; it places a tiling of squares inside of free and computes the spanning tree of the resulting connectivity graph [372, 373]. Suppose again
C
that Cfree is polygonal. Consider the example shown in Figure 7.37a. The first
step is to tile the interior of free with squares, as shown in Figure 7.37b. Each square should be of width ǫ, for some constant ǫ > 0. Next, construct a roadmap by placing a vertex in the center of each square and by defining an edge that connects the centers of each pair of adjacent cubes. The next step is to compute a spanning tree of . This is a connected subgraph that has no cycles and touches every vertex of ; it can be computed in O(n) time, if has n edges [683]. There are many possible spanning trees, and a criterion can be defined and optimized to
C
G
G G
G
induce preferences. One possible spanning tree is shown Figure 7.37c.
Once the spanning tree is made, the robot path is obtained by starting at a
- (b)
(c) (d)
Figure 7.37: (a) An example used for spanning tree covering. (b) The first step is to tile the interior with squares. (c) The spanning tree of a roadmap formed from grid adjacencies. (d) The resulting coverage path.
Figure 7.38: A circular path is made by doubling the resolution and following the perimeter of the spanning tree.
point near the spanning tree and following along its perimeter. This path can be precisely specified as shown in Figure 7.38. Double the resolution of the tiling, and form the corresponding roadmap. Part of the roadmap corresponds to the spanning tree, but also included is a loop path that surrounds the spanning tree. This path visits the centers of the new squares. The resulting path for the example of Figure 7.37a is shown in Figure 7.37d. In general, the method yields an optimal route, once the approximation is given. A bound on the uncovered area due to approximation is given in [372]. Versions of the method that do not require an initial map are also given in [372, 373]; this involves reasoning about information spaces, which are covered in Chapter 11.