移动机器人路径动态规划有向D~*算法

Directed D~* algorithm for dynamic path planning of mobile robots

针对传统D~*路径规划算法搜索效率低、成本较高的问题,提出有向D~*算法.该算法考虑目标点与障碍物信息,引入关键节点概念,逐级扩展确定可行路径,并且引入导向函数以控制单次搜索的节点搜索范围来提高搜索效率;在原欧几里得评价指标的基础上引入路径平滑度函数对偏移路径进行惩罚,避免机器人无效转弯而增加移动成本;通过路径平滑度函数中的"转弯因子"协调路径长度与平滑度之间的关系,给出路径平滑度函数的分段原理与转弯因子的确定方法,并对算法收敛性进行证明.在不同环境下的仿真实验表明,该算法较传统算法能更好地兼顾局部搜索与全局最优性,尤其适用于障碍物较多的复杂环境.

A directed D~*route planning algorithm was proposed,aiming at the low efficiency and high cost of the traditional D~*route planning algorithms.In the proposed directed D*algorithm,the key nodes are defined by utilizing the location information of target points and obstacles so that the feasible routes could be determined by a stepwise expanding way,and a directed function is introduced to control the single searching range of nodes in order to improve the searching efficiency.A path smoothness function which punishes the deviation of paths is introduced to the algorithm in addition to Euclidean evaluation function,in order to avoid the redundant turning of robots and reduce the costs.The length of the path and the smoothness are taken into account simultaneously by the turning factor of the path smoothness function.The piecewise principle of the path smoothness function and the determining method of the turning factor are proposed.The convergence of the algorithm was also proved.Simulation experiments in different environments show that the proposed algorithm can balance the local searching and the global optimality,and it is especially suitable for complex environments with many obstacles.