Let me end with a spoiler: The correct way to mow your lawn is to pay someone else to do it. Period. But I'm a data scientist so I'm going to show you how to spend all your time planning how to do it instead. You won't actually get to start mowing because this method takes more time than you'll spend mowing your lawn all summer. Possibly literally.
In the code in my Jupyter Notebook you won't see the function laid out in this way. I actually just filter out the edges that aren't adjacent to each other.
In the case where both edges are not activated, the associated turn is forced to zero (-1 <= 2x <= 0). When one edge is active but the other isn't we also get the turn variable pinned to 0 (0 <= 2x <= 1). Lastly, when both edges are active the turn variable must be active because 1 <= 2x <= 2
I hate mowing so I sat down to plan out how to minimize the amount of time I spent mowing. This planning time of course was a thinly veiled attempt at procrastination thus it's actually a multi-objective optimization problem and solution.
What interested me in this problem was finding a real world use case for solving some small versions of the Traveling Salesperson Problem. I also thought the wrinkle about minimizing turns was an interesting modification to figure out.
Mow Like a Salesperson Travels
The optimal mowing path can be solved as a Traveling Salesperson problem. The idea is that your path starts and ends at the same point and you never visit the same location twice.
In addition to this though, I added an additional cost for turning the mower. The damn thing is heavy. I ain't turning it left and right like a jackrabbit. I'd like to keep my path as straight and comfortable as possible.
Let's talk about how to set this up.
- First, this is a mixed integer program. If you don't know what that is, stick around. This whole post is about that.
- We need to define an objective function. I could measure how much distance one travels... but every solution will cover the same distance since they cover the whole yard and never cross. I add in counting turns as well. Different plans can vary wildly on this front.
- We'll need some assumptions/constraints:
- First, I'm gonna assume my whole yard can be represented as square tiles of grass. It's the decision scientist's spherical cow.
- Every possible path one tile can take to its adjacent tiles (immediately up, left, right, and down from it) will be individual variables.
- Every possible turn from each tile will also each be a variable.
- Next, I'm going to require that every tile lead to exactly one other tile.
- Also each tile should be lead to from exactly one other tile. That means we'll have two constraints for every tile.
- No tile can lead from itself to itself. That's just lame.
- There can only be one continuous uninterrupted path across the tiles. This is the hard part.
- Lastly, we'll need to use lazy constraints to handle that last constraint. Basically, we'll solve the problem using a mixed integer solver then, we'll check to see if we have more than one cycle (or sub-path). If we do, we'll add each as a constraint and then resolve the problem.
That's all there is to it! I'm just joking. It's a lot of work and the algorithm takes forever to run. Literally as I sit here typing this the solver has been running for 15+ hours. The best solution I've had so far has only two cycles:
Really quickly let me explain this. This is a janky top down view of an approximation of my house and yard. Each red square is what I call a "BlockedTile" in my code (you'll see that called out when I link to my github). The green dashed grid represents grass tiles and the black line represents the path of my lawn mower. That big red blob is my house and driveway together. The small red areas are trees/shrubs and garden areas. Can't mow those. Unacceptable penalty cost of divorce.
Modeling the Problem
Most of these constraints I think are pretty straight-forward once they're explained so I'm going to spend more time on the one that was tricky, the turn count, and how I generated the constraints.
Here's the problem in math along with some explanations of what each bit means:
We've got a few concepts to define:
- Each location is an (x, y) pair that maps to one specific tile in the given grid.
- An edge is the direct path between two given tiles (i, j). In our example, there can be an edge only between tiles that are immediately adjacent to one another. Their sides or top/bottom must be touching.
- A turn is represented as two edges (i, j) who meet at a corner. More specifically this requires that the three distinct locations required to define the turn do not all have the same x locations or y locations.
With that hopefully I'm explaining it well enough that you can map those concepts to the math below:
So just to summarize: A turn is a 2-tuple of edges. Edges are a 2-tuple of locations, and locations are (x, y) coordinates (basically).
Next let's use these variables to define our constraints one by one:
Each location j must be entered from exactly one other location (any i in L that's adjacent)
And each location must leave via exactly one edge (that's adjacent)
Next we need to make sure locations don't loop back on themselves.
We need to be able to count how many turns exist in our solution. This constraint handles this. I'll explain why after giving you a chance to digest it.
Lastly, we need to make sure we have no cycles. In other words, there should be one long continuous path. We can enforce this by solving our current model, then searching the solution for cycles and then adding constraints to prevent those before re-running the model. We can repeat this over and over until we find a solution with no cycles.
The notebook linked to below shows how this is all implemented.
We've got a solution with just two cycles so I'm going to call it good. On top of writing the model and blogging this, it took 15+ hours to get to that solution so it's too late to mow now.
If you'd like to dive deeper into the notebook I've posted it on Github. Note that it requires PyGurobi (and thus Gurobi) to run. You may need to install a trial: