Robot Localization

Table of Contents

1 Robot Localization简介

Robot Localization是指在已知的地图中,确定Robot的位置,所以Localization又称为Position Estimation或者Position Tracking.

基本上,所有基于概率的 Robot Localization算法都源于Bayes Filter或其变种。

注:Bayes Filter是通用的状态估计方法,除用于估计定位外,还可以估计其它状态。

Bayes Filter的基本递推式如下:
\[{\color{red}{bel(x_t)}} = \eta \, p(z_t \mid x_t) \int p(x_t \mid x_{t-1}, u_t) {\color{red}{bel(x_{t-1})}} \, \mathrm{d} x_{t-1}\]

Probabilistic Robotics, by Sebastian Thrun, Chapter 7 Mobile Robot Localization: Markov and Gaussian
Probabilistic Robotics, by Sebastian Thrun, Chapter 8 Mobile Robot Localization: Grid And Monte Carlo

1.1 Local VS. Global Localization

There are two types of localization: local and global.

  • Local techniques aim at compensating odometric errors during robot navigation. They require that the initial location of the robot is approximately known and they typically cannot recover if they lose track of the robot’s position.
  • Global techniques can localize a robot without any prior knowledge about its position, i.e., they can handle the kidnapped robot problem, in which a robot is kidnapped and carried to some unknown location.

2 Robot Localization算法

2.1 Markov Localization

Markov Localization算法直接基于Bayes Filter算法。在定位问题中,地图(常用 \(m\) 表示)是已知输入,故可得到Markov Localization算法的框架如图 1 所示。


Figure 1: Markov Localization

2.2 EKF Localization

Markov Localization使用概率分布 \(bel(x_t)\) 来表达位置的估计,这很通用,但却很低效。 EKF Localization不用概率分布,而使用均值 \(\mu_t\) 和协方差 \(\sum_t\) 来表示位置的估计,而且地图中需要有路标(Landmark)。 EKF Localization算法如图 2 所示。

EKF Localization算法只能用来线性高斯系统(即其Motion model和Measurement model都必须是线性的,噪声必须是高斯噪声)。


Figure 2: EKF Localization

说明1:上面算法中,第8-22行是EKF的“Measurement Update”过程。外层的for循环是根据 \(t\) 时刻每一个feature的观察值进行相应更新,内层的for循环加上第16行是用最大似然估计法求解correspondence variable(这个变量标记feature观察值和地图中feature的关系)。
说明2:关于上面EKF Localization算法中所使用的Motion model和Measurement model,以及EKF Localization的推导请参考:Probabilistic Robotics, by Sebastian Thrun, 7.4 EKF Localization, 7.5 Estimating Correspondences

2.3 Grid Localization

Grid Localization使用Histogram Filter(离散Bayes Filter应用于连续状态空间时就称为Histogram Filter)来对机器人位置进行估计。Grid Localization算法如图 3 所示。


Figure 3: Grid Localization, a variant of the discrete Bayes filter

2.4 Monte Carlo Localization (MCL)

Monte Carlo Localization使用Particle Filter对机器人位置进行估计。Grid Localization算法如图 4 所示。


Figure 4: MCL, or Monte Carlo Localization, a localization algorithm based on particle filter

我们知道,Particle Filter中权重小的粒子在重抽样时可能消失(称为Particle Deprivation Problem)。这可以导致MCL不能工作,一种解决办法是加入一些随机粒子,这种思路应用到MCL算法中称为Augmented_MCL算法,如图 5 所示。


Figure 5: An adaptive variant of MCL that adds random samples

另外一个MCL算法的改进变种是不固定粒子数,让粒子数量可变。称为 KLD-sampling 算法,如图 6 所示。


Figure 6: KLD-sampling MCL with adaptive sample set size

Author: cig01

Created: <2016-06-19 Sun 00:00>

Last updated: <2016-08-10 Wed 23:44>

Creator: Emacs 25.1.1 (Org mode 9.0.7)