基于粒群行为与克隆的移动机器人进化路径规划
李枚毅, 蔡自兴
(中南大学 信息科学与工程学院, 湖南 长沙, 410083)
摘要: 针对移动机器人路径规划, 将粒群行为和生命科学中的免疫克隆原理、 进化算法相结合, 将过去进化过程中的经验通过粒群行为来体现, 提出了一种结合粒群行为和免疫克隆的移动机器人进化规划, 较快速地规划出性能是全局优化的可行路径。 分析了粒群行为的二种学习方式对路径规划的作用, 研究了通过调整粒群行为操作中的参数实现多路径规划。 通过仿真实验, 对上述算法进行了验证。
关键词: 移动机器人; 路径规划; 粒群行为; 克隆; 进化算法
中图分类号:TP278 文献标识码:A 文章编号: 1672-7207(2005)05-0739-06
Evolutionary path planning based on swarm behavior and clone for mobile robot
LI Mei-yi, CAI Zi-xing
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: An immune evolutionary planning algorithm with swarm behavior and clone for mobile robot, which combines clone principle in life science with swarm into evolutionary algorithm, was presented. Experiences (excellent individuals) in elapsed evolutionary process were stored by swarm behavior, and by means of swarm behavior and clone, evolutionary algorithms could quickly plan global-optimal path. Relation of learning approaches in swarm behavior and performs of path planning was analyzed, and the multi-path planning could be attained by means of adjusting parameters in the operator of swarm behavior. The simulating experimental results show that the algorithms will improve performance of path planning for mobile robot.
Key words: mobile robot; path planning; swarm behavior; clone; evolutionary algorithms
移动机器人进化导航任务之一是运用进化计算规划出能避开障碍物的安全的最优路径。
由于已有的用于研究路径规划研究成果如构型空间法、 人工势场法、 可视图法等, 都存在不同程度的不足, 因此, 进化计算进行机器人规划和导航成为研究热点[1-5]。 但进化计算也有其不足, 主要是进化算法方式收敛速度较慢, 经常要耗费大量的机器时间, 达不到在线规划和实时导航的要求。 如果仅采用选择、 交叉和变异的标准进化计算进行路径规划, 理论上说使用最优保存策略时能以概率1进化出最佳路径, 但进化代数太大。 通常, 基于进化的路径规划和导航都考虑了机器人导航特点, 设计了新的进化算子。
粒群算法是一种基于群体搜索的算法[6-8], 建立在模拟鸟群社会行为的基础上。 一个粒子的搜索行为受到群体中其他粒子的搜索行为的影响。 粒子的行为是一种共生合作行为, 同时, 由于记忆了粒子过去的最好位置, 因此, 具备对过去经验的简单学习能力。
将免疫机制引入进化算法[9]是近年来的研究发展趋势之一, 将免疫机制的优点和进化算法的优点进行结合, 能够提高进化算法的性能。
作者针对移动机器人路径规划问题, 将生命科学中的克隆原理[10,11]、 模仿鸟群的粒群方法和进化算法[12-17]相结合, 构造一类粒群、 克隆和进化算法相结合的混合进化算法, 提高移动机器人进化路径规划的性能。
1 机器人免疫进化导航算法
1.1 个体的编码方法
一条路径是从起点到终点、 由若干线段组成的折线, 线段的端点叫节点(用平面坐标(x,y)表示), 绕过了障碍物的路径为可行路径。 一条路径对应进化种群中的一个个体, 一个基因用其节点坐标(x,y)和状态量组成的表来表示, b刻画节点是否在障碍物内和本节点与下一节点组成的线段是否与障碍物相交, 以及记录使用绕过障碍物的免疫操作状态。 个体X可表示如下:
X={(x1, y1,b1), (x2,y2,b2),…,(xn,yn,bn)}
其中: (x1,y1)和(xn,yn)是固定的, 分别表示起止点坐标。
群体的大小是预先给定的常数N, 按随机方式产生n-2个坐标点(x2,y2), …, (xn-1, yn-1)。
1.2 适应度函数
本文讨论的问题是求一条最短路径, 要求路径与障碍物不交, 并保证机器人能安全行驶。 据此适应度函数可取为:
F(X)=fdist(X)+r
(X)+cφ(X)。(1)
其中: r和c为正常数; 
, 为路径总长; d(mi,mi+1)为两相郊节点mi和mi+1之间的距离; φ(X)为路径与障碍物相交的线段个数; 
, 为节点的安全度; Ci用于衡量障碍物的排斥力, 定义如下:
其中: gi为线段mimi+1到所检测到的障碍物的距离; τ为预先定义的安全距离参数, 本文实验中机器人尺寸取为8。
1.3 操作算子
a. 交叉算子[5]: 由选择方式选择2个个体, 以二者中较短的1个的节点数为取值上限, 以1为下限, 产生1个服从均匀分布的随机数, 以此数为交叉点, 对2个个体进行交叉操作。 记交叉操作的概率为pc。
b. 克隆算子: 对每一个个体, 以这个个体作为父本, 在其上随机选1个节点(非起点和终点), 将此节点的x坐标和y坐标分别用全问题空间内随机产生的值代替。 对每一个父本, 用这个产生节点的方法克隆Nc个子本, 从这Nc个子本和父本组成的Nc+1个样本中选择最优1个样本和从中随机再选择一个样本进入下一个进化操作阶段。
c. 粒群行为算子: 每个个体按照粒子行为进行操作。
d. 免疫算子: 绕过挡住了道路的障碍物的操作, 如图1所示。
图 1 免疫算子
Fig. 1 Immune operator
从机器人运动角度分析, 直线运行是最理想的, 随着环境的复杂化, 运行的路线随之复杂化, 特别是转角大的点, 运动控制难度变大, 前进速度变小。 为了提高路径光滑度, 转角大的点(用曲率来度量)要裁角。 绕过障碍物的免疫操作产生的路径上的节点有时前后顺序错位, 需要交换某些节点的前后顺序; 有时有多余的节点, 需要删除。 为此, 使用了文献[5]中的交换算子和删除算子。
1.4 粒群行为算子
将每个个体作为1个粒子, 按如下的粒子行为进行操作。 记种群中的个体(或者叫粒子)为Xi(t), 其适应度值为Fit(Xi(t))。 记Xi(t)至今有过的最好适应度为Ibesti, 全局最佳个体的最好适应度为Gbest。
a. 比较每个个体当前第t代适应度与它至今有过的最好适应度Ibesti, 如果Fit(Xi(t))〈Ibesti, 那么,
b. 把每个个体的性能与全局最佳个体的适应度Gbest进行比较, 如果F(Xi(t))〈Gbest, 那么,
c. 个体的行动速度为:
其中: ρ1和ρ2为随机变量。 ρ1和ρ2确定为ρ1=r1c1, ρ2=r2c2。 r1, r2~U(0,1), 而c1和c2为正加速度常数, U(0, 1)是[0,1]上的均匀分布参数。
d. 把每个个体按下式进行调整:
Xi(t+1)=Xi(t)+vi(t+1)。(6)
计算中对于节点个数不相同的情况, 以节点个数较小的项作为基准, 舍去节点个数较多的项中的节点。 实验时, vi(0)取为0。
1.5 算法描述与免疫算子分析
1.5.1 算法描述
在进行免疫操作的接种疫苗后进行免疫选择[8], 就是将免疫操作产生的个体X′与其父本X进行比较。 若适应度得到改进, 则替代其父本, 否则按概率p(X)=exp((F(X)-F(X′))/Tk替代其父本。 在本文实验中, 免疫选择中Tk取为Tk=1/ln(k+1)。 其中, k是进化代数。
基于粒群行为和免疫克隆的移动机器人进化路径规划算法为:
a. 初始化群体;
b. 评价群体的适应度;
c. 若不满足停机条件则循环执行:
{
d. 选择操作;
e. 交叉操作;
f. 克隆操作;
g. 粒群行为操作;
h. 删除算子操作;
i. 用免疫操作接种疫苗;
j. 免疫选择;
k. 评价群体的适应度;
l. 将上一代中最优的个体加入种群;
m. 淘汰部分个体, 保持种群规模;
}
n. 输出种群中的最优个体。
为了方便, 称此算法为SBICEPP算法。
1.5.2 免疫算子
从整个免疫进化算法的算子构造来看, 免疫算子主要作用是局部性的, 进化算法是起全局作用的, 因此, 本文构造的算法是全局收敛性能较好的进化算法和局部优化能力较强的免疫算子的结合; 从个体适应度提高能力来分析, 结合式(1), 绕过障碍物的免疫算子能将不可行路径变换为可行路径, 裁角算子能使运动路径变得更光滑, 但对不可行路径进行光滑化的免疫操作, 其意义小于可行路径进行光滑化, 这可从式(1)的系数确定上体现出来。 在这种情况下, 不可行路径进行光滑化的免疫操作概率应当小于绕过障碍物的免疫操作概率。
如果都是可行路径, 进行光滑化的免疫操作概率将适当增大。
状态b中保存了绕过障碍物的免疫操作的记录, 指明光滑化和删除节点操作的使用频率, 绕过障碍物的免疫操作产生的几个节点, 在其后的几代进化中, 应当使用较大的概率进行删除操作和光滑化操作。
状态b由如下几个部分组成: 本节点到下一节点组成的线段是否与障碍物相交; 绕过障碍物的免疫操作记录, 若此节点在当代使用绕过障碍物的免疫或I型变异操作, 则置此处为某个整数k(后面的仿真实验中k=6), 若是II型变异操作, 则置此处为k/2; 若使用了光滑化和删除节点操作, 则此值减1; 当此值为0时, 进行光滑化和删除节点操作的概率为pd0(仿真实验取0.2),否则为pd1(仿真实验取0.8)。
2 仿真实验
对于图2所示的环境, 进行仿真实验。 图2中位于左边的小方块是机器人的起始位置(S), 对应地, 右边的小方块是终止位置(G)。
各分别进行50次仿真实验, 记录已收敛到全局最优解时的收敛代数, 然后计算平均收敛代数、 最快收敛代数和解的平均适应值。
将50次仿真实验运行的结果列在表1中, 可看出本文构造的算法收敛速度较快。
仿真时种群规模为30, 粒群行为操作概率和疫苗接种操作概率分别为0.3, 交叉概率pc和克隆概率pm按如下适应性概率计算公式进行适应性调整:
其中: fav和fmin分别为种群的平均适应度和最小适应度; f′为用于交叉操作的2个个体中较小的适应度。
个体选择的概率按下式计算:
其中: j=1, …, N; 0〈q〈1; N为种群规模。 概率最大值是最优个体的选择概率。 实验时取q=0.6(图2)。
图 2 进化路径规划结果
Fig. 2 Result of evolutionary path planning
删除和交换概率分别为0.4和0.6, r=2000, c=5000, τ=0.6。 Nc取为10, 粒群行为操作的c1和c2分别取为0.5。 仿真在Matlab 6.1下进行, 机器是PIII 850, 内存为128 Mb。 进行比较的其他算法的参数采用文献中的相关设置。
表 1 4个基于进化机制的路径规划算法的结果对比
Table 1 Comparison of four path planning algorithms based on evolutionary mechanism
表1所示数据说明本文提出的结合粒群行为和免疫疫苗接种的进化路径规划算法的性能比其他3种进化有关的路径规划算法好。
3 粒群自我学习与多路径规划
本文使用的粒群行为操作由2部分组成: 粒群自我学习(由式(3)体现)和粒群向最优者学习(由式(4)体现)。 粒群自我学习的结果是个体向自己历史上最优秀的位置运行, 体现了个体自我发展, 这将导致进化种群具有较好的多样性。 粒群粒群向最优者的结果是种群中所有个体都向同一个位置运行, 体现了种群的统一性, 这将导致进化种群多样性下降。
多路径规划是近几年一些研究者的研究课题, 其研究原因在于地图并不能完全保持与环境一致, 或者由于某些意外因素致使原来规划的路径不可通行, 需要备用路径。 例如医院走廊上担任向导的机器人, 由于走廊被突发事件堵住了, 就需要其他的通道; 公路上担任运输的自主车由于发生交通事故, 需要走其他路线。 在这些情况下, 就需要多路径规划, 将规划好的多条路径储存, 在需要的时候, 按环境情况从多条路径中选择1条给机器人。
多路径规划与进化计算的多样性相关联, 多样性大, 表示种群中个体之间有较大的差别。 对于路径规划问题, 就是种群中存在多条不同的运行路径。 若进化计算运行结束时, 种群中仍存在足够多的不同运行路径, 几乎包括了所有可能的路径, 则达到了多路径规划的目标。
为了达到多路径规划的目标, 结合前面粒群行为2种学习能力的分析, 提出如下的参数调整策略: 粒群行为操作的c1和c2分别取不同的值; 体现自我学习能力的乘子c1取较大的值; 相反地, c2取较小的值; 同时使用较小的选择压力, 也就是说, 个体选择的概率式(9)中q取较小的值, 因为q较小, 减弱了选择压力对多样度的负面影响。
为了检验上述参数调整策略的可行性, 进行了多路径规划的仿真。 图3所示为种群中已经进化到能够避开所有障碍物的部分路径, 它们基本上概括了所有可能的路径(有些障碍物之间距离太小, 因此没有路径经过), 而且路程短的路径多一些。 图4所示为种群中一些仍在继续进化着的路径, 它们还不是可行路径, 不同程度地与障碍物相交。 这个仿真例子说明, 通过合理的参数调整, 种群在进化过程中, 个体能够较多地体现自我发展与个性化进化, 一些个体进化快, 而另有一些个体进化慢, 既保证了个体的相对集中性(路程短的个体多一些), 又保证了个体的覆盖率(基本上包含了所有可能的路径)。
图 3 多路径规划结果(A)
Fig. 3 Result (A) of multi-path planning
图 4 多路径规划结果(B)
Fig. 4 Result (B) of multi-path planning
实验时, 粒群行为操作中的参数c1和c2分别取为0.9和0.1。 式(9)中q=0.2, 其他参数的设置与前面的相同。
4 结 论
a. 针对移动机器人规划与导航任务的特点, 按自然免疫系统中的克隆机制构造克隆操作; 同时, 构造了免疫疫苗接种算子, 按模拟退火原理构造了免疫选择算子。
b. 模仿粒群行为, 构造了粒群行为操作, 达到种群中个体之间的相互促进和对过去经验的简单学习。
c. 研究了粒群行为的2种学习与多路径规划之间的关系, 指出通过调整粒群行为的参数实现多路径规划。
d. 利用仿真实验对算法进行了验证, 并和其他一些算法进行了比较, 证实了本文构造的算法能有效而较快速地规划出安全的全局(次)最优导航路径和达到多路径规划的要求。
参考文献:
[1]Nachol C. Time-optimal path planning and control using neural networks and a genetic algorithm[J]. International Journal of Computational Intelligence and Applications, 2002, 2(2): 153-172.
[2]李枚毅, 蔡自兴. 改进的进化编程及其在机器人路径规划中的应用[J]. 机器人, 2000, 22(6): 490-494.
LI Mei-yi, CAI Zi-xing. Improved evolutionary programming and its application on path planning of robots[J]. Robot, 2002, 22(6): 490-494.
[3]Xiao J, Michalewisz Z, Lin H S. Evolutionary planner/navigator: operator performance and self-tuning[A]. Koza J R. Proc IEEE Int Conf Evolutionary Computation[C]. Nagoya: IEEE, 1996. 366-371.
[4]Prahlad V, Kay C T, Wang M L. Evolutionary artificial potential fields and their application in real time robot path planning[A]. IEEE Computer Society. Proceedings of the IEEE Conference on Evolutionary Computation[C]. California: IEEE, 2000. 256-263.
[5]周翔. 移动机器人自主导航的进化控制理论及其系统平台的开发与应用研究[D]. 长沙: 中南工业大学自动控制系, 1999.
ZHOU Xiang. Research on the Theory of Evolutionary Control for Navigation of Autonomous Mobile Robot with Development and Application of Its System Platform[D]. Changsha: Department of Automation Control, Central South University of Technology, 1999.
[6]Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proc IEEE International Conference on Neural Networks[C]. Perth: IEEE, 1995. 1942-1948.
[7]Eberhart R, Shi Y, Kennedy J. Swarm Intelligence[M]. San Francisco: Morgan Kaufmann, 2001.
[8]蔡自兴, 徐光祐. 人工智能及其应用(第3版)[M]. 北京: 清华大学出版社, 2004.
CAI Zi-xing, XU Guang-you. Artificial Intelligence: Principles and Applications(3rd Edition)[M]. Beijing: Tsinghua University Press, 2004.
[9]Jiao L C, Wang L. A novel genetic algorithm based on Immunity[J]. IEEE Trans on Systems, Man, And Cybernetics-Part A: Systems and Humans, 2000, 30(5): 552-561.
[10]Roitt I M, Delves P J. Essential immunology(10th Edition)[M]. London: Blackwell Science Inc, 2001.
[11]陆德源, 马宝骊. 现代免疫学[M]. 上海: 上海科学技术出版社, 1998.
LU De-yuan, MA Bao-li. Modern Immunology[M]. Shanghai: Shanghai Scientific and Technical Press, 1998.
[12]陈国良, 王煦法, 庄镇泉,等. 遗传算法及其应用[M]. 北京:人民邮电出版社, 1996.
CHEN Guo-liang, WANG Xi-fa, ZHANG Zheng-quan, et al. Genetic Algorithms and Application[M]. Beijing: Post and Telecommunication Press, 1996.
[13]周明,孙树栋. 遗传算法原理及应用[M]. 北京: 国防工业出版社, 1999.
ZHOU Ming, SUN Shu-dong.Genetic Algorithms: Theory and Applications[M]. Beijing: National Defence Industry Press, 1999.
[14]Goldberg D E.Genetic Algorithms in Search, Optimization and Machine Learning, Reading[M]. MA: Addison-Wesley, 1989.
[15]Srinvas M, Patnai L M. Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans Syst, Man, and Cybern, 1994, 24(4): 656-666.
[16]Cao H, Yu J, Kang L, et al. Modeling and prediction for discharge lifetime of battery systems using hybrid evolutionary algorithms[J]. Comput Chem, 2001, 25(3): 251-259.
[17]Hafner C, Frohlich J. Generalized function analysis using hybrid evolutionary algorithms[A]. Angeline P J. Proceedings of the Congress on Evolutionary Computation[C]. Piscataway: IEEE,1999. 287-294.
收稿日期:2005-01-28
基金项目:国家自然科学基金资助项目(60234030, 60404021)
作者简介:李枚毅(1962-), 男, 湖南湘乡人, 博士研究生, 副教授, 从事智能计算、 图像识别、 智能机器人研究
论文联系人: 李枚毅, 男, 副教授; 电话: 0731-8830583(O); E-mail: meiy_li@yahoo.com.cn
