Feedback motion planning over cell decompositions provides a robust method for generating collision-free robot motion with formal guarantees. However, existing algorithms often produce paths with unnecessary bending, leading to slower motion and higher control effort. This paper presents a computationally efficient method to mitigate this issue for a given simplicial decomposition. A heuristic is introduced that systematically aligns and assigns local vector fields to produce more direct trajectories, complemented by a novel geometric algorithm that constructs a maximal star-shaped chain of simplexes around the goal. This creates a large ``funnel'' in which an optimal, direct-to-goal control law can be safely applied. Simulations demonstrate that our method generates measurably more direct paths, reducing total bending by an average of 91.40% and LQR control effort by an average of 45.47%. Furthermore, comparative analysis against sampling-based and optimization-based planners confirms the time efficacy and robustness of our approach. While the proposed algorithms work over any finite-dimensional simplicial complex embedded in the collision-free subset of the configuration space, the practical application focuses on low-dimensional (d≤3) configuration spaces, where simplicial decomposition is computationally tractable.
Figures & tables
Fig. 1 : Geometric construction of valid vector fields for 2-simplex (triangle). The conical region, constructed by boundary vectors bi,j , illustrates the set of valid constant cell vector fields Vc,i that satisfy the conditions of Definition 2 . The diagram visualizes the geometric constraints for face vector fields (Definition 3 ), showing the face inward normal nin,f , the exit face outward normal nx , and the hyperplane normal nbf . The dashed lines are the GVD surface.
Fig. 2 : Geometric test for expanding the star-shaped region R with an adjacent simplex ΔT (in 2D). (Left) A valid addition where the new vertex vnew lies within the visibility cone from xg (Criterion 1 ). (Right) An invalid addition where visibility is obstructed.
Environment
Metric
Baseline
Proposed Method
Improv. (%)
Win Rate (%)
Maze (NG=109,NP=52045)
Path Length
16.70 ± 10.85
12.14 ± 7.85
27.30
97.89
Max Curvature
23.35 ± 8.66
18.38 ± 8.40
21.30
66.59
Total Bending
602.65 ± 1664.75
94.44 ± 76.88
84.33
97.50
Total Turning
47.28 ± 65.04
12.21 ± 9.03
74.18
99.73
LQR Travel Time
16.70 ± 10.85
12.14 ± 7.85
27.30
97.29
LQR Control Effort
19.59 ± 13.12
8.00 ± 4.96
59.16
98.55
TABLE I : Quantitative Comparison of Methods. NG : Number of Goal Cells tested, NP : Total Integral Curves evaluated.
Fig. 3 : Qualitative comparison of integral curves for the baseline and proposed methods across three environments. The maximal star-shaped region is highlighted in brown. Notably, in the Bug Trap environment, Steiner points were introduced to generate closer to equilateral triangles and avoid skewed triangles.
Environment
Method
Continuity
Success Rate (%)
Total Time (s)
Path Length (m)
Sparse (Boston)
APF
C0
0.0
N/A
N/A
A*
C0
100.0
0.042±0.018
9.823±1.797
RRT*
C0
100.0
0.826±0.696
12.491±2.314
FPP
Ck
100.0
3.718±0.939
9.547 ± 1.684
Proposed
C∞
100.0
0.087 ± 0.003
10.280±2.219
Maze
APF
C0
0.0
N/A
N/A
TABLE II : Quantitative comparison of different algorithms in two different environments. Results report the mean ± standard deviation.
Fig. 4 : Qualitative comparison of paths for the baselines across the maze and sparse environments.
Fast motion planning requires both sample-efficient exploration and computationally efficient local steering. Conventional straight-line steering is inexpensive but wastes samples by rejecting colliding extensions. Quadratic program controllers with control barrier function (CBF) constraints can be used to achieve effective local steering but can increase the planning time due to the expensive sequential evaluations. We develop a method to accelerate CBF steering by computing a time horizon within which CBF-filtered velocity may be applied constantly using closed-form kinematic bounds on collision-clearance. Our method, FLASH-CBF-RRT, significantly reduces the number of evaluations compared to prior CBF-RRT approaches because the planner can take adaptive steering step sizes that are shorter near obstacles and longer in open space. We implement this steering procedure as an extension of RRT-Connect in OMPL. Across 689 MotionBenchMaker problems, FLASH-CBF-RRT matches RRT-Connect's 100% success rate while reducing median planning time by 3.82x, and is 3.88x faster than fixed-step CBF-RRT. Hardware experiments on a 17-DoF mobile manipulator demonstrate 2.2x faster planning and 4.2x fewer evaluations. Videos and results are available at: https://mamani828.github.io/FLASH-CBF-RRT/.
Mani Amani, Hesam Mojtahedi, Reza Akhavian +2
Department of Civil, Construction, and Environmental Engineering, San Diego State University, San Diego, CA, USA · Department of Electrical and Computer Engineering, University of California San Diego, La Jolla, CA, USA
We study semidefinite relaxations for collision-free motion planning. We focus on a point robot moving from start to goal through spherical obstacles in Rn, subject to path continuity constraints and squared derivative costs; a setting that is conceptually simple yet captures the hardness of collision-free motion planning. We formulate this problem exactly as a nonconvex problem over polynomial curves, and present a natural semidefinite relaxation. We contribute two key theoretical insights; to our knowledge this is the first theoretical analysis of semidefinite relaxations for collision-free motion planning. First, we show that solving the convex relaxation is equivalent to solving, to global optimality, a related motion planning problem in a potentially higher-dimensional space. This geometric interpretation yields necessary and sufficient conditions for tightness, and a clear intuition for when the relaxation is loose. Second, we show that the relaxation admits a symmetry reduction that makes it significantly smaller than one might expect, with positive semidefinite cone sizes that scale linearly with the polynomial degree and are independent of the ambient dimension. The resulting relaxation is 10 to 100 times faster than direct nonlinear programming transcriptions solved with SNOPT and IPOPT, exhibits significantly lower variance in solve times, and reliably finds a locally optimal path for the original problem. We demonstrate its effectiveness as a convex steering function in an RRT planner for minimum-snap quadrotor planning with C4 continuous trajectories.
Bernhard Paus Graesdal, Alexandre Amice, Pablo A. Parrilo +1
Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA.
We propose a workspace-fibered decomposition framework for motion planning in nR planar redundant manipulators operating in cluttered environments. Rather than planning directly in the full n-dimensional configuration space, the method incrementally constructs obstacle-constrained reachable workspaces of lower-dimensional non-redundant sub-chains and recursively lifts them through redundant orientation fibers. This yields a sequence of reduced planning manifolds that preserve branch-consistent reachability structure while avoiding explicit construction of the full configuration-space obstacle geometry. We first establish that, for planar position-only manipulators, the obstacle-constrained reachable workspace induced by the minimal non-redundant sub-chain provides an exact characterization of feasibility with respect to the connected component of the start configuration, enabling early infeasibility detection prior to introducing redundant degrees of freedom (DOF). We then introduce an incremental fiber-lifting procedure that propagates reachable workspace structure through successive redundant links while enforcing local inverse-kinematic branch consistency using Jacobian determinant continuity constraints. The resulting representation admits efficient reduced-space planning directly on recursively-constructed workspace-fiber manifolds. Experimental results on redundant nR planar manipulators demonstrate that the proposed construction preserves collision-free connectivity structure across successive lifting stages while substantially reducing collision checking complexity relative to direct configuration space reasoning.
Aayush Rath, Antony Thomas
Robotics Research Center, IIIT Hyderabad, Hyderabad 500032, India.