Cell Decompositions and Coverage

Carving the free space into cells simple enough to sweep — the trapezoidal decomposition by a vertical sweep with Choset's four event types, the boustrophedon and Morse decompositions whose walls sit only at critical points, Euler's count and the coverage path-length bound, sensor-based coverage with the cycle algorithm and an incrementally built Reeb graph, and pursuit–evasion as a decomposition by information.

The problem: Rusty mows the living room

Room C of the Apartment, furnished for this chapter with a sofa against the north wall and a coffee table, is the free space of disc-Rusty: the room shrunk by Rusty's radius, the furniture grown by it (Chapter 4's inflation). Rusty's effector — the brush — is its own diameter, $2r = 0.44$ m. Put it down in the south-west corner of the room and ask it to cover the room twice, from the same start, knowing nothing about the room but what its range ring tells it.

The raster scan looked done. Every lap it drove was a full lap, every turn was neat, and the algorithm terminated by its own rule — no unexplored openings in the cell it thought it was covering. But it never followed the bottom of the sofa at the moment the sofa ended, so it never learned that the free space split there; the strip behind the sofa was another cell, and nothing told the robot it existed. That is Choset Fig. 6.22 in a living room, and the rest of the chapter is the machinery that makes the failure impossible: cells, the points where cells begin and end, how to sense those points, and a motion pattern that cannot walk past one.

Building intuition

Cells, walls, and a graph

The cells have to be "simple" in a specific sense: something a robot can cover without thinking. A cell bounded left and right by vertical segments and above and below by obstacle boundary — a floor and a ceiling that never double back in $x$ — is covered by vertical laps one effector width apart, stepping over along the floor or ceiling between laps. That is the boustrophedon ("ox-turning") pattern of a plough, and it is why every decomposition in this chapter is built by sweeping a vertical line.

Where the walls go: the trapezoidal sweep

The chapter's micro-world — the bench — is a convex quadrilateral plot $B = (0, 0.2), (10, 0), (10.4, 6), (0.3, 6.2)$ with a triangle $T = (2,2), (4,1.5), (3,4)$ and a quadrilateral $K = (6,1), (8,0.8), (8.6,4), (6.5,4.4)$; its eleven vertex abscissae are distinct. A vertical line sweeps it from left to right and stops only at vertices. Between stops nothing can happen: the edges the line crosses stay in the same vertical order, and the free intervals between them only stretch or shrink. The widget's strip is that ordered list, $L$. At a stop, the two edges meeting at the vertex are inserted into $L$, deleted from it, or one replaces the other — Choset's four event types — and the vertex shoots a vertical extension up to the next edge of $L$ above it and down to the next below, if free space lies there.

Watch the totals. The eleven vertices do not produce twenty-two extensions; they produce thirteen, because most vertices have obstacle on one side. The pass-through vertices — $(0.3, 6.2)$ on the plot's upper chain, $T$'s top $(3,4)$, $K$'s $(6.5, 4.4)$, $(8, 0.8)$, and the plot's corner $(10, 0)$ — each get one. The leftmost and rightmost vertices of $T$ and $K$ get two. The plot's own leftmost and rightmost vertices get none. Cells: twelve trapezoids (some degenerate into triangles), and the adjacency graph has thirteen edges, one per extension.

Fewer walls: the boustrophedon decomposition

Now keep only the extensions that go both up and down. There are four — at the leftmost and rightmost points of $T$ and of $K$ — and with the slice's birth at $(0, 0.2)$ and death at $(10.4, 6)$ they are the six places where the free part of the sweep line changes its number of pieces: one interval, then two (above and below $T$), then one, two (around $K$), one, none. Merge the trapezoids that the other extensions separated and you have seven cells. The Reeb graph docked beside the canvas is the dual picture: a node per critical point, an edge per cell. Six nodes, seven edges, two holes:

and the widget re-prints it live while you drag any vertex — Euler's count is a theorem, not a coincidence of this world.

Then Rusty mows. With a $0.5$ m effector, the first cell (from $x = 0$ to the triangle's tip at $x = 2$) takes $\lceil 2/0.5 \rceil = 4$ laps. From a start at $(1.5, 3)$ the boustrophedon mower finishes the bench in $158.4$ m; switch to the trapezoidal decomposition and the same mower needs $174.4$ m — one more lap and $14$ m more of transits, because twelve cells mean twelve entries and twelve exits. In the living room the gap is wider: $45.9$ m against $79.1$ m, because the octagonal corners of Rusty's C-obstacles shatter the room into 29 trapezoids. More cells is not finer coverage; it is more turnarounds.

Six slices, one definition

Nothing in the boustrophedon decomposition depends on the slices being vertical lines. Sweep circles out from a centre, or diamonds, or rays, or the fronts of a brushfire, and the same rule — a cell wall wherever the swept slice splits or merges — gives a different decomposition and a different pattern of laps (Choset Figs. 6.12–6.18). The gallery computes all six on the bench by one raster algorithm.

Two things in the gallery are worth a second look. The spiral's circles touch the outer wall many times, yet not every touch is a critical point: the first touch turns a closed circle into an arc — one piece before, one piece after — and connectivity is what Definition 6.2.1 counts. And the brushfire decomposition is a tree, not a graph with a loop per obstacle: its slices are fronts around each obstacle, so each obstacle is itself a critical set where a cell is born, and Euler's count takes a different form (Derivation 5).

The mathematics

Cell decompositions by sweeping

How many trapezoids? Each event opens new cells: a vertex with extensions both ways (a split) closes one cell and opens two; a vertex where two edges leave and free space lies between them (a birth) opens one; a pass-through closes one and opens one; a vertex where two edges arrive with obstacle between (a merge) closes two and opens one; a vertex where two edges arrive with free space between (a death) only closes. Counting cells opened per vertex gives

For a convex $m$-gon boundary with convex $k_i$-gon holes, each hole has one split and no death and the boundary has one death and no split, so the count is $(m - 1) + \sum_i (k_i + 1)$ — on the bench, $3 + 4 + 5 = 12$. The surprise is that the closed form survives non-convexity: $\#\text{split} - \#\text{death} = N_{ob} - 1$ for every polygonal free space in general position (Exercise 1 proves it from Euler's count), so

which the check confirms on 200 convex and 100 star-shaped seeded worlds — 69 of the latter have a notch tip that opens or closes a slice — and which gives the living room's $28 + 2 - 1 = 29$ and the Workbench top's $16 + 3 - 1 = 18$.

Morse decompositions

Sensing a critical point

Choset's observation (§6.2.4) is that a critical point can be felt. A robot following an obstacle boundary at standoff $\delta$ knows the direction to the nearest obstacle point — its range ring's shortest ray — and that direction is $-\nabla D$, the negative of the distance gradient (Chapter 7, Derivation 2). The boundary normal is $\nabla m \parallel \nabla D$ there. So the rank condition of Derivation 3 becomes one angle comparison.

The Reeb graph and Euler's count

The complexity of coverage

How much can a lawnmower miss? Inside a cell with floor $f(x)$ and ceiling $c(x)$, the laps sit at most $r$ apart horizontally from every point, so a point $(x, y)$ escapes its nearest lap at $x_j$ only if $y < f(x_j)$ or $y > c(x_j)$ — a sliver under a dip of the floor or over a bump of the ceiling, of height at most the variation of $f$ or $c$ between $x_j$ and $x$. Integrating over the half-gaps gives a bound that is not in Choset, and that the check holds the mower to:

with $\mathrm{TV}$ the total vertical variation of a chain. On the bench it is $6.150$ m², and the mower misses $0.67$ m² (98.7 % covered on a 3 cm raster) — all of it under the slanted edges of the plot and of $T$ and $K$. In the rectilinear living room the bound is $2.350$ m² and the mower misses almost nothing ($99.87$ %, the octagonal corners of the furniture). The online coverer, which follows both floor and ceiling of every gap, covers $100.0$ % in all three worlds.

Coda: decomposing by information — pursuit and evasion

The last decomposition in Choset Chapter 6 is carved by visibility, not by a sweep, and it is a workspace problem: the pursuers and the evader are points in $\W_{free}$, not configurations of a robot (C Problem 7).

Crossing from one conservative region to another changes the gaps in one of four ways, and the labels follow (Choset §6.3): a gap edge disappears — do nothing; a gap edge appears — label it 0, since what it now hides was just visible; gap edges merge — the new label is the OR of the old; a gap edge splits — the pieces inherit its label. The information graph $G_i$ has a node per (conservative region, label vector) and an edge per transition the rules allow; a pursuer strategy is a path in $G_i$ to any node whose labels are all zero.

The port computes $V(x)$ by an angular sweep — one exact ray through every vertex and one a hair to either side — and the check compares it with 1 800 brute-force rays at each of 24 random points in three worlds: the largest disagreement is below $10^{-13}$ m. Contamination is kept on an $12.5$ cm raster: what the pursuers see is cleared, and contamination then floods every hidden pixel connected to a contaminated one, because the evader is arbitrarily fast. The four transition rules are not coded; they emerge from the flood, and the gap labels are read off it. The conservative regions are computed by grouping pixels by which polygon vertices they cannot see (plus, with a static pursuer, the corners of its view) — a refinement of Choset's regions, since $B(x)$ cannot change while that set is fixed — and labels are carried across a region boundary by overlap: a shadow on the far side is contaminated iff it overlaps a contaminated shadow on the near side. Breadth-first search on the resulting $G_i$ finds a strategy for the two-pocket world after 286 information states, and the replay through the flood leaves nothing contaminated. In the three-pocket world it exhausts all 693 reachable states without an all-zero node — one pursuer cannot do it — while a second pursuer parked at the hub (the static pursuer of Step 1) brings a solution after 2 480 states, which the replay confirms. The naive patrol the widget shows instead — visit each pocket's far leg in turn — leaves 10.25 m² contaminated: every pocket it clears is recontaminated through the hub while it clears the next.

The algorithm

Implementation in Rust

The cells crate is introduced here. Its spine is a decomposition — cells with floor and ceiling chains, and the adjacency graph as a petgraph graph whose edges carry the shared wall — and every algorithm above produces or consumes one.

use nalgebra::Point2;
use petgraph::graph::UnGraph;

/// A planar polygonal free space: Choset §6.1's standing assumption. For disc-Rusty the
/// polygons are Chapter 4 C-obstacles; for Reach's pad they are the Workbench's objects.
#[derive(Clone, Debug)]
pub struct PolyWorld {
    pub boundary: Vec<Point2<f64>>,       // counter-clockwise
    pub obstacles: Vec<Vec<Point2<f64>>>, // holes, counter-clockwise, disjoint
}

/// The wall two adjacent cells share: a vertical extension from an event vertex.
#[derive(Clone, Copy, Debug)]
pub struct Boundary {
    pub segment: (Point2<f64>, Point2<f64>),
}

/// A cell: everything between a floor chain and a ceiling chain over an x-interval.
/// Trapezoids have two-point chains; boustrophedon cells bend at pass-through vertices.
#[derive(Clone, Debug)]
pub struct Cell {
    pub floor: Vec<Point2<f64>>,
    pub ceiling: Vec<Point2<f64>>,
    pub x_range: (f64, f64),
}

pub struct Decomposition {
    pub cells: Vec<Cell>,
    pub adjacency: UnGraph<usize, Boundary>,
}

impl Decomposition {
    /// Faces of the planar adjacency graph by Euler, f = 2 − V + E: the holes plus the outside.
    pub fn euler_faces(&self) -> i64 {
        2 - self.adjacency.node_count() as i64 + self.adjacency.edge_count() as i64
    }
}

impl PolyWorld {
    /// Choset assumes distinct vertex abscissae; a rectilinear room violates that on every wall.
    /// The shear x ← x + σy keeps edges straight and polygons simple, and moves nothing by more
    /// than σ·height — a few millimetres in a room of the Apartment.
    pub fn in_general_position(mut self) -> Self {
        const SIGMA: f64 = 1.0e-3 * std::f64::consts::SQRT_2;
        let mut xs: Vec<f64> = self.vertices().map(|p| p.x).collect();
        xs.sort_by(f64::total_cmp);
        if xs.windows(2).all(|w| w[1] - w[0] > 1e-7) {
            return self;
        }
        for p in self.vertices_mut() {
            p.x += SIGMA * p.y;
        }
        self
    }
}

The sweep keeps $L$ as a vector sorted by height at the current abscissa — the bookkeeping is easier to read than a tree keyed by a moving comparator, and the event logic is the same. The interesting part is the match, which is Choset Fig. 6.4.

use std::collections::HashMap;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum EventKind { BothRight, BothLeft, LowerLeftUpperRight, LowerRightUpperLeft }

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Rule { Trapezoidal, Boustrophedon }

pub fn sweep(world: &PolyWorld, rule: Rule) -> Decomposition {
    let edges = world.edges();
    let mut events: Vec<Vertex> = world.vertex_list();
    events.sort_by(|a, b| a.p.x.total_cmp(&b.p.x));
    assert!(events.windows(2).all(|w| w[1].p.x > w[0].p.x), "general position: distinct x");

    let mut l: Vec<usize> = Vec::new();                     // crossed edges, bottom to top
    let mut open: HashMap<usize, OpenCell> = HashMap::new(); // open cells keyed by floor edge
    let mut out = Builder::new(rule);

    for v in &events {
        let (e_prev, e_next) = world.incident_edges(v);
        let rest: Vec<usize> = l.iter().copied().filter(|&e| e != e_prev && e != e_next).collect();
        // e_LOWER and e_UPPER: one search at v's height, because every update happens there.
        let i = rest.partition_point(|&e| edges[e].y_at(v.p.x) < v.p.y);
        let (lo, up) = (i.checked_sub(1).map(|j| rest[j]), rest.get(i).copied());
        let (free_up, free_down) = world.free_vertical(v); // the extensions that exist
        match world.event_kind(v) {
            EventKind::BothRight => {
                let (a, b) = world.order_rightward(v, e_prev, e_next); // lower edge first
                l = [&rest[..i], &[a, b], &rest[i..]].concat();
                if free_up && free_down {
                    // Split: the slice interval (lo, up) is cut by the new obstacle.
                    let c = open.remove(&lo.unwrap()).unwrap();
                    out.close(c, v.p.x);
                    out.open_two(&mut open, (lo.unwrap(), a), (b, up.unwrap()), v, true);
                } else {
                    out.open(&mut open, a, b, v); // birth: free space starts between a and b
                }
            }
            EventKind::BothLeft => {
                let (a, b) = world.order_leftward(v, e_prev, e_next);
                l = rest;
                if free_up && free_down {
                    let (below, above) = (open.remove(&lo.unwrap()).unwrap(), open.remove(&b).unwrap());
                    out.merge(below, above, &mut open, lo.unwrap(), up.unwrap(), v); // merge
                } else {
                    out.close(open.remove(&a).unwrap(), v.p.x); // death
                }
            }
            _ => {
                // One edge leaves the line, the other arrives in its slot.
                let (leaving, arriving) = world.left_right(v, e_prev, e_next);
                for e in l.iter_mut() {
                    if *e == leaving { *e = arriving; }
                }
                let floor_side = free_up; // v lies on the floor of the cell above it
                out.pass_through(&mut open, v, leaving, arriving, floor_side, lo, rule);
            }
        }
    }
    out.finish()
}

The Morse layer adds the slice function and the Reeb graph. For $h = x$ the boustrophedon decomposition is the sweep with Rule::Boustrophedon; the trait is there so that the variable slices of §6.2.3 share one interface (the raster construction behind the gallery implements it for the curved ones).

use nalgebra::{Point2, Vector2};
use petgraph::graph::UnGraph;

pub trait SliceFn {
    fn h(&self, q: Point2<f64>) -> f64;
    fn grad_h(&self, q: Point2<f64>) -> Vector2<f64>;
}
pub struct Vertical;
impl SliceFn for Vertical {
    fn h(&self, q: Point2<f64>) -> f64 { q.x }
    fn grad_h(&self, _: Point2<f64>) -> Vector2<f64> { Vector2::x() }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Kind { Birth, Split, Merge, Death }

#[derive(Clone, Copy, Debug)]
pub struct CriticalPoint { pub q: Point2<f64>, pub kind: Kind }

/// Nodes are critical points, edges are cells (the dual of the adjacency graph).
pub struct ReebGraph { pub graph: UnGraph<CriticalPoint, usize> }

impl ReebGraph {
    /// Euler's count for a boustrophedon decomposition: e = v + N_ob − 1.
    pub fn euler_check(&self, n_obstacles: usize) -> bool {
        self.graph.edge_count() + 1 == self.graph.node_count() + n_obstacles
    }

    /// χ(Q_free) from Chapter 8's Morse count with boundary: births (index 0) and merges
    /// (index 1) are the boundary critical points where ∇h points into the free space.
    pub fn morse_chi(&self) -> i64 {
        self.graph.node_weights().map(|c| match c.kind {
            Kind::Birth => 1,
            Kind::Merge => -1,
            Kind::Split | Kind::Death => 0,
        }).sum()
    }
}

pub fn boustrophedon(world: &PolyWorld) -> (Decomposition, ReebGraph) {
    let d = sweep(world, Rule::Boustrophedon);
    let reeb = ReebGraph::from_cells(&d); // one node per critical event, one edge per cell
    (d, reeb)
}

Coverage: the exhaustive walk is a DFS, the laps are a closed-form set of abscissae, and the transits are Chapter 6's A* on the trapezoids.

pub struct CoveragePath {
    pub points: Vec<Point2<f64>>,
    pub laps: usize,
    pub lap_len: f64, pub boundary_len: f64, pub transit_len: f64,
}

/// ⌈width/2r⌉ laps, the outer ones r inside the cell's ends: every point of the cell is
/// within r of a lap horizontally, which is what the missed-area bound needs.
pub fn lap_xs(x_l: f64, x_r: f64, two_r: f64) -> Vec<f64> {
    let n = ((x_r - x_l) / two_r - 1e-9).ceil().max(1.0) as usize;
    if n == 1 { return vec![0.5 * (x_l + x_r)]; }
    let r = 0.5 * two_r;
    let step = (x_r - x_l - two_r) / (n - 1) as f64;
    (0..n).map(|k| x_l + r + k as f64 * step).collect()
}

pub fn coverage_path(d: &Decomposition, world: &PolyWorld, two_r: f64, start: Point2<f64>) -> CoveragePath {
    let trapezoids = sweep(world, Rule::Trapezoidal); // convex: safe transits (Derivation 2)
    let order = dfs_first_visits(&d.adjacency, d.locate(start).unwrap_or(0));
    let mut path = PathBuilder::at(start);
    for c in order {
        let cell = &d.cells[c];
        let xs = lap_xs(cell.x_range.0, cell.x_range.1, two_r);
        let pattern = Lawnmower::new(cell, &xs).entered_nearest(path.here());
        path.transit(&trapezoids, pattern.first()); // A* + midpoint–centroid chaining
        path.extend(pattern);
    }
    path.finish()
}

/// Δ²/2r + 4ΔN_ce + 5P_total — Choset §6.2.5.
pub fn bound(world: &PolyWorld, two_r: f64, n_cells: usize) -> f64 {
    let delta = world.min_enclosing_circle().radius * 2.0;
    delta * delta / two_r + 4.0 * delta * n_cells as f64 + 5.0 * world.total_perimeter()
}

The online coverer is a state machine around Chapter 3's follower. Its tick advances one motion primitive and returns the phase, so the widget and a test harness drive the same code.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Phase { Forward, Reverse, Closing, Backtrack, Done }

pub struct Coverer<'r> {
    pub robot: &'r mut sim::Rusty,
    pub reeb: ReebGraph,
    pub two_r: f64,
    pub phase: Phase,
    gap_start: Point2<f64>,   // where the current gap's first lap began
    far_end: Point2<f64>,     // the previous lap's other end, T_k
    best_progress: f64,       // max x-progress along the current follow
}

impl Coverer<'_> {
    /// One step of the cycle algorithm. Critical points come from the range ring alone.
    pub fn tick(&mut self, scan: &bugs::RangeScan, dt: f64) -> Phase {
        let progress = self.sweep_dir() * (self.robot.pose().x - self.gap_start.x);
        self.best_progress = self.best_progress.max(progress);
        // Derivation 4: the boundary turned back ⇔ the tangent went vertical ⇔ the minimum
        // ray was parallel to the sweep. Classify by where that ray points.
        if self.following() && progress < self.best_progress - 0.3 * self.standoff() {
            let g = scan.gradient();                        // ∇D = −(minimum ray)
            let convex = g.x * self.moving_dir() > 0.3;
            let node = self.reeb.add_or_match(self.robot.position(), self.classify(convex));
            self.close_cell(node);
            self.phase = Phase::Backtrack;                  // DFS picks the next unexplored edge
            return self.phase;
        }
        self.phase = match self.phase {
            Phase::Forward if progress >= self.two_r => { self.lap_to_other_side(); Phase::Reverse }
            Phase::Reverse if progress <= 0.0 => {
                if (self.robot.position() - self.far_end).norm() > self.close_tol() {
                    self.lap_toward(self.far_end);          // an obstacle lies between: find why
                    Phase::Closing
                } else {
                    self.undo_reverse();                    // retrace, then the next gap
                    Phase::Forward
                }
            }
            Phase::Backtrack => self.travel_to_next_unexplored(),
            p => { self.robot.follow_boundary(dt); p }
        };
        self.phase
    }
}

Pursuit is short once visibility is exact: a polygon from rays, and a BFS whose transitions carry labels by overlap.

pub fn visibility_polygon(world: &PolyWorld, x: Point2<f64>) -> Vec<Point2<f64>> {
    const EPS: f64 = 1e-5;
    let mut bearings: Vec<f64> = world.vertices()
        .flat_map(|v| { let a = (v.y - x.y).atan2(v.x - x.x); [a - EPS, a, a + EPS] })
        .collect();
    bearings.sort_by(f64::total_cmp);
    bearings.into_iter().map(|a| x + world.ray_cast(x, a) * Vector2::new(a.cos(), a.sin())).collect()
}

pub struct InfoState { pub cell: usize, pub labels: Vec<u8> }

/// BFS on G_i from (start region, all ones) to any all-zero node — Choset Fig. 6.39.
pub fn clear(world: &PolyWorld, start: Point2<f64>, static_pursuer: Option<Point2<f64>>) -> Option<Vec<usize>> {
    let regions = conservative_regions(world, static_pursuer);
    let s0 = InfoState { cell: regions.locate(start)?, labels: regions.all_contaminated(start) };
    bfs(s0, |s| regions.crossings(s.cell).map(|t| t.carry(&s.labels)), |s| s.labels.iter().all(|&b| b == 0))
}

The worked example, and its printed output

fn main() {
    let bench = PolyWorld::bench(); // B, T, K of the §3 micro-example
    let t = sweep(&bench, Rule::Trapezoidal);
    println!("trapezoidal: {} cells, {} adjacency edges, euler faces = {}",
             t.cells.len(), t.adjacency.edge_count(), t.euler_faces());
    let (b, reeb) = boustrophedon(&bench);
    println!("boustrophedon: {} critical points, {} cells, reeb nodes = {}, reeb edges = {}, euler_check = {}",
             reeb.graph.node_count(), b.cells.len(), reeb.graph.node_count(),
             reeb.graph.edge_count(), reeb.euler_check(bench.obstacles.len()));
    println!("morse chi = {}", reeb.morse_chi());
    println!("laps in cell 0 at 2r = 0.5: {}", lap_xs(0.0, 2.0, 0.5).len());
}

#[test]
fn workbench_counts_match_text() {
    let bench = PolyWorld::bench();
    let t = sweep(&bench, Rule::Trapezoidal);
    assert_eq!((t.cells.len(), t.adjacency.edge_count(), t.euler_faces()), (12, 13, 3));
    let (b, reeb) = boustrophedon(&bench);
    assert_eq!((reeb.graph.node_count(), b.cells.len()), (6, 7));
    assert!(reeb.euler_check(2));
    assert_eq!(lap_xs(0.0, 2.0, 0.5), vec![0.25, 0.75, 1.25, 1.75]);
}

trapezoidal: 12 cells, 13 adjacency edges, euler faces = 3
boustrophedon: 6 critical points, 7 cells, reeb nodes = 6, reeb edges = 7, euler_check = true
morse chi = -1
laps in cell 0 at 2r = 0.5: 4

fn main() {
    let room = PolyWorld::living_room().in_general_position(); // Room C, sofa and coffee table
    let (d, _) = boustrophedon(&room);
    let start = Point2::new(9.0, 0.8);
    let off = coverage_path(&d, &room, 0.44, start);
    println!("offline: length {:.2} m, covered {:.2} %", off.length(), 100.0 * covered(&room, &off.points, 0.22, 0.03));
    for policy in [Policy::Cycle, Policy::Raster] {
        let run = Coverer::run(&room, start, 0.44, policy);
        println!("{policy:?}: length {:.2} m, covered {:.2} %, {} critical points, bound {:.1} m",
                 run.length(), 100.0 * covered(&room, &run.points, 0.22, 0.03),
                 run.reeb.graph.node_count(), bound(&room, 0.44, run.reeb.graph.edge_count()));
    }
}

offline: length 45.86 m, covered 99.87 %
Cycle: length 85.74 m, covered 100.00 %, 6 critical points, bound 308.9 m
Raster: length 21.70 m, covered 79.66 %, 2 critical points, bound 191.3 m

two pockets (20 edges), 1 pursuer: cleared after 286 information states
three pockets (28 edges), 1 pursuer: no all-zero node in 693 states
three pockets (28 edges), 2 pursuers (one static at the hub): cleared after 2480 states

The tests pin all of these: workbench_counts_match_text as above; euler_holds_on_random_worlds asserts $N_{ce} = N_{cp} + N_{ob} - 1$ and $V + N_{ob} - 1$ trapezoids on 300 seeded worlds; coverage_is_complete asserts covered == 100 % at a 3 cm raster and length <= bound for the cycle algorithm in the living room, on the Workbench top and on the bench. Every number above is reproduced by the TypeScript port that runs this page, and the chapter's checks hold it to the printed digits.

Putting it together: three free spaces, three mowers

The integration lab covers three free spaces three ways: offline (the map is known: sweep, walk, mow), online with the cycle algorithm (the map is unknown: sense, mow, build the Reeb graph), and online with a conventional raster scan. The living room is mowed by disc-Rusty with its own diameter as effector; the Workbench top is wiped by Reach's end-effector pad, 20 cm wide, around the block, the post and the shelf (reachability is ignored here — Chapter 4 maps it); the bench is the §3 micro-world.

Three things to read off the table. Knowing the map is worth a factor of 1.5 to 1.9 in length: the cycle algorithm follows both boundaries of every gap and retraces its reverse follows, drives a closing lap through every split and merge, and travels between cells over ground it has already covered rather than along the shortest route. Not knowing it costs nothing in coverage — the cycle algorithm is the only method at 100 % everywhere, because it follows both the floor and the ceiling of every gap, while the offline lawnmower misses the slivers the missed-area bound allows. A raster scan's failure is not a constant: on the Workbench its lucky phase finds the merges that matter and it misses 0.05 %; in the living room it misses a fifth of the room. A method whose completeness depends on the phase of its laps is not complete.

Part II closes here, and its scorecard is worth stating. Every planner in Chapters 6–10 is complete — it finds a path when one exists and says so when none does — and most are exact: the visibility graph, the GVD, Canny's roadmap, the cell decompositions represent $\Qfree$ without approximation. The price is dimension. A trapezoidal sweep is $O(n \log n)$ in the plane; Canny's roadmap is singly exponential in the dimension of $\Q$; the decompositions of this chapter have no practical analogue for Reach's six-joint cousins. Chapter 11 gives the guarantee up for a probabilistic one and gets the dimension back: it will measure its roadmaps against exactly the kind of decomposition built here, on spaces small enough for both. Chapter 14 reuses the adjacency graph as the discrete layer of task planning, and the sister book's exploration chapter replaces the coverage of a known-to-be-there space with the coverage of an unknown one under a belief — frontiers instead of critical points.

Exercises

1. Foundation exerciseFDifficulty 2 of 3Counting trapezoids, convex or not

   (a) Derive the trapezoid count $(m - 1) + \sum_i (k_i + 1)$ for a convex $m$-gon boundary with convex $k_i$-gon holes in general position, by counting the cells each vertex opens. (b) Now notch $K$: replace it by $(6, 1), (8.6, 0.8), (7.3, 2.4), (8.8, 4), (6.5, 4.4)$, whose vertex $(7.3, 2.4)$ is reflex and is the tip of a notch opening to the right. Classify every vertex of the notched $K$ (split, merge, birth, death, pass) and count again. (c) Prove the general rule: trapezoids $= V + \#\text{split} - \#\text{death}$, and $\#\text{split} - \#\text{death} = N_{ob} - 1$ for every polygonal free space in general position, so the count is always $V + N_{ob} - 1$ — reflex vertices do not break it.

   How many trapezoids does the bench have with the notched K (five vertices)? (The sweep in this chapter's code agrees with your count.)

   Check Reveal

   Stuck? Get a hint
2. Foundation exerciseFDifficulty 2 of 3Where a critical point can sit

   Prove that a critical point cannot lie in the interior of a slice interval (Choset §6.2.2): at an interior point the slice meets $\Qfree$ on both sides. Then, for the squarel $h = |x| + |y|$, show that a corner of the diamond $\{h = \lambda\}$ touching an obstacle vertex is a critical point exactly when the obstacle's normal cone at that vertex meets the convex hull of the normals of the two flat sides meeting at the corner (C §6.2.3) — the generalized-gradient condition of Chapter 9.

   Stuck? Get a hint
3. Conceptual exerciseCDifficulty 1 of 3Predict, then drag
   Predict first

   In the Boustrophedon Mower (bench), drag the triangle's top vertex from (3, 4) down to (3, 1.6), just below the chord from (2, 2) to (4, 1.5). Before releasing: what happens to the two cell counts, trapezoidal 12 and boustrophedon 7?

   Trapezoidal drops to 11, boustrophedon stays 7

   Both unchanged: 12 and 7

   Boustrophedon rises to 8, because (3, 1.6) becomes critical
4. Conceptual exerciseCDifficulty 2 of 3Three pockets, one pursuer
   Predict first

   In the Pursuit-Evasion widget, pick three pockets with one pursuer. The search exhausts G_i without an all-zero node. Which statement explains why no strategy exists?

   The pockets are too deep to see into from the hub

   While the pursuer clears one pocket, the hub is unwatched and the third pocket recontaminates the one already cleared

   One pursuer can never clear a polygon with more than 20 edges
5. Practical exercisePDifficulty 2 of 3Spiral and squarel critical points on polygons

   Implement Radial and Squarel slice functions for polygons in morse.rs: the critical points of $|q - c|$ restricted to an edge are its endpoints and the foot of the perpendicular from $c$ (if inside the edge); for $|x - c_x| + |y - c_y|$, the endpoints and the points where the edge crosses $x = c_x$ or $y = c_y$. Keep only the candidates where the free slice's number of intervals changes (a circle first touching the outer wall does not count), build the Reeb graph by sweeping $\lambda$, and assert Euler's count. Render Choset Figs. 6.12 and 6.14 for the bench with $c = (5, 3)$ and compare your counts with the gallery's raster ones (12 and 15 critical points at 8 cm pixels).

6. Practical exercisePDifficulty 3 of 3The brushfire decomposition, end to end

   Build the brushfire decomposition (C §6.2.3) from Chapter 7's brushfire and Chapter 8's GVD: cells are born at each obstacle, and change where fronts first collide — at saddles of $D$ on the GVD (C Fig. 6.16). Cover each cell by following the obstacle boundary at increasing offsets $D = r, 3r, 5r, \dots$ with Chapter 3's offset follower, switching to the GVD where the robot becomes doubly equidistant (C Fig. 6.17). Assert that the Reeb graph is a tree with $N_{ce} = N_{cp} - 1$, and compare the path length with the boustrophedon mower's on the living room. Which pattern would you choose for a robot whose odometry drifts?

References

1. Choset, H., Lynch, K. M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. E., and Thrun, S. (2005) Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press.link to Principles of Robot Motion: Theory, Algorithms, and Implementations (opens in a new tab)

   Chapter 6 is this chapter's source: the trapezoidal sweep and its four events (Figs. 6.1–6.8), Morse decompositions (Def. 6.2.1) and the variable slices of Figs. 6.12–6.18, sensor-based coverage and the cycle algorithm (§6.2.4), Euler's count and the path-length bound (§6.2.5), and pursuit–evasion after Suzuki and Yamashita and LaValle, Guibas et al. (§6.3).

2. Choset, H. (2000) Coverage of Known Spaces: The Boustrophedon Cellular Decomposition. Autonomous Robots 9(3), 247–253.doi:10.1023/A:1008958800904 (opens in a new tab)

   The boustrophedon decomposition and its coverage path: cells only where the sweep line changes connectivity, and the comparison with the trapezoidal decomposition that the Boustrophedon Mower reproduces.

3. Acar, E. U., Choset, H., Rizzi, A. A., Atkar, P. N., and Hull, D. (2002) Morse Decompositions for Coverage Tasks. International Journal of Robotics Research 21(4), 331–344.doi:10.1177/027836402320556359 (opens in a new tab)

   Definition 6.2.1 in full: critical points of a slice function on the obstacle boundary, and the spiral, spike, squarel and brushfire patterns of the gallery.

4. Acar, E. U. and Choset, H. (2002) Sensor-Based Coverage of Unknown Environments: Incremental Construction of Morse Decompositions. International Journal of Robotics Research 21(4), 345–366.doi:10.1177/027836402320556368 (opens in a new tab)

   Critical-point sensing from range data, the incremental Reeb graph, and the cycle algorithm whose forward, reverse and closing phases the online coverer implements.

5. Choset, H. (2001) Coverage for Robotics — A Survey of Recent Results. Annals of Mathematics and Artificial Intelligence 31, 113–126.doi:10.1023/A:1016639210559 (opens in a new tab)

   The survey that frames coverage as exhaustive walks on cell decompositions and places the boustrophedon and Morse decompositions among heuristic, approximate and exact methods.

6. Galceran, E. and Carpin, S. (2013) A Survey on Coverage Path Planning for Robotics. Robotics and Autonomous Systems 61(12), 1258–1276.doi:10.1016/j.robot.2013.09.004 (opens in a new tab)

   The modern map of the field: cellular decompositions, grid-based and graph-based coverage, multi-robot coverage, and coverage on 3-D surfaces — where to go after this chapter.

7. LaValle, S. M. (2006) Planning Algorithms. Cambridge University Press.link to Planning Algorithms (opens in a new tab)

   Chapter 6 treats cell decompositions (vertical decomposition, cylindrical decomposition) and §12.4 visibility-based pursuit–evasion with information spaces — the decomposition by information of this chapter's coda, at full length.