Cyrill Stachniss

The problem of learning maps is one of the fundamental problems in mobile robotics. Models of the environment are needed for a series of applications such as transportation, cleaning, rescue, and various other service robotic tasks. Learning maps passively, i.e. by perceiving sensor data only, requires the solution of two tasks, which are mapping, and localization. Mapping is the problem of integrating the information gathered with the robot's sensors into a given representation. It can intuitively be described by the question ``What does the world look like?'' Central aspects in mapping are the representation of the environment and the interpretation of sensor data. In contrast to this, localization is the problem of estimating the pose of the robot relative to a map. In other words, the robot has to answer the question ``Where am I?'' These two tasks cannot be solved independently of each other.

Whenever robots operate in the real world, not only their observations but also their motion is affected by noise. Building accurate spatial models under those conditions is widely known as the simultaneous localization and mapping (SLAM) problem. In the last few years, we developed two solution to the SLAM problem. the first one is based on a Rao-Blackwellized particle filter. A Rao-Blackwellized particle filter is a probabilistic state estimation technique that can deal with non-Gaussian noise and provides a joint posterior about the map of the environment and the trajectory taken by the robot. Our mapping approach uses an informed proposal distribution to create the next generation of particles. This allows us to draw samples only in those areas where the robot is likely to be located. As a result, our technique can construct grid maps from large datasets in indoor as well as in structured outdoor environments. Our approach makes no assumptions about the structure of the environment such as parallel walls or any pre-defined feature extractors.

The second solution uses the so-called graph-based or network-based formulation of the SLAM problems in which the poses of the robot are modeled by nodes in a graph. Constraints between poses resulting from observations or from odometry are encoded in the edges between the nodes. The goal of an algorithm designed to solve this problem is to find the configuration of the nodes that maximizes the observation likelihood encoded in the constraints. We developed an approach that extends Olson's algorithm and uses a variant of stochastic gradient descent to compute network configurations with low errors. We parameterize the nodes in the graph using a tree which yields several improvements verses traditional parameterizations. Additionally, we are able to bound the complexity to the size of the environment and not to the length of the trajectory.

Traditional approaches to mapping assume that the environment is static. We address the problem of mapping and localization in non-static environments. The assumption of a static world is unrealistic since most places in which robots are deployed are populated by humans. Instead of removing the non-static aspects from the map as most related approaches do, we present a technique to map their typical configurations. The idea behind this approach is that several non-static objects occur only in a limited number of states. Doors, for example, are typically either open or closed and a parking lot is either free or occupied by a car. Our approach allows a robot to consider different spatial configurations of the environment and in this way makes the localization of the vehicle more robust and more accurate in non-static worlds.

SLAM approaches are entirely passive. That means that they only perceive sensor data but do not need to generate actions to guide the robot through its environment. Whenever a robot is required to autonomously learn a model of the environment it has also to decide where to move next. The selected action, however, can have a significant influence on the resulting map build by the SLAM approach. Thus, an integrated system needs to consider SLAM and action selection at the same time. These methods are also called solutions to the simultaneous localization, mapping, and planning (SLAMP) problem.

We developed algorithms that allows a robot to simultaneously deal with its pose uncertainty, with the uncertainty in its sensor data, and in its map. It applies a Rao-Blackwellized particle filter to model the posterior about the trajectory of the vehicle and the map of the environment. The decision-theoretic action selection technique aims to minimize the uncertainty in this joint posterior. Whenever our approach evaluates a set of actions, it takes into account sequences of potential observations in order to minimize this uncertainty. This is achieved by simulating observation sequences based on the joint posterior. The actions that are taken into account guide the robot in order to explore unknown areas, move it to places which are well-known in order to reduce the pose uncertainty, or actively close loops. As a result, we obtain a robust active map learning approach that (i) minimizes the uncertainty in the robot's world model, (ii) solves the SLAM problem, (iii) considers exploration, place revisiting, and loop-closing actions, (iv) considers the cost of carrying out an action, and (v) reasons about potential observation sequences based on the posterior about the map of the environment.

The use of multiple robots is often suggested to have advantages over single robot systems. First, cooperating robots have the potential to accomplish a task faster than a single robot. Another advantage of robot teams arises from merging overlapping sensor information, which can help to compensate for sensor uncertainty. However, when robots operate in teams there is the risk of interference between them. For example the more robots that are used, the more time each robot may spend on detours in order to avoid collisions with other members of the team. Efficient exploration techniques that seek to minimize the overall time to complete the task should consider techniques to distribute the robots over the environment and to reduce the number of redundantly explored areas.

We presented algorithms for coordinating a group of robots that enables them to efficiently explore their environment. The goal is to complete the task as fast as possible. Our technique assigns a utility to each target location and follows a decision-theoretic approach to explicitly coordinate the robots. It does so by maximizing the overall utility and by minimizing the potential for overlap in information gain amongst the various robots. The algorithm simultaneously considers the utility of observing unexplored areas and the cost for reaching these areas. By trading off the utilities and the cost and by reducing the utilities according to the number of robots that are already heading towards this area, coordination is achieved in an elegant way. In practice, one also has to deal with problems like limited communication ranges of the network that limit the ability of the vehicles to exchange data. Naturally, the task of exploring a terrain with limited communication range is harder than without this constraint.

Since DARPA Grand Challenge 2005, the usage of cars instead of classical mobile robots became popular in the research community. Compared to standard robots, cars offer the possibility to travel longer distances, carry more sensors, and thus being more suitable for tasks such as mapping large areas.

In cooperation between the ETH Zurich, the EPLF in Lausanne and the University of Freiburg, we build an autonomous Smart car that is equipped with a series of sensors. It uses an inertial measurement unit, a differential GPS, an optical gyro, and the wheel encoders. To perceive the surroundings it uses five laser range finders. Three of them point to the front of the car and two are rotating on top of the roof of the car. With this setup, we realized autonomous navigation and build a platform for large scale mapping.

Using learning techniques in the context of robots allows them to adapt their behavior based on previous observations. This is one of the prerequisites for truly autonomous vehicles. In our research, we used different technique to avoid the usage of preprogrammed an d manually tuned feature extractors which are used to make decisions in an heuristic way. Instead, we applied for example boosting technique such as AdaBoost to learn classifies that allow the robot to estimate the sematic place it is currently in. In this way, the robot can determine if it it currently located in a room, an office, etc. In combination with probabilistic relaxation, even accurate topological maps can be constructed autonomously
Additionally, we applied Gaussian processes to estimate the geometry of the environment based on monocular vision data only. By treating this task as a non-linear regression problem, comparably accurate estimate can be obtained.

Cameras have become popular sensors in the robotics community. Compared to proximity sensors such as laser range finders, they have the advantage of being cheap, lightweight, and energy efficient. The drawback of cameras, however, is the fact that due to the projective nature of the image formation process, it is not possible to sense depth information directly. Thus, from a geometric point of view, one needs at least two images taken from different locations to recover the depth information analytically.

To overcome this limitation, one can learn a range function that maps orientation angles to the corresponding distances to obstacles. Such a function can then be utilized in a wide variety of existing solutions to robotic problems, such as mapping, localization, exploration, or place classification. In a recent approach, we formulated the problem as a supervised regression problem, in which the training set is build by acquiring images of the environment as well as ground truth proximity data using a laser range finder. We apply Gaussian processes as the learning framework in our proposed system, since this technique is able to model non-linear functions, offers a direct way of estimating uncertainties for its predictions, and it has proved successful in previous work on range functions. The approach allows us to prediction range information similar to the one obtained by a laser range finder based on a single monocular image.

We furthermore investigated the use of visual data to detect objects and to utilize this information when trying to identify semantic labels of places in the environment such as kitchens, offices, etc. By extracting features and combining these data with laser range information, it is possible to accurately estimate the type of place a robot is currently in.

Path planning is one of the fundamental problems in robotics, and the ability to plan collision-free paths is a precondition for numerous applications of autonomous robots. The path planning problem has traditionally received considerable attention in the past and has been well-studied. The majority of approaches, however, has focused on the problem of planning paths in static environments and with rigid obstacles. We studied the planning problem considering the kinematic constraints of the vehicle. This allows a robot to plan trajectories which are slightly longer than other but the robot is able to move faster along such trajectories.

We furthermore investigated scenarios in which not all objects are ridged. Taking the knowledge about non-ridged objects into account can enable a robot to accomplish navigation tasks that otherwise cannot be carried out. For example, in our everyday life we deal with many deformable objects such as plants, curtains, or cloth and we typically utilize the information about the deformability of objects when planning a path. Our approach allows a mobile robot to determine the deformation cost introduced by passing the curtain and to utilize this information during path planning. The key idea of our approach is to use a heuristic function leaned based on offline simulations to estimate the deformation cost, which allows the robot to perform the necessary calculations online.