SLAM

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

$$x_k = f(x_{k-1}, u_k)$$

Observation model

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

$$z_k = h(x_k, m)$$

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