This page contains selected papers and other resources (like power point slides). Or you can return to Edwin Olson's home page.

Direct questions/comments to eolson@mit.edu.


Mobile robots are dependent upon a model of the environment for many of their basic functions. Locally accurate maps are critical to collision avoidance, while large-scale maps (accurate both metrically and topologically) are necessary for efficient route planning. Solutions to these problems have immediate and important applications to autonomous vehicles, precision surveying, and domestic robots.

This thesis describes an optimization algorithm that can rapidly estimate the maximum likelihood map given a set of observations. The algorithm, which iteratively reduces map error by considering a single observation at a time, scales well to large environments with many observations. The approach is particularly robust to noise and non-linearities, quickly escaping local minima that trap current methods. Both batch and online versions of the algorithm are described.

In order to build a map, however, a robot must first be able to recognize places that it has previously seen. Limitations in sensor processing algorithms, coupled with environmental ambiguity, make this difficult. Incorrect place recognitions can rapidly lead to divergence of the map. This thesis describes a place recognition algorithm that can robustly handle ambiguous data. 

@phdthesis{ eolson2008phd,
        AUTHOR    = {Edwin Olson},
	TITLE     = {Robust and Efficient Robotic Mapping},
	MONTH     = {June},
	YEAR      = {2008},
	SCHOOL    = {Massachusetts Institute of Technology},
	ADDRESS   = {Cambridge, MA, USA}
}

Non-linear optimization has traditionally been considered out-of-reach of most SLAM applications do to its computational cost. However, a family of iterative batch algorithms has recently demonstrated remarkably fast convergence. Because they are batch algorithms, however, they are not well-suited to online applications. In this work, we extend the reach of these algorithms to incremental applications by describing a way of maintaining spatially-adaptive learning rates, and a way of accelerating convergence by preferentially optimizing the least-converged parts of the pose graph. 

@inproceedings{ Olson-RSS-07,
	AUTHOR    = {E. Olson and J. Leonard and S. Teller},
	TITLE     = {Spatially-Adaptive Learning Rates for Online Incremental SLAM},
	BOOKTITLE = {Proceedings of Robotics: Science and Systems},
	YEAR      = {2007},
	ADDRESS   = {Atlanta, GA, USA},
	MONTH     = {June}
}

Simple substitution ciphers are a class of puzzles often found in newspapers, in which each plaintext letter is mapped to a fixed ciphertext letter and spaces are preserved. In this paper, we describe a system for automatically solving them, even when the ciphertext is too short for statistical analysis, and when the puzzle contains non-dictionary words. Our approach is a based around a dictionary attack; we describe several important performance optimizations, as well as effective techniques for dealing with non-dictionary words. We present quantitative performance results for several variations of our approach as well as two other implementations.

@inproceedings{OlsonDecrypto2007,
	      author="Edwin Olson",
 	      title="Robust Dictionary Attack of Short Simple Substitution Ciphers",
	      journal = {Cryptologia},
	      institution = {MIT CSAIL},
	      year = {2007},
}

This is an expanded and improved version of the AUV2004 paper described below.

We present a system of simultaneously estimating the position of an Autonomous Underwater Vehicle (AUV) and the positions of stationary range-only beacons. Notably, our system does not reuqire beacon positions a priori, and our system performs well even when range measurements are severely degraded by noise and outliers. We present a powerful rejection method that can identify groups of range measurements that are consistent with each other, and a method for initializing beacon positions in an EKF. We have successfully applied our algorithms to real-world data and have demonstrated a SLAM system whose navigation performance is comparable to that of systems that assume known beacon locations.

@article{OlsonLocalization2006,
		      author = "E. Olson and J. Leonard and S. Teller",
		      title = "Robust Range-Only Beacon Localization",
		      journal = "IEEE Journal of Oceanic Engineering",
		      volume = "31",
		      number = "4",
		      pages = "949-958",
		      month = "October",
		      year = "2006"
}

Like a growing family of SLAM approaches, we explicitly optimize only the robot trajectory-- features are easily computed once the trajectory is known. Our approach uses an iterative nonlinear optimization algorithm similar to stochastic gradient descent. In short, constraints in the pose graph are considered one at a time: each constraint yields a loop with respect to the posterior robot trajectory. Any error in the constraint is distributed around the loop. In addition, we present a state space representation which allows each constraint to be updated in O(log N) time, for a trajectory with N poses.

The major advantages of this approach are that it is fast (without requiring approximate factoring of the probability density function), and that it is robust to poor initial estimates. 

@inproceedings{OlsonGraph2006,
	       author="Edwin Olson and John Leonard and Seth Teller",
	       title="Fast Iterative Optimization of Pose Graphs with Poor Initial Estimates",
	       journal = {ICRA},
	       institution = {MIT CSAIL},
	       year = {2006},
	       pages="2262-2269"
  }

An early version of this paper won Best Paper Award at the CSAIL Student Workshop in Fall 2005.


We present an algorithm for finding a single cluster of well-connected nodes in a graph. The general problem is NP-hard, but our algorithm produces an approximate solution in $O(n^2)$ by considering the spectral properties of the graph's adjacency matrix. We show how this algorithm can be used to find sets of self-consistent hypotheses while rejecting incorrect hypotheses, a problem that frequently arises in robotics. We present results from a range-only SLAM system, a polynomial time data association algorithm, and a method for parametric line fitting that can outperform RANSAC. 

@inproceedings{OlsonSCGP2005,
     author="Edwin Olson and Matthew Walter and John Leonard and Seth Teller",
     title="Single Cluster Graph Partitioning for Robotics Applications",
     booktitle="Proceedings of Robotics Science and Systems",
     pages="265-272",
     year={2005}
}

We present a system that performs pure range-only SLAM on sparsely located beacons in an environment with severe noise.

@inproceedings{Olson2004,
     author="Edwin Olson and John Leonard and Seth Teller",
     title="Robust Range-Only Beacon Localization",
     booktitle="Proceedings of Autonomous Underwater Vehicles, 2004",
     journal="IEEE AUV",
     year={2004}
}

A description of a robotics controller board that was used in the first year of MASLab.

@inproceedings{Olson2001,
    author="Max Bajracharya and Edwin Olson",
    title="A Low-Cost, High-Performance Robotics Platform for Education and Research",
    booktitle="AAAI Symposium on Robotics and Education 2001: Working Notes",
    year={2001}
}