An area in the shape of a square 10 units on a side needs to be mowed. The mower, which only goes forward, has a mowing "footprint" that is a unit square, and turns about the center of its footprint.

An optimal mowing plan is sought. A mowing plan designates a starting position and from there gives a complete mowing path. An optimal mowing plan is one closest to a straight line in the sense that the sum of all the changes in the mower's angular direction is minimized, each such change taken as the minimum possible positive value. The mower is not impeded by the border of the square and can travel without difficulty outside it as well as inside it.

Is "spiral" better than "back and forth," and what about a "diagonal" plan?

Does the lawn mower have a minumum turning radius or not?
Or can it only turn when not moving forward?
Can it only travel straight forward?

If it can travel sideways, you can obviously mow the entire lawn without rotating at all, so that answers the last question.

If you can turn while moving forward you may be able to do a smooth arithmetic spiral.  I'll look into just how efficient that is.  I suppose you can move and turn with small enough increments that this should be allowable.  So that would answer the first two questions.

-Jer

Posted by Jer on 2005-02-14 17:18:14