WANG Zhongyu, ZENG Guohui, HUANG Bo. Mobile robot path planning algorithm based on improved bidirectional A star*[J]. 2020, (11): 141-143+147. DOI: 10.13873/J.1000-9787(2020)11-0141-03.
基于改进双向A*的移动机器人路径规划算法
摘要
针对双向A
*
(B-A
*
)算法在障碍物空间生成路径的过程中搜索过多无用区间且生成路径存在很多冗余点和拐点的问题
提出了一种基于B-A
*
算法改进的高效路径规划(EB-A
*
)算法。首先引入了一种智能采样函数
使区间搜索更具方向性
从而减少无用区间搜索。其次采用了精英搜索策略
使改进后的算法在障碍物空间规划路径时
根据目标点与当前点的相对位置采用不同搜索矩阵
进一步减少了寻路时间。最后采用路径平滑策略
删除路径中的冗余点
平滑生成路径。仿真实验表明:改进后的算法能够提高工作效率
平滑生成路径。
Abstract
Aiming at the problem that the bidirectional A*( B-A*) algorithm search
too many useless intervals in the process of generating path in the obstacle space
and there are many redundant points and inflection points in the generated path
a high efficient path planning algorithm based on B-A*improvement
referred to as EB-A*is proposed. Firstly
the algorithm introduces an intelligent sampling function
which makes the interval search more directional
thus reducing the useless interval search. Secondly
the elite search strategy is adopted
so that the improved algorithm uses different search matrices according to the relative position of the target point and the current point
which further reduces the pathfinding time. Finally
the path smoothing strategy is adopted to delete redundant points in the path and smooth the generated path. Simulation experiments show that the improved algorithm can improve work efficiency and smooth the generation path.