Key Moments
Stanford AA274A Principles of Robotic Autonomy | Autumn 2019 | EKF Localization
Stanford OnlineKey Moments
EKF localization approximates robot pose using Gaussian assumptions, making it computationally efficient but less accurate for multimodal initial states or dynamic environments.
Key Insights
The core problem of localization is to find the transformation (rotation and translation) that aligns the robot's local coordinate system with the map's global coordinate system.
EKF localization is best suited for 'local' localization problems where the initial robot pose is known with high certainty, assuming a unimodal probability distribution.
For 'global' or 'kidnapped robot' localization problems, where the initial pose is unknown, multimodal algorithms like particle filters are more appropriate than EKF.
The state transition model in EKF localization incorporates robot kinematics, process noise, and importantly, a constraint based on the known map to prevent physically impossible states (e.g., collisions).
The measurement model for EKF localization uses range and bearing sensors to estimate the robot's state (XY position and orientation), relating known landmark positions to noisy sensor readings.
EKF localization iteratively updates the robot's estimated pose and its uncertainty (covariance) by sequentially processing measurements, combining motion and measurement models.
Defining the localization problem
Localization is fundamentally about determining a robot's pose (position and orientation) relative to a known map. This involves finding the transformation between the map's global coordinate system and the robot's local coordinate system. Essentially, it's about aligning these two frames of reference. Knowing this transformation allows the robot to understand its environment and plan safe paths, avoid obstacles, and reach its destination. The process is inherently a filtering problem, as the robot's true state is unobservable directly and must be inferred from noisy measurements over time, combined with control inputs and prior map information. This is analogous to Bayesian filtering, where we maintain a probabilistic belief about the robot's state.
Classifying localization challenges
Localization problems can be categorized along several dimensions. Firstly, the initial state uncertainty: 'local localization' assumes a well-known starting pose, often modeled by a unimodal (e.g., Gaussian) distribution, making EKF suitable. 'Global localization' starts with high uncertainty (e.g., uniform distribution), requiring multimodal approaches like particle filters. The 'kidnapped robot problem' is a variant where the robot's pose is suddenly lost or changed, demanding robustness. Secondly, environmental dynamics: 'static' environments have only the robot moving, while 'dynamic' environments include other moving objects, adding complexity. Thirdly, active vs. passive localization: passive localization uses sensor data collected during normal operation, while active localization strategically plans movements to improve pose estimation. Lastly, single-robot vs. multi-robot localization involves collaborative pose estimation.
Formulating localization as Bayesian filtering
The lecture frames localization as a Bayesian filtering problem. Key components are defined: the 'state' (e.g., robot's X, Y position and orientation), 'controls' (e.g., linear and angular velocities influencing state transitions), and 'measurements' (e.g., range and bearing to landmarks from sensors). A crucial addition for robotics is the 'map,' which provides prior knowledge about the environment. The goal is to estimate the posterior belief of the robot's state at time 't', given all previous states, controls, measurements, and the map. This involves defining a state transition model (how the robot moves) and a measurement model (how sensors relate to the state), both incorporating probabilistic noise and the map information.
Modeling robot motion with the state transition model
The state transition model describes how the robot's state evolves over time based on control inputs and inherent process noise. For a robot like a unicycle, this model is derived from its kinematic equations (e.g., relating linear velocity and steering angle to changes in X, Y, and orientation). To make it probabilistic, Gaussian process noise is added, reflecting uncertainties in motion. A critical enhancement for localization is conditioning this model on the map. This means the transition probability should disallow impossible states, such as the robot moving into an obstacle. Mathematically, this is achieved by multiplying the standard transition probability by a factor that is zero if the resulting state is a collision and non-zero otherwise. This map-aware transition model ensures that the robot's predicted state remains physically plausible.
Representing the environment with maps
Maps can be represented in various ways, impacting computational complexity and information content. 'Occupancy grid maps' discretize the environment into cells, each assigned a probability of being occupied. This is a dense, volumetric representation but can be memory-intensive. 'Feature-based maps' represent the environment as a collection of landmarks (points, lines, or semantic objects) with known properties (e.g., coordinates). This is more concise but requires accurate feature extraction and matching. The lecture uses point landmarks (like beacons) with known global coordinates for illustrative purposes, focusing on how sensor measurements relate to these landmarks and the robot's pose.
The measurement model and landmark association
The measurement model relates the robot's state to the sensor readings. For range and bearing sensors measuring distance and angle to landmarks, the relationship is non-linear. The robot's pose (X, Y, θ) and the known landmark coordinates determine the expected sensor measurements. A significant challenge is 'data association': determining which sensor reading corresponds to which landmark, especially with multiple landmarks and potential ambiguities. The lecture introduces 'correspondence variables' (CT) to explicitly model this association, noting that assuming known correspondences simplifies the problem, while unknown correspondences require estimation, often via Maximum Likelihood Estimation.
EKF approximation for non-linearities
The Extended Kalman Filter (EKF) is employed to handle the non-linearities in robot motion and measurement models. It linearizes these models around the current best estimate of the robot's state using Taylor series expansion. The state transition model is linearized using its Jacobian matrix (G), and the measurement model is linearized using its Jacobian matrix (H). This approximation allows the standard Kalman filter update equations to be applied. The filter iteratively updates the mean (μ) and covariance (Σ) of the robot's estimated pose. The covariance represents the uncertainty in the pose estimate.
The EKF update cycle
The EKF localization process involves two main steps: prediction and update. In the prediction step, the robot's current pose estimate (mean and covariance) is propagated forward using the state transition model and control inputs. This results in a predicted pose estimate and an increased covariance due to process noise and the linearization of the motion model. In the update step, sensor measurements are used to correct the predicted pose. The filter calculates a Kalman gain, which determines how much to adjust the predicted pose based on the difference between the actual measurement and the expected measurement (innovation). This gain balances the uncertainties in the prediction and the measurement. The pose estimate is then updated, and its covariance is reduced, reflecting increased certainty. The process repeats for each new measurement or time step.
Mentioned in This Episode
●Products
●Software & Apps
●Organizations
●Books
●Concepts
Common Questions
Robot localization is the problem of determining a robot's pose (position and orientation) relative to a known map. It involves finding the transformation between the map's coordinate system and the robot's local coordinate system.
Topics
Mentioned in this video
The fundamental framework used for localization, extending concepts from last week's lecture on Bayesian filtering.
A simpler, intuitive method for applying Bayesian filtering for localization, though computationally intractable in its general form.
An approximation technique used in conjunction with Bayesian filtering, leading to the Extended Kalman Filter (EKF).
The global reference frame associated with the known map.
The probabilistic graphical model framework that underpins both Bayesian filtering and localization problems.
The state of the robot, typically its position (X, Y) and orientation (theta), which needs to be determined relative to a map.
Observable data collected by sensors, used to constrain possible state values.
A map representation that relies on identifying and locating specific features or landmarks in the environment.
The robot's own reference frame.
A method to handle dynamic environments by expanding the state space to include the motion of other objects.
Uncertainty added to the state transition model to account for unpredictable factors and inaccuracies in the robot's motion.
An example robot used to illustrate localization problems, requiring the estimation of XY coordinates and orientation.
A complex localization scenario where the robot's initial pose is unknown, and it might be moved unexpectedly during operation.
Unobservable quantities that define the robot's situation, represented by a belief distribution.
Inputs that affect the evolution of the robot's state over time.
A type of map representation that divides the environment into discrete cells, each marked as occupied or free.
A probabilistic representation of the robot's knowledge about its state.
The problem of simultaneously building a map and localizing within it, discussed as a future topic when the map is unknown.
Defines the probabilistic relationship between the robot's state and the sensor measurements it receives.
A type of probability distribution used for global localization when the initial pose is unknown, contrasting with unimodal Gaussian distributions.
Localization in an environment where other objects or features are also moving, adding complexity to the problem.
A numerical method used for approximating solutions to differential equations, applied here to discretize the robot's motion model.
A probabilistic approach to localization that uses random sampling, with particle filters being a key implementation.
An abstract map representation that defines relationships between places or regions, rather than precise geometric locations.
The fundamental theorem of probability used extensively in deriving the localization algorithms.
A method used for estimating parameters, mentioned in the context of estimating landmark correspondences.
A type of feature used in landmark-based maps, represented by its X and Y coordinates.
A matrix of first-order partial derivatives used to linearize non-linear models in EKF approximations.
A key algorithm for localization, derived from Gaussian approximation, particularly effective for local localization problems.
An algorithm suitable for multimodal distributions, used for global localization and kidnapped robot problems.
A foundational algorithm for state estimation, which the EKF extends for non-linear systems.
More from Stanford Online
View all 159 summaries
78 minStanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Parametric Filtering
57 minWebinar: Regulating at the Speed of AI with Francis Fukuyama and Nate Persily
104 minStanford CME295 Transformers & LLMs | Autumn 2026 | Lecture 4 - Reinforcement Learning with LLMs
78 minStanford AA274A Principles of Robotic Autonomy | Autumn 2019 | Localization & Filters
Ask anything from this episode.
Save it, chat with it, and connect it to Claude or ChatGPT. Get cited answers from the actual content — and build your own knowledge base of every podcast and video you care about.
Get Started Free