Research Abstracts - 2007

Introduction

Mobile robots have much to offer: they can vacuum our carpets, guide and/or transport our elderly and infirm, and remove humans entirely from dangerous industrial or military activities. Many applications subject the robot not to the orderly and predictable confines of an assembly-line, but to the ever-changing and often chaotic environments of the real world. Even if an architect provided a detailed map of a nursing home, for example, that map would not account for the positions of furniture, chairs, or humans. For robots to help us, they must be able to build up-to-the-moment maps themselves.

Mapping is a sensor fusion problem: compute the best possible map from a set of sensor observations. The problem is infinitely variable in complexity: better sensors and confined environments lead to simpler problems, while poorer sensors and expansive environments make the problem harder. With better mapping algorithms, robots can handle larger environments, or can be built with lower-cost sensors. The limited penetration of robots into our daily lives is a testament to the shortcomings of the state-of-the-art; at best, we see very expensive robots operating in rather limited environments.

We are working on several techniques that significantly improve mapping algorithms, increasing their reliability, increasing the quality of the maps, and increasing the speed at which those maps can be computed.

Recognizing Places

A central problem in robot navigation is recognizing when a robot is somewhere that it has been before. Without "closing the loop", the robot's position uncertainty increases without bound; consequently navigation, map-building, and other common robot tasks become impossible.

In the presence of globally-unique features (RFID tags embedded in the environment, for example), closing the loop is trivial. More commonly, however, evidence of a loop closure is weak. Planar laser scanners are a typical robotic sensor, producing cross-sectional maps of environments (see above). Unfortunately, indoor environments tend to be composed of similar-looking elements (corners, walls, etc.), leading to many false matches.

     

We are developing algorithms that consider groups of several dozen loop closure hypotheses and robustly rejects the incorrect hypotheses. Our approach maps the loop-closing problem onto the Single Cluster Graph Partitioning (SCGP) problem, which has an efficient solution [1].

Optimizing Maps

As a robot explores an environment, recognizing when it revisits places it has been before, the challenge is to compute a posterior map that incorporates all of the data collected by the robot. This is, in effect, an optimization problem in a large and non-linear state space.

     

Current optimization algorithms have a limited ability to deal with poor initial estimates. The family of linearizing approaches (Extended Kalman Filter, Extended Information Filter, and the many approaches that improve upon their computational complexity [2,3], irrevocably introduce linearization error. When the state estimate is poor, these linearization errors can lead to poor estimates, even though the filter's covariance estimate may indicate low error.

We are investigating a family of approaches that offer an iterative way of computing a posterior map. Each individual iteration takes very little time and memory, extending the reach of mapping algorithms to larger environments while allowing implementors to trade-off run-time versus quality [4].

Our most recent efforts have produced an incremental algorithm: one that can incorporate new data without the need to restart the optimization from scratch. This makes the algorithm far more attractive for online use.

Automotive Sensing

In conjunction with MIT's DARPA Grand Challenge Team, we are also pursuing automotive sensing algorithms that track and predict the behavior of other vehicles while detecting other driving hazards. Not only is this a difficult task, but a failure (such as failing to detect an oncoming car) can lead to catastrophe. The automotive environment is also very dynamic: closing rates of vehicles exceed 60mph even in city traffic, requiring systems to be not only reliable, but also very fast.

References:

[1] Edwin Olson, Matthew Walter, John Leonard, and Seth Teller. Single Cluster Graph Partitioning for Robotics Applications. In Proceedings of Robotics Science and Systems, pp. 265-272, Cambridge, MA 2005.

[2] J. Knight, A. Davison, and I. Reid. Towards constant time SLAM using postponement. In Proceedings of the International Conference on Intelligent Robots and Systems, Maui, USA, 2001.

[3] Jose Guivant and Eduardo Nebot. Compressed Filter for Real Time Implementation of Simultaneous Localization and Map Building. In FSR 2001 International Conference on Field and Service Robotics. 2001.

[4] Edwin Olson, John Leonard, and Seth Teller. Fast Iterative Optimization of Pose Graphs with Poor Initial Estimates. In Proceedings of ICRA 2006, pp 2262-2269. 2006.