Covering every blade

Suppose the mower already knows exactly where it is — centimetre-grade, drift-free, the problem we took apart in the localization article. A new question immediately follows: where should it go next? Not "how do I get from A to B," the classic point-to-point planning problem, but something subtly harder. The robot must pass its cutting deck over every point of the lawn at least once, stay out of the flowerbeds and off the patio, and do it without mowing the same stripe four times or spending half the battery pirouetting at the ends of rows.

This is complete coverage path planning (CPP), a branch of motion planning with decades of theory behind it.12 It shows up wherever a tool has to sweep an area: vacuuming, floor scrubbing, demining, crop spraying, ship-hull inspection, and — the case in front of us — cutting grass. This article builds the problem from its formal statement to the algorithms a fielded mower actually runs, and ends where the whole research program ends: the same math, lifted into the air.

01What "cover the whole lawn" really asks

The lawn is a bounded region in the plane. Some of it is grass we must cut; some is obstacles — beds, trees, the pool, the shed — we must not enter. Call the cuttable region the free space and everything else obstacle space. The cutting deck is a tool of width \(w\); as the robot moves, it sweeps a swath of that width along the path.

Three requirements define a good coverage path, and they pull against each other:

• Completeness. Every point of free space must be swept by the deck at least once. A missed patch is a tuft of uncut grass — the single most visible failure mode of a robotic mower.
• Obstacle avoidance. The deck must never enter obstacle space. This is not optional and not soft: clipping a flowerbed is worse than leaving grass long.
• Efficiency. Subject to the first two, minimize wasted work — redundant overlap between swaths, total path length, and the number and cost of turns. Efficiency is what separates a 40-minute mow from a 70-minute one on the same lawn.

The tension is the whole story. Perfect completeness is trivial if you allow unlimited overlap; perfect efficiency is trivial if you tolerate gaps. Coverage planning is the art of getting completeness for nearly free in overlap and turns.

02Formalizing complete coverage

Let \(W \subset \mathbb{R}^2\) be the workspace, \(\mathcal{O}\subset W\) the obstacles, and \(F = W \setminus \mathcal{O}\) the free space to be cut. A path is a curve \(\gamma:[0,T]\to F\). Let \(D(\gamma(t))\) be the set of points covered by the deck when the robot is at \(\gamma(t)\) — a disk or rectangle of width \(w\) centred on the tool. The swept set over the whole path is the union

$$ \mathcal{C}(\gamma) = \bigcup_{t\in[0,T]} D\big(\gamma(t)\big). $$

The path is a complete coverage path when it sweeps all of free space while never entering an obstacle:

$$ F \subseteq \mathcal{C}(\gamma) \quad\text{and}\quad \gamma(t)\in F\ \ \forall t. $$

Among all such paths we want the cheapest one. A practical cost objective trades off how far the robot drives against how much it doubles back over ground it already cut. Define the overlap ratio as the swept area in excess of the free area, normalized by the free area:

$$ r_{\text{ov}} = \frac{\operatorname{area}\!\big(\mathcal{C}(\gamma)\big) - \operatorname{area}(F)}{\operatorname{area}(F)} \;\ge\; 0, $$

which is zero only for a perfect tiling and grows as swaths overlap or the deck re-covers cut grass. A combined objective then weights path length, overlap, and a turning penalty we will define in §07:

$$ J(\gamma) = \underbrace{L(\gamma)}_{\text{path length}} \;+\; \lambda_{\text{ov}}\, r_{\text{ov}} \;+\; \lambda_{\text{turn}} \sum_{k} c_{\text{turn}}(\delta_k), $$

where \(L(\gamma)=\int_0^T \lVert\dot\gamma(t)\rVert\,dt\) is the arc length, the sum runs over the turns, \(\delta_k\) is the heading change of the \(k\)-th turn, and the \(\lambda\)'s set the exchange rate between metres driven, fraction re-covered, and seconds lost turning. Minimizing \(J\) subject to complete coverage is the problem — and it is hard in general, closely related to the Traveling Salesman Problem, so real systems decompose it into pieces that each admit a clean answer.

03The boustrophedon pattern

For a single open, obstacle-free patch of grass, the optimal-in-practice motion is the oldest one there is: drive a straight line across the patch, turn around, come back one deck-width over, and repeat. The Greeks called this boustrophedon — "as the ox plows," the path an ox-drawn plough traces turning at the end of each furrow. It is the back-and-forth, the lawnmower pattern.

The boustrophedon pattern is efficient for one reason: long straight runs and few turns. Within a convex region, parallel passes spaced at the deck width \(w\) (or slightly less, to guarantee no gap) cover the area with the minimum number of passes, and therefore the minimum number of end-of-row turns. A region of width \(d\) across the sweep needs roughly \(\lceil d/w \rceil\) passes. Two design choices follow immediately:

• Sweep direction matters. Orienting passes along the region's longest dimension minimizes turns — one turn per pass, so you want as few, as-long passes as possible. On a thin strip, mow along the strip, not across it.
• Convex regions are easy; the lawn is not. A simple back-and-forth stays clean only where no obstacle pokes into the sweep. The moment a tree or bed interrupts it, naive boustrophedon either collides or leaves crescents of uncut grass behind the obstacle. The fix is to stop treating the lawn as one region.

04Exact cellular decomposition

The dominant idea in classical coverage is exact cellular decomposition: chop the free space into non-overlapping cells, each shaped so that a simple boustrophedon sweep covers it completely, then cover every cell and stitch the cells together. Because the cells exactly tile the free space, covering all of them covers the lawn — provably, with no gaps.2

The canonical method is Choset and Pignon's boustrophedon cellular decomposition (BCD).3 Imagine sweeping a vertical line — a slice — across the workspace from left to right. As it moves, it intersects the free space in some number of disjoint open intervals. That number stays constant except at special points — the leftmost and rightmost vertices of obstacles, where the slice's connectivity splits or merges. These are the critical points (events). A cell boundary is drawn at each one; the regions between consecutive events are the cells, each "slice-monotone" enough that a straight back-and-forth covers it. Events come in two types:

• IN (split). The slice hits an obstacle's left tip and one interval splits into two — the lawn forks around the tree. One cell closes; two open.
• OUT (merge). The slice passes the right tip and two intervals merge into one. Two cells close; one opens.

Run the sweep once, record the events in order, and the lawn is decomposed into a handful of obstacle-free cells. Two sub-problems remain, and they separate cleanly:

1. Cover each cell. Inside a cell there are no obstacles, so a boustrophedon sweep (oriented along the cell's long axis) does the job optimally.
2. Order the cells. Build an adjacency graph whose nodes are cells and whose edges connect cells that share a boundary. The robot must visit every node, covering each cell and driving between adjacent ones, while minimizing the dead travel ("deadheading") between cells. Choosing a good visiting order is a graph problem — and it is exactly here that the Traveling Salesman Problem walks in.

Finding the cell-visit order that minimizes total transit is a TSP (a generalized TSP if per-cell sweep direction is left free) over the adjacency graph. TSP is NP-hard, so optimal ordering is intractable at scale; in practice we use heuristics, or solve exactly because most lawns yield only a dozen-odd cells. Arkin, Fekete and Mitchell made the connection rigorous: the underlying "lawn mowing problem" — the shortest tour of a cutter covering a region — is itself NP-hard, and they gave constant-factor approximation algorithms for it.6

Pseudocode — boustrophedon decomposition and coverage

# Free space F with polygonal obstacles; deck width w.
def boustrophedon_coverage(F, obstacles, w):
    # --- 1. SWEEP: build cells at critical points ---
    events = sort_by_x(critical_vertices(obstacles))   # IN / OUT events
    cells, open_cells = [], [full_slice(F)]
    for e in events:
        if e.type == "IN":                       # lawn forks around obstacle
            close(open_cells, e); open_cells = split_into_two(e)
        elif e.type == "OUT":                    # lawn rejoins past obstacle
            close(open_cells, e); open_cells = merge_into_one(e)
        cells += newly_closed_cells()

    # --- 2. ORDER: TSP over the cell adjacency graph ---
    G     = adjacency_graph(cells)                     # edge if cells share a border
    order = tsp_tour(G)                                # NP-hard; heuristic for many cells

    # --- 3. COVER: boustrophedon inside each cell, connect ---
    path = []
    for c in order:
        axis = longest_axis(c)                         # fewest, longest passes
        path += boustrophedon(c, w, along=axis)        # back-and-forth sweep
        path += transit_to(next_cell(c, order))        # deadhead between cells
    return path

The structure is worth internalizing because it recurs in every coverage system: decompose, cover each piece with a sweep, order the pieces as a TSP. Everything fancier is a refinement of one of those three stages.

05Morse decomposition and adjacency

The boustrophedon decomposition sweeps a straight vertical line, which is why its critical points are obstacle vertices. Acar, Choset and colleagues generalized this with Morse decompositions.4 The trick is to replace the sweeping line with the level sets of a smooth Morse function \(h(x)\): instead of asking where a vertical slice changes connectivity, ask where the level curves of \(h\) do. Cell boundaries land at the critical points of \(h\), where its gradient vanishes — hence the name.

Choosing \(h(x)=x_1\) recovers the original boustrophedon decomposition exactly, since the level sets are vertical lines. Other Morse functions give other decompositions: \(h(x)=\lVert x - x_0\rVert\) makes the level sets concentric circles, producing spiral coverage suited to a circular field. The framework unifies a whole family under one criterion — cut a cell wherever the level-set topology changes — and, crucially, it makes the decomposition computable from sensor data as the robot drives, the bridge to online coverage in §08.

Either way the downstream artifact is the same: a set of simple cells plus an adjacency graph recording which cells touch. Coverage is then a walk on that graph visiting every node — the cell-ordering TSP again. Decomposition turns an intractable continuous problem into a finite graph problem, which is why it is the backbone of the field.

06Grid methods and spanning-tree coverage

A different lineage abandons exact geometry and approximates the free space with a grid of equal cells the size of the tool. The classic instance is Gabriely and Rimon's Spanning-Tree Coverage (STC).5 Tile the workspace with cells of size \(2w \times 2w\), build a graph connecting adjacent free cells, and compute any spanning tree of that graph. The robot then circumnavigates the tree — hugging it on one side — using sub-cells of size \(w\); the path tracing a spanning tree's boundary is a single closed loop that visits every sub-cell exactly once. Its properties are why it is beloved in practice:

• Provably complete on the grid: every cell the tree reaches is covered.
• Essentially no overlap. Because the circumnavigation visits each sub-cell once, STC covers an obstacle-free region with the tool passing over each cell a single time — the overlap ratio \(r_{\text{ov}}\) approaches zero on the discretized area.
• Linear time. The offline version computes an optimal covering path in \(O(N)\) for \(N\) cells, and the tree structure gives a clean single closed tour with no decision-making at runtime.
• An online twin. The same spanning-tree idea extends to a robot that discovers the grid as it goes, building the tree incrementally with only local sensing.

The price is discretization: a grid of tool-sized squares cannot represent a curved bed's boundary exactly, so STC leaves a thin uncovered margin along irregular edges, handled by a separate perimeter-following pass. Grid methods trade a little boundary fidelity for enormous simplicity and a hard completeness guarantee — a trade many production mowers take, pairing an STC-style interior fill with a perimeter trim.

07The cost of turning

On a real lawn the straight passes are nearly free — the robot drives them at full speed, cutting the whole time. The turns are where time and energy go: at the end of each row the mower must decelerate, pivot or arc through roughly 180°, and reaccelerate, cutting little or nothing. These headland turns (the term is from farming — the "headland" is the field-edge strip reserved for turning equipment) dominate the inefficiency of any boustrophedon pattern.

That is why the objective in §02 carries an explicit turning penalty. A simple, effective model charges each turn a cost that grows with how sharply the heading changes:

$$ c_{\text{turn}}(\delta) = \alpha + \beta\,|\delta|, $$

where \(\delta\) is the heading change, \(\alpha\) is a fixed cost per turn (the decelerate–reaccelerate overhead you pay even for a gentle bend), and \(\beta\) scales the extra cost of sharper turns. A full 180° end-of-row reversal is expensive; a shallow course correction is cheap. Summed over a boustrophedon sweep of \(n\) passes — which makes \(n-1\) end turns — the turning term is on the order of \((n-1)\,c_{\text{turn}}(\pi)\), which is why cutting the number of passes by sweeping along the long axis pays off twice: less straight-line distance, and far fewer expensive reversals.

This reframes the sweep-direction choice as an optimization, not a heuristic: for each cell we pick the orientation \(\phi\) that minimizes passes-plus-turns, and when turns are very expensive the optimum can shift away from the naive "longest axis" answer. Headland turns are also why cell ordering matters beyond raw transit distance — a good TSP tour lets the robot exit one cell already pointed into the next, amortizing a turn that would otherwise be pure waste.

08Online coverage and multi-robot partitioning

Everything so far assumed a known map. But a mower meets a stray toy, a new planter, a sleeping dog. Online (sensor-based) coverage drops the prior map and plans as the robot perceives. Acar and Choset's incremental Morse decomposition is the principled answer: the robot detects critical points from its own sensors as it sweeps, growing the decomposition and adjacency graph in real time, and stays provably complete despite never having the full map up front.4 The online STC variant does the analogous thing on a grid. The practical pattern is a hybrid — cover from a stored map for efficiency, but treat every unexpected obstacle as a fresh critical point and re-plan the affected cell locally.

The second extension is more than one robot. Two mowers cut a sports field in under half the wall-clock time of one — if they are not fighting over the same grass. The dominant strategy is area partitioning: divide the free space into balanced sub-regions, assign one to each robot, and let each run single-robot coverage in its own territory. Good partitions equalize workload, respect each robot's reachability, and minimize the shared boundary where double-cutting happens. The cell adjacency graph is again the substrate — partition it into connected, balanced parts — and multi-robot spanning-tree methods extend STC's guarantees to a team.

09The NLR coverage stack

Put together, a wire-free mower plans coverage in layers that mirror the theory:

1. Decompose the lawn. From the taught boundary map and the known obstacles, build an exact cellular decomposition into obstacle-free cells plus an adjacency graph. Curved beds get a Morse-style decomposition; rectilinear yards reduce to clean boustrophedon cells.
2. Orient and sweep each cell. Pick each cell's sweep direction by minimizing passes-plus-turns, then fill it with a boustrophedon pattern at a swath spacing slightly under the deck width to guarantee no gap.
3. Order the cells as a TSP. Solve the visit order to minimize deadheading and line up cell exits with the next entrance. A handful of cells is solved exactly; larger sites use a TSP heuristic.
4. Trim the perimeter and re-plan online. A boundary-following pass cleans the irregular edges grid coverage leaves behind, and any unexpected obstacle becomes a new critical point that triggers a local re-decomposition.
5. Track coverage explicitly. The robot keeps a live map of what it has actually swept, so it can verify completeness, resume after a charge cycle, and report the overlap ratio achieved.

The governing principle is the one that runs through the localization stack: turn an intractable continuous problem into a finite, well-posed one. Decomposition makes coverage a graph problem; the cost objective makes "efficient" measurable; explicit coverage tracking makes "complete" verifiable rather than hoped-for.

10How this transfers to drones

The grass is incidental. Complete coverage is the abstract problem of sweeping a tool over a region, and the moment you tilt the workspace into the sky it is exactly the problem of flying a sensor over an area.

That is the throughline of NLR's research: the surface changes — lawn, field, façade, snow — but coverage is one problem. Decompose the space, sweep each piece, order the pieces, and count what you have actually covered. Solve it well on the ground and you can sweep anything, anywhere.

Sources & further reading

1. Choset, H. "Coverage for robotics – A survey of recent results." Annals of Mathematics and Artificial Intelligence, 31:113–126, 2001. doi:10.1023/A:1016639210559
2. Galceran, E., & Carreras, M. "A survey on coverage path planning for robotics." Robotics and Autonomous Systems, 61(12):1258–1276, 2013. doi:10.1016/j.robot.2013.09.004
3. Choset, H., & Pignon, P. "Coverage Path Planning: The Boustrophedon Cellular Decomposition." Field and Service Robotics, Springer, 1998. doi:10.1007/978-1-4471-1273-0_32
4. Acar, E.U., Choset, H., Rizzi, A.A., Atkar, P.N., & Hull, D. "Morse Decompositions for Coverage Tasks." The International Journal of Robotics Research, 21(4):331–344, 2002. doi:10.1177/027836402320556359
5. Gabriely, Y., & Rimon, E. "Spanning-tree based coverage of continuous areas by a mobile robot." Annals of Mathematics and Artificial Intelligence, 31:77–98, 2001. doi:10.1023/A:1016610507833
6. Arkin, E.M., Fekete, S.P., & Mitchell, J.S.B. "Approximation algorithms for lawn mowing and milling." Computational Geometry, 17(1–2):25–50, 2000. Establishes the NP-hardness of the lawn-mowing (coverage) problem. doi:10.1016/S0925-7721(00)00015-8