---
title: Robotics
module: Frontiers
moduleNumber: 6
lessonNumber: 3
order: 603
summary: >
  A robot is an agent with a body: sensors that read the physical world and
  effectors that push back on it. This lesson grounds the abstract AI machinery in
  that body. We build up the hardware (range finders, proprioception, degrees of
  freedom), then cast perception as probabilistic filtering — the kinematic motion
  and sensor models, Monte Carlo localization, the extended Kalman filter, and
  simultaneous localization and mapping (SLAM). The companion lesson takes the
  estimated pose forward into planning and control.
topics: [Frontiers]
sources:
  - book: AIMA
    ref: "Ch. 25 — Robotics; §25.1 Introduction; §25.2 Robot Hardware"
  - book: AIMA
    ref: "§25.3 Robotic Perception"
---

Every other agent in these notes operates on symbols: it reasons over states,
updates beliefs, searches a graph, or minimizes a loss, and when the deliberation
ends nothing in the physical world has moved. A **robot** is a physical agent
that performs tasks by manipulating the physical world. That one requirement — a
body — brings in everything the abstract agents could ignore: noisy sensors,
slipping motors, and a world that is partially observable, stochastic, dynamic,
continuous, and bound to real time.[^intro]

This lesson grounds that machinery in a body. The
[vision-and-perception lesson](/artificial-intelligence/frontiers/vision-and-perception)
turned photons into a scene description; here that scene has to be turned into a
location, a plan, and a stream of motor torques, in a body that is already
drifting off course while you compute. Nothing new is invented — the same search,
probability, filtering, and control appear again — but each acquires a physical
body and, with it, a set of constraints the symbolic versions never faced.

## The robot as a physical agent

A robot is built from two kinds of hardware. **Effectors** are the means by which
it moves and changes the world: legs, wheels, joints, grippers. Each effector's
job is to assert a physical force on the environment. **Sensors** are the
perceptual interface, the devices that let the robot perceive: cameras and lasers
that measure the environment, gyroscopes and accelerometers that measure the
robot's own motion.[^intro] The distinction between the effector (the physical
device) and the _actuator_ (the control line carrying a command to it) matters
once we start writing control laws.

Today's robots fall into three families; the split determines which of the
problems below arise.

$$
% caption: The three families of robot. Manipulators are anchored and rigid;
% mobile robots move but cannot brace against anything; mobile manipulators pay
% for both freedoms at once.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  root/.style={draw, thick, minimum width=28mm, minimum height=9mm, align=center},
  leaf/.style={draw, minimum width=30mm, minimum height=15mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[root, draw=acc, text=acc] (r) at (0,0) {robots};
  \node[leaf] (man)  at (-4.6,-2.5) {manipulators\\(arms, anchored\\to a workplace)};
  \node[leaf] (mob)  at (0,-2.5)    {mobile robots\\(UGV, UAV, AUV,\\rovers, legged)};
  \node[leaf] (mm)   at (4.6,-2.5)  {mobile\\manipulators\\(mobility + arms)};
  \draw[->, acc, thick] (r) -- (man);
  \draw[->, acc, thick] (r) -- (mob);
  \draw[->, acc, thick] (r) -- (mm);
\end{tikzpicture}
$$

A **manipulator**, or robot arm, is physically anchored to its workplace — a
factory line, a surgical table, the International Space Station. The anchor gives
it rigidity: it can push hard and place its effector precisely because it is
braced against the floor. Manipulators are by far the most common industrial
robot, with roughly a million units installed worldwide. A **mobile robot** moves
about using wheels, legs, or similar mechanisms — unmanned ground vehicles (UGVs)
on roads, unmanned air vehicles (UAVs) overhead, autonomous underwater vehicles
(AUVs) in the deep, planetary rovers on Mars. A **mobile manipulator** combines
the two: it can reach further afield than an anchored arm, but its task is harder
precisely because it lacks the rigidity the anchor provided.

## Robot hardware

The success of a real robot depends at least as much on the design of its sensors
and effectors as on its program. So far the rest of these notes took the agent
architecture — sensors, effectors, processors — as given and concentrated on the
agent program. Here the hardware is the point.

### Sensors

Sensors split first by whether they inject energy. **Passive sensors**, such as
cameras, capture signals that other sources generate. **Active sensors**, such as
sonar, send energy into the environment and read what reflects back; they provide
more information than passive sensors at the cost of power consumption and
possible interference when several run at once.

The most important category for navigation is the **range finder**, which
measures distance to nearby objects.

| Range finder | Principle | Best for | Weakness |
| --- | --- | --- | --- |
| Sonar | reflected sound, time-of-flight | underwater (AUVs) | poor resolution in air |
| Stereo vision | parallax between two cameras | passive, rich | not reliably accurate on ground robots |
| Time-of-flight camera | reflected light, per-pixel timing | dense range images, up to 60 fps | limited range |
| Scanning lidar | steered laser beam, 1-pixel timing | long range, bright daylight | mechanically complex |
| Radar | reflected radio, km-scale | UAVs, long range | coarse |
| Tactile | physical contact | very close objects | contact-only |

A second class is the **location sensor**. Outdoors, the **Global Positioning
System** (GPS) triangulates distances to orbiting satellites — measured from the
phase shifts of their pulsed signals — to fix absolute position on Earth to within
a few meters; **differential GPS**, using a second ground receiver at a known
location, reaches millimeter accuracy. GPS fails indoors and underwater, where
localization instead leans on beacons at known positions.

The third class, and the one that ties directly to the filtering below, is the
**proprioceptive sensor**, which informs the robot of its own motion. **Shaft
decoders** count motor revolutions in small increments; on a wheeled robot they
yield **odometry**, the measured distance traveled — accurate only over short
distances, because wheels drift and slip. **Inertial sensors** (gyroscopes)
resist the change of velocity and so help reduce that uncertainty. **Force** and
**torque sensors** measure how hard the robot is gripping and turning, which is
what lets a one-ton manipulator screw in a light bulb without crushing it.

> **Definition (Passive vs. active sensor).** A **passive sensor** observes
> energy the environment already emits (a camera reads ambient light). An
> **active sensor** emits its own energy and measures the reflection (sonar,
> lidar). Active sensing buys information at the cost of power and interference.

### Effectors and degrees of freedom

To reason about effectors in the abstract, count **degrees of freedom** (DOF): one
DOF for each independent direction in which the robot, or one of its effectors,
can move. A rigid mobile robot such as an AUV has six DOFs — three for its
$(x, y, z)$ location in space and three for its angular orientation (_yaw_,
_roll_, _pitch_). Those six define the **kinematic state**, or **pose**, of the
robot. The **dynamic state** adds six more: the rate of change of each kinematic
dimension, that is, the velocities.

For a non-rigid body there are further DOFs inside the robot itself, contributed
by its joints. Two joint types recur.

$$
% caption: The two joint primitives. A revolute joint (R) rotates about an axis;
% a prismatic joint (P) slides along one. The Stanford Manipulator packs five
% revolute and one prismatic joint for six DOFs total.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % --- revolute joint (left) ---
  \fill[acc!12] (0,0) circle (7mm);
  \draw[acc, thick] (0,0) circle (7mm);
  \fill[acc] (0,0) circle (1.4pt);
  \draw[acc, ->, thick] (0.55,0.55) arc (45:315:0.78);
  \draw[black, very thick] (0,0) -- (1.9,0.9);
  \node[anchor=west] at (2.0,0.9) {rigid link};
  \node[anchor=north] at (0,-0.95) {revolute (R): rotates};
  % --- prismatic joint (right) ---
  \begin{scope}[xshift=6.4cm]
    \draw[black, very thick] (-0.4,0) -- (2.4,0);
    \draw[acc, thick, fill=acc!12] (0.5,-0.28) rectangle (1.3,0.28);
    \draw[acc, <->, thick] (-0.1,0.6) -- (1.9,0.6);
    \node[anchor=south, acc] at (0.9,0.62) {slide};
    \node[anchor=north] at (0.9,-0.4) {prismatic (P): translates};
  \end{scope}
\end{tikzpicture}
$$

A **revolute joint** generates rotational motion; a **prismatic joint** generates
sliding motion. Six DOFs are the minimum required to place a hand at a particular
point in a particular orientation. Manipulators with _extra_ DOFs are easier to
control — you can verify by hand that placing your palm flat on a table still
leaves you free to swing your elbow — so many industrial arms carry seven DOFs, not
six.

For mobile robots the DOFs of motion need not match the DOFs of actuation. A car
can be maneuvered to any $(x, y)$ point in any orientation, so it has three
**effective degrees of freedom** — but it has only two **controllable degrees of
freedom** (drive forward/back, turn). A robot is **nonholonomic** when it has more
effective than controllable DOFs, and **holonomic** when the two match. Holonomic
robots are easier to control (a car that could slide sideways would be trivial to
park) but mechanically more complex. Most arms are holonomic; most mobile robots
are nonholonomic.

The constraint can be written down exactly. A car at heading $\theta$ may only
move along the direction it points: its velocity vector $(\dot x, \dot y)$ is
parallel to $(\cos\theta, \sin\theta)$. The component _perpendicular_ to the
heading must vanish,

$$
\dot x \sin\theta - \dot y \cos\theta = 0.
$$

This is a constraint on the velocities, not on the positions, and — the defining
feature of a nonholonomic constraint — it cannot be integrated into a constraint
of the form $g(x, y, \theta) = 0$ on the configuration alone. No relation among
$(x, y, \theta)$ is forbidden; the car can reach every pose. What is forbidden is
reaching them by sliding sideways, so the constraint restricts the _paths_
between poses, which is precisely why parallel parking takes a sequence of
forward-and-turn maneuvers rather than one lateral slide. A holonomic robot has no
such velocity constraint: every direction of $(\dot x, \dot y)$ is directly
commandable.

$$
% caption: A car is nonholonomic: at pose (x, y) with heading theta it has three
% effective DOFs (any position, any orientation) but only two controllable ones
% (drive, steer), so it cannot translate sideways in one move.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % car body, rotated
  \begin{scope}[rotate=22]
    \draw[acc, thick, fill=acc!10] (-1.1,-0.5) rectangle (1.1,0.5);
    % front wheels
    \draw[black, very thick] (0.75,0.5) -- (0.75,0.8);
    \draw[black, very thick] (0.75,-0.5) -- (0.75,-0.8);
    % rear wheels
    \draw[black, very thick] (-0.75,0.5) -- (-0.75,0.8);
    \draw[black, very thick] (-0.75,-0.5) -- (-0.75,-0.8);
    \fill[acc] (0,0) circle (1.6pt);
    % heading arrow
    \draw[acc, ->, thick] (0,0) -- (1.9,0);
  \end{scope}
  \node[anchor=west] at (2.1,0.85) {heading (theta)};
  \node[anchor=north, acc] at (0.3,-0.95) {pose (x, y)};
  % allowed vs forbidden motions
  \draw[black, ->, thick] (3.6,0.6) -- (4.9,0.6);
  \node[anchor=west] at (5.0,0.6) {drive: allowed};
  \draw[red, thick] (3.6,-0.6) -- (4.9,-0.6);
  \draw[red, thick] (4.15,-1.05) -- (4.35,-0.15);
  \node[anchor=west] at (5.0,-0.6) {slide sideways: forbidden};
\end{tikzpicture}
$$

Locomotion mechanisms follow from these constraints. **Differential drive** uses
two independently actuated wheels, one per side (as on a tank): equal velocities
drive straight, opposite velocities spin in place. **Synchro drive** turns and
rolls every wheel in tight coordination. Both are nonholonomic. Legs handle rough
terrain that wheels cannot but are slow and hard to build. Stability makes the
walking gait precise. A robot is **statically stable** if the vertical projection
of its center of gravity falls strictly _inside_ the **support polygon** — the
convex hull of its ground-contact points — at every instant, so it can freeze
mid-stride and simply stand there without toppling. A six-legged robot can keep a
static gait by always leaving three well-spread legs down (a tripod), guaranteeing
the projected center of gravity has a wide polygon to sit inside. A two- or
four-legged robot in a fast gait has too few feet down to enclose its center of
gravity and is only **dynamically stable**: it stays upright by moving, keeping its
falling body under itself the way a runner does, and would fall the moment it
stopped. Dynamic stability is faster and more efficient but demands active feedback
control, which is why hopping and running robots need the controllers of the
[moving section](#moving) that a plodding tripod does not. Whatever the mechanism,
an effector needs power: the **electric motor** is the usual choice, with
**pneumatic** and **hydraulic actuation** filling niches that need more force.

## Robotic perception

Perception maps sensor measurements into internal representations of the world.
It is hard because sensors are noisy and the environment is partially observable
and dynamic — which is to say robots have exactly the problems of **state
estimation**, or **filtering**, met in the
[reasoning-over-time lesson](/artificial-intelligence/uncertainty/reasoning-over-time).
The whole apparatus carries over, with two changes for the physical setting: the
robot's own past actions become observed variables in the model, and the
variables are _continuous_ rather than discrete.

$$
% caption: Robot perception as temporal inference. State X_t evolves under action
% A_t (the transition/motion model) and emits observation Z_t (the sensor model);
% filtering folds each new action and measurement into the belief over X.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8mm},
  ob/.style={circle, draw, fill=black!8, minimum size=8mm},
  ac/.style={draw, fill=black!8, minimum size=7mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st] (xm) at (0,0)   {Xt-1};
  \node[st] (x)  at (2.6,0) {Xt};
  \node[st] (xp) at (5.2,0) {Xt+1};
  \node[ob] (zm) at (0,-1.7)   {Zt-1};
  \node[ob] (z)  at (2.6,-1.7) {Zt};
  \node[ob] (zp) at (5.2,-1.7) {Zt+1};
  \node[ac] (am) at (0,1.7)   {At-2};
  \node[ac] (aa) at (2.6,1.7) {At-1};
  \node[ac] (ap) at (5.2,1.7) {At};
  \draw[->] (xm) -- (x); \draw[->] (x) -- (xp);
  \draw[->] (xm) -- (zm); \draw[->] (x) -- (z); \draw[->] (xp) -- (zp);
  \draw[->, acc] (am) -- (xm); \draw[->, acc] (aa) -- (x); \draw[->, acc] (ap) -- (xp);
\end{tikzpicture}
$$

Let $\mathbf{X}_t$ be the state of the environment (including the robot) at time
$t$, $\mathbf{z}_t$ the observation received, and $a_t$ the action taken after
that observation. The belief state $P(\mathbf{X}_{t+1} \mid \mathbf{z}_{1:t+1},
a_{1:t})$ updates recursively, exactly as before but with an integral in place of
the sum:

$$
P(\mathbf{X}_{t+1} \mid \mathbf{z}_{1:t+1}, a_{1:t}) = \alpha\,
P(\mathbf{z}_{t+1} \mid \mathbf{X}_{t+1}) \int
P(\mathbf{X}_{t+1} \mid \mathbf{x}_t, a_t)\,
P(\mathbf{x}_t \mid \mathbf{z}_{1:t}, a_{1:t-1})\, d\mathbf{x}_t .
$$

Here $P(\mathbf{X}_{t+1} \mid \mathbf{x}_t, a_t)$ is the **transition** (or
**motion**) **model** and $P(\mathbf{z}_{t+1} \mid \mathbf{X}_{t+1})$ is the
**sensor model**. Every filter in this section instantiates this one equation.

The recursion is worth deriving, because its two-stage shape — **predict** then
**update** — reappears in every filter below (MCL, EKF, SLAM). Start from the
posterior after the new measurement and apply Bayes' rule, treating the action
$a_t$ as a known input rather than a random variable:

$$
P(\mathbf{X}_{t+1} \mid \mathbf{z}_{1:t+1}, a_{1:t}) =
\alpha\, P(\mathbf{z}_{t+1} \mid \mathbf{X}_{t+1}, \mathbf{z}_{1:t}, a_{1:t})\,
P(\mathbf{X}_{t+1} \mid \mathbf{z}_{1:t}, a_{1:t}).
$$

The first factor collapses to the sensor model $P(\mathbf{z}_{t+1} \mid
\mathbf{X}_{t+1})$ by the **sensor Markov assumption**: the current measurement
depends only on the current state, not on the history that produced it. The
second factor is the one-step **prediction** — the belief _before_ folding in
$\mathbf{z}_{t+1}$ — and it comes from marginalizing over the previous state
$\mathbf{x}_t$:

$$
P(\mathbf{X}_{t+1} \mid \mathbf{z}_{1:t}, a_{1:t}) = \int
P(\mathbf{X}_{t+1} \mid \mathbf{x}_t, a_t, \mathbf{z}_{1:t}, a_{1:t-1})\,
P(\mathbf{x}_t \mid \mathbf{z}_{1:t}, a_{1:t-1})\, d\mathbf{x}_t.
$$

The first factor inside the integral reduces to the motion model
$P(\mathbf{X}_{t+1} \mid \mathbf{x}_t, a_t)$ by the **first-order Markov
assumption** on states: given $\mathbf{x}_t$ and the action $a_t$, the next state
is independent of everything earlier. The second factor is just the previous
belief. Substituting both back reproduces Equation (25.1): the integral is the
prediction step (spread the old belief through the motion model), and the leading
$\alpha\,P(\mathbf{z}_{t+1} \mid \mathbf{X}_{t+1})$ is the update step (reweight by
how well each state explains the new measurement). Nothing here is specific to
robots — it is the recursive Bayes filter — but the continuous integral, rather
than a discrete sum, is what forces the two representations below: sample the
integral (particle filter) or assume it stays Gaussian (Kalman filter).

### Localization

**Localization** — finding out where things are, including the robot itself — is
at the heart of any physical interaction. Take a mobile robot moving slowly in a
flat 2D world for which it has an exact map. Its pose is
$\mathbf{X}_t = (x_t, y_t, \theta_t)^\top$: two Cartesian coordinates and a
heading $\theta_t$.

In the **kinematic approximation**, each action specifies a translational velocity
$v_t$ and a rotational velocity $\omega_t$ over a short interval $\Delta t$. The
deterministic prediction of the next pose is

$$
\hat{\mathbf{X}}_{t+1} = f(\mathbf{X}_t, v_t, \omega_t)
= \mathbf{X}_t + \begin{pmatrix}
v_t \Delta t \cos\theta_t \\
v_t \Delta t \sin\theta_t \\
\omega_t \Delta t
\end{pmatrix} .
$$

$$
% caption: The simplified kinematic model. From pose X_t with heading theta_t, a
% translational velocity v_t (advancing v_t*dt) and rotational velocity omega_t
% (turning omega_t*dt) predict pose X_{t+1}; the same landmark at (x_i, y_i) is
% seen at range h(X_t).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % robot t
  \draw[thick] (0,0) circle (5mm);
  \draw[thick] (0,0) -- (0.42,0.27);
  \node[anchor=north] at (0,-0.6) {Xt};
  % robot t+1
  \draw[thick] (3.2,1.7) circle (5mm);
  \draw[thick] (3.2,1.7) -- (3.66,1.9);
  \node[anchor=north west] at (3.5,1.5) {Xt+1};
  % translation arrow
  \draw[acc, ->, thick] (0.42,0.27) -- (2.78,1.55);
  \node[acc, anchor=south east] at (2.0,1.1) {advance};
  % heading angle
  \draw[black] (0,0) -- (1.3,0);
  \draw[black, ->] (0.75,0) arc (0:31:0.75);
  \node[anchor=west] at (1.0,0.2) {theta};
  % rotation at t+1
  \draw[black] (3.2,1.7) -- (4.5,1.7);
  \draw[red, ->] (4.2,1.7) arc (0:34:1.0);
  \node[red, anchor=west] at (4.3,2.1) {turn};
  % landmark
  \fill[red] (-1.0,2.6) circle (1.8pt);
  \node[red, anchor=south] at (-1.0,2.7) {landmark};
  \draw[red, dashed] (-1.0,2.6) -- (0,0);
  \node[red, anchor=east] at (-0.7,1.3) {range};
\end{tikzpicture}
$$

Physical robots are unpredictable, so the motion model is this prediction plus
Gaussian noise: $P(\mathbf{X}_{t+1} \mid \mathbf{X}_t, v_t, \omega_t) =
\mathcal{N}(\hat{\mathbf{X}}_{t+1}, \boldsymbol{\Sigma}_x)$. Two sensor models
serve the update. A **landmark model** assumes the robot detects stable,
recognizable features whose map locations $(x_i, y_i)$ are known; without noise the
range and bearing follow from geometry,

$$
\hat{\mathbf{z}}_t = h(\mathbf{x}_t) = \begin{pmatrix}
\sqrt{(x_t - x_i)^2 + (y_t - y_i)^2} \\[2pt]
\arctan\dfrac{y_i - y_t}{x_i - x_t} - \theta_t
\end{pmatrix} ,
\qquad P(\mathbf{z}_t \mid \mathbf{x}_t) = \mathcal{N}(\hat{\mathbf{z}}_t, \boldsymbol{\Sigma}_z).
$$

A **range-scan model** instead uses an array of beams; with $\hat{z}_j$ the exact
range along beam $j$ and i.i.d. Gaussian errors,

$$
P(\mathbf{z}_t \mid \mathbf{x}_t) = \alpha \prod_{j=1}^{M}
e^{-(z_j - \hat{z}_j)^2 / 2\sigma^2} .
$$

The range-scan model needs no landmark identified before a scan can be
interpreted — an advantage in a featureless corridor — but where distinctive
landmarks _are_ visible, they can pin the robot down instantly.

#### Worked example: one motion-and-observation step

For example, put the robot at pose
$\mathbf{X}_t = (2,\, 3,\, 30^\circ)$ — two meters east, three north, heading
$30^\circ$ above the $x$-axis — and issue the command $v_t = 0.5$ m/s,
$\omega_t = 10^\circ/\text{s}$ over $\Delta t = 1$ s. The deterministic prediction
$f(\mathbf{X}_t, v_t, \omega_t)$ updates each coordinate in turn. Using
$\cos 30^\circ = 0.8660$ and $\sin 30^\circ = 0.5000$,

$$
\begin{aligned}
x_{t+1} &= 2 + (0.5)(1)\cos 30^\circ = 2 + 0.4330 = 2.4330,\\
y_{t+1} &= 3 + (0.5)(1)\sin 30^\circ = 3 + 0.2500 = 3.2500,\\
\theta_{t+1} &= 30^\circ + (10^\circ/\text{s})(1\text{ s}) = 40^\circ.
\end{aligned}
$$

So $\hat{\mathbf{X}}_{t+1} = (2.4330,\, 3.2500,\, 40^\circ)$. The heading turns by
the full $\omega_t\Delta t$, but the _displacement_ is computed at the starting
heading $\theta_t$ — the model advances first, rotates second, which is the source
of the small arc-versus-chord error that shrinks as $\Delta t \to 0$. The true
next pose is this prediction plus a draw from $\mathcal{N}(\mathbf{0},
\boldsymbol{\Sigma}_x)$; a particle filter represents that spread by scattering
samples around $\hat{\mathbf{X}}_{t+1}$.

Now suppose a landmark sits at $(x_i, y_i) = (5, 7)$ and the robot, at the
predicted pose, looks for it. The noise-free observation $h(\mathbf{x}_{t+1})$
is a range and a bearing. The offset to the landmark is $\Delta x = 5 - 2.4330 =
2.5670$, $\Delta y = 7 - 3.2500 = 3.7500$, so

$$
\begin{aligned}
\text{range} &= \sqrt{2.5670^2 + 3.7500^2} = \sqrt{6.590 + 14.063}
  = \sqrt{20.65} = 4.545 \text{ m},\\
\text{bearing} &= \arctan\frac{3.7500}{2.5670} - 40^\circ
  = 55.62^\circ - 40^\circ = 15.62^\circ.
\end{aligned}
$$

The bearing is measured relative to the robot's own heading, which is why the
$-\theta_{t+1}$ term appears: the landmark lies $55.62^\circ$ above the world
$x$-axis, but only $15.62^\circ$ to the left of where the robot is pointing. If
the sensor actually returns $\mathbf{z}_{t+1} = (4.60,\, 14^\circ)$, the update
step weights this pose by $\mathcal{N}(\mathbf{z}_{t+1};\, \hat{\mathbf{z}},\,
\boldsymbol{\Sigma}_z)$ — close to the prediction, so this particle survives; a
particle whose pose predicted, say, a range of $8$ m would be weighted near zero
and culled at the next resample.

### Monte Carlo localization

Two representations of the belief $P(\mathbf{X}_t \mid \mathbf{z}_{1:t},
a_{1:t-1})$ dominate. The Kalman filter carries a single multivariate Gaussian; the
particle filter carries a cloud of samples, each a candidate pose. Localization by
particle filtering is called **Monte Carlo localization** (MCL) — the particle
filter of the reasoning-over-time chapter, handed the robot's motion and sensor
models. Its behavior as a robot finds itself inside a symmetric office building is
the clearest picture of a belief distribution in action.

$$
% caption: Monte Carlo localization. (a) Particles spread uniformly encode global
% uncertainty; (b) after moving down a symmetric corridor the cloud is bimodal —
% two equally good hypotheses; (c) a distinctive room collapses it to one mode.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % --- (a) global ---
  \draw[black] (0,0) rectangle (3,2);
  \foreach \x/\y in {0.3/0.4,0.7/1.5,1.1/0.8,1.5/1.7,1.9/0.5,2.3/1.3,2.7/0.9,
    0.5/1.1,1.3/0.3,1.7/1.1,2.1/1.8,2.5/0.4,0.9/1.9,2.9/1.6,1.5/0.9}
    \fill[acc] (\x,\y) circle (0.9pt);
  \node[anchor=north] at (1.5,-0.1) {(a) global};
  % --- (b) bimodal ---
  \begin{scope}[xshift=4cm]
    \draw[black] (0,0) rectangle (3,2);
    \foreach \x/\y in {0.55/1.0,0.65/1.05,0.6/0.95,0.7/1.1,0.5/0.9,0.62/1.0}
      \fill[acc] (\x,\y) circle (1.1pt);
    \foreach \x/\y in {2.35/1.0,2.45/1.05,2.4/0.95,2.5/1.1,2.3/0.9,2.42/1.0}
      \fill[acc] (\x,\y) circle (1.1pt);
    \node[anchor=north] at (1.5,-0.1) {(b) bimodal};
  \end{scope}
  % --- (c) unimodal ---
  \begin{scope}[xshift=8cm]
    \draw[black] (0,0) rectangle (3,2);
    \foreach \x/\y in {1.45/1.0,1.55/1.05,1.5/0.95,1.6/1.1,1.4/0.9,1.52/1.0,1.48/1.08,1.58/0.97}
      \fill[acc] (\x,\y) circle (1.1pt);
    \node[anchor=north] at (1.5,-0.1) {(c) unimodal};
  \end{scope}
\end{tikzpicture}
$$

The algorithm reads as one turn of the particle filter, specialized to a range
scan. Each cycle predicts every particle forward through the motion model,
weights it by how well its predicted scan matches the real one, and resamples in
proportion to weight so that improbable poses die out and probable poses multiply.

```algorithm
caption: $\textsc{Monte-Carlo-Localization}$ — particle filter for pose over a known map
input: velocities $v, \omega$; range scan $z = z_1, \ldots, z_M$; motion model $P(X' \mid X, v, \omega)$; sensor model $P(z \mid z^\ast)$; map $m$
input: $S$, a vector of $N$ samples (persistent across calls)
if $S$ is empty then
  for $i = 1$ to $N$ do
    $S[i] \gets$ sample from $P(X_0)$ // initialization phase
for $i = 1$ to $N$ do
  $S'[i] \gets$ sample from $P(X' \mid X = S[i], v, \omega)$ // apply motion model
  $W'[i] \gets 1$
  for $j = 1$ to $M$ do
    $z^\ast \gets \textsc{Ray-Cast}(j, X = S'[i], m)$ // predicted range along beam $j$
    $W'[i] \gets W'[i] \cdot P(z_j \mid z^\ast)$ // weight by sensor likelihood
$S \gets \textsc{Weighted-Sample-With-Replacement}(N, S', W')$
return $S$
```

#### Worked example: one predict–weight–resample cycle

Run the loop on five particles to see how weight concentrates the cloud. Suppose
after the motion step the five predicted poses produce these unnormalized sensor
likelihoods $W'[i]$ (each is the product $\prod_j P(z_j \mid z^\ast)$ over the beams):

| Particle | Predicted pose (x, y) | Raw weight $W'$ | Normalized $w$ | Cumulative $\sum w$ |
| --- | --- | --- | --- | --- |
| 1 | (2.4, 3.3) | 0.40 | 0.286 | 0.286 |
| 2 | (2.5, 3.1) | 0.10 | 0.071 | 0.357 |
| 3 | (2.3, 3.4) | 0.30 | 0.214 | 0.571 |
| 4 | (2.6, 3.0) | 0.20 | 0.143 | 0.714 |
| 5 | (5.1, 6.8) | 0.40 | 0.286 | 1.000 |

The raw weights sum to $1.40$, so dividing by $1.40$ gives the normalized column.
Two particles tie for the largest weight — particle 1 near the true pose and
particle 5 at the symmetric decoy location — reproducing the bimodal belief
of the corridor.

**Low-variance resampling** draws $N = 5$ new particles with a single random
offset $r \in [0, 1/N) = [0, 0.2)$, then steps through the cumulative
distribution at positions $r,\, r + 0.2,\, r + 0.4,\, r + 0.6,\, r + 0.8$. Take
$r = 0.10$; the five comb positions are $0.10,\, 0.30,\, 0.50,\, 0.70,\, 0.90$.
Reading each against the cumulative column selects:

$$
\underbrace{0.10}_{\to\, 1},\quad
\underbrace{0.30}_{\to\, 1},\quad
\underbrace{0.50}_{\to\, 3},\quad
\underbrace{0.70}_{\to\, 4},\quad
\underbrace{0.90}_{\to\, 5}.
$$

The resampled set is $\{1, 1, 3, 4, 5\}$: particle 1 is duplicated (its high
weight earns two slots), particle 2 — the least likely — is deleted, and particles
3, 4, 5 each survive once. The improbable pose has died out and the probable pose
has multiplied, with no explicit sorting: the single comb sweep is what makes
low-variance resampling both $O(N)$ and lower-variance than drawing $N$
independent samples.

$$
% caption: One low-variance resampling sweep. The comb has N=5 equally spaced
% teeth offset by a single random r=0.10; each tooth lands in the cumulative
% interval of one particle (widths proportional to weight), so particle 1 (widest)
% is picked twice and particle 2 (narrowest) is dropped.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % cumulative bar, width 10cm = total weight 1.0
  % segment widths: p1 2.86, p2 0.71, p3 2.14, p4 1.43, p5 2.86 (cm)
  \def\yb{0}
  \fill[acc!22] (0,\yb) rectangle (2.86,0.7);
  \fill[acc!22] (3.57,\yb) rectangle (5.71,0.7);
  \fill[acc!22] (7.14,\yb) rectangle (10.0,0.7);
  \fill[red!14] (2.86,\yb) rectangle (3.57,0.7);
  \fill[red!14] (5.71,\yb) rectangle (7.14,0.7);
  \draw[black] (0,\yb) rectangle (10.0,0.7);
  % segment dividers
  \foreach \xx in {2.86,3.57,5.71,7.14} \draw[black] (\xx,\yb) -- (\xx,0.7);
  % labels inside segments
  \node at (1.43,0.35) {p1};
  \node at (3.21,0.35) {p2};
  \node at (4.64,0.35) {p3};
  \node at (6.42,0.35) {p4};
  \node at (8.57,0.35) {p5};
  % comb teeth at cumulative 0.10,0.30,0.50,0.70,0.90 -> x = 1.0,3.0,5.0,7.0,9.0
  \foreach \xx in {1.0,3.0,5.0,7.0,9.0}{
    \draw[acc, very thick, ->] (\xx,1.5) -- (\xx,0.75);
    \fill[acc] (\xx,1.5) circle (1.4pt);
  }
  \node[acc, anchor=south] at (5.0,1.55) {comb of N=5 teeth (spacing 1/N), of\/fset r};
  % result row
  \node[anchor=north] at (1.0,-0.1) {1};
  \node[anchor=north] at (3.0,-0.1) {1};
  \node[anchor=north] at (5.0,-0.1) {3};
  \node[anchor=north] at (7.0,-0.1) {4};
  \node[anchor=north] at (9.0,-0.1) {5};
  \node[anchor=north, black] at (5.0,-0.6) {resampled set: 1, 1, 3, 4, 5 (p2 dropped)};
\end{tikzpicture}
$$

Where the belief is well approximated by a single Gaussian, the **Kalman filter**
is the other route. But it is closed under only _linear_ motion and sensor models,
and $f$ and $h$ above are not linear. To address this, **linearize** them: take the
first-degree **Taylor expansion**, the tangent to $f$ at the current mean
$\boldsymbol{\mu}_t$. Around that point,

$$
f(\mathbf{x}_t, a_t) \approx f(\boldsymbol{\mu}_t, a_t) +
\mathbf{F}_t\,(\mathbf{x}_t - \boldsymbol{\mu}_t),
\qquad
\mathbf{F}_t = \left.\frac{\partial f}{\partial \mathbf{x}}\right|_{\boldsymbol{\mu}_t},
$$

where the **Jacobian** $\mathbf{F}_t$ is the matrix of partial derivatives of $f$,
one row per output coordinate and one column per state coordinate. For the
kinematic model this Jacobian is easy to write down: differentiating each row of
$f$ with respect to $(x, y, \theta)$, the only nontrivial entries come from the
$\theta$-dependence of the displacement,

$$
\mathbf{F}_t = \begin{pmatrix}
1 & 0 & -v_t\Delta t\,\sin\theta_t \\
0 & 1 &  v_t\Delta t\,\cos\theta_t \\
0 & 0 & 1
\end{pmatrix}.
$$

The prediction step then pushes the mean through the exact $f$ but the covariance
through the linear map: $\boldsymbol{\mu}_{t+1} = f(\boldsymbol{\mu}_t, a_t)$ and
$\boldsymbol{\Sigma}_{t+1} = \mathbf{F}_t\,\boldsymbol{\Sigma}_t\,\mathbf{F}_t^\top +
\boldsymbol{\Sigma}_x$. The sensor model $h$ is linearized the same way, with its
own Jacobian $\mathbf{H}_t = \partial h/\partial \mathbf{x}$, and the standard
Kalman gain then folds the measurement in. A Kalman filter that linearizes this way
is the **extended Kalman filter** (EKF). The approximation is only good when $f$
and $h$ are close to linear over the width of the current covariance; a sharp turn
with a broad belief is where the EKF misestimates its own uncertainty, since the
projected covariance is the tangent's spread, not the true nonlinear one.

The two terms in the covariance update determine the qualitative behavior. Between
landmark sightings only the prediction runs: $\boldsymbol{\Sigma}$ grows by
$\boldsymbol{\Sigma}_x$ every step, so an initial position variance of, say,
$0.01\text{ m}^2$ climbs to $0.05$, $0.09$, $0.13\ldots$ as motion noise
accumulates — the covariance ellipse swelling along the direction of travel. The
instant a landmark of known location is measured, the update step multiplies the
covariance by $(\mathbf{I} - \mathbf{K}_t\mathbf{H}_t)$ with Kalman gain
$0 < \mathbf{K}_t < \mathbf{I}$, snapping the variance back down toward the sensor's
own $\boldsymbol{\Sigma}_z$ — the ellipse contracting. Plotted over a run, the
covariance expands between landmarks and collapses at each sighting.

$$
% caption: EKF covariance over a straight run. Position variance grows by the
% motion noise Sigma_x between landmarks (rising segments) and is cut back toward
% the sensor noise Sigma_z at each landmark sighting L1, L2, L3 (downward jumps),
% so uncertainty breathes rather than diverging.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes
  \draw[->, black] (0,-0.7) -- (8.4,-0.7);
  \draw[->, black] (0,-0.7) -- (0,3.2);
  \node[anchor=north] at (4.2,-1.0) {time / distance traveled};
  \node[anchor=south, rotate=90] at (-0.35,1.4) {position variance};
  % rising then dropping trace
  \draw[acc, very thick]
    (0,-0.3) -- (2.2,1.8)   % grow
    (2.2,1.8) -- (2.2,0.0) % drop at L1
    (2.2,0.0) -- (4.6,2.0) % grow
    (4.6,2.0) -- (4.6,-0.1) % drop at L2
    (4.6,-0.1) -- (7.0,1.9) % grow
    (7.0,1.9) -- (7.0,0.0) % drop at L3
    (7.0,0.0) -- (8.0,0.9);% grow
  % landmark markers
  \foreach \xx/\lab in {2.2/L1, 4.6/L2, 7.0/L3}{
    \fill[red] (\xx,-0.7) circle (1.6pt);
    \node[red, anchor=north] at (\xx,-0.75) {\lab};
  }
  \node[acc, anchor=west, font=\scriptsize] at (0.35,2.75) {grows by Sigma-x};
  \node[red, anchor=west, font=\scriptsize] at (4.75,2.55) {cut at sighting};
\end{tikzpicture}
$$

EKF localization works well when landmarks are easy to identify; when they are
not, matching a scan to the wrong landmark is an instance of the **data
association** problem.

### SLAM

Often no map exists, and the robot must build one while using it — a chicken-and-egg
problem: to place itself it needs the map, and to build the map it needs to know
where it is. Solving both at once is **simultaneous localization and mapping**
(SLAM). Using the EKF is direct: augment the state vector with the locations of the
landmarks, so the filter estimates robot pose and map together. The EKF update
scales quadratically, so for a few hundred landmarks it is quite feasible; larger
maps are built with graph-relaxation methods or expectation–maximization.

> **Definition (SLAM).** Simultaneous localization and mapping: estimating the
> robot's pose and a map of the environment jointly, from the same stream of
> motion commands and range measurements, when neither is known in advance.

Not all perception is localization. Robots also estimate temperature, odors, or
whether the surface ahead is drivable; machine learning helps here too, mapping
high-dimensional sensor streams into low-dimensional representations and letting a
robot adapt its classifier as lighting and terrain change.


With the robot placed in its world — its pose and a map estimated from noisy motion
and range readings — the next question is what to do with that estimate. A location
is only useful if it feeds a plan: a path for the effector to follow and a stream of
torques to drive it there, computed while the body keeps drifting off course. That is
the second half of robotics, and it continues in
[Robotics: Planning and Control](/artificial-intelligence/frontiers/robot-planning-and-control).

[^intro]: **AIMA**, Ch. 25 — Robotics, §25.1 Introduction and §25.2 Robot Hardware: robots as physical agents with effectors and sensors; the manipulator / mobile-robot / mobile-manipulator taxonomy; sensor classes (passive/active, range/location/proprioceptive) and effectors, degrees of freedom, holonomicity, and locomotion.
[^perception]: **AIMA**, §25.3 Robotic Perception: robot perception as continuous, action-conditioned filtering; the kinematic motion model and landmark / range-scan sensor models; Monte Carlo localization, the extended Kalman filter and linearization, and SLAM by state augmentation.