摘要
跳点搜索是一种应用于路径规划的快速的图搜索算法。针对现有基于改进JPS算法的路径规划过程中,跳点搜索过程复杂、节点扩展数量较多导致搜索效率较低,为此提出一种基于改进JPS的全局路径规划策略,包括减少冗余节点扩展的方法以及提出安全平滑路径生成策略。首先,进行搜索方向的优先级排序,调整各个可能移动方向的优先级,优先探索指向目标的方向,依次按照该优先级排序扩展其他节点寻求跳点。其次,结合路径优化策略,包括安全节点更新、冗余节点消除及路径平滑等策略,确保路径的安全性与平滑性。安全节点更新策略减少危险路径,冗余节点消除策略有效降低路径长度,路径平滑策略通过三次准均匀B样条曲线处理改善路径的平滑度。最后,通过仿真与真实场景的试验验证改进算法的性能,仿真结果表明,改进的JPS算法在复杂环境中相较于传统的JPS算法和A*算法,分别减少了19.0%和99.92%的搜索时间,Improved-JPS算法的扩展节点数相较于JPS减少了56.9%,相较于A^(*)算法减少了98.9%。在更复杂的实际环境中,ROS智能车在实际环境中的实验结果表明,搜索时间相较于A*算法提高了约20.5%。相较于JPS提高了约28.0%,有效提高复杂场景下车辆路径规划效率和安全性。验证了Improved-JPS算法的有效性和优越性。
Jump point search is a fast graph search algorithm applied to path planning.Aiming at the existing path planning process based on the improved JPS algorithm,the complexity of the hopping point search process and the high number of node extensions lead to low search efficiency,this paper proposes a global path planning strategy based on the improved JPS,including a method to reduce redundant node extensions as well as proposing a safe and smooth path generation strategy.First,the priority ranking of search directions is performed,and the priority of each possible moving direction is adjusted to prioritize the exploration of the direction pointing to the goal,and the other nodes are expanded to seek jump points according to this priority ranking in turn.Second,path optimization strategies are combined,including safe node updating,redundant node elimination and path smoothing to ensure the safety and smoothness of paths.The safe node update strategy reduces the dangerous paths,the redundant node elimination strategy effectively reduces the path length,and the path smoothing strategy improves the smoothness of the paths by three times quasi-uniform B-spline curve processing.Finally,the performance of the improved algorithm is verified through simulation and real scenarios.The simulation results show that the improved JPS algorithm reduces the search time by 19.0%and 99.92%in complex environments compared to the traditional JPS algorithm and A*algorithm,respectively,and the number of expansion nodes of the improved-JPS algorithm is reduced by 56.9%compared to the JPS and 98.9%compared to the A*algorithm.98.9%.In more complex real-world environments,the experimental results of the ROS intelligent vehicle in real-world environments show that the search time is improved by about 20.5%compared to A*algorithm.Compared with JPS,the search time is improved by about 28.0%,which effectively improves the efficiency and safety of vehicle path planning in complex scenarios.The effectiveness and superiority of Improved-JPS algorithm is verified.Jump point search is a fast graph search algorithm widely used in path planning.However,the complexity of the hopping point search process and the excessive number of node extensions can lead to low search efficiency.To address these limitations,this paper proposes a global path planning strategy based on an improved JPS algorithm.The proposed approach includes a method to reduce redundant node extensions and introduces a safe and smooth path generation strategy.First,a directional priority ranking is introduced,where the search directions are adjusted to prioritize movement toward the goal.Nodes are then expanded sequentially according to this ranking to search for jump points more efficiently.Second,several path optimization strategies are combined,including safe node updating,redundant node elimination and path smoothing to ensure the safety and smoothness of paths.The safe node update strategy reduces the dangerous paths,the redundant node elimination strategy effectively reduces the path length,and the path smoothing strategy improves the smoothness of the paths by three times quasi-uniform B-spline curve processing.Finally,the performance of the improved algorithm is verified through simulation and real scenarios.The simulation results show that the improved JPS algorithm reduces the search time by 19.0%and 99.92%in complex environments compared to the traditional JPS algorithm and A*algorithm,respectively,and the number of expansion nodes of the improved-JPS algorithm is reduced by 56.9%compared to the JPS and 98.9%compared to the A*algorithm.98.9%.In more complex real-world environments,tests conducted on a ROS-based intelligent vehicle demonstrate search time improvements of approximately 20.5%over A*and 28.0%over JPS.These results confirm that the proposed Improved-JPS algorithm significantly enhances the efficiency and safety of path planning in complex scenarios,validating its effectiveness and superiority.
作者
朱振东
姚强强
石艺恒
谢麒麟
Zhu Zhendong;Yao Qiangqiang;Shi Yiheng;Xie Qilin(School of Mechanical Engineering,Qinghai University,Xining 810016,China)
出处
《仪器仪表学报》
北大核心
2025年第6期194-204,共11页
Chinese Journal of Scientific Instrument
基金
青海大学中青年科研基金(2023-QGY-15)、青海大学大学生科研训练计划(SRT202541)项目资助。
关键词
智能车路径规划
跳点搜索
优先级排序
路径优化
安全策略
intelligent vehicle path planning
jump point search
priority ranking
path optimization
safety strategy
