Last weekend I got myself one of those robot vacuum cleaners (a Deebot, if it matters). It works well and it’s still new enough to me that it’s fun watching it work instead of doing the work myself instead. I noticed right off the bat that it doesn’t vacuum the room the way I imagined it would, like I would mow a lawn. The cleaner seems to randomly meander around the room, only occasionally going on a long(ish) run before turning and going back to short random movements, including spiraling in or out of a circle about two meters diameter.
This got me wondering: what algorithm does it use to ensure it covers the entire room? How is this more efficient than “lawn mower style”?
I’ve read a bit about the Roomba. I don’t know if others follow a similar algorithm.
The Roomba first tries to figure out the size of the room. I’m not sure if it uses ultrasound or infra-red to do that but I assume it’s one or the other. Then it goes roughly to the center of that area and spirals out. When it detects objects then it starts going back and forth and basically goes around the object and keeps going in this sort of manner. If it finds another open area then it does the same sort of algorithm on that area as well.
The spiraling yours is doing makes me think that it is using a similar algorithm.
Since you are able to see the entire room and pretty much instantly figure out where the obstacles are, it’s fairly easy for you to figure out an efficient algorithm. If you were completely blind and were shoved into a random location where you didn’t even have the size of the room, and your only sense was that you could look in a particular direction and your sense would give you a number based on how far away you were from the nearest obstacle in that direction (wall, shoe, coffee table, you’re not sure), you wouldn’t be able to use the same type of algorithm. Going up and back like a lawn mower would get you stuck when you encountered something like a coffee table. You’d end up going around one side of the table and ignoring the other side.
Going up and back also requires a fairly precise sense of which direction you are facing. The robot doesn’t have that type of precision guidance system. When it turns, it’s not sure exactly how much it turned, and it has no way to properly orient itself. Any turn errors would compound in an up and back type algorithm.