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

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

Chinese Journal of Engineering Design

2023, Vol. 30

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

Robotic and Mechanism Design

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

Download:

HTML

PDF(7497KB)
Export: BibTeX | EndNote (RIS)

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

Received: 22 March 2023 Published: 02 January 2024

CLC:

TP 242

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Yaqin TIAN
	Menghui HU
	Wentao LIU
	Yinzhi HOU

Cite this article:

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

URL:

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

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

为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题，引入自适应交叉算子和变异算子，将改进后的跳点搜索（ $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 算法$ 可以有效缩短寻优执行时间，提高寻优准确率，减少运算执行次数，在稳定性、准确性、快速性上具有明显的优势。

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

Fig.1 Schematic diagram of 30×30 grid matrix

Fig.2 Schematic diagram of oblique line forced neighbors

Fig.3 Schematic diagram of linear forced neighbors

Fig.4 Schematic diagram of

j u m p p o i n t s e a r c h

Fig.5 Flow chart of

J P S G

algorithm

Fig.6 Path planning result based on traditional JPS algorithm

Fig.7 Path planning result based on improved JPS algorithm

Fig.8

S i m u l a t i o n r e s u l t s o f p a t h p l a n n i n g i n s t a t i c e n v i r o n m e n t

Fig.9

S i m u l a t i o n r e s u l t s o f p a t h p l a n n i n g l e n g t h i n s t a t i c

e n v i r o n m e n t

算法	规划路径长度	准确率/%	收敛迭代数/次	规划时间/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$

Table1 Comparison of algorithm performance in static environment

Fig.10 Path planning results based on JPSG algorithm

算法	规划时间/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

Table 2 Performance comparison between JPSG algorithm and the algorithm in literature [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

Table 3 Performance comparison between JPSG algorithm and the algorithm in literature [23]

Fig.11 Comparison of simulation results of path planning in static and dynamic environments

Fig.12 Schematic of path planning after the robot encounters the first and second dynamic obstacles

Fig.13 Simulation results of path planning in dynamic environment

算法	规划路径长度	准确率/%	收敛迭代数/次	规划时间/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$

Table 4 Performance comparison results of different algorithms in dynamic environments


[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]	Di ZHAO,Guo CHEN,Xiaoli CHEN,Xiongjin WANG. Terrain adaptive mechanism design and obstacle-surmounting performance analysis of wheeled search and rescue robot[J]. Chinese Journal of Engineering Design, 2023, 30(5): 579-589.

[2]	Fangjian DOU,Qingying QIU,Cheng GUAN,Jinjie SHAO,Haifeng WU. Optimization design of acceleration and deceleration curve of winding machine with large moment of inertia[J]. Chinese Journal of Engineering Design, 2023, 30(4): 503-511.

[3]	Xin MI,Hong LI,Yan-qing GUO,Hong-wei GAO,Hao-nan WANG,Yi-fan NING. Parameter optimization of single plunger pump check valve based on linear regression[J]. Chinese Journal of Engineering Design, 2022, 29(6): 705-712.

[4]	Qin LI,Ying-qi JIA,Yu-feng HUANG,Gang LI,Chuang YE. A multi-objective trajectory optimization algorithm for industrial robot[J]. Chinese Journal of Engineering Design, 2022, 29(2): 187-195.

[5]	DING Shu-yong, ZHANG Zheng, DING Wen-jie, LIN Yong. Optimization design of multi-lane stereo garage and research on vehicle access strategy[J]. Chinese Journal of Engineering Design, 2021, 28(4): 443-449.

[6]	YAN Guo-ping, ZHOU Jun-hong, ZHONG Fei, LI Zhe, ZHOU Hong-di, PENG Zhen-ao. Design and optimization of magnetic compression correction device for paper-plastic composite bag[J]. Chinese Journal of Engineering Design, 2021, 28(3): 367-373.

[7]	CHENG Bin, JING Bing-xue. Process route optimization based on bacteria foraging and ant colony algorithm[J]. Chinese Journal of Engineering Design, 2020, 27(5): 600-607.

[8]	ZHANG Shuai, HAN Jun, TU Qun-zhang, YANG Xiao-qiang, YANG Xuan. Multi-objective optimization design of deployable mechanism of scissor folding bridge based on GA-NLP[J]. Chinese Journal of Engineering Design, 2020, 27(1): 67-75.

[9]	LIU Chun-qing, WANG Wen-han. Parameter optimization of generating method spherical precision grinding based on ANN-GA[J]. Chinese Journal of Engineering Design, 2019, 26(4): 395-402.

[10]	MA Tian-bing, WANG Xiao-dong, DU Fei, WANG Xin-quan. Fault diagnosis for rigid guide based on GA-SVM[J]. Chinese Journal of Engineering Design, 2019, 26(2): 170-176.

[11]	DENG Xing, YU Lan-feng, LEI Cong, XU Jiang-ping, XIAO Ze-ping. Lightweight design of trackless telescopic gantry crane based on response surface method[J]. Chinese Journal of Engineering Design, 2018, 25(3): 288-294.

[12]	TANG Wei, XIE Yan-min, HUANG Ren-yong, ZHANG Fei, PAN Bei-bei. Constitutive parameter inverse for nonisothermal stamping of magnesium alloy based on adaptive SVR-ELM mixture surrogate model[J]. Chinese Journal of Engineering Design, 2017, 24(5): 536-544.

[13]	CHENG Bing, YU Lan-feng, WU Yong-ming, FU Kang. Research on lightweight design of underfloor lifting system based on response surface method[J]. Chinese Journal of Engineering Design, 2016, 23(6): 606-611.

[14]	QIU Rui-bin, LEI Fei, CHEN Yuan, WANG Qiong. Research on the method of multi-case topology optimization of frame structure based on the weight ratio[J]. Chinese Journal of Engineering Design, 2016, 23(5): 444-452.

[15]	LI Xiao-huo, SHI Shang-wei, WENG Zheng-yang, QIAN Ya-sen, LI Yan, YANG Zi-jia. Dynamic optimization of working mechanism for impacting and crushing rock road-header based on BP-GA[J]. Chinese Journal of Engineering Design, 2016, 23(4): 358-363.

Viewed

Full text

Abstract

Cited

Shared

Discussed