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

doi:10.3785/j.issn.1006-754X.2023.03.136

工程设计学报

2023, Vol. 30

Issue (6): 697-706 DOI: 10.3785/j.issn.1006-754X.2023.03.136

机器人与机构设计

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

田雅琴(

),胡梦辉,刘文涛,侯寅智

太原科技大学机械工程学院，山西太原 030024

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

Yaqin TIAN(

),Menghui HU,Wentao LIU,Yinzhi HOU

School of Mechanical Engineering, Taiyuan University of Science and Technology, Taiyuan 030024, China

全文: PDF(7497 KB) HTML

摘要：

为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题，引入自适应交叉算子和变异算子，将改进后的跳点搜索（ $j u m p ? p o i n t ? s e a r c h$ ）算法与改进遗传算法融合，得到跳点搜索-遗传（ $j u m p ? p o i n t ? s e a r c h - g e n e t i c$ ，JPSG）算法。JPSG算法利用 $J P S$ 算法的高效局部搜索能力来提高整体搜索能力，加速算法整体收敛趋势；利用改进遗传算法的全局搜索能力改变 $J P S$ 算法不能在复杂障碍物状况下解析最优路径的状态，提高算法对动态环境的适应性。在栅格矩阵中的路径规划仿真表明，相比于改进遗传算法、传统遗传算法， $J P S G 算法$ 可以有效缩短寻优执行时间，提高寻优准确率，减少运算执行次数，在稳定性、准确性、快速性上具有明显的优势。

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

Abstract:

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 search-genetic (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.

Key words: genetic algorithm dynamic environment adaptive operator jump point search algorithm route planning

收稿日期: 2023-03-22 出版日期: 2024-01-02

CLC:

TP 242

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

作者简介: 田雅琴（1976—），女，副教授，山西介休人，硕士生导师，博士，主要从事机械设计及制造以及金属材料微成型方面的研究, E-mail: tianyaqin@tyust.edu.cn, http://orcid.org/0000-0002-1803-8432

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	田雅琴
	胡梦辉
	刘文涛
	侯寅智

引用本文:

田雅琴,胡梦辉,刘文涛,侯寅智. 基于跳点搜索-遗传算法的自主移动机器人路径规划[J]. 工程设计学报, 2023, 30(6): 697-706.

Yaqin TIAN,Menghui HU,Wentao LIU,Yinzhi HOU. Path planning of autonomous mobile robot based on jump point search-genetic algorithm[J]. Chinese Journal of Engineering Design, 2023, 30(6): 697-706.

链接本文:

https://www.zjujournals.com/gcsjxb/CN/10.3785/j.issn.1006-754X.2023.03.136 或 https://www.zjujournals.com/gcsjxb/CN/Y2023/V30/I6/697

图1 30×30的栅格矩阵示意图

图2 斜线强制邻居示意图

图3 直线强制邻居示意图

图4 跳点搜索示意图

图5 JPSG算法流程图

图6 基于传统JPS算法的路径规划结果

图7 基于改进JPS算法的路径规划结果

图8 静态环境下路径规划的仿真结果

图9 静态环境下规划路径长度的仿真结果

算法	规划路径长度	准确率/%	收敛迭代数/次	规划时间/s	方差
$J P S G 算法$	$43.399 ? 5$	$95$	$15$	$7.9$	$0.103$
改进遗传算法	$43.937 ? 1$	$55$	$36$	$8.9$	$0.147$
传统遗传算法	$44.072 ? 6$	$50$	$40$	$9.3$	$0.149$

表1 静态环境下算法性能对比

图10 基于JPSG算法的路径规划结果

算法	规划时间/s	路径长度	拐点总数量/个
传统 $R R T$ 算法	0.707 3	38.85	38
改进 $R R T$ 算法	0.092 5	41.25	15
$D i j k s t r a$ 算法	4.674 8	27.31	—
$R R T - D i j k s t r a$ 算法	0.915 0	31.37	6
$J P S$ 算法	0.228 5	27.31	6
$J P S G 算法$	1.432 5	27.31	6

表2 JPSG算法与文献[22]中算法的性能对比

算法	规划路径长度	规划时间/s
遗传算法	31.67	20.540 0
改进遗传算法	31.34	20.120 0
改进遗传-鲸鱼融合算法	30.34	19.570 0
$J P S$ 算法	28.04	0.273 6
$J P S G 算法$	28.04	1.372 4

表3 JPSG算法与文献[23]中算法的性能对比

图11 在静态和动态环境下路径规划仿真结果的对比

图12 机器人遇到第1，2个动态障碍物后的路径规划示意

图13 动态环境下规划路径长度的仿真结果

算法	规划路径长度	准确率/%	收敛迭代数/次	规划时间/s	方差
$J P S G$ 算法	$44.100 ? 6$	$82$	$19$	9.1	$0.142$
改进遗传算法	$44.956 ? 7$	$53$	$39$	10.4	$0.286$
$传统遗传算法$	$45.280 ? 3$	$42$	$42$	10.6	$0.293$

表4 动态环境下不同算法的性能对比结果

1	王雷，李明. 改进自适应遗传算法在移动机器人路径规划中的应用［J］. 南京理工大学学报：自然科学版， 2017， 41（5）： 627-633. doi：10.14177/j.cnki.32-1397n.2017.41.05.015 WANG L， LI M. Application of improved adaptive genetic algorithm in mobile robot path planning ［J］. Journal of Nanjing University of Science and Technology： Natural Science Edition， 2017， 41（5）： 627-633. doi: 10.14177/j.cnki.32-1397n.2017.41.05.015
2	王雷，李明，唐敦兵，等. 基于改进遗传算法的机器人动态路径规划［J］. 南京航空航天大学学报， 2016， 48（6）： 841-846. doi：10.16356/j.1005-2615.2016.06.010 WANG L， LI M， TANG D B， et al. Dynamic path planning for mobile robot based on improved genetic algorithm ［J］. Journal of Nanjing University of Aeronautics and Astronautics， 2016， 48（6）： 841-846. doi: 10.16356/j.1005-2615.2016.06.010
3	王涛，喻韬. 一种基于遗传模拟退火算法的通信卫星资源规划方法［J］. 无线电工程， 2021， 51（8）： 767-772. doi：10.3969/j.issn.1003-3106.2021.08.015 WANG T， YU T. A communication satellite resource planning method based on genetic simulated annealing algorithm ［J］. Radio Engineering， 2021， 51（8）： 767-772. doi: 10.3969/j.issn.1003-3106.2021.08.015
4	LI Y H， HUANG Z H， XIE Y. Research status of mobile robot path planning based on genetic algorithm ［J］. Journal of Physics Conference Series， 2020， 1544（1）： 012021.
5	杨恒，李越，孙寒挺，等. 路径最优的移动机器人路径规划研究［J］. 机械设计， 2022， 39（8）： 58-67. YANG H， LI Y， SUN H T， et al. Research on path planning of mobile robot with optimal path ［J］. Mechanical Design， 2022， 39（8）： 58-67.
6	CHEN Z Q， ZHOU J H， SUN R Z， et al. A new evolving mechanism of genetic algorithm for multi-constraint intelligent camera path planning［J］. Soft Computing， 2021， 25（27）： 1-20.
7	鲁婷婷，冯彦翔，闫振龙. 一种健康管理机器人协同任务分配方法［J］. 无线电工程， 2022， 52（7）： 1276-1283. doi：10.3969/j.issn.1003-3106.2022.07.022 LU T T， FENG Y X， YAN Z L. A cooperative task allocation method for health management robots［J］. Radio Engineering， 2022， 52（7）： 1276-1283. doi: 10.3969/j.issn.1003-3106.2022.07.022
8	黄维，刘惟伊，刘志恩，等. 基于多目标遗传算法的实验目标车底盘结构优化［J］. 工程设计学报， 2021， 28（1）： 80-88. doi：10.3785/j.issn.1006-754X.2021.00.012 HUANG W， LIU W Y， LIU Z E， et al. Structural optimization of experimental target vehicle chassis based on multi-objective genetic algorithm ［J］. Journal of Engineering Design， 2021， 28（1）： 80-88. doi: 10.3785/j.issn.1006-754X.2021.00.012
9	董炫良，赵桂清. 人工势场引导蚁群算法的机器人导航路径规划［J］. 机械设计与制造， 2021（6）： 169-173. doi：10.3969/j.issn.1001-3997.2021.06.039 DONG X L， ZHAO G Q. Robot navigation path planning based on ant colony algorithm guided by artificial potential field ［J］. Mechanical Design and Manufacturing， 2021（6）： 169-173. doi: 10.3969/j.issn.1001-3997.2021.06.039
10	孙鹏耀，黄炎焱，潘尧. 基于改进势场法的移动机器人路径规划［J］. 兵工学报， 2020， 41（10）： 2106-2121. doi：10.3969/j.issn.1000-1093.2020.10.021 SUN P Y， HUANG Y Y， PAN Y. Path planning of mobile robots based on improved potential field algorithm［J］. Journal of Military Industry， 2020， 41（10）： 2106-2121. doi: 10.3969/j.issn.1000-1093.2020.10.021
11	CHEN X A， GAO P J. Path planning and control of soccer robot based on genetic algorithm ［J］. Journal of Ambient Intelligence and Humanized Computing， 2019， 11（12）：1-10.
12	成彬，景冰雪. 基于细菌觅食和蚁群算法的工艺路线优化［J］. 工程设计学报， 2020， 27（5）：600-607， 624. doi：10.3785/j.issn.1006-754X.2020.00.073 CHENG B， JING B X. Process route optimization based on bacterial foraging and ant colony algorithm ［J］. Journal of Engineering Design， 2020， 27（5）： 600-607， 624. doi: 10.3785/j.issn.1006-754X.2020.00.073
13	刘二辉，姚锡凡. 基于改进遗传算法的自动导引小车路径规划及其实现平台［J］. 计算机集成制造系统， 2017， 23（3）： 465-472. doi：10.13196/j.cims.2017.03.003 LIU E H， YAO X F. AGV path planning based on improved genetic algorithm and implementation platform ［J］. Computer Integrated Manufacturing System， 2017， 23（3）： 465-472. doi: 10.13196/j.cims.2017.03.003
14	ZHOU K J， YU L L， LONG Z W， et al. Local path planning of driverless car navigation based on jump point search method under urban environment ［J］. Future Internet， 2017， 9（3）： 51-51.
15	张许有，刘有余. 基于位置代价A算法的机械臂避障路径规划［J］. 机械设计， 2021， 38（2）： 108-113. ZHANG X Y， LIU Y Y. Path planning of obstacle avoidance for manipulators based on position cost A algorithm ［J］. Mechanical Design， 2021， 38（2）： 108-113.
16	杨博，刘树东，鲁维佳，等. 改进遗传算法在机器人路径规划中的应用［J］. 现代制造工程， 2022（6）： 9-16. YANG B， LIU S D， LU W J， et al. Application of improved genetic algorithm in robot path planning ［J］. Modern Manufacturing Engineering， 2022， 6： 9-16.
17	陈亮，姚懿轩. 基于AGA-WOA算法融合的移动机器人路径规划［J］. 今日制造与升级， 2021， 12： 41-43. CHEN L， YAO Y X. Path planning of mobile robot based on AGA-WOA algorithm fusion［J］. Manufacturing and upgrading today， 2021， 12： 41-43.
18	徐兴，俞旭阳，赵芸，等. 基于改进遗传算法的移动机器人全局路径规划［J］. 计算机集成制造系统， 2022， 6： 1659-1672. doi：10.13196/j.cims.2022.06.006 XU X， YU X Y， ZHAO Y， et al. Global path planning of mobile robot based on improved genetic algorithm ［J］. Computer Integrated Manufacturing System， 2022， 6： 1659-1672. doi: 10.13196/j.cims.2022.06.006
19	ZHOU L F， YANG L N， FANG H. Lunar rover path planning based on comprehensive genetic algorithm based on slip prediction［J］. Journal of Physics： Conference Series， 2019， 1267.
20	王强，姚进，王进戈. 基于遗传算法的移动机器人的一种路径规划方法［J］. 哈尔滨工业大学学报， 2004， 36（7）： 867-870. doi：10.3321/j.issn:0367-6234.2004.07.007 WANG Q， YAO J， WANG J G. A path planning approach to moving robot based on genetic algorithms［J］. Journal of Harbin Institute of Technology， 2004，36（7）： 867-870. doi: 10.3321/j.issn:0367-6234.2004.07.007
21	黄智榜，胡立坤，张宇，等. 基于改进跳点搜索策略的安全路径研究［J］. 计算机工程与应用， 2021， 57（1）： 56-61. HUANG Z B， HU L K， ZHANG Y， et al. Research on security path based on improved hop search strategy ［J］. Computer Engineering and Application， 2021， 57（1）： 56-61.
22	马新国，马希青. 融合改进RRT和Dijkstra算法的机器人动态路径规划［J］. 组合机床与自动化加工技术， 2023， 2： 5-9. MA X G， MA X Q. Robot path planning based on improved RRT and Dijkstra approach ［J］. Combined Machine Tool and Automated Processing Technology， 2023， 2： 5-9.
23	谢冲冲，李莹. 基于改进算法的移动机器人路径规划［J］. 重庆大学学报， 2021， 45（12）： 140-148. doi：10.11835/j.issn.1000-582X.2021.12.012 XIE C C， LI Y. Path planning of mobile robots based on improved algorithm ［J］. Journal of Chongqing University， 2021， 45（12）： 140-148. doi: 10.11835/j.issn.1000-582X.2021.12.012

[1]	赵迪,陈果,陈小利,王熊锦. 轮式搜救机器人地形自适应机构设计及越障性能分析[J]. 工程设计学报, 2023, 30(5): 579-589.
[2]	窦方健,邱清盈,管成,邵锦杰,吴海峰. 大转动惯量缠绕机加减速曲线优化设计[J]. 工程设计学报, 2023, 30(4): 503-511.
[3]	米鑫,李虹,郭彦青,高宏伟,王浩楠,宁羿帆. 基于线性回归的单柱塞泵单向阀参数优化[J]. 工程设计学报, 2022, 29(6): 705-712.
[4]	李琴,贾英崎,黄玉峰,李刚,叶闯. 一种工业机器人多目标轨迹优化算法[J]. 工程设计学报, 2022, 29(2): 187-195.
[5]	丁述勇, 张征, 丁文洁, 林勇. 多巷道式立体车库优化设计与车辆存取策略研究[J]. 工程设计学报, 2021, 28(4): 443-449.
[6]	唐东林, 龙再勇, 汤炎锦, 潘峰, 游传坤. 储罐检测爬壁机器人全遍历路径规划[J]. 工程设计学报, 2020, 27(2): 162-171.
[7]	张帅, 韩军, 涂群章, 杨小强, 杨旋. 基于GA-NLP的剪刀式折叠桥梁展桥机构多目标优化设计[J]. 工程设计学报, 2020, 27(1): 67-75.
[8]	刘春青, 王文汉. 基于人工神经网络-遗传算法的展成法球面精密磨削参数优化[J]. 工程设计学报, 2019, 26(4): 395-402.
[9]	周结华, 代冀阳, 周继强, 张孝勇. 面向大型机场草坪的割草机器人路径规划及轨迹跟踪控制研究[J]. 工程设计学报, 2019, 26(2): 146-152.
[10]	马天兵, 王孝东, 杜菲, 王鑫泉. 基于GA-SVM的刚性罐道故障诊断[J]. 工程设计学报, 2019, 26(2): 170-176.
[11]	唐东林, 袁波, 胡琳, 李茂扬, 魏子兵. 储罐探伤爬壁机器人全遍历路径规划方法[J]. 工程设计学报, 2018, 25(3): 253-261.
[12]	邓星, 于兰峰, 雷聪, 徐江平, 肖泽平. 基于响应面法的无轨伸缩式门式起重机轻量化设计[J]. 工程设计学报, 2018, 25(3): 288-294.
[13]	梁承姬, 沈珊珊, 胡文辉. 基于路段时间窗考虑备选路径的AGV路径规划[J]. 工程设计学报, 2018, 25(2): 200-208.
[14]	唐维, 谢延敏, 黄仁勇, 张飞, 潘贝贝. 基于自适应SVR-ELM混合近似模型的镁合金差温成形本构参数反求[J]. 工程设计学报, 2017, 24(5): 536-544.
[15]	朱龙彪, 王辉, 王景良, 邵小江, 朱志慧. 基于动态时间窗的泊车系统路径规划研究[J]. 工程设计学报, 2017, 24(4): 440-448.

Viewed

Full text

Abstract

Cited

Shared

Discussed