I am wondering, how do they make them go around, and clean every spot then go back to the charging station. Any research on this?

That's a travelling sales man problem, which has several interesting solutions. I'd start with a spanning tree over a discretization of the house, where the nodes have the width of the robot.

its all about sensors, imagine a Diablo mini-map that gets rendered as you pass through the level. Once you have a map, its about navigating through the `world (not that much as in a game world but more like a basic setup with directx world matrix and camera matrix transformations)

My parents used to have a pool cleaning robot. It worked entirely on water pressure. The robot was attached to a hose, which was attached to the pump pulling water out of the pool for filtering. I think it had some sort of mechanical randomization to keep it from getting stuck in any one path. No AI. No electronics or electrical components of any type. Just randomly walking around, pulled by a difference in water pressure. And it worked, more or less. It wasn't particularly efficient, but it didn't have to be because you could just keep it running overnight.

[quote]That's a travelling sales man problem[/quote]

No it's not; it's much easier to plan a path that says “cover all this area reasonably efficiently” than it is to say “visit these arbitrary nodes in the minimal cost order.”

A Roomba will also typically cover certain areas of the room more than others; either because it gest “locally stuck” on that part of the map, or because it's some central/bottleneck area that needs to be visited a lot on paths going to other areas.

In general, what you should look up is “SLAM” – the robotics terminology for Simultaneous Locating And Mapping. Based on the distance sensor of the LIDAR in the bot, and its estimated movement based on wheel odometry (how far has each wheel turned, which gives you both position and orientation,) it can build a map of the room, and then keep a simple cell-based occupancy map to make sure it sweeps all accessible areas.

Thought there is more to it than just going blind forward till it finds an obstacle.

hplus0603 said:
No it's not; it's much easier to plan a path that says “cover all this area reasonably efficiently” than it is to say “visit these arbitrary nodes in the minimal cost order.”

If you divide your area into any form of elements, you need to traverse all of them. So it is travelling salesman, although we may not need constraints to visit each element only once, while efficiency adds complexity e.g. limiting turns. So it's not exactly the same problem but a close variation.

Here's what I would actually do if I were to build such a robot right now, with modern technology:

Divide the world into a 2D grid of cells. Each grid space has one of three values: “clean”, “unknown”, and “wall”. ("unknown" is equivalent to “dirty”, since we haven't visited the cell yet.) Initially, all cells are “unknown”.

Use a breadth-first search for the shortest path to a reachable “unknown” cell, passing only through “clean” cells. Move along this path. If the cell is reached, mark it “clean”. If the path is blocked, mark it “wall”. Repeat this until there are no more reachable “unknown” cells.

When there are no more reachable “unknown” cells, you have four options:

• Return to the charging station.
• Mark all “wall” cells as “unknown”, in case one of them was a temporary obstacle.
• Mark all “clean” cells as “unknown”, in case new dirt has appeared.
• Mark both the “wall” and the “clean” cells as “unknown”, to handle both of the above two possibilities.

This seems like a reasonable compromise between intelligence and simplicity. A lot smarter than random wandering, but simple enough that it can be tested and debugged without too much trouble. I have no idea what actual commercial cleaning robots do, but I would expect it to be at about this level of complexity, with a general trend toward more intelligence in newer models.

_WeirdCat_ said:

Thought there is more to it than just going blind forward till it finds an obstacle.

the robots constructor needs to keep the robot practical and cheap. There`s two way of doing it. Use and exterior electrical signal (radio that is) to help determine where you are and then bump into objects to build a map, or second method use cameras or proximity sensors to map the surroundings without something from outside to tell you where you are. With the first method once you have a map built you don`t need to check for walls again in real life afterwards you just check your position based on the map you have in your memory, of course someone can drop a box in the middle of the room and that needs to be mapped as well but that`s an exception. Second case scenario you need to constantly check for walls in real life to determine where you are.

The original Roomba algorithm is very simple.

• Clean outward in an increasing spiral until hitting something.
• If obstacle is wall-like, follow the wall for a while.
• Go in a straight line in a random direction for a while.
• Start over.

Rod Brooks spoke on this once. It takes about 2x the cleaning effort of actually visiting each spot only once.

More modern vacuums have actual navigation systems, but if you just need a vacuum in a game, the above should work.