lawn mowing problem / algorithm, part 1 Nov2007

I live in a suburban HOA controlled neighborhood just north of Austin. This means I have to mow my lawn or I get nasty letters from the home owners association telling me that my inability to mow my lawn as frequently as my retired neighbor (hi Dennis) causes the HOA to be ugly. The letters aren't so bad, but I secretly think they club a baby seal each time they send me a letter, so for the sake of the baby seals, I try to mow my lawn.

As I'm mowing my lawn, I frequently wonder to myself if I'm doing it the optimal way. Should I start near the sidewalk and work my way across the yard vertically? Does going horizontally from the side of my house really make a difference?

I began to think of this issue in an algorithmically (is that a word?) manner after about the 5th time I'd mowed it. This is my first home, I figure I have 30 years of lawns ahead of me. NOW is the time to solve this issue for every house I may own in the future.

After much thought (and sunny days behind the push mower) I realized I needed to treat the yard as a graph of nodes, where each node represents a certain chunk of the yard. Video games do this with tiles and will use something like Djikstra's shortest path to determine object collision. This is close, but I wanted something more like Prim's Spanning Tree, which will hit every node in the graph. Unfortunately, a spanning tree isn't the precise answer either. I really needed something more like a trail through my graph that minimized or didn't repeat any node visitations, because why would I wish to mow portions of my lawn twice? The spanning tree may cover every node in the cheapest overall way, but doesn't guarantee me the fastest/cheapest way through the tree w/o repeating edges (connections between nodes) or nodes.

So, here's what I've got so far. If you look at the picture below, it's sort of a simplistic view of my front yard, just broken up into tiles.

lawn tiles

Above, the tiles A-I are nodes, or just blocks of yard that require mowing. If you notice the "bone" shaped object spread across nodes A-F, that's some landscaping bricks and other plants that I don't mow over (at least not when the wife's looking...). The blue lines are edges between the nodes linking possible entries into that node from other nodes. If you notice, I can get to node B from node A, but not any other node. That's because the landscaping blocks it. Also, I can get to node E from F and H only, again, due to landscaping. Btw, you may be wondering what about diagonal edges - well, good question. The answer is that I'm just lazy and didn't feel like drawing those -- meaning they could be used also.

Below is a more traditional way of viewing a graph. Each node below has a corresponding node in teh tiles image above and the same edges (or connections to other nodes).

lawn graph

I think in my next post, I'll go into why a spanning tree won't really work, and a possible way I'm thinking of getting around the issues.

keep in mind the practical application and limitations here. Each node in the yard will have a "cost" associated with it. Maybe the grass is higher there.. who knows. Also, each entrance into a node and corresponding exit also has a cost. It's preferable to turn the mower 90 degrees instead of 180 degrees, etc. So If i constantly enter a node and do a uturn to get out of it, that's sub-optimal. For these reasons, I need a different way of calculating the costs associated with entering a node.

Granted, there could be a solution for this problem already and I've not found it in my (limited) googling. This is the kind of problem I think most about while I'm pushing the mower, I haven't spent a great deal of time looking for algorithms so far.... perhaps I'll also do a quick survey of those as well for the next post.

Anyway, this is just the initial presentation of a problem I've been pondering a while, and decided to share. Hope you enjoy thinking about it now, as well, and happy mowing!

These thoughts are my own, unless they're yours. And if they're yours, we may have metaphysical problems beyond simple concept ownership and should probably talk soon.
[login]