Author name cluster

Edwin Olson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

50 papers

2 author rows

ICRA Conference 2021 Conference Paper

AXLE: Computationally-efficient trajectory smoothing using factor graph chains

Edwin Olson

Factor graph chains– the special case of a factor graph in which there are no potentials connecting non-adjacent nodes– arise naturally in many robotics problems. Importantly, they are often part of an inner loop in trajectory optimization and estimation problems, and so applications can be very sensitive to the performance of a solver. Of course, it is well-known that factor graph chains have an O(N) solution, but an actual solution is often left as "an exercise to the reader"… with the inevitable consequence that few (if any) efficient solutions are readily available. In this paper, we carefully derive the solution while keeping track of the specific block structure that arises, we work through a number of practical implementation challenges, and we highlight additional optimizations that are not at first apparent. An easy-to-use and self-contained solver is provided in C, which outperforms the AprilSAM general-purpose sparse matrix factorization library by a factor of 7. 3x even without specialized block operations. The name AXLE reflects the names of the key matrices involved (the approach here solves the linear problem AX = E by factoring A as LL T ), while also reflecting its key application in kino-dynamic trajectory estimation of vehicles with axles.

IROS Conference 2020 Conference Paper

The Masked Mapper: Masked Metric Mapping

Acshi Haggenmiller
Cameron Kabacinski
Maximilian Krogius
Edwin Olson

In this paper, we propose a flexible mapping scheme that uses a masking function (mask) to focus the attention of a pose graph SLAM (Simultaneous Localization and Mapping) system. The masking function takes the robot's observations and returns true if the robot is in an important location. State-of-the-art methods in SLAM generate dense metric lidar maps, creating precise maps at a high computational cost by storing lidar scans for each pose node and continually attempting to close loops. In many cases, trying to always make loop closures is unnecessary for localization and even risky because of perceptual aliasing and false positives. By masking out these less useful positions, our method can create more accurate maps despite performing far fewer scan matches. We evaluate our system with three simple mask functions on a 2. 5 km trajectory with significant angular drift. We compare the number of scan matches performed under each mask as well as the accuracy of the loop closures.

IROS Conference 2019 Conference Paper

Flexible Layouts for Fiducial Tags

Maximilian Krogius
Acshi Haggenmiller
Edwin Olson

Fiducials are artificial features with a variety of uses in computer vision such as object tracking and localization. We propose the idea of flexible tag layouts for visual fiducial systems. In contrast to traditional square tags, flexible tag layouts allow circular, annular, or other shapes as desired. One use of layout flexibility is to increase the data density of standard square shaped tags. In addition, we describe a detector that is faster and has higher recall than both the AprilTag 2 and ArUco detectors while maintaining precision.

IROS Conference 2019 Conference Paper

GLFP: Global Localization from a Floor Plan

Xipeng Wang
Ryan J. Marcotte
Edwin Olson

In this paper, we describe a method for global localization in a previously unvisited environment using only a schematic floor plan as a prior map. The floor plan need not be a precision map–it can be the sort of image found in buildings to guide people or aid evacuation. The core idea is to identify features that are stable across both a drawn floor plan and robot point-of-view LIDAR data, for example wall intersections, which appear as corners from overhead and as vertical lines from the ground. We introduce a factor graph-based global localization method that uses these features as landmarks. The detections of such descriptorless features are noisy and often ambiguous. We therefore propose robust data association based on a pairwise measurement consistency check and maxmixtures error model. We evaluate the resulting system in a real-world indoor environment, demonstrating performance comparable to a baseline system that uses a conventional LIDAR-based prior map.

ICRA Conference 2019 Conference Paper

Non-parametric Error Modeling for Ultra-wideband Localization Networks

Acshi Haggenmiller
Maximilian Krogius
Edwin Olson

We propose an ultra-wideband-based (UWB) localization system that achieves high accuracy through nonparametric estimation of measurement probability densities and explicit modeling of antenna delays. This problem is difficult because non-line-of-sight conditions give rise to multimodal errors, which make linear estimation methods ineffective. The primary contribution in this paper is an approach for both characterizing these errors in situ and an optimization framework that recovers both positions and antenna delays. We evaluate our system with a network of 8 nodes based on the DecaWave DWM1000 and achieve accuracies from 3 cm RMSE in line-of-sight conditions to 30 cm RMSE in non-line-of-sight conditions. Collecting measurements and localizing the network in this manner requires less than a minute, after which the realized network may be used for dynamic real-time tracking.

ICRA Conference 2018 Conference Paper

ApriISAM: Real-Time Smoothing and Mapping

Xipeng Wang
Ryan J. Marcotte
Gonzalo Ferrer 0001
Edwin Olson

For online robots, incremental SLAM algorithms offer huge potential computational savings over batch algorithms. The dominant incremental algorithms are iSAM and iSAM2 which offer radically different approaches to computing incremental updates, balancing issues like 1) the need to re-linearize, 2) changes in the desirable variable marginalization order, and 3) the underlying conceptual approach (i. e. the “matrix” story versus the “factor graph” story). In this paper, we propose a new incremental algorithm that computes solutions with lower absolute error and generally provides lower error solutions for a fixed computational budget than either iSAM or iSAM2. Key to AprilSAM's performance are a new dynamic variable reordering algorithm for fast incremental Cholesky factorizations, a method for reducing the work involved in backsubstitutions, and a new algorithm for deciding between incremental and batch updates.

ICRA Conference 2018 Conference Paper

Backprop-MPDM: Faster Risk-Aware Policy Evaluation Through Efficient Gradient Optimization

Dhanvin Mehta
Gonzalo Ferrer 0001
Edwin Olson

In Multi-Policy Decision-Making (MPDM), many computationally-expensive forward simulations are performed in order to predict the performance of a set of candidate policies. In risk-aware formulations of MPDM, only the worst outcomes affect the decision making process, and efficiently finding these influential outcomes becomes the core challenge. Recently, stochastic gradient optimization algorithms, using a heuristic function, were shown to be significantly superior to random sampling. In this paper, we show that accurate gradients can be computed - even through a complex forward simulation - using approaches similar to those in deep networks. We show that our proposed approach finds influential outcomes more reliably, and is faster than earlier methods, allowing us to evaluate more policies while simultaneously eliminating the need to design an easily-differentiable heuristic function. We demonstrate significant performance improvements in simulation as well as on a real robot platform navigating a highly dynamic environment.

IROS Conference 2018 Conference Paper

C-MPDM: Continuously-Parameterized Risk-Aware MPDM by Quickly Discovering Contextual Policies

Dhanvin Mehta
Gonzalo Ferrer 0001
Edwin Olson

Risk-aware Multi-Policy Decision Making (MPDM)is a powerful framework for reliable navigation in a dynamic social environment where rather than evaluating individual trajectories, a “library” of policies (reactive controllers)is evaluated by anticipating potentially dangerous future outcomes using an on-line forward roll-out process. There is a core tension in Multi-Policy Decision Making (MPDM)systems - it is desirable to add more policies to the system for flexibility in finding good policies, however, this increases computational cost. As a result, MPDM was limited to small (perhaps 5-10)discrete policies - a significant performance bottleneck. In this paper, we radically enhance the expressivity of MPDM by allowing policies to have continuous-valued parameters, while simultaneously satisfying real-time constraints by quickly discovering promising policy parameters through a novel iterative gradient-based algorithm. Our evaluation includes results from extensive simulation and real-world experiments in semi-crowded environments.

AAMAS Conference 2018 Conference Paper

Calibrating Mixed Reality for Scalable Multi-Robot Experiments

Victoria Edwards
Peter Gaskell
Edwin Olson

When testing multi-robot teams, researchers are often forced to make a choice: test on real robots (where fidelity is high, but the number of actual robots is low) or test in simulation (where fidelity is low, but the number of robots can be large). This problem is acute for robots with sophisticated sensing and planning systems, where the cost of the robots rises in concert with their need for more realistic environments. We propose a mixed-reality testing framework in which real robots interact with virtual counterparts, allowing a large number of robots to interact in the environment with high fidelity. However, this creates a new problem: the simulated robots must behave like their real teammates. We consider the problem of calibrating the parameters of virtual robots so that the results of a mixed-reality experiment are representative of the performance of a real robotic team. In particular, we use virtual robots to elicit behaviors from physical robots in order to empirically measure their kino-dynamic characteristics.

ICRA Conference 2017 Conference Paper

Fast discovery of influential outcomes for risk-aware MPDM

Dhanvin Mehta
Gonzalo Ferrer 0001
Edwin Olson

In the Multi-Policy Decision Making (MPDM) framework, a robot's policy is elected by sampling from the distribution of current states, predicting future outcomes through forward simulation, and selecting the policy with the best expected performance. Electing the best plan depends on sampling initial conditions with influential (very high costs) outcomes. Discovering these configurations through random sampling may require drawing many samples, which becomes a performance bottleneck. In this paper, we describe a risk-aware approach which augments this sampling with an optimization process that helps discover those influential outcomes. We describe how we overcome several practical difficulties with this approach, and demonstrate significant performance improvements on a real robot platform navigating a semi-crowded, highly dynamic environment.

ICRA Conference 2017 Conference Paper

FLAG: Feature-based Localization between Air and Ground

Xipeng Wang
Steve Vozar
Edwin Olson

In GPS-denied environments, robot systems typically revert to navigating with dead-reckoning and relative mapping, accumulating error in their global pose estimate. In this paper, we propose Feature-based Localization between Air and Ground (FLAG), a method for computing global position updates by matching features observed from ground to features in an aerial image. Our method uses stable, descriptorless features associated with vertical structure in the environment around a ground robot in previously unmapped areas, referencing only overhead imagery, without GPS. Multiple-hypothesis data association with a particle filter enables efficient recovery from data association error and odometry uncertainty. We implement a stereo system to demonstrate our vertical feature based global positioning approach in both indoor and outdoor scenarios, and show comparable performance to laser-scan-matching results in both environments.

ICRA Conference 2016 Conference Paper

Adaptive forward error correction with adjustable-latency QoS for robotic networks

Ryan J. Marcotte
Edwin Olson

Mobile robotic teams require robust communication in order to coordinate effectively, which is a challenge given the dynamic, unpredictable nature of mobile ad hoc networks (MANET). These networks are subject to rapidly varying link qualities as robots move through their environment. Improving the robustness of these point-to-point links leads to greater overall network performance, which in turn allows the robots to perform their mission more effectively. In this work, we present a forward error correction (FEC) technique that exploits latency tolerance in network traffic to provide consistent packet delivery performance even on low-quality links. Our proposed system estimates link quality based on recent packet reception history and uses that estimate to determine FEC encoding strength. Furthermore, this system provides a novel Quality of Service (QoS) mechanism that trades latency tolerance for more reliable, lower overhead transmission. We evaluate the effectiveness of this technique in a real-world robotic testbed.

IROS Conference 2016 Conference Paper

AprilTag 2: Efficient and robust fiducial detection

John Wang
Edwin Olson

AprilTags and other passive fiducial markers require specialized algorithms to detect markers among other features in a natural scene. The vision processing steps generally dominate the computation time of a tag detection pipeline, so even small improvements in marker detection can translate to a faster tag detection system. We incorporated lessons learned from implementing and supporting the AprilTag system into this improved system. This work describes AprilTag 2, a completely redesigned tag detector that improves robustness and efficiency compared to the original AprilTag system. The tag coding scheme is unchanged, retaining the same robustness to false positives inherent to the coding system. The new detector improves performance with higher detection rates, fewer false positives, and lower computational time. Improved performance on small images allows the use of decimated input images, resulting in dramatic gains in detection speed.

IROS Conference 2016 Conference Paper

Autonomous navigation in dynamic social environments using Multi-Policy Decision Making

Dhanvin Mehta
Gonzalo Ferrer 0001
Edwin Olson

In dynamic environments crowded with people, robot motion planning becomes difficult due to the complex and tightly-coupled interactions between agents. Trajectory planning methods, supported by models of typical human behavior and personal space, often produce reasonable behavior. However, they do not account for the future closed-loop interactions of other agents with the trajectory being constructed. As a consequence, the trajectories are unable to anticipate cooperative interactions (such as a human yielding), or adverse interactions (such as the robot blocking the way). In this paper, we propose a new method for navigation amongst pedestrians in which the trajectory of the robot is not explicitly planned, but instead, a planning process selects one of a set of closed-loop behaviors whose utility can be predicted through forward simulation. In particular, we extend Multi-Policy Decision Making (MPDM) [1] to this domain using the closed-loop behaviors Go-Solo, Follow-other, and Stop. By dynamically switching between these policies, we show that we can improve the performance of the robot as measured by utility functions that reward task completion and penalize inconvenience to other agents. Our evaluation includes extensive results in simulation and real-world experiments.

IROS Conference 2016 Conference Paper

Fast and robust 3D feature extraction from sparse point clouds

Jacopo Serafin
Edwin Olson
Giorgio Grisetti

Matching 3D point clouds, a critical operation in map building and localization, is difficult with Velodyne-type sensors due to the sparse and non-uniform point clouds that they produce. Standard methods from dense 3D point clouds are generally not effective. In this paper, we describe a feature-based approach using Principal Components Analysis (PCA) of neighborhoods of points, which results in mathematically principled line and plane features. The key contribution in this work is to show how this type of feature extraction can be done efficiently and robustly even on non-uniformly sampled point clouds. The resulting detector runs in real-time and can be easily tuned to have a low false positive rate, simplifying data association. We evaluate the performance of our algorithm on an autonomous car at the MCity Test Facility using a Velodyne HDL-32E, and we compare our results against the state-of-the-art NARF keypoint detector.

IROS Conference 2016 Conference Paper

FLAT2D: Fast localization from approximate transformation into 2D

Robert Goeddel
Carl Kershaw
Jacopo Serafin
Edwin Olson

Many autonomous vehicles require precise localization into a prior map in order to support planning and to leverage semantic information within those maps (e. g. that the right lane is a turn-only lane.) A popular approach in automotive systems is to use infrared intensity maps of the ground surface to localize, making them susceptible to failures when the surface is obscured by snow or when the road is repainted. An emerging alternative is to localize based on the 3D structure around the vehicle; these methods are robust to these types of changes, but the maps are costly both in terms of storage and the computational cost of matching. In this paper, we propose a fast method for localizing based on 3D structure around the vehicle using a 2D representation. This representation retains many of the advantages of “full” matching in 3D, but comes with dramatically lower space and computational requirements. We also introduce a variation of Graph-SLAM tailored to support localization, allowing us to make use of graph-based error-recovery techniques in our localization estimate. Finally, we present real-world localization results for both an indoor mobile robotic platform and an autonomous golf cart, demonstrating that autonomous vehicles do not need full 3D matching to accurately localize in the environment.

IROS Conference 2016 Conference Paper

Learning semantic place labels from occupancy grids using CNNs

Robert Goeddel
Edwin Olson

The goal of this paper is to develop a robot with a grounded spatial vocabulary. Such a vocabulary would allow it to give and follow directions, and would give it valuable additional information in aiding localization and navigation. We approach the problem by defining an ontology of space (including corridor, doorway, and room) and by creating a Convolutional Neural Network (CNN) that allows the robot to classify LIDAR sensor data accordingly. In particular, we propose a CNN architecture that performs comparably or better than existing methods based on engineered features. Training CNNs can be fickle; we describe several specific aspects of our approach that are important for good performance in this task.

IROS Conference 2015 Conference Paper

Augmented vehicle tracking under occlusions for decision-making in autonomous driving

Enric Galceran
Edwin Olson
Ryan M. Eustice

This paper reports on an algorithm to support autonomous vehicles in reasoning about occluded regions of their environment to make safe, reliable decisions. In autonomous driving scenarios, other traffic participants are often occluded from sensor measurements by buildings or large vehicles like buses or trucks, which makes tracking dynamic objects challenging. We present a method to augment standard dynamic object trackers with means to 1) estimate the occluded state of other traffic agents and 2) robustly associate the occluded estimates with new observations after the tracked object reenters the visible region of the sensor horizon. We perform occluded state estimation using a dynamics model that accounts for the driving behavior of traffic agents and a hybrid Gaussian mixture model (hGMM) to capture multiple hypotheses over discrete behavior, such as driving along different lanes or turning left or right at an intersection. Upon new observations, we associate them to existing estimates in terms of the Kullback-Leibler divergence (KLD). We evaluate the proposed method in simulation and using a real-world traffic-tracking dataset from an autonomous vehicle platform. Results show that our method can handle significantly prolonged occlusions when compared to a standard dynamic object tracking system.

ICRA Conference 2015 Conference Paper

M3RSM: Many-to-many multi-resolution scan matching

Edwin Olson

We describe a new multi-resolution scan matching method that makes exhaustive (and thus local-minimum-proof) matching practical, even for large positional uncertainties. Unlike earlier multi-resolution methods, in which putative matches at low-resolutions can lead the matcher to an incorrect solution, our method generates exactly the same answer as a brute-force full-resolution method. We provide a proof of this. Novelly, our method allows decimation of both the look-up table and in the point cloud, yielding a 10x speedup versus contemporary correlative methods. When a robot closes a large-scale loop, it must often consider many loop-closure candidates. In this paper, we describe an approach for posing a scan matching query over these candidates jointly, finding the best match(es) between a particular pose and a set of candidate poses (“one-to-many”), or the best match between two sets of poses (“many-to-many”). This mode of operation finds the first loop closure as much as 45x faster than traditional “one-to-one” scan matching.

IROS Conference 2015 Conference Paper

Maximum likelihood tracking of a personal dead-reckoning system

Surat Kwanmuang
Edwin Olson

We consider the problem of a human-following robot in which a human is equipped with a low-fidelity odometry sensor and a robot follows the human leader - often lagging well behind and out of visual contact with the human. The challenge is for the robot to determine the path taken by the human, despite the relatively noisy odometry data available. Such a system is useful in a “pack mule” application, where the robot carries a heavy load for the human. Our key idea is to equip the robot with sensors allowing it to build a map, and to use observations of the environment structure to constrain the path of the human. We propose and evaluate several approaches: a particle filter method that extends monte-carlo localization approaches, and a multi-hypothesis maximum-likelihood approach based on stochastic gradient descent optimization that efficiently clusters similar trajectories. We demonstrate that our proposed approaches are able to track human trajectories in several synthetic and real-world datasets.

ICRA Conference 2015 Conference Paper

MPDM: Multipolicy decision-making in dynamic, uncertain environments for autonomous driving

Alexander G. Cunningham
Enric Galceran
Ryan M. Eustice
Edwin Olson

Real-world autonomous driving in city traffic must cope with dynamic environments including other agents with uncertain intentions. This poses a challenging decision-making problem, e. g. , deciding when to perform a passing maneuver or how to safely merge into traffic. Previous work in the literature has typically approached the problem using ad-hoc solutions that do not consider the possible future states of other agents, and thus have difficulty scaling to complex traffic scenarios where the actions of participating agents are tightly conditioned on one another. In this paper we present multipolicy decision-making (MPDM), a decision-making algorithm that exploits knowledge from the autonomous driving domain to make decisions online for an autonomous vehicle navigating in traffic. By assuming the controlled vehicle and other traffic participants execute a policy from a set of plausible closed-loop policies at every timestep, the algorithm selects the best available policy for the controlled vehicle to execute. We perform policy election using forward simulation of both the controlled vehicle and other agents, efficiently sampling from the high-likelihood outcomes of their interactions. We then score the resulting outcomes using a user-defined cost function to accommodate different driving preferences, and select the policy with the highest score. We demonstrate the algorithm on a real-world autonomous vehicle performing passing maneuvers and in a simulated merging scenario.

IROS Conference 2015 Conference Paper

TailoredBRIEF: Online per-feature descriptor customization

Andrew Richardson 0002
Edwin Olson

Image feature descriptors composed of a series of binary intensity comparisons yield substantial memory and runtime improvements over conventional descriptors, but are sensitive to viewpoint changes in ways that vary per feature. We propose a method to improve the matching performance of such descriptors by specifically reasoning about the reliability of test results on a feature-by-feature basis. We demonstrate an intuitive method to learn improved descriptor structures for individual features. Further, these learned results can be efficiently applied during matching with little increase in runtime. We provide an evaluation using a standard, ground-truthed, multi-image dataset.

IROS Conference 2014 Conference Paper

Locally-weighted homographies for calibration of imaging systems

Pradeep Ranganathan
Edwin Olson

A homography is traditionally formulated as a linear transformation and is used in multiple-view geometry as a linear map between projective planes (or images). Analogous to the use of homography-based techniques to calibrate a pin-hole camera, non-linear homographies extend the pinhole camera model to deal with non-linearities such as lens distortion. In this work, we propose a novel non-parametric nonlinear homography technique. Unlike a parametric non-linear mapping that can have inherent biases, this technique automatically adjusts model complexity to account for non-linearities in observed data. With this technique, we demonstrate nonparametric estimation of lens distortion from a single calibration image. We evaluate this technique on real-world lenses and show that this technique can improve the stability of cameracalibration. Furthermore, the non-parametric nature of our technique allows rectification of arbitrary sources of lens distortion.

IROS Conference 2014 Conference Paper

PAS: Visual odometry with Perspective Alignment Search

Andrew Richardson 0002
Edwin Olson

Visual odometry is typically formulated as a descriptor-based image feature tracking problem, followed by outlier rejection and simultaneous estimation of the scene structure and camera motion. We propose a fundamentally different formulation for the stereo case: a multi-scale search over pose to estimate the transformation that best aligns two sparse point clouds in image space. This has three main consequences. First, data association is descriptorless and implicit, supporting the use of features with indistinct appearance, such as edge features. Second, outlier rejection is subsumed by the use of a robust kernel and a joint feature alignment objective. Third, the method is robust to local minima, in contrast to coarse-to-fine or iterative approaches. This paper details the proposed method, which we call Perspective Alignment Search (PAS), integrated into an edge feature visual odometry system, and an evaluation against a LIDAR-based SLAM solution.

ICRA Conference 2014 Conference Paper

Robust pose graph optimization using stochastic gradient descent

John Wang
Edwin Olson

Robust SLAM methods can allow robots to recover correct maps even in the presence of incorrect loop closures. While these approaches improve robustness to outliers, they are susceptible to getting caught in local minima, a problem which is exacerbated by poor initial estimates. In this paper, we describe a stochastic gradient descent optimization approach that exhibits greater robustness to poor initial estimates. Our approach can either be used as a stand-alone optimization system or in conjunction with existing methods such as Gauss-Newton solvers. Using a combination of synthetic and real-world datasets, we demonstrate that our proposed approach is able to recover correct pose graphs significantly more frequently than other methods when large initialization errors are present.

IROS Conference 2013 Conference Paper

AprilCal: Assisted and repeatable camera calibration

Andrew Richardson 0002
Johannes H. Strom
Edwin Olson

Reliable and accurate camera calibration usually requires an expert intuition to reliably constrain all of the parameters in the camera model. Existing toolboxes ask users to capture images of a calibration target in positions of their choosing, after which the maximum-likelihood calibration is computed using all images in a batch optimization. We introduce a new interactive methodology that uses the current calibration state to suggest the position of the target in the next image and to verify that the final model parameters meet the accuracy requirements specified by the user. Suggesting target positions relies on the ability to score candidate suggestions and their effect on the calibration. We describe two methods for scoring target positions: one that computes the stability of the focal length estimates for initializing the calibration, and another that subsequently quantifies the model uncertainty in pixel space. We demonstrate that our resulting system, AprilCal, consistently yields more accurate camera calibrations than standard tools using results from a set of human trials. We also demonstrate that our approach is applicable for a variety of lenses.

IROS Conference 2013 Conference Paper

Inferring categories to accelerate the learning of new classes

Robert Goeddel
Edwin Olson

On-the-fly learning systems are necessary for the deployment of general purpose robots. New training examples for such systems are often supplied by mentor interactions. Due to the cost of acquiring such examples, it is desirable to reduce the number of necessary interactions. Transfer learning has been shown to improve classification results for classes with small numbers of training examples by pooling knowledge from related classes. Standard practice in these works is to assume that the relationship between the transfer target and related classes is already known. In this work, we explore how previously learned categories, or related groupings of classes, can be used to transfer knowledge to novel classes without explicitly known relationships to them. We demonstrate an algorithm for determining the category membership of a novel class, focusing on the difficult case when few training examples are available. We show that classifiers trained via this method outperform classifiers optimized to learn the novel class individually when evaluated on both synthetic and real-world datasets.

ICRA Conference 2013 Conference Paper

Learning convolutional filters for interest point detection

Andrew Richardson 0002
Edwin Olson

We present a method for learning efficient feature detectors based on in-situ evaluation as an alternative to hand-engineered feature detection methods. We demonstrate our in-situ learning approach by developing a feature detector optimized for stereo visual odometry. Our feature detector parameterization is that of a convolutional filter. We show that feature detectors competitive with the best hand-designed alternatives can be learned by random sampling in the space of convolutional filters and we provide a way to bias the search toward regions of the search space that produce effective results. Further, we describe our approach for obtaining the ground-truth data needed by our learning system in real, everyday environments.

IROS Conference 2013 Conference Paper

Predicting object functionality using physical simulations

Lauren Hinkle
Edwin Olson

It is challenging for a robot acting in the world to interact with and use novel objects. While a person may be able to look past visual differences and recognize the intended function of an object, doing so is more difficult for robots, which tend to rely on visual similarity to recognize categories of objects. A robot that recognizes and classifies objects based on their functional properties and potential capabilities is better prepared to use unknown objects. We propose a technique for functionally classifying objects using features obtained through physical simulations. The described method simulates spheres falling onto an object from above. We show how a feature vector can be derived from the results of the physics-based simulation, and that this feature vector is informative for a variety of affordance classification tasks. This process allows a robot equipped with a 3D sensor to determine the functionality of objects in its environment given only a few training examples from various function classes. We show that this method is able to accurately learn membership of 3D models in three function classes: “drinking vessel”, “table”, and “sittable”. We then show that this can be extended to 3D scans of objects using the models as training examples.

IROS Conference 2013 Conference Paper

Robust sensor characterization via max-mixture models: GPS sensors

Ryan D. Morton
Edwin Olson

Large position errors plague GNSS-based sensors (e. g. , GPS) due to poor satellite configuration and multipath effects, resulting in frequent outliers. Due to quadratic cost functions when optimizing SLAM via nonlinear least square methods, a single such outlier can cause severe map distortions. Following in the footsteps of recent improvements in the robustness of SLAM optimization process, this work presents a framework for improving sensor noise characterizations by combining a machine learning approach with max-mixture error models. By using max-mixtures, the sensor's noise distribution can be modeled to a desired accuracy, with robustness to outliers. We apply the framework to the task of accurately modeling the uncertainties of consumer-grade GPS sensors. Our method estimates the observation covariances using only weighted feature vectors and a single max operator, learning parameters off-line for efficient on-line calculation.

IROS Conference 2012 Conference Paper

DART: A particle-based method for generating easy-to-follow directions

Robert Goeddel
Edwin Olson

Despite evidence that human wayfinders consider directions involving landmarks or topological descriptions easier to follow, the majority of commerical direction-planning services and GPS navigation units plan routes based on metrically or temporally shortest paths, ignoring this potentially valuable information. We propose a method for generating directions that maximizes the probability of a human arriving at the correct destination, taking into account a model of their ability to follow topological, metrical, and landmark-based directions. We discuss optimization techniques for employing these models and present a method, DART, for extracting model-improved sets of directions in a tractable amount of time. DART employs particle simulation techniques to maximize the probability that the modeled wayfinder will successfully reach their destination. Our synthetic evaluation shows that DART produces improvements in arrival rates over existing methods and illustrates how DART's directions reflect properties of the wayfinder model.

IROS Conference 2012 Conference Paper

Gaussian Process for lens distortion modeling

Pradeep Ranganathan
Edwin Olson

When calibrating a camera, the radial component of lens distortion is the dominant source of image distortion. To model this lens distortion, camera models incorporate a radial distortion model that conforms to a certain parametric form. In practice however, multiple parametric forms can be used to model distortion for a given lens. Ideally, one would choose the best suited parametric form using a model selection procedure. In this work, we propose the use of Gaussian Process regression to model lens distortion. With the use of a squared exponential covariance function, a Gaussian Process (GP) can describe the space of smooth distortion functions; kernel hyperparameter selection in this space then analogous to performing explicit model selection between possible parametric models. Our evaluation shows that this Gaussian Process formulation of lens distortion performs on par with parametric distortion models.

IROS Conference 2012 Conference Paper

IPJC: The Incremental Posterior Joint Compatibility test for fast feature cloud matching

Yangming Li
Edwin Olson

One of the fundamental challenges in robotics is data-association: determining which sensor observations correspond to the same physical object. A common approach is to consider groups of observations simultaneously: a constellation of observations can be significantly less ambiguous than the observations considered individually. The Joint Compatibility Branch and Bound (JCBB) test is the gold standard method for these data association problems. But its computational complexity and its sensitivity to non-linearities limit its practical usefulness. We propose the Incremental Posterior Joint Compatibility (IPJC) test. While equivalent to JCBB on linear problems, it is significantly more accurate on non-linear problems. When used for feature-cloud matching (an important special case), IPJC is also dramatically faster than JCBB. We demonstrate the advantages of IPJC over JCBB and other commonly-used methods on both synthetic and real-world datasets.

IROS Conference 2012 Conference Paper

Multi-sensor ATTenuation Estimation (MATTE): Signal-strength prediction for teams of robots

Johannes H. Strom
Edwin Olson

Multi-robot teams are often constrained by communications; better signal-strength models enable more efficient coordination while still maintaining adequate communication. This work discusses several prediction algorithms applicable to this scenario. Whereas previous approaches typically focus on prediction in the presence of deployed base-stations, we consider the more general problem where all nodes in the network can be mobile. Our new algorithm, Multi-sensor ATTenuation Estimation (MATTE), addresses this problem by leveraging other forms of sensor data in combination with signal-strength measurements to infer the locations of attenuating materials in the robots' environment. We also extend prior tomographic and correlation-based approaches to the multi-robot case, allowing a competitive evaluation. All methods are evaluated on a large corpus of real-world indoor and outdoor environments.

IROS Conference 2012 Conference Paper

Variable reordering strategies for SLAM

Pratik Agarwal
Edwin Olson

State of the art methods for state estimation and perception make use of least-squares optimization methods to perform efficient inference on noisy sensor data. Much of this efficiency is achieved by using sparse matrix factorization methods. The sparsity structure of the underlying matrix factorization which makes these optimization methods tractable is highly dependent on the choice of variable reordering; but there has been no systematic evaluation of reordering methods in the SLAM community. In this paper we evaluate the performance of various reordering techniques on benchmark SLAM data sets and provide definitive recommendations based on our results. We also compare these state of the art algorithms against our simple and easy to implement algorithm which achieves comparable performance. Finally, we provide empirical evidence that few gains remain with respect to variants of minimum degree ordering.

ICRA Conference 2011 Conference Paper

AprilTag: A robust and flexible visual fiducial system

Edwin Olson

While the use of naturally-occurring features is a central focus of machine perception, artificial features (fiducials) play an important role in creating controllable experiments, ground truthing, and in simplifying the development of systems where perception is not the central objective. We describe a new visual fiducial system that uses a 2D bar code style "tag", allowing full 6 DOF localization of features from a single image. Our system improves upon previous systems, incorporating a fast and robust line detection system, a stronger digital coding system, and greater robustness to occlusion, warping, and lens distortion. While similar in concept to the ARTag system, our method is fully open and the algorithms are documented in detail.

IROS Conference 2011 Conference Paper

Iterative path optimization for practical robot planning

Andrew Richardson 0002
Edwin Olson

We present a hybrid path planner that combines two common methods for robotic planning: a Dijkstra graph search for the minimum distance path through the configuration space and an optimization scheme to iteratively improve grid-based paths. Our formulation is novel because we first commit to the minimum distance path, then explicitly relax the path to maximize the clearance up to a user-specified bound. Notably, this formulation yields more predictable paths than potential field methods which try to trade increases in path length for greater clearance around obstacles. These potential field costs infer a trade off that can yield poor paths when the obstacle map is partially observable and has a finite history. Some approximations are used to ensure efficient planning, but only a small set of additional behaviors were required to ensure safe operation. Our method has been field tested extensively, as it is the main on-robot path planner for our large team of 14 medium-scale autonomous ground robots and entry to the 2010 Multi Autonomous Ground-robotic International Challenge, MAGIC 2010.

IROS Conference 2011 Conference Paper

Occupancy grid rasterization in large environments for teams of robots

Johannes H. Strom
Edwin Olson

We introduce a method for efficiently rasterizing large occupancy grids. Efficient Maximum Likelihood Estimation (MLE) of robot trajectories has been shown to be highly scalable using sparse SLAM algorithms such as SqrtSAM, but unfortunately such approaches don't directly provide a rasterized grid map. We harness these existing SLAM methods to compute maximum likelihood (ML) robot trajectories and introduce a new efficient algorithm to rasterize a dynamic occupancy grid. We propose a spatially-aware data structure that enables the cost of a map update to be proportional to the impact of any loop closures, resulting in better average case performance than naive methods. Furthermore, we show how redundant sensor data can be exploited to improve map quality and speed up rasterization. We evaluate our method using several data sets collected using a team of 14 autonomous robots and show success in mixed indoor-outdoor urban environments as large as 220m × 170m, with 0. 1m resolution.

ICRA Conference 2011 Conference Paper

On computing the average orientation of vectors and lines

Edwin Olson

Computing the "average" orientation of lines and rotations is non-trivial due to the need to account for the periodicity of rotation. For example, the average of +10 and +350 degrees is 0 (or 360) degrees, not 180. This problem arises in many disciplines, particularly those in which empirically collected data is processed or filtered. In this paper, we review a common but sub-optimal method for computing average orientation and provide a new geometric interpretation. We also propose a new method which provides additional insights into the geometry of the problem. Our new method also produces significantly more accurate results in the regime of operation usually encountered in robotics applications. We characterize this regime and provide guidance regarding which method to use, and when.

IROS Conference 2011 Conference Paper

Positive and negative obstacle detection using the HLD classifier

Ryan D. Morton
Edwin Olson

Autonomous robots must be able to detect hazardous terrain even when sensor data is noisy and incomplete. In particular, negative obstacles such as cliffs or stairs often cannot be sensed directly; rather, their presence must be inferred. In this paper, we describe the height-length-density (HLD) terrain classifier that generalizes some prior methods and provides a unified mechanism for detecting both positive and negative obstacles. The classifier utilizes three novel features that inherently deal with partial observability. The structure of the classifier allows the system designer to encode the capabilities of the vehicle as well as a notion of risk, making our approach applicable to virtually any vehicle. We evaluate our method in an indoor/outdoor environment, which includes several perceptually difficult real-world cases, and show that our approach out-performs current methods.

ICRA Conference 2011 Conference Paper

Structure tensors for general purpose LIDAR feature extraction

Yangming Li
Edwin Olson

The detection of features from Light Detection and Ranging (LIDAR) data is a fundamental component of feature-based mapping and SLAM systems. Classical approaches are often tied to specific environments, computationally expensive, or do not extract precise features. We describe a general purpose feature detector that is not only efficient, but also applicable to virtually any environment. Our method shares its mathematical foundation with feature detectors from the computer vision community, where structure tensor based methods have been successful. Our resulting method is capable of identifying stable and repeatable features at a variety of spatial scales, and produces uncertainty estimates for use in a state estimation algorithm. We verify the proposed method on standard datasets, including the Victoria Park dataset and the Intel Research Center dataset.

IROS Conference 2010 Conference Paper

A passive solution to the sensor synchronization problem

Edwin Olson

Knowing the time at which sensors acquired data is critical to the proper processing and interpretation of that data, particularly for mobile robots attempting to project sensor data into a consistent coordinate frame. Unfortunately, many popular commercial sensors provide no support for synchronization, rendering conventional synchronization algorithms useless. In this paper, we describe a passive synchronization algorithm that can significantly reduce timing error versus naively time-stamping sensor data when it arrives at the host. It is passive in the sense that the algorithm requires no special cooperation from the sensor. Our method estimates the timing jitter induced by hosts, and thus does not require a real-time operating system. We rigorously derive and characterize the method, proving that it can only improve upon the synchronization accuracy of the standard approach.

IROS Conference 2010 Conference Paper

Automated safety inspection of grade crossings

Pradeep Ranganathan
Edwin Olson

A grade crossing is a crossing of a railway line and a motor road. In 2009 alone there were 248 deaths and 682 injuries at grade crossings in the United States. Factors like the elevation profile of a crossing or the environment and foliage around the crossing can render it unsafe. Often, vehicles with low ground clearance bottom out on a crossing with a humped elevation profile. Excessive foliage around the crossing can obstruct the visibility of an approaching train, reducing the time a driver has to stop. Hence ensuring safety requires regular monitoring and timely maintenance of grade crossings across the country. In this paper, we describe our method for automatically inspecting grade crossings. Our work employs principled machine learning methods to detect grade crossings from sensor data and then reconstructs the profile of that rail-road intersection. We then show how traffic simulation on the reconstructed profile can be used to determine whether the crossing is unsafe.

ICRA Conference 2010 Conference Paper

Extracting general-purpose features from LIDAR data

Yangming Li
Edwin Olson

The detection of features from Light Detection and Ranging (LIDAR) data is a fundamental component of feature-based mapping and SLAM systems. Existing detectors tend to exploit characteristics of specific environments: corners and lines from indoor (rectilinear) environments, and trees from outdoor environments. While these detectors work well in their intended environments, their performance in different environments can be very poor. We describe a general purpose feature detector for LIDAR data that is applicable to virtually any environment. Our methods adapt classic feature detection methods from the image processing literature, specifically the multi-scale Kanade-Tomasi corner detector. Our resulting method is capable of identifying stable features at a variety of spatial scales and produces uncertainty estimates for use in a state estimation algorithm. We present results on standard datasets, including Victoria Park and Intel Research Center (both 2D), and the MIT DARPA Urban Challenge dataset (3D).

IROS Conference 2010 Conference Paper

Graph-based segmentation for colored 3D laser point clouds

Johannes H. Strom
Andrew Richardson 0002
Edwin Olson

We present an efficient graph-theoretic algorithm for segmenting a colored laser point cloud derived from a laser scanner and camera. Segmentation of raw sensor data is a crucial first step for many high level tasks such as object recognition, obstacle avoidance and terrain classification. Our method enables combination of color information from a wide field of view camera with a 3D LIDAR point cloud from an actuated planar laser scanner. We extend previous work on robust camera-only graph-based segmentation to the case where spatial features, such as surface normals, are available. Our combined method produces segmentation results superior to those derived from either cameras or laser-scanners alone. We verify our approach on both indoor and outdoor scenes.

IROS Conference 2010 Conference Paper

LCM: Lightweight Communications and Marshalling

Albert S. Huang
Edwin Olson
David C. Moore

We describe the Lightweight Communications and Marshalling (LCM) library for message passing and data marshalling. The primary goal of LCM is to simplify the development of low-latency message passing systems, especially for real-time robotics research applications. Messages can be transmitted between different processes using LCM's publish/subscribe message-passing system. A platformand language-independent type specification language separates message description from implementation. Message specifications are automatically compiled into language-specific bindings, eliminating the need for users to implement marshalling code while guaranteeing run-time type safety. LCM is notable in providing a real-time deep traffic inspection tool that can decode and display message traffic with minimal user effort and no impact on overall system performance. This and other features emphasize LCM's focus on simplifying both the development and debugging of message passing systems. In this paper, we explain the design of LCM, evaluate its performance, and describe its application to a number of autonomous land, underwater, and aerial robots.

ICRA Conference 2009 Conference Paper

Real-time correlative scan matching

Edwin Olson

Scan matching, the problem of registering two laser scans in order to determine the relative positions from which the scans were obtained, is one of the most heavily relied-upon tools for mobile robots. Current algorithms, in a trade-off for computational performance, employ heuristics in order to quickly compute an answer. Of course, these heuristics are imperfect: existing methods can produce poor results, particularly when the prior is weak. The computational power available to modern robots warrants a re-examination of these quality vs. complexity trade-offs. In this paper, we advocate a probabilistically-motivated scan-matching algorithm that produces higher quality and more robust results at the cost of additional computation time. We describe several novel implementations of this approach that achieve real-time performance on modern hardware, including a multi-resolution approach for conventional CPUs, and a parallel approach for graphics processing units (GPUs). We also provide an empirical evaluation of our methods and several contemporary methods, illustrating the benefits of our approach. The robustness of the methods make them especially useful for global loop-closing.

ICRA Conference 2009 Conference Paper

Simultaneous local and global state estimation for robotic navigation

David C. Moore
Albert S. Huang
Matthew R. Walter
Edwin Olson
Luke Fletcher
John J. Leonard
Seth J. Teller

Recent applications of robotics often demand two types of spatial awareness: 1) A fine-grained description of the robot's immediate surroundings for obstacle avoidance and planning, and 2) Knowledge of the robot's position in a large-scale global coordinate frame such as that provided by GPS. Although managing information at both of these scales is often essential to the robot's purpose, each scale has different requirements in terms of state representation and handling of uncertainty. In such a scenario, it can be tempting to pick either a body-centric coordinate frame or a globally fixed coordinate frame for all state representation. Although both choices have advantages, we show that neither is ideal for a system that must handle both global and local data. This paper describes an alternative design: a third coordinate frame that stays fixed to the local environment over short time-scales, but can vary with respect to the global frame. Careful management of uncertainty in this local coordinate frame makes it well-suited for simultaneously representing both locally and globally derived data, greatly simplifying system design and improving robustness. We describe the implementation of this coordinate frame and its properties when measuring uncertainty, and show the results of applying this approach to our 2007 DARPA Urban Challenge vehicle.

ICRA Conference 2008 Conference Paper

Online constraint network optimization for efficient maximum likelihood map learning

Giorgio Grisetti
Dario Lodi Rizzini
Cyrill Stachniss
Edwin Olson
Wolfram Burgard

In this paper, we address the problem of incrementally optimizing constraint networks for maximum likelihood map learning. Our approach allows a robot to efficiently compute configurations of the network with small errors while the robot moves through the environment. We apply a variant of stochastic gradient descent and use a tree-based parameterization of the nodes in the network. By integrating adaptive learning rates in the parameterization of the network, our algorithm can use previously computed solutions to determine the result of the next optimization run. Additionally, our approach updates only the parts of the network which are affected by the newly incorporated measurements and starts the optimization approach only if the new data reveals inconsistencies with the network constructed so far. These improvements yield an efficient solution for this class of online optimization problems. Our approach has been implemented and tested on simulated and on real data. We present comparisons to recently proposed online and offline methods that address the problem of optimizing constraint network. Experiments illustrate that our approach converges faster to a network configuration with small errors than the previous approaches.

ICRA Conference 2006 Conference Paper

Fast Iterative Alignment of Pose Graphs with Poor Initial Estimates

Edwin Olson
John J. Leonard
Seth J. Teller

A robot exploring an environment can estimate its own motion and the relative positions of features in the environment. Simultaneous localization and mapping (SLAM) algorithms attempt to fuse these estimates to produce a map and a robot trajectory. The constraints are generally non-linear, thus SLAM can be viewed as a non-linear optimization problem. The optimization can be difficult, due to poor initial estimates arising from odometry data, and due to the size of the state space. We present a fast non-linear optimization algorithm that rapidly recovers the robot trajectory, even when given a poor initial estimate. Our approach uses a variant of stochastic gradient descent on an alternative state-space representation that has good stability and computational properties. We compare our algorithm to several others, using both real and synthetic data sets