6: Localization

In order to get somewhere we need to know where we are.

In our previous discussion of map-based navigation we assumed that the robot had a means of knowing its position. This chapter introduces some of the common techniques used to estimate the location of a robot in the world — a process known as localization.

Today GPS makes outdoor localization so easy that we often take this capability for granted. Unfortunately GPS is a far from perfect sensor since it relies on very weak radio signals received from distant orbiting satellites. It cannot work where there is no line of sight radio reception, for instance indoors, underwater, underground, in urban canyons or in deep mining pits.

This chapter we will introduce the classical navigation principles such as dead reckoning and the use of landmarks on which modern robotic navigation is founded. A number of MATLAB classes are introduced for localization and map building of a non-holonomic vehicle in a planar world with point feature landmarks. The chapter covers:

• Review of classical location estimation techniques including odometry, trilateration and triangulation, celestial navigation, and GPS
• Dead reckoning
• Map-based localization
• Making a map
• Simultaneous localization and mapping (SLAM)
• Monte-Carlo estimation (particle filter), supports multiple hypotheses

General

• Navigating Mobile Robots, Borenstein (free PDF download)
• RatSLAM home page, Milford & Wyeth, navigation system modeled on the hippocampus of a rodent
• SLAM techniques and algorithms, Jack Collier.
• A comparison of data association techniques for simultaneous localization and mapping, Aron Cooper, Masters thesis, MIT, 2005.

SLAM

• SLAM for Dummies, Riisgaard and Blas
• Simultaneous localization and mapping: part I, Durrant-Whyte and Bailey, IEEE RAM 13(2)
• Simultaneous localization and mapping: part 2, Baily and Durrant-Whyte, IEEE RAM 13(3)

Kalman filter

• A new approach to linear filtering and prediction problems, Kalman (the paper!)
• Kalman filter home page, Welch and Bishop
• Understanding the basics of the Kalman filter via a simple and intuitive derivation, Faragher

Particle filter

• Particle filter tutorial, Ioannis Rekleitis
• Particle Filter Theory and Practice with Positioning
• A brief introduction to Particle Filters, Pfeiffer
• Particle filters Theory and Practice with with Positioning Aplications, Gustafsson
• A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking, Arulampalam, IEEE Signal Processing Magazine 2002
• Sequential Monte Carlo methods & Particle Filter Resources, Arnaud Doucet

Software

• KFilter C++ extended Kalman filter library
• Carmen robot navigation toolkit
• Open SLAM
• Planar SLAM CAS Robot Navigation Toolbox
• 6 DOF SLAM
• Open RatSLAM, by David Ball

GPS

• Live position of GPS satellites, Todd Humphreys on TedX about the future of GPS and GPS spoofing
• Live position of GPS satellites, US Federal Aviation Administration
• Details of current and past GPS satellites, US Naval Observatory
• GPS-System, kowoma.de
• NOAA publications
• GPS info from Navigation Center (US Coast Guard)
• Effect of builtup environment on GPS accuracy

Hyperbolic navigation systems

• GEE the WW2 era radio localization system
• DECCA Navigator a 1950s era commercial radio localization system
• LORAN-C as used for martitime and general aviation today