Robot Mapping

Table of Contents

1 Robot Mapping简介

Mapping就是从获取的数据中构建地图。

2 Robot Mapping算法

2.1 Occupancy Grid Mapping (Mapping With Know Poses)

用Occupancy grid mapping算法构建地图,就是计算下面概率:
\[p(m \mid z_{1:t}, x_{1:t})\]

其中, \(m\) 是地图, \(z_{1:t}\) 是测量值, \(x_{1:t}\) 是机器人的路径,即一系列位置。由于假设机器人的位置是已知的,所以控制量 \(u_{1:t}\) 就没必要作为已知条件了。

Occupancy grid mapping算法把地图分解为有限的很多网格单元(grid cells),即:
\[m = \sum_i m_i\]

每一个网格单元看作是一个二值(即“已被占据”或“未被占据”)的随机变量,用 \(p(m_i = 1)\) 或者 \(p(m_i)\) 来表示网格单元被物体占据的概率。

要直接计算 \(p(m \mid z_{1:t}, x_{1:t})\) 基本上是不可行的,因为它的维度太大,假设有10000个网格单元,则可能的地图有 \(2^{10000}\) 个。Occupancy grid mapping的作法是把各个网格单元看作是相互独立的(各个网格单元相互独立的假设其实并不成立,这是为了简化计算而做的妥协),这样概率 \(p(m \mid z_{1:t}, x_{1:t})\) 可分解为:
\[p(m \mid z_{1:t}, x_{1:t}) = \prod_i p(m_i \mid z_{1:t}, x_{1:t})\]

这样,我们可以用“Binary Bayes Filter”对每个网格单元是否被占据进行概率估计了。

对每个网格单元应用“Binary Bayes Filter”算法可得Occupancy grid mapping算法,如图 1 所示。

robot_mapping_occupancy_grid.png

Figure 1: Occupancy Grid Mapping, a version of the Binary Bayes Filter

上面算法中 \(l_{t,i} = \log \frac{p(m_i \mid z_{1:t}, x_{1:t})}{1 - p(m_i \mid z_{1:t}, x_{1:t})}\) , \(l_0 = \log \frac{p(m_i = 1)}{p(m_i = 0)} \ = \log \frac{p(m_i)}{1 - p(m_i)}\) , \(\mathrm{inverse\_sensor\_model}(m_i, x_t, z_t) = \log \frac{p(m_i \mid z_t, x_t)}{1 - p(m_i \mid z_t, x_t)}\)

说明:Occupancy Grid Mapping有两个假设:(1) 机器人位置已知;(2) 网格单元是否被占据是相互独立的。

参考:
Probabilistic Robotics, by Sebastian Thrun, 9.2 The Occupancy Grid Mapping Algorithm
http://ais.informatik.uni-freiburg.de/teaching/ss15/robotics/slides/12-occupancy-mapping.pdf

2.2 Simple Counting

还有一种简单的办法来估计网格单元是否被物体占据:计数法(Simple Counting)。
基本思路是按下面方法分析传感器返回的数据:
For every cell count
hits(x,y): number of cases where a beam ended at <x,y>
misses(x,y): number of cases where a beam passed through <x,y>
\[Bel(m^{[xy]}) = \frac{\text{hits}(x,y)}{\text{hits}(x,y) + \text{misses}(x,y)}\]

参考:
http://ais.informatik.uni-freiburg.de/teaching/ss15/robotics/slides/12-occupancy-mapping.pdf
http://cmp.felk.cvut.cz/~hlavac/TeachPresEn/55IntelligentRobotics/110WorldMap.pdf


Author: cig01

Created: <2016-06-24 Fri 00:00>

Last updated: <2018-02-10 Sat 18:48>

Creator: Emacs 25.3.1 (Org mode 9.1.4)