人工鱼群算法在无人机SLAM数据关联中的应用(自动化)

                           王希彬¹，刘  涛²

（1．海军航空工程学院控制工程系，山东烟台264001;2.海军航空工程学院飞行器工程系，山东烟台264001）

摘要：错误的数据关联会降低SLAM算法的性能。为提高数据关联率，提出了基于人工鱼群算法的SLAM数据关联方法，利用启发式信息，根据状态转移概率和轮盘赌策略，建立鱼群状态量与所求解的对应关系，通过寻求最优人工鱼的状态从而获得最优解；同时使用混沌初始化鱼群，采用自适应的步长和拥挤度因子加快算法的收敛速度，在聚群和追尾行为后进行混沌优化，使人工鱼跳出局部极值点，从而获得全局最优解。最后针对无人机SLAM的数据关联问题，利用算法进行仿真试验，结果表明该方法是有效可行的。

关键词：人工鱼群算法；同时定位与作图；数据关联；混沌；无人机

中图分类号：V24  文章编号：1006 - 2394( 2016) 06 - 0013 - 04

0  引言

    同时定位与作图( Simultaneous Localization AndMapping，SLAM)就是载体从未知环境的未知位置出发，利用载体上传感器获得的不确定信息逐渐构建环境的地图，同时利用地图进行定位与导航。SLAM被认为是载体实现真正自主导航的关键。

    获得鲁棒性的SLAM解的关键之一就是数据关联问题。几乎所有的状态估计算法都会遇到数据关联的问题，也就是传感器测量值和已经建立的地图中特征的关联问题。但是由于载体位姿的不确定性、环境特征的密度、运动目标的干扰及观测中虚假成分的存在，使得SLAM问题的数据关联难度更大。

    已存在许多经典方法解决SLAM数据关联问题：最近邻( NN)方法、多假设跟踪、联合兼容分支定界等，它们大多是多目标跟踪数据关联算法的直接应用。近年来提出了许多优化算法，如整数规划、多维分配、成本函数及模拟退火等用于解决SLAM的数据关联问题，取得了较好的关联效果，但是经常会陷入局部极优。

本文将SLAM的数据关联问题演化为组合优化问题，利用鱼群算法鲁棒性强、全局收敛性好以及对初值要求低的优点，将其应用于SLAM的数据关联问题，并进行仿真试验，结果表明了方法的有效性。

1 SLAM数据关联演化为组合优化

    数据关联可以认为在观测．特征匹配空间的搜索问题。找到m个传感器测量值和n个地图特征的匹配关系，其计算复杂性会随着测量值的增多而呈指数

2基本的人工鱼群算法

    鱼群算法是李晓磊等人于2002年提出的一种自下而上设计的动物自治体优化算法，通过模拟鱼群的觅食和生存活动来实现在空间中寻求全局最优的一种新思路。鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法根据这一特点，构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为，从而获得全局最优。人工鱼的典型行为如下：

    (4)随机行为：人工鱼会在其视野内随机移动，当发现食物时，会向食物逐渐增多的地方快速移去。

    (5)约束行为：由于各种行为操作，使得人工鱼的状态变得不可行，需要加入相应的约束进行规整化。

    (6)公告板：用于记录最优人工鱼的状态。各人工鱼在迭代过程中，将自身当前状态与公告板中记录的状态进行比较，如果优于公告板中的状态，则用自身状态更新公告板中的状态，否则公告板的信息不变。当整个算法的迭代结束后，输出公告板的值，即为所求的最优值。

3基于改进人工鱼群算法的SLAM数据关联

    在离散系统中，李晓磊提出了most操作计算中心位置，但由于数据关联考虑的特征数量比较大，参与寻优的人工鱼数目比较多，most操作在整个寻优过程中反复出现计算量大。因此，考虑采用随机数进行编码，直接在编码空间模拟人工鱼的行为，根据状态转移概率和轮盘赌策略进行最优解码，加快人工鱼的寻优速度。

服从均匀分布的伪随机数。把某条人工鱼对应的量测与特征匹配的路径长度作为适应度函数，分别计算N条人工鱼的适应度值，从中选择较好的M条人工鱼，作为鱼群的初始位置。

    对第k条人工鱼，量测值i对特征j的状态转移概率：

    轮盘赌选择策略是一种正比选择策略，状态转移概率高的分量所占的比例大，被选择的概率高，得到的问题的解就是当前鱼群对应的最优解。

3.1  自适应步长和拥挤度因子

    基本人工鱼群算法中，参数取固定值，算法一般在优化初期收敛速度快，后期却往往收敛速度减慢。为此在人工鱼群的搜索过程中引进自适应的变步长和变拥挤度因子，加快算法的收敛速度，提高寻优精度。

    在开始阶段，每条鱼以较大的步长和拥挤度因子进行寻优，可以加快寻优速度，避免陷入局部最优；随着算法的进行，自适应地减小人工鱼的步长和拥挤度因子，从而加快算法的收敛速度，提高搜索的精度。引

3.2混沌

    混沌是自然界广泛存在的一种非线性现象，它看似混沌，却有着精致的内在结构，具有随机性、遍历性及规律性等特点，它对初始条件极度敏感，能在一定范围内按其自身规律不重复地遍历所有状态，利用混沌运动的这些性质可以进行优化搜索。

    混沌搜索中经常用到Logistic映射，迭代公式如下：

3.3人工鱼群算法数据关联的流程

步骤1：参数初始化。设置混沌初始化鱼群规模

    步骤6：公告板更新。鱼群迭代后，若鱼群中最优鱼状态的适应值优于公告板中的最优值，则更新公告板。若终止条件满足，则该条人工鱼对应的量测与特征的匹配关系即为最优数据关联。

    一次迭代后，计算下一次迭代的拥挤度因子及步长，直至满足终止条件。

4仿真试验

    仿真试验中，无人机在平面内作半径为20 m的圆周运动，利用机载传感器持续测量36个地标，如图1所示，圆周代表无人机的运动轨迹，离散的点表示地标，均匀分布在轨迹的内侧和外侧半径为18和22的圆周上，角度的测量偏差为1 0，距离的量测偏差为0.1m。在试验中，各参数的选取如下：人工鱼群体规模为10，拥挤度因子=0. 618，衰减因子=0.95，人工鱼

    表1给出了最大概率、基本鱼群算法和改进鱼群算法三种算法的正确关联率，以及收敛与否的比较结果。图2～图4给出了三种算法的数据关联率曲线。仿真结果表明，与最大概率方法和基本的鱼群算法相比，本文提出的鱼群算法不仅使SLAM算法收敛，并且得到了较高的正确数据关联率，因而使得SLAM算法更加稳定。

5结论

    本文将SLAM数据关联问题作为组合优化问题进行考虑，提出了基于改进人工鱼群算法的SLAM数据关联方法。从对无人机SLAM数据关联的仿真试验看，该方法提高了正确的数据关联率，得到了较好的关联效果，改善了SLAM的性能，表明了该算法的可行性和优越性。