Monday, 19 November 2012

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.

2 comments:

  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.

    ReplyDelete
  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...

    ReplyDelete