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

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

摘要/Abstract

摘要：

通过构建正六边形栅格地图, 并修改传统跳点搜索(jump point search, JPS)算法的邻居剪枝、强制邻居判断的规则和JPS策略, 提出一种新的正六边形栅格JPS算法, 并且利用该算法解决智能体在环境地图存在障碍物时的路径规划问题。利用Pycharm平台进行仿真研究, 并与传统正方形栅格A^*算法和JPS算法进行路径规划仿真比较, 结果表明正六边形栅格JPS算法可更好地实现路径规划, 所规划出的路径可避免穿越墙角的不安全行为、减少转向次数, 且该算法可减少路径规划时间, 提高了路径规划的质量和效率。

关键词: 正六边形, 栅格地图, JPS算法, 路径规划

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

中图分类号:

N945

王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.

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

图/表 20

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

表1

图17

图18

图19

参考文献 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]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[2]	尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.
[3]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[4]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[5]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[6]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[7]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.
[8]	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42(9): 1988-1994.
[9]	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42(10): 2312-2319.
[10]	杨秀霞, 曹唯一, 张毅. 时间和角度约束下的双圆弧路径规划[J]. 系统工程与电子技术, 2019, 41(8): 1835-1843.
[11]	胡腾, 刘占军, 刘洋, 夏帅帅, 陈前斌. 多无人机3D侦察路径规划[J]. 系统工程与电子技术, 2019, 41(7): 1551-1559.
[12]	高春庆, 寇英信, 李战武, 徐安, 李游, 常一哲. 小型无人机协同覆盖侦察路径规划[J]. 系统工程与电子技术, 2019, 41(6): 1294-1299.
[13]	王瑛, 郑煜坤, 姚頔, 李正欣, 李超. 危险天气下改航路径网络规划[J]. 系统工程与电子技术, 2019, 41(6): 1309-1315.
[14]	吴云华, 牛康, 李磊, 陈志明. 基于3D-APF和约束动力学的无人机编队飞行控制[J]. 系统工程与电子技术, 2018, 40(5): 1104-1108.
[15]	刘源, 李玉玲, 郝勇, 赵琳. 基于遗传算法的多星协同攻击轨道优化方法[J]. 系统工程与电子技术, 2017, 39(8): 1815-1822.