046工程第1卷·第1期·2015年3www.engineering.org.cn研究机器人-文章工程2015，1（1）：46-面向运动规划的有效位形空间构造与Jia Pan1*和Dinesh Manocha2位形空间是算法机器人中广泛使用的一个基本机器人、计算机辅助设计和相关领域的许多应用都可以归结为构形空间的计算问题。在本文中，我们回顾了我们最近的一些工作，解决了与位形空间相关的两个重要挑战：①如何有效地计算高维位形空间的近似表示;②如何在高维配置空间中高效地进行几何邻近和运动规划查询。我们提出了新的配置空间构造算法的基础上机器学习和几何逼近技术。这些算法在许多配置样本上执行冲突查询。碰撞查询结果用于计算配置空间的近似表示，该近似表示快速收敛到精确的配置空间。我们还提出了基于GPU的并行算法，以加快性能的优化和搜索计算的配置空间。特别是，我们设计了高效的基于GPU的并行k-近邻和并行碰撞检测算法，并使用这些算法来加速运动规划。关键词配置空间，运动规划，GPU并行算法1引言智能机器人在工业和日常生活中变得越来越重要。在工业领域，不断上涨的劳动力成本促使制造商考虑在工厂中使用更多的机器人。例如，在中国，2012年平均最低工资增长了20%以上，而制造业机器人的供应量也增长了51% [1]。欧洲和美国也呈现出类似的趋势：智能机器人的设计旨在提高工人的生产力，并使制造商在价格和质量方面更具竞争力。最近的一个例子是，智能机器人是新的“Baxter”机器人[2]，它配备了软件，使机器人能够从人类演示中学习各种任务，识别不同的物体，并对外力做出智能反应。智能机器人有望在日常生活中帮助人们。未来，这种机器人有望执行各种任务，包括①家庭和护理支持，如烹饪和洗衣;②健康生活支持，如与老人聊天和照顾残疾人;以及③在化工厂等不安全工作条件下的劳动力支持[3]。有几个成功的机器人助手原型。例如，Willow Garage的PR 2机器人已被证明可以帮助四肢瘫痪等严重身体残疾的人[4];而HRP-4等人形机器人可以执行类似人类的动作，并可以使用语音与人交流[5]。除了在工业和日常生活中的应用外，现代智能机器人还可以在其他领域提供帮助，包括自动驾驶汽车[6]，医疗和手术干预[7]，紧急和灾难救援[8]以及军事任务[9]。在过去十年中，智能机器人的设计和可用性的巨大改进是基于许多相关领域的进步，包括计算机视觉、人工智能、机器学习、控制、传感器系统和机械系统，它们对应于智能机器人系统的不同组件（图1）。例如，同步定位和地图绘制（SLAM）算法使机器人能够在未知环境中准确跟踪其位置[10]。此外，在先进视觉技术的帮助下，机器人现在可以从背景点云中识别和分割对象[11]。与传统的工业机器人相比，现代智能机器人系统的一个重要特征是高层次的规划和导航。它的主要目的是根据要执行的任务的高级描述计算低级指令;然后将这些低级指令提供给机器人执行器系统。这个规划和导航组件由许多不同的子组件组成（图1），1香港大学计算机科学系;2纽约大学计算机科学系Carolina，Chapel Hill，NC 27599-3175，美国* 通讯作者。电子邮件地址：jpan@cs.hku.hk接收日期：2015年3月12日;接收日期：2015年3月20日;接受日期：2015年3月25日作者（S）2015出版社：Engineering Sciences Press这是CC BY许可下的开放获取文章（http：//creativecommons.org/licenses/by/4.0/）www.engineering.org.cn第1卷·第1期·2015年3月工程047机器人-文章研究图1.机器人系统中重要的硬件和软件子系统。①前馈系统（F），包括任务规划、导航策略、运动规划和轨迹生成; ②控制系统（C），包括运动学、动力学和控制算法; ③致动器系统（A），包括电机、伺服、传动等;传感器系统（S），包括各种传感器，如摄像机、激光器、IMU，以及相关的底层传感器数据处理算法，如信号处理、估计和融合;机器人传感器后处理系统（S+），包括定位、地图绘制等。机器人系统的主要软件组件是高级规划以及导航，其在给定要执行的期望任务的情况下确定发送到致动器系统的指令。高级规划和导航的一个重要组成部分是运动规划，其重点是从环境描述中计算轨迹。在这一领域已经有了大量的工作，如任务规划[12]、观测反馈[13，14]、最优控制[15] 自适应控制[16]。高级规划和导航组件中最重要的子系统之一是运动规划系统，它使机器人能够安全地从初始位置移动到目标位置，而不会与任何静态碰撞。或移动的障碍物。一种快速的在线运动规划算法对于许多应用来说是至关重要的。例如，在制造领域中，越来越多的人需要使用移动机器人来帮助人类完成重复的、非增值的任务[17]。为了确保机器人与人类之间的安全协作，机器人需要及时对变化的环境做出反应，这就要求实时运动规划，避免任何意外。在线运动规划在提高许多传统制造过程的自动化水平的同时也至关重要。例如，对于自动箱子拾取，有效的在线运动规划对于抓取性能至关重要[18]。此外，快速规划也是服务机器人工作所需要的在医院和人类的家中。运动规划问题可以在3D工作空间中直接形式化和解决，例如使用广泛使用的势场算法[19]。然而，这些工作空间解决方案不能容易地处理具有不同几何形状和机械约束的机器人。为了克服这些困难，可以在称为配置空间的新空间中对运动规划进行形式化和求解[20-22]。在配置空间中，具有复杂几何形状的机器人在3D工作空间中被映射为点机器人，并且机器人的轨迹对应于高维配置空间中的连续曲线（图5）。基于配置空间公式，运动规划问题可以通过两个步骤来解决：(1) 构造配置空间的表示;(2) 根据计算的代表执行优化站。这种基于配置空间的运动规划流水线是非常成功的，并且被许多需要最优规划解决方案的现实世界的规划应用所采用。已经提出了配置空间的许多不同表示，包括多面体[23]，半代数集[24，25]，图[26]和树/森林[27]。针对不同的配置空间表示，提出了不同的优化方法，包括计算最短路径、计算到配置空间内闭集边界的最小距离等。此外，相同的流水线也隐含地用于一些运动规划算法中，以仅用于计算可行路径（即，不违反其它约束的无冲突路径）。例如，快速探索随机树（RRT）[27]的许多变体使用不同的算法来引导搜索朝向目标配置，同时增长搜索树结构作为配置空间的近似表示。这种策略可以被视为上述流水线的变体，其中配置空间构造与优化计算交替。然而，这种基于配置空间的算法流水线仍然存在许多计算挑战。这里描述了两个最重要的挑战(1) 有效地计算配置空间的近似或精确表示是困难的，特别是对于具有高维配置空间的高DOF（自由度）机器人。这种构形空间近似问题将具有指数复杂性。(2) 许多机器人应用需要实时规划，以便在具有移动障碍物的人类环境中可靠且有效地工作，但是在配置空间的计算表示中执行优化可能是耗时的。在本文中，我们将讨论我们最近的工作，以解决这些挑战有关的配置空间。特别地，我们首先演示如何将配置空间构造问题转换为机器学习问题，然后使用主动学习来高效且鲁棒地计算近似配置空间（第4节）。其次，我们提供了基于GPU的并行算法来加速配置空间中的优化计算，这可以允许在许多挑战环境中进行实时规划计算（第5节）。2 背景和相关工作2.1 配置空间位形空间是经典力学中用来描述和分析许多重要系统运动的关键概念[28]。通常，配置q是向量的独立参数唯一指定的状态配置空间或C空间是给定系统的所有可能配置的集合。例如，对于n个点粒子的系统，配置是描述所有粒子的位置的向量，并且相应的C空间是R3n; 3D刚体的配置研究机器人-文章048工程第1卷·第1期·2015年3www.engineering.org.cn由其位置和方向组成，如果允许旋转和平移，则配置空间为SE（3），如果只允许平移，则配置空间为R3;并且铰接对象的配置是其所有关节角度的矢量。机器人A的位形空间由两个部分组成：无碰撞空间Cfree= {q：A（q）<$B= n}和碰撞空间或障碍物空间Cobs= {q：A（q）<$B<$n}，其中B对应于环境中障碍物的几何表示，A（q）对应于具有曲率q的A。Cobs是一个闭集，它的边界表示为接触空间C=Cobs，它对应于A和B只是相互接触而没有穿透的配置集。图2显示了两个图2.两个对象的配置空间。橙色曲线突出显示A和B的接触空间C。橙色曲线内/上的点属于Cobs，橙色曲线外的点属于Cfree。红点和绿点分别表示Cobs和Cfree中的对象，其中C用橙色曲线高亮显示。在A和B都是刚性物体并且机器人A只能执行平移运动的特殊情况下，Cobs等于A和B之间的众所周知的Minkowski和：Cobs =A <$（- B）= { x = x A + xB|xA∈ A，xB∈- B }。Minkowski和的一个例子当机器人A可以执行一般运动时（即，平移和旋转），Cobs的几何形状要复杂得多，如图所示图3. 2D刚体A和B之间的间隙。对于每个旋转角度θ∈或表面）。由于C-space =Cfree<$Cobs和Cfree<$Cobs=<$，我们只需要构造Cfree的表示，或Cobs。另一个等价的解决方案是计算Cfree和Cobs之间的边界Cbits。以往的位形空间构造方法可以分为两类：基于几何的和基于拓扑的。基于几何的方法计算配置空间的精确几何表示，而基于拓扑的方法捕获配置空间的连通性。基于几何的方法通常限于低维配置空间，这是由于计算高维配置空间的Cobs的边界所涉及的组合复杂性。大多数以前的工作都集中在特殊情况下，当对象A和B是刚体只执行平移运动。如第2.1节所述，所得的Cobs是A和即使对于这种特殊情况，计算Cobs的计算复杂度仍然很高：当A和B都是凸对象时，复杂度为O（mn），当A和B都是非凸对象时，复杂度为O（m3n3）[29] ， 其 中 m 和 n 分 别 是 A 除 了 高 复 杂 度 之 外 ， 用 于 计 算Minkowski和的大多数现有实现方式易于受到在3D几何算法的上下文中出现的挑战。特别地，这些实现方式①对数值误差不鲁棒，并且②易受退化影响（即，不能可靠地处理多边形汤或具有孔的网格）。最近的工作已经提出了用于有效且可靠地计算近似Minkowski和的方法[30-32]，但是这些方法也容易产生鲁棒性问题，并且在处理复杂对象方面可能具有很高的复杂性。除了闵可夫斯基和之外，还有其他计算Cobs的方法。例如，Varadhan等人。[33]通过使用自适应网格近似Cobs来计算具有旋转和平移的2D对象的Cobs; Zhang等人。[34]使用细胞分解计算4D C空间的近似。基于拓扑的方法捕获配置空间的连通性。大多数以前的方法试图使用采样技术捕获C自由的连接性[26，27]。其基本思想是首先在C自由生成随机样本（称为里程碑），然后组织这些样本使用图结构或树结构森林（图[0，2π），我们可以计算A（θ）和- B之间的Minkowski和是将A绕原点旋转θ度后的结果形状当4）. 作为C的拓扑免费可以是相当复杂的，并且可以将所有角度θ的Minkowski和叠加，我们得到A和B之间的Cobs。图3中的2D示例。基于位形空间的概念，三维工作空间中的运动规划问题可以归结为C空间中点机器人的路径规划问题，即在C空间中寻找一条连接机器人初始位形和目标位形的曲线。2.2 位形空间构造在配置空间中执行运动规划计算之前，一个先决条件是以适当的表示（例如，的曲线图由多个组件或小而窄的通道组成，很难使用随机抽样来捕获无C的完整连接性。通过使用不同的采样策略[35-40]，在改进连通性计算方面做了大量工作。最近的工作试图捕捉Cfree和Cobs的拓扑结构[41]。基于拓扑的方法可以比基于几何的方法快得多地计算近似C空间表示。然而，这些方法不能很好地用于狭窄的通道，并且对于高DOF机器人可能很慢。2.3 位形空间一旦精确或近似地表示出了一种新的方法，www.engineering.org.cn第1卷·第1期·2015年3月工程049机器人-文章研究图4.基于拓扑的位形空间计算方法(a) 使用图结构捕获C自由;（b）使用树结构的森林捕获C自由。在计算了C-空间表示之后，我们接下来需要在该C-空间表示中执行优化。例如，目标运动规划的关键是计算C空间中的轨迹，如图5所示。轨迹应满足以下约束：①它应完全在Cfree内;②它应是可行的，例如，对于类人机器人，机器人在跟随轨迹时不应该摔倒。此外，优选地，轨迹在某些度量下是最优的。例如，最佳轨迹可能是短的-最短的执行时间，或与障碍物保持最大距离。因此，运动规划可以形式化为C空间中的约束优化问题。类似的配方可以应用于不同的应用，图5.运动规划在空间和配置空间。左图显示了障碍物（不同颜色）和2连杆机器人在工作区中（初始和目标设置）。右图为左图工作空间对应的配置空间，不同颜色表示工作空间中障碍物与配置空间中障碍物的对应关系。 蓝色曲线是连接初始配置和目标配置的轨迹， 运动规划算法。例如穿透深度计算[39，42-44]。C空间中的优化通常是计算开销较大的。特别是对于具有复杂结构和拓扑的高维C-空间。为了说明C空间优化问题的计算挑战，我们以C空间中的运动规划为例。理论上，使用C空间的精确表示的运动规划具有高计算复杂度。如果对于任何规划问题实例，规划算法将找到解决方案或将正确地报告不存在解决方案，则规划算法被认为是“完整的”。完整 的规 划算 法已 被证 明是 PSPACE-硬 [45]和 PSPACE- 完 整[24]，并且运动动力学运动规划（即，具有简单运动学或动力学约束的运动规划） 具有 被证明 被 NEXPTIME-硬[25]。对于具有一般微分约束的运动规划，可判定性仍然是未知的[46]。当使用C空间的近似表示时（例如，使用图或森林来近似Cfree的连通性），存在提供概率完整性[26，27]和/或渐近最优性[47]的保证的近似运动规划算法。这些近似运动规划算法的复杂度通常为O（nlnn），其中n是C空间近似表示中使用的配置样本数[47]。由于当Cfree具有窄通道和/或高维数时，n可能非常大[48]，因此这些近似算法的性能仍然远远不能达到实时。在过去的几十年中，已经提出了与C空间相关的各种规划方法，包括基于优化的规划算法，如CHOMP [49]和TrajOPT[50]，以及基于搜索的算法，如Anytime A* [51]。对于高自由度机器人的运动规划，大多数实用方法都基于随机算法，包括概率路线图（PRM）[26]和RRT [27]。3 概述我们对与配置空间相关的挑战的解决方案包括两个部分，分别用于配置空间优化和配置空间优化。3.1 有效的配置空间构造在第一部分[52]中，我们提出了一种新的算法，使用机器学习技术有效地近似高维配置空间。其主要思想是在位形空间中生成样本，然后用这些样本通过一个分离面来逼近接触空间C，该分离面能正确地分离所有的碰撞样本和无碰撞样本。该分离表面使用支持向量机（SVM）分类计算。我们的方法通过利用增量和主动学习技术大大减少了所需的样本数量。当样本数增加时，由我们的方法计算的近似接触空间可以快速收敛到精确接触空间;我们还提供了近似接触空间中的预期误差的界。我们评估的性能，我们的算法在高维基准。为了构造配置空间的表示，我们使用离线学习算法，如图6中的左框所示。我们首先在C-空间的子空间中为两个给定的对象生成一个小的均匀样本集。接下来，我们证明这些配置是否位于C自由或在Cobs通过执行两个对象之间的精确碰撞检查。我们用记法c（q）∈{–1 if 给定所有配置样本的碰撞状态，使用分类器计算接触空间的粗略近似值LCS0（图6（b）），其中LCS代表学习的接触空间。接下来，我们在C空间中选择新的样本，以进一步提高使用主动学习的初始表示LCS0的准确性。在主动学习过程中，我们要么选择远离先前样本的样本（探索）（图6（c）），要么选择接近LCS0的样本（探索）。研究机器人-文章050工程第1卷·第1期·2015年3www.engineering.org.cn（图6（d））。在生成新样本之后，我们基于增量机器学习技术计算更新的近似LCS1（图6（e））。我们重复这个过程，生成近似表示LCS0，LCS1，.，越来越精确。重复该迭代过程，直到所有新样本的碰撞状态可以通过当前近似正确地预测。最终结果LCS（图6（f））对应于接触空间的光滑表面近似。3.2 位形空间通过我们工作的第一部分计算的近似接触空间可以直接用于运动规划，例如，通过将其用作轨迹优化框架中的无碰撞约束[53]。然而，该约束是高度非凸的。因此，解决由此产生的优化问题仍然是不平凡的，这是我们正在进行的工作的重点之一。解决运动规划问题的另一种方法是使用对配置空间的基于样本的近似，这已经被许多传统的规划算法（诸如PRM）所采用。在本文的第二部分[54]中，我们提出了一种用于高自由度机器人实时运动规划的新型并行算法，该算法利用了400美元商品图形处理单元（GPU）的计算能力。当前的GPU是可编程的众核处理器，其可以支持数千个并发线程。我们使用它们来实时计算PRM和惰性规划器。我们描述了高效的并行策略，用于构建路线图，包括样本生成，碰撞检测，连接附近的样本，和本地规划。查询阶段也基于图搜索并行执行。为了设计一个高效的单查询规划器，我们使用了延迟冲突检查和局部规划的策略。我们还描述了新的基于层次的碰撞检测算法，以加快整体性能。我们选择PRM算法作为并行规划的基础方法，因为它最适合在GPU上开发多核和数据并行性。PRM算法分为两个阶段：路线图构建和查询.路线图构建阶段包括四个主要步骤：①在配置空间中生成样本;②通过执行离散碰撞查询来计算与自由空间中的样本相对应的里程碑;③对于每个里程碑，找到与其最近的其他里程碑;以及使用本地规划将附近的里程碑连接起来，并形成路线图。查询阶段包括两个部分：①将查询的初始配置和目标配置连接到路线图，②在路线图上执行图搜索算法并找到无冲突路径。部分PRM算法，如碰撞查询，是并行的[55]。我们可以使用众核GPU来显著增强其他组件的性能。我们的PRM算法在GPU上的框架如图7所示。我们并行化的PRM算法的六个步骤中的每一个有效地。首先，多核GPU的每个线程生成一个随机的机器人配置，其中一些配置将与障碍物碰撞。所有是里程碑并且成为路线图的顶点。接下来，每个GPU线程计算单个里程碑的k个最近邻居，并收集所有邻居对。 然后，每个线程检查是否可以通过执行本地规划来连接这些相邻对。如果在相邻的一对里程碑之间存在无冲突路径，我们将边缘添加到路线图中。路线图构建完成后，到路线图中，我们使用并行图搜索算法来查找路径。由此产生的基于GPU的框架非常有效，规划问题的多查询版本。在这种计算中最昂贵的步骤是局部规划算法，因此，我们使用新的碰撞检测算法，以im-crossing算法。图6. 离线计算流水线的C近似。LCS的不同近似值显示在相应阶段的下方。我们用绿色点表示无碰撞配置样本，红点表示碰撞样本。（a）精确接触空间（供参考）;（b）初始模型;(c)探索;（d）开发;（e）第i次迭代后的解;（f）最终近似接触空间。www.engineering.org.cn第1卷·第1期·2015年3月工程051机器人-文章研究受我我图7. PRM概述和我们算法中的并行组件。证明其性能。为了加速单查询算法，我们引入了一个解决方案，使用懒惰的策略和延迟碰撞检查的本地规划。换句话说，该算法连接所有对应的边到最近的邻居，并搜索初始和最终配置之间的路径。之后，它在构成这些路径的边缘上执行局部规划。tors，它是学习中使用的配置样本的一个小子集。直觉上，S是最接近C的样本。我们使用SVM分类器[56]从初始值中学习LCS0k个配置的样本。SVM生成的决策函数是一个光滑的非线性曲面。我们使用硬边缘SVM，因为底层样本总是可以分为无碰撞空间和碰撞空间。实际上，SVM使用函数来映射给定的样本{qi}从输入空间到更高（可能是无限）维的特征空间。SVM计算由参数w和b表征的线性分离超平面。超平面的最大边缘在高维特征空间中。超平面对应于输入空间中的非线性分离曲面。w是超平面的法向量，参数b确定超平面沿法向量从原点的偏移。在特征空间中，超平面与最近的样本点之间的距离称为“边缘”，最佳分离超平面应使该距离最大化。最大裕度可以通过求解以下优化问题来实现：14 基于学习的近似接触空间minw，b||2||22（一）建设在这一节中，我们提出了我们的算法离线学习的接触空间和计算LCS。该算法的不同阶段如图6所示。4.1 初始采样我们在C-空间中进行均匀采样，以获得一组配置点。我们不是对整个C空间进行采样，而是在包含C的子空间中生成样本。给定S.T. c（w·n（q）+b）≥1， 1≤i ≤k其中ci∈{我们定义K（qi，qj）=T（qi）T（qj）作为核函数（即，用于计算特征空间中的内积的函数）。我们使用径向基函数（RBF）核在我们的结果。Eq的解。(1)是输入空间中的非线性曲面（以及特征空间中的超平面），其分离无碰撞配置和碰撞配置。该解可以公式化为：K两个物体A和B，接触空间C包含在f（q）=w*·k（q）+b*=∑α c K（q，q）+b*（二）它们的包围体BV（A）和BV（B）的碰撞空间4.2 计算LCS0给定来自Cobs（BV（A），BV（B））的一组k个样本，我们在A和B之间执行精确的碰撞查询，以检查这些样本是否在碰撞空间内。我们的目标是从这些构型中学习近似表示LCS0。特别地，LCS0对应于完全由C空间中的一组配置S确定的决策函数f（q）= 0。我们将f（q）称为分类器，并使用它来预测给定的配置q是否是无冲突的（f（q））。<0）或碰撞中（f（q）> 0）。S对应于支持向量机我我我i= 1其中w * 和b*是方程的解。(1)且αi≥0。对应于非零αi的向量qi称为支持向量，记为S。直观地，支持向量是最接近分离超平面f（q）= 0的那些样本，如图6（b）中较大的红色和绿色点所示。因此，LCS0是LCS0（q）的一个非线性函数=f（q）和一组样本SLCS0= S（即，所述方法包括以下步骤：其用于近似精确的接触空间。4.3 使用主动学习优化LCS0我们使用主动学习来改进LCS0目标是积极图8. LCS计算使用2D星形模型和房间模型之间的2D接触空间的主动学习，如图6中的学习管道的输入所示。我们突出显示对应于LCSi的支持向量的数量。(a) i = 0，|S| = 37;（b）i = 4，|S| = 75;（c）i = 8，|S| = 198;（d）i = 14，|S|（e）i = 20;|S| = 654。研究机器人-文章052工程第1卷·第1期·2015年3www.engineering.org.cn图9.使用主动学习的LCS计算，用于2D星形和房间模型之间的3D接触空间，如图6中的学习管道的输入所示。 我们突出显示对应于LCS i的支持向量的数量。垂直轴表示C空间的旋转分量（a）LCS0，|S|= 88;（b）LCS5，|S| = 174;（c）LCS9，|S| = 237;（d）LCS12，|S| = 248。选择新的样本，以便通过将这些样本合并到LCS0中可以获得更好的近似接触空间表示LCS1。我们使用勘探和开发相结合的方法[57]。这个想法是通过掷一个有偏见的硬币来确定是探索还是利用，硬币有一定的正面着陆概率（最初为0.5）。如果结果是正面，我们采用探索法，如果是反面，我们采用剥削法。根据由当前LCS i正确预测的探测样本的碰撞状态的分数来调整头上着陆的概率新样本用于更新LCS0并生成新的近似LCS1（或从LCSi细化到LCSi+1）。我们重复主动学习步骤，直到所有新样本都可以被当前LCSi正确预测，或者最终结果（表示为LCS）具有足够的精度来近似C。4.4 增量学习我们应用增量学习技术从LCSi有效地计算LCSi+1，而不是使用所有以前的样本从头开始计算新的决策函数。智能学习利用一小组新样本来更新LCSi。LCSi的决策函数用作生成LCSi+1的初始猜测。增量SVM [58]可以更新使用SVM生成的当前结果;关键是保留等式的最优性条件。(1)（即，Kuhn-Tucker条件），同时添加新的样本。这是通过调整方程中的系数αi和b来(2)并通过调整支持向量集S。系数调整和支持向量变化由等式（1）中的目标函数的梯度引导。（二）、4.5 终止主动学习当出现以下任何一种情况已满足：(1) 在勘探和开采过程中产生的所有新样本的碰撞状态可以正确地预测由当前近似LCSi。(2) 在主动学习中使用的样本总数-erations大于用户指定的阈值。第一个条件保证用于学习LCS的所有配置是一致的（即，它们可以由LCS正确地预测）。这意味着当前LCS是底层接触空间的近似。第二个条件控制近似C的精度：随着使用更多的样本，我们得到更好的近似C。5 基于GPU的组态空间实时优化在本节中，我们将详细介绍如何使用GPU加快了配置空间的优化速度。5.1 层次计算我们为机器人构建了一个包围体层次结构（BVH），并为环境中的每个障碍物构建了一个包围体层次结构，以加速冲突查询。我们使用参考文献[59]中介绍的基于GPU的构造算法，对于给定的三角形表示，该算法可以在GPU上并行构造轴对齐边界框或定向边界框（OBB）的层次结构。对于碰撞检测，我们使用OBB层次结构，因为它提供了更高的剔除效率和类似GPU的架构上的性能改进。这些层次结构存储在GPU内存中，我们适用于不同的配置适当的转换。5.2 路线图建设路线图构建阶段尝试捕获自由配置空间的连通性，这是PRM算法的主要计算密集部分。(1) 样本生成：我们首先需要在配置空间中生成随机样本。由于样本是独立的，我们调度足够的并行线程来利用GPU并使用MD5加密哈希函数[60]，这在实践中提供了良好的随机性，而无需共享种子。(2) 里程碑计算：对于上一步中生成的每个配置，我们需要检查它是否里程碑：即，位于自由空间中的配置并且不会与障碍物碰撞。我们使用一个层次的碰撞检测方法，使用BVH测试之间的重叠的障碍物和机器人的配置定义的样本。在每个线程中通过使用两个BVH中的遍历算法来执行冲突检测。遍历算法从两个BVH根节点开始，并以递归方式测试OBB节点的重叠。如果两个节点重叠，那么应该递归地测试其子节点的所有可能配对是否相交。我们还使用GPU来计算实际的BVH结构对于机器人和障碍物，使用并行层次结构构造算法[59]。由于机器人的几何对象移动取决于配置，其BVH仅对初始配置有效。为了避免重新计算-www.engineering.org.cn第1卷·第1期·2015年3月工程053机器人-文章研究在为每个配置创建BVH之前，我们在执行重叠测试之前用当前配置样本转换机器人BVH的每个节点。因此，只有在碰撞测试期间实际需要的节点才被转换。(3) 邻近计算：对于计算的每个里程碑，我们需要找到它的k-最近邻（k-NN）.一般来说，有两种类型的k-NN算法：精确k-NN和近似k-NN，这是更快的，允许一个小的放松。我们的邻近算法是基于一个范围查询，使用BVH结构的配置空间中的点。对于3-DOF欧几里得空间，我们首先使用并行算法[59]为所有里程碑构建BVH结构。对于每个构形q，我们把它封闭在一个轴向对齐的盒子里：一个以q为中心，边长为2ε的盒子。接下来，我们遍历BVH树以找到所有叶节点（即，配置），ε箱。这简化为q的范围查询。对于一个非欧核素-一个自由度，我们复制样本，将其转换到一个欧几里德空间本地。例如，假设 一个 DOF 是 旋转 角 α∈[0 ， 2π] 。 我们 添加 另 一个 样本 α*∈[−π，3π]，距离α为2π。如果所有的3-DOF都是旋转，我们需要为每个里程碑添加另外7个样本。一旦范围查询完成，我们从所有查询结果中选择k-最近的;这给了我们精确的最近邻居。通过使用分解策略，这种方法可以扩展到处理高维空间中的k-NN搜索;细节在我们最近的工作中[61]。为了进一步提高近距离计算机的性能针对高维空间中的k-近邻问题，提出了一种新的k-近邻算法，该算法利用局部敏感哈希（LSH）和布谷鸟哈希算法在GPU上并行高效地计算近似k-近邻。有关更多详细信息，请参阅我们最近的工作[62]。(4) 局部规划：局部规划检查两个里程碑之间是否存在局部路径，该路径对应于路线图上的边。它是PRM算法中最昂贵的部分。假设我们有nm 个里程碑，每个里程碑最多有nk个最近的邻居。该算法最多执行nm·nk次局部规划。如果我们使用DCD，那么我们最多需要执行nl = nm·nk·ni个冲突查询，这对于复杂的基准测试来说可能非常高。 对于多查询问题，这个成本可以在多个查询中分摊，因为路线图只构建一次。 对于单查询问题，计算整个路线图的成本太高。因此，在单查询的情况下，我们使用一种惰性策略来推迟本地规划，直到绝对必要的时候。给定一个查询，我们计算从初始到最终配置的路线图中的几个不同的候选路径，并且只检查候选路径上的路线图边缘的局部规划。局部规划可能会得出结论，其中一些边是无效的，在这种情况下，我们将它们从路线图中删除。如果存在一条没有无效边的候选路径，则该算法找到了无冲突的解决方案。否则，我们在更新的路线图上再次计算候选路径，并重复上述过程。这种惰性策略可以大大提高单个查询的性能。5.3 查询阶段查询阶段包括两个部分：将查询连接到路线图和执行图搜索以找到路径。(1) 查询连接：给定单个查询中的初始目标配置，我们将它们连接到路线图。对于这两种配置，我们在路线图上找到k个最近的里程碑，并在查询和里程碑之间添加可以通过本地规划连接的边。我们使用与路线图构建阶段相同的算法，除了使用的k(2) 图搜索：搜索算法试图在路线图上找到连接初始配置和目标配置的路径。我们使用深度优先搜索（DFS）或广度优先搜索（BFS）进行图搜索。对于多查询情况，每个GPU线程使用DFS遍历一个查询的路线图，最终结果是无冲突路径。对于单查询情况，我们利用所有GPU线程使用BFS搜索来找到一个查询的路径：对于距离初始节点相同步数的节点，我们将其未访问的邻居并行添加到队列中。换句话说，不同的GPU核心遍历图形的不同部分。 这种方法的主要挑战是，随着BFS的遍历，进步，并且不同核上的计算负载可能显著变化。为了解决负载平衡和工作分配问题，以保持所有核的并行性，我们使用了参考文献[1]中的轻量级负载平衡策略。[63].6 实验在本节中，我们将研究我们的方法的性能，同时解决与配置空间相关的两个挑战。6.1 位形空间构造我们已经使用了一组复杂的基准来评估我们的算法的接触空间近似结果。我们首先计算所示2D对象的接触空间作为图6中的学习管道的输入。在这个实验中，物体A只能进行平移运动，而物体B是固定的。由此产生的配置空间有2个自由度，通过我们基于学习的方法计算的LCS曲面系列如图8所示。我们可以看到，经过几百个样本的几次迭代，学习的LCS可以很好地近似这两个对象之间的精确接触空间。接下来，我们计算同一对2D对象，但我们现在允许对象A执行旋转在2D平面上。生成的构形空间具有3个自由度，生成的LCS曲面系列我们的方法如图9所示。与2D接触空间的情况类似，学习的接触空间可以快速收敛到精确接触空间的良好近似。最后，我们计算图10（a）中所示的一对3D对象的接触空间，其中对象A仅可以不接触。研究机器人-文章054工程第1卷·第1期·2015年3www.engineering.org.cn图10. LCS计算使用主动学习3D杯子和勺子之间的3D接触空间。我们提供对应于LCSi的支持向量的数量。如图所示，该算法可以在几次迭代中计算出良好的近似值。(a)对象A和B;（b）LCS0，|S| = 231;（c）LCS5，|S| = 869;（d）LCS9，|S| = 1350;（e）LCS12，|S| = 1572。因此相应的配置空间是三维的。类似地，我们可以观察到学习的接触空间序列快速收敛到精确的接触空间。6.2 位形空间我们目前的细节，我们的实施和评估我们的算法的性能在一组基准。这里报告的所有时间都是在一台使用英特尔酷睿i7 CPU（约600美元）、3.2 GHz CPU和6 GB内存的机器上进行的。我们使用CUDA在具有1 GB视频内存的NVIDIA GTX 285 GPU（约380美元）上实现了我们的算法。RRT），设置与C-PRM相同。表1显示了算法之间的时序比较。一般来说，G-PRM比C-PRM快10倍，GL-PRM可以为单查询问题提供另外10倍的加速。即使对于动态场景，G-PRM也比C-PRM快。目前的C-RRT和C-PRM都是单核版本。然而，即使是多核版本的PRM也只能将时序最多提高4倍，因为在8核CPU上，很难线性地扩展层次计算和最近邻计算。我们的GPU算法仍然可以提供比CPU算法高1-2个数量级的性能图11.用于我们算法的基准场景按以下顺序：钢琴（2484个三角形），直升机（2484个三角形），迷宫3d1（40个三角形），迷宫3d2（40个三角形），迷宫3d3（970个三角形）和阿尔法拼图（2016个三角形）。我们在GPU上实现了PRM算法（G-PRM）用于多查询规划问题，并实现了其懒惰版本（GL-PRM）用于单查询问题。我们将这些与OOPSMP库[64]中实现的PRM和RRT算法进行比较，OOPSMP库是CPU上运动规划算法的流行库。所使用的基准测试如图11所示。我们的比较设计如下：对于每个基准，我们找到一个合适的设置，CPU-PRM（C-PRM）找到一个解决方案，然后我们运行G-PRM与可比数量的样本。之后，我们使用与G-PRM相同的设置运行GL- PRM，并运行CPU-RRT（C-表1.左边两列评估OOPSMP中PRM和RRT算法的性能。右边的两列评估了我们基于GPU的算法的性能。C-PRMC-RRTG-PRMGL-PRM钢琴6.53 S十九点四十四秒1.71 S111.23毫秒直升机8.20 S20.94秒2.22 S129.33毫秒迷宫3d1138.00秒二十一点十八秒14.78秒71.24毫秒迷宫3d269.76秒十七点四十分十四点四十七秒408.60毫秒迷宫3d38.45 S4.30 S1.40 S96.37毫秒阿尔法1.565.73秒2.80 S12.86秒1446.00毫秒图12显示了G-PRM和GL-PRM的各个步骤之间的时序细分。这两种算法的性能之间的差异是显而易见的：在G-PRM中，局部规划是瓶颈，并主导了时间，而在GL-PRM中，图搜索花费更长的时间，因为局部规划是以惰性或输出敏感的方式执行的。在GL-PRM中，三个组件占用最多的时间：里程碑图12.时间分割：在G-PRM和GL-PRM的不同部分花费的时间比例。www.engineering.org.cn第1卷·第1期·2015年3月工程055机器人-文章研究构造、邻近度计算和图搜索，因为所有这些都可能严重执行冲突查询。如果环境混乱，模型具有复杂的几何形状，里程碑的构建将会很慢（图12中的alpha谜题）。如果环境是一个开放的空间，并且有许多里程碑，那么邻近计算将成为瓶颈（图12中的maze3d2）。如果懒惰策略不能猜测正确的路径，那么由于大量的冲突查询（图12中的maze3d3），图搜索将是计算密集型的。然而，在所有这些环境中，GL-RPM优于所有其他方法。我们在maze 3d 3基准上测试了G-PRM和GL-PRM的可伸缩性，结果如图13所示。很明显，GL-PRM通常比G-PRM更快，并且两种算法在基准上都实现了近线性缩放。然而，观察到随着样本数量的增加，GL-PRM比G-PRM慢得更快。这是因为当样本数量增加时，邻近计算变得越来越昂贵，并且当样本数量接近100万时，邻近计算支配定时。图13. G-PRM和GL-PRM的可扩展性。我们的方法可以被扩展用于对关节体的有效规划，并且可以实现PR2抓取操作的实时性能，如图14所示。图14.我们的基于GPU的运动规划器可以在不到1的时间内计算出PR2的无碰撞路径。（a）PR 2模拟;（b）真实PR 2。7 结论本文讨论
我的内容管理
展开
