Skip to content

Optimal Cleaning Paths

Yesterday I twittered:

Doing too much operations research. Spent more time figuring out optimal mowing pattern than mowing lawn.

roombaToday, I came across a picture of a Roomba’s path to clean the floor of an l-shaped room (through a number of sites, but I think I am referring to the original). I think I am a little more efficient in lawnmowing, but, then again, I know the shape of my lawn: Roombas figure out the shape dynamically. Interesting OR problem to come up with the optimal Roomba algorithm.

{ 5 } Comments

  1. Larry (IEOR Tools) | May 10, 2009 at 9:59 pm | Permalink

    What could be fun is deciding the objective decision criteria for the Roomba. Shortest path? Fastest time to clean the room? Best path to minimize battery usage? Optimal path to and from charging station? This sounds like a fun introductory OR lesson.

  2. Matthew Saltzman | May 10, 2009 at 10:37 pm | Permalink

    Funny, mowed the lawn this afternoon, and distracted myself thinking about the very same thing. Got done much sooner than if I’d solved the path problem and then followed the optimal path…

    Satisficing *is* optimizing!

  3. Greg Glockner | May 10, 2009 at 11:08 pm | Permalink

    If I understand correctly, the Roomba’s algorithm covers the area as many times as possible over a battery charge cycle. This is its heuristic to clean a floor as thoroughly as possible. However, it also gives a chance that some areas will receive little or no cleaning.

    Search Google for time lapse roomba video and you’ll see some examples.

    I don’t think this is as desirable for mowing lawns. You don’t need to cover the same area multiple times, while missing some grass could lead to an unsightly lawn.

  4. Ian | May 11, 2009 at 4:57 pm | Permalink

    There are a couple of robotic lawn mowers out there: robomow and lawnbot. I think you bury a guide wire to provide them with boundaries. I have heard they’re slow (so out working your lawn a lot of the time) and the cut can be a little uneven, so not ideal if those are your objectives. Payback period is supposed to be around two years. But for minimizing emissions and the time you spend mowing, these are the way to go.

  5. Hypnosis training | May 18, 2009 at 3:29 pm | Permalink

    This headline from The Onion: “Suicide prevented by video of kitten riding Roomba”. Love the picture, not sure I””m sold on the concept. I mean, you wouldn””t want to leave a stamp collection lying around. /// Some years ago a lawnmower manufacturer designed a robot lawnmower on similar principles – the mower would live in a docking/charging station, coming out to mow the grass at programmed intervals. Great in theory, but it did have some EMC issues where mains spikes would spontaneously turn the thing on and it would go haywire, chewing up all in its path. There””s a bad B-movie in there somewhere.