Boustrophedon decomposition

One approach to the coverage problem is to decompose ${\cal C}_{free}$ into cells and perform boustrophedon (from the Greek ``ox turning'') motions in each cell as shown in Figure 7.35 [222]. It is assumed that the robot is a point in ${\cal W}= {\mathbb{R}}^2$, but it carries a tool of thickness $\epsilon$ that hangs evenly over the sides of the robot. This enables it to paint or mow part of ${\cal C}_{free}$ up to distance $\epsilon/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.

Figure 7.35: An example of the ox plowing motions.

If ${\cal C}_{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 would cause unnecessary repositioning of the robot. A similar method, which furthermore optimizes the number of robot turns, is presented in [468].

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.