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
- EKF-based dead reckoning
- EKF-based localisation using a landmark map
- Creating a landmark map
- EKF-based localization & mapping (SLAM)
- Pose-graph SLAM
- Monte-Carlo estimation (particle filter), supports multiple hypotheses
General
- Navigating Mobile Robots (Where am I?, 1996) (archived), Borenstein, Everett and Feng, 1996 (free PDF); the 1994 version is in Michigan's Deep Blue repository
- RatSLAM, Milford & Wyeth, a navigation system modelled on the rodent hippocampus; open-source version by David Ball
- SLAM techniques and algorithms (archived), Jack Collier
- A comparison of data association techniques for simultaneous localization and mapping, Aron Cooper, Masters thesis, MIT, 2005
- C4B Mobile Robotics, Paul Newman's Oxford lecture notes (free ebook)
SLAM
- SLAM for Dummies, Riisgaard and Blas, MIT course project
- Simultaneous localization and mapping: part I, Durrant-Whyte and Bailey, IEEE RAM 13(2)
- Simultaneous localization and mapping: part 2, Bailey and Durrant-Whyte, IEEE RAM 13(3)
- Giorgio Grisetti's home page, GMapping, TORO, g2o and more
- Tim Bailey's home page, SLAM tutorials and software
Kalman filter
- A new approach to linear filtering and prediction problems, Kalman (the paper!)
- Kalman filter home page (archived), Welch and Bishop
- Understanding the basics of the Kalman filter via a simple and intuitive derivation, Faragher
- EKF covariance update for a new landmark, a note on the derivation
Particle filter
- Particle filter made simple: a step-by-step beginner-friendly guide, arXiv 2025
- Particle Filter Theory and Practice with Positioning
- A brief introduction to Particle Filters (archived), Pfeiffer
- Particle filters Theory and Practice with Positioning Applications, 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
- SLAM toolbox for MATLAB, Joan Solà; EKF-SLAM in 2D and 3D, including 6-DOF visual SLAM
- pykalman, Kalman filter, smoother and EM algorithm in Python
- Carmen robot navigation toolkit
- OpenSLAM.org
- Planar SLAM CAS Robot Navigation Toolbox (archived)
- CSM, the Canonical Scan Matcher (includes PLICP), Andrea Censi
- Cartographer, real-time 2D and 3D SLAM (Google)
- FLANN, fast approximate nearest-neighbour search
- ProSLAM, stereo visual SLAM
- Factor graphs and GTSAM, a hands-on introduction
- GMapping, grid-based SLAM with particle filters (OpenSLAM)
- Hector SLAM, ROS package
GPS
- GPS.gov: how the system works
- Live position of GPS satellites, US Federal Aviation Administration
- GPS constellation status, US Coast Guard Navigation Center
- GPS info from Navigation Center (US Coast Guard)
- How to fool a GPS (TEDx talk), Todd Humphreys on the future of GPS and GPS spoofing
- NOAA publications
- 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 maritime and general aviation
These links are kept in one place for every edition and checked monthly. Resources for every chapter.