CS Paper Radar

Towards Kinematic Actionable Infeasibility Detection in Motion Planning

Aayush Rath, Lakshya Jindal, Antony Thomas

cs.RO cs.CG ·submitted 2026-09-26 17:27 UTC · v2
top venue

Abstract

Motion planning in robotics requires not only computing collision-free paths but also certifying infeasibility when no such path exists. Complete methods are limited to low-dimensional spaces, while sampling-based planners scale efficiently but cannot provide finite-time infeasibility certificates, leaving this problem largely unresolved in high-dimensional spaces. In this letter, we present a geometry-driven framework for certifying infeasibility through an explicit resolution-dependent analysis of configuration space topology. Leveraging signed distance field representations, the proposed method traces separating manifolds induced by obstacle boundaries directly in configuration space, enabling both detection of infeasibility and identification of the specific geometric cause. To address computational challenges, we develop a parallel frontier-expansion algorithm that exploits GPU acceleration for efficient simplicial reconstruction in high-dimensional spaces. We validate the approach on 4-DOF and 5-DOF robot scenarios, certifying infeasibility within seconds for 4-DOF cases and under four minutes for 5-DOF cases. We further discuss avenues for improving scalability to higher-dimensional spaces.

Comment
Accepted for publication in IEEE Robotics and Automation Letters (RA-L)
DOI
10.1109/LRA.2026.3746038

Closest papers

Nearest neighbours by meaning across the whole index.

ReVAMP: Vector-Accelerated Motion Planning for Kinematically-Constrained Systems via Reparameterization

cs.RO ·2026-09-24 ·Shrutheesh R. Iyer, Thomas Cohn, Zachary Kingston
similarity 0.70
Abstract

Robots often must satisfy one or more constraints during motion planning for real-world tasks. When such constraints reduce the valid configuration space to a measure-zero subset, sampling based planning algorithms require modifications to draw feasible samples. For many common end-effector constraints, parameterizations built on inverse kinematics (IK) provide an alternate formulation where the constraints are satisfied by construction, allowing directly sampling the feasible set. Despite their elegant approach, parameterized planners have remained slower than vector-accelerated implementations of projection-based approaches, leaving their performance ceiling an open question. We explore a new axis of vectorization built upon reparameterizing the planning space through analytic IK. This approach addresses existing inefficiencies in vectorized projection-based planners and exposes new opportunities for parallelism within the planner. We show that the planner can synthesize plans in microseconds to milliseconds for high dimensional systems (up to 20 dimensions), with complex constraints, up to 10x faster than the current state-of-the-art. Furthermore, we demonstrate how such planning speeds open up avenues for restructuring sequential manipulation pipelines.

0.19

Navigate or Relocate? Planning Among Movable Obstacles in Unknown Environments

cs.RO ·2026-09-17 ·Yuqing Zhang, Haoyu Zhu, Yiannis Kantaros
similarity 0.67
Abstract

Conventional robot planning methods seek collision-free paths to a goal but fail when all paths are blocked. In these cases, the robot must determine which objects to relocate, in what order, and where to place them to clear a path---a problem known as Navigation Among Movable Obstacles (NAMO). Most NAMO planners assume a known environment, while existing approaches for unknown environments typically reason locally about relocations and cannot plan interdependent relocation sequences. We consider NAMO in unknown environments revealed through onboard sensing, where the robot must decide whether a blocked route requires relocation or a feasible path may exist through unexplored space. We propose an online framework that addresses this ambiguity by selecting between navigation and relocation using shortest paths that treat discovered movable objects as obstacles or as removable. Navigation relies on existing motion planners, while relocation uses a sampling-based approach that, unlike existing approaches for unknown environments, searches over \textit{interdependent} relocation sequences and uses an LLM to bias sampling. Numerical experiments demonstrate scalability to cluttered environments requiring interdependent relocations and improved plan quality over existing baselines.

0.26

geodex: A Library for Motion Planning on Riemannian Manifolds

cs.RO ·2026-10-06 ·Phone Thiha Kyaw, Ben Wei, Sepehr Samavi, Miguel Angel Rogel Garcia, Jonathan Kelly
benchmarkcode/data similarity 0.67
Abstract · 8 pages, 7 figures, 4 tables. Code, documentation, and tutorials at https://geodex.readthedocs.io

Planning motions that respect the intrinsic geometry of a robot's configuration space, including its curvature and a configuration-dependent notion of cost, yields shorter, lower-energy, and more natural trajectories than planning under the ambient flat metric. Existing libraries for optimization on manifolds provide rich geometric primitives but do not plan around obstacles. While general-purpose motion planning libraries support many state spaces and custom distance functions, they do not yet treat a configuration-dependent Riemannian metric as the geometry that drives distance, interpolation, and geodesics. We present geodex, an open-source C++20 library with Python bindings. The library exposes the manifold, its Riemannian metric, the retraction, and the sampler as independent, interchangeable components through a single sampling-based motion planning interface. The same planner runs unchanged on canonical spaces $\mathbb{R}^n$, $\mathbb{T}^n$, $\mathbb{S}^n$, matrix Lie groups such as $SO(2)$, $SE(2)$, $SO(3)$, and $SE(3)$, products of these spaces, and articulated-robot configuration spaces, each equipped with a user-defined Riemannian metric. We make geodex publicly available with documentation, tests, and a reproducible benchmark suite.

0.37

Foundation-Model-Guided Topology-Aware Semantic Risk Fields for Manipulation

cs.RO ·2026-09-29 ·Giung Lee, Weihang Guo, Lydia E. Kavraki
similarity 0.66
Abstract

Robot motion planning in everyday environments must satisfy hard geometric constraints while accounting for context-dependent semantic risk. We present a foundation-model-guided, topology-aware semantic risk field that extends manipulation safety beyond collision avoidance. For each manipulated-object/scene-object pair, a foundation model provides six directional risk weights and a pair-specific spatial decay scale. The method combines these priors with voxelized 3D scene geometry using topology-aware shielding and geodesic spatial decay. A GPU-parallel backend batches object-level distance and risk computations to construct a dense 3D field that serves as a modular cost for downstream motion planning. We evaluate the field's shielding behavior under full and partial barriers and compare its 3D workspace representation with a pixel-wise semantic-prior baseline. Across three household simulation scenarios, trajectories optimized with the proposed field have lower semantic exposure than collision-only trajectories under the same geometric constraints. We also evaluate the computational practicality and reliability of the supporting pipeline. Together, these results support the proposed field as a practical topology-aware semantic cost representation for manipulation planning beyond collision avoidance.

0.18

Funnel planning and control for manipulators using neural Signed Configuration Distance Functions

cs.RO ·2026-10-10 ·Bernhard Wullt, Christos K. Verginis, Per Mattsson, Mikael Norrlöf, Thomas B. Schön
similarity 0.66
Abstract

Robust motion planning and control for manipulators is the problem of guaranteeing safe execution and collision-free motion under disturbances. The Kinodynamic Motion Planning via Funnel Control (KDF) is a recently proposed planner that comes with robustness guarantees and is particularly attractive for collision-free control as it guarantees closed-loop evolution inside a funnel, i.e., a collision-free region around a nominal trajectory. Despite its attractive theoretical properties, the current approach for computing funnels is computationally demanding, which limits its expressiveness and performance. We address its current limitations by proposing a novel funnel planning and control solution. Our key tool to enable this is a neural Signed Configuration Distance Function (nSCDF) which allows us to estimate collision-free balls and gradients in a computationally efficient way. We use the nSCDF in our planner to compute a nominal trajectory, where path length and clearance are balanced. To track the trajectory with collision-avoidance guarantees, we design a funnel controller that exploits the geometric information from the nSCDF. From numerical experiments, we observe that our planner produces nominal paths $2$ times faster, while at the same time obtaining $20 \%$ shorter path length and $5$ times the clearance. Finally, we also observe improved motion performance and robustness properties when using the nSCDF for funnel control.

0.20

PATACON: GPU-Parallel Tangent-Bundle RRT-Connect for Constrained Motion Planning

cs.RO ·2026-10-09 ·Gahyun Oh, Junho An, Suhyun Jeon, Suhan Park
similarity 0.66
Abstract · 8 pages, 6 figures, 2 tables

Fast whole-body motion planning enables continuous replanning for humanoid robots in dynamic environments while satisfying collision avoidance and kinematic constraints. However, constrained motion planning incurs substantial computational cost due to repeated constraint projection in addition to collision checking and nearest-neighbor search. Recently, GPU-based massively parallel planners have been proposed to reduce computational cost. Nevertheless, these planners still steer in the ambient configuration space, so projecting candidates that deviate from the manifold remains a significant source of overhead, particularly in highly constrained, high-dimensional problems. In this work, we introduce PATACON, a GPU-parallel bidirectional planner that explores tangent space to exploit the local manifold geometry induced by known constraint functions. Experiments on dual-arm closed-chain and humanoid whole-body constrained planning tasks show that PATACON outperforms the prior work as configuration-space dimension and constraint codimension grow, achieving up to an 11.25 times speedup. These results suggest that GPU-parallel tangent-space exploration brings constrained whole-body motion planning closer to real-time performance.

0.28

Motion planning in high dimensional spaces hybridizing RRT and HAR via position-direction decoupling

cs.RO ·2026-09-15 ·Frederic Cazals, Nelson Feyeux
similarity 0.65
Abstract · 22 pages, 8 figures

The exploration of high-dimensional spaces remains a challenging problem, in particular in the presence of narrow passages and small clearances. We propose novel sampling-based path-planning methods for high-dimensional spaces combining Rapidly-exploring Random Trees (RRT) and Hit-and-Run (HAR) random walks by decoupling the point being extended from the direction of extension. We also show that RRT and HAR appear as special cases of a generic algorithm coupling the biases used for the point and direction extension, respectively. We further study a sparse-move strategy in which only a fraction p_r of the robots is moved at each step, helping both RRT and the proposed HAR algorithms handle cluttered instances. Tests are presented for two families of models: classical piano mover problems in 3D, and complex molecular systems involving tens of rigid domains moving relatively to one another -- the latter viewed as independent robots exploring the motion space SE(3)N . Within seconds on a standard laptop, our algorithms solve instances with up to 64 robots and 384 degrees of freedom. We conclude by suggesting one of our methods, HARF, as the method of choice for complex multi-robot planning problems, being up to two orders of magnitude faster than the classical RRT moving all robots at each step--when it succeeds at all, and still up to 2.4 fold faster on most instances when both use their best p_r.

0.33

AirSplan: Risk-Aware Motion Planning for Quadrotors in Cluttered 3D Gaussian Splats

cs.RO ·2026-09-18 ·Seth Isaacson, William Hong, Katherine A. Skinner, Ram Vasudevan
publishedcode/data similarity 0.65
Abstract · To appear in the proceedings of IROS 2026

Quadrotors are increasingly deployed in applications such as agriculture, infrastructure inspection, and maintenance. In each of these applications, the robot must navigate complex scene geometry while remaining strictly collision-free. Unlike in ground domains, even minor collisions for aerial vehicles can result in the loss of the robot. This safety requirement induces a pair of technical challenges. First, the environment must be represented with sufficient fidelity to encode complex structure, even when no ground-truth obstacle data is available. Second, a motion planner must leverage this representation to determine a collision-free path to the goal. This paper proposes a system that addresses these complementary challenges. The proposed method, AirSplan, adopts a normalized variant of 3D Gaussian Splatting that encodes high-fidelity scene geometry. It then applies a novel reachability-based motion planner that leverages the differential flatness of quadrotors to compute continuous-time collision constraints that tightly overapproximate the robot's occupancy. Experiments demonstrate that AirSplan successfully finds a path in 81.2% of challenging test cases, a significant improvement over the nearest baseline method's 51.2%.

0.54