李欢++唐江锋++刘伟

[摘 要]细菌觅食算法是一种仿生学寻优算法。本文根据传统的细菌算法，对其与力场相结合，应用于机器人路径规划领域。机器人在引力的作用下以定步长变方向向目标点运动，引入斥力作为躲避避障物的条件，引进迭代终止条件，并通过仿真实验验证了其可行性。

[关键词]细菌觅食算法；路径规划；力场

中图分类号：TP301.6 文献标识码：A 文章编号：1009-914X（2016）03-0122-01

1.引言

路径规划[1]是移动机器人设计领域中的核心技术之一。移动机器人路径规划是指在有一定障碍物的环境条件中，找到一条从给定起点到目标点的适当路径，使机器人能够安全无碰的绕过所有障碍物。机器人路径规划一般分为全局路径规划和局部路径规划两种。全局路径规划是指环境信息已知，从起点到目标点的无碰路径规划，常用的全局路径规划算法有可视图法、栅格法[2]、自由空间法等。局部路径规划是指环境信息未知，机器人根据传感器检测到的环境信息，实时在线的调整机器人行走路线，最终安全无碰的到达目标点，常用的局部路径规划算法有人工势场法[3]、模糊算法、蚁群算法、粒子群算法以及遗传算法等。

近年来，基于人工智能的仿生学算法，逐步融合甚至取代传统算法应用于机器人路径规划领域。比如，模仿蚂蚁觅食行为而提出的蚁群算法根据蚂蚁觅食过程中释放的信息素浓度寻找最优路径；遗传算法根据生物学中自然界物竞天择适者生存的规律演化而来的启发式随机搜索算法。细菌算法[4]是近几年出现的仿生学算法，它是根据细菌的觅食行为提出的，由于其与机器人路径寻优有很大的相似性，故本文把细菌算法引入机器人路径规划领域，并通过仿真实验验证了其可行性。

2.基于细菌觅食算法的路径规划

2.1 细菌觅食算法

细菌觅食算法，又称细菌觅食优化算法，它是由K.M.Passino在2002年根据大肠杆菌在人体肠道内的觅食行为提出的，该算法由于具有群体智能并行搜索、易跳出局部极小值等优点，成为生物启发式搜索算法领域的研究热点。在人体中，大肠杆菌周身长满鞭毛，大肠杆菌通过体表鞭毛的摆动达到在环境中移动的目的。当大肠杆菌聚集区的食物消耗殆尽，细菌便会随机选择一个方向运动，以寻找新的食物源，如果食物丰富便会停下来，直到食物消耗殆尽，细菌便会沿着上一次的方向继续向前运动；若是遇到无法通行的地方或者找寻一段距离未发现食物，细菌便会改变搜索方向，重新寻找食物。如果食物丰富能够满足细菌的繁殖需要，细菌便会进行个体的分裂，壮大菌落；若是食物稀少细菌变化死亡。根据大肠杆菌的这种觅食行为，提出细菌觅食算法，其运动方式主要有：趋化、复制和驱散三个步骤。

趋化是指细菌向食物营养富集的地方运动的过程，趋化过程由游动和翻转两个动作组成。游动是指细菌向指定方向运动一定的距离；翻转是指改变细菌游动的方向。在细菌觅食算法中，用P（i，j，k，l）代表第l次驱散第k次复制第j次趋化运动中第i个细菌的位置坐标。C（i，k）表示单位游动步长。因此，在每一次的趋化运动中，细菌的位置可表示为：

其中，Δ（i）表示细菌的游动的方向，可根据round函数随机产生，亦可根据目标性能自行设定。

复制操作是指在完成趋化操作时，细菌进行繁衍。在细菌繁殖前，对每个细菌个体进行健康度评定。保留健康度较好的半数细菌，并将这些细菌一分为二分裂复制，复制后保留母细菌的特性，即保留运动方向和运动步长，健康度较差的半数细菌便被淘汰。细菌健康度评价公式为：

其中，Nc表示细菌趋化的次数。

在细菌完成趋化和复制操作后，经行消除和驱散操作。去除掉在复制过程中健康值较差的半数细菌，再以某一规则选取经过复制操作的细菌，将其驱散到其他位置，这样，被驱散的细菌便有了新的位置，可以进行新的觅食行为。通过细菌驱散操作，减少了细菌陷入局部最优解的可能性，但也驱散了接近全局最优解的部分细菌。

2.2 改进细菌觅食算法路径规划

在机器人路径规划领域中，一方面要保证机器人能够持续向目标位置运动，另一方面要保证机器人避开所走路径上的所有障碍物，同时，要尽可能的使机器人走过的总路程最短。为保证细菌能够持续向目标运动，引入引力作为其适应度函数：

式中，α为引力系数，d（P，T）为当前细菌所处位置与目标点位置的距离。细菌在引力的作用下持续向目标点运动，当细菌到达目标点以后，引力为零，细菌停止运动，进行复制、驱散操作。

为保证细菌在运动过程中能够有效的避开障碍物，引入斥力函数进行障碍物的躲避，障碍物大小对细菌的影响程度不同，障碍物越大，则对细菌的阻碍越大，设置斥力函数为：

式中，Radius 表示障碍物的最大半径，即为障碍物中心到四周最远点距离；Raffect 表示障碍物的影响距离。根据斥力的大小情况，细菌实时调整运动方向，有效避开障碍物。

3 仿真实验及其结果

为验证上述方法的正确性和有效性，利用Matlab7.0软件进行仿真实验。在实验中，小圆圈形表示起始点，小正方形表示目标位置，小六边形表示细菌。仿真参数设置为：细菌个数为s=26，细菌趋化次数Nc=100，复制次数为Nre=4，驱散次数为Ned=2，障碍物中心坐标为xo=[3.5 2 6 7 7 9]，yo=[3 5 5 8 10 5 ]，障碍物半径Radius=[0.4 0.3 0.6 0.5 0.5 0.5]，障碍物影响距离Raffect=1，d_att、h_rep、om_att和om_rep均为0.05，细菌运动起点为[0 0]，运动目标点为[10 10]，为保证细菌能够尽可能的找到所有路径，其运动步长与方向均为随机值。

实验结果如图1、图2所示。图1是细菌进行趋化操作，寻找到达目标点的安全路径，细菌随机选择运动方向，寻找尽可能的能够到达目标点的路径，从而避免了因单一目标陷入局部最小值不能到达目标点的情况。图2是从所有路径中选出来的最优路径，路径中在小范围内存在许多的弯曲点，对其进行逼近，便可得到一条光滑的、最优的路径。通过仿真实验，说明本文采用的细菌觅食算法能够安全无碰的到达目标点，寻找出一条最优路径，完成机器人路径规划的要求。

4 结论

本文采用的改进细菌觅食算法采用引力场作为适应度函数，引入障碍物大小与影响距离作为排斥力，分步寻找最优路径的方法，具有能够快速的找到一条安全无碰的最优路径的能力，能够很好的用于机器人路径规划，本算法采用的静态仿真环境，同样也可以应用与动态环境的避障研究。在以后的研究中，还可以对其操作步骤进行优化，与其他算法相结合，进一步提高其可行性和可靠性。

参考文献

[1] 曲道奎， 杜振军， 徐殿国， 等. 移动机器人路径规划方法研究[J]. 2008.

[2] Lee. Visibility of a simple polygon[J]. Computer version， Graphics and Image processing， 1983，2292）：207-221.

[3] Yogita Gigras， Kusum Gupta. Artificial Intelligence in Robot Path Planning[J].International Journal of Soft Computing and Engineering.2012（2）：171-174.

[4]吴晓涛，孙增圻.用遗传算法进行路径规划.清华大学学报（自然科学版）， 1995， 35（5）： 14-19.