摘要
为解决传统JPS(Jump Point Search)算法的拐点多和路径次优等问题,提出一种改进的跳点搜索算法。首先,根据地图可行率,对障碍物进行适应性膨胀,以保障安全距离;其次,结合方向性因素对启发函数进行调整,显著提高了路径搜索的目的性;最后,提出了一种能剔除冗余节点的关键点提取策略,优化了初始规划后的路径,在保证路径最短的同时,显著减少了拓展节点和拐角。实验结果表明,与传统的JPS算法相比,所提算法能缩短路径长度并减少拐角数量,同时拓展节点数量平均减少19%,搜索速度平均提升21.8%。
To address issues such as excessive turning points and suboptimal paths in traditional JPS(Jump Point Search)algorithms,an improved jump point search algorithm is proposed.First,based on the feasibility of the map,the obstacles are adaptively expanded to ensure a safe distance.Then,an improved heuristic function based on directional factor is integrated.And a key point extraction strategy is proposed to optimize the initial planned path,significantly reducing the number of expanded nodes and turning points while ensuring the shortest path.The experimental results show that compared to traditional JPS algorithms,the proposed ensures a shorter path length and fewer corners,while reducing the number of extended nodes by an average of 19%and improving search speed by an average of 21.8%.
作者
何精武
李伟东
HE Jingwu;LI Weidong(School of Automobile Engineering,Dalian University of Technology,Dalian 116024,China)
出处
《吉林大学学报（信息科学版）》
CAS
2024年第5期808-816,共9页
Journal of Jilin University（Information Science Edition）
基金
辽宁省科技创新重大专项基金资助项目(ZX20220560)。
关键词
跳点搜索算法
障碍物膨胀
方向性
关键点提取
jump point search algorithm
obstacles expansion
directionality
key node extraction
