基于正六边形栅格JPS算法的智能体路径规划

doi:10.12305/j.issn.1001-506X.2021.12.26

Abstract

Abstract:

By constructing a regular hexagon grid map and modifying the rules of neighbors pruning, forced neighbors judgment and jump point search (JPS) strategy of the traditional JPS algorithm, a new regular hexagon grid JPS algorithm is proposed, which is used to solve the path planning problem of the agent on the environment map with obstacles. The path planning simulations and the simulation comparisons with the traditional square grid A^* algorithm and JPS algorithm are carried out on Pycharm platform. The simulation results show that the regular hexagon grid JPS algorithm can plan paths better, avoiding the unsafely crossing corner behaviors, reducing the number of turnings and the time of path planning, thus the algorithm improves the quality and efficiency of path planning.

Key words: regular hexagon, grid map, jump point search (JPS) algorithm, path planning

CLC Number:

N945

Wenming WANG, Jialu DU. Agent path planning based on regular hexagon grid JPS algorithm[J]. Systems Engineering and Electronics, 2021, 43(12): 3635-3642.

Figures/Tables 20

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Table 1

Fig.17

Fig.18

Fig.19

References 28

1	XU Z , ZHANG E Z , CHEN Q W . Rotary unmanned aerial vehicles path planning in rough terrain based on multi-objective particle swarm optimization[J]. Journal of Systems Engineering and Electronics, 2020, 31 (1): 130- 141.
2	AHMED S A , BAKIR A I . A comparative study of various intelligent optimization algorithms based on path planning and neural controller for mobile robot[J]. Journal of Engineering, 2019, 25 (8): 80- 99. doi: 10.31026/j.eng.2019.08.06
3	ABBAS Q , HUSSAIN Q , ZIA T . Reduced solution set shortest path problem: Capton algorithm with special reference to Dijkstra's algorithm[J]. Malaysian Journal of Computer Science, 2018, 31 (3): 175- 187. doi: 10.22452/mjcs.vol31no3.1
4	SADDIQ A T , RAHEEM F A , ABBAS N A F . Robot arm tra-jectory planning optimization based on integration of particle swarm optimization and A^* algorithm[J]. Journal of Computational and Theoretical Nano Science, 2019, 16 (3): 1046- 1055. doi: 10.1166/jctn.2019.7996
5	HARABOR D, GRASTIEN A. Online graph pruning for path finding on grid maps[C]//Proc. of the AAAI 25th Conference on Artificial Intelligence, 2011: 1114-1119.
6	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42 (9): 1988- 1994.
	CHEN D D , LI W Y . Local path planning algorithm for USV with towed cable[J]. Systems Engineering and Electro-nics, 2020, 42 (9): 1988- 1994.
7	MIN J G , RUY W S , PARK C S . Faster pipe auto-routing using improved jump point search[J]. International Journal of Naval Architecture and Ocean Engineering, 2020, 12, 596- 604. doi: 10.1016/j.ijnaoe.2020.07.004
8	TRAISH J , TULIP J , MOORE W . Optimization using boundary lookup jump point search[J]. IEEE Trans.on Computational Intelligence and AI in Games, 2017, 8 (3): 268- 277.
9	ZHENG T, XU Y. AGV path planning based on improved A-star algorithm[C]//Proc. of the IEEE 3rd Advanced Information Management, Communicates, Electronic and Automation Control Conference, 2019: 1534-1538.
10	ZENG J J , QIN L , HU Y . Integrating a path planner and an adaptive motion controller for navigation in dynamic environments[J]. Applied Sciences, 2019, 9 (7): 1384. doi: 10.3390/app9071384
11	JIANG C J, SUN S F, LIU J L, et al. Global path planning of mobile robot based on improved JPS+algorithm[C]//Proc. of the Chinese Automation Congress, 2020: 2387-2392.
12	马小陆, 梅宏. 基于JPS策略的ACS移动机器人全局路径规划[J]. 机器人, 2020, 42 (4): 494- 502.
	MA X L , MEI H . The global path planning of ant colony system mobile robot based on jump point search strategy[J]. Robot, 2020, 42 (4): 494- 502.
13	HU Y , HARABOR D , QIN L , et al. Regarding goal bounding and jump point search[J]. Journal of Artificial Intelligence Research, 2021, 70, 631- 681. doi: 10.1613/jair.1.12255
14	邱磊, 刘辉玲, 雷建龙. 跳点搜索算法的原理解释及性能分析[J]. 新疆大学学报, 2016, 33 (1): 80- 87.
	QIU L , LIU H L , LEI J L . Principle explanation and perfor-mance analysis of jump search algorithm[J]. Journal of Xinjiang University, 2016, 33 (1): 80- 87.
15	MA L, GAO X, FU Y X, et al. An improved jump point search algorithm for home service robot path planning[C]//Proc. of the Chinese Control And Decision Conference, 2019: 2477-2482.
16	武达, 王然风, 付翔, 等. 矿用机器人局部路径优化算法研究[J]. 煤炭工程, 2020, 52 (3): 132- 136.
	WU D , WANG R F , FU X , et al. Research on local path optimization algorithm mining robot[J]. Coal Engineering, 2020, 52 (3): 132- 136.
17	RAHEEM F A , ABDULKAREEM M I . Development of path planning algorithm using probabilistic road map based on modified ant colony optimization[J]. World Journal of Engineering and Technology, 2019, 7 (4): 583- 597. doi: 10.4236/wjet.2019.74042
18	ZENG C , XU Y . An ant colony algorithm for robot path planning under honeycomb grid[J]. Mechanical Science and Technology, 2016, 35 (8): 1308- 1312.
19	陶哲, 高跃飞, 郑天江. 基于A^*算法在蜂巢栅格地图中的路径规划研究[J]. 中北大学学报(自然科学版), 2020, 41 (4): 310- 317. doi: 10.3969/j.issn.1673-3193.2020.04.005
	TAO Z , GAO Y F , ZHENG T J . Research on path planning in honeycomb grid map based on A^* algorithm[J]. Journal of North University of China (Natural Science Edition), 2020, 41 (4): 310- 317. doi: 10.3969/j.issn.1673-3193.2020.04.005
20	王维才, 艾廷华, 晏雄锋. 多约束条件下的正六边形格网室内路径规划[J]. 武汉大学学报(信息科学版), 2020, 45 (1): 111- 118.
	WANG W C , AI T H , YAN X F . Indoor path planning of regular hexagonal grid under multiple constraints[J]. Journal of Wuhan University (Information Science Edition), 2020, 45 (1): 111- 118.
21	WANG Y L, XU L, LI B, et al. Research and implementation of global path planning for unmanned surface vehicle based on electronic chart[C]//Proc. of the International Conference on Mechatronics and Intelligent Robotics, 2017: 534-539.
22	AVERSA D, SARDINA S, VASSOS S. Path planning with inventory-driven jump-point-search[C]//Proc. of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2015: 2-8.
23	TSATCHA D , SAUX E , CLARAMUNT C . A bidirectional path-finding algorithm and data structure for maritime routing[J]. International Journal of Geographical Information Science, 2014, 28 (7): 1355- 1377. doi: 10.1080/13658816.2014.887087
24	ZHOU K , YU L , LONG Z , et al. Local path planning of dri-verless car navigation based on jump point search method under urban environment[J]. Future Internet, 2017, 9 (3): 51- 63. doi: 10.3390/fi9030051
25	JANINS A , BADE A , HAMZAH . Integration of enhanced jump point search algorithm and modified bresenham technique for path finding in grid-based map environment[J]. Journal of Computational and Theoretical Nanoscience, 2018, 24 (3): 1582- 1586.
26	FDA B , ABA B , MKA B , et al. Path planning with modified A star algorithm for a mobile robot[J]. Procedia Engineering, 2014, 96, 59- 69. doi: 10.1016/j.proeng.2014.12.098
27	WANG Y L , YU X , LIANG X . Design and implementation of global path planning system for unmanned surface vehicle among multiple task points[J]. International Journal of Vehicle Autonomous Systems, 2018, 14 (1): 82- 105. doi: 10.1504/IJVAS.2018.093119
28	WEI D . An optimized Floyd algorithm for the shortest path problem[J]. Journal of Networks, 2010, 5 (12): 1496- 1504.

对比项目	正方形栅格A^*算法	正六边形栅格A^*算法	正方形栅格JPS算法	正六边形栅格JPS算法
路径节点数/个	23	26	7	7
比较节点数/个	212	184	11	10
路径规划时间/s	0.210 5	0.125 8	0.101 2	0.056 8
转折次数/次	10	5	8	5
路径长度/m	42.81	43.30	42.81	43.30
危险路径点数/个	3	0	2	0

[1]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[2]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[3]	Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint [J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.
[4]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.
[5]	Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method [J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.
[6]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[7]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[8]	Zhiqiang JIAO, Jieyong ZHANG, Peiyang YAO, Xun WANG, Yichao HE. Distributed evolution method of C4ISR service deployment based on hierarchical structure [J]. Systems Engineering and Electronics, 2021, 43(6): 1572-1585.
[9]	Yanan LI, Haibin HUANG, Liangming CHEN, Yufei ZHUANG, Xiaoli WANG. Energy-optimal three-dimensional path planning for AUV under changing ocean current environment [J]. Systems Engineering and Electronics, 2021, 43(12): 3667-3674.
[10]	Wengang LI, Liujiang WANG, Dexiang FANG, Yuwei LI, Jun Huang. Path planning algorithm combining A^* with DWA [J]. Systems Engineering and Electronics, 2021, 43(12): 3694-3702.
[11]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[12]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[13]	Quanxian ZHANG, Bin ZENG, Houpu LI. Underway replenishment path planning method for distributed naval warfare under the influence of sea conditions [J]. Systems Engineering and Electronics, 2020, 42(10): 2312-2319.
[14]	Sheng GAO, Jianliang AI, Zhihao WANG. Mixed population RRT algorithm for UAV path planning [J]. Systems Engineering and Electronics, 2020, 42(1): 101-107.
[15]	YANG Xiuxia, CAO Weiyi, ZHANG Yi. Bi-arc path planning with time and angle constraints [J]. Systems Engineering and Electronics, 2019, 41(8): 1835-1843.

Agent path planning based on regular hexagon grid JPS algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 28

Related Articles 15

Recommended Articles

Metrics

Comments