We address the problem of systematically covering all accessible floor space in an unknown environment by a mobile robot. Our approach uses rectangular regions that are swept across the environment. In the first stage, the robot covers each region using the classic boustrophedon pattern and planning paths to uncovered areas within the region while keeping track of its position uncertainty. The region is then moved sideways to cover the next part of the environment until all accessible space has been visited. In the second stage, the robot revisits the perimeter around the obstacles. We compare our method in terms of total trajectory length to 5 off-line methods including the distance transformation by Zelinsky et al. [1] in a standard test environment as well as in multi-room homes. The presented method has been employed in our Mint cleaning robot [2] for autonomously sweeping and mopping the floors.

Localization using continuous signals such as WiFi or active beacons is a cost-effective approach for enabling systematic navigation of robots. In our previous work we showed how localization maps, represented as regular grids, of such signals can be learned through application of vector field SLAM [1]. In this paper we describe a method that, given such a localization map, finds the pose of a mobile robot from observations of the signals. Our method first generates pose hypotheses by searching the localization map for places that best fit to a measurement taken by the robot. A localization filter using an extended Kalman filter (EKF) then verifies one pose hypothesis by tracking the pose over a short distance. In experiments carried out in a standard test environment equipped with active beacons we obtain an average position accuracy of 10 to 35 cm with a localization success rate of 96 to 99 %. The proposed method enables a robot mapping an environment using vector field SLAM to recover from kidnapping and resume its navigation.

Localization in unknown environments using low-cost sensors on embedded hardware is challenging. Yet, it is a requirement for consumer robots if systematic navigation is desired. In this paper, we present a localization approach that learns the spatial variation of an observed continuous signal over the environment. We model the signal as a piecewise linear function and estimate its parameters using a simultaneous localization and mapping (SLAM) approach. By applying the concepts of the exactly sparse extended information filter (ESEIF) , a constant-time, linear-space algorithm is obtained under certain approximations. We apply our framework to a sensor measuring bearing to active beacons, where measurements are distorted because of occlusion and signal reflections. Experimental results from running GraphSLAM, extended Kalman filter SLAM, and ESEIF-SLAM on manually collected sensor measurements, as well as on data recorded on a vacuum-cleaner robot, validate our model. The ESEIF-SLAM solution is evaluated on an ARM 7 embedded board with 64-kB RAM connected to a Roomba 510 vacuum cleaner. The presented methods are also used in Evolution Robotics ' Mint Cleaner product for autonomous floor cleaning.

Localization in unknown environments using low-cost sensors remains a challenge. This paper presents a new localization approach that learns the spatial variation of an observed continuous signal. We model the signal as a piece-wise linear function and estimate its parameters using a simultaneous localization and mapping (SLAM) approach. We apply our framework to a sensor measuring bearing to active beacons where measurements are systematically distorted due to occlusion and signal reflections of walls and other objects present in the environment. Experimental results from running GraphSLAM and EKF-SLAM on manually collected sensor measurements as well as on data recorded on a vacuum-cleaner robot validate our model.

With the development of biped robots, systems became able to navigate in a 3 dimensional world, walking up and down stairs, or climbing over small obstacles. We present a method for obtaining a labeled 2.5D grid map of the robot's surroundings. Each cell is marked either as floor or obstacle and contains a value telling the height of the floor or obstacle. Such height maps are useful for path planning and collision avoidance. The method uses a novel combination of a 3D occupancy grid for robust sensor data interpretation and a 2.5D height map for fine resolution floor values. We evaluate our approach using stereo vision on the humanoid robot QRIO and show the advantages over previous methods. Experimental results from navigation runs on an obstacle course demonstrate the ability of the method to generate detailed maps for autonomous navigation.

This work presents methods for path planning and obstacle avoidance for the humanoid robot QRIO, allowing the robot to autonomously walk around in a home environment. For an autonomous robot, obstacle detection and localization as well as representing them in a map are crucial tasks for the success of the robot. Our approach is based on plane extraction from data captured by a stereo-vision system that has been developed specifically for QRIO. We briefly overview the general software architecture composed of perception, short and long term memory, behavior control, and motion control, and emphasize on our methods for obstacle detection by plane extraction, occupancy grid mapping, and path planning. Experimental results complete the description of our system.

For the fully autonomous navigation in a 3 dimensional world, a humanoid robot must be capable of stepping up and down staircases and other obstacle where a sufficient large flat surface can support the robot's feet. This paper presents methods for the recognition of stairs and a control architecture that enable the humanoid robot QRIO to safely climb up and down in its environment The approach is based on data captured by a stereo vision system and segmented into planar surfaces. From the segmented planes, stairs that can be climbed by the robot are extracted and fed to a control system which decides the action to be taken next. Experimental results on a staircase as well as climbing up and down a sill are presented.

This paper describes a method for identifying an environment a robot is operating in by comparing the geometry of landmarks of a map the robot is currently building with a set of previously created maps. Landmark maps are created using the stochastic map approach originally presented by Smith, Self and Cheeseman [1990]. The paper provides a method for measuring the similarity of such maps and presents a closed form solution for the special case that covariances are constant. Experiments carried out on a developer version of the AlBO robot and on a prototype of the humanoid SDR-4X robot show that the approach is applicable even for robots with poor odometry.

Localization is one of the fundamental problems in mobile robot navigation. Past experiments have shown that, in general, grid-based Markov localization is more robust than Kalman filtering while the latter can be more accurate than the former Recently new methods for localization employing particle filters have become popular. In this paper, we compare different localization methods using Kalman filtering, grid-based Markov localization, Monte Carlo Localization (MCL), and combinations thereof. We give experimental evidence that a combination of Markov localization and Kalman filtering as well as a variant of MCL outperform the other methods in terms of accuracy, robustness, and time needed for recovering from manual robot displacement, while requiring only few computational resources.

Robotic soccer is a challenging research domain because many different research areas have to be addressed in order to create a successful team of robot players. The paper presents the CS Freiburg team, the winner in the middle-size league at RoboCup 1998, 2000, and 2001. The paper focuses on multiagent coordination for both perception and action. The contributions of the paper are new methods for tracking ball and players observed by multiple robots, team coordination methods for strategic team formation and dynamic role assignment; a rich set of basic skills allowing robots to respond to a large range of situations in an appropriate way, and an action-selection method based on behavior networks, as well as a method to learn the skills and their selection. As demonstrated by evaluations of the different methods and by the success of the team, these methods permit the creation of a multirobot group which is able to play soccer successfully. In addition, the developed methods promise to advance the state of the art in the multirobot field.

Robust and accurate object recognition and tracking is a necessary pre-requisite for visual servoing tasks. This paper presents a new approach using disparity images provided by a stereo vision system from which 3D models are reconstructed. We use a segmentation procedure based on a simple region growing process to segment the non-dense 3D images, and compare it to a classical dense range image segmenter. The obtained regions are classified according to a simple model of the target object, and multiple candidates are handled over image sequences by application of the CONDENSATION algorithm. We then use a histogram based clusterization technique to identify the target object pose for visual servoing commands. Experimental results in localizing a door-handle show an accuracy of about 10 cm for the estimated position, while being robust to clutter and noise in the sensor images.

This work presents methods for tracking objects from noisy and unreliable data taken by a team of robots. We develop a multi-object tracking algorithm based on Kalman filtering and a single-object tracking method involving a combination of Kalman filtering and Markov localization for outlier detection. We apply these methods in the context of robot soccer for robots participating in the RoboCup middle-size league and compare them to a simple averaging method. Results including situations from real competition games are presented.

Self-localization is important in almost all robotic tasks. For playing an aesthetic and effective game of robotic soccer, self-localization is a necessary prerequisite. When we designed our robotic soccer team for RoboCup'98, it turned out that all existing approaches did not meet our requirements of being fast, accurate, and robust. For this reason, we developed a new method, which is presented and analyzed in the paper We additionally present experimental evidence that our method outperforms other methods in the RoboCup environment.

Localization is the process of updating the pose of a robot in an environment, based on sensor readings. In this experimental study, we compare two methods for localization of indoor mobile robots: Markov localization, which uses a probability distribution across a grid of robot poses; and scan matching, which uses Kalman filtering techniques based on matching sensor scans. Both these techniques are dense matching methods, that is, they match dense sets of environment features to an a priori map. To arrive at results for a range of situations, we utilize several different types of environments, and add noise to both the dead-reckoning and the sensors. Analysis shows that, roughly, the scan-matching techniques are more efficient and accurate, but Markov localization is better able to cope with large amounts of noise. These results suggest hybrid methods that are efficient, accurate and robust to noise.