How do autonomous robotic vacuum cleaners perceive the environment for navigation?
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.