Plan Optimal Collision-Free Trajectories with Non-Convex Cost Functions Using Graphs of Convex Sets
Landon Clark, Biyun Xie
AI summary
Problem
Existing Graphs of Convex Sets (GCS) planners efficiently compute shortest-distance paths but cannot handle arbitrary nonconvex cost functions, limiting their use in complex robotic applications.
Approach
The method approximates nonconvex cost functions using multi-layer ReLU neural networks to partition the configuration space into linear-cost regions, then applies McCormick relaxation to convexify edge costs within a GCS graph structure.
Key results
- Novel GCSGC algorithm for nonconvex cost optimization
- McCormick relaxation to convexify nonconvex edge costs
- Graph preprocessing to remove cycles and high-cost paths
- Competitive efficiency and optimality in 2-D and 7-D validation
Why it matters
Provides a computationally efficient, globally optimal motion planning framework for robots and autonomous systems without relying on sampling heuristics or offline training.
Abstract
The recently developed approach to motion planning in graphs of convex sets (GCS) provides an efficient framework for computing shortest-distance collision-free paths using convex optimization. This new motion planner is notably more computa- tionallyefficientthanpopularsampling-basedmotionplanners,but it does not support nonconvex cost functions. This article develops a novel motion planning algorithm, graph of convex sets with general costs (GCSGC), to solve this problem. A given nonconvex cost function is accurately approximated by a multiple-layer ReLU neural network and the configuration space is decomposed into a set of linear-cost regions using the hidden layers of the neural network. These linear-cost regions are intersected with a set of collision-free regions, and the resulting collision-free linear-cost regions are intersected to form the vertices and edges of the mo- tion planner’s underlying graph structure. The edge costs have a closed-form solution within each collision-free linear-cost region, but it is nonconvex, so the McCormick relaxation is applied to convexify the edge costs. Finally, a graph preprocessing technique is developed to compute a representative graph structure that acts as a heuristic for the edge costs of the underlying GCS and then simplify the underlying graph structure by removing cycles and high-cost paths, which can significantly improve the efficiency of the planner and quality of the produced trajectories. The proposed motion planner is first validated in a 2-D configuration space with comparisons between different sized neural networks with and without preprocessing, comparisons between optimal trajectories from GCSGC with shortest-distance trajectories, and comparisons between GCSGC and GCS-Sequential linear programming (SLP). The GCSGC planner is further validated in a complex 7-D config- uration space by comparing to state-of-the-art multiquery (PRM*, GCS-SLP) and single-query (TrajOpt, BIT*, AIT*, RRT*) plan- ners. The results show that the proposed motion planner is very competitive in terms of computational efficiency, trajectory cost, and memory footprint. Two physical experiments further validate the effectiveness of the proposed motion planner in real-world motion planning applications.