基于双向A*-APF算法的船舶路径规划研究
Ship path planning based on bidirectional A*-APF algorithm
孟凡齐 1孙潇潇 2朱金善 1梅斌 1郑沛洁1
作者信息
- 1. 大连海事大学航海学院,辽宁大连 116026
- 2. 上海船舶运输科学研究所有限公司,上海 200135
- 折叠
摘要
为解决目前船舶路径规划算法中存在的全局非最优解和局部最优解等问题,在双向A*算法的基础上加入了优化函数PathOptimization和IsClear,以去除冗余拐点,缩短全局路径距离;在人工势场法(artifi-cial potential field,APF)的基础上,设定离散化步长函数、斥力感应阈值和临时终点,以避免局部最优解和震荡问题;实现两种算法的融合算法(双向A*-APF算法),在MATLAB模拟的相同栅格图中,对比算法改进前后的模拟试验数据.结果表明,融合算法平均减少了 50％的冗余拐点,平均减少了 47.5％的算法搜索时间,平均缩短了 7％的路径距离,能够同时安全规避动态障碍物和静态障碍物.研究表明,双向A*-APF算法可用于解决船舶路径全局非最优解和局部最优解等问题.
Abstract
In order to address the existing issues of suboptimal global and local solutions in current path planning algorithms,an optimization function PathOptimization and IsClear were incorporated into the Bidirectional A*algo-rithm,aiming to eliminate redundant turning points and to shortening the global path distance.Additionally,a dis-cretization step function,repulsive force threshold,and temporary endpoint were introduced to avoid local optimal solutions and oscillation problems based on the artificial potential field method.A hybrid algorithm,termed Bidirec-tional A*-APF algorithm,was implemented by integrating these two approaches.Comparative simulation experi-ments were conducted on identical grid maps using MATLAB to assess the algorithm's performance before and after the improvements.The results showed that the hybrid algorithm reduced the average number of redundant turning points by approximately 50％,decreased the average algorithm search time by 47.5％,and shortened the average path distance by around 7％.Moreover,it safely avoided dynamic and static obstacles.The findings indicate that the Bidirectional A*-APF algorithm effectively addresses issues related to suboptimal global and local solutions.
关键词
双向A*算法/人工势场法/路径规划/融合算法Key words
bidirectional A*algorithm/artificial potential field method/path planning/fusion algorithm引用本文复制引用
基金项目
国家自然科学基金面上项目(52178067)
出版年
2024
NETL
NSTL
万方数据