基于跳点搜索-遗传算法的自主移动机器人路径规划  

Path planning of autonomous mobile robot based on jump point search-genetic algorithm

作　　者：田雅琴[1] 胡梦辉 刘文涛 侯寅智 TIAN Yaqin;HU Menghui;LIU Wentao;HOU Yinzhi(School of Mechanical Engineering,Taiyuan University of Science and Technology,Taiyuan 030024,China)

机构地区：[1]太原科技大学机械工程学院,山西太原030024

出　　处：《工程设计学报》2023年第6期697-706,共10页Chinese Journal of Engineering Design

基　　金：国家自然科学基金资助项目(52005358);山西省重点研发项目(202102020101011);山西省应用基础研究面上自然基金(201901D111240);山西省回国留学人员科研资助项目(2016-095)。

摘　　要：为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump point search-genetic,JPSG)算法。JPSG算法利用JPS算法的高效局部搜索能力来提高整体搜索能力,加速算法整体收敛趋势;利用改进遗传算法的全局搜索能力改变JPS算法不能在复杂障碍物状况下解析最优路径的状态,提高算法对动态环境的适应性。在栅格矩阵中的路径规划仿真表明,相比于改进遗传算法、传统遗传算法,JPSG算法可以有效缩短寻优执行时间,提高寻优准确率,减少运算执行次数,在稳定性、准确性、快速性上具有明显的优势。The adaptive crossover operators and mutation operators were introduced to integrate the improved jump point search(JPS)algorithm with the adaptive genetic algorithm,solving the problems of multiple inflection points,susceptibility to getting stuck in local optima,large number of iterations,and long optimization time in the optimal path analysis of genetic algorithm.The jump point searchgenetic(JPSG)algorithm was obtained.JPSG algorithm used the efficient local search ability of JPS algorithm to improve the overall search ability and accelerate the overall convergence trend of the algorithm.The global search capability of improved genetic algorithm was used to change the state that JPS algorithm could not resolve the optimal path under complex obstacles,and improved the adaptability of the algorithm to dynamic environment.The path planning simulation in the grid matrix shows that compared with improved genetic algorithm and traditional genetic algorithm,JPSG algorithm can effectively shorten the optimization execution time,improve the optimization accuracy and reduce the operation execution times,and has obvious advantages in stability,accuracy and rapidity.

关 键 词：遗传算法 动态环境 自适应算子 跳点搜索算法 路径规划 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]