Slashdot Mirror
The Mathematics of Lawn Mowing
Hugh Pickens writes "I enjoy mowing my six-acre lawn with my John Deere 757 zero-turn every week, and over the course of the last five years of mowing I have come up with my own most efficient method of getting the job done which takes me about three hours. While completing my task this morning, I decided after I finished to research the subject to discover if there is a method for determining the most efficient path for mowing, and found that Australians Bunkard Polster and Marty Ross wrote last summer about an elegant mathematical presentation of the problem of mowing an irregularly shaped area as efficiently as possible. First we simplify our golf course mowing problem by covering the course with an array of circles with each circle radius equal to the width of the mower disc. Connecting the centers of the circles produces an equilateral triangular grid, with vertices at the circle centers. Following a path consisting of grid edges, there will necessarily be a fair amount of overlap so the statement of the problem is to minimize the overlap by minimizing the number of vertices that are visited more than once which Polster and Ross say is easily achieved by well-known computer search algorithms. Any other tips from Slashdot readers?"
... hire someone to mow it for you. :)
But it's such a tease... what computer algorithms are referred to near the end of the article? I can't remember my intro algo's class :(
Believe it or not sometimes people are better at solving certain problems than computers. This is one of those fuzzy problems with lots of irregularities that a human is excellent at working out with just a little help from a stopwatch.
A bullet may have your name on it but splash damage is addressed "To whom it may concern."
... get off my lawn! :-)
SCNR
The Tao of math: The numbers you can count are not the real numbers.
Own less lawn.
In America, you mow the lawn!
...is your friend!
First, let me say that I do like this type of story. Interesting, thought provoking, nerdy and mathematical in nature.
I will also preface what I am about to say by noting that people are free to make whatever life tradeoffs they want.
At the same time, I really wonder why anyone would want a property that takes three hours just to cut the grass. Life is short, why spend it maintaining a large property. I make low six figures now and could afford a lot more of a house than I have, and even when I upgrade to a nicer neighborhood next year will still way underbuy what the bank wants me to borrow.
If you are stinking rich and want the large property, go ahead... but hire someone to do it for you. Your time is more valuable than the cost of having someone cut your grass. Give some teenager or out of work adult the opportunity to earn some money. That is the real win-win of capitalism.
Finally, the article linked to seems light on the math itself, but seems very descriptive. I don't know that there is a purely mathematical solution to the problem but wonder if genetic algorithms would get you to where you want to be. I also wonder if you have a yard like mine with tree roots all over the place would change the outcome :)
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
I can't speak to mathematical models of efficiency but I can tell you about landscapers models of gas and employee efficiency.
Use trimmers and small mowers to shape up the irregular areas until they reach a common area or edge.
Allow the riding mowers to tackle the larger squared zones
Of course none of this accounts for the grass, which must be hauled with an attached trailer on the riding mowers and regularly emptied regardless of the efficiency pattern.
When the foot seeks the place of the head, the line is crossed. Know your place. Keep your place. Be a shoe.
Sheep?
TITS That ist what ist required for this to have any shot at validity. I mean, it ist true that stinkin' armpits should not be allowed on a plane, but it shouldn't for a wholly different reason. Same for the mathematics of lawn mowing. TITS
Because I live in a US county that publicly owns two hydro-electric dams our electric power rates are low enough to make it much more economical to use an electric-powered lawn mower instead of a gasoline-powered lawn mower. The safest method of mowing the grass would be to ensure that the power cord always stays out of the way of the grass-cutting head of the mower. This complicates the efficient mowing technique because, in general, it's better to simply mow so that the power cord is always on the freshly mowed grass and never on the soon-to-be-mowed grass.
I wonder what effect this would have on the system.
No one ever had to evacuate a city because the solar panels broke!
By treating the lawn as a set of circular areas of radius equal to the mower disc, they eliminate all possible routes that would involve driving the mower on some path other than vertex to vertex. And I expect it would not be hard to construct a lawn where the best path involved just such a route. As constructed I think the problem is actually kind of boring (which is not to say I can solve it!); it would be more interesting if they had come up with some way to attack the optimization problem without turning it into something out of graph theory.
How boring...
The 'optimal' solution has the mower finishing in the middle of the lawn, which is usually not where you want to leave it parked.
Although Dykstra's algorithm is great for the most efficient airline flights between airports..I like the symmetry patterns of Fenway Park..although I only have to cut 1/2 acre.
They don't use gas or waste your time.
How does the circular mower cut corners? Don't most people have a corner of smaller radius that their imaginary circular lawnmower?
Shouldn't the problem be how to sweep a straight line of some given width to cover an area? I'm guessing the circular mower is some sort of simplifying assumption. Never had a lawn before, so no idea.
This neglects the reality that even with zero turn mowers, there is some cost to turning.
You can't make a right angle turn at full speed.
There isn't a mathematically correct solution unless you correctly model the costs of turning.
If you're doing it 'by hand' - then you also need to model the cost of screwing up.
It may be that comparatively simple schemes - such as an interleaved raster scan may be
in practice optimal for a human to mow it.
In my experience (with 1-acre and 4-acre sections to mow) there is a little you can do to optimize the route, but in general, you want to end up with the clippings shooting toward the center of the lawn so it's easy to rake. (The bags on the mowers are a pain because you have to empty them so often.) So the perfect path in the article is marred by the fact that you then have to either re-mow some of it to shoot the clippings in the right direction, or get out a blower and spend just as much time doing that.
"If you make people think they're thinking, they'll love you; But if you really make them think, they'll hate you." - DM
"I enjoy mowing my six-acre lawn with my John Deere 757"
Wait, he enjoys that?
My goal with my lawn, year by year, is to slowly but surely destroy it. I rip it up and replace it with gardens, trees, or crushed stone with ornamental larger rocks, sometimes with ferns and moss around the edges. The remaining grass is entirely naturally selected -- that is, if it survives without additional water, fertilizer, aeration or other manual interference other than the occasional mow, it lives. If not, it can go ahead and die, to be replaced by the stuff that can survive. Since I bought this house I've decreased the total lawn area by about 25%, and my front lawn is down to about 40% of the original area (60% of it is replaced). What time I spend maintaining the non-lawn areas is expended yanking the occasional weed out of the garden, trimming bushes, or raking the gravel and arranging the ornamental boulders. It looks quite nice in the front. The back needs a lot more work (too much grass), but most people don't see it, so I can neglect the mowing a bit.
My optimal lawn mowing strategy is to mow less. Permanently.
It sounds (after those particular assumptions) like you want to solve the Traveling Salesman Problem, in particular the special case with Euclidean 2d distances (more or less, depending on hills). "Computer search algorithms" is a little bit of a weasel word... I believe these are exactly solved in practice on moderate-size instances using integer linear programming (ILP) techniques, the work of Bill Cook and co-authors is likely useful. From a theoretical (but not so important) perspective: the problem is NP-complete but admits an "approximation scheme." See http://en.wikipedia.org/wiki/Travelling_salesman_problem
What? Floodfill ftw.
Seven puppies were harmed during the making of this post.
When America collapses, people with 6-acre lawns will soon find very persuasive arguments that they should be sharing their land with the less lucky.
...for a tractor-haybine combination with an 80" swath and a 20' turning radius.
Warning: this article may contain humor, sarcasm, parody, and perhaps even irony. Read at your own risk.
It's a case of the Traveling Salesman Problem http://en.wikipedia.org/wiki/Travelling_salesman_problem On the one hand it is the special case with Euclidean 2d distances (more or less, depending on hills). But also, it is the special case where all point-point distances are equal, depending on what exactly you meant by 'grid', which is called Graphical TSP. "Computer search algorithms" is a little bit of a weasel word... but as far as I know TSP instances are exactly solved in practice on moderate-size instances using integer linear programming (ILP) techniques, the work of Bill Cook and co-authors is likely useful. From a theoretical (but not so important) perspective: the 2d Euclidean problem is NP-complete but admits an "approximation scheme." I am not sure about the doubly special case you present, but my gut feeling would be it's also NP-complete.
may be huRting that the project coDunterpart, sux0r status, *BSD
I've had a similar problem which I guess may be easier solved intuitively:
I'm at a golf course at the chipping green, and chip a bucket of balls onto the green. Now I wish to pick up those balls and put them back in the bucket. What is the most efficient path to take to pick up the balls (especially if I'm not a good chipper and some balls are spread out significantly).
If you are using your wet RAM thinking about about lawn care you can possibly take it as a sign that your youth and the more interesting times of your life are over.
The quickest method I've found for mowing my lawn is to hire someone else. It literally takes me only 3 to 5 minutes to write the check, and there is no geometry involved.
mowing 6 acres with a lawn mower? that should be a crime in its own. invest in 20-25 goats and a fence. not sheep. sheep are stupid and they smell. goats are smart. you'll find that looking at them is really relaxing. they'll also keep your lawn at golf-course grade length. price? sell your john deere and you should have enough to buy the lot.
BORING!!!!!!
It could be described as a variant of the Traveling Salesman problem, where each node is a mower-sized swath of grass and your object is to visit very node, returning to the starting one...
I enjoy eating gruel out of a plastic bowl placed on the tarp outside my tent every morning in the tent city where I live.
The solution to this is very similar to what a cam package would produce.
This is a fantastic example of how Americans take a simple problem and absolutely fuck up the solution.
So these Americans want to partake in some outdoor activity that requires a bit of open grass. Their solution? Buy a 6 acre lawn, pay property taxes on this land, buy a lawnmower, buy fuel for the lawnmower, buy fertilizer for the lawn, and waste hours each week mowing the lawn. Even if they pay somebody to maintain it for them, it's still a huge waste of money, time, and effort.
What do people in sensible countries do? They build parks, and everybody in the vicinity contributes a small amount of money towards its upkeep, without the burden falling directly on their shoulders. They can go use it whenever they want, and such parks are large enough that thousands of people can partake in all sorts of sports or other activities at the same time, from barbecuing, to playing catch, to even playing golf, without interfering with one another.
Oh, wait. Parks are probably too "socialist" at best, or "communist" at worst, for most Americans.
Pay someone to mow it for you.
Six acres isn't a lawn, it's a field... anyone else get the impression this guy just wanted a reason to say "I have a six acre lawn"?
The best solution: don't mow it.
Why the hell do you have 6 acres of grass? Plant some trees for christs sake.
Anyone else looked at these patterns and thought "CNC milling"?
Even if the zero-turn is very impressive it is not the mathematical model. When turning the width of the combined blades and the average speed will be reduced, making each turn sub optimal. As a boy I used a(n unsafe, think of the children) mower on a rope turning perfect spirals with a distant supervisor and finished off the in betweens in direct supervision mode.
I found cows, goats and fowl to do a good job and save me lots of time.
from a mathematician with a few dozen published papers and half a dozen published books on mathematics.
So now you ask slashdot just to make sure???
http://en.wikipedia.org/wiki/Maze_solving_algorithm
And retire to the porch with your beer.
My goats and sheep mow the lawn while I drink beer.
Examination of the example in the article suggests a heuristic algorithm that should provide near-optimal solutions and is suitable for real-time execution on neural wetware.
1. Start by mowing around the outside border.
2. Proceed going around, from the outside in.
3. When you reach a strip <= 3 mowers wide, clear it with short back-and-forths.
Proof of an upper bound on excess mowing vis-a-vis the optimal solution is left as an exercise for the reader.
I think that the math is now fine but you can see that the answer is clearly wrong by looking at the result.
Look how close to the edges you have to drive. Almost half of the lawn mower will be out of the green area. And that goes around the outer perimeter of the whole area. That just can't be simply optimal way to do it even if it produces a nice grid incide of the area.
1. Buy beer. 2. Start mower. 3. Open beer. 4. Start "mowing and drinking" 5. Be amazed as time flies and the grass gets cut
Cover your yard in asphalt and paint it green. It also doubles as a tennis/basketball court. I hate "mowing lawns".
Once you've represented the lawn area as a tessellation of (slightly overlapping) lawnmower-sized patches, then isn't this just the traveling salesman problem - visit all patches with the least distance traveled?
This is a classic NP problem... if the problem size (N) is too large to fully evaluate (in this case 6 acres = 29,000 square yards, tractor area = 1 square yard, so N = 29,000 which is rather large for this type of problem), then heuristics are you're friend.
The optimal solution, which would only apply for a circular lawn, is obviously a spiral pattern. For an irregular shape lawn one obvious heuristic would be to decompose the lawn area into a set of various sized circular blobs and do each of these in an expanding spiral pattern, then onto the next.
A similar heuristic would be to start by spiraling inwards around the entire lawn, and "recurse" into smaller areas when they (via having narrow "neck" entrances) are about to be cut off from the main spiral - specifically when the neck has been reduced to two tractor widths wide (one path in, one path out). In fact, this may well be the optimum strategy, particularly as it takes advantage of the specific problem topology rather than being a generic traveling salesman heuristic.
Please send cash to SpinyNorman c/o Slashdot if this makes you money!
and havent found the perfect way to mow my lawn.... any suggestions?
I have 4 acres with trees, and get sick of mowing. (I also have a 1 acre woodlot) I see that the solution given is flawed for several reasons. In the real world it will produce a poor looking finish, but that is tolerable. The lawn will be one height and neat, but not well finished. Also the mowing modeled as a circular area is a built in inefficiency, because only the edge of the circle is cutting.
I did not get out of the setup whether edges were treated as "hard" or "soft". A hard edge you cannot pass the mower over, this would be a wall, tree, mailbox, or valuable planting. A soft edge would be a material that you can pas the mower over, this would be a driveway, patio, and certain planting bed edges.
I find that the best balance in real world finish and speed is when I mow 2 laps around the edges so I can turn with my old school garden tractor, then to create boxes that move across the yard. This allows for maximum velocity to be maintained, long orderly cuts which provide better finished appearance than irregular turnings, and adequate turning radius for my equipment, which is very different from the OP's.
Since my machine has a top mowing speed of about 5mph, and a 46 inch cut, this takes just under 1 hour per acre, for me. About 3 hours for 4 acres on a good day mowing neat growth. If my meadow has sat for several weeks, it will take 3 hours to mow and mulch that area alone, a common problem in the spring since it is river floodplain and will be under water a fair number of times.
With a zero turn cutting a 60 inch path at up to 9.5mph going in straight lines will outweigh minimizing recut because slowing down to turn reduces the area cut per unit time more significantly than cutting a small area a second or third time. That is a muscle car of a lawnmower the OP is using. He should take a whole lot less time to mow than he reports, probably because of all the turns he is taking.
Phil
Laugh, it's good for you!
I have found that the most efficient way to mow the lawn is to call a couple of guys, Manny and Angel, who leave the place looking great.
The only downside, is they flirt with my daughter, my wife, my mother-in-law and probably when I'm not looking, my 8 year old border collie.
You are welcome on my lawn.
Some of us mow the lawn to make it look good. If it takes a little longer to leave a nice pattern, that's what headphones and a good collection of MP3s are for.
(name withheld by request)
There's one point you all missed.
Who the hell has time to get up in the morning and mow the fucking six-acre lawn? Don't these people have jobs? Night life? Anything?
Or are these the people you can find at grocery stores and department stores at 9pm on a Friday and Saturday night? Mostly fatties and retirees.
BTW if I had six acres I'd start a garden or something. A big one. Learn to grow my own food. Store a few years worth of supplies including ammo in a secure location. Dig a well and have both electric and manual pumps for it. Maybe invest in some kind of solar or other energy-producing technology.
I sure as hell wouldn't play stupid games with lawnmower geometry. That would be a sign that I need more important things going on in my life.
I have an irregular 2 acre lawn that I mow with a Toro zero-turn.
The problem with using TFA method is that the grass "revolts" after a while.
Grass does not want to be cut in the same pattern each time. What I have found is that over time the use of a repetitive pattern will tend to leave clumps of long strips of grass along the paths used. Even with freshly sharpened blades for each cut this occurs.
The manual for my tractor suggests going around the outside and then in-filling using a decreasing spiral not terribly unlike what TFA suggests. The manual is much less mathematical about it of course.
I now use a series of 4 different patterns. I always start by doing the entire outline of the properly at the edges. Then I start mowing by effectively going north-south for the entire cutting. The next cutting I will do east-west exclusively. The third time I cut I will go diagonally to the two previous cuts. And for the fourth cut, you guessed it, I do the opposite diagonal. This has resulted in a very thick, uniform looking lawn. It also gives the lawn that overlapping golf course grid type pattern that some like.
As far as the amount of time added/removed that it takes... regardless of the method used I am on the tractor for about 1.5 hours. The variability in time required seems to be +/- 10 minutes. I'm not going to get excited about those few minutes.
I believe what you are interested in is called a Eulerian Path: http://en.wikipedia.org/wiki/Eulerian_path
Also the similarly related Hamiltonian Path: http://en.wikipedia.org/wiki/Hamiltonian_path
As others have mentioned the actual method of solving the problem is probably best defined as "The traveling salesman" problem: http://en.wikipedia.org/wiki/Traveling_salesman_problem
Good Luck.
Buy a goat.
Extra Added Advantage: At your convenience, Lawnmower Curry.
I've calculated my velocity with such exquisite precision that I have no idea where I am.
Lawns do not need to be mowed weekly. Dropping to every other week will save 3 hours weekly. The optimal solution will not be able to gain that much.
electric-powered lawn mower [...] ensure that the power cord always stays out of the way
I thought the power cord would stay in the garage and charge the mower's battery overnight.
Why are we still growing grass that needs to be cut?
There have been algorithms for about 50 years for solving the related but much more complex problem of milling. This is equivalent to a particular variant called pocket milling.
Seriously, you don't need math to know that you mow in a circle, with the ejecting side of the lawnmower facing towards the center of the yard at all times.
Still waiting on Serviscope_minor to wake up to fucking reality and realize that Jessica Price isn't going to fuck him.
I have a self propelled lawnmower so as long as i hold a lever an just calmly walk behind it mowing is not an issue.
That is until i try to turn which requires me to use a comparatively large amount of force, it also takes a lot of time as you sort of have to stop, turn then go.
And this is where i think the algorithm is flawed, as it doesn't consider turns but only area covered.
I find just keeping to the outer edge of the unmoved area works best while straightening out curves as best as possible, then just mowing it sector by sector (as ours is not exactly convex in shape)
- "There is nothing quite like an ineffective solution to an nonexistant problem"
That is the most efficient. To have someone who makes less money.
Slashdot needs to work on a Hank Hill Annual Award.
I am a mesh maker and work with tessellations, (mostly in 3D but also 2D). You don't need this heavy duty math to arrive at the solution. Any area you mow more than once represents wasted effort. The simplest non intersecting path is, start at the outer edge and follow the boundary of the unmowed area and progressively you move inwards. Additional brownie points to choose the direction so that clippings are discharged into unmowed area.
sed -e 's/Chuck Norris/Rajnikant/g' joke > fact
I'm waiting to see your neighbor's face as you perform the stated algorithm. They might call somebody to asses the situation.
I've got a better tip. Why not just get a few sheep and let them mow (and manure) the lawn? Better yet, make sure the animals are ewes and milk them. I'm a professional cheesemaker, so my choice for the product will be obvious, but ewe's milk is usually high in fat, so you can also have amazing cream (or butter).
I just drive around the edge until it all disappears. You simply have to not care about the track pattern. If you're going for track pattern: one can't help the obsessive.
Why did you immediately assume less lawn meant less land? The area around the lawn could still be yours, but, for example, be used for growing useful stuff. (Food, biofuel...)
FRA: STFU GTFO
I have about 3.5 acres of lawn and I enjoy the weekly "chore" of grooming it. It is a time to ponder the fate of planet earth or when to visit the grand kids again. I really can't think of any negatives to mowing the grass other than the price of gas.
What is next, analyzing the fastest way to brush our teeth? I'll try not to give away the best approach.
Next week, kids, we move on to tire rotation.
I come here for the love
Exactly. Bragging about how he enjoys to mow his lawn every single week with his John Deere 757 zero-turn makes makes him a yuppie and a complete tool. He obviously needs to move out of suburbia.
I have about three acres of actual yard. Not lawn, but yard. It's a mix-match of various grasses and is anything but flat. The other four acres of my property is hardwoods, and beyond that is nationally protected forest. It has also been my goal to outright eliminate the lawn immediately surrounding my house. I've taken a somewhat similar path by planting trees and laying down stone walkways everywhere. I've been pleased to see that while the grass doesn't fair very well, I have a lot of soft moss coming up instead. It's been too hot to really plant any younglings this year, but I'm hoping to get a bunch of ferns in next spring. They're provide even better ground cover for the moss, and also make the ground a little more varied and interesting.
"He who can destroy a thing, controls a thing." --Paul Atreides, Dune
Tie it to a pole with a rope and let it mow circularly without human behind it.
https://lh5.googleusercontent.com/-ft5kOozZ9aM/TjJTKAgyTQI/AAAAAAAAFdU/5-zSQzE83dU/7492_18cc.gif
https://picasaweb.google.com/emil.oppeln.bronikowski/2011072802#5634657515195223298
A perfect mowing mows at every vertex exactly once. The perfect mowing exists if there is a hamiltonian path in the triangular grid graph on the lawn. In general the hamiltonian path problem is NP-complete even on the triangular grid graph. However [1] states:
A hamiltonian cycle in a connected, locally connected triangular grid graph (not isomorphic to D) can be found in polynomial time.
D is the linearly-convex hull of the Star of David. A polynomial time algorithm which is not exactly simple is available in [2]. It can be applied to solid grid graphs.
This approximately means if your lawn is not shaped like the Star of David and does not enclose any trees, bushes or ponds, you can implement the algorithm from [2] and get an perfect mowing path in polynomial time.
[1] Gordon, Orlovich, Werner. COMPLEXITY OF THE HAMILTONIAN CYCLE PROBLEM IN TRIANGULAR GRID GRAPHS
[2] W. Lenhart and C. Umans. Hamiltonian Cycles in Solid Grid Graphs
You just need to get the Google Mower 500! Actually, a friend developed an automated circular system using a self-propelled mower, a rope and a pipe. The mower was tethered to the pipe and as it moved forward it wrapped the rope around the pipe and was pulled ever closer. An egg timer solved termination by triggering manual intervention.
As a person who does lawn maintenance for a living I have found out one fact: the less you turn the better. I always begin by mowing the edges and odd parts of the yards to form a rectangle or square and go from there. You can mow much faster in a straight line than you can mowing in turns. Also when coming up against a tree, fire hydrant or anything in the lawn I always 2 do circular cuts around the object then continue on (saves time on edging later on, I work alone).
Keep in mind nearly all of my accounts are lawns (not fields), under 2 acres and residential dwellings. This is a living where time IS actually money. There faster I go, the more I mow the better I eat.
Love!
Unless you live in the US Midwest, where grasslands are natural habitat, you should plant some trees on that six acre plot of earth.
In most of the rest of the country, the natural habitat is NOT grassland, its either woodlands, desert, or wetlands.
If you simply must have grass, don't mow it a large portion of the six acres, let it mature into a semi-natural meadow.
If the Government becomes a lawbreaker, it breeds contempt for law;
I hate to intrude on your little fantasy with reality but there are plenty of public parks in the USA. When folks are referencing 6 acre plots of land for their home they are generally in rural areas. Such areas commonly have natural fields, woods, etc nearby so public parks are less of a necessity.
Perhaps you should consider that many people outside the US are misinformed regarding life in the US, just as many in the US are misinformed about life outside the US.
Get out more.
Goats.
"If any question why we died, Tell them because our fathers lied."
But this is slashdot so the geek solution would be more appropriate. Robotics. A "roomba" lawn mower. :-)
How much beer will be consumed during the mowing activity? Assuming you bring the beer with you in a small cooler (because who wants to walk across six acres just to get another one) will the mowing get done before the ice melts and the beer gets warm?
Anyone who has mowed the same lawn repeatedly knows that to mow it exactly the same way time after time damages the lawn. Any "optimal" solution will almost certainly be series of patterns mowed on the same lawn so as not to damage the lawn.
See section: Change Direction Each Time You Mow:
http://www.homeimprovementsdepot.com/lawn-mowing-tips-and-tricks-to-keep-your-lawn-green/
If you are talking about an irregular lawn (say, an H shape), mowing one half (in spiraling-out circles), then switching to cover the center section in as few passes as possible, then spiraling inward on the other half would seem to be the most efficient method.
Factor in a swath to return to refuel when needed. Also, other irregular shapes would add in more figuring (say, a |-|-| shape; mow one side, mow a swath to reach the far side across the top or bottom of the middle section, then finish in the middle).
I don't see how a computer algorithm would make this any easier than just figuring out the path in your head; an algorithm can't calculate in rest breaks, refueling stops, etc. any easier than common sense.
I spent my teenage years mowing my parents 3 acre lawn with a tractor and gang mower and always trying to figure out the optimum method. My favorite was the random swaths, but maybe not the most efficient. I think that got me interested in computer programming, algorithms, and graphic design. Remember, Philo Farnsworth invented television by looking at corn fields.
While I appreciate the mathematics and the problem involved, why the heck does the guy have a lawn so large that it take a full three hours to cut? This feels more like a "Hey look guys, I can afford a lawn that is so big, it take three hours to cut!" more than any sort of real request for help with the math.
Why would anyone want 6 acres of grass lawn!? Do some landscaping, plant trees and shrubs, make a walking path, add a rock waterfall with a small pond, anything to make the area more interesting! Grass is boring!! If you really want a boring 6 acre space, plant some ground cover that doesn't need mowing!
So these scientists basically do all this stuff, come up with a solution, and say it's easily solved with commonly used methods. Yet... you think the Slashdotters will come up with something better? Really? You do realize 99% of Slashdotters only know what they read on Slashdot, right?
Unless youre in the british isles you probably shouldnt have one of these. I hate invasive lifeforms. Hard to get more cardeinals when 50,000 starlings occupy each tree.
Though I think a specific form of invasive species is mostly responsible for this. Its just that reducing its numbers tends to make the internet angry.
To minimize the amount of time spent mowing, get someone else to do it, e.g. hire some neighbor's kid.
To minimize the amount of resources spent mowing, forego mowing entirely.
Would this be similar to a polygon flood fill algorithm?
http://en.wikipedia.org/wiki/Flood_fill
"I have a 6 acre lawn and I'm trying to take less than 3 hours to mow it."
A friend has a self-propelled mower tethered by a rope to a pipe located in the middle of his yard. The mower propels forward and slowly spirals in as the rope wraps around the pipe. He drinks a beer and enjoys mowing his lawn too.
All modern computer-aided machining systems have solvers for this problem. When you tell a CAM system to machine an arbitrary area, it computes a tool path to do the job. Here's MasterCam doing it. Even low-end 2D CAM systems can solve the lawnmower problem. High-end systems can solve much tougher problems, automatically deciding what tool to use, clearing big areas with big tools and finishing up the tight spots with small ones. The most advanced CAM tools can do that in 3D on very complex objects.
Consider a large, rectangular lawn that can be mowed with excellent efficency by going in long, parallel lines. If the lawn is large enough, turns and corners become negligible and the mowing time is dominated by the number and length of the lines. In the triangulation method, parallel lines have a significant overlap, so it is certainly less optimal than a rectangular pattern that offers zero overlap for parallel lines.
You may find the most efficient path for mowing, but it won't be optimal for the lawn. Grass should not be cut in the same pattern every time. It should be alternated between horizontal, vertical, and both diagonals. This helps keep the grass healthy and prevents it from beginning to lean.
I just patented 'A Method to Mow Lawns More Efficiently". Now, what again was your name and address?
Get some sheep or rabbits or both, and you won't need to mow and you'll keep your carbon footprint down. Lawns only appeared in the 18th century as a way for the elite to show off their wealth and that they were rich enough to have meadows that did not need animals to keep the grass down.
Mowing the lawn is the only time I can't hear my wife or kids. It's like meditation. "Leave Daddy alone - he's mowing the lawn"
Than I realized you are just another tool flexing their epeen with the "brand" they own.
*shudders* mowing a lawn is the most foolish bit of self-induced slavery I've ever been party to - and I vow, 'no mow no mo!'
It is a waste of my time to cut down carbon containing plant fiber to either a) mulch it back into the soil or b) send it to landfill.
It is a waste of fuel too, pouring all that fuel-carbon into the air, and damaging the ozone too (when you refuel and sunlight finds the fumes).
Instead, I garden. I grow vegetables and eat the produce. It is the best, freshest way to get your food. It is a relaxing past-time and can be done in a ultra-low-labor way (cover ground with weed barrier to avoid weeding labor, use simple metal stake and metal fencing to let your plants climb tall and not crowd each other while they maximize the sun engergy captured).
My former front lawn is flowers and berries to attract insect eating birds and pollenating bees too. My former back yard is vegetable plot, producing enough tomato, pepper, broccolli and cabbage to augment my own diet and that of four neighbors' for the summer, as well as allowing for preserved foods that last me into the winter and sometimes beyond.
If you don't need/want the food yourself, donate it to a local community program!
Grassed lawns are an archaic status symbol of european aristocracy. GET OVER IT ALREADY!
I see goats all the time here taking down high grass. This works well in CA because you only need to take the grass down for the dry season.
In climates with year-round rain, the goats would have to be trucked in more often.
If you don't want barnyard animals running around, my other suggestion is "plant trees". Mowing them is much less frequent, and much more profitable.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Why was this triangular grid chosen? Why do the circles overlap? If you mow in parallel runs you get constant overlap. Anyone could get a better result from any number of straightforward paths along a "square" grid without overlapping circles.
Like most algorithm articles, the solution is described but the mowing is left "as an exercise for the reader".
I love my lawn and it's 7 acres with forest around keeping the neighbors at a distance. Land is cheap around here so you easily can afford it.
If you never mow the same spot twice, you have 100% efficiency. There are plenty of ways to mow any shaped lawn without covering the same spot twice. heres an example
if its a square, circle the border and eventually make your way inwards.
if you have a series of interconnected areas, circle the radius of one sector at a time.
Eventually you hit an obstacle such as a small tree in your way. circle around it when you are near it. You're only visiting that location once.
seriously this is not that complicated. its how your parents should have shown you.
been doing this myself for quite some time, it's quite effective and makes a nice pattern of the outlines of the lawn and bushes spiraling towards a single point.. you have to carry the mower to it's shed to preserve the pattern tho :P(not worth it).... as any lawnmowing tho, it's booring as hell..
It's a fairly obvious solution. I always mow this way.
All pretty much the same problem. But as anyone who's driven a large tractor or even a riding mower knows, there's a limited turning radius. This discussion leaves this out (there are 0-turning radius mowers, though). Further, there's a desire when mowing to discharge over already-mowed areas (although some people like to keep pushing clippings to the center, it's hard on the mower), so you want to keep the path oriented properly all the time.
Optimal satisfaction with your zero-radius mower, and the fact that you bought it, requires that the number of U-turns be maximized.
I think this would be better classified as a "bridges of konigsberg" problem. Yes, Euler wrote a paper on it, and yes, people refer to at as an eulerian path problem sometimes.
But basically, the key to the problem is that you can only have an eulerian path in a "bridges of konigsberg" problem, if your number of vertices of odd degree (paths in/out is an odd number) is two or zero.
If the number of vertices of odd degree is two, you have to start at at one of them, and end at the other.
But that said, you can still minimize the path by successively cutting your areas in two, keeping the number of vertices of odd degree minimized. Then you only enter and leave that area an even number of times. Not that that solution generates the answer, but the answer will follow that solution.
Perhaps to help generate the answer, your cutting the area in "half" needs to zero the vertices of odd degree of one (non-half) piece, while minimizing the number of introduced vertices of odd degree of the other piece.
But ... that leads us back to a previous situation: In picking your circles of lawnmower width, there are an infinite variety of points to choose. Because of that, you should be able to keep your number of vertices of odd degree two zero. At that point, you should be able to generate a path through all of them, by basically splitting the area in two, and entering the area once and leaving it once.
Anyhow, I'd suggest that one should read "Euler's Gem". It's an entertaining read, which will then allow one to solve this problem (or more rightly, to identify this problem as already solved.)
I have ~6 acre lawn also and use a JD 855 to cut it. While the plot itself is rectangular, it is bisected by a curvy driveway.
Without using any mathematics, I arrived the fastest/most efficient route by analysis. It's very simple: The fewer turns you make, the more efficient the cut. For 2 reasons: Every turn follows a radius which introduces overlap of lawn already cut and for every turn you generally have to slow down - so the longer it takes. Leading to my one simple rule: Cut the largest number of longest swaths that you can without making turns.
Now because it's recommended that one should always change the cuts on the lawn, my most efficient time for 6 acres comes in at about 2hr:45minutes, my most inefficient cut (a diamond cut like you see on baseball fields) comes in at 3 hrs:45 minutes.
Perhaps you should consider that many people outside the US are misinformed regarding life in the US, just as many in the US are misinformed about life outside the US.
Amen.
I really need to get me one of those.
But I suppose I'd need my own house first though, huh?
What you're looking for is the shortest Hamiltonian path. Although it may seem like there is an efficient way to come up with the optimal solution, there isn't: it's an NP-Complete problem (it's actually the Traveling Salesman Problem.) There are great solutions which are less than optimal, but finding the best path where the number of vertices is greater than ~26 is too computationally complex.
BSD is for people who love Unix, Linux is for people who hate Microsoft.
Since it uses electricity, it will also be better for your environment compared to your 2 stroke mower that doubles as a gasoline evaporator. They are available from several companies in several prices.
If you got like the poster have to spend $3500 + gas and maintenance + salary to get your lawn mowed, there are really big ones available that will probably get ROI in 2-3 years. There's some mathematics for you.
Custom electronics and digital signage for your business: www.evcircuits.com
mow half an acre, declare the remainder a field and get two hours of your life back (unless that 3 hours is also therapeutic).
There are vertices that don't need to be visited at all because their circles are completely covered by surrounding vertices' circles, so a solution where every vertex is visited exactly once might not be the optimal solution.
Also, the start and stop points are given as well. That makes the 'well known computer algorithms' a lot more complex, so that we might end up with O(n^4) or even np-complete problems.
Funny how many Subjects get sarcastic DUMBASS comments.
SIN
TFA says "Clearly what is optimal for a lazy Maths Master is to push the lawnmower the shortest distance possible." and goes on from there.
While an interesting NP problem in itself, the things you're more likely to be trying to minimize are time, fuel, cost. Hence, turning matters significantly.
I know, I've spent lots of time thinking on this but through experience come to the conclusion that using long parallel strips as often as possible is easiest on mind and body because, finally, acceleration is also quite important.
You agree with me.
Integrated circuits have been called the most expensive "real estate" on earth, in terms of $$$ per square cm. It is rumored that Micron up in Idaho was successful in its early days as a designer of memory chips because they used their silicon real estate efficiently - just like the potato farmers all around them did.
If you want to learn about the most efficient manner of drawing tightly packed designs across a surface, ask an integrated circuit designer.
LawnBott LB3510 costs about $4,000. Assuming your time is worth $50/hour, at 3 hours a week that means you are spending $150 a week. You make your money back in 6 months.
excitingthingstodo.blogspot.com
who cares how long it takes......
Should be Burkard, not Bunkard. The guy teaches at my school
The math is fun here, thanks for the enjoyable distraction. Do you have a ZT or do you have to compensate for turning radii as well?
If you don't enjoy mowing, but like the big outdoor space there are some alternatives.
This year tilled up and reseeded the "grass" around my gardens with dwarf dutch clover. Best idea ever. Before It was a huge PITA to string-trim between the raised beds. I've only mowed it twice this year, and it looks great. In the spring we're going to replace the rest of the lawn with a dwarf clover and dwarf fescue mix.
Now I can spend my mowing time in the garden instead.
You know what?
I'm starting to get really really tired of the negitive replies in the "ask slashdot" articles.
Maybe the OP *likes* cutting his own lawn, likes the smell, or maybe it's an excuse to get out of the house.
Not everyone has the same values as you do. How about we start to respect that?
I live adjacent to a grass runway, and part of my responsibilities include mowing my section of the runway. Some of my neighbors are particular and for safety reasons demand the mowing occur lengthwise along the runway so you can see an airplane coming at you and get out of the way. This is a constraint that could be mitigated if I had 360 degree vision.
How do the authors address constraints like this?
Ross Youngblood
It's probably too late to get modded up so you can see this, but:
The technical term you are looking for is "coverage path planning", and there are well known algorithms to solve it efficiently such as Choset's Boustrophedon. I don't think any of them are optimal for a nontrivial shape, but they will probably beat most human heuristics.
In addition to lawns, this is important for machining (material removal), de-mining (completeness is essential, but overlap is expensive), and large floor cleaning.
http://scholar.google.com/scholar?q=coverage+path+planning
My intuition tells me that a spiral path would be so close to most efficient that it wouldn't make a significant difference if there was something more efficient. In a spiral you don't mow over previously mowed areas which is obviously inefficient and you don't have to do a 180 turn which I think is not perfectly efficient in terms of area covered. Maybe if the lawn had a really strange shape a spiral might have some inefficiencies. However I'd start on the outside edge and spiral inwards and otherwise not worry about efficiency.
One thing that might help would be to know how to steer the tractor so that you have the least overlap necessary between the newly mowed path and the adjacient previously mowed path. This could take some experimentation you might put some kind of flag to act as a "gunsight" on the front of the tractor and keep it lined up with the edge of the mowed/nonmowed areas.
But as for outside the box thinking, how many sheep could you support with six acres of grass? That might produce resources fertilizer, wool, meat, instead of requiring them. It would bring efficiency to a new level.
Goats are best, Sheep eat around stubborn grasses; horses make loblollys and cows are just trouble. Six acres is stupid huge for a lawn. Let 5 of it go to field and hay the thing. For the fastest time, mow the same pattern every single time; this is bad for your lawn. You should change up the pattern once in a while.
We have 10 acres in Iowa. A couple of years ago a large cigar shaped craft landed in the field. The next week, almost all the grass turned brown. We don't need to mow it at all now. So we think the optimal mowing pattern is to have a giant glowing ufo land on your land. Does this make sense?
If you really enjoy mowing then you want the least efficient path.
Dynamic Programming (http://en.wikipedia.org/wiki/Dynamic_programming) find the optimal path in any problem like this.
Assuming you set up the problem well, the DP solution is indisputably the best (proven mathematically).
It requires the problem to be modelled in discrete time and space i believe, but it looks like they're doing something like that already.
larger or more regularly (e.g. rectangular) shaped fields. It essentially guarantees an overlap of approx 13% (1-sqrt(3)/2) of the diameter of the lawnmower cutting circle, merely in an effort to reduce the overlap in the number of turns. If the same field was made larger, the 13% cost would far outweigh the gains made in reducing the turn overlap. A rectangular path would easily eliminate the 13% waste and then the problem could be reduced to minimizing the number of turns.
It may be the most optimal solution in terms of not covering the same place twice, but I'm not sure it is the quickest. I'm not bothered if I go over the same area twice, so long as I get the job done as fast as possible - making a turn takes time and there are plenty of those in the proposed solution. It may still be the quickest as some of those turns are quite small angles, but I think a 'turn penalty' is required to truly find the quickest solution.
Regarding search and rescue, the object there is not to cover the whole search area as fast as possible. It is to cover the most likely locations for whatever is being sought as quickly as possible, and then cover the more unlikely places. For a static location that might mean starting in the middle and tracing a spiral. However, for someone falling overboard at sea, retracing the ship's path at close to it would be a higher priority than a simple spiral from any point.
I've got a fair sized lawn that takes me 6 hours to mow with a push mower so I think about this a lot... What I like to do is mow the edges and around obstacles first getting unmown rectangles, rounding off the sides of the rectangles, and then going around the rounded shape non-stop. The rounding off of the edges saves a lot of time that would otherwise be spent stopping and turning around and lets me just go continuously.
1 - get a life
2 - stop wasting earth's finite resources. get a grass eater. plant tress - less grass.
I would love to use a genetic algorithm for this. The problem I've always had with GAs is the way you represent the problem so that you can use GA techniques such as mutation and crossover. Converting the space into circles and then in turn into triangle facets is one option. That then gives you a problem that is not too far away from the Traveling Salesman problem.
The real question is: Will the time you save generating the "perfect" solution out way the time you spend finding it? I see this issue all over bluishness and IT. The developers want to move to a modern language as the program will perform faster, reduce bugs and provide a better product. But after spending time converting all the old software, training all the staff etc would it have been better to just spend extra time on the old product?
It's not an easy yes/no question as theres a lot of dependences involved, but with a bit of investigation and mathematics you can work out some rough numbers to help you decide:
Lets say a GA (or other algorithm) comes up with your optimum solution. Lets say it's so good that you save 30 mins every time you cut your lawn.
Lets also assume it took you 5 hours to investigate possible solutions and then a further 5 to implement that solution.
The first few times you cut your lawn (lets say 3) it actually took you longer to cut the grass as you were learning how to implement the optimum solution.
Assuming 30mins extra each time up to the point where you are ready to cut your lawn in 2h30 (instead of 3) you have already spent 11h30m extra.
So we need the optimum solution to at least save you that time in the future.
11h30 = 690m :D
690/30 = 23.
23 + 3 (change over cuts) = 26
So there we have it (using countless assumptions and estimates based on thin air) we have worked out the magic number: 26.
If you are likely to need to cut your grass 26 more times then you will have saved time. Every cut after that is time you are saving yourself
Of course none of this accounts for the fact that the investigation and creation of a solution could be considered a "god use" of your time. As you know have the knowledge to solve similar problems. For example, shaving your beard, eating a pizza, painting a wall).
It turns out, as usual, it's very difficult to isolate a real life problem, then solve it and then prove without doubt that it is better.
Good luck.
I cut lawns and fields for a living. The larger the area to cut and trim, the less money I make. Most of these rich guys are cheap when it comes to hiring me to cut their huge lawns that are littered with trees and flowerbeds. Trimming takes more time due to the area I have to cover on foot. Some places take me 45 minutes or more to trim. Paying me $100. to cut their estate is half what it should be. I can make much more money per day cutting $40. smaller city-style lots than these cheapos who expect perfection. There is no way a pro-cutter would ever do circles to save a little time. Straight lines is the way to do it if you want the property to look good. The cheapos would freak out if their fields/lawns where cut in circles.
Buy a goat.
Plant wild flowers, or no mow grass(yes it exists, and works great)! -You will save $ on gas -pollute a lot less! (mowers are some of the least efficient motors around) -Make more fresh air -looks a lot better -get some nice birds, butterflies and such. -Gain 3 hours a week back. You can do a ton with that. And If you must mow, make a solar powered lawnmower with a server battery and starter mower like I did!
...is the dumbest thing yet, I have seen on /.
The easiest way to mow a lawn:
Step 1: Buy one of these: http://www.robotshop.com/ca/ka-lawnbott-lb1200-spyder-robot-lawn-mower.html
Step 2: Turn it on
Step 3: Put feet up
Having mown lawns professionally for many years, I should add that time alone is not the only thing you might want to optimize. I would usually mow the irregular portions around the perimeter of the yard first, so that I could zone out and not even have to think about where I was going or what I was doing, once this was done. For me, it wasn't the actual time, but the perceived time, which made the difference. Rectangular areas with left-hand turns are optimal if the self-propelled lever is on the left side of the mower. If you have a riding mower with zero turning radius, then everything changes.
I helped create an autonomous lawnmower prior to my Masters.
Here are the remnants of a powerpoint we put together, if anyone cares to look at it.
http://edge.rit.edu/content/P06113/public/technical.html
When we changed our mowing pattern algorithms from pure pursuit to carrot, it had caught on fire...Power mosfets blew due to a few situations where the wheels tried to rotate back and forth too quickly. Nonetheless, getting the mower to make a nice looking lawn was a real challenge.
-John
I've always mowed my lawn in a spiral that starts at the outer edge and works in a spiral towards the center. It's irregularly shaped, but there is little overlap.
I see the article proposes a solution which cuts (pun intended) about 1-2% of the time off of a spiral. When I'm cutting my lawn, I want to get it done, not do complex math during the process. A contracting spiral is obvious and effortless.
Seems like your post (your question) is a direct hit on the same spot where I was going to post my request. ;) ...or... prove me wrong.
Break down your lawn into small squares, load coordinates into my excel spreadsheet and off you go...
I need a partner to scale my algorithm, please help me.
My algorithm files are linked to my blog here: http://ctsps.blogspot.com/2011/08/tsp-cyclical-solver-lets-roll.html
I should've renamed it to Moving Lawn Mover's Problem though... ;)