Christoph Sprunk

Robot navigation is one of the most studied problems in robotics and the key capability for robot autonomy. Navigation techniques have become more and more reliable, but evaluation mainly focused on individual navigation components (i.e., mapping, localization, and planning) using datasets or simulations. The goal of this paper is to define an experimental protocol to evaluate the whole navigation system, deployed in a real environment. To ensure repeatability and reproducibility of experiments, our benchmark protocol provides detailed definitions and controls the environment dynamics. We define standardized environments and introduce the concept of a reference robot to allow comparison between different navigation systems at different experimentation sites. We present applications of our protocol in experiments in two different research groups, showing the usefulness of the benchmark.

Enhanced logistics is widely regarded as a key technology to increase flexibility and cost efficiency of today’s factories. For example, fully autonomous transport vehicles aim to gradually replace conveyor belts, guided vehicles, and manual labor. In this context, especially omnidirectional robots are appealing thanks to their advanced maneuvering capabilities. In industrial applications, however, accuracy as well as safety and efficiency are key requirements for successful navigation systems. In this paper, we present an accurate navigation system for omnidirectional robots. Our system includes dedicated modules for mapping, localization, trajectory generation and robot control. It has been designed for accurate execution by devising smooth, curvature continuous trajectories, by planning appropriate velocities and by accounting for platform and safety constraints. In this way, it completely utilizes the maneuvering capabilities of omnidirectional robots and optimizes trajectories with respect to time of travel. We present extensive experimental evaluations in simulation and in changing real-world environments to demonstrate the robustness and accuracy of our system.

Mobile robots are increasingly populating our human environments. To interact with humans in a socially compliant way, these robots need to understand and comply with mutually accepted rules. In this paper, we present a novel approach to model the cooperative navigation behavior of humans. We model their behavior in terms of a mixture distribution that captures both the discrete navigation decisions, such as going left or going right, as well as the natural variance of human trajectories. Our approach learns the model parameters of this distribution that match, in expectation, the observed behavior in terms of user-defined features. To compute the feature expectations over the resulting high-dimensional continuous distributions, we use Hamiltonian Markov chain Monte Carlo sampling. Furthermore, we rely on a Voronoi graph of the environment to efficiently explore the space of trajectories from the robot’s current position to its target position. Using the proposed model, our method is able to imitate the behavior of pedestrians or, alternatively, to replicate a specific behavior that was taught by tele-operation in the target environment of the robot. We implemented our approach on a real mobile robot and demonstrated that it is able to successfully navigate in an office environment in the presence of humans. An extensive set of experiments suggests that our technique outperforms state-of-the-art methods to model the behavior of pedestrians, which also makes it applicable to fields such as behavioral science or computer graphics.

In robotics, grid maps are often used for solving tasks like collision checking, path planning, and localization. Many approaches to these problems use Euclidean distance maps (DMs), generalized Voronoi diagrams (GVDs), or configuration space (c-space) maps. A key challenge for their application in dynamic environments is the efficient update after potential changes due to moving obstacles or when mapping a previously unknown area. To this end, this paper presents novel algorithms that perform incremental updates that only visit cells affected by changes. Furthermore, we propose incremental update algorithms for DMs and GVDs in the configuration space of non-circular robots. These approaches can be used to implement highly efficient collision checking and holonomic path planning for these platforms. Our c-space representations benefit from parallelization on multi-core CPUs and can also be integrated with other state-of-the-art path planners such as rapidly-exploring random trees. In various experiments using real-world data we show that our update strategies for DMs and GVDs require substantially less cell visits and computation time compared to previous approaches. Furthermore, we demonstrate that our GVD algorithm deals better with non-convex structures, such as indoor areas. All our algorithms consider actual Euclidean distances rather than grid steps and are easy to implement. An open source implementation is available online.

In the last years, many researchers started to consider teach-and-repeat approaches for reliable autonomous navigation. The paradigm, in all its proposed forms, is deeply rooted in the idea that the robot should autonomously follow a route that has been demonstrated by a human during a teach phase. However, human demonstrations are often inefficient in terms of execution time or may cause premature wear of the robot components due to jittery behavior or strong accelerations. In this paper, we propose the concept of teach, optimize and repeat, which introduces a trajectory optimization step between the teach and repeat phases. To address this problem, we further propose LexTOR, a constrained trajectory optimization method for teach and repeat problems, where the constraints are defined according to user preferences. At its core, LexTOR optimizes both the execution time and the trajectory smoothness in a lexicographic sense. The experiments show that LexTOR is very effective, both qualitatively and quantitatively, in terms of execution time, smoothness, accuracy and bound satisfaction.

The typically restricted field of view of visual sensors often imposes limitations on the performance of localization and simultaneous localization and mapping (SLAM) approaches. In this paper, we propose and analyze the combination of an RGB-D camera with two planar mirrors to split the field of view such that it covers both front and rear view of a mobile robot. We describe how to estimate the extrinsic calibration parameters of the modified sensor using a standard parametrization and a reduced one that exploits the properties of the setup. Our experimental evaluation on real-world data demonstrates the robustness of the calibration procedure. Additionally, we show that our proposed sensor modification substantially improves the accuracy and the robustness in a simultaneous localization and mapping task.

In mobile robot navigation, cost functions are a popular approach to generate feasible, safe paths that avoid obstacles and that allow the robot to get from its starting position to the goal position. Alternative ways to navigate around the obstacles typically correspond to different local minima in the cost function. In this paper we present a highly effective approach to overcome such local minima and to quickly propose a set of alternative, topologically different and optimized paths. We furthermore describe how to maintain a set of optimized trajectory alternatives to reduce optimization efforts when the robot has to adapt to changes in the environment. We demonstrate in experiments that our method outperforms a state-of-the-art approach by an order of magnitude in computation time, which allows a robot to use our method online during navigation. We furthermore demonstrate that the approach of using a set of qualitatively different trajectories is beneficial in shared autonomy settings, where a user operating a wheelchair can quickly switch between topologically different trajectories.

Platforms with holonomic drives are particularly interesting due to their maneuvering capabilities. Robots used for transportation tasks usually have a non-circular footprint. In this work, we present a navigation strategy for a holonomic mobile robot with anyshape footprint. Our technique introduces an efficient navigation method based on a strategy that makes use of discrete and continuous techniques. We introduce compact discrete intervals to represent the free space for computing fast-to-update plans. Based on these, we provide a continuous motion generation approach to generate smooth motions that are fast to compute. We evaluated our approach by running simulated experiments and by using a real holonomic L-shaped robot. Our experiments demonstrate that our technique can be carried out online and is able to smoothly drive the robot to its goal locations even in dynamic environments.

Automation of logistics tasks for small lot sizes and flexible production processes requires intuitive and easy-to-use systems that allow non-expert shop floor workers to naturally instruct transportation systems. To this end, we present a novel laser-based scheme for teach-and-repeat of mobile robot trajectories that relies on scan matching to localize the robot relative to a taught trajectory, which is represented by a sequence of raw odometry and 2D laser data. This approach has two advantages. First, it does not require to build a globally consistent metrical map of the environment, which reduces setup time. Second, the direct use of raw sensor data avoids additional errors that might be introduced by the fact that grid maps only provide an approximation of the environment. Real-world experiments carried out with a holonomic and a differential drive platform demonstrate that our approach repeats trajectories with an accuracy of a few millimeters. A comparison with a standard Monte Carlo localization approach on grid maps furthermore reveals that our method yields lower tracking errors for teach-and-repeat tasks.

Many applications in mobile robotics and especially industrial applications require that the robot has a precise estimate about its pose. In this paper, we analyze the accuracy of an integrated laser-based robot pose estimation and positioning system for mobile platforms. For our analysis, we used a highly accurate motion capture system to precisely determine the error in the robot's pose. We are able to show that by combining standard components such as Monte-Carlo localization, KLD sampling, and scan matching, an accuracy of a few millimeters at taught-in reference locations can be achieved. We believe that this is an important analysis for developers of robotic applications in which pose accuracy matters.

Mobile robots that operate in a shared environment with humans need the ability to predict the movements of people to better plan their navigation actions. In this paper, we present a novel approach to predict the movements of pedestrians. Our method reasons about entire trajectories that arise from interactions between people in navigation tasks. It applies a maximum entropy learning method based on features that capture relevant aspects of the trajectories to determine the probability distribution that underlies human navigation behavior. Hence, our approach can be used by mobile robots to predict forthcoming interactions with pedestrians and thus react in a socially compliant way. In extensive experiments, we evaluate the capability and accuracy of our approach and demonstrate that our algorithm outperforms the popular social forces method, a state-of-the-art approach. Furthermore, we show how our algorithm can be used for autonomous robot navigation using a real robot.

In this paper, we present improved spline fitting techniques with the application of trajectory teaching for mobile robots. Given a recorded reference trajectory, we apply non-linear least-squares optimization to accurately approximate the trajectory using a parametric spline. The fitting process is carried out without fixed correspondences between data points and points along the spline, which improves the fit especially in sharp curves. By using a specific path model, our approach requires substantially fewer free parameters than standard approaches to achieve similar residual errors. Thus, the generated paths are ideal for subsequent optimization to reduce the time of travel or for the combination with autonomous planning to evade obstacles blocking the path. Our experiments on real-world data demonstrate the advantages of our method in comparison with standard approaches.

This paper presents a novel approach to kino-dynamic trajectory generation for non-circular omnidirectional platforms that can be combined with existing path planners. We use quintic Bézier splines to specify position and orientation of the holonomic robot for every point in time. To fully exploit the capabilities of the holonomic robot we propose a novel path representation. It allows for continuous variation of path shapes in the spectrum between straight-line paths with turns on the spot and smooth paths with independent rotations and translations. Using this representation our method optimizes trajectories according to a user-defined cost function, considering the constraints of the platform. This way, it generates fast and efficient trajectories in an anytime fashion. The experiments carried out on an industrial robot show that our approach generates highly efficient and smooth motion trajectories that can be tracked with high precision and predictability. Furthermore, the system operates in real-world environments containing unmapped obstacles and narrow passages.

This paper presents techniques to incrementally update collision maps, distance maps, and Voronoi diagrams in the configuration space of non-circular mobile robots. Compared to previous work, our approach only updates the cells affected by changes in the environment. Thus, it is applicable in large workspaces and in the presence of unknown or moving obstacles. The c-space collision maps allow for performing highly efficient collision checks in dynamically changing environments, for 2D, 2.5D, and 3D representations of robots and obstacles. By using the proposed c-space distance maps, long trajectories can efficiently be checked for collisions. Finally, our c-space Voronoi diagrams allow effective and complete path planning in narrow spaces. Our algorithms are easy to implement, benefit from parallelization on multi-core CPUs, and can be integrated with state-of-the-art path planners. Experiments demonstrate the effectiveness of our methods and show their applicability to real-world scenarios.

This paper presents novel, highly efficient approaches for updating Euclidean distance maps and Voronoi diagrams represented on grid maps. Our methods employ a dynamic variant of the brushfire algorithm to update only those cells that are actually affected by changes in the environment. In experiments in different environments we show that our update strategies for distance maps and Voronoi diagrams require substantially fewer cell visits and significantly less computation time compared to previous approaches. Furthermore, the dynamic Voronoi diagram also improves on previous work by correctly dealing with non-convex obstacles such as building walls. We also present a dynamic variant of a skeletonization-based approach to Voronoi diagrams that is especially robust to noise. All of our algorithms consider actual Euclidean distances rather than grid steps. An open source implementation is available online.

This paper presents an approach to time-optimal kinodynamic motion planning for a mobile robot. A global path planner is used to generate collision-free straight-line paths from the robot's position to a given goal location. With waypoints of this path, an initial trajectory is generated which defines the planned position of the robot over time. A velocity profile is computed that accounts for constraints on the velocity and acceleration of the robot. The trajectory is refined to minimize the time needed for traversal by an any-time optimization algorithm. An error-feedback controller generates motor commands to execute the planned trajectory. Quintic Bezier splines are used to allow for curvature-continuous joins of trajectory segments, which enables the system to replan trajectories in order to react to unmapped obstacles. Experiments on real robots are presented that show our system's capabilities of smooth, precise, and predictive motion.

In this paper a camera-based system for detection, tracking, and classification of U.S. speed signs is presented. The implemented application uses multiple connected stages and iteratively reduces the number of pixels to process for recognition. Possible sign locations are detected using a fast, shape-based interest operator. Remaining objects other than speed signs are discarded using a classifier similar to the Viola-Jones detector. Classification results from tracked candidates are utilized to improve recognition accuracy. On a standard PC the system reached a detection speed of 27fps with an accuracy of 98.8%. Including classification, speed sign recognition rates of 96.3% were achieved with a frame rate of approximately 11fps and one false alarm every 42s.

The ongoing automation of manufacturing processes increases productivity and reduces physically demanding labor, a cornerstone for today’s living standards and economic wealth in industrialized countries. However, industrial automation requires a costly setup phase. Therefore, it is only worthwhile when manufacturing large quantities of identical products. As globalization increases the pace of market changes and due to the trend towards product customization, there is a demand for more flexible, adaptable automation to retain global competitiveness for smaller batch sizes and changing products. Here, autonomous navigation is a key technology to reduce setup costs and increase flexibility. In this thesis, we present contributions towards the deployment of mobile robot naviga- tion in real-world industrial settings. We provide vehicle-based material transport between processes that is fast and intuitive to set up. Since our approaches only rely on wheel encoders and the mandatory safety scanners of an autonomous vehicle, they work without additional, inflexible infrastructure. We first propose a navigation system that enables omnidirectional vehicles to autonomously navigate with high accuracy while respecting safety constraints. Our system accounts for the dynamics of the vehicle when optimiz- ing smooth, curvature continuous trajectories that are frequently updated in changing environments. We furthermore present a localization and docking method to achieve millimeter accuracy at target locations. For use cases that require automated vehicles to follow predefined routes, we propose an approach for intuitive instruction that relies on user demonstrations and can be combined with our navigation system to realize different levels of autonomy. For scenarios with predefined routes only, we further reduce the setup costs. Our teach-and-repeat framework needs no pre-built environment map and only a single, non-expert demonstration to track taught trajectories with millimeter accuracy. For realistic estimates of the performance and reliability of navigation systems, we propose a benchmark protocol that instead of individual components evaluates complete systems. The tested system and a reference system interact with a carefully specified and scripted dynamic environment to ensure comparability between different evaluations. We conducted extensive experiments for all our systems. Through the combination of high accuracy and reliability with flexibility and ease of use, they present a substantial contribution towards navigation for flexible automation. Autonomous vehicles can also be equipped with robotic arms, e.g., welding robots mounted on autonomous vehicles instead of bolted to the factory floor. Beyond logistics, navigation can thereby contribute to efficiently reconfigurable process chains and the vision of transformable factories.