Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (1): 56-61.DOI: 10.3778/j.issn.1002-8331.2003-0064

Previous Articles     Next Articles

Research on Security Path Based on Improved Hop Search Strategy

HUANG Zhibang, HU Likun, ZHANG Yu, HUANG Bin   

  1. School of Electrical Engineering, Guangxi University, Nanning 530004, China
  • Online:2021-01-01 Published:2020-12-31

基于改进跳点搜索策略的安全路径研究

黄智榜,胡立坤,张宇,黄彬   

  1. 广西大学 电气工程学院,南宁 530004

Abstract:

The path planned by JPS(Jump Point Search) algorithm is often too close to the obstacle, which affects the quality of the path. Therefore, an improved JPS algorithm based on path collision hazard is proposed. By using the risk assessment function to evaluate the traditional jump points, the jump points with high risk in the same corner of the obstacle are combined to form a new type of jump points. At the same time, the obstacle is puffed up to keep a certain distance between the jump point and the obstacle, so as to improve the search range of each iteration of the algorithm. Finally, the non-direct jump point is deleted to reduce the path length of the improved algorithm and improve the performance of the algorithm. Simulation results show that the improved JPS algorithm increases the average search speed by 58.9%, reduces the average path length by 2.7%, and reduces the average collision risk by 41.3% in the complex environment.

Key words: path planning, Jump Point Search(JPS) algorithm, jump point, collision risk

摘要:

JPS(Jump Point Search)算法规划的路径往往过于靠近障碍物,影响路径的质量。为此,提出基于路径碰撞危险度的改进JPS算法;通过对传统跳点用危险度评估函数评估,将障碍物同一个拐角中危险度高的跳点结合形成新类型的跳点;对障碍物进行膨化处理,使跳点与障碍物保持一定距离,提高算法每次迭代的搜索范围;删除不可直达的后继跳点,降低改进JPS算法的路径长度,改善算法的性能。仿真结果表明改进JPS算法在复杂环境中平均搜索速度提升58.9%,平均路径长度缩短2.7%,平均碰撞危险度降低41.3%。

关键词: 路径规划, JPS算法, 跳点, 碰撞危险度