Beyond Pairwise Costs: Hyper Graph of Convex Sets for Smoothness-Aware Trajectory Planning
Yunyi Zhang, Meng Guo, Zhongkui Li
AI summary
Problem
Classical graph of convex sets relies on pairwise costs that ignore higher-order geometric interactions, often producing poor initializations for downstream trajectory refinement in cluttered spaces.
Approach
The method extends GCS with hyperedges over consecutive regions to encode triplet-based smoothness costs, then converts the hypergraph into an equivalent classical GCS solvable with existing mixed-integer convex programming tools.
Key results
- Generalization of GCS to a hypergraph-structured HGCS for higher-order costs
- Equivalence-preserving transformation enabling standard GCS solver compatibility
- 3-uniform smoothness-aware framework that improves initialization quality for trajectory optimization
- Experimental validation showing shorter durations and faster computation than hierarchical and joint baselines
Why it matters
Provides a scalable, smoothness-aware planning pipeline that bridges discrete route selection and continuous optimization for robotics and autonomous navigation.
Abstract
Classical graph of convex sets (GCS) formulations rely on pairwise edge costs, which are insufficient to capture higher-order geometric interactions relevant to trajectory re- finement. This paper proposes a hyper graph of convex sets (HGCS), which extends GCS by introducing hyperedges over multiple vertices. Using a 3-uniform construction, a second- order smoothness cost is incorporated to favor path sequences that are more suitable for dynamically feasible trajectory generation. To preserve tractability, the HGCS is converted into an equivalent classical GCS, so the resulting shortest-path problem can still be solved with existing GCS methods. The discrete path is then refined by trajectory optimization within the corresponding safe corridor. Numerical simulations and quadrotor experiments show that the proposed method pro- vides better initialization for downstream optimization, achieves shorter trajectory duration than hierarchical GCS baselines, and is faster than joint spatio-temporal optimization.