用随机分割法快速生成点云障碍物间的安全路径区域
PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds
- 基于随机迭代空间分割，直接从原始点云生成凸多面体
- 速度比现有方法快一个数量级，保持相近路径体积
- 适合实时导航的机器人系统，尤其擅长复杂环境
自主机器人导航需要快速生成无碰撞区域以支持轨迹规划。然而，现有走廊生成方法难以满足实时传感器速率的计算要求。为此，我们提出 PathCover 框架，其核心是 RISP——一种新型随机算法，在温和的概率消除条件下可在线性期望时间内直接从原始点云数据构建凸多面体。PathCover 生成一系列重叠的无障碍物多面体，可安全约束下游模型预测控制（MPC）与轨迹优化。数学上保证算法在有限步内终止，并沿任意无障碍参考路径持续推进。在合成与真实世界 LiDAR 数据集上的大量基准测试显示，该方法相较当前最优方法实现数量级提速，同时保持相近的走廊体积。完整流程通过高保真四旋翼仿真及四足机器人实际部署验证，可在动态 LiDAR感知下完成受限环境导航。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。