Collision-Affording Point Trees: SIMD-Amenable Nearest Neighbors for Fast Collision Checking

对于实时机器人控制来说，基于传感器数据的运动规划通常是一个关键的瓶颈。对于采样式运动规划器，这种方法对于高维系统（如机械臂）非常有效，但最耗时的组成部分是碰撞检查。我们提出了一种新颖的空间数据结构——碰撞允许点树（CAPT）：这是一种精确的点云表示，可以将机器人和点云之间的碰撞检查查询加速一个数量级，3D场景中的平均查询时间不到10纳秒，包含数千个点。使用CAPT，采样式规划器可以在不到1毫秒的时间内生成有效的高质量路径，在单个消费级CPU的一个线程上，总的端到端计算时间比60 FPS更快。我们还提出了一种基于空间填充曲线的点云过滤算法，可以减少点云中的点数同时保留结构。我们的方法使机器人能够在感知环境下以实时速度进行规划，为高维系统在动态、变化和未建模环境中的规划开辟了潜在的用途。

CAPT论文试图通过提出一种新的空间数据结构来加速机器人与点云之间的碰撞检测，从而加速高维机器人的路径规划。

论文提出了一种新的空间数据结构——碰撞点树（CAPT），用于加速机器人与点云之间的碰撞检测，使得基于采样的路径规划器可以在毫秒级内生成有效的高质量路径。

实验表明，CAPT可以在包含数千个点的3D场景中实现平均查询时间小于10纳秒的碰撞检测。同时，论文还提出了一种基于空间填充曲线的点云过滤算法，可以在保留结构的同时减少点云中的点数。这篇论文的方法可以使得机器人在感知环境中以实时速度进行路径规划，开辟了高维机器人在动态、变化和未建模环境中进行路径规划的潜在应用。

最近的相关研究包括：1）基于采样的路径规划器；2）点云过滤算法；3）碰撞检测算法。其中，与CAPT最相关的研究包括：1）OctoMap：一种用于表示3D空间的八叉树结构；2）Kd-Tree：一种用于高效查询的树形数据结构；3）BVH：一种用于加速碰撞检测的层次包围盒结构。