Hand-Drawn sketches are natural means by which abstract descriptions of environments can be provided. They represent weak prior information about the scene, thereby enabling a robot to perform autonomous navigation and exploration when a full metrical description of the environment is not available beforehand. In this paper, we present an extensive evaluation of our navigation system that uses a sketch interface to allow the operator of a robot to draw a rough map of an indoor environment as well as a desired trajectory for the robot to follow. We employ a theoretical framework for sketch interpretation, in which associations between the sketch and the real world are modeled as local deformations of a suitable metric manifold. We investigate the effectiveness of our system and present empirical results from a set of experiments in real-world scenarios, focusing both on the navigation capabilities and the usability of the interface.

Robots are expected to operate autonomously in increasingly complex scenarios such as crowded streets or heavy traffic situations. Perceiving the dynamics of moving objects in the environment is crucial for safe and smart navigation and therefore a key enabler for autonomous driving. In this paper we present a novel model-free approach for detecting and tracking dynamic objects in 3D LiDAR scans obtained by a moving sensor. Our method only relies on motion cues and does not require any prior information about the objects. We sequentially detect multiple motions in the scene and segment objects using a Bayesian approach. For robustly tracking objects, we utilize their estimated motion models. We present extensive quantitative results based on publicly available datasets and show that our approach outperforms the state of the art.

Text is one of the richest sources of information in an urban environment. Although textual information is heavily relied on by humans for a majority of the daily tasks, its usage has not been completely exploited in the field of robotics. In this work, we propose a localization approach utilizing textual features in urban environments. Starting at an unknown location, equipped with an RGB-camera and a compass, our approach uses off-the-shelf text extraction methods to identify text labels in the vicinity. We then apply a probabilistic localization approach with specific sensor models to integrate multiple observations. An extensive evaluation with real-world data gathered in different cities reveals an improvement over GPS-based localization when using our method.

The perception of the dynamic aspects of the environment is a highly relevant precondition for the realization of autonomous robot system acting in the real world. In this paper, we propose a novel method for estimating dense rigid scene flow in 3D LiDAR scans. We formulate the problem as an energy minimization problem, where we assume local geometric constancy and incorporate regularization for smooth motion fields. Analyzing the dynamics at point level helps in inferring the fine-grained details of motion. We show results on multiple sequences of the KITTI odometry dataset, where we seamlessly estimate multiple motions pertaining to different dynamic objects. Furthermore, we test our approach on a dataset with pedestrians to show how our method adapts to a case with non-rigid motion. For comparison we use the ground truth from KITTI and show how our method outperforms different ICP-based methods.

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.

Networks of laser range finders are a popular tool for monitoring large cluttered areas and to track people. Whenever multiple scanners are used for this purpose, one major problem is how to determine the relative positions of all the scanners. In this paper, we present a novel approach to calibrate a network of multiple planar laser range finders scanning horizontally. To robustly deal with the potentially restricted overlap between the fields of view, our approach only requires a dynamic object, e.g., a person, moving through the observed area. We employ a RANSAC-like algorithm to find the correspondences between the measurements of the different laser range finders. Based on these correspondences we formulate a graph-based optimization problem to determine the maximum likelihood extrinsic parameters of the sensor network. Furthermore, we present a method to evaluate the consistency of the resulting calibration based on visibility constraints. Experiments on real and simulated data show that the proposed approach yields better results than techniques that only perform pairwise calibration.

Robot localization is one of the most important problems in robotics. Most of the existing approaches assume that the map of the environment is available beforehand and focus on accurate metrical localization. In this paper, we address the localization problem when the map of the environment is not present beforehand, and the robot relies on a hand-drawn map from a non-expert user. We addressed this problem by expressing the robot pose in the pixel coordinate and simultaneously estimate a local deformation of the hand-drawn map. Experiments show that we can successfully identify the room in which the robot is located in 80% of the tests.

Many mobile manipulation tasks require the robot to be accurately localized with respect to the object where the manipulation has to be executed. These tasks include autonomous docking and positioning as well as pick and place or logistics tasks. State-of-the-art approaches to the problem commonly assume that the environment is static and localize the robot with respect to predetermined locations. In this paper, we present an approach that relaxes the static assumption and enables a robot to accurately localize with respect to a reference object that could be moved in the environment. The core of the paper is an extension of the generalized ICP method to handle multiple rigid bodies that move independently to each others. Experiments in both simulated and real world scenarios show that our approach is able to localize the robot with respect to a moved object with an accuracy of less than one centimeter.

Non-linear error minimization methods became widespread approaches for solving the simultaneous localization and mapping problem. If the initial guess is far away from the global minimum, converging to the correct solution and not to a local one can be challenging and sometimes even impossible. This paper presents an experimental analysis of dynamic covariance scaling, a recently proposed method for robust optimization of SLAM graphs, in the context of a poor initialization. Our evaluation shows that dynamic covariance scaling is able to mitigate the effects of poor initializations. In contrast to other methods that first aim at finding a good initial guess to seed the optimization, our method is more elegant because it does not require an additional method for initialization. Furthermore, it can robustly handle data association outliers. Experiments performed with real world and simulated datasets show that dynamic covariance scaling outperforms existing methods, both in the presence and absence of data association outliers.

Localization approaches typically rely on an already available map to identify the position of the sensor in the environment. Such maps are usually built beforehand and often require the user to record data from the same sensor used for localization. In this paper, we relax this assumption and present a localization approach based on architectural floor plans. In general, floor plans are readily available for most man-made buildings but only represent basic architectural structures. The incomplete knowledge leads to ambiguous pose estimates. To solve this problem, we present W-RGB-D, a new method for indoor global localization based on WiFi and an RGB-D camera. We introduce a sensor model for RGB-D cameras that is suitable to be used with abstract floor plans. To resolve ambiguities during global localization, we estimate a coarse initial distribution about the sensor position using the WiFi signal strength. We evaluate our W-RGB-D localization method in indoor environments and compare its performance with RGB-D-based Monte Carlo localization. Our results demonstrate that the use of WiFi information as proposed with our approach improves the localization in terms of convergence speed and quality of the solution.

Map consistency is an important requirement for applications in which mobile robots need to effectively perform autonomous navigation tasks. While recent SLAM techniques provide an increased robustness even in the context of bad initializations or data association outliers, the question of how to determine whether or not the resulting map is consistent is still an open problem. In this paper, we introduce a novel measure for map consistency. We compute this measure by taking into account the discrepancies in the sensor data and leverage it to address two important problems in SLAM. First, we derive a statistical test for assessing whether a map is consistent or not. Second, we employ it to automatically set the free parameter of dynamic covariance scaling, a robust SLAM back-end. We present an evaluation of our approach on over 50 maps sourced from 16 publicly available datasets and illustrate its capability for the inconsistency detection and the tuning of the parameter of the back-end.

In the past, highly effective solutions to the SLAM problem based on solving nonlinear optimization problems have been developed. However, most approaches put their major focus on runtime and accuracy rather than on memory consumption, which becomes especially relevant when large-scale SLAM problems have to be solved. In this paper, we consider the SLAM problem from the point of view of memory consumption and present a novel approximate approach to SLAM with low memory consumption. Our approach achieves this based on a hierarchical decomposition consisting of small submaps with limited size. We perform extensive experiments on synthetic and publicly available datasets. The results demonstrate that in situations in which the representation of the complete map requires more than the available main memory, our approach, in comparison to state-of-the-art exact solvers, reduces the memory consumption and the runtime up to a factor of 2 while still providing highly accurate maps.

Developing the perfect SLAM front-end that produces graphs which are free of outliers is generally impossible due to perceptual aliasing. Therefore, optimization back-ends need to be able to deal with outliers resulting from an imperfect front-end. In this paper, we introduce dynamic covariance scaling, a novel approach for effective optimization of constraint networks under the presence of outliers. The key idea is to use a robust function that generalizes classical gating and dynamically rejects outliers without compromising convergence speed. We implemented and thoroughly evaluated our method on publicly available datasets. Compared to recently published state-of-the-art methods, we obtain a substantial speed up without increasing the number of variables in the optimization process. Our method can be easily integrated in almost any SLAM back-end.

In this paper we address the problem of cooperative localization and target tracking with a team of moving robots. We model the problem as a least squares minimization problem and show that this problem can be efficiently solved using sparse optimization methods. To achieve this, we represent the problem as a graph, where the nodes are robot and target poses at individual time-steps and the edges are their relative measurements. Static landmarks at known position are used to define a common reference frame for the robots and the targets. In this way, we mitigate the risk of using measurements and state estimates more than once, since all the relative measurements are i.i.d. and no marginalization is performed. Experiments performed using a set of real robots show higher accuracy compared to a Kalman filter.

Place recognition, i.e., the problem of recognizing if the robot is navigating in an already visited place, is a fundamental problem in mobile robot navigation. Efficient solutions to this problem are relevant for effectively localizing robots and for creating maps in real time. Relatively few methods have been proposed to efficiently solve this problem in very large environments using 2D range data. In this paper, we introduce geometrical FLIRT phrases (GFPs) as a novel retrieval method for very efficient and precise place recognition. GFPs perform approximate 2D range data matching, have low computational cost, can handle complicated partial matching patterns and are robust to noise. Experiments carried out with publicly available datasets demonstrate that GFPs largely outperform state-of-the-art approaches in 2D range-based place recognition in terms of efficiency and recall. We obtain retrieval performances with more than 85% recall at 99% precision in less than a second, even on data sets obtained from several kilometer long runs.

In this paper we present the projection and bias heuristic (PBH), a motion planning algorithm that makes use of low-dimensional projections to improve sampling-based planning algorithms. In contrast to other state-of-the-art methods, we do not assume that projections are either random or given by an expert user. Rather, our goal is to learn projections such that planning on them improves the efficiency and the quality of solutions. We present both, a method to learn effective projections and a sampling algorithm that makes use of them. We show that our approach can be easily integrated into popular sampling-based planners. Extensive experiments performed in simulated environments demonstrate that our approach produces paths that are in general shorter than those obtained with state-of-the-art algorithms. Moreover, it generally requires less computation time.

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.

In this paper we consider the problem of null space minimization in coverage path planning of 3D surfaces for redundant manipulators. Existing coverage solutions only focus on Euclidean cost functions and often return suboptimal paths with respect to the joint space. In the approach described here, we explicitly consider the null space by treating different inverse kinematics solutions as individual nodes in a graph and model the problem as a generalized traveling salesman problem (GTSP). The GTSP is a generalization of the TSP where the nodes of the graph are subdivided into clusters and at least one node in each cluster needs to be visited. We evaluate our approach using a PR2 robot and complex objects. Our results demonstrate that our method outperforms Euclidean coverage algorithms in terms of manipulation effort and completion time.

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.

People tracking is a key component for robots operating in populated environments. Previous works have employed different filtering and data association techniques for this purpose that typically rely on a set of generic assumptions on target behavior and detector characteristics. In this paper, we focus on these assumptions rather than the tracking approach itself and show that with informed models, people tracking can be made substantially more accurate without compromising efficiency. Concretely, we present better, human-specific models for the occurrence of new tracks, false alarms, track occlusions, and track deletions. In the experiments with a large-scale outdoor data set collected with a laser range finder, the models and combinations thereof are experimentally compared using a multi-hypothesis baseline tracker and the CLEAR MOT metrics. The results show how some models selectively improve tracking performance at the expense of other measures. The final combination is then able to resolve the trade-offs, leading to a reduction of data association errors by more than a factor of two at the same cost.

In this paper we present a probabilistic model for spatio-temporal patterns of human activities that enable robots to blend themselves into the workflows and daily routines of people. The model, called spatial affordance map, is a non-homogeneous spatial Poisson process that relates space, time and occurrence probability of activity events. We describe how learning and inference is made and present a novel planning algorithm that produces paths which maximize the probability to encounter a person. We show that the problem is a special class of the orienteering problem that can be solved as a finite horizon Markov decision process. We develop a simulator of populated office environments to validate the model and the planning algorithm. The simulated agents follow activity patterns learned by administering a questionnaire to 27 colleagues over two weeks. The experiments shows that the model is statistically valid with respect to both the Anderson-Darling test and the expected waiting time estimation. They further show that the proposed algorithm is able to find optimal paths.

In this paper we address the problem of human-aware coverage planning. We first present an approach to learn and model human activity events in a probabilistic spatio-temporal map using spatial Poisson processes. We then propose a coverage planner for paths that minimize the interference probability with people. To this end, we pose the coverage problem as an asymmetric traveling salesman problem with time-dependent costs (ATDTSP) derived from the information in the map. The approach enables a noisy robotic vacuum in a home scenario, for instance, to learn to avoid busy places at certain times of the day such as the kitchen at lunch time. We evaluate the planner using a simulator of people in a home environment to generate typical weekday activity patterns. In the experiments with a regular TSP planner and two modified TSP heuristics, the proposed coverage planner significantly reduces interference with people in terms of number of disturbed persons and overall disturbance time.

For many tasks in populated environments, robots need to keep track of current and future motion states of people. Most approaches to people tracking make weak assumptions on human motion such as constant velocity or acceleration. But even over a short period, human behavior is more complex and influenced by factors such as the intended goal, other people, objects in the environment, and social rules. This motivates the use of more sophisticated motion models for people tracking especially since humans frequently undergo lengthy occlusion events. In this paper, we consider computational models developed in the cognitive and social science communities that describe individual and collective pedestrian dynamics for tasks such as crowd behavior analysis. In particular, we integrate a model based on a social force concept into a multi-hypothesis target tracker. We show how the refined motion predictions translate into more informed probability distributions over hypotheses and finally into a more robust tracking behavior and better occlusion handling. In experiments in indoor and outdoor environments with data from a laser range finder, the social force model leads to more accurate tracking with up to two times fewer data association errors.

Local image features are used for a wide range of applications in computer vision and range imaging. While there is a great variety of detector-descriptor combinations for image data and 3D point clouds, there is no general method readily available for 2D range data. For this reason, the paper first proposes a set of benchmark experiments on detector repeatability and descriptor matching performance using known indoor and outdoor data sets for robot navigation. Secondly, the paper introduces FLIRT that stands for Fast Laser Interest Region Transform, a multi-scale interest region operator for 2D range data. FLIRT combines the best detector with the best descriptor, experimentally found in a comprehensive analysis of alternative detector and descriptor approaches. The analysis yields repeatability and matching performance results similar to the values found for features in the computer vision literature, encouraging a wide range of applications of FLIRT on 2D range data. We finally show how FLIRT can be used in conjunction with RANSAC to address the loop closing/global localization problem in SLAM in indoor as well as outdoor environments. The results demonstrate that FLIRT features have a great potential for robot navigation in terms of precision-recall performance, efficiency and generality.

This paper presents a novel framework for integrating fundamental tasks in robotic navigation through a statistical inference procedure. A probabilistic model that jointly reasons about scan-matching, moving object detection and their motion estimation is developed. Scan-matching and moving object detection are two important problems for full autonomy of robotic systems in complex dynamic environments. Popular techniques for solving these problems usually address each task in turn disregarding important dependencies. The model developed here jointly reasons about these tasks by performing inference in a probabilistic graphical model. It allows different but related problems to be expressed in a single framework. The experiments demonstrate that jointly reasoning results in better estimates for both tasks compared to solving the tasks individually.

Moving objects are present in many robotic applications. An accurate detection and motion estimation of these objects can be crucial for the success and safety of the robot and people surrounding it. This paper presents a new probabilistic framework for clustering dependent or relational data, applied to the problem of motion clustering and estimation. While conventional techniques such as scan differencing perform well in many cases, they usually assume that a good pose estimate is available and fail when points belonging to dynamic objects show some overlap in consecutive readings. The technique proposed, CRF-Clustering, by explicitly reasoning about the underlying motion of the object, is able to deal with poor initial motion estimate and overlapping points. Moreover, it is able to consider the dependencies between neighbor points in the scans to reduce the noise in the clustering assignment. The model parameters can be estimated from labeled data in a statistically sound learning procedure. Experiments show that CRF-Clustering is able to detect moving objects, cluster them and estimate their motion.

We present a new algorithm for solving the global localization problem called Frozen-Time Smoother (FTS). Time is 'frozen', in the sense that the belief always refers to the same time instant, instead of following a moving target, like Monte Carlo Localization does. This algorithm works in the case in which global localization is formulated as a smoothing problem, and a precise estimate of the incremental motion of the robot is usually available. These assumptions correspond to the case when global localization is used to solve the loop closing problem in SLAM. We compare FTS to two Monte Carlo methods designed with the same assumptions. The experiments suggest that a naive implementation of the FTS is more efficient than an extremely optimized equivalent Monte Carlo solution. Moreover, the FTS has an intrinsic laziness: it does not need frequent updates (scans can be integrated once every many meters) and it can process data in arbitrary order. The source code and datasets are available for download.

In this paper we present a novel technique to estimate the state of heterogeneous features from inaccurate sensors. The proposed approach exploits the reliability of the feature extraction process in the sensor model and uses a Rao-Blackwellized particle filter to address the data association problem. Experimental results show that the use of reliability improves performance by allowing the approach to perform better data association among detected features. Moreover, the method has been tested on a real robot during an exploration task in a non-planar environment. This last experiment shows an improvement in correctly detecting and classifying interesting features for navigation purpose.

Smoothing and optimization approaches are an effective means for solving the simultaneous localization and mapping (SLAM) problem. Most of the existing techniques focus mainly on determining the most likely map and leave open how to efficiently compute the marginal covariances. These marginal covariances, however, are essential for solving the data association problem. In this paper we present a novel algorithm for computing an approximation of the marginal. In experiments we demonstrate that our approach outperforms two commonly used techniques, namely loopy belief propagation and belief propagation on a spanning tree. Compared to these approaches, our algorithm yields better estimates while preserving the same time complexity.

Recently, Rao-Blackwellized particle filters have become a popular tool to solve the simultaneous localization and mapping problem. This technique applies a particle filter in which each particle carries an individual map of the environment. Accordingly, a key issue is to reduce the number of particles and/or to make use of compact map representations. This paper presents an approximative but highly efficient approach to mapping with Rao-Blackwellized particle filters. Moreover, it provides a compact map model. A key advantage is that the individual particles can share large parts of the model of the environment. Furthermore, they are able to re-use an already computed proposal distribution. Both techniques substantially speed up the overall process and reduce the memory requirements. Experimental results obtained with mobile robots in large-scale indoor environments and based on published, standard datasets illustrate the advantages of our methods over previous Rao-Blackwellized mapping approaches