【感知算法】Dempster-Shafer理论

具体阐述了问题：智能驾驶系统地图数据更新面临挑战，在群体协作（众包）机制下如何通过多批次、不完全一致的数据信息综合处理实现关键要素定位与优化配置？其中，在p次观测中新增了一处标牌标识，在q次无明显观察的情况下，请问应如何评估数据可靠性并据此推算出现的概率？
探讨了一种传统算法：以纪念两位奠定理论基础的关键研究者。

Dempster-Shafer理论

首先抽象一般问题，即推断、论断等问题的建模。

基本概念：mass belief plausibility

这些基本概念显得较为抽象。然而通过结合自动驾驶地图众包更新问题进行分析时，则会变得清晰明了。为了方便后续查阅，请先记下：

一般而言，在本文中将判断定义为各种状态（如"无禁停标志"、"有……"等），这些状态相互矛盾。
每个判断可信程度可表示为一区间（由plausibility\belief界定），满足条件belief < plausibility。
每个判断的质量（mass）代表其对应证据的支持程度（即各个判断子集的整体证据量），但质量值无法直接用于计算单个判断或其中任意部分的支持程度。
某个判断的支持度（belief）即包含该假设的所有判断子集的质量总和，反映证据对这一判断的支持强度。
某假设的可能性上限（plausibility）等于两种情况之一：

1. 1减去所有与该假设交集为空的判断子集的质量总和；
2. 或者所有与该假设交集不为空的判断子集的质量总和，
   这表示该假设成立的可能性上限即为此值。

pl(p) = 1- bel(\sim p)

定义

X 被定义为所有可能状态的集合。其超集构成集合族 2^X。
数学上，

X = \{a, b\}, \quad 2^X = \{\{a\}, \{b\}, \emptyset, \{a, b\}\}

为了量化不确定性，在信任理论中引入信任度函数 m: 2^X \rightarrow [0,1]：

• 满足边界条件：

  m(\emptyset) = 0

以及归一化条件：

\sum_{A \in 2^X} m(A) = 1

基于此定义的信任度范围满足：

bel(A) \leq P(A) \leq pl(A)

其中，

bel(A) = \sum_{B|B\subseteq A} m(B)

而置信上限由下式给出：

pl(A) = \sum_{B|B\cap A\neq\emptyset} m(B)

在后续研究中将此理论应用于自动驾驶地图众包更新问题中，并通过实践能够更好地理解和掌握这些抽象的数学。

现在尝试把DS理论应用到自动驾驶地图众包更新。

地图特征变化判断

A mass function is used to measure the existence evidence.
Existence states include: existent, nonexistent, tentative, and conflict.
Mathematical expressions are represented as: \exist, \not\exist, \Omega, and \phi.
The mass function is used to measure the existence evidence.

mass functions of the measurement

mass_{z_t}( \exist ) = \lambda \\ mass_{z_t}( \not \exist ) = 0 \\ mass_{z_t}( \phi ) = 0 \\ mass_{z_t}( \Omega ) = 1-\lambda

• mass functions of the non-measurement

mass_{z_t}( \exist ) = 0 \\ mass_{z_t}( \not \exist ) = \lambda \\ mass_{z_t}( \phi ) = 0 \\ mass_{z_t}( \Omega ) = 1-\lambda

Derivation of the existence of map features under the Dempster Combination Rule

概率质量函数和新增的概率质量函数初始化为第i个地图特征作为先验置信度λ_HD。

测度mass_{{H D_{{{{{\{ i }\}}} }}}}在不存在时等于\lambda_{{H D}}}，
测度mass_{{H D_{{{{{\{ i }\}}} }}}}在存在与否时等于零，
测度mass_{{H D_{{{{{\{ i }\}}} }}}}在空集上等于零，
测度mass_{{H D_{{{{{\{ i }\}}} }}}}在全集上等于 1-\lambda_{{H D}}}。

该地图特征的质量参数通过下述公式进行初始化设置：

mass_{new,j}(\exist) = 0 \\ mass_{new,j}(\not{\exist}) = 0 \\ mass_{new,j}(\phi) = 0 \\ mass_{new,j}(\Omega) = 1

其中，在存在状态、不存在状态以及空集状态下质量参数的初始值均设为零；唯一例外的是全集状态下的质量参数被设定为一。

The Dempster–Shafer combination rule, denoted by \oplus, is utilized to aggregate the existence of measurements, represented as mass_{z_t}, across each map feature at time t-1.

mass_{HD_{t\{i\}}} = mass_{HD_{t-1\{i\}}}\oplus mass_{z_t} \\ mass_{new_{t\{j\}}} = mass_{new_{t-1\{j\}}}\oplus mass_{z_t}

其中，
mass_{1\oplus2}(\phi) = 0 \\ mass_{1\oplus2}(A) = \frac{mass_{1\cap2}(A)}{1-mass_{1\cap2}(\phi)}, \forall A\subseteq\Omega,A\neq\phi \\ \forall A\subseteq\Omega, mass_{1\cap2}(A) = \sum_{B\cap C=A|B,C\subseteq\Omega}mass_1(B)mass_2(C)
注：公式mass_{1⊕2}(A)即mass_1(A)⊕mass_2(A)
求和条件中的|表示并列关系而非逻辑或，并集运算符∪对应于逻辑或∨；这里Ω为超集2^X的子集族族族族族族族族族族族族族族族；它与上文中的状态含义不同。
\exists ∩ \exists = \exists\\ \exists ∩ Ω = \exists\\ \exists ∩ ¬∃ = ∅ \\ ∅ ∩ 存在 = ∅ \\ ∅ ∩ ¬存在 = ∅ \\ 不存在 Ω = 不存在 \\ 不存在 不存在 = 不存在 \\
集合运算满足交换律。