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

• URL: http://arxiv.org/abs/2608.05586v1
• Date: Thu, 06 Aug 2026 04:17:13 GMT
• Title: PathCover: A Fast Convex Decomposition along a Path via Randomized Iterative Space Partitioning (RISP) on Point Clouds
• Abstract summary: We introduce PathCover, a framework driven by RISP to generate obstacle-free regions for autonomous robot navigation.<n>We mathematically guarantee the algorithm terminates in finite steps while ensuring continuous progress along any obstacle-free reference path.<n>The complete pipeline is validated via high-fidelity quadpedal simulations and physical deployment on a quadrurotor robot.
• Score: 7.061252397888759
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Nonlinear Model Predictive Control via Sequential Convex Programming for Drone-to-Drone Docking [0.0]
  This work formulates the docking task as a finite-horizon optimal control problem based on a reduced-order nonlinear model augmented with disturbance states.<n>The resulting problem is solved using sequential convex programming within a receding-horizon framework to generate dynamically feasible docking trajectories.
  arXiv  Detail & Related papers  (2026-08-11T06:27:45Z)
• GASP: GPU-Accelerated Safe Planner for Real-Time Collision-Aware Motion Generation with Latent Trajectory Sampling [1.2669530824264628]
  We present GASP, a GPU-Accelerated Safe Planner for real-time, collision-aware joint-space motion generation in known environments.<n>GASP combines a clamped B-spline trajectory parameterization with a convolutional residual neural network that predicts the free interior control points.<n>We validate GASP as an online motion-generation module, where it achieves analytical-level success rates with high collision-aware feasibility.
  arXiv  Detail & Related papers  (2026-08-05T09:18:16Z)
• Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
  We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
  arXiv  Detail & Related papers  (2026-08-03T19:48:24Z)
• AutoPath: Learning Transferable Goal-Conditioned Stochastic Path Prior for Safe Navigation Without Human Demonstrations [103.61864552260316]
  Real-time navigation in dynamic environments requires collision-free and dynamically feasible motion under limited perception.<n>We formulate navigation as learning a transferable goal-aligned path prior that models a reusable distribution over goal-aligned geometry-consistent local paths conditioned on local observations.<n>We develop a structured prior learning framework that parameterizes local paths using a geometry-aware polar action manifold and incorporates risk-sensitive utility shaping with multi-goal distributional rollouts for stable and safety-aware planning.
  arXiv  Detail & Related papers  (2026-07-13T16:00:41Z)
• Integrated Graph Search and Model Predictive Control for Smooth and Efficient Path Planning in Autonomous Vehicles [1.228397872697275]
  A rough path is first obtained via Dijkstra search on a discretized grid.<n>A Model Predictive Control problem is formulated to refine the path.<n>The proposed algorithm is evaluated in multiple overtaking scenarios on both straight and curved roads.
  arXiv  Detail & Related papers  (2026-07-05T12:14:33Z)
• Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM [0.0]
  In structured multi-agent projects, agents often must follow predefined routes, making rerouting or impossible.<n>This paper addresses route-constrained multi-agent coordination by optimizing waypoint times while preserving each agent's assigned waypoint order and nominal route assignment.
  arXiv  Detail & Related papers  (2026-03-23T12:34:18Z)
• Amortizing Trajectory Diffusion with Keyed Drift Fields [2.5352713493505785]
  Keyed Drifting Policies is a one-step trajectory generator trained with a drift-field objective.<n>It repels generated trajectories toward condition-matched dataset windows.<n>It achieves strong performance with one-step inference and substantially lower planning latency than diffusion sampling.
  arXiv  Detail & Related papers  (2026-03-14T17:56:15Z)
• Spatially-Aware Adaptive Trajectory Optimization with Controller-Guided Feedback for Autonomous Racing [74.83272587893508]
  We present a framework for autonomous raceline optimization that combines NURBS-based trajectory representation, CMA-ES global trajectory optimization, and controller-guided spatial feedback.<n>In simulation, our approach achieves a 17.38% lap time reduction compared to a controller parametrized with maximum static acceleration.<n>On real hardware, tested with different tire compounds ranging from high to low friction, we obtain a 7.60% lap time improvement without explicitly parametrizing friction.
  arXiv  Detail & Related papers  (2026-02-17T15:10:44Z)
• FlowConsist: Make Your Flow Consistent with Real Trajectory [99.22869983378062]
  We argue that current fast-flow training paradigms suffer from two fundamental issues.<n> conditional velocities constructed from randomly paired noise-data samples introduce systematic trajectory drift.<n>We propose FlowConsist, a training framework designed to enforce trajectory consistency in fast flows.
  arXiv  Detail & Related papers  (2026-02-06T03:24:23Z)
• Unifying Environment Perception and Route Choice Modeling for Trajectory Representation Learning [47.00223863430964]
  Tray Learning (TRL) aims to encode raw trajectories into low-dimensional vectors, which can be leveraged in various downstream tasks, including travel time estimation, location prediction, and trajectory similarity analysis.<n>We propose a framework that unifies comprehensive environment textbfPertemporal explicit textRoute choice modeling for effective textbfPRTrajectory representation learning, dubbed textbfPRTraj.
  arXiv  Detail & Related papers  (2025-10-16T15:55:28Z)
• Enhancing Path Planning Performance through Image Representation Learning of High-Dimensional Configuration Spaces [0.4143603294943439]
  We present a novel method for accelerating path-planning tasks in unknown scenes with obstacles.<n>We approximate the distribution of waypoints for a collision-free path using the Rapidly-exploring Random Tree algorithm.<n>Our experiments demonstrate promising results in accelerating path-planning tasks under critical time constraints.
  arXiv  Detail & Related papers  (2025-01-11T21:14:52Z)
• Risk-Averse MPC via Visual-Inertial Input and Recurrent Networks for Online Collision Avoidance [95.86944752753564]
  We propose an online path planning architecture that extends the model predictive control (MPC) formulation to consider future location uncertainties. Our algorithm combines an object detection pipeline with a recurrent neural network (RNN) which infers the covariance of state estimates. The robustness of our methods is validated on complex quadruped robot dynamics and can be generally applied to most robotic platforms.
  arXiv  Detail & Related papers  (2020-07-28T07:34:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.