Towards Optimizing a Convex Cover of Collision-Free Space for Trajectory Generation
Yuwei Wu, Igor Spasojevic, Pratik Chaudhari, Vijay Kumar
AI summary
Problem
Existing Safe Flight Corridor generation methods use greedy, decoupled approaches that ignore downstream trajectory costs, often producing suboptimal paths in cluttered environments.
Approach
The authors propose an iterative algorithm that simultaneously optimizes overlapping polytopes and trajectory waypoints by maximizing inscribed ellipsoid volumes while minimizing a heuristic trajectory cost function.
Key results
- Formulates SFC generation as a joint optimization problem coupled with trajectory planning
- Develops a novel heuristic-based iterative solver with partially distributed variables for computational efficiency
- Demonstrates robust performance across diverse synthetic environments and benchmarks against existing methods
- Provides the first comprehensive analysis linking front-end path geometry and SFC properties to downstream trajectory cost
Why it matters
Enables more efficient and reliable autonomous navigation for quadrotors and mobile robots by ensuring the collision-free corridor directly supports optimal trajectory generation.
Abstract
We propose an online iterative algorithm to opti- mize a convex cover to under-approximate the free space for autonomous navigation to delineate Safe Flight Corridors (SFC). The convex cover consists of a set of polytopes such that the union of the polytopes represents obstacle-free space, allowing us to find trajectories for robots that lie within the convex cover. In order to find the SFC that facilitates trajectory optimization, we iteratively find overlapping polytopes of maximum volumes that include specified waypoints initialized by a geometric or kinematic plan- ner. Constraints at waypoints appear in two alternating stages of a joint optimization problem, which is solved by a novel heuristic- based iterative algorithm with partially distributed variables. We validate the effectiveness of our proposed algorithm using a range of parameterized environments and show its applications for two- stage motion planning.