Trajectory Planning Using Safe Ellipsoidal Corridors As Projections of Orthogonal Trust Regions
Akshay Jaitly, Jon Arrizabalaga, Guanrui Li
AI summary
Problem
Existing corridor-based planners scale poorly with environmental complexity and require explicit time allocation across discrete convex segments, causing sensitivity and inefficiency in complex navigation tasks.
Approach
The authors parameterize trajectories in nonconvex safe corridors as projections of a convex Cartesian product of high-dimensional balls, formulating the optimization as an Orthogonal Trust Region Problem solvable via a parallelizable block coordinate descent algorithm.
Key results
- Convex representation of nonconvex trajectory sets using a product of high-dimensional balls
- Orthogonal Trust Region Problem (Orth-TRP) formulation with separable block constraints
- Parallelizable solver exploiting trust-region structure for efficient QCQP optimization
- Demonstrated lower runtimes and smoother trajectories than state-of-the-art corridor planners on quadrotor benchmarks
Why it matters
Enables real-time, scalable collision-free navigation for robots in highly complex environments by eliminating the scaling bottlenecks and time-allocation issues of traditional corridor-based methods.
Abstract
Planning collision free trajectories in complex environments remains a core challenge in robotics. Exist- ing corridor based planners which rely on decomposition of the free space into collision free subsets scale poorly with environmental complexity and require explicit allocations of time windows to trajectory segments. We introduce a new trajectory parameterization that represents trajectories in a nonconvex collision free corridor as being in a convex cartesian product of balls. This parameterization allows us to decouple problem size from geometric complexity of the solution and naturally avoids explicit time allocation by allowing trajectories to evolve continuously inside ellipsoidal corridors. Building on this representation, we formulate the Orthogonal Trust Region Problem (Orth-TRP), a specialized convex program with separable block constraints, and develop a solver that exploits this parallel structure and the unique structure of each parallel subproblem for efficient optimization. Experiments on a quadrotor trajectory planning benchmark show that our approach produces smoother trajectories and lower runtimes than state-of-the-art corridor based planners, especially in highly complicated environments.