roomba algorithms

I purchased a Roomba last week to help me keep up with two kids and one cat. Watching the Roomba is like watching a Zamboni: I can’t take my eyes off of it.  My Roomba has quickly become part of the family–my kids even pet it.  I suspect that people make videos of their Roombas and post them to youtube along with videos of their children (I subsequently checked: there are 6,520 of such videos on youtube alone).

What intrigues me about the Roomba is that it is inefficiently efficient.  The whole idea is to clean the entire floor before the battery runs out by covering and recovering different areas.   It can only cover the entire floor by doubling back over areas it has already cleaned. But it just can’t meander all over the place, since it has a finite battery life.  It needs to cover the floor in a relatively short amount of time.  And, amazingly, it really covers the entire floor’s surface.

I wonder about the Roomba algorithm, and a google search indicates that many resources out there to find out more. An interview with iRobot (the company that makes Roombas) executive Nancy Dussault Smith sheds some light on the Roomba algorithm (emphasis added):

[The Roomba] computes its algorithm 67 times every second, constantly stitching together information about its environment and recomputing its path. When it starts you’ll notice a spiral pattern, it’ll spiral out over a larger and larger area until it hits an object. When it finds an object, it will follow along the edge of that object for a period of time, and then it will start cris-crossing, trying to figure out the largest distance it can go without hitting another object, and that’s helping it figure out how large the space is, but if it goes for too long a period of time without hitting a wall, it’s going to start spiraling again, because it figures it’s in a wide open space, and it’s constantly calculating and figuring that out. It’s similar with the dirt sensors underneath, when one of those sensors gets tripped it changes its behaviors to cover that area. It will then go off in search of another dirty area in a straight path. The way that these different patterns pile on to each other as they go, we know that that is the most effective way to cover a room. The patterns that we chose and how the algorithm was originally developed was based off of behavior-based algorithms born out of MIT studying animals and how they go about searching areas for food. When you look at how ants and bees go out and they search areas, these kinds of coverage and figuring all of that out comes from that research. It’s not exact, obviously, I’m not saying we’re honeybees, but it’s that understanding of how to search out an area in nature that is the basis behind how our adaptive technology is developed.

I’ll also refer you to Mike Trick’s post on Roomba path algorithms and HowStuffWorks on Roomba algorithms. An illustration of the algorithm is posted below, using time-lapsed photography.

Time lapsed roomba path

About these ads