Motivation

Anyone who has spent time on or behind a lawnmower has developed an intuitive algorithm for getting an efficient and clean mow. Many of these intuitions will be useful for a programmed mowing algorithm, however some will not be. A programmed algorithm will likely trade off efficiency for robustness or safety - in particular the safety of the mower itself which shouldn't drive into dams, through fences, or hit solid walls or tree trunks.

The lawn mowing algorithm

'The lawn mowing algorithm' is actually a well-known computer science problem (also called the milling problem). It is the shortest (or quickest or cheapest) path which mows an entire lawn, or mills (like a CNC) a particular shape. It also pops up in 3D printing, and is closely related to the Travelling Salesman problem (think about a salesman turned lawn-mowing contractor who travels from town to town mowing people's lawns, and you will get the picture).

There is no way easy way to compute an optimal general solution, so a pragmatic algorithm is required. Here is a nice YouTube video simulation of a lawn mower solving the problem.

Simulation one - adaptive infill

This is a mowing simulation using a 'stake dropping algorithm'. A left-wall-hugging rover starts at a boundary, and works its way around the mow field. The boundary can be a combination of a virtual fence, and real obstacles (including real fences). The rover drops (virtual) stakes as it moves around, and hence knows where it has mown. It treats the stakes as obstacles when it meets them next time round, and hence should gradually mow towards the centre.

The rover here is the red rectangle (towards the north east), which has gotten stuck in a local island towards the north east. This one gets a fail - it is too susceptible to trapping itself. Also it's pretty easy to thing of situations where it will fail.

Simulation two - auto-striping with simple collision avoidance

This is a mowing simulation following a set stripe-path, but with obstacle avoidance. It completes the mission.

Simplest solution

While mowing a busy and crowded lawn, collision avoidance will be necessary. However farm pasture is generally cleared of objects. It would be relatively easy to divide most paddocks into simple convex shapes, and apply an auto-striping algorithm with collision detection.

Software

Animation showing the lawn mowing concept.

Cool links

Get Allegrobotics updates on twitter
Greenzie use stand-on mowers for their conversions. Very cool.
The Manscraper.
Others doing some cool stuff.
Others doing some Mowbotics.
Dave Z JR remote control lawnmower.

Leave a comment

Something I'm doing wrong? Solved my problems? Got a better idea? Got a similar problem?
Think I might have solved your problem? Ninety-nine problems, but your robot ain't one? Say so ..