Feature-based 3D SLAM | EPFL Graph Search

This doctoral thesis deals with an open subproblem of robot navigation, namely simultaneous localization and mapping (SLAM) in three-dimensional space. The goal is to develop a system which is capable of localizing a mobile robot in a reliable way and at the same time reconstruct its environment as a three-dimensional map. Besides enabling robot navigation in 3D, such a map could be of great importance for higher-level robotic tasks, like scene interpretation or manipulation as well as visualization purposes in general, which are required in surveying, architecture, urban search and rescue and others. The third dimension is challenging. Firstly, sensors providing three-dimensional data have to be found which suit the requirements of mobile robots and therefore have to be limited in size and power consumption. For this work, two sensors have been considered: the Swiss Ranger from CSEM (Swiss Center for Electronics and Microtechnology) and a custom-built range sensor based on a commercially available 2D laser scanner from SICK. Both are active sensors relying on measuring the time-of-flight of the emitted light. After calibration and error analysis it was concluded that the Swiss Ranger is less suited for localization and mapping than the rotating laser scanner due to its noisy data and limited field of view. It was therefore not further considered in the ensuing work. As a single 3D scan generated by the rotating laser scanner can be composed of many tens of thousands of data points and the robot takes dozens of scans during a mission, it is necessary to compress the raw data to visualize and process it efficiently. The method chosen in this work is to use a feature-based representation, which enables detailed and, at the same time, compact and informative environment reconstruction. The chosen features are planar segments, whose probabilistic representation and extraction are described, results of the SLAM algorithm are shown. With the aid of an Extended Kalman Filter (EKF) the pose of the robot and the location of the different planar segments – considering their uncertainty – can be estimated in an incremental way. The framework defined by the SPmodel (Symmetries and Perturbations Model) is used, allowing to represent and process various uncertain geometric models. The approach is validated through different experiments with a mobile robot in an office environment.

Hybrid, metric - topological, mobile robot navigation

Nicola Tomatis

This thesis presents a recent research on the problem of environmental modeling for both localization and map building for wheel-based, differential driven, fully autonomous and self-contained mobile robots. The robots behave in an indoor office environment. They have a multi-sensor setup where the encoders are used for odometry and two exteroperceptive sensors, a 360° laser scanner and a monocular vision system, are employed to perceive the surrounding. The whole approach is feature based meaning that instead of directly using the raw data from the sensor features are firstly extracted. This allows the filtering of noise from the sensors and permits taking account of the dynamics in the environment. Furthermore, a properly chosen feature extraction has the characteristic of better isolating informative patterns. When describing these features care has to be taken that the uncertainty from the measurements is taken into account. The representation of the environment is crucial for mobile robot navigation. The model defines which perception capabilities are required and also which navigation technique is allowed to be used. The presented environmental model is both metric and topological. By coherently combining the two paradigms the advantages of both methods are added in order to face the drawbacks of a single approach. The capabilities of the hybrid approach are exploited to model an indoor office environment where metric information is used locally in structures (rooms, offices), which are naturally defined by the environment itself while the topology of the whole environment is resumed separately thus avoiding the need of global metric consistency. The hybrid model permits the use of two different and complementary approaches for localization, map building and planning. This combination permits the grouping of all the characteristics which enables the following goals to be met: Precision, robustness and practicability. Metric approaches are, per definition, precise. The use of an Extended Kalman Filter (EKF) permits to have a precision which is just bounded by the quality of the sensor data. Topological approaches can easily handle large environments because they do not heavily rely on dead reckoning. Global consistency can, therefore, be maintained for large environments. Consistent mapping, which handle large environments, is achieved by choosing a topological localization approach, based on a Partially Observable Markov Decision Process (POMDP), which is extended to simultaneous localization and map building. The theory can be mathematically proven by making some assumptions. However, as stated during the whole work, at the end the robot itself has to show how good the theory is when used in the real world. For this extensive experimentation for a total of more than 9 km is performed with fully autonomous self-contained robots. These experiments are then carefully analyzed. With the metric approach precision with error bounds of about 1 cm and less than 1 degree is further confirmed by ground truth measurements with a mean error of less than 1 cm. The topological approach is successfully tested by simultaneous localization and map building where the automatically created maps turned out to work better than the a priori maps. Relocation and closing the loop are also successfully tested.

EPFL2001

Topological SLAM

Adriana Tapus

This thesis is about topological navigation, more precisely about space representation, perception, localization and mapping. All these elements are needed in order to obtain a robust and reliable framework for navigation. This is essential in order to move in an environment, manipulate objects in it and avoid collisions. The method proposed in this dissertation is suitable for fully autonomous mobile robots, operating in structured indoor and outdoor environments. High robustness is necessary to obtain a distinctive and reliable representation of the environment. This can be obtained by combining the information acquired by several sensors with complementary characteristics. A multimodal perception system that includes the wheel encoders for odometry and two extereoceptive sensors composed of a laser range finder that gives a 360° view of the environment and an omnidirectional camera are used in this work. Significant, robust and stable features are extracted from sensory data. The different features extracted from the extereoceptive sensors (i.e. corners, vertical edges, color patches, etc.) are fused and combined into a single, circular, and distinctive space representation named the fingerprint of a place. This representation is adapted for topological navigation and is the foundation for the whole dissertation. One of the major tasks of a mobile robot is localization. Different topological localization approaches based on the fingerprint concept are presented in this dissertation. Localization on a fingerprint-based representation is reduced to a problem of fingerprint matching. Two of these methods make use of the Bayesian Programming (BP) formalism and two others are based on dynamic programming. They also show how multimodal perception increases the reliability of topological localization for mobile robots. In order to autonomously acquire and create maps, robots have to explore their environment. Several exploration tools for indoor environments are presented: wall following, mid-line following, center of free space of a room, door detection, and environment structure identification. An automatic and incremental topological mapping system based on fingerprints of places and a global localizer using Partially Observable Markov Decision Processes (POMDP) are proposed. The construction of a topological mapping system is combined with localization, both relying on fingerprints of places, in order to perform Simultaneous Localization and Mapping (SLAM). This enables navigation of an autonomous mobile robot in a structured environment without relying on maps given a priori, without using artificial landmarks and by employing a semantic spatial representation that allows a more natural interface between humans and robots. The fingerprint approach, combining the information from all sensors available to the robot, reduces perceptual aliasing and improves the distinctiveness of places. This fingerprint-based approach yields a consistent and distinctive representation of the environment and is extensible in that it permits spatial cognition beyond just pure navigation. All these methodologies have been validated through experiments. Indoor and outdoor experiments have been conducted over a distance exceeding 2 km. The fingerprints of places proved to provide a compact and distinctive methodology for space representation and place recognition – they permit encoding of a huge amount of placerelated information in a single circular sequence of features. The experiments have verified the efficacy and reliability of this approach.

EPFL2005

Hybrid, metric - topological, mobile robot navigation

Nicola Tomatis

EPFL2001

Topological SLAM

Adriana Tapus

EPFL2005