免疫算法在移动机器人路径规划中的应用*

赵 娜

(太原师范学院，山西太原030012)

移动机器人是自动化与机器人领域最有前景的研究方向之一。它是小车机械、机器人学、机电一体化、精密仪器、轨迹规划、多智能协调等理论、技术的融合体，它对于研发多智能体系统具有重要的研究模型意义。

与移动机器人相关的研究内容有:运动控制、多智能体合作、软硬件平台与路径规划。其中，对移动机器人的性能影响比较大的是路径规划算法的性能，它为顶层决策与底层控制提供了衔接功能。移动机器人路径规划问题可以这样来描述:确定目标点和出发点，处于具有有障碍物(固定或移动)的环境中，为移动机器人在满足一定的最优规则的情况下规划一条无碰的路径，使得移动机器人遵照规划的路径运动并到达目标点。最优规则包括最短的路径长度、最小的消耗能量和最短运行时间等。目前路径规划有许多方法，如势场法［1］、动态意图预测法［2］，在文献［3］中提出了基于遗传算法的路径规划方法。

信息处理系统模仿生物免疫系统，为找到新的更优的智能控制算法提供比较有力的启发。生物免疫系统是一个基本防御系统，它的作用是抵抗细菌、病毒和其它致病因子入侵。免疫系统是一个复杂系统，其由器官、细胞和分子组成。与神经系统相同，它是一个机体能特异地识别“自己/非己”的刺激、精确应答、保留记忆的功能系统。同时，免疫系统利用一套复杂的机制使基因重组，使产生的抗体能够有效地识别入侵的抗原，并消灭抗原。在这个过程中，通过体细胞理论和网络理论可得出抗体具有模式识别、免疫记忆与学习、多样性的产生、噪声耐受、归纳概括、分步检测、自我抑制调节的功能［4］。

自然免疫系统为人工智能方法提供了灵感。人工免疫算法是一种在生物界中得到启示，以自然免疫系统为机理，将其中的有利用价值的原理应用到人工智能中的一种算法。受这样的启发，已经有很多种人工免疫算法提出，它们利用自然免疫系统的原理实现了类似于免疫系统的识别抗原、分化细胞、记忆以及自调节的良好功能;免疫行为较好地使多样性得到保持，从而有效地预防了“早熟”现象。

在目前人工免疫系统的基础上，本文将其中一种人工免疫算法用于移动机器人路径规划中。对移动机器人基本控制方式进行了简要说明，然后求得算法中需要的函数，并详细说明了人工免疫算法在路径规划中的实施过程，仿真结果充分说明了该算法的可行性和有效性。

1 移动机器人运动路径的选取与亲和力函数构建

1.1 路径抗体编码的产生

编码对于机器人路径规划是非常重要的，由于本文使用人工免疫算法求解最优路径，所以对路径进行如图1所示的抗体编码。

图1 路径点选取示意图

起点与终点构成线段SG，长度为DIST，并确定一个路径有效搜索区域，一般为正方形;将SG进行n等分，通过每个等分点做SG的垂线段，依次在每一条垂线段上任意取一点Aji，按顺序依次连接这些点，则构成一条路径Lj;同理，可以得到m条路径。表示如下:

其中，j=1，2，3，…，m;i=0，1，2，…，n;Aji为第 j条路径的第i条垂线段上的点;Aj0取为起点，Ajn取为终点。

由于等分的特点，把路径点转化为直角坐标形式的一维编码，则有:

其中，yji为点Aji在直角坐标中的纵坐标，并且规定起点与终点坐标固定。

1.2 亲合力函数的构建［3］

亲和力函数的选取将直接影响到免疫算法收敛速度的快慢和最终的结果。在移动机器人的路径规划中，亲和力函数应该满足两个现实条件，即路径最短并且能够有效避开障碍物。为此，文中将亲和力函数分为两部分。

路径距离的亲和力函数可以由以下公式确定

其中(xji，yji)是第j条路径第i点的坐标。

假设在路径搜索区域内有q个障碍物，每个障碍物的大小表示为圆心为xk，yk，半径为r的圆，则路径点到障碍物的安全距离为r。则对于路径点Aji避开障碍物的程度为:

其中，k=1，2，…，q。

这样可以得出路径避开障碍物的亲和力函数:

综合以上结论，得到总体亲和力函数的计算公式:

其中，α，β为加权系数，调节加权系数可以改变亲和力函数中距离与避障所占的比例。

亲和力函数将实际约束条件有机地结合起来，计算比较简单。人工免疫算法的最终目标是选择亲和力高的抗体作为最优解的，在每一步操作中都以亲和力高作为优胜抗体的主要标准。

2 人工免疫算法在路径规划中的实现

文中将免疫系统中的优化机理概括为:选择、克隆扩增、受体编辑、骨髓产生新细胞。其中克隆扩增和受体编辑分别用来进行局部和全局搜索，骨髓产生新B细胞以增加群体的多样性。免疫进化算法的具体操作和步骤分为:选择、扩展、突变和替换［5］。

算法在路径规划中的具体实现包括以下具体操作:

(1)选择操作

随机产生n个实数编码的路径抗体作为初始群体A，编码采用 Lj={0，yi1，yi2，…，yji，…，yjn－1，0}的形式，并且按照公式fj=α/ftj1+β·ftj2计算其中每个路径抗体的亲和力。选出其中m个亲和力最高的个体组成群体B(其中m＜n)。

(2)扩展操作

模拟免疫系统的克隆扩增过程，构造一个小邻域，群体B中每个路径抗体在其小邻域内随机产生若干新路径抗体，m个路径抗体产生n个新路径抗体组成群体C。群体B中任意一个路径抗体Li的小邻域SN(vi)构造为:

其中Ω为可行解空间，‖·‖为欧几里德范数。SN(Li)是由与Li的欧氏距离不大于常数r的所有可行解构成，在解空间中是以Li为中心，以r为半径的球形区域。

B细胞的亲和力越高，其克隆扩增生成的子细胞就越多，因此用正比选择法实现亲和力越高的路径抗体扩展出越多的新路径抗体。设群体B中的路径抗体为L1，L2，…，Lm，亲和力值分别为f1，f2，…，fm，则每个路径抗体扩展新路径抗体的概率为:

(3)突变操作

构造一个较大邻域，群体C中亲和力最低的n－m个路径抗体中的每个抗体突变为其大邻域内的任一个抗体。突变后的路径抗体与群体C中未突变的路径抗体一起组成群体D。设路径抗体Lj进行突变操作，其大邻域构造为:

MN(Lj)在解空间中是以Lj为中心，以R为半径的球形区域。群体C中亲和力最低的n－m个路径抗体一定不会被选入下一代，对其进行突变操作，相当于在解空间的全局范围内进行大邻域搜索。

(4)替换操作

群体D中亲和力最低的J个路径抗体替换为随机路径抗体形成群体E。替换操作模拟骨髓产生新B细胞过程以增加群体多样性。

为了避免当前群体中最优抗体被扩展操作破坏掉以及保证算法收敛，算法采取最优个体保留策略。实现步骤如下:

(1)随机产生初始群体A0，令k=0;

(2)重复以下步骤，直到满足收敛准则。

a.计算当前群体Ak中的每个路径抗体的亲和力;

b.对群体Ak进行选择操作得到群体Bk;

c.对群体Bk进行扩展操作得到群体Ck;

d.对群体Ck进行突变操作得到群体Dk;

e.对群体Dk进行替换操作得到群体Ek;

f.群体Ek中评价值最低的路径抗体替换为Ak中亲和力最高的抗体，形成下一代群体Ak+1，令k=k+1。

(3)输出结果

在本文中，采用了限定迭代次数作为终止条件。

3 实验结果与结论

在移动机器人仿真软件RobotSoccer1.5a中进行静态环境仿真试验，设置算法的参数m=20、n=10、J=1，迭代次数为200代，图2和图3分别是算法中有无突变操作时的路径规划仿真结果。

从仿真结果可以看到，算法中的突变操作大范围的产生了新路径抗体，这样有利于算法在全局范围内进行寻优。同时，全局竞争可以粗略地搜索到抗体亲和力高的区域，而扩展操作随后可以进行细致地搜索并得到高精度的抗体解，这样可以有效避免算法过早收敛于局部值的“早熟”现象。

图2 不存在突变操作时的仿真图

图3 存在突变操作时的仿真图

实验仿真结果表明，把人工免疫算法用于移动机器人的路径规划中是有效和可行的，在实际应用时，要进一步深入考虑实时性和动态性，合理选择群体规模和迭代次数，注意改变亲和力函数以满足系统动态性能要求，从而达到路径规划的要求。

［1］钟碧良，张祺，杨宜民.基于改进势场法的移动机器人避障路径规划［J］.控制理论与应用，2003，20(4):623－626.

［2］唐平，李夏，杨宜民.移动机器人进行障碍物动态意图预测的研究［J］.控制理论与应用，2002，19(4):604－606.

［3］吴丽娟，徐心和.基于遗传算法的移动机器人比赛中障碍回避策略的设计［J］.机器人，2001，23(2):142－145.

［4］莫宏伟.人工免疫系统原理与应用［M］.哈尔滨:哈尔滨工业大学出版社，2002.

［5］左兴权，李士勇，黄金杰.一种新的免疫进化算法及其性能分析［J］.系统仿真学报，2003，15(11):1607－1609.