基于改进遗传算法的机器人路径规划

徐梦颖,王娇娇,刘宝,马良,柴林杰,向丽,周杰

(石河子大学信息科学与技术学院,新疆 石河子832003)

提高路径规划效率逐渐成为移动机器人领域中的研究热点,其任务在于已知起点和终点,探寻出一条无碰撞的最优路径[1-3]。遗传算法是现今应用最为广泛的最优解处理算法[4-6],传统算法容易陷入局部最优解,通过改进传统遗传算法提升机器人路径规划效率[8-9]。解决路径规划的问题,首先要对环境进行建模[10-13],栅格法是研究人员解决机器人路径规划问题并建立环境模型使用的主要方法[14-15]。目前,一些学者提出了许多智能算法,ZHANG J H[16]使用粒子群算法(Particle Swarm Optimization,PSO)提高运动效率,该算法能够有效优化路径长度、路径的平滑度和安全程度,然而算法容易出现早熟收敛的问题;巩敦卫等[17]提出了一种模拟退火算法(Simulated Annealing,SA)能有效避免节点布置中一些路径暴露问题;混合遗传算法容易陷入进化停滞,导致得到的解集质量较低。

为了解决寻找最短路径时存在解的质量较低的问题,本文提出一种免疫克隆自适应遗传算法(Immune Clone Adaptive Genetic Algorithm,ICAGA),通过建立栅格模型对栅格进行编码,再进行选择、交叉、变异,计算出最短路径,并使用Matlab对其进行仿真实验验证,并与SA、PSO进行比较。

1 基于ICAGA的最优路径规划

1.1 路径规划模型

路径规划是指如何让移动机器人依照特定指标完成从起始点到终点而且能够避开途中障碍物的一种技术。栅格法是解决路径规划问题的重要方法[18],机器人所处的栅格有可行动栅格和障碍栅格2种。……