摘要
针对传统A~*算法在路径规划中存在折点多、运行时间长、累计转折角度大等问题。提出一种定向加权A~*算法。首先,对传统A~*算法四个方向搜索和八个方向搜索进行实验对比;其次,将算法搜索方向进行二级分类,以竖直和水平方向为一级搜索、斜向为二级搜索,以一级搜索为主判断二搜索方向是否进行;最后,对距离代价函数进行加权处理。实验结果表明,与传统A~*算法相比较:最优距离长度缩短了28%,算法运行时间减少50%,转折点数减少75%,累计转折角度减小83%。所提算法能够有效避免横穿障碍物的危险,同时减少了算法的运行时间、转折次数和累计转折角度,提高了路径规划效率。
In the traditional A＊ algorithm, there are some problems such as discounted turning points, long running time and large cumulative turning angle. An improved directional weighted A＊ algorithm was proposed. Firstly, the traditional A＊ algorithm was researched in four direction search and eight direction search; secondly,the search direction of the algorithm was classified into two level,the vertical and horizontal direction is the first level search, the oblique direction is the second search, and the result of first level search was used to determine whether to do the second search; finally,Weighting the distance cost function was weighted. The experimental results show that compared with the traditional A＊algorithm： the optimal distance length is reduced by 28%, the algorithm running time is shortened by 50%, the number of turning points is reduced by 75%,the cumulative turning angle is reduced by 83%. The proposed algorithm can effectively avoid the risk of crossing the obstacle,and reduce the running time, the turning points and the cumulative turning angle of the algorithm, and improve the efficiency of path planning.
出处
《计算机应用》
CSCD
北大核心
2017年第A02期77-81,共5页
journal of Computer Applications
基金
内蒙古自治区自然科学基金资助项目(2014MS0619)
内蒙古科技项目(20120304)
关键词
A＊算法
定向
加权
路径规划
折点数
运行时间
A ＊ algorithm
orientation
weighting
path planning
number of turning points
running time
