﻿ 果蝇算法和改进D-S证据理论的四轴飞行器障碍辨识
«上一篇
 文章快速检索 高级检索

 智能系统学报  2020, Vol. 15 Issue (3): 499-506  DOI: 10.11992/tis.201809011 0

### 引用本文

XU Yaosong, WANG Chuanwei. FOA and improved D-S evidence theory for quadcopter obstacle identification[J]. CAAI Transactions on Intelligent Systems, 2020, 15(3): 499-506. DOI: 10.11992/tis.201809011.

### 文章历史

FOA and improved D-S evidence theory for quadcopter obstacle identification
XU Yaosong , WANG Chuanwei
College of Electrical and Control Engineering, Liaoning Technical University, Huludao 125105, China
Abstract: Aiming at the problem that the quadrilateral aircraft has poor recognition effect and low precision, we studied the method of quadcopter obstacle recognition using a multisensor based on an ultrasonic sensor, infrared ranging sensor, and lidar sensor. The original data evidence weight of the sensor was optimized using the fruit-fly optimization algorithm (FOA) to obtain the optimal weight. According to the optimal weight of each sensor, an improved D-S evidence theory algorithm was used to fuse the data of multiple sensors to improve the obstacle recognition accuracy of the quadcopter. By comparing the single sensor and other data fusion algorithms, the research results show that under the same condition, the proposed method has a higher recognition accuracy for obstacles and faster response to obstacles.
Key words: quadcopter    obstacle avoidance    ultrasonic sensor    infrared distance sensor    lidar sensor    multisensor information fusion    FOA    D-S evidence theory

1 D-S证据理论

D-S证据理论[15]是由Dempster在1967年提出，并由Shafer进一步发展起来的一种具有不确定推理模型理论。被广泛地应用于处理各种不确定信息的数据融合算法。其优点是可以将大量的不同性质的主观不确定信息，通过D-S证据理论转变为确定性的决策信息。在四轴飞行器进行障碍物辨识的过程中，由于存在大量的干扰因素，以至于传感器得到的数据不准确，主观不确定性比较高，采用多种传感器对障碍物数据进行获取可以有效提高其准确性，而D-S证据理论是融合这类数据信息的有效途径之一[16-18]

1.1 基本概念

D-S证据理论使用集合的方式表示命题，把问题涉及到的所有可能取值定义为N个详细和具有排他性非空假设的一个非空集合 $\theta$ ，称为样本空间或者识别框架。 ${{\rm{2}}^\theta }$ $\theta$ 所有子集组成的集合。

1)基本概率赋值函数(BPA)

 $\left\{ {\begin{array}{*{20}{c}} {m\left( \text{Ø} \right) = {\rm{0}}\;\;\;\;} \\ {\displaystyle\sum\limits_{A \in \theta } {m\left( A \right) = {\rm{1}}} } \end{array}} \right.$ (1)

$m\left( A \right)$ 为基本赋值函数，其中， $\text{Ø}$ 为空集，如果 $m\left( A \right) > {\rm{0}}$ $A$ 称之为焦元， $m\left( A \right)$ 的作用是对命题的可信度进行分配， $m\left( A \right)$ 反映了证据对集合 $\theta$ 中命题 $A$ 支持程度。

2)信任函数(BEL)

 ${\rm{BEL}}\left( A \right) = \sum\limits_{B \subseteq A} {m\left( B \right)} ,\forall A \in {{\rm{2}}^\theta }$ (2)

3)似真函数(PL)

 ${\rm{PL}}\left( {{A}} \right) = {\rm{1}} - {\rm{BEL}}\left( {\overline A } \right) = \sum\limits_{B \cap A\phi } {m\left( B \right)}$ (3)

1.2 D-S证据理论组合规则

 $m\left( A \right) = \left\{ {\begin{array}{*{20}{l}} {{\rm{0}},} \quad {A = \text{Ø} } \\ {\dfrac{{\rm{1}}}{{{\rm{1}} - K}},} \quad {A \ne \text{Ø} } \end{array}} \right.$ (4)

1.3 D-S证据理论证据冲突问题

m1m2是相同识别框架 ${{\rm{2}}^\theta }$ 上的2个相互独立的基本概率赋值，焦元分别是 ${A_{\rm{1}}}, {A_{\rm{2}}},\cdots ,{A_k}$ ${B_{\rm{1}}},{B_{\rm{2}}} ,\cdots, {B_k}$ ，又设：

 $K = \sum\limits_{{A_i} \cap {B_j} = \phi } {{m_{{\rm{1}}}\left( {{A_i}} \right)}{m_{\rm{2}}}\left( {{B_j}} \right)} < {\rm{1}}$ (5)

 $m\left( C \right) = \left\{{\begin{array}{{l}} {\displaystyle\sum\limits_{{A_i} \cap {B_j} = C} {{m_{\rm{1}}}\left( {{A_i}} \right){m_{\rm{2}}}\left( {{B_j}} \right)} ,\quad}{\forall C \in \theta {\text{且}}C \ne \text{Ø} } \\ {{\rm{0}},\quad}{C = \text{Ø} } \end{array} } \right.$ (6)

1.4 证据权

$K \to {\rm{1}}$ ，即证据高度冲突时，利用原组合原则就会导致与实际常理相违背的结果，可以利用文献[22]提出的证据权对基本分配函数进行修正来解决此类问题。 ${m_i}{\text{、}}{m_j}$ 的距离定义为

 $\begin{array}{c} d\left( {{m_{i,}}{m_j}} \right) = \\ \sqrt {\dfrac{{\rm{1}}}{{\rm{2}}}\left( {\left\langle {{M_i},{M_j}} \right\rangle + \left\langle {{M_j},{M_i}} \right\rangle - {\rm{2}}\left\langle {{M_i},{M_j}} \right\rangle } \right)} \end{array}$ (7)

 $\left\langle {{M_i},{M_j}} \right\rangle = \sum\limits_{{A_i}} {\sum\limits_{{A_j}} {{m_i}\left( {{A_i}} \right){m_j}\left( {{A_j}} \right)\frac{{\left| {{A_i} \cap {A_j}} \right|}}{{\left| {\left| {{A_i} \cup {A_j}} \right|} \right|}}} }$ (8)

${m_i}{\text{、}}{m_j}$ 的近似度定义为

 $s\left( {{m_{\rm{1}}},{m_{\rm{2}}}} \right) = {\rm{1}} - d\left( {{m_{\rm{1}}},{m_{\rm{2}}}} \right)$ (9)

 $\alpha \left( {{m_i}} \right) = \sum\limits_{j = {\rm{1}},j \ne {\rm{1}}}^n {s\left( {{m_i},{m_j}} \right)}$ (10)

 $\alpha \left( {{m_f}} \right) = \mathop {\rm max }\limits_{{\rm{1}} \leqslant i \leqslant n} \left\{ {\alpha \left( {{m_i}} \right)} \right\}$ (11)

 ${\beta _i} = \frac{{\alpha \left( {{m_i}} \right)}}{{\alpha \left( {{m_f}} \right)}}$ (12)

 $m_i'\left( A \right) = {\beta _i}{m_i}\left( A \right),\forall A \in {{\rm{2}}^\theta },A \ne \theta$ (13)
 $m_i'\left( \theta \right) = {\beta _i}{m_i}\left( \theta \right) + \left( {{\rm{1}} - {\beta _i}} \right)$ (14)

2 D-S证据最优权值优化算法

2.1 果蝇算法

2.2 果蝇算法优化权值

Step1　参数初始化

Step2　生成潜在解

1)把每个权值作为果蝇个体，对果蝇位置进行初始化：

 ${x_{ - \rm axis}} = {\rm random}\left( {\rm LR} \right)$
 ${y_{ -\rm axis}} = {\rm random}\left( {\rm LR} \right)$

2)根据已知嗅觉给出觅食果蝇飞行的随机方向和随机距离：

 ${x_i} = {x_{ - \rm axis}} + {\rm random}\left( {\rm FR} \right)$
 ${y_i} = {y_{ - \rm axis}} + {\rm random}\left( {\rm FR} \right)$

3)计算觅食果蝇与原点的距离：

 ${D_i} = \sqrt {x_i^{\rm{2}} + y_i^{\rm{2}}}$

4)计算气味浓度判定值 ${S_i}$

 ${S_i} = \frac{{\rm{1}}}{{{D_i}}}$
 $\frac{{\rm{1}}}{{{D_i}}} = \sqrt {\begin{array}{*{20}{l}} {{{\left( {{x_{ -\rm axis}} + {\rm random}\left( {\rm FR} \right)} \right)}^{\rm{2}}}}+\\ { {{\left( {{y_{ - \rm axis}} + {\rm random}\left( {\rm FR} \right)} \right)}^{\rm{2}}}} \end{array}}$

Step3　将气味浓度判定值 ${S_i}$ 代入目标函数(function)中计算个体果蝇所处位置的气味浓度 $\left( {{\rm{Smel}}{{\rm{l}}_i}} \right)$

 ${\rm{Smel}}{{\rm{l}}_i} = {\rm{function}}\left( {{S_i}} \right)$

 $F = {\rm max} \left\{ {{\rm min} \left[ {m\left( {{C_{\rm{0}}}} \right) - m\left( {{C_i}} \right)\left| {i = {\rm{1}},2, \cdots ,N - {\rm{1}}} \right.} \right]} \right\}$

Step4　寻到群体中最优的气味浓度和个体位置，本文取最大值

 $\left[ {\rm bestSmell\;bestindex} \right] = ｛\rm max｝ \left( {\rm Smell} \right)$

Step5　果蝇群体飞向气味浓度最大值的果蝇个体，形成新的果蝇群体位置，记录此时的权值

 $\begin{array}{*{20}{c}} {\rm Smell\;best = best\;smell}\\ {{X_{{\rm{ - }}\rm axis}} = X\left( {\rm bestindex} \right)}\\ {{Y_{{\rm{ - }}\rm axis}} = Y\left( {\rm bestindex} \right)} \end{array}$

Step6　开始迭代优化，重复执行step2~step5，当气味浓度值在约束条件下不再优于先前的迭代气味浓度或者迭代数达到最大时，循环停止，并将此时的权值代入D-S证据理论中进行多传感器信息融合。

 $m\left( c \right) = \left\{ {\begin{array}{l} {\begin{array}{l} \!\!\! \!\!\! \!\!\! {\rm{0}},\;\;{C = \text{Ø} } \end{array}} \\ {\begin{array}{*{20}{c}} \!\!\! \!\!\! \!\!\! {\displaystyle\sum\limits_{{A_i} \cap {B_j}} {\frac{{m_{\rm{1}}^{{\beta _{\rm{1}}}}\left( {{A_{\rm{1}}}} \right)m_{\rm{2}}^{{\beta _{\rm{2}}}}\left( {{B_j}} \right)}}{{{\rm{1}} - {K_{\rm{1}}}}}} },\;\;{\forall C \subset \theta ,}{C \ne \text{Ø} } \end{array}} \end{array}} \right.$
 $\begin{array}{*{20}{c}} {{K_{\rm{1}}} = \displaystyle\sum\limits_{{A_i} \cap {B_j} = C} {\frac{{m_1^{{\beta _1}}\left( {{A_i}} \right)m_{\rm{2}}^{{\beta _{\rm{2}}}}\left( {{B_j}} \right)}}{{\left( {{\rm{1}} - {K_{\rm{1}}}} \right)}} < {\rm{1}}}}\\ {m\left( {{C_{\rm{0}}}} \right) - m\left( {{C_i}} \right) > {\rm{0}}} \end{array}$ (15)
 ${\rm{0}} \leqslant {\beta _i} \leqslant {\rm{1}},\sum\limits_{i = 1}^N {{\beta _i}} = {\rm{1}},\beta _i^{{\rm{min}} } \leqslant {\beta _i} \leqslant \beta _i^{{\rm{max}} }$

3 四轴飞行器信息检测系统

4 基于FOA-DS的多传感器信息融合技术在四轴飞行器障碍辨识中的应用

1)获取证据源，参考专家经验给出的权值上下限，确定范围。

2)由果蝇算法在范围内按照2.2节寻找最优权值。

3)将最优权值按照式(7)~(14)进行基本概率重分配，以满足D-S证据理论组合规则对各证据的权重要求相同的条件。

4)按照组合规则进行数据融合输出结果。FOA−DS证据理论障碍辨识流程如图3所示。

 Download: 图 3 FOA-DS证据理论障碍辨识流程 Fig. 3 FOA-DS evidence theory obstacle identification flow chart

 $\begin{array}{*{20}{c}} {{\rm{BEL}}\left( {{A}} \right) = 0.629}\\ {{\rm{BEL}}\left( {{B}} \right) = 0.135}\\ {{\rm{BEL}}\left( {{C}} \right) = 0.112} \end{array}$

 $\begin{array}{*{20}{c}} {{\rm{BEL}}\left( {{A}} \right) = 0.362}\\ {{\rm{BEL}}\left( {{B}} \right) = 0.253}\\ {{\rm{BEL}}\left( {{C}} \right) = 0.385} \end{array}$

 Download: 图 6 单一传感器与多传感器障碍辨识准确率对比 Fig. 6 Comparison of obstacle recognition accuracy between single sensor and multi sensor

 Download: 图 7 改进D-S证据理论与贝叶斯估计和粒子滤波算法障碍辨识准确率对比 Fig. 7 Comparison of improved D-S evidence theory with Bayesian estimation and particle filter algorithm for obstacle recognition accuracy

5 结束语

 [1] 杨秀霞, 周硙硙, 张毅. 基于速度障碍圆弧法的UAV自主避障规划研究[J]. 系统工程与电子技术, 2017, 39(1): 165-176. YANG Xiuxia, ZHOU Weiwei, ZHANG Yi. Automatic obstacle avoidance planning for UAV based on velocity obstacle arc method[J]. Systems engineering and electronics, 2017, 39(1): 165-176. (0) [2] 杨秀霞, 张毅, 周硙硙. 一种动态不确定环境下UAV自主避障算法[J]. 系统工程与电子技术, 2017, 39(11): 2546-2552. YANG Xiuxia, ZHANG Yi, ZHOU Weiwei. Autonomous obstacle avoidance algorithm for UAV in dynamic uncertain environment[J]. Systems engineering and electronics, 2017, 39(11): 2546-2552. DOI:10.3969/j.issn.1001-506X.2017.11.23 (0) [3] 关震宇, 杨东晓, 李杰, 等. 基于Dubins路径的无人机避障规则算法[J]. 北京理工大学学报, 2014, 34(6): 570-575. GUAN Zhengyu, YANG Dongxiao, LI Jie, et. Obstacle avoidance planning algorithm for UAV based on Dubins path[J]. Transactions of Beijing Institute of Technology, 2014, 34(6): 570-575. (0) [4] 任佳, 高晓光, 张艳. 移动威胁情况下的无人机路径规划[J]. 控制理论与应用, 2010, 27(5): 641-646. REN Jia, GAO Xiaoguang, ZHANG Yan. Path planning based on model predictive control algorithm under moving threat[J]. Control theory & applications, 2010, 27(5): 641-646. (0) [5] SCHMITTL, FICHTER W. Collision-avoidance framework for small fixed-wing unmanned aerial vehicles[J]. Journal of guidance, control, and dynamics, 2014, 37(4): 1323-1329. DOI:10.2514/1.G000226 (0) [6] JENIE Y I, VAN KAMPEN E J, DE VISSER C C, et al. Selective velocity obstacle method for deconflicting maneuvers applied to unmanned aerial vehicles[J]. Journal of guidance, control, and dynamics, 2015, 38(6): 1140-1145. DOI:10.2514/1.G000737 (0) [7] 余超凡, 孙建辉. 基于光流传感器的旋翼无人机实时避障系统[J]. 计算机应用于软件, 2018, 35(1): 206-210. YU Caofang, SUN Jianhui. A real-time obstacle avoidance system for multi-rotor unmanned aerial vehicle based on optical flow sensor[J]. Computer applications and software, 2018, 35(1): 206-210. (0) [8] 周源, 王希彬. 无人机SLAM避障技术研究[J]. 兵工自动化, 2015, 34(11): 78-81. ZHOU Yuan, WANG Xibin. Research on obstacles avoidance for UAV SLAM technology[J]. Ordnance industry automation, 2015, 34(11): 78-81. DOI:10.7690/bgzdh.2015.11.020 (0) [9] 王伟, 王华. 基于约束人工势场法的弹载飞行器实时避障航迹规划[J]. 航空动力学, 2014, 29(7): 1738-1743. WANG Wei, WANG Hua. Real-time obstacle avoidance trajectory planning for missile borne air vehicle based on constrained artificial potential field method[J]. Journal of aerospace power, 2014, 29(7): 1738-1743. (0) [10] [10] LIU Zhiyang, JIANG Tao. Route planning based on improved artificial potential field method[C]//Proceedings of 2017 Asia-Pacific Conference on Intelligent Robot System. Wuhan, China: IEEE, 2017: 196−199. (0) [11] ZHANG Yingkun. Flight path planning of agriculture UAV based on improved artificial potential field method[C]//Proceedings of 2018 Chinese Control and Decision Conference. Shenyang, China: IEEE, 2018: 1526−1530. (0) [12] BOUNINI F, GINGRAS D, POLLART H, et al. Modified artificial potential field method for online path planning applications[C]//Proceedings of 2017 IEEE Intelligent Vehicles Symposium. Los Angeles, USA: IEEE, 2017: 180−185. (0) [13] 赵海, 陈星池, 王家亮, 等. 基于四轴飞行器的单目视觉避障算法[J]. 光学精密工程, 2014, 22(8): 2232-2241. ZHAO Hai, CHEN Xingchi, WANG Jialiang, et al. Obstacle avoidance algorithm based on monocular vision for quad-rotor helicopter[J]. Optics and precision engineering, 2014, 22(8): 2232-2241. (0) [14] MA Lili. Vision-based avoidance of obstacles with unknown constant velocity[C]//Proceedings of the 2010 American Control Conference. Baltimore, USA: IEEE, 2010: 5550−5555. (0) [15] 孙锐. 基于D-S证据理论的信息融合及在可靠性数据处理中的应用研究[D]. 成都: 电子科技大学, 2017. SU Rui. Researche on D-S evidence theory based information fusion and its application in reliability data processing[D]. Chengdu: University of Electronic Science and Technology of China, 2017. (0) [16] 刘标, 许腾, 李光. D-S证据理论改进算法提高水下目标识别准确性[J]. 现代防御技术, 2018, 46(1): 120-155. LIU Biao, XU Teng, LI Guang. Algorithm improvement of D-S evidence theory in submarine target recognition[J]. Modern defense technology, 2018, 46(1): 120-155. DOI:10.3969/j.issn.1009-086x.2018.01.019 (0) [17] 李昌钰, 周焰, 林菡, 等. 考虑传感器置信度的改进的D-S证据合成算法[J]. 解放军理工大学学报(自然科学版), 2017, 18(1): 81-86. LI Changyu, ZHOU Yan, LIN Han, et al. Improved D-S evidence combination rule based on reliability of sensors[J]. Journal of PLA University of Science and Technology (Natural Science Edition), 2017, 18(1): 81-86. (0) [18] 王慧, 宋宇宁. D-S证据理论在火灾检测中的应用[J]. 中国安全科学学报, 2016, 26(5): 19-23. WANG Hui, SONG Yuning. Application of D-S evidence theory in fire detection[J]. China safety science journal, 2016, 26(5): 19-23. (0) [19] 李玲玲, 马冬娟, 王成山, 等. D-S证据理论冲突处理新方法[J]. 计算机应用研究, 2011, 28(12): 4528-4531. LI Lingling, MA Dongjuan, WANG Chengshan, et al. New method for conflict evidence processing in D-S theory[J]. Application research of computers, 2011, 28(12): 4528-4531. DOI:10.3969/j.issn.1001-3695.2011.12.034 (0) [20] 韩德强, 杨艺, 韩崇昭. D-S证据理论研究进展及相关问题探讨[J]. 控制与决策, 2014, 29(1): 1-11. HAN Deqiang, YANG Yi, HAN Chongzhao. Advances in DS evidence theory and related discussions[J]. Control and decision, 2014, 29(1): 1-11. (0) [21] 袁杰, 王福利, 王姝, 等. 基于D-S融合的混合专家知识系统故障诊断方法[J]. 自动化学报, 2017, 43(9): 1580-1587. YUAN Jie, WANG Fuli, WANG Shu, et al. A fault diagnosis approach by D-S fusion theory and hybrid expert knowledge system[J]. Acta automatica sinica, 2017, 43(9): 1580-1587. (0) [22] 刘海燕, 赵宗贵, 刘熹. D-S证据理论中冲突证据的合成方法[J]. 电子科技大学学报, 2008, 37(5): 701-704. LIU Haiyan, ZHAN Zhonggui, LIU Xi. Combination of conflict evidences in D-S theory[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(5): 701-704. DOI:10.3969/j.issn.1001-0548.2008.05.016 (0) [23] 王林, 吕盛祥, 曾宇容. 果蝇优化算法研究综述[J]. 控制与决策, 2015, 32(7): 1153-1162. WANG Lin, LYU Shengxiang, ZENG Yurong. Literature survey of fruit fly optimization algorithm[J]. Control and decision, 2015, 32(7): 1153-1162. (0) [24] 饶盛华, 张小平, 张铸, 等. 基于果蝇算法的开关磁阻电机多目标优化研究[J]. 电子测量与仪器仪表学报, 2017, 31(7): 1152-1158. RONG Shenghua, ZHANG Xiaoping, ZHANG Zhu, et al. Study on multi-objective optimization of SRM based on FOA[J]. Journal of electronic measurement and instrumentation, 2017, 31(7): 1152-1158. (0) [25] 徐湘寓, 崔颖强, 罗丽燕. 基于多传感器信息融合的室内定位算法研究[J]. 信息系统与网络, 2018, 48(1): 10-16. XU Xiangya, CUI Yingqiang, LUO Liyan. An indoor pedestrian localization algorithm based on multi-sensor information fusion[J]. Radio engineering, 2018, 48(1): 10-16. (0) [26] 陈辉, 邓记才, 吴晓辉, 等. 多传感器信息融合在轮式机器人运动控制中的应用[J]. 传感技术学报, 2011, 24(6): 915-918. CHEN Hui, DENG Jicai, WU Xiaohui, et al. Implementation of the multisensory information fusion technology in the wheel-robot movement control[J]. Chinese journal of sensors and actuators, 2011, 24(6): 915-918. DOI:10.3969/j.issn.1004-1699.2011.06.027 (0)