Wednesday, December 14, 2011

Room-Bore-Rhythm - Roomba's traversal algorithm


We have had Miss Roomba as our cleaner for over 2 years now, and she has played an important role in my life. Her availability and ability has been partly responsible for my obesity. I have been obsessed with trying to understand her algorithm for floor coverage and have spent hours on the couch fascinatingly watching her in action. I am enamored and at the same time intrigued by this sexy little cleaner.

As far as getting the job done is concerned, she is very adept and efficient. If you wanted a number to quantify her performance, I would say she is about 95% efficient. To put that number in perspective, a human being with good eyes using an average vacuum cleaner is about 90% efficient, which is same as a human being with OCD and bad eyes. An human being with OCD and good eyes is about 80% efficient, because at some point they forget all about the actual purpose of the exercise and become obsessed with organizing the collected dirt in a desired pattern. In short, Miss Roomba is an efficient cleaning machine.

Most vacuum cleaners have to be grabbed by the neck and subjugated into cleaning a room, which they then proceed to do with great reluctance and greater noise. Miss Roomba operates unassisted once a few appropriate buttons on her head have been pressed correctly. You can also give her a cleaning routine for the week and she will remember that and execute it correctly unless there is a bug in her clock which makes her go faster or slower than the rest of the world. In one sentence, Ms Roomba is awesome. She is the best gift you can give to a lazy person who wants his room clean.

But lets consider a different metric - area covered in sq. ft/time taken in seconds. By this criteria, the Roomba will qualify as arguably the slowest vacuum cleaner ever made, even if one were to include the earliest model built by the cavemen in Peru - body made from the skin of a bear wrapped around the rib-cage of a goat, the bag made from the stomach of a pig and the handle from the tusk of an elephant, and operated by wind-power.

Here is the simplified version of Roomba's floor traversal algorithm (with edge cases, error handling and boundary conditions left out for brevity):
1. Select a random integer between 1 and 10 (let's call it x).
2. Select a random integer between 0 and 155 (let's call it y).
3. Select a random integer between 30 and 60 (let's call it t).
3. Turn around y degrees clockwise and travel x feet.
    3.1 If the path being traversed has dirt, clean it.
    3.2 If you encounter obstacles or bump into walls, stop and go to Step 1.
4. If the time elapsed is greater than t minutes, stop and declare success, else go to Step 1.

The closest analogy to Roomba's path traversal is how my one year old baby girl walks. She just gets up and goes, in an assumed angle for an assumed distance, bumping into every obstacle in her way, and bouncing off of every wall she encounters. When she does that, she falls down, stares at me to see my reaction. If my face registers shock or fear or concern, she starts bawling her eyes out. If not, she gets up, picks two more random numbers and off she goes again.

Now that Neato has finally designed a Robotic vacuum cleaner with a laser guidance system which makes a map of the room before it starts cleaning, iRobot might have to try and upgrade Roomba's algorithm to at least match the walking patterns of my four year old boy. I think just doing that will decrease the time taken by the Roomba to traverse a room by a factor of 10.

But if that happens, the novelty and charm of watching Miss Roomba in all her fumbling, bumbling glory will be lost.