The Robot's Dilemma

That guessing game is the deepest problem in all of robotics, and almost everything else in this course is a clever way of playing it well. Before we name it or do any math, let's feel it.

Get lost on purpose

The ghost below is where you truly are. The solid dot is where you think you are. Walk around in the dark and watch the two drift apart.

Try this:

1. Blind walk. Tap Step blindly ten times. Watch the uncertainty bubble swell and your estimate peel away from reality.
2. Touch a wall. Near a door (15 m, 30 m, 45 m), tap Touch wall. Your uncertainty collapses in an instant: you just got a fix.
3. Let it run, then stop touching. Step 30 times with your eyes closed. How hopelessly lost are you?

Two forces, locked in a tug-of-war: moving makes you lost, looking makes you found. That tension is the robot's dilemma, and it never goes away. It just gets managed.

The two ways to know where you are

Every robot, animal, and ship navigator has only two tricks.

Trick one: count your own steps. Close your eyes and track how far you've moved. Wheel encoders, leg counts, the spin of a gyroscope. It's smooth, always available, and needs nothing from the outside world. It is also a slow-motion catastrophe: every step adds a sip of error, and the errors never cancel. They pile up. Engineers call this odometry, or dead reckoning, and it has been drowning people for centuries.

↘ How a sextant actually works: bringing a star down to the horizon

The sextant is the perfect physical metaphor for this whole lesson, so it is worth understanding instead of just looking at. It is a doubly reflecting instrument: it measures the angle between two visible objects (usually a star or the Sun and the horizon) by bouncing light off two mirrors in series.

The two mirrors. Light from the star hits the index mirror (mounted on a swinging arm), reflects down onto the horizon mirror, and from there into a small telescope at your eye. The horizon mirror is the clever part: half of it is plain glass and half is silvered. Through the clear half you look straight out at the real horizon. In the silvered half you see the reflected star. Swing the index arm until the two images line up in the same view, and you have optically "brought" the star down to sit right on the horizon.

Reading the angle off the arc. The index arm slides along a curved, graduated scale (the arc), and where it stops tells you the altitude: the angle between the star and the horizon. Sailors call this "sighting," "shooting," or "taking a sight." A quirk of the double reflection is that the scale must be marked at twice the true mirror angle: rotate the index arm by 20 degrees and the angle between the incoming and outgoing rays changes by 40 degrees, because the angle of incidence always equals the angle of reflection at each mirror. A good sextant reads to one minute of arc (1/60 of a degree), and a skilled navigator gets the right answer to within a fraction of that.

Why the name. The frame is a sector of about one sixth of a circle, roughly 60 degrees, which is exactly what "sextant" means (Latin sextans, "one sixth"). You "swing" the instrument gently to make sure you are holding it truly vertical when the star kisses the horizon.

From one angle to a place on Earth. That single altitude reading, paired with the exact time you took it, is enough to draw a line of position on the chart: every point along that line would see the star at the same height. Sight the Sun at local noon, or Polaris at night in the Northern Hemisphere, and your line of position is a line of latitude. To turn that line into a single dot, you cross it with a second sight, or with your existing dead-reckoning track. That intersection is the fix.

That last sentence is the whole lesson in miniature. Between sights, the sailor ran on dead reckoning and drifted (the predict step). A sextant sight snapped that drift back to a known line (the update step). And the hardest fix of all, longitude, needs the exact time: measuring the Moon's angular distance from a star gives Greenwich time, and hence longitude. That dependence on accurate time at sea is precisely the problem the Longitude Prize, mentioned above, was created to solve.

Trick two: look for landmarks. Touch a doorframe you recognise; spot a star; read a sign. Suddenly your accumulated drift snaps back to zero. This is exteroception (sensing the outside world), and it's the only thing that stops dead reckoning from killing you. Cameras, lidar, that sextant. The cost: landmarks aren't always there, and your eyes lie a little too.

The dance: predict, then correct

Stir those two tricks together and you get the heartbeat of every localization algorithm ever written:

• Predict. Take a step with your eyes closed. Uncertainty grows. 📈
• Update. Open your eyes, spot a landmark, snap back to reality. Uncertainty shrinks. 📉

Predict, update, predict, update, a hundred times a second, for as long as the robot is alive. Kalman filters, particle filters, graph SLAM: every method in this course is just a different, more mathematically honest way of doing this exact two-step. Master the dance and the rest is choreography.

Your brain already does this

If this feels intuitive, it should: you are running it right now. Tucked in your entorhinal cortex are grid cells that fire in a stunning hexagonal lattice as you move, dead-reckoning your position in space. Nearby place cells fire when you recognise a specific spot, your biological "landmark update."

Same dilemma, everywhere

• Mars rovers can't use GPS, so they watch terrain features slide past their cameras to estimate motion, and still drift, so they correct against maps shot from orbit.
• Warehouse robots stick QR codes to the floor every few metres: cheap, reliable, deliberately-placed landmarks.
• Self-driving cars match a live lidar scan against a pre-built high-definition map: a landmark fix, millions of points at a time.

Different sensors, identical dilemma: move and drift, look and correct.

↘ The math: why uncertainty grows like a random walk

We can be precise about how lost you get. Your position estimate evolves through a motion model:

$$x_t = f(x_{t-1}, u_t) + w_t$$

where $u_t$ is the control (how far you meant to move) and $w_t$ is process noise: the slip, the skid, the imperfect step. Each step injects a little independent variance, and because the noise is independent, the variances add:

$$\sigma_t^2 = \sigma_{t-1}^2 + \sigma_{\text{motion}}^2$$

So after $n$ blind steps with per-step noise $\sigma_{\text{motion}}$, your uncertainty grows as

$$\sigma_n = \sigma_{\text{motion}}\sqrt{n}$$

That $\sqrt{n}$ is the signature of a random walk, the same law that governs a drunkard's stagger and a diffusing gas molecule. Ten blind steps at $\sigma_{\text{motion}} = 0.5\,\text{m}$ leaves you with $0.5\sqrt{10} \approx 1.58\,\text{m}$ of doubt. A landmark fix is what resets that clock to (nearly) zero.

Key takeaways

• Internal sensors (odometry, IMU) are always available but drift: error compounds as $\sqrt{n}$ and never self-corrects.
• External sensors (cameras, lidar) fix drift against landmarks, but only when a landmark is in view.
• SLAM is the endless cycle of predict (move, grow uncertainty) and update (observe, shrink it). Every algorithm ahead is a refinement of this one idea.