SLAM

This is an article I had for quite a while as a draft. As part of my yearly cleanup, I've published it without finishing it. It might not be finished or have other problems.

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)

SLAM algorithm parts

Motion model

Observation model

Map Representations

Data Association

SLAM algorithms

EKF-SLAM

See also

Published

Category

Tags

Contact