周飞龙，甘 屹

（上海理工大学机械工程学院，上海 200093）

0 引言

相对于其他算法，RRT 算法因其在多约束、高维路径规划问题中具有概率完备性和渐近最优性［13］而越来越受欢迎。针对RRT 算法收敛速度较慢的问题，Urmson 等［14］更改节点采样方式，提出具有节点偏向目标概率的hRRT（Heuristically RRT）算法；Wang［15］从多随机树方面提出双向随机树；刘成菊等［16］提出基于RRT 的变步长搜索以提高搜索效率。

路径规划算法的目的是找到可达路径，然而一些基于RRT 的算法在狭窄复杂环境中并不能求解出路径。这是由于在狭窄空间中选取节点是困难的，狭窄通道体积小，任何基于容量的抽样分布都可能失败［17］。Rodriguez 等［18］从多向随机树角度提出了在OB-RRT（Obstacle Based RRT）中通过狭窄通道区域建立根节点，让随机树更快地寻找到可行路径，但需要预先确定狭窄空间位置；Informed-RRT*与RABIT*通过局部优化器，提高路径中的狭窄区域采样概率，但是其效率有待提高［19-20］；文献［13］提供一种桥梁检测算法提高对狭窄空间的采样概率，但会在有凹三角形轮廓障碍物附近产生多余采样节点，增加了算法时间。

本文提出一种融合切线段的hRRT 狭窄空间路径规划算法（An hRRT Narrow Space Path Planning Algorithm Fused with Tangent Segment，T-hRRT）。先使用hRRT 算法搜索到障碍物附近，再利用切线段寻找狭窄空间入口并构建障碍物轮廓的可通过狭窄空间，由于最短路径的解一定是由切线及其轮廓组成［8］，因此，T-hRRT 算法在狭窄空间环境中可以得到相对较短的路径，并且算法效率大幅提高。

1 狭窄空间定义

全局通行度是在地图上的所有可通行空间内，除去机器人或车辆所占空间外，自由空间面积的最小值与该点自由空间总面积的百分比［21］。……