Beyond Pairwise Costs: Hyper Graph of Convex Sets for Smoothness-Aware Trajectory Planning

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 refinement. 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 provides better initialization for downstream optimization, achieves shorter trajectory duration than hierarchical GCS baselines, and is faster than joint spatio-temporal optimization.