人工鱼群移动机器人路径运用

路径规划［1，2］是移动机器人导航的最基本环节之一，其依据是在其工作空间中找到一条从起始状态到目标状态能避开障碍物的最优路径。而对于清罐移动机器人［3］边界清理需要按照移动机器人路径规划原则，遍历油罐底部边界及拐角，通常油罐底部有固定障碍物如支架、加强环和扶梯等，因此，它与移动机器人路径规划情况一致且属于全局路径规划。对于环境信息完全已知的全局路径规划问题，已经提出了许多有效的解决方法，如栅格法［4］、可视图法［5］、人工势场法［6］和智能算法［7］等，但上述方法各有优缺点，其中栅格法算法简单，但空间分辨率、时间复杂度与内存容量、实时性要求较高限制了它的使用;可视图法能够求得最短路径，但是缺乏灵活性，且存在组合爆炸问题;人工势场法结构简单、易于实现，应用广泛，但其缺点较为明显，如在陷阱区域、在相近障碍物之间不能发现路径、在障碍物前面震荡、参数不易调整等;智能算法可以方便调整路径上的点，易得到全局的最优路径，但智能算法如粒子群算法、遗传算法等有其固有的缺陷，往往得到的最优路径是局部路径。近年来，人工鱼群算法［8］在工程领域应用较多，其原因是人工鱼群算法(artificialfishschoolalgo-rithm，AFSA)具有良好的求取全局极值能力，具有对初值和参数选择不敏感、鲁棒性强、简单、易实现等优点。近3年，有不少学者对人工鱼群算法进行研究，但人工鱼群智能算法有其固有的缺陷，如存在易陷入局部最优、收敛精度不高的缺点。本文中针对人工鱼群算法的不足，提出一种自适应变步长、变拥挤度因子和变视野域的自适应人工鱼群算法(adaptiveartificialfishschoolalgorithm，AAFSA)，该算法通过自适应调整因子调整人工鱼的可视域、移动步长和拥挤度因子，使算法的遍历性得到改善，既可获得全局最优，又可实现局部搜索，避免了传统人工鱼群算法局部寻优能力弱的缺点，提高了收敛速度和算法的精度。然后将其引入清罐移动机器人路径规划当中，设计出一种基于自适应人工鱼群算法的清罐移动机器人路径规划算法，并通过实验验证该方法的有效性。

1自适应人工鱼群算法在机器人路径规划中的应用

1.1自适应人工鱼群算法［9］AAFSA算法思想是在人工鱼觅食、聚群和追尾等搜索过程进行中，随环境自适应变化，其目的是加快算法的收敛速度、提高算法精度。早期以较大的视野域、较大的步长寻优;后期自适应调整视野域，对陷入平坦区的人工鱼进行自适应扰动，改变人工鱼状态，避免陷入局部最优，再改变步长和调整拥挤度因子，加快算法的收敛速度、提高算法精度。

1.1.1自适应人工鱼视野、步长和拥挤度因子的自适应调整算法文献［10］表明，视野、步长和拥挤度因子对算法中各种行为和收敛性能有较大影响。为此在算法运行前期，采用较大的视野和步长，使人工鱼在更大范围内进行粗搜索;随着搜索的进行，视野和步长逐渐减小，算法逐步演化为局部搜索，定位在最优解附近区域并进行精细搜索，从而提高算法的局部搜索能力和寻优结果的精度。视野visual、步长step和拥挤度因子δ的调整式为

1.1.2自适应人工鱼算法数学描述弹性自适应人工鱼群算法与传统人工鱼群算法有区别［8］，自适应人工鱼群算法寻优迭代过程中随环境感知距离、移动步长和拥挤度因子是自适应调整的，而不是随机取步长和固定感知距离及拥挤度因子，即觅食行为可以自适应调整感知距离和移动步长，聚群行为和追尾行为可以自适应调整移动步长和拥挤度因子，而鱼群视野在聚群行为和追尾行为中仍然保持不变，仅在觅食行为中变换。1)觅食行为visual表示人工鱼的感知距离;step表示人工鱼移动步长，stepmax表示人工鱼移动步长的最大值;δ表示拥挤度因子。以神经网络输出误差E定义人工鱼个体当前位置的食物浓度值FC。其中2)聚群行为设人工鱼当前状态为Xi，探索其邻域的伙伴数目nf，形成集合K，且K={Xj|dij≤visual}若K不为空集，则搜索伙伴中心位置状态Xi，center(k)，按下面的公式执行，即3)追尾行为设人工鱼当前状态为Xi，探索当前感知范围内(即dij＜visual)的伙伴中FC值最大的伙伴Xmax，若满足FCmax/nf＞δFCi，表明伙伴Xmax的状态具有较高的食物浓度并且其周围不太拥挤，则朝伙伴Xmax的方向前进一步，执行下面的公式，即(3)自适应调整。否则执行觅食行为。若感知范围内没有其它伙伴，也执行觅食行为。4)公告板公告板用来记录最优人工鱼个体的状态。各人工鱼个体在寻优过程中，每次行动完毕就检验自身状态与公告板的状态。如果自身状态优于公告板状态，就将公告板的状态改写为自身状态，这样就使公告板记录下历史最优的状态。5)行为选择对人工鱼当前所处的环境进行评价，即模拟执行聚群、追尾行为，然后选择行动后食物浓度值较大的动作来执行，缺省行为方式为觅食行为。

1.2机器人路径规划自适应人工鱼群算法的步骤Step1初始化。确定机器人路径规划中的起始位置，障碍物的位置坐标及各段路径权向量。确定算法的参数:输入人工鱼的群体规模N，最大迭代次数number，人工鱼可视域Visual的范围，人工鱼移动步长step的范围，拥挤度因子δ的范围，人工鱼的最大移动步长step和初始值，拥挤度因子δ初始值;设置初始迭代次数number=0，在控制变量可行域内随机生成N个人工鱼个体，形成初始鱼群，各个分量均为设定区间内的随机数;Step2评价。以均方差的倒数作为函数(FC)，计算鱼群中各人工鱼个体当前位置的食物浓度值FC，并比较大小。取FC为最大值者进入公告板，将此人工鱼赋值给公告板，那么该人工鱼对应的极值就是下次迭代中最优路径。Step3更新极值。各人工鱼分别模拟追尾行为和聚群行为，然后选择行动后食物浓度值(FC)较大的动作来执行，缺省行为方式为觅食行为;各人工鱼每行动一次后，检验自身的FC与公告板的FC，如果优于公告板，则以自身取代之。若所有人工鱼的个体极值中最好的优于当前全局极值，则将该人工鱼赋值给公告板作为更新全局极值。按公式(1)自适应调整感知距离visual、移动步长step和拥挤度因子δ，各人工鱼分别多次模拟追尾行为、聚群行为和觅食行为，各人工鱼每行动一次后，检验自身的FC，找出当前全局极值，更新全局极值。Step4检验。当迭代达到最大次数number或最小误差要求时，停止迭代，全局极值为机器人路径规划最优路经。否则转到Step2。

2仿真实验

假设本次实验设置某油罐底部的边界及拐角等，有支架、加强环和扶梯等不同固定障碍物有30个，其顶点坐标信息均为已知(见表1):求基于自适应人工鱼群清罐移动机器人路径规划方法得到的最短距离。首先设置自适应人工鱼如何越过机器人路径上的障碍物，不同障碍物的位置和尺寸对人工鱼寻找优化路径方式不一样。自适应人工鱼越过障碍物的方式仿真结果见图1所示。从图1可见，自适应人工鱼能自适应选择机器人路径上障碍物的穿越方式，表明具有自适应性。下面采用自适应人工鱼群算法对表1这条路径进行优化。程序运行环境为奔腾2GHz，操作系统为WindowsXp，程序执行软件为Matlab7.2。采用的自适应人工鱼群算法参数设置为:人工鱼的可视域visual范围［0.6，35］，步长step范围［0.5，15］，拥挤度因子δ范围［0.5，0.9］，初始为0.618，鱼群规模N=60，最大试探次数trynumber=6;最大迭代次数kmax为200。为了验证自适应人工鱼群在清罐移动机器人路径规划方法的合理性和有效性，本文将其运算仿真结果同人工鱼群算法在清罐移动机器人路径规划方法所得结论相对照。选择相同的起始点A和终止点d，初始路径选为起始点和终止点连线上均匀分布的点列。利用本文提出的自适应人工鱼群算法以及人工鱼群算法，分别对路径A～d进行优化。计算机仿真结果如图2和图3所示。用人工鱼群算法对同样的问题进行算法仿真，其初始参数设置:人工鱼的可视域visual范围［0.6，30］，步长step范围［0.5，10］，拥挤度因子δ范围［0.5，0.9］，初始为0.618，鱼群规模N=60，最大试探次数trynumber=6;最大迭代次数kmax为200。仿真结果见图3所示。从图2和图3可知自适应人工鱼群算法在迭代到200步时达到稳定，求得最优路径为15526.6894cm，而人工鱼群算法在迭代到200步时，求得最优路径长度为19762.94cm。可见，自适应人工鱼群算法在机器人路径规划方面优于人工鱼群算法。两种算法各运行200次，图4为用自适应人工鱼群算法和人工鱼群算法对路径进行优化的收敛性图。可以看到，用自适应人工鱼群算法求解问题，算法可以在平均110代以内收敛，找到全局最优值，且不会陷入局部极小;用人工鱼群算法求解问题，平均将近200代才能找到最优值，且有多次陷入局部极小，并且波动性较大。很明显，用自适应人工鱼群算法来求解清罐移动机器人路径规划大大节约了时间，明显优于用人工鱼群算法，能满足机器人路径规划的实时性要求。从图2和图3可以看出，使用自适应人工鱼群算法和人工鱼群算法均能到达d点，即完成清罐移动机器人路径规划任务，得到全局最优解。从图4可知，自适应人工鱼群算法迭代到110次，得到的全局最优解为15526.6894cm，比人工鱼群算法所得的全局最优解少4236.2506cm，所耗的时间低于后者，即收敛速度高于后者。充分体现了自适应人工鱼群在求解清罐机器人路径规划方面的优越性，也表明本实验清罐移动机器人规划的最短路径为自适应人工鱼群算法所求的最优解。通过视野域调整因子调整人工鱼视野、步长调整因子调整人工鱼步长和拥挤度调整因子调整拥挤度因子，可以自适应调整人工鱼的行为。即使选择起始点B和终止点A，即路径为B－d－A;或起始点C和终止点B，即路径为C－d－A－B，与传统人工鱼群做对比实验，自适应人工鱼群算法迭代到100次，得到的全局最优解分别为15933.2841cm和15011.3637cm，比人工鱼群算法所得的全局最优解分别少4453.3617cm和4108.1863cm，所耗的时间低于后者，即收敛速度高于后者。可见，自适应人工鱼群算法充分利用了自适应人工鱼视野、步长和拥挤度因子的自适应调整算法的优点，解决了随机性搜索和确定性搜索平衡问题，提高了收敛速度。仿真结果表明，自适应人工鱼群算法收敛速度快，计算效率高，简单易实现，为清罐移动机器人路径规划提供了一种简便有效的策略。

3结论

1)自适应人工鱼群算法通过自适应调整因子分别调整人工鱼觅食行为中的可视域和移动步长、聚群和追尾行为过程中的移动步长和拥挤度因子，使算法的遍历性得到改善，既可获得全局最优，又可实现局部搜索，避免了传统人工鱼群算法局部寻优能力弱的缺点，提高了收敛速度和算法的精度;2)用自适应人工鱼群算法来调整机器人路径规划上的点，在很少的迭代次数内能快速获得全局最优路径。表明自适应人工鱼群方法能满足清罐移动机器人路径规划的实时性，为清罐移动机器人路径规划提供了一种科学的、有效的方法。