This paper presents a novel algorithm for computing absolute space representations (ASRs) for mobile robots equipped with sonar sensors and an odometer. The robot is allowed to wander freely (i.e. without following any fixed path) along the corridors in an office environment from a given start point to an end point. It then wanders from the end point back to the start point. The resulting ASRs computed in both directions are shown.
In recent years the idea of computing a network of local (metrical) spaces as a representation of the environment that an autonomous agent has experienced is gaining momentum. This idea, commonly known as computing a hybrid map, is favored by both the pragmatists (i.e. those researchers interested in building mobile robots) and the theorists (i.e. those researchers interested in developing computational theories of cognitive maps).
Thrun implemented a mobile robot that computes gridbased maps of its environment using artificial neural networks and naïve Bayesian integration. From the grid-maps, it generates networks of empty spaces. The network representation is used for fast planning and problem solving.
Tomatis, Nourbakhsh and Siegwart offered a different solution – they compute a topological network of open spaces found in corridors and metric maps for rooms. The latter are then attached to the appropriate nodes in the network. Open spaces in corridors are distinguished by the presence of physical corners separating them.
A new algorithm is proposed in this project. The key ideas underlying our new algorithm are as follows:
1. ASRs are computed for each path traversed – a path is a single continuous movement of the robot through the environment (i.e. without any stopping or turning);
2. The important exits found in a path are the exits at both ends of it (i.e. given the poor sensing, one cannot trust the side exits detected). This means that the required ASR for path is the bounded region for the path;
3. To compute the bounded region, preference is given to using the large surfaces as opposed to the smaller ones;
4. A split and merge algorithm  is then used to split or combine ASRs obtained from single paths to produce the final ASRs for the environment.
Source: AUT University
Author: Chee K. Wong | Wai K. Yeap | Jochen Schmidt