PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds

📄 arXiv: 2608.05586v1 📥 PDF

作者: Kunal S. Narkhede, Abhijeet M. Kulkarni, Guoquan Huang, Ioannis Poulakakis

分类: cs.RO

发布日期: 2026-08-06

备注: 13 pages, 5 figures

💡 一句话要点

提出PathCover以解决自主机器人导航中的障碍物区域生成问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 自主导航 凸多面体 随机化算法 点云处理 实时计算 轨迹优化 机器人技术

📋 核心要点

  1. 现有的走廊生成方法在实时性和计算效率上存在瓶颈，难以满足自主导航的需求。
  2. PathCover框架结合随机化算法RISP，能够从点云数据中快速构建凸多面体，显著提高了计算效率。
  3. 实验结果显示，PathCover在合成和真实世界的LiDAR数据集上实现了显著的速度提升，同时保持了走廊体积的可比性。

📝 摘要（中文）

自主机器人导航需要快速生成无障碍区域以进行轨迹规划。然而，现有的走廊生成器在实时和传感器速率计算约束下表现不佳。为了解决这一瓶颈，本文提出了PathCover框架，利用一种新颖的随机算法RISP，从原始点云数据中以期望线性时间构建凸多面体。PathCover生成重叠的无障碍多面体序列，安全约束下游的模型预测控制和轨迹优化。我们数学上保证该算法在有限步骤内终止，并确保沿任何无障碍参考路径的持续进展。大量基准测试表明，该方法在速度上比现有最先进的方法快一个数量级，同时保持相似的走廊体积。

🔬 方法详解

问题定义：本文旨在解决自主机器人导航中障碍物区域快速生成的问题。现有方法在实时性和计算效率上存在显著不足，无法满足传感器速率的要求。

核心思路：PathCover框架通过引入随机化算法RISP，直接从原始点云数据中构建凸多面体，期望在有限时间内完成计算，从而提高导航效率。

技术框架：该框架主要包括数据输入、随机化空间划分、凸多面体生成和后续轨迹优化等模块。通过这些模块的协同工作，PathCover能够快速生成无障碍区域。

关键创新：PathCover的核心创新在于RISP算法的引入，使得算法在期望线性时间内完成计算，并且在保证算法终止的同时，确保沿无障碍路径的持续进展。这一设计与现有方法相比，显著提升了计算效率。

关键设计：在算法设计中，设置了适当的概率消除条件，以确保算法的有效性和稳定性。此外，算法的参数设置经过优化，以适应不同的环境和数据特征。具体的损失函数和网络结构细节在论文中进行了详细描述。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，PathCover在合成和真实世界的LiDAR数据集上实现了比现有最先进方法快一个数量级的速度提升，同时保持了相似的走廊体积。这一显著的性能提升为实时导航提供了新的可能性。

🎯 应用场景

该研究的潜在应用领域包括自主机器人导航、无人机飞行控制和智能交通系统等。通过快速生成无障碍区域，PathCover能够提高机器人在复杂环境中的导航能力，具有重要的实际价值和广泛的应用前景。

📄 摘要（原文）

Autonomous robot navigation requires the rapid generation of obstacle-free regions for trajectory planning. However, existing corridor generators struggle to meet real-time, sensor-rate computational constraints. To resolve this bottleneck, we introduce PathCover, a framework driven by RISP; a novel randomized algorithm that constructs convex polytopes directly from raw point cloud data in expected linear time under a mild probabilistic elimination condition. PathCover generates sequences of overlapping, obstacle-free polytopes that safely constrain downstream MPC and trajectory optimization. We mathematically guarantee that the algorithm terminates in finite steps while ensuring continuous progress along any obstacle-free reference path. Extensive benchmarks on synthetic and real-world LiDAR datasets demonstrate an order-of-magnitude speedup over state-of-the-art methods while maintaining comparable corridor volumes. The complete pipeline is validated via high-fidelity quadrotor simulations and physical deployment on a quadrupedal robot navigating constrained environments using live LiDAR perception.