基于改进A^(*)算法的移动机器人的路径规划

Improved A^(*) algorithm for path planning of mobile robot

因为传统A^(*)算法规划移动机器人的行驶路径,存在寻路时间较长、算法遍历节点数和路径转折次数较多等问题,为此提出了一种改进A^(*)算法。首先,计算移动机器人周围环境中障碍物所占比例,利用环境障碍率来改变启发函数在不同环境下的权重;其次,通过关键点选择策略,删除路径中冗余节点和转折点;然后,优化open表中节点数目,删除表中早期加入的节点和估值较大的节点;最后,在Matlab中的仿真实验显示,2种不同实验环境下,与传统A^(*)算法相比,改进A^(*)算法的路径规划时间分别缩短了57.14%和55.56%,转折次数分别减少了37.5%和50%,遍历节点数分别减少了57.46%和76.19%,路径长度分别减少了0.003%和0.04%。实验证明,改进的A^(*)算法可有效缩短路径规划的时间、路径的转折次数和算法遍历节点数。

When planning the traveling path of a mobile robot using the traditional A^(*)algorithm,there are problems such as longer path finding time,higher number of traversed nodes and path transitions,for this reason,an improved A^(*)algorithm is proposed.First of all,the proportion of obstacles in the surroundings of the mobile robot is calculated,and the environmental obstacle rate is utilized to change the weight of the heuristic function in different environments.Afterwards,redundant nodes and turning points in the path are removed by the critical point of the chosen solution.In addition,the number of nodes in the open table is optimized by removing the nodes that were added earlier in the table and those with larger valuations.Finally,simulation experiments in Matlab indicate that,for both experimental environments,in comparison with the traditional A^(*)algorithm,the improved A^(*)algorithm has a reduction in path planning time by 57.14%and 55.56%,the number of transitions by 37.5%and 50%,the number of nodes traversed by 57.46%and 76.19%,and the length of the paths by 0.003%and 0.04%,respectively.According to the experimental outcomes,the proposed improved A^(*)algorithm can effectively minimize the time of path planning,the number of turning points of the path and the number of nodes traversed by the algorithm.