Making roomba smarter

[Cogman]

So I was reading up on roomba and its compatition the trilobyte, and I just can't help but wonder "Why does roomba have to be so dumb". Yes, it keeps the costs down. But why can't they find somewhat of a middle ground.

For example, mapping out a room doesn't need ultrasonic soundwaves to instantly tell what the environment looks like, instead, simple optic mouse tech can tell the roomba how far it has traveled (on a 2d coordinate system) Flash memory is certainly cheap enough to give the roomba a pretty good idea of where it has or hasn't been, and 2d mapping problems arn't entirely too hard. Heck, you could even have roomba do a quick trial run of a room, save the map generated from all the bumps, and then do some math while charging to determine the best route to take to clean the whole room the next time.

Am I on to something here?

 

[silverpig]

You want the roomba to solve the travelling salesman problem?

 

[Cogman]

Originally posted by: silverpig
You want the roomba to solve the travelling salesman problem?

Does it have to? We are talking about covering an area not choosing the fastest route given waypoints.

Think of it like a 3d game, there are vectors that determing where a two lines intersect, the roomba can basically get these vectors by running into walls and connecting the dots. After that, the resulting area between the dots is where the roomba has to cover, the easiest method for that is probably a back and forth motion. The roomba is already capable of finding walls and running along them, so why not take it the extra step and map out where the walls are?

 

[Born2bwire]

Originally posted by: Cogman

Originally posted by: silverpig
You want the roomba to solve the travelling salesman problem?

Does it have to? We are talking about covering an area not choosing the fastest route given waypoints.

Think of it like a 3d game, there are vectors that determing where a two lines intersect, the roomba can basically get these vectors by running into walls and connecting the dots. After that, the resulting area between the dots is where the roomba has to cover, the easiest method for that is probably a back and forth motion. The roomba is already capable of finding walls and running along them, so why not take it the extra step and map out where the walls are?

I know a grad student who's MS thesis was just that, using a laser scanning device on a RC car to automatically map out a room/hallway. It was not easy and I'm not sure if he ever got it working well. You have to come up with the appropriate filters to construct the walls off of noisy data (and this was with a laser device designed for this kind of application, forget about using mouse laser optics). You need to decide if the new reading of a wall close to an old wall is in fact the new wall or the old one. You have to be able to take into account a changing environment (objects moving around as you clean). You have to be able to accurately track your movements, using local feedback and the feedback from determining your position in the room from the mapping device. I've worked in a lab that dealt with control theory using hovercraft and these aren't easy things to do, especially with cheap devices. Webcams have large distortion in their video making it hard to use them as an optical feedback device (you have to map the distortions and apply the appropriate filters, but then you have a variations in the resolution across the picture). Cheap accelerometers have drift, and etc.

It was my understanding that the Roomba does retain maps of the rooms that it cleans. It physically maps out rooms via touch or other collision sensors and that it saves the room data. The more the Roomba runs the same areas the more confident it becomes with its map.

 

[degibson]

I have to agree with Born2bwire and silverpig -- it doesn't sound too bad, but it is actually computationally very difficult to do. By 'difficult' I mean its quite hard to find an algorithm that outperforms random search.

As an aside, I once had a blind dog who was pretty much just like a Roomba... he would just walk around until he bumped into something, then walk in a different direction. He would learn about rooms, gain confidence, and pretty soon he'd be running all over the place. Of course, he got pretty confused when we'd move furniture or something...

 

[CycloWizard]

What is the objective of the Roomba? I assume it's to clean your floor without outside interference. You could formalize this by saying that the time/power consumption required to clean the entire floor should be minimized. This isn't exactly the same as a traveling salesman problem and actually could be solved exactly using linear optimization for many cases. However, add strangely shaped walls and furniture and the solution space will often become nonconvex, making the solution much more complicated. It could be that the only way to guarantee that the entire floor is cleaned is to use a simulated annealing approach, which is only deterministic if the time allowed is infinite. Still, with some moderate assumptions, there are a variety of optimization techniques that should allow a fairly rapid, fairly complete cleaning of your floor. The most efficient methods would probably be either a pattern search or an AI/neural network approach where the cleaner could actually "learn" how to clean your floor.

 

[degibson]

I disagree, CycloWizard: Optimization problems have a lot of trouble with noisy data. You must consider that the Roomba never knows its own position accurately, and will receive various false positives from people, animals, and rabid dust bunnies. I like the simulated annealing approach, though again I'm not sure how to adapt it to deal with noise on its inputs. It also seems to me that there is no good way to evaluate the solution without human interference (hence no feedback to annealing) since the Roomba cannot know when the room is clean (again, because it doesn't know its own position accurately).

 

[Modelworks]

The real contender would be optical.
Using a webcam with just B&W images to determine where to go.
That would require more processing power though and the cost would be much higher.
There are people into hobby robots that already are doing this.

 

[degibson]

There are plenty of challenges in computer vision that come to mind with optically-driven robots, but I think it would improve the roomba overall -- especially the relative positioning.

Light changes over time would be a problem, as well as people or animals walking around, but I think they could be overcome, again with time given to the Roomba. Processors are pretty cheap, and it would probably be OK to give the little guy a few seconds per snapshot.

 

[CycloWizard]

Originally posted by: degibson
I disagree, CycloWizard: Optimization problems have a lot of trouble with noisy data. You must consider that the Roomba never knows its own position accurately, and will receive various false positives from people, animals, and rabid dust bunnies. I like the simulated annealing approach, though again I'm not sure how to adapt it to deal with noise on its inputs. It also seems to me that there is no good way to evaluate the solution without human interference (hence no feedback to annealing) since the Roomba cannot know when the room is clean (again, because it doesn't know its own position accurately).

I fit noisy data using optimization all the time without any problem. But the first thing I do is try to develop sensors that will reduce the noise level. Accurately measuring position is relatively trivial and could be done in this case in a number of ways. The more elaborate way would be to have three "satellite" units around the house from which it could triangulate its position similar to a GPS, but this would be impractical and expensive. The other would be to simply install a device to measure the rotation of the wheels. This tells you the velocity of the thing and, therefore, its position to an arbitrary degree of accuracy (arbitrary since simple gearing can change the number of rotations required for a measurement). This would be very cheap and is implemented in any number of existing systems.

It could be set up such that it remembers the layout of rooms. If you move furniture, hit a reset button and it will try to start over and figure it out again. To map the room, all it would have to do is track its velocity and locate the constraints (walls and furniture). This could be done by running until you find a wall/piece of furniture, then turning left 90° and going again until you find something. This time when you hit something, turn 180° and go again. Then you turn 90° right, move one unit (length of robot), then right 90° again. Rinse and repeat. This isn't foolproof, since it would fail if non-90° angles were encountered, but the idea is the same. I'm not going to develop an entire algorithm for a hypothetical project here when I could probably make a decent chunk of change implementing it myself.

 

[Born2bwire]

Originally posted by: CycloWizard

Originally posted by: degibson
I disagree, CycloWizard: Optimization problems have a lot of trouble with noisy data. You must consider that the Roomba never knows its own position accurately, and will receive various false positives from people, animals, and rabid dust bunnies. I like the simulated annealing approach, though again I'm not sure how to adapt it to deal with noise on its inputs. It also seems to me that there is no good way to evaluate the solution without human interference (hence no feedback to annealing) since the Roomba cannot know when the room is clean (again, because it doesn't know its own position accurately).

I fit noisy data using optimization all the time without any problem. But the first thing I do is try to develop sensors that will reduce the noise level. Accurately measuring position is relatively trivial and could be done in this case in a number of ways. The more elaborate way would be to have three "satellite" units around the house from which it could triangulate its position similar to a GPS, but this would be impractical and expensive. The other would be to simply install a device to measure the rotation of the wheels. This tells you the velocity of the thing and, therefore, its position to an arbitrary degree of accuracy (arbitrary since simple gearing can change the number of rotations required for a measurement). This would be very cheap and is implemented in any number of existing systems.

It could be set up such that it remembers the layout of rooms. If you move furniture, hit a reset button and it will try to start over and figure it out again. To map the room, all it would have to do is track its velocity and locate the constraints (walls and furniture). This could be done by running until you find a wall/piece of furniture, then turning left 90° and going again until you find something. This time when you hit something, turn 180° and go again. Then you turn 90° right, move one unit (length of robot), then right 90° again. Rinse and repeat. This isn't foolproof, since it would fail if non-90° angles were encountered, but the idea is the same. I'm not going to develop an entire algorithm for a hypothetical project here when I could probably make a decent chunk of change implementing it myself.

Accelerometers and tachometers (is this the right word for it?) on the wheels are only half the solution. You'll end up getting drift in your measurements that will continually compound unless you can update with a different set of feedback. You'll need to a surveying device to measure your position periodically in the room. The movement sensors provide quick feedback for short movements and precise control. The position measurement, which can be a relatively long measurment, provides periodic updates to remove the inherent drifts and other errors that will creep in. With your proposition, position feedback from collision with permanent obstacles like walls and entrenched furniture can be a crude solution. But again, I thought this was what the Roomba currently does.

 

[CycloWizard]

Originally posted by: Born2bwire
Accelerometers and tachometers (is this the right word for it?) on the wheels are only half the solution. You'll end up getting drift in your measurements that will continually compound unless you can update with a different set of feedback. You'll need to a surveying device to measure your position periodically in the room. The movement sensors provide quick feedback for short movements and precise control. The position measurement, which can be a relatively long measurment, provides periodic updates to remove the inherent drifts and other errors that will creep in.

Accelerometers and traditional tachometers are one approach, but there are superior alternatives that are, of course, more expensive. Modern cone-and-plate rheometers use a very cool tachometer system that can consistently measure the rotation of the small spindle used with a precision of a few nanometers with no upper limit. This setup would easily allow a drift-free measurement of the wheel velocity/position. The rheometer I linked costs about $80k, with the tachometer components comprising probably around $1-2k of that (guys at TA wouldn't tell me exactly, so I'm guessing here ).

With your proposition, position feedback from collision with permanent obstacles like walls and entrenched furniture can be a crude solution. But again, I thought this was what the Roomba currently does.

I'm not sure what it currently does. I've only seen one in operation for about two minutes at a friend's house, and it seemed like it just blindly wandered around the room, always turning a certain direction when it hits an object. Adding a mapping component could greatly increase the efficiency by removing the need to hit all of the walls in this way every time - you'd only have to do it once.

 

[Born2bwire]

Originally posted by: CycloWizard

With your proposition, position feedback from collision with permanent obstacles like walls and entrenched furniture can be a crude solution. But again, I thought this was what the Roomba currently does.

I'm not sure what it currently does. I've only seen one in operation for about two minutes at a friend's house, and it seemed like it just blindly wandered around the room, always turning a certain direction when it hits an object. Adding a mapping component could greatly increase the efficiency by removing the need to hit all of the walls in this way every time - you'd only have to do it once.

Ditto, I've only seen them in action on limited occasions. But it would seem to me that it would be the pinnacle of foolishness not to implement at least a mapping algorithm like you had suggested. I would also want to clarify that the main problem with using obstacles as your reference feedback for location is that if you have a large empty room, then the only time you will get any feedback is at the edges. Depending on how you traverse the room, the frequency of your updates can be sporadic to nonexistent (traversing in parallel rows versus spiral pattern working from outside in). Thus, there would be long periods of motion without anything to correct the feedback.

 

[CycloWizard]

Originally posted by: Born2bwire
Ditto, I've only seen them in action on limited occasions. But it would seem to me that it would be the pinnacle of foolishness not to implement at least a mapping algorithm like you had suggested. I would also want to clarify that the main problem with using obstacles as your reference feedback for location is that if you have a large empty room, then the only time you will get any feedback is at the edges. Depending on how you traverse the room, the frequency of your updates can be sporadic to nonexistent (traversing in parallel rows versus spiral pattern working from outside in). Thus, there would be long periods of motion without anything to correct the feedback.

Right. The method I suggested is hardly an optimized search, but when you have no input regarding the shape of the space, there's not a simpler way that will give good results. Since you only have to run the mapping once, it shouldn't be a huge deal. However, I'm sure if we sat down and tried to work this out, we could come up with a more efficient way to do it. One could add sensors to the sides to get more input (like the backup sensors used on cars now), but at added cost. This would enable you to simply follow the outline of the room, which would speed up the mapping considerably. It could result in missing obstacles in the center of the room (like coffee tables). Lacking information like this in the map would render the "optimal cleaning pattern" pretty much useless. Bottom line: you could make this thing as fancy or as simple as you want, depending on how much you want to spend on it. The current model appears to be very simple and not very cheap, so it seems like there's room for competition. Maybe we should start one.

 

[TuxDave]

Originally posted by: Cogman
So I was reading up on roomba and its compatition the trilobyte, and I just can't help but wonder "Why does roomba have to be so dumb". Yes, it keeps the costs down. But why can't they find somewhat of a middle ground.

For example, mapping out a room doesn't need ultrasonic soundwaves to instantly tell what the environment looks like, instead, simple optic mouse tech can tell the roomba how far it has traveled (on a 2d coordinate system) Flash memory is certainly cheap enough to give the roomba a pretty good idea of where it has or hasn't been, and 2d mapping problems arn't entirely too hard. Heck, you could even have roomba do a quick trial run of a room, save the map generated from all the bumps, and then do some math while charging to determine the best route to take to clean the whole room the next time.

Am I on to something here?

I think the problem with your idea is that it has a potentially diverging error margin. If you're relying on the accuracy of knowing its exact position based on measurements that can have cumulated errors, you'll eventually end up with contradicting data.

 

[Born2bwire]

Originally posted by: CycloWizard

Originally posted by: Born2bwire
Ditto, I've only seen them in action on limited occasions. But it would seem to me that it would be the pinnacle of foolishness not to implement at least a mapping algorithm like you had suggested. I would also want to clarify that the main problem with using obstacles as your reference feedback for location is that if you have a large empty room, then the only time you will get any feedback is at the edges. Depending on how you traverse the room, the frequency of your updates can be sporadic to nonexistent (traversing in parallel rows versus spiral pattern working from outside in). Thus, there would be long periods of motion without anything to correct the feedback.

Right. The method I suggested is hardly an optimized search, but when you have no input regarding the shape of the space, there's not a simpler way that will give good results. Since you only have to run the mapping once, it shouldn't be a huge deal. However, I'm sure if we sat down and tried to work this out, we could come up with a more efficient way to do it. One could add sensors to the sides to get more input (like the backup sensors used on cars now), but at added cost. This would enable you to simply follow the outline of the room, which would speed up the mapping considerably. It could result in missing obstacles in the center of the room (like coffee tables). Lacking information like this in the map would render the "optimal cleaning pattern" pretty much useless. Bottom line: you could make this thing as fancy or as simple as you want, depending on how much you want to spend on it. The current model appears to be very simple and not very cheap, so it seems like there's room for competition. Maybe we should start one.

Yes, yes, we could do that. Or, I could just send you out to clean people's carpets manually. To tell the truth, I'm leaning towards the latter, less work on my part.

 

[CycloWizard]

Originally posted by: Born2bwire
Yes, yes, we could do that. Or, I could just send you out to clean people's carpets manually. To tell the truth, I'm leaning towards the latter, less work on my part.

Hey, I'm not a grad student anymore - I expect to get paid to work from now on! Funny thing is, I actually used to sell Kirby's door-to-door as a summer job in college. Only did that for one summer and made quite a bit of money doing it. My previous experience as a janitor in high school really helped me convey things to people I guess. I made almost a grand a week vacuuming four rooms a day and getting people to pay $1700 for a vacuum/shampoo system. I feel absolutely evil now looking back at it, but at the time I had a lot of debt and not a lot of time. /guilty conscience

 

[degibson]

It sounds like most of us are in agreement that the problem is computationally intensive, yes, but also relies very heavily on quality sensors. My original argument assumed a great deal of error in positioning because measurements of wheel rotation aren't too accurate on, say, carpet. Tux makes a great point in that these errors accumulate until the Roomba's position becomes known to arbitrary accuracy (never?).

However, I do not assert that it is impossible. I think it would be fun to get a Roomba and spritz it up. The first thing I would go for would be those satellites mentioned by CycloWizard -- their role would be to tri- or quadrangulate the Roomba's position based on 1) Computer-vision absolute positioning augmented with 2) Magnetic compass to aid with bearings. Assume all sensors are of the highest quality.

In fact, since we have satellite units, lets have /them/ map the room first. Then they all come back to mama Roomba and tell her all about the room layout. Roomba fires up her Pentium D and figures out a 99% coverage for vacumming, then the sattelites follow her around, helping her to navigate over any deltas that may have accumulated on the map (like a marauding german shepherd or an overturned couch) by verifying her position and suggesting alternate routes.

After the work is done, Roomba and the Roombettes go an plug themselves in to charge up for the next use.

What am I missing? =)

 

[Born2bwire]

Originally posted by: degibson
It sounds like most of us are in agreement that the problem is computationally intensive, yes, but also relies very heavily on quality sensors. My original argument assumed a great deal of error in positioning because measurements of wheel rotation aren't too accurate on, say, carpet. Tux makes a great point in that these errors accumulate until the Roomba's position becomes known to arbitrary accuracy (never?).

However, I do not assert that it is impossible. I think it would be fun to get a Roomba and spritz it up. The first thing I would go for would be those satellites mentioned by CycloWizard -- their role would be to tri- or quadrangulate the Roomba's position based on 1) Computer-vision absolute positioning augmented with 2) Magnetic compass to aid with bearings. Assume all sensors are of the highest quality.

In fact, since we have satellite units, lets have /them/ map the room first. Then they all come back to mama Roomba and tell her all about the room layout. Roomba fires up her Pentium D and figures out a 99% coverage for vacumming, then the sattelites follow her around, helping her to navigate over any deltas that may have accumulated on the map (like a marauding german shepherd or an overturned couch) by verifying her position and suggesting alternate routes.

After the work is done, Roomba and the Roombettes go an plug themselves in to charge up for the next use.

What am I missing? =)

You can't have Roombettes without a daddy Roomba too. I don't think you would need a magnetic compass if you already have a position update via vision or electromagnetic triangularization (I think the latter would be a cheaper and more reliable solution, but it would be limited to having beacons set in each room). It's information would be redundant but of course that's not a bad thing, it'll just be additional info for the filter. As for computational intensity, you could do this easily with a single board computer (SBC). That is what was used for the hovercraft. However, the vision processing was offloaded to a centralized computer and was sent via wireless to the hovercraft. But the hovercraft processed the data and calculated the controls.

 

[CycloWizard]

Originally posted by: degibson
It sounds like most of us are in agreement that the problem is computationally intensive, yes, but also relies very heavily on quality sensors. My original argument assumed a great deal of error in positioning because measurements of wheel rotation aren't too accurate on, say, carpet. Tux makes a great point in that these errors accumulate until the Roomba's position becomes known to arbitrary accuracy (never?).

However, I do not assert that it is impossible. I think it would be fun to get a Roomba and spritz it up. The first thing I would go for would be those satellites mentioned by CycloWizard -- their role would be to tri- or quadrangulate the Roomba's position based on 1) Computer-vision absolute positioning augmented with 2) Magnetic compass to aid with bearings. Assume all sensors are of the highest quality.

In fact, since we have satellite units, lets have /them/ map the room first. Then they all come back to mama Roomba and tell her all about the room layout. Roomba fires up her Pentium D and figures out a 99% coverage for vacumming, then the sattelites follow her around, helping her to navigate over any deltas that may have accumulated on the map (like a marauding german shepherd or an overturned couch) by verifying her position and suggesting alternate routes.

After the work is done, Roomba and the Roombettes go an plug themselves in to charge up for the next use.

What am I missing? =)

If you have the "satellites," the position is uniquely determined without the need for computer vision. That, and your proposal is expensive. Simplicity is the key for this thing, since that's why people buy it. Throwing 3-4 "satellites" around the house takes out the simplicity to the point where only a few rich guys would buy it.

Also, in the two minutes I watched one of these things, the dogs (and cats) didn't want anything to do with it. Maybe they were scaredy cats, but they scattered as soon as this thing was put on the floor.

 

[Born2bwire]

Originally posted by: CycloWizard

Originally posted by: degibson
It sounds like most of us are in agreement that the problem is computationally intensive, yes, but also relies very heavily on quality sensors. My original argument assumed a great deal of error in positioning because measurements of wheel rotation aren't too accurate on, say, carpet. Tux makes a great point in that these errors accumulate until the Roomba's position becomes known to arbitrary accuracy (never?).

However, I do not assert that it is impossible. I think it would be fun to get a Roomba and spritz it up. The first thing I would go for would be those satellites mentioned by CycloWizard -- their role would be to tri- or quadrangulate the Roomba's position based on 1) Computer-vision absolute positioning augmented with 2) Magnetic compass to aid with bearings. Assume all sensors are of the highest quality.

In fact, since we have satellite units, lets have /them/ map the room first. Then they all come back to mama Roomba and tell her all about the room layout. Roomba fires up her Pentium D and figures out a 99% coverage for vacumming, then the sattelites follow her around, helping her to navigate over any deltas that may have accumulated on the map (like a marauding german shepherd or an overturned couch) by verifying her position and suggesting alternate routes.

After the work is done, Roomba and the Roombettes go an plug themselves in to charge up for the next use.

What am I missing? =)

If you have the "satellites," the position is uniquely determined without the need for computer vision. That, and your proposal is expensive. Simplicity is the key for this thing, since that's why people buy it. Throwing 3-4 "satellites" around the house takes out the simplicity to the point where only a few rich guys would buy it.

Also, in the two minutes I watched one of these things, the dogs (and cats) didn't want anything to do with it. Maybe they were scaredy cats, but they scattered as soon as this thing was put on the floor.

My main concern for these satellites or beacons is that walls may not be penetrable to the radiation. I've heard people having problems with WLAN in their homes if they have plastering on the walls. If this was the situation, then you would need to set beacons in each room for adequate coverage. In addition, you will have to deal with multipath reflections in these situations. That will require additional signal processing to remove these ghosts. You could of course use very low frequency waves to ensure penetration through objects, but then you are going to have a lot of other problems. The first is that you're going to be operating in near fields as opposed to the far field if you used a frequency suitable for room communication (ie 2.4 GHZ). Second, you run into spurious signals, like the 60 Hz wall power and its harmonics and other low frequency signals (atomic clock, submarine communications, etc. depending on how low you go).

 

[degibson]

And of course, there are only a few bands legal in the US due to the evil FCC.

 

[Machupo]

Ever lived in a German house? These things could take a GBU-31 without flinching. No chance at getting Wifi throughout the house (thick plaster, every wall has sheetrock and wire mesh framing).

What if the roomba took an initial sodar/radar snapshot from it's initialization point and then moved to some additional number of points (# of points determined by obstacles / deadspace) around the room (cleared by previous images) to develop a map of the room? Periodic update images during the clean to identify changes? Might be computationally intensive to create a map this way, but there would be no bumping (or at least, less bumping) and nighttime operation wouldn't be an issue (as with visual images).

 

[Born2bwire]

Originally posted by: Machupo
Ever lived in a German house? These things could take a GBU-31 without flinching. No chance at getting Wifi throughout the house (thick plaster, every wall has sheetrock and wire mesh framing).

What if the roomba took an initial sodar/radar snapshot from it's initialization point and then moved to some additional number of points (# of points determined by obstacles / deadspace) around the room (cleared by previous images) to develop a map of the room? Periodic update images during the clean to identify changes? Might be computationally intensive to create a map this way, but there would be no bumping (or at least, less bumping) and nighttime operation wouldn't be an issue (as with visual images).

Radar would be rather expensive and bulky to implement, I would imagine ditto for sonar for anything other than collision detectors.

 

[JF060392]

Originally posted by: Machupo
Ever lived in a German house? These things could take a GBU-31 without flinching. No chance at getting Wifi throughout the house (thick plaster, every wall has sheetrock and wire mesh framing).

What if the roomba took an initial sodar/radar snapshot from it's initialization point and then moved to some additional number of points (# of points determined by obstacles / deadspace) around the room (cleared by previous images) to develop a map of the room? Periodic update images during the clean to identify changes? Might be computationally intensive to create a map this way, but there would be no bumping (or at least, less bumping) and nighttime operation wouldn't be an issue (as with visual images).

thats true but how would it detect the areas that are dirty if it isnt preprogrammed on a certain path to follow. in the end the roomba will just bump into walls like it regularly does.