• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

SLAM

Contents

  • SLAM algorithm parts
    • Motion model
    • Observation model
    • Map Representations
    • Data Association
  • SLAM algorithms
    • EKF-SLAM
  • See also
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)

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

Published

Mär 26, 2018
by Martin Thoma

Category

Machine Learning

Tags

  • Artificial Intelligence 2
  • Robotics 1

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor