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.

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

      Delete
  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
  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!

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

    ReplyDelete

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

Attiny85 timer programming using Timer1

This Arduino sketch uses Timer1 to drive the LED blinker: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 /* * Program ATTiny85 to blink LED connected to PB1 at 1s interval. * Assumes ATTiny85 is running at 1MHz internal clock speed. */ #include <avr/io.h> #include <avr/wdt.h> #include <avr/sleep.h> #include <avr/interrupt.h> bool timer1 = false , led = true ; // Interrupt service routine for timer1 ISR(TIMER1_COMPA_vect) { timer1 = true ; } void setup() { // Setup output pins pinMode( 1 , OUTPUT); digitalWrite( 1 , led); set_sleep_mode(SLEEP_MODE_IDLE); // Setup timer1 to interrupt every second TCCR1 = 0 ; // Stop timer TCNT1 = 0 ; // Zero timer GTCCR = _BV(PSR1); // Reset prescaler OCR1A = 243 ; // T = prescaler / 1MHz = 0.004096s; OCR1A = (1s/T) - 1 = 243 OCR1C = 243 ; // Set to same value to reset timer1 to

Hacking an analog clock to sync with NTP - Part 5

This is how it looks after I have put everything together. The Arduino sketch is available here . The 2 jumper wires soldered to the clock mechanism are connected to pins D0 and D1 on the ESP-12 (in any order). When the device first boots up, it presents an access point which can be connected to via the PC or smartphone. Once connected, the captive portal redirects the web browser to the configuration page:     A custom field has been added to the WiFi configuration page to enter the current clock time in HHMMSS format. Try to set the clock time to as close to the current time as possible using the radial dial at the back of the clock so the clock will have less work to do catching up. In the config page, the HTML5 Geolocation API is also used to obtain your current location (so if your web browser asks if you would like to share your location, answer "yes"). This is then passed to the Google Time Zone API to obtain the time and DST offset of your time z