用凸集图的最短路径统一求解机器人混合离散连续规划问题。
Mixed Discrete and Continuous Planning using Shortest Walks in Graphs of Convex Sets
- 构建凸集图模型，将离散与连续决策融合为统一优化框架。
- 通过半定规划生成分段二次下界，指导增量搜索得近似最优路径。
- 在避障规划、技能串联和混合系统控制中验证高效性与通用性。
我们研究图中凸集（GCS）的最短路径问题（SWP）。GCS 是一种图结构，其中每个顶点关联一个凸规划问题，每条边通过额外代价和约束耦合相邻规划。图中的一条路径是顶点序列，顶点可重复，路径长度为对应凸规划最优值之和。为求解 GCS 中的 SWP，我们首先利用半定规划合成问题代价到目标函数的分段二次下界；随后以此下界引导增量搜索算法，获得近似最短路径。我们证明，GCS 中的 SWP 可自然表达机器人领域众多混合离散-连续规划问题，统一了原本需专用方法处理的任务，并实现高性能与高计算效率。实验验证了其在无碰撞运动规划、技能链组合及混合系统最优控制中的有效性。
原文摘要 · Abstract (English)
We study the Shortest-Walk Problem (SWP) in a Graph of Convex Sets (GCS). A GCS is a graph where each vertex is paired with a convex program, and each edge couples adjacent programs via additional costs and constraints. A walk in a GCS is a sequence of vertices connected by edges, where vertices may be repeated. The length of a walk is given by the cumulative optimal value of the corresponding convex programs. To solve the SWP in GCS, we first synthesize a piecewise-quadratic lower bound on the problem's cost-to-go function using semidefinite programming. Then we use this lower bound to guide an incremental-search algorithm that yields an approximate shortest walk. We show that the SWP in GCS is a natural language for many mixed discrete-continuous planning problems in robotics, unifying problems that typically require specialized solutions while delivering high performance and computational efficiency. We demonstrate this through experiments in collision-free motion planning, skill chaining, and optimal control of hybrid systems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。