SLAM is short of simultaneous localization and mapping. It is a term used to describe the problem of creating a map and locating the mobile agent within the map at the same time.

This kind of problem is hard, because of the chicken-and-egg problem: In order to get a good localization, you need a map. In order to create a map, you need to localize the agent.

It can be applied to:

- Indoors: Vacuum cleaner robots
- Outdoors: Self-driving cars
- Underground: Exploration of mines

## SLAM algorithm parts

### Motion model

A motion model gives the state \(x\) at time \(k\) after having the state at time \(k-1\) and the control \(u\) at time \(k\):

### Observation model

The observation model gives the observation \(z\) at time \(k\), given the map \(m\) and the state \(x\) at time \(k\):

See odometry.

### Map Representations

Maps can either simply be topological or be metric. The first one means distances don't matter, only the ordering / number of branches.

### Data Association

Data association means that we want to identify landmarks. The two-frame matching problem is called (Correspondence Problem).

## SLAM algorithms

- Graph SLAM
- EKF-SLAM (Extended Kalman filter)
- Fast SLAM: Rao-Blackwellised particle filters
- Mono SLAM
- Topological SLAM

### EKF-SLAM

Components:

- The state vector \(x \in \mathbb{R}^{n}\) contains the position of the agent (for example: x, y, orientation) as well as all landmarks (for example: \(l_{1,x}, l_{1,y}, l_{2,x}, l_{2,y}\)).
- A covariance matrix \(C \in \mathbb{R}^{n \times n}\)

Pseudocode:

```
def filter_step(x, m):
"""
Parameters
----------
x : ndarray
State vector, including landmark positions
shape: n
C : ndarray
Covariance matrix
spahe: n x n
"""
x_pred = predict_state(x) # odometry
z_pred = predict_measurement(x)
z = measure()
# data association
# Kalman filter update
# Integration of new landmarks by extending x and C
```

Complexity:

- Cost per step: \(O(n^2)\) where \(n\) is the number of landmarks
- Total cost to build a map: O(n^3)
- Memory consumption: O(n^2)

## See also

Other blogposts: * Kalman Filter

Papers and Slides:
* Uni Freiburg: Slides and YouTube playlist
* Hugh Durrant-Whyte, Tim Bailey: Simultaneous Localisation and Mapping (SLAM): Part I The Essential Algorithms
* Ziegler et. al: Making Bertha Drive — An Autonomous Journey on a Historic Route
* Grisetti, Kummerle, Stachniss, Burgard: A Tutorial on Graph-Based SLAM

Datasets: * Victoria Park

Software: * Mark Paskin: Stanford

Stack Exchange:
* Robotics
* Stack Overflow
* A.I.

Other: * Wikipedia