Motion planning plays a key role in autonomous driving. In this work, we introduce the combinatorial aspect of motion planning which tackles the fact that there are usually many possible and locally optimal solutions to accomplish a given task. Those options we call maneuver variants. We argue that by partitioning the trajectory space into discrete solution classes, such that local optimization methods yield an optimum within each discrete class, we can improve the chance of finding the global optimum as the optimum trajectory among the manuever variants. This work provides methods to enumerate the maneuver variants as well as constraints to enforce them. The return of the effort put into the problem modification as suggested is gaining assuredness in the convergency behaviour of the optimization algorithm. We show an experiment where we identify three local optima that would not have been found with local optimization methods.

In this paper we propose a highly detailed map for the field of autonomous driving. We introduce the notion of lanelets to represent the drivable environment under both geometrical and topological aspects. Lanelets are atomic, interconnected drivable road segments which may carry additional data to describe the static environment. We describe the map specification, an example creation process as well as the access library libLanelet which is available for download. Based on the map, we briefly describe our behavioural layer (which we call behaviour generation) which is heavily exploiting the proposed map structure. Both contributions have been used throughout the autonomous journey of the Mercedes Benz S 500 Intelligent Drive following the Bertha Benz Memorial Route in summer 2013.

Estimating surface normals is an important task in computer vision, e.g. in surface reconstruction, registration and object detection. In stereo vision, the error of depth reconstruction increases quadratically with distance. This makes estimation of surface normals an especially demanding task. In this paper, we analyze how error propagates from noisy disparity data to the orientation of the estimated surface normal. Firstly, we derive a transformation for normals between disparity space and world coordinates. Afterwards, the propagation of disparity noise is analyzed by means of a Monte Carlo method. Normal reconstruction at a pixel position requires to consider a certain neighborhood of the pixel. The extent of this neighborhood affects the reconstruction error. Our method allows to determine the optimal neighborhood size required to achieve a pre specified deviation of the angular reconstruction error, defined by a confidence interval. We show that the reconstruction error only depends on the distance of the surface point to the camera, the pixel distance to the principal point in the image plane and the angle at which the viewing ray intersects the surface.

In this paper, we present the strategy for trajectory planning that was used on-board the vehicle that completed the 103 km of the Bertha-Benz-Memorial-Route fully autonomously. We suggest a local, continuous method that is derived from a variational formulation. The solution trajectory is the constrained extremum of an objective function that is designed to express dynamic feasibility and comfort. Static and dynamic obstacle constraints are incorporated in the form of polygons. The constraints are carefully designed to ensure that the solution converges to a single, global optimum.

In August 2013, the modified Mercedes-Benz SClass S500 Intelligent Drive (“Bertha”) completed the historic Bertha-Benz-Memorial-Route fully autonomously. The self-driving 103 km journey passed through urban and rural areas. The system used detailed geometric maps to supplement its online perception systems. A map based approach is only feasible if a precise, map relative localization is provided. The purpose of this paper is to give a survey on this corner stone of the system architecture. Two supplementary vision based localization methods have been developed. One of them is based on the detection of lane markings and similar road elements, the other exploits descriptors for point shaped features. A final filter step combines both estimates while handling out-of-sequence measurements correctly.

Next generation driver assistance systems require precise self localization. Common approaches using global navigation satellite systems (GNSSs) suffer from multipath and shadowing effects often rendering this solution insufficient. In urban environments this problem becomes even more pronounced. Herein we present a system for six degrees of freedom (DOF) ego localization using a mono camera and an inertial measurement unit (IMU). The camera image is processed to yield a rough position estimate using a previously computed landmark map. Thereafter IMU measurements are fused with the position estimate for a refined localization update. Moreover, we present the mapping pipeline required for the creation of landmark maps. Finally, we present experiments on real world data. The accuracy of the system is evaluated by computing two independent ego positions of the same trajectory from two distinct cameras and investigating these estimates for consistency. A mean localization accuracy of 10 cm is achieved on a 10 km sequence in an inner city scenario.

We present the hardware design, software architecture, and core algorithms of Herb 2.0, a bimanual mobile manipulator developed at the Personal Robotics Lab at Carnegie Mellon University, Pittsburgh, PA. We have developed Herb 2.0 to perform useful tasks for and with people in human environments. We exploit two key paradigms in human environments: that they have structure that a robot can learn, adapt and exploit, and that they demand general-purpose capability in robotic systems. In this paper, we reveal some of the structure present in everyday environments that we have been able to harness for manipulation and interaction, comment on the particular challenges on working in human spaces, and describe some of the lessons we learned from extensively testing our integrated platform in kitchen and office environments.

In this paper, we present the concepts and methods developed for the autonomous vehicle known as AnnieWAY, which is our winning entry to the 2011 Grand Cooperative Driving Challenge. We describe algorithms for sensor fusion, vehicle-to-vehicle communication, and cooperative control. Furthermore, we analyze the performance of the proposed methods and compare them with those of competing teams. We close with our results from the competition and lessons learned.

Accurate 3d perception from video sequences is a core subject in computer vision and robotics, since it forms the basis of subsequent scene analysis. In practice however, online requirements often severely limit the utilizable camera resolution and hence also reconstruction accuracy. Furthermore, real-time systems often rely on heavy parallelism which can prevent applications in mobile devices or driver assistance systems, especially in cases where FPGAs cannot be employed. This paper proposes a novel approach to build 3d maps from high-resolution stereo sequences in real-time. Inspired by recent progress in stereo matching, we propose a sparse feature matcher in conjunction with an efficient and robust visual odometry algorithm. Our reconstruction pipeline combines both techniques with efficient stereo matching and a multi-view linking scheme for generating consistent 3d point clouds. In our experiments we show that the proposed odometry method achieves state-of-the-art accuracy. Including feature matching, the visual odometry part of our algorithm runs at 25 frames per second, while - at the same time - we obtain new depth maps at 3-4 fps, sufficient for online 3d reconstructions.

Modern driver assistance systems such as collision avoidance or intersection assistance need reliable information on the current environment. Extracting such information from camera-based systems is a complex and challenging task for inner city traffic scenarios. This paper presents an approach for object detection utilizing sparse scene flow. For consecutive stereo images taken from a moving vehicle, corresponding interest points are extracted. Thus, for every interest point, disparity and optical flow values are known and consequently, scene flow can be calculated. Adjacent interest points describing a similar scene flow are considered to belong to one rigid object. The proposed method does not rely on object classes and allows for a robust detection of dynamic objects in traffic scenes. Leading vehicles are continuously detected for several frames. Oncoming objects are detected within five frames after their appearance.

Safe handling of dynamic highway and inner city scenarios with autonomous vehicles involves the problem of generating traffic-adapted trajectories. In order to account for the practical requirements of the holistic autonomous system, we propose a semi-reactive trajectory generation method, which can be tightly integrated into the behavioral layer. The method realizes long-term objectives such as velocity keeping, merging, following, stopping, in combination with a reactive collision avoidance by means of optimal-control strategies within the Frenét-Frame of the street. The capabilities of this approach are demonstrated in the simulation of a typical high-speed highway scenario.

Numerous applications require precise determination of the motion of a textured surface. Image based sensors are attractive for this purpose, since they are contactless and do not suffer from slip effects. Moreover, they do not only measure scalar speed, but can determine velocity as a 2D vectorial quantity, and, if two sensors are combined, can even observe yaw rate of the surface. If this kind of sensor is mounted inversely on a vehicle, it can determine its motion by measuring the relative displacement of the road surface. In this paper we will use a commercial motion sensor that has been originally designed for application in an optical computer mouse. We will show that, by well-considered dimensioning of the optical part of the system, this sensor can measure velocities in a range that is typical for automotive application. The result is a highly integrated, low-cost, angle sensitive motion sensor that does not exhibit slip effects. We evaluate this sensor through testing on a vehicle that is equipped with reference sensors, with special consideration on the advantages of this measurement principle over conventional wheel speed sensors.

We present a method for fast collision checking that is suitable for application in motion planning for intelligent vehicles. One of the difficulties that arises in this domain is the fact that typical, car-like autonomous vehicles cannot easily be approximated by a rotationally invariant disk shape. Instead, the orientation of the vehicle must be accounted for explicitly. Our proposal is to decompose the vehicle shape into several disk shaped primitives, so that the task of collision checking can be broken down into few very simple collision tests. We also propose a highly optimised method to perform these primitive collision tests that requires a minimum of arithmetic operations. We show by experiments that our method bears significant performance benefits over conventional methods.

We present a method for motion planning in the presence of moving obstacles that is aimed at dynamic on-road driving scenarios. Planning is performed within a geometric graph that is established by sampling deterministically from a manifold that is obtained by combining configuration space and time. We show that these graphs are acyclic and shortest path algorithms with linear runtime can be employed. By reparametrising the configuration space to match the course of the road, it can be sampled very economically with few vertices, and this reduces absolute runtime further. The trajectories generated are quintic splines. They are second order continuous, obey nonholonomic constraints and are optimised for minimum square of jerk. Planning time remains below 20 ms on general purpose hardware.

We propose a novel method for tracking an articulated model in a 3D-point cloud. The tracking problem is formulated as the registration of two point sets, one of them parameterised by the model’s state vector and the other acquired from a 3D-sensor system. Finding the correct parameter vector is posed as a linear estimation problem, which is solved by means of a scaled unscented Kalman filter. Our method draws on concepts from the widely used iterative closest point registration algorithm (ICP), basing the measurement model on point correspondences established between the synthesised model point cloud and the measured 3D-data. We apply the algorithm to kinematically track a model of the human upper body on a point cloud obtained through stereo image processing from one or more stereo cameras. We determine torso position and orientation as well as joint angles of shoulders and elbows. The algorithm has been successfully tested on thousands of frames of real image data. Challenging sequences of several minutes length where tracked correctly. Complete processing time remains below one second per frame.