How does a domestic autonomous robotic vacuum cleaner - such as a Roomba - know when it's working cleaned area (aka virtual map), and how does it plan to travel to the areas which hasn't been explored yet?

Does it use some kind of A* algorithm?


3 Answers 3


An agent perceives the environment through sensors and act according to the incoming percepts (agent's perceptual input at any instant). An autonomous vacuum cleaner can be as simple as

(blocki, clean) --> Move to blocki+1
(blocki, dirty) --> Clean

This is just a general description, actual one is more complicated. Or the bot can have a memory where it stores all its previous decision and incorporate those while taking new ones.
This can be helpful if the bot wants to remember where an obstacle (like wall, in this case bot don't want to go and check the presence of wall each and every single time it is turned on) is, or where it is more probable to find dirt. If the bot is not remembering its history then it will be scanning the whole house over and over again, sensing the same obstacle every time and going across them.
Bot which keeps no log of its history will take the same procedure again and again, making the same mistakes again and again. This is not an efficient way and a waste of its energy (or battery).

Normally today bots have ordinary sensors which can only sense the dirt and obstacle. This limits the number of tasks a bot can perform. If a bot has decent camera as a sensor, and some algorithms of Image Processing are dumped into it, then it increases the tasks it can perform. Like detecting the stairs and cleaning different floors. Normally stairs will be considered obstacle and bot will just go around them. In case, when camera sensor is provided, stairs are potentially a path to be taken.

A* algorithm is not necessarily used in case when the bot is not remembering the map of the house (or room). A normal robot which just scans the room and cleans it, will not be needing, as it don't know it's destination. Its only goal is to clean if it finds something dirty. But a bot which knows the map of the room and where there is a high probability of finding dirt, the A* algorithm can be used.


I think it uses a kind of algorithm you presented, in combination with various sensors. It uses the sensors to make a virtual map and can then traverse the terrain with a combination of these sensors and the virtual map. Of course it uses a kind of path-planning algorithm to find the best way from A to B.

Maybe you should look at this wikipedia page: https://en.wikipedia.org/wiki/Robotic_mapping

The new robotic vacuum cleaner from Samsung, I think, uses a 360° camera to perceive its environment.

  • 3
    $\begingroup$ According to the description page, Roomba does not generate a map of the room they are cleaning. $\endgroup$
    – Ébe Isaac
    Commented Sep 13, 2016 at 19:12
  • $\begingroup$ Just read it, you are absolutely right! Couldn't find any more information about the iAdapt® 2.0 navigation, though... $\endgroup$
    – Thomas
    Commented Sep 13, 2016 at 19:33
  • $\begingroup$ Here's a promotional page on such a device's behavior, which might be a useful starting point. (It's a PDF from the Internet Archive.) $\endgroup$
    – Ben N
    Commented Sep 13, 2016 at 21:09
  • $\begingroup$ Keep in mind that Rodney Brooks is behind iRobot, and his approach to AI differs from the once traditional approaches, inducing planning. Early versions of Roomba where hitting objects quite often, as the robot discovered its environment a la Brooks. A good and concise answer from yesterday gives good details about the original method, and Roomba's is very likely derived from this subsumption architecture (I am not from iRobot, though). $\endgroup$ Commented Sep 13, 2016 at 23:39

Autonomous vacuum cleaners usually have these following task environment properties:

i. Partially observable environment

ii. Deterministic environment.

iii. Sequential environment.

iv. Static environment.

v. Discrete environment

vi. Single agent environment

Since it's a partially observable environment, the agent performs its actions based on what is sees and thus it's is in an deterministic environment where the current action will be the result of previous actions. And since, the agent is continuously performing, it's an sequential environment. Since, the environment doesn't change when agent is working, the environment is static and discrete since there are only finite no. of discrete states in which agent can be in.

There are certain rules written which tells an agent how to react when in a particular state. If there are multiple rules which are satisfied, then agent uses its experience to choose an optimal action to perform. The rules are written by the programmer keeping in mind the task envt. properties.

The agent's actions also depend on the type of agent it is decided by the programmer. It can be simple reflex-based, or a goal based, or a goal-based + feedback or a complete learning based agent. An agent can't use A* algorithm because the entire environment is not visible and it will be useless to use A* algorithm where we don't know when our goal may be reached.

The agent has various sensors attached which give it info. about the surrounding, like cameras, sound recorders, thermal sensors, etc. An autonomous vacuum cleaner may also have a dirt sensor to detect the dirt. The agent performs an action using one of its actuators like wheels, robot arms, etc.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .