第5卷第6期 智能系统学报 Vol.5 No.6 2010年12月 CAAI Transactions on Intelligent Systems Dec.2010 doi:10.3969/i.i8sn.1673-4785.2010.06.004 广义证据推理融合结构 黄心汉，李鹏，王敏 (华中科技大学控制科学与工程系，湖北武汉430074) 摘要：针对Dempster--Shafer理论(DST)及Dezert-Smarandache理论(DSmT)难以处理不确定信息的问题，定义了辨 识框架中的不确定因子，提出了2种自适应通用分配法则(AUPR).并提出了证据理论的广义融合框架，并在此基础 上构建了广义证据推理机.以Pioneer2-DXe机器人为实验平台，绘制了实验场景的信度分布图.实验结果验证了所 提方法的有效性和实用性，为构建统一的信息融合框架提供了有力的依据。 关键词：证据推理；融合框架；地图构建；信息融合 中图分类号：TP242.6文献标志码：A文章编号：16734785(2010)060487-05 General evidence reasoning fusion structure HUANG Xin-han,LI Peng,WANG Min Dept.of Control Science Engineering,Huazhong University of Science and Technology,Wuhan 430074,China) Abstract:In order to solve the problem of the Dempster-Shafer theory (DST)and Dezert-Smarandache theory (DSmT)both being unable to deal with uncertain information,the uncertainty mass in the frame was defined and two kinds of adaptive universal proportional redistribution rules (AUPR)were proposed.Next,a general evidence reasoning fusion structure was proposed based on the general evidence with which the reasoning machine was built. Lastly,the pioneer 2-DXe mobile robot was used to build the belief distribution maps of various environments.The experimental results verify the validity and the practicality of the proposed methods.They also supply powerful theo- retical evidence for constructing a uniform information fusion frame. Keywords:evidence reasoning;fusion frame;map building;information fusion 证据推理是信息融合的重要理论基础，但从证首先提出了证据理论，他的学生G.Shafer随后进一 据理论诞生至今，尚未出现一个统一的融合框架，这 步将其发展成为一种不精确推理理论，即Dempter- 与证据理论的应用特殊性有关，因为随着证据源的 Shafer证据理论(DST)I山.该理论以数字化的证据 增加，其计算复杂度也急剧增加，这使得应用难度加 支持度处理证据的权重，主要致力于证据的组合.经 大，因此为了简化计算，通常都是具体问题具体对 由几十年的发展及研究，DST证据理论的应用性得 待，没有统一的处理方法，这也使得证据理论的应用 到了广泛的证实，使得该理论获得了众多学者的认 与推广难度加大.因此，研究和提出统一的证据推理 可，成为一种经典的信息融合理论 框架有助于标准化证据推理，使其能够得到更为广 Dezert和Smarandache于2002年提出了DSmT 泛应用 (Dezert--Smarandache theory)2],它是在DST的基础 1证据理论简介 上发展而来的，是DST和贝叶斯理论的扩展，其描 述和处理融合问题的范围和能力远远强于DST,克 1.1DST和DSmT 服了DST难以解决证据冲突问题的固有缺陷，具有 Dempster在贝叶斯概率论的基础上，在1967年 广阔的应用前景。 1.2冲突因子与不确定因子 收稿日期：2010-04-21. 基金项目：国家自然科学基金资助项目(60675028). 在DST和DSmT中冲突因子3)都被定义为 通信作者：黄心汉.E-mail:xhhuang(@mail.hust.ed加.cn
·488· 智能系统学报 第5卷 子的信度赋值；c2(X)是与X相关的信度赋值之和； h1,2= mi(X;) c2（X)=m1(X)+m2（X)+…+m,(X)≠0； 1nn…n,=中 但DST和DSmT都未定义并集焦元，在许多情况下 42(Xu)为全局不确定因子；f2是与不确定因子相 关的信度赋值之和.L(X)为不确定因子阈值函数， 并集焦元通常描述的都是不确定的信息，因此将并 其作用是根据当前证据自动找出阈值并判断是否分 集焦元定义为不确定因子： 配不确定因子，表达式如下： 41.2=∑ Πm,(X). L(X)= X1,X2,…,X,eD8玉 X1UX2U…UX,=g r1,山2，（X)≤min[m12(X),…,m2,(X,)]; 1.3自适应通用分配法则 0,u12,(X)≥max[m12,（X1）,…,m2,（X,）]. 信息融合的目的是消除信息的冲突与不确定， (2) 使原本不精确、不确定甚至高冲突的信息变得清晰 AUPR2自适应通用分配法则2是按合取一 明了.在信息融合的过程中，常常会产生冲突因子和 致形式的比例将局部不确定因子分配到与其相关的 不确定因子冲突因子可以根据PCR法则45]将其 元素上.对于s≥2个证据源时，H(X≠0)∈G, 消除，但不确定因子却没有相应的消除法则.而在很 AUPR2的计算公式为 多情况下，不确定因子与冲突因子一样也需要消除 TLAUPR2(X)=mpcR(X)+m2,（X)· 掉，如何处理不确定因子也是非常重要的问题， 为了使融合结果更具有确定性意义，提出了一 (∑UA2(X,k)). (3) 种自适应通用分配法则AUPR(adaptive universal 式中：L(X)与式(2)相同，UAu0(X,k)表达式如 proportional redistribution rule),使得信息融合过程 下： 中可以视具体情况同时将冲突因子和不确定因子分 UAUP(X,k)= 配到其他非空的确定性集合上，从而达到加强确定 m2,(XUXU…UX&) 性命题的目的. X1,…,XeG8/月x 在DSmT框架下，考虑到分配精度和实时性的要 mp(X)+∑ma,(X) {1,…,gleP 求，提出了一种基于PCR的自适应通用分配法则，根 X1nX2■x 据应用需要设定一阈值，当不确定因子大于该阈值 2 广义证据推理结构 时，说明不确定信度值太高，当前证据已无法将其消 除，只能等待进一步的证据收集；当不确定因子小于 2.1证据推理机的基本框架 阈值时，表明该因子是可消除的，则采用通用分配法 Shafer于1976年提出了著名的DS证据理论之 则将冲突因子和不确定因子一起分配到其他焦元上. 后，许多研究人员也相继根据DS理论提出了一些 AUPR分为2种分配方式，一种是在分配冲突 相应的证据理论，以解决DS证据理论所无法处理 因子的同时一起分配不确定因子，称之为AUPR1; 的高冲突问题.但迄今为止，仍然没有一个统一的融 另一种是在计算出合取形式后，根据合取形式的相 合结构 对比例分配不确定因子，称之为AUPR2.下面给出2 综合过去的各类证据推理方法，大致可以将证 种分配方式的表达式 据推理划分为4个层面：证据源层、信度分配层、信 AUPR1自适应通用分配法则1在分配全局 度融合层以及决策层.而这些理论通常都是基于等 不确定因子时只涉及到相关的冲突量而不是所有非 可靠信息源的，当信息源是非等可靠的且其不可靠 空集合，并按照所对应的信度矩阵的非空列的比例 程度是已知的，就可以将获取到的证据加以特殊处 将其分配到所有非空集合上.对于s≥2个证据源 理，如Shafer提出的折扣理论.因此，可以将信度校 时，H(X≠0)∈G°，AUPR1的计算公式为 正作为一个新的层次加入到证据推理的结构中去， mAUPRI (X)=mPCRs (X)+ 其位置在信度分配层与信度融合层之间.证据推理 c2（X2.L(X)·hn(Xu). 机(evidence reasoning machine,ERM)的基本框架如 (1) fi2, 图1所示[61.信度融合层可以采用各种不同的证据 式中：mpCR(X)是由PCR规则融合得出的无冲突因 理论，如DST或DSmT等
第6期 黄心汉，等：广义证据推理融合结构 489· 决策层 据推理机(general evidence reasoning machine, 4 GERM)如图2所示. 在信度分配层，F(S)为信度赋值函数，通过信 信度触合层 度分配函数之后便成为了原始的基本信度赋值 0(·).对于2焦元的辨识框架，通过交运算和并运 信度校正层 算获取的基本信度赋值只有4种.在信度校正层中， 没有采用Shafer的折扣方法，取而代之的是人工神 信度分配层 经网络方法.因为在大多数情况下，非等可靠证据源 的折扣信息是无法得知的，即使能够获取其折扣值， 原始证据 但由于各种条件所限，往往也会呈现出非线性状态， 而折扣方法却是线性的，而且一旦确定就无法改变， 图1证据推理机的基本框架 这使得其应用价值大大降低.而神经网络方法则更 Fig.1 The basic frame of evidence reasoning machine 为灵活通用，它可以根据先验知识拟合非线性的折 2.2基于DSmT的广义证据推理机 扣值，因此可以适应不同的条件，比Shafer的折扣方 文献[6]中提出了基于DSmT的广义证据推理 法更为精确地描述非线性的打折情况.m(·)即为 机，但其不能分配不确定因子，为此对其加以改进， 通过神经网络校正之后的基本信度赋值 使其更具普适性.基于DSmT的二元素改进广义证 0.(0n0, m,0∩0) 0.(0Ua mws(0,∩0，) P{0,n82 m,(6,U6) ANN FRM 0.0) M0,) gE) ma(0U0)》 0,U0D O8) (,0) 8 ! ms(0) P0) O,(8,n8 m,0∩6) ☒ ☒ 0Ue m,(0,U0) F(S ANN & O0) M0) g() mo(e) P{0,} O,(0) m,(8) 原始 信度分配层 !信度 证据 校正层 信度融合层 决策层 图2基于DSmT的广义证据推理机 Fig.2 DSmT based generalized evidence reasoning machine 图2中FRM(factor redistribution machine)是因 tc转换来计算元素的发生概率，但通常情况下不需 子分配器信度校正层⑧是乘法算子，g(Σ)是激励 要这个扩展层. 函数，对于DSmT而言，激励函数就是比较简单的求 对于整个推理机而言，只有2个证据源输入口， 和算子，也可以采用其他证据理论的算法如DST(若 但其能够处理任意V≥2个证据源的情况.假定有 采用DST,则激励函数就相对DSmT复杂一些，包含 一组含有n个证据源的有限集{X,X2,…,Xn},现 了除法运算).mMa(·)融合后的结果.FRM是因 将这个有限集依次送入推理机，即X,和X2作为初 子分配器，冲突因子和不确定因子通过分配器被重 始的S,和S2,在第1轮融合周期结束后，由X,和 新分配到mw(e)(0,)和mMo)(02)上，如果冲突因子 或不确定因子不需分配，则可直接通过分配器成为 X,2个证据源融合得到结果mM(e)(·)不是最终的 mw()(0∩0，)和mwe)(0U02).分配器中的算法 结果，而是一个中间结果，因此m4()(·)又重新变 可以采用自适应通用分配法则(AUPR),也可采用 为m(·),与新进人推理机的证据源3进行融合， 其他方法，如只需分配冲突因子时，就可只采用 此时X3与上一轮结果mMe(·)分别成为了新 PCR法则 轮融合的S,和S2,只不过me(·)是直接进人信 最后的决策层是一个扩展层，采用广义Pignis- 度融合层而无需再通过信度分配和信度校正层(X
·490· 智能系统学报 第5卷 需通过这2层).X3与mw(e)（·)通过第2轮融合 GREM的信度融合层的算法可以采用贝叶斯概 后又可获得一个新的中间融合结果mM)(·),接 率法、DST或DSmT等.考虑到DSmT算法的优越 下来mM()(·)与X4又进入第3轮融合周期.如此 性，采用其作为GEM的融合算法.由于融合过程 循环，直至所有的原始证据源都进入推理机.当最后 中会产生冲突因子和不确定因子，因此需采用AU 一个证据源X,进入推理机并获得了一个融合结果 PR方法来分配因子.虽然不确定因子对地图精确性 mM(9)(·),倘若没有更新的证据送入推理机，则 的影响不如冲突因子大，但微小的不确定因子是完 mM(e)(·)便是最终融合结果了.当获取到最终结 全可以消除的，因此也可以采用基于PCR2的AU- 果后，如果需要则可让其进入到决策层 PR1法则(AUPR1计算复杂度要小于AURP2),即 在2个元素01和02的情况下，广义证据推理 PCR2-AUPR1算法， 机包含了经典DSm模型和混合DSm模型，约束条 件的附加是在信度分配层进行的，即F(S)函数.无 约束条件则为经典DSm模型，若F(S)中有附加的 约束项，则变为了混合DSm模型，若元素个数大于 2,则信度分配层和信度融合层就变得更为复杂，其 (0,0.0°）】 复杂度增长速度非常惊人，不过大多数情况下2个 000 元素已经足够，因为任何问题都可以分解为“是”或 “否”这个元素 这个广义证据推理机同样也适用于DST理论 框架下的各种证据理论.在信度分配层，信度赋值函 4840mm 数将冲突分量的系数置为0，则整个推理机就工作 图3实验环境及机器人初始位置 在Shafer模型下了.之后信度融合层的激励函数 Fig.3 Experiment environment and original position of robot g(Σ)也需修改为DST的融合法则.对于其他的证 分别进行2组探测未知环境的实验，第1组采用 据理论而言情况也相差无几，只需修改信度赋值函 经典DST的方法，第2组采用PCR2-AUPR1方法 数和激励函数的融合算法就可以了. 实验结果如图4和图5所示.图4为2种算法 广义推理机不仅适用于定量信息融合，同样也 得到的不确定区域，灰度值越大表示不确定的信度 适用于定性信息融合以及混合信息融合，只需采用 值越大，即表明该区域的信息不足不明，无法得知. 相应的融合算法即可， 图5为2种算法计算出的最终信度分布图，灰度值 3实验结果及分析 越大表示该区域被占用的可能性越大， 实验采用Pioneer2-DXe移动机器人，机器人本 体上装有16个声呐，对声呐的建模见文献[7].建 立4840mm×3100mm的房间地图，实验环境和机 器人初始位置如图3所示，进行构建环境地图实验。 设定机器人的初始位置为地图的坐标原点，初始位 姿为(0,0,0). 采用提出的GREM作为融合框架，在GREM中 (a)DST算法得到的不确定区域 有信度校正层.由于每个声呐都是一个独立的证据 源，因此必须对每个声呐都进行信度校正，而校正所 用的折扣值则由神经网络训练得到.出于对速度和 复杂度的需求，采用了最为简单但很有效的3层BP 网络，训练函数采用较快的LM(levenberg-mar quardt)算法，激励函数采用Sigmoid函数.功能函数 采用SSE(sum squared error).学习速率设定为0.1， 最终误差设定为0.001.为了使计算更为精确，将输 (b)PCR2-AUPR1算法得到取的不确定区域 入输出值都放大1000倍.每个声呐都需要训练一 图4不确定区域比较 个BP网络，因此一共需要训练16个网络 Fig.4 The comparison of uncertainty area
第6期 黄心汉，等：广义证据推理融合结构 491. 参考文献： [1]SHAFER G.A mathematical theory of evidence[M].Prin- ceton,USA:Princeton University Press,1976:1-100. [2]DEZERT J.Foundations for a new theory of plausible and paradoxical reasoning[J].Information and Security,2002, 9:1357 [3]SMARANDACHE F,DEZERT J.Advances and applica- tions of DSmT for information fusion[M].Rehoboth,USA: (a)DST算法实验结果 American Research Press,2004:3-31. [4]SMARANDACHE F,DEZERT J.Advances and applica- tions of DSmT for information fusion[M].Rehoboth.USA: American Research Press,2006:47-49. [5 SMARANDACHE F,DEZERT J.Advances and applica- tions of DSmT for information fusion[M].Rehoboth,USA: American Research Press,2009:137-160. [6]HUANG Xinhan,LI Peng,WANG Min.Evidence reason- ing machine based on DSmT for mobile robot mapping in un- known dynamic environment[C]//2009 IEEE Interational (b)PCR2-AUPR1算法实验结果 Conference on Robotics and Biomimetics.Guilin,China: 图5最终实验结果比较 2009:753-758. Fig.5 The comparison of final experiment results [7]李鹏，黄心汉，王敏.基于混合DSm模型的移动机器人动 由实验结果可以看出，DST存在固有的融合缺 态环境地图构建[J刀.机器人，2009,31(1)：4046,52. 陷，它无法处理高冲突信息，在处理高冲突信息时往 LI Peng,HUANG Xinhan,WANG Min.Hybrid-DSm-mod- 往得出反人类直觉的结果，占地面积小的障碍物往 el-based mobile robot map building in dynamic environment 往会被该区域所覆盖而被标记为空，其描绘出的最 [J].Robotics,2009,31(1):40-46,52. 终地图实际上是整个场景的外部轮廓，而且DST所 作者简介： 计算出的不确定信度分布图也与实际场景不符，已 黄心汉，男，1946年生，教授，博士生 被机器人探测过的部分仍然有不确定因子存在（即 导师.主要研究方向为智能控制、智能机 器人、多传感器集成与信息融合等.曾任 图4(a)中散布的黑斑)，而且信度值都很低，表明了 国家“863”计划智能机器人主题控制专题 融合的不完善；实际上被探测过的部分已经获取到 专家组成员.现任中国人工智能学会常务 了充分证据，这些不确定因子完全可以消除掉. 理事、智能机器人专业委员会主任等职 与DST相比，PCR2-AUPR1方法能很好地分配 发表学术论文300余篇. 冲突因子和不确定因子，消除了信度值很低的不确 定因子，使得不确定因子信度分布图的解释更加合 李鹏，男，1981年生，博士研究 理，因此所绘制的最终地图则更为接近真实环境. 生.主要研究方向为信息融合、机器人 地图创建与定位、多机器人系统.发表 4结束语 学术论文10余篇， 本文在DSmT框架下定义了不确定因子，提出 了2种自适应通用分配法则，使得证据推理过程中 产生的低信度不确定焦元得到了合理的分配和解 王敏，女，1954年生，教授.主要 释.同时提出了基于证据理论的统一融合框架，构造 研究方向为图像处理与模式识别技术、 了广义证据推理机.最后以移动机器人为实验平台 机器人视觉与传感技术、智能控制与神 进行了2组实验，分别构造了未知环境的不确定因 经元网络原理及应用等.现任中国人工 子信度分布图和最终信度分布图.实验结果表明本 智能学会理事、智能机器人专业委员会 文提出的AUPR方法和广义证据推理机能有效地处 秘书长等职.发表学术论文80余篇，出 理高冲突和不确定信息，能更精确合理地反映真实 版教材3部. 环境地图，是一种先进的证据推理融合结构
