Search papers, labs, and topics across Lattice.
This paper introduces PathCover, a novel framework that utilizes a randomized iterative space partitioning (RISP) algorithm to efficiently generate convex polytopes from point cloud data for real-time obstacle-free trajectory planning in autonomous robots. By achieving expected linear time complexity under a mild probabilistic condition, PathCover significantly accelerates corridor generation, providing overlapping polytopes that enhance model predictive control (MPC) and trajectory optimization. Extensive evaluations on both synthetic and real-world LiDAR datasets reveal that PathCover offers an order-of-magnitude speedup compared to existing methods while preserving corridor volume integrity, validated through simulations and physical robot deployments.
Achieving real-time obstacle-free navigation, PathCover accelerates corridor generation by an order of magnitude while maintaining corridor volume integrity.
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.
