Robot Mapping and SLAM

About this guide

This guide introduces robot mapping and simultaneous localisation and mapping from first principles. It begins with the basic ideas of state, pose, sensing, and localisation before developing the probabilistic formulation of SLAM.

The middle sections explain the dependencies and uncertainty that make SLAM difficult, then compare the major algorithm families used to solve it. Later sections cover motion models, observation models, graph optimisation, observability, and robust estimation.

Mathematical expressions, explanatory diagrams, and interactive graphs are included throughout the guide to connect the theory with its geometric and probabilistic interpretation.

---

The Robot-Mapping Problem

What is a robot?

For this chapter, a robot is a device that moves through an environment, carries sensors, receives or generates control commands, and processes information about itself and its surroundings. The method of motion is not important: a mobile robot may use wheels, legs, tracks, propellers, wings, or underwater thrusters.

The same mapping ideas therefore apply to wheeled ground robots, drones, autonomous cars, underwater vehicles, planetary rovers, and mobile manipulators. A useful simplified view is:

A mobile robot is a sensing and computation system attached to a moving platform.

Information available to the robot

A mapping system primarily uses two information streams.

Motion information

Motion information describes how the robot attempted to move or how it estimates it moved. It may describe a one-metre forward movement, a left rotation of $20^\circ$, motion with linear velocity $v$ and angular velocity $\omega$, a change in altitude, or a stop command.

The control applied during time step $t$ is conventionally written as:

$$u_t$$

The sequence of all controls from time $1$ to $T$ is:

$$u_{1:T}=\{u_1,u_2,\ldots,u_T\}.$$

Sensor observations

An observation describes what the robot sensed at time $t$. Depending on the platform, it may be a LiDAR scan, a camera frame, a depth image, a range and bearing to a landmark, a sonar scan, or an IMU measurement.

An observation at time $t$ is written as:

$$z_t$$

and the complete observation sequence is:

$$z_{1:T}=\{z_1,z_2,\ldots,z_T\}.$$

What is a map?

A map is any representation of the environment that is useful for estimation or decision-making. It may encode metric positions, occupied and free space, landmarks, walls and surfaces, room connectivity, traversable regions, or semantic labels.

A map is written abstractly as:

$$m.$$

The symbol $m$ does not prescribe a specific representation. It may denote an occupancy grid, landmark set, point cloud, topological graph, or another model.

---

States, Positions, Orientations, and Poses

State

A state is the collection of quantities needed to describe the part of the system being estimated.

For a planar robot, a common state is:

$$x_t= \begin{bmatrix} x_t\\ y_t\\ \theta_t \end{bmatrix},$$

Here, $x_t$ and $y_t$ are position coordinates, $\theta_t$ is heading or orientation, and $t$ is the time index.

For a flying robot, the state may include:

$$x_t= \begin{bmatrix} x&y&z&\phi&\theta&\psi&v_x&v_y&v_z&\cdots \end{bmatrix}^{\mathsf T},$$

where $\phi,\theta,\psi$ represent roll, pitch, and yaw.

Position

Position describes where the robot is. For planar motion, it can be represented as:

$$\mathbf{p}_t= \begin{bmatrix} x_t\\ y_t \end{bmatrix}.$$

Orientation

Orientation describes how the robot is rotated. For a planar robot, one angle is sufficient:

$$\theta_t.$$

For a free-flying body, orientation requires three rotational degrees of freedom or another orientation representation such as a quaternion.

Pose

Pose combines position and orientation. For a planar robot, the pose is:

$$\boxed{x_t=(x_t,y_t,\theta_t)}.$$

For a six-degree-of-freedom robot:

$$\boxed{x_t=(x_t,y_t,z_t,\phi_t,\theta_t,\psi_t)}.$$

---

State Estimation

Definition

State estimation means inferring an unknown state from imperfect information. The state may describe the current robot pose, a sequence of poses, landmark locations, sensor biases, velocities, or an environmental map.

An exact state is rarely available because sensors are noisy, actuators do not execute commands perfectly, wheels slip, models simplify reality, measurements can be associated with the wrong object, and the environment itself may change.

Deterministic versus probabilistic state estimation

A deterministic estimator might claim:

$$x_t=\hat{x}_t.$$

A probabilistic estimator instead represents a distribution:

$$p(x_t).$$

The distribution describes both the most likely state and the uncertainty around it.

For a Gaussian estimate:

$$x_t\sim\mathcal N(\mu_t,\Sigma_t),$$

Here, $\mu_t$ is the estimated mean and $\Sigma_t$ is the covariance matrix.

The multivariate Gaussian density is:

$$p(x)= \frac{1} {\sqrt{(2\pi)^n|\Sigma|}} \exp\left[ -\frac12(x-\mu)^{\mathsf T} \Sigma^{-1} (x-\mu) \right].$$

The covariance matrix contains both individual uncertainty and cross-correlation between state variables.

---

Localisation, Mapping, and SLAM

Localisation

Localisation estimates the robot pose when the map is already known.

Known:

$$m,\quad u_{1:T},\quad z_{1:T}.$$

Unknown:

$$x_t \quad\text{or}\quad x_{0:T}.$$

The localisation question is:

Given a known map and sensor data, where is the robot?

Localisation cycle

flowchart TD
    A[Previous pose estimate] --> B[Apply motion or odometry]
    B --> C[Predicted pose]
    C --> D[Predict expected sensor observation from known map]
    D --> E[Compare expected and measured observations]
    E --> F[Corrected pose estimate]
    F --> A

A motion estimate usually increases uncertainty. A useful observation reduces uncertainty.

Mapping

Mapping estimates the environment when the sensor trajectory is known.

Known:

$$x_{0:T},\quad z_{1:T}.$$

Unknown:

$$m.$$

The mapping question is:

Given the poses from which measurements were collected, what does the environment look like?

If the sensor pose is known, an observed range can be transformed into the map frame and inserted into the environment model.

SLAM

SLAM stands for:

$$\boxed{\text{Simultaneous Localisation and Mapping}}.$$

In SLAM, neither the trajectory nor the map is known perfectly.

Unknown:

$$x_{0:T},\quad m.$$

The robot must estimate both from:

$$u_{1:T},\quad z_{1:T}.$$

Comparison

Problem	Map known?	Robot pose known?	Estimated quantity
Localisation	Yes	No	Pose or trajectory
Mapping	No	Yes	Map
SLAM	No	No	Trajectory and map

The chicken-and-egg dependency

A good map is required for accurate localisation, but accurate localisation is required to construct a good map.

flowchart LR
    A[Accurate pose estimate] --> B[Measurements placed correctly]
    B --> C[Accurate map]
    C --> D[Better localisation]
    D --> A

The destructive version is:

flowchart LR
    A[Pose drift] --> B[Measurements inserted at wrong positions]
    B --> C[Distorted map]
    C --> D[Poorer localisation]
    D --> A

Therefore, localisation and mapping are not generally independent stages. They form a joint estimation problem.

---

Navigation and Motion Planning

Navigation

Navigation means moving a robot autonomously from one location to another. A complete navigation system may combine a map, localisation, path planning, obstacle avoidance, and low-level control.

SLAM is not identical to navigation. SLAM estimates the robot and environment; navigation uses those estimates to decide and execute motion.

Motion planning

Motion planning determines a valid sequence of states or controls that takes a system from an initial configuration to a goal.

For a mobile robot:

$$x_{\text{start}}\rightarrow x_{\text{goal}}.$$

For a manipulator, the state may instead be a vector of joint angles:

$$q= \begin{bmatrix} q_1&q_2&\cdots&q_n \end{bmatrix}^{\mathsf T}.$$

Motion planning is therefore broader than mobile navigation.

Relationship among the fields

flowchart TD
    A[State estimation] --> B[Localisation]
    A --> C[Mapping]
    B --> D[SLAM]
    C --> D
    D --> E[Map and current pose]
    E --> F[Navigation]
    F --> G[Motion planning]
    G --> H[Control and actuation]

---

Why SLAM Matters

SLAM is a foundation of autonomy because an autonomous robot must determine both its own location and the structure of its surroundings. These two questions are commonly expressed as:

$$\text{Where am I?}$$

The corresponding environmental question is:

$$\text{What does the environment look like?}$$

SLAM supports applications ranging from warehouse logistics, domestic cleaning, autonomous lawnmowers, drones, and autonomous wheelchairs to underwater inspection, mine exploration, archaeological mapping, disaster response, planetary exploration, and flexible industrial production.

Engineering compromises

Commercial systems often simplify SLAM by modifying the environment. Boundary wires for lawnmowers, ceiling beacons for cleaning robots, artificial fiducial markers, magnetic strips, and outdoor GPS all introduce additional structure that makes estimation easier.

These systems do not make SLAM unimportant. They illustrate a practical principle:

An engineering system may reduce estimation difficulty by introducing environmental assumptions or external infrastructure.

Passive mapping

In passive mapping, another agent controls the robot while the SLAM system only processes the data.

flowchart LR
    A[Human or separate controller] --> B[Robot motion]
    B --> C[Sensor and odometry stream]
    C --> D[Passive SLAM]
    D --> E[Map and pose estimate]

Unvisited areas remain unmapped because the estimator does not choose informative actions.

Active SLAM

Active SLAM selects actions that improve the estimate rather than merely accepting a predetermined trajectory.

flowchart LR
    A[Current map and uncertainty] --> B[Choose informative next action]
    B --> C[Robot moves]
    C --> D[New observations]
    D --> E[Updated map and uncertainty]
    E --> A

The robot may deliberately revisit a known place, observe an uncertain landmark, explore unknown space, close a loop, or avoid motion that would provide little useful information.

---

Formal SLAM Notation

Robot trajectory

The robot pose at time $t$ is written as:

$$x_t.$$

The complete trajectory collects every pose from the initial state through time $T$:

$$x_{0:T} = \{x_0,x_1,\ldots,x_T\}.$$

Why there is one more pose than control

Each control connects two poses:

flowchart LR
    X0["x₀"] -- "u₁" --> X1["x₁"]
    X1 -- "u₂" --> X2["x₂"]
    X2 -- "u₃" --> X3["x₃"]

With $T$ motion transitions, there are $T+1$ poses. The initial pose is often defined as the coordinate origin:

$$x_0=(0,0,0).$$

This fixes the map frame; it does not necessarily provide an absolute global position.

Controls versus odometry

A command states what the robot was asked to do, whereas odometry estimates what the robot actually did. For example, the requested motion might be:

$$\text{commanded displacement}=1.00\text{ m},$$

The measured odometric motion may instead be:

$$\text{odometric displacement}=0.99\text{ m}.$$

Odometry is often preferable to raw commands because it includes feedback from encoders or other motion sensors. It still accumulates drift.

---

The Probabilistic SLAM Problem

Full SLAM posterior

The full SLAM problem is:

$$\boxed{ p(x_{0:T},m\mid z_{1:T},u_{1:T}) }.$$

Read this as:

The probability distribution over the complete robot trajectory and the map, conditioned on all controls and observations.

The quantities before the conditioning bar are unknown:

$$x_{0:T},m.$$

The quantities after the bar are known data:

$$z_{1:T},u_{1:T}.$$

Why a distribution is necessary

A robot cannot know its motion exactly. Even if a command says “move one metre,” actuator error, wheel slip, surface irregularity, calibration error, and finite encoder resolution can all cause the realised motion to differ.

Thus, the robot should not represent its position as one exact point unless the uncertainty is genuinely negligible.

Narrow and wide Gaussian beliefs

{
  "data": [
    {
      "x": [-4,-3.8,-3.6,-3.4,-3.2,-3,-2.8,-2.6,-2.4,-2.2,-2,-1.8,-1.6,-1.4,-1.2,-1,-0.8,-0.6,-0.4,-0.2,0,0.2,0.4,0.6,0.8,1,1.2,1.4,1.6,1.8,2,2.2,2.4,2.6,2.8,3,3.2,3.4,3.6,3.8,4],
      "y": [0.0001,0.0003,0.0009,0.0024,0.006,0.014,0.031,0.061,0.112,0.187,0.278,0.375,0.458,0.503,0.484,0.399,0.278,0.164,0.082,0.035,0.012,0.0034,0.0008,0.00015,0.00002,0.000003,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      "type": "scatter",
      "mode": "lines",
      "name": "Low uncertainty"
    },
    {
      "x": [-4,-3.8,-3.6,-3.4,-3.2,-3,-2.8,-2.6,-2.4,-2.2,-2,-1.8,-1.6,-1.4,-1.2,-1,-0.8,-0.6,-0.4,-0.2,0,0.2,0.4,0.6,0.8,1,1.2,1.4,1.6,1.8,2,2.2,2.4,2.6,2.8,3,3.2,3.4,3.6,3.8,4],
      "y": [0.027,0.034,0.042,0.051,0.061,0.072,0.085,0.098,0.111,0.124,0.137,0.149,0.159,0.167,0.174,0.178,0.18,0.179,0.176,0.171,0.164,0.155,0.145,0.134,0.122,0.109,0.096,0.083,0.071,0.059,0.049,0.039,0.031,0.024,0.018,0.013,0.009,0.006,0.004,0.0025,0.0015],
      "type": "scatter",
      "mode": "lines",
      "name": "High uncertainty"
    }
  ],
  "layout": {
    "title": "Probability beliefs with different uncertainty",
    "xaxis": {"title": "Possible state value"},
    "yaxis": {"title": "Probability density"},
    "legend": {"orientation": "h"}
  }
}

A narrow distribution means high confidence. A wide distribution means low confidence.

Motion error accumulation

If independent motion errors have variance $\sigma_u^2$, a simplified random-walk model gives:

$$\operatorname{Var}(x_T) = \operatorname{Var}(x_0)+T\sigma_u^2.$$

The standard deviation grows as:

$$\sigma_T = \sqrt{\sigma_0^2+T\sigma_u^2}.$$

{
  "data": [
    {
      "x": [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
      "y": [0.1,0.245,0.332,0.4,0.458,0.51,0.557,0.6,0.64,0.678,0.714,0.748,0.781,0.812,0.843,0.872,0.9,0.927,0.954,0.98,1.005],
      "type": "scatter",
      "mode": "lines+markers",
      "name": "Pose standard deviation"
    }
  ],
  "layout": {
    "title": "Accumulation of odometric uncertainty",
    "xaxis": {"title": "Number of motion steps"},
    "yaxis": {"title": "Position standard deviation"},
    "showlegend": false
  }
}

A tiny systematic heading error can produce large lateral error over a long distance.

---

Recursive Bayesian Estimation

A probabilistic robot commonly alternates between prediction and correction.

Belief

The posterior belief over the current pose is denoted by:

$$bel(x_t)$$

This distribution incorporates all information processed up to the current time.

Prediction step

Before processing the new observation, the robot predicts its state using the motion model:

$$\boxed{ \overline{bel}(x_t) = \int p(x_t\mid u_t,x_{t-1}) bel(x_{t-1}) \,dx_{t-1} }.$$

In this expression, $bel(x_{t-1})$ is the previous belief, $p(x_t\mid u_t,x_{t-1})$ is the motion model, and $\overline{bel}(x_t)$ is the predicted belief.

Prediction generally spreads the distribution because motion adds uncertainty.

Correction step

After receiving $z_t$, the robot corrects the prediction:

$$\boxed{ bel(x_t) = \eta\, p(z_t\mid x_t,m) \overline{bel}(x_t) }.$$

Here, $p(z_t\mid x_t,m)$ is the observation likelihood, while $\eta$ is a normalisation constant that ensures the distribution integrates to one.

Prediction-correction diagram

flowchart TD
    A["Previous posterior bel(xₜ₋₁)"] --> B["Motion model p(xₜ | xₜ₋₁,uₜ)"]
    B --> C["Predicted belief b̄el(xₜ)"]
    C --> D["Observation likelihood p(zₜ | xₜ,m)"]
    D --> E["Corrected posterior bel(xₜ)"]
    E --> A

---

Graphical Model of SLAM

Dependency structure

The SLAM graphical model connects poses $x_t$, controls $u_t$, observations $z_t$, and the map $m$. It makes the conditional dependencies among these variables visible:

flowchart LR
    U1["u₁"] --> X1["x₁"]
    U2["u₂"] --> X2["x₂"]
    U3["u₃"] --> X3["x₃"]

    X0["x₀"] --> X1
    X1 --> X2
    X2 --> X3

    X1 --> Z1["z₁"]
    X2 --> Z2["z₂"]
    X3 --> Z3["z₃"]

    M["map m"] --> Z1
    M --> Z2
    M --> Z3

Motion dependency

The new pose depends on the previous pose and motion input:

$$\boxed{ p(x_t\mid x_{t-1},u_t) }.$$

Observation dependency

The observation depends on the current pose and map:

$$\boxed{ p(z_t\mid x_t,m) }.$$

Interpretation of arrows

An arrow indicates probabilistic influence. For example:

$$x_{t-1}\rightarrow x_t$$

means the previous pose helps determine the current pose.

Likewise:

$$m\rightarrow z_t$$

and:

$$x_t\rightarrow z_t$$

mean the expected measurement depends on both the environment and the robot’s sensor pose.

Graphical models also expose modelling assumptions. Removing an edge asserts a conditional independence that may simplify computation but may also reduce accuracy.

---

Full SLAM and Online SLAM

Full SLAM

Full SLAM estimates the joint posterior over the complete trajectory and the map:

$$\boxed{ p(x_{0:T},m\mid z_{1:T},u_{1:T}) }.$$

Because it retains the entire trajectory, full SLAM is well suited to global map consistency, loop-closure correction, trajectory smoothing, offline processing, and graph optimisation.

Online SLAM

Online SLAM estimates only the current pose and map:

$$\boxed{ p(x_T,m\mid z_{1:T},u_{1:T}) }.$$

It is particularly relevant when the robot must act immediately.

Marginalisation

Online SLAM is obtained from full SLAM by integrating out earlier poses:

$$\boxed{ p(x_T,m\mid z_{1:T},u_{1:T}) = \int p(x_{0:T},m\mid z_{1:T},u_{1:T}) \,dx_0\,dx_1\cdots dx_{T-1} }.$$

For generic random variables $A$ and $B$:

$$p(A)=\int p(A,B)\,dB.$$

Marginalisation removes variables that are not retained explicitly.

Comparison

Property	Full SLAM	Online SLAM
Estimated robot states	Entire trajectory	Current pose
Past poses retained	Yes	Marginalised
Loop-closure correction	Natural	More restricted
Typical goal	Global consistency	Immediate operation
Common interpretation	Smoothing	Filtering

---

Why SLAM Is Difficult

Pose-map correlation

A landmark observed from an uncertain pose inherits both sensor and pose uncertainty. If the robot later improves the landmark estimate, the earlier poses connected to that landmark may also improve.

flowchart LR
    P1[Pose uncertainty] --> L[Landmark uncertainty]
    S[Sensor uncertainty] --> L
    L --> R[Re-observation]
    R --> C1[Improved landmark estimate]
    C1 --> C2[Improved previous pose estimates]

Thus, pose and map estimates are correlated. Solving them independently discards useful information.

Loop closure

Loop closure occurs when the robot recognises a previously visited place.

flowchart LR
    X0["x₀"] --> X1["x₁"]
    X1 --> X2["x₂"]
    X2 --> X3["x₃"]
    X3 --> X4["x₄"]
    X4 -. "recognises start region" .-> X0

The new loop constraint can correct accumulated drift throughout the trajectory.

Data association

Data association determines which map feature generated an observation. Formally, an association variable may be written as:

$$c_t=i,$$

meaning observation $z_t$ corresponds to landmark $m_i$.

The estimator may need to decide whether the observation came from an existing landmark, a new landmark, an outlier, or one of several plausible matches.

Wrong association

flowchart TD
    A[New observation] --> B{Which landmark produced it?}
    B -->|Correct match| C[Useful pose and map correction]
    B -->|Wrong match| D[Incorrect constraint]
    D --> E[Map deformation]
    E --> F[Overconfident wrong state]
    F --> G[Possible divergence]

Wrong data association may be more damaging than ordinary sensor noise because it introduces a structurally incorrect constraint.

Multimodal uncertainty

A robot may have several plausible locations. For example, two visually identical corridors can produce two pose hypotheses.

{
  "data": [
    {
      "x": [-6,-5.8,-5.6,-5.4,-5.2,-5,-4.8,-4.6,-4.4,-4.2,-4,-3.8,-3.6,-3.4,-3.2,-3,-2.8,-2.6,-2.4,-2.2,-2,-1.8,-1.6,-1.4,-1.2,-1,-0.8,-0.6,-0.4,-0.2,0,0.2,0.4,0.6,0.8,1,1.2,1.4,1.6,1.8,2,2.2,2.4,2.6,2.8,3,3.2,3.4,3.6,3.8,4,4.2,4.4,4.6,4.8,5,5.2,5.4,5.6,5.8,6],
      "y": [0,0,0,0,0.001,0.004,0.012,0.032,0.069,0.121,0.176,0.199,0.176,0.121,0.069,0.032,0.012,0.004,0.001,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.001,0.004,0.012,0.032,0.069,0.121,0.176,0.199,0.176,0.121,0.069,0.032,0.012,0.004,0.001,0,0],
      "type": "scatter",
      "mode": "lines",
      "name": "Belief"
    }
  ],
  "layout": {
    "title": "Multimodal pose belief",
    "xaxis": {"title": "Possible robot position"},
    "yaxis": {"title": "Probability density"},
    "showlegend": false
  }
}

A single Gaussian cannot faithfully represent two widely separated peaks.

Accuracy and consistency

An estimate is accurate when it is close to the true state, while it is consistent when its claimed uncertainty honestly covers the true error. Accuracy and consistency are related but distinct properties.

A robot may be inaccurate but consistent:

The robot is unsure and reports a large uncertainty region.

A robot may be inaccurate and inconsistent:

The robot is wrong but reports extremely high confidence.

Inconsistent overconfidence is dangerous because the estimator may reject later corrective measurements.

---

Map Representations

Volumetric maps

A volumetric map models occupied, free, or surface-containing regions of physical space. Common representations include occupancy grids, voxel maps, point clouds, signed-distance fields, and dense surface maps.

Occupancy grid

A two-dimensional occupancy grid divides the world into cells.

For cell $m_i$:

$$p(m_i=\text{occupied})$$

is the probability that the cell contains an obstacle.

A typical visual convention uses white for free cells, black for occupied cells, and grey for cells whose state is unknown.

Log-odds representation

Occupancy probability is often represented using log odds:

$$l_t(m_i) = \log \frac{p(m_i\mid z_{1:t},x_{1:t})} {1-p(m_i\mid z_{1:t},x_{1:t})}.$$

A common recursive update is:

$$l_t(m_i) = l_{t-1}(m_i) + \log \frac{p(m_i\mid z_t,x_t)} {1-p(m_i\mid z_t,x_t)} -l_0,$$

where $l_0$ is the prior log odds.

To recover probability:

$$p(m_i) = \frac{1}{1+\exp[-l_t(m_i)]}.$$

Feature-based maps

A feature map stores only distinct landmarks:

$$m= \{m_1,m_2,\ldots,m_N\}.$$

For planar point landmarks:

$$m_i= \begin{bmatrix} m_{i,x}\\ m_{i,y} \end{bmatrix}.$$

Feature maps are compact, efficient for localisation, and well suited to landmark-based filters. Their usefulness depends on reliable feature extraction and data association, however, and a sparse landmark set may not represent obstacle geometry well.

Geometric maps

A geometric map stores metric positions, distances, and shapes. Occupancy grids, floor plans, point clouds, and metric landmark maps are all geometric representations.

It can answer questions such as:

What is the distance between these two locations?

Topological maps

A topological map stores connectivity.

graph LR
    A[Entrance] --> B[Corridor]
    B --> C[Lab]
    B --> D[Office]
    D --> E[Staircase]

It answers:

Which places are connected, and through what route?

It may not preserve exact geometric distances.

Hybrid maps

A practical robot may combine a global topological graph, local geometric maps, semantic labels, and metric obstacle layers. This hybrid representation supports compact long-range planning while preserving the precision required for local motion.

---

Taxonomy of SLAM Systems

mindmap
  root((SLAM systems))
    Map representation
      Volumetric
      Feature based
      Geometric
      Topological
      Hybrid
    Correspondence
      Known
      Unknown
      Outlier tolerant
    Environment
      Static
      Dynamic
    Uncertainty
      Gaussian
      Multimodal
      Sample based
    Control
      Passive
      Active
    Resources
      Real time
      Anytime
      Any space
    Robots
      Single robot
      Multi robot

Known versus unknown correspondence

With known correspondence:

$$z_t\leftrightarrow m_i$$

is supplied.

With unknown correspondence, the estimator must infer the association. The number of possible association histories can grow rapidly.

Static versus dynamic environment

Classical SLAM usually assumes:

$$m_t=m$$

for all $t$.

A dynamic-world formulation may instead use:

$$m_t\neq m_{t-1}.$$

Moving people, doors, cars, and machinery should not necessarily be inserted into the permanent map.

Passive versus active SLAM

Passive SLAM accepts the trajectory provided to it.

Active SLAM chooses actions to reduce uncertainty or increase map coverage.

An active objective may balance travel cost and information gain:

$$a_t^* = \arg\max_{a_t} \left[ \text{expected information gain} - \lambda\,\text{motion cost} \right].$$

Anytime algorithms

An anytime algorithm produces a valid estimate quickly and refines it when additional time is available.

Any-space algorithms

An any-space algorithm adapts to memory constraints by changing the map resolution, the number of retained landmarks, the retained history, or the number of stored measurements.

Multi-robot SLAM

Multiple robots introduce extra unknown transformations between their local frames.

If robot $A$ and robot $B$ build separate maps, the system may need to estimate:

$${}^{A}T_B,$$

the transform from robot $B$’s frame to robot $A$’s frame.

Shared loop closures can then merge the maps.

---

Major SLAM Algorithm Families

Kalman-filter-based SLAM

Kalman approaches represent the state as a Gaussian:

$$x\sim\mathcal N(\mu,\Sigma).$$

For nonlinear robotics models, the Extended Kalman Filter linearises the functions around the current estimate.

Generic nonlinear system

$$x_t=g(x_{t-1},u_t)+\varepsilon_t,$$ $$z_t=h(x_t,m)+\delta_t,$$

Here, $g$ is the motion function, $h$ is the observation function, and $\varepsilon_t$ and $\delta_t$ represent noise.

The EKF uses Jacobians:

$$G_t= \frac{\partial g}{\partial x} \bigg|_{\mu_{t-1},u_t},$$ $$H_t= \frac{\partial h}{\partial x} \bigg|_{\bar{\mu}_t}.$$

Kalman-filter approaches provide a structured probabilistic formulation with explicit covariance and correlation, making them effective for approximately Gaussian landmark SLAM. Their limitations include linearisation error, poor representation of multimodal beliefs, expensive covariance growth for large maps, and vulnerability to incorrect associations.

Particle-filter-based SLAM

A particle filter represents the belief using weighted samples:

$$\left\{ x_t^{[i]},w_t^{[i]} \right\}_{i=1}^{N}.$$

The empirical distribution is:

$$p(x_t) \approx \sum_{i=1}^{N} w_t^{[i]} \delta(x_t-x_t^{[i]}).$$

Each particle represents one hypothesis. A typical update samples the motion model, evaluates observation likelihoods, updates and normalises the particle weights, and then resamples the population.

Particle filters can represent non-Gaussian beliefs and multiple hypotheses, making them a natural fit for global ambiguity. Their limitations include particle depletion, potentially high computational cost, and the large number of particles that may be required in high-dimensional state spaces.

Graph-based SLAM

Graph-based SLAM represents poses or landmarks as nodes and measurements as constraints or edges.

graph LR
    X0["x₀"] -- odometry --> X1["x₁"]
    X1 -- odometry --> X2["x₂"]
    X2 -- odometry --> X3["x₃"]
    X3 -- odometry --> X4["x₄"]
    X4 -. loop closure .-> X0

For a constraint $k$, define an error:

$$e_k(X) = z_k-\hat{z}_k(X).$$

The weighted least-squares objective is:

$$\boxed{ X^* = \arg\min_X \sum_k e_k(X)^{\mathsf T} \Omega_k e_k(X) },$$

Here, $X$ contains all optimised states and $\Omega_k$ is the information matrix of measurement $k$, with $\Omega_k=\Sigma_k^{-1}$ whenever the covariance is invertible.

Graph methods support large-scale trajectory optimisation, natural loop-closure handling, flexible sensor fusion, a direct full-SLAM interpretation, and convenient multi-robot extension. Their performance depends on solving a potentially expensive optimisation problem, rejecting false loop closures, choosing suitable robust losses, and providing a reasonable initial estimate.

Comparison

Family	Representation	Best-known strength	Main limitation
EKF SLAM	Mean and covariance	Correlated Gaussian landmark estimates	Scaling and linearisation
Particle SLAM	Weighted hypotheses	Multimodal uncertainty	Particle cost and depletion
Graph SLAM	Nodes and constraints	Global consistency and loop closure	Optimisation and outliers

---

Motion Models

Probabilistic motion model

The motion model is:

$$\boxed{ p(x_t\mid x_{t-1},u_t) }.$$

It describes the possible new poses after applying a control from a previous pose.

Rotation-translation-rotation model

A planar odometry motion can be decomposed into an initial rotation, a translation, and a final rotation.

flowchart LR
    A[Initial pose] -->|rotate δrot1| B[Aligned with travel direction]
    B -->|translate δtrans| C[New position]
    C -->|rotate δrot2| D[Final pose]

For poses $(x,y,\theta)$ and $(x',y',\theta')$:

$$\delta_{\text{trans}} = \sqrt{(x'-x)^2+(y'-y)^2},$$ $$\delta_{\text{rot1}} = \operatorname{atan2}(y'-y,x'-x)-\theta,$$ $$\delta_{\text{rot2}} = \theta'-\theta-\delta_{\text{rot1}}.$$

The predicted pose is:

$$x' = x+ \delta_{\text{trans}} \cos(\theta+\delta_{\text{rot1}}),$$ $$y' = y+ \delta_{\text{trans}} \sin(\theta+\delta_{\text{rot1}}),$$ $$\theta' = \theta+ \delta_{\text{rot1}} + \delta_{\text{rot2}}.$$

Noise is added to each component in a probabilistic model.

Nonlinear motion and banana-shaped beliefs

Heading uncertainty causes forward motion to spread position estimates along an arc.

{
  "data": [
    {
      "x": [0.7,0.9,1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9,3.1,3.3,3.5,3.7,3.9,4.1,4.3,4.5,4.7,4.9,5.1,5.3,5.5,5.7,5.9],
      "y": [-1.6,-1.5,-1.38,-1.22,-1.02,-0.78,-0.52,-0.25,0.02,0.28,0.52,0.72,0.88,1.0,1.06,1.07,1.02,0.92,0.77,0.58,0.34,0.08,-0.2,-0.48,-0.76,-1.02,-1.25],
      "mode": "markers",
      "type": "scatter",
      "name": "Possible endpoints"
    }
  ],
  "layout": {
    "title": "Illustrative banana-shaped motion uncertainty",
    "xaxis": {"title": "Forward position"},
    "yaxis": {"title": "Lateral position"},
    "showlegend": false
  }
}

A single Gaussian may approximate this shape but cannot exactly reproduce it.

---

Observation Models

Probabilistic observation model

The observation model is:

$$\boxed{ p(z_t\mid x_t,m) }.$$

It measures how likely an observation is if the robot is at pose $x_t$ in map $m$.

Range example

Suppose a wall should be five metres away. A simple model for the measurement is:

$$z_t\sim\mathcal N(5,\sigma_z^2).$$

The likelihood of an actual range $z_t$ is:

$$p(z_t\mid x_t,m) = \frac{1}{\sqrt{2\pi\sigma_z^2}} \exp\left[ -\frac{(z_t-\hat z_t)^2}{2\sigma_z^2} \right],$$

where $\hat z_t$ is the predicted range.

Landmark range-bearing model

For robot pose $(x,y,\theta)$ and landmark $(m_x,m_y)$:

$$\hat r = \sqrt{(m_x-x)^2+(m_y-y)^2},$$ $$\hat\phi = \operatorname{atan2}(m_y-y,m_x-x)-\theta.$$

The expected observation is:

$$\hat z= \begin{bmatrix} \hat r\\ \hat\phi \end{bmatrix}.$$

The innovation or residual is:

$$\nu_t=z_t-\hat z_t.$$

A small residual indicates that the state and map explain the measurement well.

Non-Gaussian sensor behaviour

Real range sensors may produce correct but noisy returns, unexpected short readings, maximum-range readings, missed returns, reflections, or measurements from dynamic objects.

A realistic model may therefore be a mixture:

$$p(z) = w_{\text{hit}}p_{\text{hit}}(z) + w_{\text{short}}p_{\text{short}}(z) + w_{\text{max}}p_{\text{max}}(z) + w_{\text{rand}}p_{\text{rand}}(z),$$

with:

$$\sum_i w_i=1.$$

---

Advanced Interpretation of SLAM

SLAM as Bayesian inference

Known data:

$$\mathcal D=\{u_{1:T},z_{1:T}\}.$$

Hidden variables:

$$\mathcal X=\{x_{0:T},m\}.$$

The task is:

$$p(\mathcal X\mid\mathcal D).$$

Maximum a posteriori estimation

Instead of representing the entire posterior, an estimator may seek its most probable configuration:

$$\boxed{ (x_{0:T}^*,m^*) = \arg\max_{x_{0:T},m} p(x_{0:T},m\mid z_{1:T},u_{1:T}) }.$$

Using Bayes’ rule:

$$p(\mathcal X\mid\mathcal D) \propto p(\mathcal D\mid\mathcal X)p(\mathcal X).$$

Taking negative logarithms converts products of Gaussian likelihoods into sums of squared errors, which leads to graph-optimisation objectives.

Filtering versus smoothing

Filtering estimates the current state using measurements up to the current time:

$$p(x_t\mid z_{1:t},u_{1:t}).$$

Smoothing estimates past states using all available measurements:

$$p(x_k\mid z_{1:T},u_{1:T}), \qquad k<T.$$

A future loop-closure observation can therefore improve an earlier pose in smoothing or full-SLAM systems.

Observability

A state variable is observable when the available measurements provide enough information to estimate it. Weak observability can arise while driving through a long featureless corridor, rotating in a visually repetitive room, attempting monocular scale estimation without additional constraints, or moving without any external observation.

Poor observability causes uncertainty to remain large in particular directions.

Gauge freedom

SLAM generally estimates relative geometry. Without an external global reference, the entire solution can be translated or rotated without changing internal measurements.

Therefore, one pose is fixed, commonly:

$$x_0=(0,0,0),$$

to remove this ambiguity.

This is not a physical measurement; it is a coordinate convention.

Robust estimation

False loop closures and outliers can dominate an ordinary squared-error objective.

Robust graph SLAM may replace:

$$e^{\mathsf T}\Omega e$$

with:

$$\rho\left(e^{\mathsf T}\Omega e\right),$$

where $\rho$ is a robust loss such as Huber or Cauchy loss.

The goal is to reduce the influence of extreme residuals.

---

Historical Perspective

Related estimation problems existed in surveying and geodesy long before mobile robotics. During the mid-1980s, robotics research began treating uncertainty in geometric relationships explicitly. The early 1990s brought probabilistic approaches to concurrent mapping and localisation, and the term SLAM became standard by the middle of that decade. Theoretical convergence results followed in the late 1990s under specific assumptions.

From around 2000 onward, practical Kalman, particle, and graph-based systems expanded rapidly. Modern SLAM now includes large-scale visual, LiDAR, inertial, semantic, dynamic, and multi-robot systems.

The problem remains active because sensors, environments, assumptions, and resource constraints differ substantially.

---

Complete End-to-End Mental Model

flowchart TD
    A["Previous belief over pose and map"] --> B["Receive control or odometry uₜ"]
    B --> C["Motion prediction"]
    C --> D["Uncertainty usually increases"]
    D --> E["Receive sensor observation zₜ"]
    E --> F["Predict expected observation from pose and map"]
    F --> G["Compute residual or likelihood"]
    G --> H["Correct current pose"]
    G --> I["Update map"]
    H --> J["Maintain pose-map correlations"]
    I --> J
    J --> K{Previously visited place?}
    K -->|Yes| L["Add loop-closure constraint"]
    K -->|No| M["Continue"]
    L --> N["Optimise or update trajectory and map"]
    M --> A
    N --> A

The central principle is:

$$\boxed{ \text{Pose accuracy affects map accuracy, and map accuracy affects pose accuracy.} }$$

---

Key Concepts at a Glance

Essential definitions

State estimation refers to the estimation of unknown robot or environmental variables. Within that broader task, localisation estimates the robot pose in a known map, mapping estimates a map from known sensor poses, and SLAM estimates the trajectory and map together.

Odometry is a relative motion estimate obtained from onboard motion sensors, while a landmark is a recognisable environmental feature. Data association determines which map feature generated an observation, and loop closure recognises a previously visited place so accumulated drift can be corrected.

Navigation covers the decisions and actions required to move toward a goal. Motion planning is the part of that process that finds a valid sequence of states or controls.

Core equations

The full SLAM posterior estimates the complete trajectory together with the map:

$$p(x_{0:T},m\mid z_{1:T},u_{1:T}).$$

The online formulation retains only the current pose and the map:

$$p(x_T,m\mid z_{1:T},u_{1:T}).$$

The motion model describes how control and the previous pose constrain the next pose:

$$p(x_t\mid x_{t-1},u_t).$$

The observation model measures how well a pose and map explain a sensor reading:

$$p(z_t\mid x_t,m).$$

The Bayesian prediction step propagates the previous belief through the motion model:

$$\overline{bel}(x_t) = \int p(x_t\mid u_t,x_{t-1}) bel(x_{t-1}) \,dx_{t-1}.$$

The correction step combines that prediction with the latest observation likelihood:

$$bel(x_t) = \eta p(z_t\mid x_t,m)\overline{bel}(x_t).$$

Marginalisation converts the full posterior into an online estimate by integrating out earlier poses:

$$p(x_T,m\mid z_{1:T},u_{1:T}) = \int p(x_{0:T},m\mid z_{1:T},u_{1:T}) dx_{0:T-1}.$$

Graph SLAM instead finds the state configuration that minimises the weighted error across all constraints:

$$X^* = \arg\min_X \sum_k e_k(X)^{\mathsf T} \Omega_k e_k(X).$$

Core ideas

Motion introduces uncertainty, and odometric errors accumulate as a robot travels. Observations can correct that drift, but pose and map estimates remain correlated: an inaccurate pose produces an inaccurate map, and an inaccurate map in turn degrades localisation. A successful loop closure can correct the entire trajectory, while a wrong data association can push the estimator toward divergence.

A Gaussian belief represents one main hypothesis, whereas particle filters can retain several competing hypotheses. Graph methods take a different view by optimising a network of constraints over poses, landmarks, and measurements.

SLAM normally estimates relative geometry unless the solution is tied to a global reference, and most classical systems assume a static environment. Active SLAM extends estimation into decision-making by selecting actions that improve the map or reduce uncertainty. No method is universally best; the right choice depends on the assumptions, sensors, environment, and available computational resources.

---

Questions for Further Exploration

• Why is mapping easy when the sensor trajectory is exactly known?

• Why does localisation require a prior map?

• Explain the chicken-and-egg nature of SLAM.

• Why is $x_{0:T}$ indexed from zero while $u_{1:T}$ begins at one?

• Interpret every symbol in:

  $$p(x_{0:T},m\mid z_{1:T},u_{1:T}).$$

• Distinguish filtering, smoothing, full SLAM, and online SLAM.

• Why does motion uncertainty generally increase over time?

• Why can a loop closure modify poses estimated much earlier?

• What is data association, and why can a wrong match be catastrophic?

• Compare volumetric and feature-based maps.

• Compare geometric and topological maps.

• Why can a single Gaussian fail in a symmetric environment?

• State the purpose of a motion model.

• State the purpose of an observation model.

• Explain the graph-SLAM objective in words.

• Why must one pose normally be fixed in SLAM?

• What distinguishes passive SLAM from active SLAM?

• Why are dynamic environments harder than static ones?

• What does estimator consistency mean?

• Under what conditions would EKF, particle, or graph-based SLAM be preferred?

---

Summary

Robot mapping combines motion information and sensor observations to estimate a representation of the environment. Localisation estimates the robot pose when the map is known; mapping estimates the map when the sensor trajectory is known; SLAM estimates both together because pose and map accuracy are mutually dependent. The full probabilistic problem is $p(x_{0:T},m\mid z_{1:T},u_{1:T})$. Motion models predict state and increase uncertainty, while observation models compare expected and actual measurements to correct the estimate. SLAM is difficult because the map and trajectory are correlated, motion errors accumulate, observations require data association, and false associations or loop closures can cause divergence. Kalman methods represent approximately Gaussian beliefs, particle methods represent multiple hypotheses, and graph-based methods optimise constraints over poses and landmarks. The correct system depends on the map representation, sensor characteristics, uncertainty, environment dynamics, computational resources, and intended robotic task.