Google Answers Logo
View Question
 
Q: The Lawnmower Problem (covering) ( No Answer,   5 Comments )
Question  
Subject: The Lawnmower Problem (covering)
Category: Science > Math
Asked by: paulie111-ga
List Price: $19.50
Posted: 16 Aug 2006 16:56 PDT
Expires: 15 Sep 2006 16:56 PDT
Question ID: 756801
Consider a special lawnmower.  This lawnmower can go infinitely fast,
but has a finite possible acceleration in any direction.  What is the
optimal path for such a lawnmower to cut all the grass in a given
rectangle?  (Not a polygon, a rectangle).

Please note it is perfectly acceptable for the lawnmower
to cross over previously cut areas.

Clarification of Question by paulie111-ga on 19 Aug 2006 13:12 PDT
Thanks for your thoughts -

This is not really about a lawnmower, but has applications in many
areas of science - such as imaging and remote autonomous verhicles.

But allow me to clarify - yes - it has only a finite cutting swath -
say dimension with diameter A.  The rectangle has width B and C.  I
should not have said it can go infinitely fast - but rather, it's
speed is unlimited.

So if we consider a path like a raster pattern, it must accelerate
along each span, slow down (decelerate), turn and reaccelerate along
the next span.  In all these cases, acceleration is the limiting
factor.  It simply cannot turn 90 degrees as this would require
infinite acceleration.

A spiral overlaying a rectangle spends a large amount of time outside
the rectangle - and hence is probably not optimal.  A raster pattern
does not spend any time outside the rectangle, but has to slow down at
every turn, which is also probably not optimal.

Good luck with the thoughts!

Request for Question Clarification by pafalafa-ga on 19 Aug 2006 14:16 PDT
paulie111-ga,

Can you clarify what you mean by "optimal".  Least time?  Maximum lawn
cut per distance travel (i.e. smallest number of cross-overs)?  Fewest
changes in direction?

Also, if you explain the acceleration constraint a bit more, it would help.

Thanks,

pafalafa-ga
Answer  
There is no answer at this time.

Comments  
Subject: Re: The Lawnmower Problem (covering)
From: stanmartin1952-ga on 17 Aug 2006 00:19 PDT
 
A spiral?
Subject: Re: The Lawnmower Problem (covering)
From: ansel001-ga on 17 Aug 2006 02:03 PDT
 
I assume also that its rate of deceleration in a given direction is
also finite and the same as its rate of acceleration.  The answer will
also depend on the dimensions of the rectangular lawn and the width of
the swath the lawnmower cuts with one pass.  Also, shall we assume the
lawnmower can turn 90 degrees in place or does it have a turning
radius?

For an finite surface area that is rectangular, a spiral might not be
optimal.  It could cause problems when you get the the edge of the
lawn.  Also, how does one account for going in a spiral?  You are
continually changing direction which involes decelerating in one
direction and accelerating in another?
Subject: Re: The Lawnmower Problem (covering)
From: myoarin-ga on 17 Aug 2006 05:22 PDT
 
Hi,
Since you are talking about a theoretical lawnmower, I presume you are
asking a theoretical question, i.e., that you are not interested in
the real practicalities of proper lawnmowing.  These are mowing
parallel with the sides where one turns to achieve a good cut there  -
two, three or four rows so that one can turn without bothering to try
to make a neat job in the turning area.
Obviously, if one wants to benefit from the speed of this lawnmower,
one should mow back and forth the longer length of the rectangle,
making as few turns as possible.
Maybe I have missed something in your statement:  "but has a finite
possible acceleration in any direction".  As Ansel has pointed out,
change in direction limits the speed; a reverse of direction and an
90 turn imply a dead stop.

Can you elucidate us?
Subject: Re: The Lawnmower Problem (covering)
From: myoarin-ga on 19 Aug 2006 15:22 PDT
 
Hi, again,
This is kind of a fun project, but I still think we need another clarification.
Ansel has raised the question about speed reduction in curves,
spiraling.  This is a limitation for actual vehicles.

1. Is it one for your lawnmower or a "remote autonomous vehicle"? 
(wouldn't seem to be one for electronic imaging)
2. Can the lawnmower go beyond the b,c dimensions of the lawn?

If the answers are 1. yes, 2. no; I still see no better solution that
a raster the major length of b,c.
If the answers are different, the problem could be more interesting.  
For example, it could be fastest to mow along the longer edge, making
a half circle to come back along the other side of the midfield
parallel line, turning back the same way to cut a swath parallel the
the first one, and so on, then racing to mow the corners.

I expect that my speculation is making the problem more difficult than
you anticipated.
Subject: Re: The Lawnmower Problem (covering)
From: activealexaoki-ga on 26 Aug 2006 00:12 PDT
 
If you can go over the rectangle to turn 180 degrees, you can take the
fewest stroke to cover it. (assuming there is a width of the lawnmower
to cover in a stroke) The mowing is neat but slower than using the
application of Graph Theory, which asks the maximum number of
intersection possibly made by finite number of line segments...

But in real life, if you do slappy mowing, you are fired anyway. So
"mathematically appropriate" path is not always the "socially
expected" path.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy