Robotics

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.¹

This lesson grounds that machinery in a body. The vision-and-perception lesson 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.¹ 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.

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.

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.

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.

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,

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.

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 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. 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.

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:

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:

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$:

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

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},{\mathbf{\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,

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,

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$,

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}(0,{\mathbf{\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

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}},{\mathbf{\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.

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.

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^{\prime }[i]$ (each is the product ${\prod }_{j}P(z_j\mid z^{\ast })$ over the beams):

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:

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.

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 ${\mathbf{\mu }}_t$. Around that point,

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,

The prediction step then pushes the mean through the exact $f$ but the covariance through the linear map: ${\mathbf{\mu }}_{t+1}=f({\mathbf{\mu }}_t,a_t)$ and ${\mathbf{\Sigma }}_{t+1}={\mathbf{F}}_t{\mathbf{\Sigma }}_t{\mathbf{F}}_t^{\top }+{\mathbf{\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: $\mathbf{\Sigma }$ grows by ${\mathbf{\Sigma }}_x$ every step, so an initial position variance of, say, $0.01{\text{ m}}^2$ climbs to $0.05$, $0.09$, $0.13\dots$ 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 ${\mathbf{\Sigma }}_z$ — the ellipse contracting. Plotted over a run, the covariance expands between landmarks and collapses at each sighting.

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.

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.