关键词:
路径规划
RRT算法
RRT-D算法
摘要:
针对传统RRT(rapidly exploring random tree)算法在复杂环境下收敛速度慢、存在重复采样、缺乏目标导向性和规划的路径质量不高的问题,提出一种贪婪搜索和目标导向的RRT算法(RRT-D算法),在传统RRT算法的基础上,改进节点的采样方式和父节点的选取策略,取消步长限制,通过贪婪式的搜索方式一次生长10个候选节点,选取符合条件的且距离目标点最近的候选点作为子节点生长到树中,提高了算法的搜索能力,降低了路径代价;用动态减少重复搜索区域的方式减少了无效搜索;每次采样后判断采样点能否与目标点直接相连,增加了采样的目标导向性,提高了搜索效率,遍历全树构成无向图时,可根据总采样点数量,通过限制无向图边的长度来减少边的数量,由Dijkstra算法搜索代价最小的路径;最后由分段三次Hermite插值函数对路径进行平滑处理。试验结果表明,与传统RRT算法相比,RRT-D算法不仅大幅缩短了规划时间,而且得到的路径代价更小、更加平滑,节点的利用率更高,验证了RRT-D算法在路径规划中的优势。