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

SLAM

Contents

  • SLAM
    • 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