英语原文共 9 页

1. 介绍

运动规划问题是机器人技术的重要组成部分之一。它是找到一系列完成给定任务的动作。运动规划算法具有各种应用，包括但不限于机器人导航，工业自动化，自动驾驶车辆和。

运动规划问题通常通过基于网格的搜索或基于采样的算法来解决。基于网格的搜索，通常由A*代表的，解决了将图论应用于离散状态空间的运动规划问题。基于网格的搜索通常可以保证分辨率的完整性和分辨率的最优性，这意味着解决方案的质量取决于分辨率。试图实现正确最优化应用于离散空间也已经成功，但是，因为物理资源例如存储空间和计算时间呈指数增长，它们不能很好地适应状态维度或问题空间的大小。

基于采样的算法，例如快速探索随机树（RRT）, 概率路线图（PRM）及其变体基于随机抽样而不是离散配置空间。它们通过迭代地添加随机样本来递增地构建一组轨迹。它们通常提供较弱的完整性。概率完整性保证了当迭代次数接近无穷大时，找到解的概率接近100％。

RRT的普及引发了广泛的研究。存在各种RRT变体以满足每个主要的要求。为了加速计算，提出了RRT的并行版本，并进一步研究了大规模分布式存储器架构。并行RRT（PRRT）使用无锁并发在现代多核CPU上获得超线性加速。当这些研究试图减少计算时间时，扩展RRT（ERRT）和动态RRT（DRRT）试图使RRT适应动态环境。它们都通过迭代运行RRT来解决运动规划问题。ERRT在前一次迭代中丢弃树，但DRRT重复使用在前一次迭代中的无碰撞分支，如D^*。Multipartite RRT（MP-RRT） 结合ERRT和DRRT的优势。Quad-RRT利用GPU和GPU进一步并行化RRT 减少了在大规模真实环境中找到解决方案的时间。

RRT^*和PRM^*被提议作为RRT和PRM的最佳对应物,指出RRT的变体产生次优解。RRT^lowast; 引入了ChooseParent过程和Rewire过程来提供渐近最优性;当迭代次数接近无穷大时,找到最优解的概率接近100％。当RRT将新节点连接到最近的顶点时，RRT^lowast; 将其连接到附近路径最短的顶点，这导致在ChooseParent过程中具有最低可能成本的路径。如果RRT^lowast; 降低了Rewire程序的成本，它还用新节点替换附近区域的父母节点。

为了减少收敛时间，已经研究了图形修剪算法和采样策略。RRT^lowast; 的作者提出了一种名为Branch-and-Bound的图修剪算法。从顶点到目标的成本的估计高于当前最佳解的成本，顶点从树中移除。通过定期删除这些顶点，RRT^lowast; 专注于改进当前的解决方案。其中一个采样策略是节点拒绝选择，如果保证它不会改善当前的解决方案，它将被拒绝。它类似于分支和绑定，但被拒绝的样本不会添加到树中，因此它减少了最近邻搜索的数量和冲突检测的数量。在节点拒绝中，随着最佳解决方案的成本变低，随机样本被接受的可能性降低。Informed-RRT^lowast; 通过定义引入了直接采样方法，被接受的区域为超椭圆体。它直接从超椭球体中取样 而不是迭代直到找到接受的状态。Informed-RRT^lowast; 的作者还将Informed-RRT^lowast; 与Fast Marching Tree^lowast; （FMT^lowast;）结合起来。

Cloud RRT^lowast; 初始化来自广义Voronoi图的采样云并将其用作采样偏差，当找到更好的解决方案时更新他们。RRT^lowast;-Smart提出了一种勘探开发算法，不仅引入了采样策略，还引入了优化路径技术。无论何时找到更好的路径，都可以通过路径矫直/平滑技术和路径的顶点进行优化并且优化路径成为偏差采样的来源。

本文提出了一种新的算法Quick-RRT^lowast; （Q-RRT^lowast;），它可以提高初始解决方案的质量和速率。收敛到最佳解决方案。本文的初步研究出现在Jeong，Lee和Kim（2015）。本文提出了一个更加成熟的版本并分析了它的性质，而且表明在提高了性能的基础上，时间复杂性与RRT^lowast; 保持一致。还用不同深度的数值模拟进行了分析，并且提供了建议用于实际使用的深度参数的值。Q-RRT^lowast; 是一种改进的RRT算法，利用RRT^lowast;的特征，局部区域中的顶点倾向于共享共同父母节点，以有效地扩大新节点的父候选集合。新样本节点的父节点候选人是RRT中新样本的一组附近顶点，但在Q-RRT^lowast;中，候选者还包括附近顶点的祖先节点。因此，它导致了成本较低的路径，如图1所示。需要指出的是，Q-RRT^lowast; 生成的路径比RRT^lowast;的路径更直接，导致路径的成本更低。由于Q-RRT^lowast; 是树扩展算法，因此可以与上述任何其他采样策略组合。

本文主要内容可归纳如下：

1.将RRT^lowast; 扩展到有效选择更好的父节点以提高最优解的收敛速度的方法。找到最佳解决方案以影响移动机器人导航的性能以及能耗。

2.与现有抽样策略的可能组合。本文的方法与采样策略不相背逆，因此可以与它们结合使用，以进一步提高性能。

本文的其余部分安排如下：第2节介绍了问题的定义和现有的算法。第3节描述了所提出的算法Q-RRT^lowast;，第4节用RRT^lowast; 和Informed-RRT^lowast;介绍模拟环境，结果和比较分析。随后进行第5节结束语。

1. 背景

本节规范了运动规划问题，并深入了解了RRT^lowast;，它构成了所提算法的基础。它还解释了Informed-RRT^lowast;，目的是清楚地理解后面提出的比较分析第4节.

2.1问题定义

设X =（0,1）d 为配置空间，Xobs 为障碍区，Xfree为无障碍区。定义了路径规划问题，其中Xinit isin;Xfree是初始状态，Xgoalsub;Xfree是目标区域。设有界变化的连续函数sigma;：[0,1]为路径。如果任意tau;isin;[0,1]，sigma;（tau;）isin;Xfree，则路径sigma;是无碰撞的。

定义1：可行的路径规划是找到可行的路径sigma;，这样的sigma;是无碰撞的。

定义2最优路径规划是找到一个可行路径sigma;，它使得成本最小化。

2.2RRT*

RRT*呈现于算法1。是一个最佳的运动规划算法，它始于一棵唯一定点没有边缘并且逐渐拓展无碰撞路径的树。如上第1节所述，当RRT将新状态Xnear连接到最近节点时，RRT^lowast; 搜索以x为中心的特定半径的超球面中的顶点，以找到一个顶点，从根节点到此的路径最短。Chosseparent伪代码显示在算法2。将Xnear连接到树上之后，如果通过Xnear的路径的成本低于当前路径，则RRT^lowast; 会尝试重新连接附近的顶点。Rewire描述于算法3。某些RRT*的原始程序在下面有所描述。

2.3Informed-RRT*

Informed-RRT^lowast; 将节点拒绝技术形式化为直接采样方法。在找到解决方案之前，Informed-RRT^lowast; 的工作方式与RRT^lowast; 的工作方式相同。一旦找到解决方案，Informed-RRT^lowast; 设置一个超椭圆体，其焦点为Xinit和Xgoal，如图2所示其中Xinit和Xgoal分别是初始状态和目标状态。椭圆体外的区域是满足条件的顶点集。

||X-Xinit|| ||Xgoal-X||gt;Cbest, (1)

其中x是随机状态，Cbest是最佳解的成本，||x，y||是从x到y的成本的可允许的启发式估计。然后，Informed-RRT^lowast; 通过从以Xinit和Xgoal的中点为中心的单位球转换均匀分布的样本，从椭球中随机采样状态。

如果超椭球的体积小于配置空间的体积,Informed-RRT^lowast; 会显著提高收敛速度。它还有助于找到通过狭窄通道的路径，因为增加了在狭窄通道中拾取随机样本的概率。

1. Q-RRT*

本节解释了所提出的Q-RRTlowast; 算法的细节，并分析了其计算复杂性。

3.1提出的算法

Q-RRTlowast; 的主要思想基于两个观察结果;常用的成本函数通常满足三角不等式，并且由于Rewire过程，RRTlowast; 中局部区域中的顶点倾向于共享共同的部分。在RRTlowast;中，需要增加半径参数Vrrt*以获得更快的收敛速度，但它还会以指数方式增加附近顶点的数量和计算时间。Q-RRT^lowast; 不是增加Vrrt*，而是通过不仅像RRT^lowast; 那样考虑超球面中包含的一组顶点而且通过考虑用户定义的祖先节点来扩大可能的父顶点集。描述Q-RRT*的伪代码如图算法4所示。

3.1.1选择父节点的程序

当Xnew被添加到树中时，Q-RRT^lowast; 在一组附近的顶点Xnear中搜索以找到以x成为最低成本的Xnew的路径的顶点,像RRT一样，但它也考虑了基于预定义参数Depth的Xnear的祖先，如图3所示。如果三角不等式适用于成本函数，则只要路径是无碰撞的，顶点Xnearisin;Xnear的父对象总是产生比Xnear成本更低的路径。Q-RRT^lowast; 利用这一点并从三角不等式中受益。即使三角不等式不成立，对CollisionFree过程的调用次数也不会显着增加。祖先集合中的顶点数量与Xnear中的顶点数量相比可以忽略不计，因为Xnear中的顶点倾向于共享公共父节点，并且仅当顶点降低成本时才调用CollisionFree过程。

3.1.2重新连接程序

如果通过Xnew或Xnew的父节点的路径生成成本较低的路径，则检查附近的顶点。具有共同父母的近顶点的趋势比RRTlowast;更加增加，因此它使Q-RRTlowast; 产生更优解。Q-RRTlowast; 的Rewire程序描述于算法5.

图4 说明了Depth2的Q-RRTlowast;与RRTlowast;相比如何工作。当一个新的样本Xnew添加进来，RRT^lowast; 仅搜索附近的顶点Xnear（灰点）并将Xnew连接到其中一个顶点。然而，Q-RRT^lowast; 搜索Xnear和Xnear的祖先，如图4（b），因此Q-RRT^lowast; 找到一条更直的路径，从而得到比RRT^lowast; 更好的解决方案。图4（c）和（d）显示了RRT^lowast; 和Q-RRT^lowast;的Rewire过程的显着差异，其中Q-RRT^lowast; 不仅使Xnew的路径变直，而且到附近顶点的路径也一样。请注意，通过Rewire过程可以改善RRT*中未改进的附近顶点。

Q-RRT^lowast; 的优点包括提高初始解决方案的质量和快速收敛速度。此外，Q-RRT^lowast; 是一种与采样策略相交的树扩展算法，这意味着它可以与任何采样策略相结合。Q-RRT^lowast; 使用的原始程序如下所述。

3.2复杂性分析

本节表明Q-RRT^lowast; 的时间和空间复杂性与RRT^lowast;保持一致。时间复杂性和空间复杂性描述给定算法分别需要多少时间和空间。表格1总结了RRT，RRT^lowast;，Informed-RRT^lowast;和Q-RRT^lowast;的复杂性。

空间复杂度定义为给定算法使用的内存空间量。Q-RRT^lowast; 维持树G_n =（V_n，E_n）并且G的大小_n 确定存储空间的量。

时间复杂度通常定义为对最耗时过程的调用次数，即Q-RRT*中的CollisionFree过程。分

资料编号：[5028]