Princeton Intro to Robotics (Fall 2026) | Lecture 10: Nondeterministic filter

Overview

The lecture develops the nondeterministic filter for robot state estimation: it maintains the set of states consistent with a known dynamics model and sensor observations, propagating that set through the dynamics and intersecting it with each observation's pre-image. Range-sensor examples clarify how measurements constrain position, while unstable dynamics, model uncertainty, and the difficulty of representing high-dimensional sets expose why the method is mainly conceptual and motivates probabilistic Bayes filtering.

Key takeaways

A perfect range sensor measuring distance from the origin constrains a 2D robot to a circle; additional range measurements intersect circles and can resolve position ambiguity.
The sensor pre-image H⁻¹(Z) is a set of candidate states, and it becomes a true inverse only when each observation uniquely identifies one state.
The nondeterministic filter updates its estimate with X̂ₜ = F(X̂ₜ₋₁) ∩ H⁻¹(Zₜ), combining reachability from dynamics with consistency under the latest observation.
Uncertainty can grow even with deterministic dynamics: for Xₜ₊₁ = λXₜ and λ > 1, an initial interval [−ε, ε] expands to [−λε, λε].
Set-based filtering can incorporate bounded errors by expanding reachable-state sets and measurement pre-images; a range error of ±ε changes an exact circle into a ring.
The method is primarily conceptual because it assigns no probabilities and can require intractable set computations for high-dimensional states or realistic camera and lidar measurements.

Chapters

0:00 State Estimation Roadmap: From Optical Flow to SLAM

The upcoming module connects state estimation, localization, and mapping, building on optical flow for drone velocity estimation.
The Lucas-Kanade algorithm illustrates the limitations and edge cases of classical optical flow; later lectures will introduce neural network approaches to SLAM.
Transformer architecture may be reviewed because modern learning-based optical flow and SLAM methods rely heavily on transformers.

5:00 Why Model Uncertainty Before Probabilistic Filtering

The nondeterministic filter represents uncertainty as a set of possible states, without probabilities or likelihood weights.
Classical localization and mapping provide a conceptual foundation for understanding assumptions and debugging modern machine learning methods.
The lecture develops set-based filtering before later lectures introduce probabilistic state estimation.

6:00 A Single Range Sensor Leaves Position Ambiguous

For a two-dimensional robot state (x, y), a range sensor measuring distance R from the origin imposes √(x² + y²) = R.
One range measurement confines the robot to a circle, so it cannot identify a unique position.
The example isolates position estimation and temporarily ignores velocity and other state variables.

12:00 Triangulation with Multiple Range Measurements

A second range measurement from the point (1, 1) restricts the robot to the intersection of two circles, generally leaving two candidate positions.
A third range measurement can resolve the ambiguity and uniquely determine position when the measurements are consistent.
The sensor measurement vector Z collects the three range observations used for triangulation.

17:00 The Sensor Model Maps State to Observation

The general sensor model is Z = H(X), mapping a robot state X to a D-dimensional observation vector.
For three range sensors, H contains distances from (x, y) to the origin, (1, 1), and a third sensor location (xc, yc).
The initial formulation assumes the sensor model is known and perfect, with no measurement error.

23:00 Pre-Images Turn Observations into Candidate States

The pre-image H⁻¹(Z) is the set of every state that could produce the observed measurement Z.
For a single perfect range sensor, the pre-image is a circle centered at the origin.
The pre-image equals an ordinary inverse function only when each observation corresponds to exactly one state.

28:00 Discrete-Time Dynamics and the Initial State Set

The filter uses discrete dynamics of the form Xₜ₊₁ = F(Xₜ, Uₜ), or Xₜ₊₁ = F(Xₜ) for closed-loop dynamics.
At time zero, the robot's state is assumed to lie within an initial set X̂₀, which may be the whole state space or a known region such as a room.
When controls are included, each dynamics update uses the specific control input applied by the robot.

32:00 Propagate Possible States Through the Dynamics

The dynamics image F(X̂₀) contains every state reachable after one step from any state in the initial set.
Formally, the image includes each X for which some X₀ in X̂₀ satisfies F(X₀) = X.
This update takes the union of all destinations generated by states in the current estimate.

38:00 Use Each Measurement to Intersect the Reachable Set

At time 1, the observation Z₁ restricts the robot to the pre-image H⁻¹(Z₁).
The updated estimate is X̂₁ = F(X̂₀) ∩ H⁻¹(Z₁), combining reachable states with states consistent with the measurement.
The same process repeats at time 2 and beyond, using each new dynamics update and observation.

42:00 The Nondeterministic Filter's Two Update Steps

At each time t, first compute the dynamics update F(X̂ₜ₋₁), then compute the observation pre-image H⁻¹(Zₜ).
The measurement update intersects those sets to produce X̂ₜ, the states still consistent with all information used by the filter.
The method is nondeterministic because it may retain multiple possible states, and non-probabilistic because it assigns no relative likelihoods.

46:00 Unstable Dynamics Can Expand State Uncertainty

Set size does not have to shrink: unstable dynamics can amplify uncertainty between observations.
For the one-dimensional dynamics Xₜ₊₁ = λXₜ with λ > 1, an initial interval [−ε, ε] expands to [−λε, λε].
With no sensor information, the observation pre-image is the entire state space, so the expanded reachable set remains uncertain.

51:00 Extend Set Filtering to Imperfect Models

The basic filter assumes exact knowledge of both the dynamics F and sensor model H, assumptions that rarely hold in practice.
With uncertain dynamics, one state can lead to a set of possible next states; the dynamics update unions those possible outcomes across the current estimate.
A range sensor with error ±ε produces a ring-shaped pre-image rather than an exact circle of radius rₜ.

58:00 Why Set-Based Filtering Leads to Bayes Filtering

Nondeterministic filtering can be overly conservative because it treats every state in the estimate as possible without ranking likelihoods.
Representing and updating sets is difficult in high-dimensional systems: a quadrotor example uses a 12-dimensional state, and realistic camera or lidar pre-images can be computationally intractable.
The next lecture introduces the Bayes filter, which maintains a probability distribution, propagates it through dynamics, and updates it using sensor observations.

Transcript excerpt

0:10 All right, I think we'll go ahead and get started. Um, so I yeah, I guess maybe before starting off with the the technical content for the day, uh, I'm trying to plan out the the next few lectures and I'm maybe just a quick poll to to try to figure out exactly what I should cover. So, the next module is going to be on state estimation, localization, and mapping. We started on this topic in the in the last lecture. Specifically, we covered optical flow, uh, which is a really important component in the state estimation uh, stack for a for a drone. Specifically, it's what allows the drone to estimate its position or its Sorry, estimate its its velocity, which you can then integrate, uh, over time to get an estimate of the position of the drone. Um, yeah, I guess maybe just before moving forward, uh,

0:58 quick show of hands, how many people have seen like the transformer architecture? Um, okay. Yeah, it's interesting. So, it's maybe 40, 50% or so. Maybe another show of hands. I guess how many people would benefit from would Yeah, would benefit from seeing a lecture or or so on on transformers? Maybe just a a quick uh, show of hands. Okay, I see. Okay, it's not unanimous. So, I guess I have to make a decision. >> [laughter] >> It's about 60% or so. Uh, yeah, I mean transformers are obviously the the kind of backbone for all of modern machine learning. So, if you haven't seen it before, uh, it is really critical to to see it. Uh, there's a question about whether you should see it in a robotics course or whether you should see it in a machine learning course, uh, but it's there's also an argument that you should just

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Introduction to Robotics @ Princeton.