Today, lightweight SLAM algorithms are needed in many embedded robotic systems. In this paper the orthogonal SLAM (OrthoSLAM ) algorithm is presented and empirically validated. The algorithm has constant time complexity in the state estimation and is capable to run real-time. The main contribution resides in the idea of reducing the complexity by means of an assumption on the environment. This is done by mapping only lines that are parallel or perpendicular to each other which represent the main structure of most indoor environments. The combination of this assumption with a Kalman filter and a relative map approach is able to map our laboratory hallway with the size of 80 m times 50 m and a trajectory of more than 500 m. The precision of the resulting map is similar to the measurements done by hand which are used as the ground-truth

This paper addresses the closing loop problem as the challenge of using all the information from the observation gathered when closing the loop in order to optimally adjust the whole map (assuming a correct data association). The proposed approach is an approximation, which allows the calculation of the gain without keeping track of all the correlations (i.e. with a complexity independent of the number of the map elements). Furthermore, the paper presents an explicit mathematical demonstration showing that the correlations computed by the EKF-based SLAM are overestimated. More precisely, it is shown that these correlations decrease exponentially with respect to the heading error of the robot. The approach is empirically demonstrated by means of meaningful simulations. The results are then discussed and conclusions are pointed out in the last section.

This paper presents an experimental evaluation of different line extraction algorithms on 2D laser scans for indoor environment. Six popular algorithms in mobile robotics and computer vision are selected and tested. Experiments are performed on 100 real data scans collected in an office environment with a map size of 80m /spl times/ 50m. Several comparison criteria are proposed and discussed to highlight the advantages and drawbacks of each algorithm, including speed, complexity, correctness and precision. The results of the algorithms are compared with the ground truth using standard statistical methods.

This paper starts with a discussion of the open challenges in the SLAM problem. In our opinion they can be grouped in two main and distinct areas: convergence of the built map and computation requirement for real world application. To deal with the previous problems, a solution in the stochastic map framework based on the concept of the relative map is proposed. The idea consists in introducing a map state, which only contains quantities invariant under shift and rotation and to carry out the estimation of this relative map in an optimal way. This is a possible way in order to have a decoupling between the robot motion and the landmark estimation and therefore not to rely the landmark estimation on the unmodeled error sources of the robot motion. Moreover, the proposed solution scales linearly with the number of landmark allowing real-time application. Experimental results, carried out on a real platform, show the better performance of this method with respect to the joint vehicle-landmark approach (absolute map filter) when the odometry is affected by undetected systematic errors or by large or unmodeled non-systematic errors.

Programming efficient and reliable code can be considered a non-trivial task, as it requires deep understanding of the problem to be solved along with good programming skills. However, software frameworks and programming paradigms can provide a dependable infrastructure upon which better programs can be written and deployed. This allows engineers to focus mainly on their task, while relying on the underlying run-time environment for taking care of low-level programming issues, such as memory allocation and disposal, typing consistency and interface compliance. In this paper, we argue that strong-typed programming languages and paradigms offer a valid support for the production of reliable programs. Aware of the challenges of formal measurement metrics for code quality, we present the benefits of strong-typing by considering a practical application: the design and implementation of RoboX, a tour-guide robot for the Swiss National Exhibition Expo.02. The example is extremely well suited for such a discussion, since complex mechatronic applications can be considered critical systems - i.e., systems whose failure may endanger missions, lives and society - thus their reliability has to be made a prime concern.

This paper presents a solution to the simultaneous localization and mapping (SLAM) problem in the stochastic map framework for a mobile robot navigating in an indoor environment. The approach is based on the concept of the relative map. The idea consists in introducing a map state, which only contains quantities invariant under translation and rotation. This is done in order to have a decoupling between the robot motion and the landmark estimation and therefore not to rely the landmark estimation on the unmodeled error sources of the robot motion. The case of the corner feature is here considered. The relative state estimated through the Kalman filter contains the distances and the relative orientations among the corners observed at the same tune. Therefore, this state is invariant with respect to the robot configuration (translation and rotation). Finally, an environment containing structures consisting of several corners is also investigated. Real experiments carried out with a mobile robot equipped with a 360/spl deg/ laser range finder show the performance of the approach.

This paper presents a navigation framework which enables multiple mobile robots to attain individual goals, coordinate their actions and work safely and reliably in a highly dynamic environment. We give an overview of the framework architecture, its layering and the subsystems reactive obstacle avoidance, local path planning, global path planning, multi-robot planning and localization. The latter receives particular attention as the localization problem is a key issue for navigation in unmodified and difficult environments. The framework permits a lightweight implementation on a fully autonomous robot. This is the result of a design effort striving for compact representations and computational efficiency. The experimental testbed was the "Robotics" pavilion at the Swiss National Exhibition Expo.02 where ten fully autonomous robots were interacting with more than half a million visitors during a five-month period on 3316 km.

This paper presents the genesis of RoboX. This tour guide robot has been built from the scratch based on the experience of the Autonomous Systems Lab. The production of 11 of those machines has been realized by a spin-off of the lab: BlueBotics SA. The goal was to maximize the autonomy and interactivity of the mobile platform while ensuring high robustness, security and performance. The result is an interactive moving machine which can operate in human environments and interacts by seeing humans, talking to and looking at them, showing icons and asking them to answer its questions. The complete design of mechanics, electronics and software is presented in the first part. Then, as extraordinary test bed, the Robotics exhibition at Expo.02 (Swiss National Exhibition) permits to establish meaningful statistics over 5 months (from May 15 to October 20, 2002) with up to 11 robots operating at the same time.

In this paper a perception approach allowing for high distinctiveness is presented. The method works in accordance to the fingerprint concept. Such representation allows using a very flexible matching approach based on the minimum energy algorithm. The whole extraction and matching approach is presented in details and viewed in a topological optic, where the matching result can directly be used as observation function for a topological localization approach. The experimentation section will validate the fingerprint approach and present different set of experiments in order to explain practically the choice of different types of features.

This paper presents both the theory and the first experimental results of a new method which allows simultaneous estimation of the robot configuration and the odometry error (both systematic and non-systematic) during the mobile robot navigation. The estimation of the non-systematic components is carried out through an augmented Kalman filter which estimates a state containing the robot configuration and the parameters of the odometry error. It uses encoder readings as inputs and the readings from a laser range finder as observations. The estimation of the non-systematic components is carried out through another Kalman filter where the observations are obtained by two subsequent robot configurations provided by the previous augmented Kalman filter.

In this paper we present an approach to obstacle avoidance and local path planning for polygonal robots. It decomposes the task into a model stage and a planning stage. The model stage accounts for robot shape and dynamics using a reduced dynamic window. The planning stage produces collision-free local paths with a velocity profile. We present an analytical solution to the distance to collision problem for polygonal robots, avoiding thus the use of look-up tables. The approach has been tested in simulation and on two non-holonomic rectangular robots where a cycle time of 10 Hz was reached under full CPU load. During a long-term experiment over 5 km travel distance, the method demonstrated its practicability.

In this paper simultaneous localization and map building is performed with a hybrid, metric-topological,approach. A global topological map connects local metric maps, allowing a compact environment model, which does not require global metric consistency and permits both precision and robustness. However, the most important innovation of the approach is the way how loops in the environment are handled by map building using the information of the multi hypotheses topological localization. The method uses data from a 360/spl deg/ laser scanner to extract comers and openings for the topological approach and infinite lines for the metric method. This hybrid approach has been tested in a 50 /spl times/ 25 m/sup 2/ portion of the institute building with a fully autonomous robot. The performances of the whole system are proven empirically by comparing maps generated by independent explorations, testing the localization capabilities, making relocation experiments and showing how the technique for closing the loop works.

In this paper a new localization approach combining the metric and topological paradigm is presented. The main idea is to connect local metric maps by means of a global topological map. This allows a compact environment model which does not require global metric consistency and permits both precision and robustness. The method uses a 360 degree laser scanner in order to extract lines for the metric localization and doors, discontinuities and hallways for the topological approach. The approach has been widely tested in a 50/spl times/25 m portion of the institute building with the new fully autonomous robot Donald Duck. 25 randomly generated test missions were performed with a success ratio of 96% and a mean error at the goal point of 9 mm for an overall trajectory length of 1.15 km.

An approach combining the metric and topological paradigm for simultaneous localization and map building is presented The main idea is to connect local metric maps by means of a global topological map. This allows a compact environment model which does not require global metric consistency and permits both precision and robustness. The method uses a 360 degree laser scanner in order to extract corners and openings for the topological approach and lines for the metric localization. The approach has been tested in a 30 /spl times/ 25 m portion of the institute building with the fully autonomous robot Donald Duck An experiment consists of a complete exploration and a set of test missions. Three experiments have been performed for a total of 15 test missions, which have been randomly defined and completed with a success ratio of 87%.

In this paper a multisensor setup for localization consisting of a 360 degree laser range finder and a monocular vision system is presented. Its practicability under conditions of continuous localization during motion in real-time (referred to as on-the-fly localization) is investigated in large-scale experiments. The features in use are infinite horizontal lines for the laser and vertical lines for the camera providing an extremely compact environment representation. They are extracted using physically well-grounded models for all sensors and passed to the Kalman filter for fusion and position estimation. Very high localization precision is obtained in general. The vision information has been found to further increase this precision, particular in the orientation, already with a moderate number of matched features. The results were obtained with a fully autonomous system where extensive tests with an overall length of more than 1.4 km and 9,500 localization cycles have been conducted. Furthermore, general aspects of multisensor on-the-fly localization are discussed.

Starting from a user point of view the paper discusses the requirements of a development environment (operating system and programming language) for mechatronic systems, especially mobile robots. We argue that user require ments from research, education, ergonomics and applications impose a certain functionality on the embedded operating system and programming language, and that a deadline-driven real-time operating system helps to fulfil these requirements. A case study of the operating system XO/2, its programming language Oberon-2 and the mobile robot Pygmalion is presented. XO/2 explicitly addresses issues like scalabilty, safety and abstraction, previously found to be relevant for many user scenarios.