Skip to main content

Roomba navigation algorithm

I have been a long time user of the Roomba vacuum robot, starting from version 1 till now. It has made a big difference to my life, and I enthusiastically recommend it to all my friends.

One thing that stands Roomba apart from other vacuum robot is its navigation algorithm. There is no high-level mapping involved. Instead it uses localized decision making, much like how insects forage for food:

Our robot 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.
The algorithm is actually quite effective and robust in the real world. For a short while, I used to house two cats in a room, and you can imagine how dusty that was. Roomba never failed to clean up the room for me after I left it to its devices. It was squeaky clean after each session, and all I had to do after that was to give the wooden floor a quick mop.

Don't take my word for it. Check out this video providing a time-lapsed coverage test of various vacuum robots, including The Roomba 5 series.

However, I never fail to notice, both online and off, how Roomba's navigation algorithm invokes all kinds of negative feeling in users. Comments typically are of the types:

... It is just going in random directions
... Personally I will not vacuum like that
... Why does it go over the same area twice?
... It is not very efficient, it takes too long 

I have seen people just standing there and supervising/criticizing their robot's every move! This is crazy! Do you stand there and supervise your washing machine? I mean, you just dump your clothes in, set a wash cycle, and come back in 45 mins or whatever. What's so difficult about that? Instead you have people just hanging around and second guessing every move the robot makes. Absurd!

I can understand maybe a robot vacuum cleaner is something new to a lot of people, it hasn't become quite as mundane as a washing machine. Or maybe a localized or bottom up algorithm is just harder to understand/accept compared to a top-down algorithm. Rodney Brooks, the co-founder of iRobot, the company that makes Roomba, is a pioneer in the field of bottom-up robotics. He famously created robotic insects that do not have a central "brain", but instead make localized decisions based on the feedback from various sensors (much like the Roomba). In the physical world, that approach turns out to be extremely robust and resilient.

AFAIK iRobot has never organized any campaign to dispel such negativity. I guess maybe it is just too difficult and technical to make people understand that a bottom-up approach is superior to a top-down (mapping) approach. I hope I can make a small difference by blogging about this here. Roomba's navigation algorithm in the real world is robust. You can move furniture around while the robot is running and not have to worry that it won't come back again. You can let it bump into your foot if you are doing stuff in the same room while it is running, but you can be assured that will not have a large impact on what it is doing.

You don't want a robot to vacuum like you do. Otherwise, cars will have legs, and washing machines will have arms. Just clear the room, set the robot down, let it run, grab a cuppa and come back an hour later. The room will be clean. Trust me.


  1. "... It is not very efficient, it takes too long "

    Well it isn't efficient. It might be effective, but it's more than valid to question efficiency. It could clean more space on a charge, make noise for less time and use less power. It could be much better. Valid criticism, not crazy criticism as you suggest.

    1. You've made one major mistake in your thought process here: you've assumed the person critiquing it analyzed the "it takes too long" like you did. Chances are, they didn't.

      You're also making the mistake about not factoring in the time you, as an individual, have freed up by using the robot. Efficiency only matters if you're doing something in serial. Most of the time, you're not 1) vacuum floor, 2) play on floor. If that were the case you'd do it yourself. You use the robot to free up time.

      Use less power? Please, shallow critique.

  2. Except the price of the mapping machinery, and the computer power necessary to implement it, will drive it off the market.

    You can buy them now on Craigslist for fifty bucks, running.

    I love the bottom up algorithm. We need them in government now...

  3. Thank you, I just bought one and I've been looking for some explanation, I knew these were good cleaners, but now that I have one it is amazing, of course the first day I was looking at the robot doing his job and questioning myself the investment but after that first day I knew it was a good purchase, the algorithm really works!

  4. Actually the most efficient way is to not vacuum or sweep. But that gets a bit messy. Yes, a smarter robot vacuum can be built. At two or more times the cost in money and power consumption. The older 618 my sis got me for my birthday does a great job! Why fix it if it ain't broke?


Post a Comment

Popular posts from this blog

Adding "Stereo Mixer" to Windows 7 with Conexant sound card

This procedure worked for my laptop (Thinkpad E530) with a Conexant 20671 sound card, but I suspect it will work for other sound cards in the Conexant family. I was playing with CamStudio to do a video capture of a Flash-based cartoon so that I can put it on the WDTV media player and play it on the big screen in the living room for my kids. The video capture worked brilliantly, but to do a sound capture, I needed to do some hacking. Apparently, there was this recording device called "Stereo Mixer" that was pretty standard in the Windows XP days. This allowed you to capture whatever was played to the speaker in all its digital glory. Then under pressure from various organizations on the dark side of the force, Microsoft and soundcard makers starting disabling this wonderful feature from Windows Vista onwards. So after much Googling around, I found out that for most sound cards, the hardware feature is still there, just not enabled on the software side. Unfortunately, to

Hacking a USB-C to slim tip adapter cable to charge the Thinkpad T450s

This hack is inspired by this post . A year ago, I bought an adapter cable for my wife's Thinkpad X1 Carbon (2nd Gen) that allows her to power her laptop with a 60W-capable portable battery (20V x 3A). A USB-C cable goes from the battery into the adapter, which converts it to the slim tip output required by the laptop. Everything works out of the box, so I didn't give much thought about it. Recently, I decided to buy a similar cable for my Thinkpad T450s. I know technically it should work because the T450s can go as low as 45W (20V x 2.25A) in terms of charging (though I have the 65W charger - 20V x 3.25A).  I went with another adapter cable because it was cheaper and also I prefer the single cable design. So imagine my surprise when the cable came and I plugged it into my laptop and it didn't work! The power manager just cycle in and out of charging mode before giving up with an error message saying there is not enough power. After much research and reading the Thinkwiki

Using Google Dashboard to manage your Android device backup

I used to use AppBrain/Fast Web Install to keep track of which apps I have installed on my phone, and to make it easier to reinstall those apps when the phone gets wiped or replaced. But AppBrain had been going down the tubes, and Fast Web Install had always been a hit-and-miss affair. Android's own "backup to the cloud" system had previously been even more unusable. There isn't a place where you can see what has been backed up. And when you setup a new phone with your Google account, you just have to wait and pray that your favorite apps will be restored to the phone. Typically all the stars have to be aligned just right for this to happen. More often than not, after waiting for an hour or so and nothing happens, you just curse under your breath and proceed to install your favorites apps manually via the Play Store. But I just looked again recently and was pleasantly surprised that things are much more civilized now. Firstly there is a place now where you can loo