Search

Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements x 1 , ... , x n ∈ SE ( d ) given noisy measurements of a subset of their pairwise relative transforms x i − 1 x j . Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a non-convex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation (MLE) whose minimizer provides an exact maximum-likelihood estimate so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable of recovering certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so significantly faster than the Gauss–Newton-based approach that forms the basis of current state-of-the-art techniques. [ABSTRACT FROM AUTHOR]

For certain applications, such as on-orbit inspection of orbital debris, defunct satellites, and natural objects, it is necessary to obtain a map of a rotating object from a moving observer, as well to estimate the object’s center of mass. This paper addresses these tasks using an observer that measures its own orientation, angular rate, and acceleration, and is equipped with a dense 3D visual sensor, such as a stereo camera or a light detection and ranging (LiDAR) sensor. The observer’s trajectory is estimated independently of the target object’s rotational motion. Pose-graph mapping is performed using visual odometry to estimate the observer’s trajectory in an arbitrary target-fixed frame. In addition to applying pose constraint factors between successive frames, loop closure is performed between temporally non-adjacent frames. A kinematic constraint on the target-fixed frame, resulting from the rigidity of the target object, is exploited to create a novel rotation kinematic factor. This factor connects a trajectory estimation factor graph with the mapping pose graph, and facilitates estimation of the target’s center of mass. Map creation is performed by transforming detected feature points into the target-fixed frame, centered at the estimated center of mass. Analysis of the algorithm’s computational performance reveals that its computational cost is negligible compared with that of the requisite image processing. [ABSTRACT FROM AUTHOR]

There are many applications that require mobile robots to autonomously cover an entire area with a sensor or end effector. The vast majority of the literature on this subject is focused on addressing path planning for area coverage under the assumption that the robot’s pose is known or that error is bounded. In this work, we remove this assumption and develop a completely probabilistic representation of coverage. We show that coverage is guaranteed as long as the robot pose estimates are consistent, a much milder assumption than zero or bounded error. After formally connecting robot sensor uncertainty with area coverage, we propose an adaptive sliding window filter pose estimator that provides a close approximation to the full maximum a posteriori estimate with a computation cost that is bounded over time. Subsequently, an adaptive planning strategy is presented that automatically exploits conditions of low vehicle uncertainty to more efficiently cover an area. We further extend this approach to the multi-robot case where robots can communicate through a (possibly faulty and low-bandwidth) channel and make relative measurements of one another. In this case, area coverage is achieved more quickly since the uncertainty over the robots’ trajectories is reduced. We apply the framework to the scenario of mapping an area of seabed with an autonomous underwater vehicle. Experimental results support the claim that our method achieves guaranteed complete coverage notwithstanding poor navigational sensors and that resulting path lengths required to cover the entire area are shortest using the proposed cooperative and adaptive approach. [ABSTRACT FROM AUTHOR]

We present a new simultaneous localization and mapping (SLAM) system capable of producing high-quality globally consistent surface reconstructions over hundreds of meters in real time with only a low-cost commodity RGB-D sensor. By using a fused volumetric surface reconstruction we achieve a much higher quality map over what would be achieved using raw RGB-D point clouds. In this paper we highlight three key techniques associated with applying a volumetric fusion-based mapping system to the SLAM problem in real time. First, the use of a GPU-based 3D cyclical buffer trick to efficiently extend dense every-frame volumetric fusion of depth maps to function over an unbounded spatial region. Second, overcoming camera pose estimation limitations in a wide variety of environments by combining both dense geometric and photometric camera pose constraints. Third, efficiently updating the dense map according to place recognition and subsequent loop closure constraints by the use of an ‘as-rigid-as-possible’ space deformation. We present results on a wide variety of aspects of the system and show through evaluation on de facto standard RGB-D benchmarks that our system performs strongly in terms of trajectory estimation, map quality and computational performance in comparison to other state-of-the-art systems. [ABSTRACT FROM PUBLISHER]

We present a parallelized navigation architecture that is capable of running in real-time and incorporating long-term loop closure constraints while producing the optimal Bayesian solution. This architecture splits the inference problem into a low-latency update that incorporates new measurements using just the most recent states (filter), and a high-latency update that is capable of closing long loops and smooths using all past states (smoother). This architecture employs the probabilistic graphical models of factor graphs, which allows the low-latency inference and high-latency inference to be viewed as sub-operations of a single optimization performed within a single graphical model. A specific factorization of the full joint density is employed that allows the different inference operations to be performed asynchronously while still recovering the optimal solution produced by a full batch optimization. Due to the real-time, asynchronous nature of this algorithm, updates to the state estimates from the high-latency smoother will naturally be delayed until the smoother calculations have completed. This architecture has been tested within a simulated aerial environment and on real data collected from an autonomous ground vehicle. In all cases, the concurrent architecture is shown to recover the full batch solution, even while updated state estimates are produced in real-time. [ABSTRACT FROM AUTHOR]

This paper presents a large scale dataset of vision (stereo and RGB-D), laser and proprioceptive data collected over an extended duration by a Willow Garage PR2 robot in the 10 story MIT Stata Center. As of September 2012 the dataset comprises over 2.3 TB, 38 h and 42 km (the length of a marathon). The dataset is of particular interest to robotics and computer vision researchers interested in long-term autonomy. It is expected to be useful in a variety of research areas—robotic mapping (long-term, visual, RGB-D or laser), change detection in indoor environments, human pattern analysis, long-term path planning. For ease of use the original ROS ‘bag’ log files are provided and also a derivative version combining human readable data and imagery in standard formats. Of particular importance, this dataset also includes ground-truth position estimates of the robot at every instance (to typical accuracy of 2 cm) using as-built floor-plans—which were carefully extracted using our software tools. The provision of ground-truth for such a large dataset enables more meaningful comparison between algorithms than has previously been possible. [ABSTRACT FROM PUBLISHER]

Inspection of ship hulls and marine structures using autonomous underwater vehicles has emerged as a unique and challenging application of robotics. The problem poses rich questions in physical design and operation, perception and navigation, and planning, driven by difficulties arising from the acoustic environment, poor water quality and the highly complex structures to be inspected. In this paper, we develop and apply algorithms for the central navigation and planning problems on ship hulls. These divide into two classes, suitable for the open, forward parts of a typical monohull, and for the complex areas around the shafting, propellers and rudders. On the open hull, we have integrated acoustic and visual mapping processes to achieve closed-loop control relative to features such as weld-lines and biofouling. In the complex area, we implemented new large-scale planning routines so as to achieve full imaging coverage of all the structures, at a high resolution. We demonstrate our approaches in recent operations on naval ships. [ABSTRACT FROM PUBLISHER]

We present a novel data structure, the Bayes tree, that provides an algorithmic foundation enabling a better understanding of existing graphical model inference algorithms and their connection to sparse matrix factorization methods. Similar to a clique tree, a Bayes tree encodes a factored probability density, but unlike the clique tree it is directed and maps more naturally to the square root information matrix of the simultaneous localization and mapping (SLAM) problem. In this paper, we highlight three insights provided by our new data structure. First, the Bayes tree provides a better understanding of the matrix factorization in terms of probability densities. Second, we show how the fairly abstract updates to a matrix factorization translate to a simple editing of the Bayes tree and its conditional densities. Third, we apply the Bayes tree to obtain a completely novel algorithm for sparse nonlinear incremental optimization, named iSAM2, which achieves improvements in efficiency through incremental variable re-ordering and fluid relinearization, eliminating the need for periodic batch steps. We analyze various properties of iSAM2 in detail, and show on a range of real and simulated datasets that our algorithm compares favorably with other recent mapping algorithms in both quality and efficiency. [ABSTRACT FROM AUTHOR]

In this paper we describe the experimental implementation of an online algorithm for cooperative localization of submerged autonomous underwater vehicles (AUVs) supported by an autonomous surface craft. Maintaining accurate localization of an AUV is difficult because electronic signals, such as GPS, are highly attenuated by water. The usual solution to the problem is to utilize expensive navigation sensors to slow the rate of dead-reckoning divergence. We investigate an alternative approach that utilizes the position information of a surface vehicle to bound the error and uncertainty of the on-board position estimates of a low-cost AUV. This approach uses the Woods Hole Oceanographic Institution (WHOI) acoustic modem to exchange vehicle location estimates while simultaneously estimating inter-vehicle range. A study of the system observability is presented so as to motivate both the choice of filtering approach and surface vehicle path planning. The first contribution of this paper is to the presentation of an experiment in which an extended Kalman filter (EKF) implementation of the concept ran online on-board an OceanServer Iver2 AUV while supported by an autonomous surface vehicle moving adaptively. The second contribution of this paper is to provide a quantitative performance comparison of three estimators: particle filtering (PF), non-linear least-squares optimization (NLS), and the EKF for a mission using three autonomous surface craft (two operating in the AUV role). Our results indicate that the PF and NLS estimators outperform the EKF, with NLS providing the best performance. [ABSTRACT FROM AUTHOR]

This paper describes an algorithm for distributed acoustic navigation for Autonomous Underwater Vehicles (AUVs). Whereas typical AUV navigation systems utilize pre-calibrated arrays of static transponders, our work seeks to create a fully mobile network of AUVs that perform acoustic ranging and data exchange with one another to achieve cooperative positioning for extended duration missions over large areas. The algorithm enumerates possible solutions for the AUV trajectory based on dead-reckoning and range-only measurements provided by acoustic modems that are mounted on each vehicle, and chooses the trajectory via minimization of a cost function based on these constraints. The resulting algorithm is computationally efficient, meets the strict bandwidth requirements of available AUV modems, and has potential to scale well to networks of large numbers of vehicles. The method has undergone extensive experimentation, and results from three different scenarios are reported in this paper, each of which utilizes MIT SCOUT Autonomous Surface Craft (ASC) as convenient platforms for testing. In the first experiment, we utilize three ASCs, each equipped with a Woods Hole acoustic modem, as surrogates for AUVs. In this scenario, two ASCs serve as Communication/Navigation Aids (CNAs) for a third ASC that computes its position based exclusively on GPS positions of the CNAs and acoustic range measurements between platforms. In the second scenario, an undersea glider is used in conjunction with two ASCs serving as CNAs. Finally, in the third experiment, a Bluefin12 AUV serves as the target vehicle. All three experiments demonstrate the successful operation of the technique with real ocean data. [ABSTRACT FROM AUTHOR]

Recent research concerning the Gaussian canonical form for Simultaneous Localization and Mapping (SLAM) has given rise to a handful of algorithms that attempt to solve the SLAM scalability problem for arbitrarily large environments. One such estimator that has received due attention is the Sparse Extended information Filter (SEIF) proposed by Thrun et al., which is reported to he nearly constant time, irrespective of the size of the map. The key to the SEIF's scalabilily is to prune weak links in what is a dense information (inverse covariance) matrix to achieve a sparse approximation that allows for efficient, scalable SLAM. We demonstrate that the SEIF sparsification strategy yields error estimates that are overconfident when expressed in the global reference frame, while empirical results show that relative map consistency is maintained. In this paper, we propose an alternative scalable estimator based on an information form that maintains sparsity while preserving consistency. The paper describes a method for controlling the population of the information matrix, whereby we track a modified version of the SLAM posterior essentially by ignoring a small fraction of temporal measurements. In this manner, the Exactly Sparse Extended Information Filter (ESEIF) performs inference over a model that is conservative relative to the standard Gaussian distribution. We compare our algorithm to the SEIF and standard EKF both in simulation as well as on two nonlinear datasets. The results convincingly show that our method yields conservative estimates for the robot pose and map that are nearly identical to those of the EKF. [ABSTRACT FROM AUTHOR]

This paper describes a vision-based, large-area, simultaneous localization and mapping (SLAM) algorithm that respects the low-overlap imagery constraints typical of underwater vehicles while exploiting the inertial sensor information that is routinely available on such platforms. We present a novel strategy for efficiently accessing and maintaining consistent covariance bounds within a SLAM information filter, thereby greatly increasing the reliability of data association. The technique is based upon solving a sparse system of linear equations coupled with the application of constant-time Kalman updates. The method is shown to produce consistent covariance estimates suitable for robot planning and data association. Real-world results are reported for a vision-based, six degree of freedom SLAM implementation using data from a recent survey of the wreck of the RMS Titanic. [ABSTRACT FROM AUTHOR]

In this paper we present a technique for mapping partially observable features from multiple uncertain vantage points. The problem of concurrent mapping and localization (CML) is stated as follows. Starting from an initial known position, a mobile robot travels through a sequence of positions, obtaining a set of sensor measurements at each position. The goal is to process the sensor data to produce an estimate of the trajectory of the robot while concurrently building a map of the environment. In this paper, we describe a generalized framework for CML that incorporates temporal as well as spatial correlations. The representation is expanded to incorporate past vehicle positions in the state vector. Estimates of the correlations between current and previous vehicle states are explicitly maintained. This enables the consistent initialization of map features using data from multiple time steps. Updates to the map and the vehicle trajectory can also be performed in batches of data acquired from multiple vantage points. The method is illustrated with sonar data from a testing tank and via experiments with a B21 land mobile robot, demonstrating the ability to perform CML with sparse and ambiguous data. [ABSTRACT FROM AUTHOR]

In this paper we describe a new technique for the creation of featurebased stochastic maps using standard Polaroid sonar sensors. The fundamental contributions of our proposal are: (1) a perceptual grouping process that permits the robust identification and localization of environmental features, such as straight segments and corners, from the sparse and noisy sonar data; (2) a map joining technique that allows the system to build a sequence of independent limited-size stochastic maps and join them in a globally consistent way; (3) a robust mechanism to determine which features in a stochastic map correspond to the same environment feature, allowing the system to update the stochastic map accordingly, and perform tasks such as revisiting and loop closing. We demonstrate the practicality of this approach by building a geometric map of a medium size, real indoor environment, with several people moving around the robot. Maps built from laser data for the same experiment are provided for comparison. [ABSTRACT FROM AUTHOR]

Addresses the problem of how to perform concurrent mapping and localization adaptively using sonar. Importance to mobile robotics research; Implementation of stochastic mapping using a delayed nearest neighbor association strategy; Metric for adaptive sensing; Estimation of the metric for each potential action of a mobile robot.