Towards Tighter Convex Relaxation of Mixed-integer Programs: Leveraging Logic Network Flow for Task and Motion Planning
作者: Xuan Lin, Jiming Ren, Yandong Luo, Weijun Xie, Ye Zhao
分类: cs.RO, eess.SY
发布日期: 2025-09-29
备注: 35 pages, 17 figures, 7 tables
🔗 代码/项目: PROJECT_PAGE
💡 一句话要点
提出逻辑网络流框架，通过更紧的凸松弛加速任务与运动规划
🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 任务与运动规划 时序逻辑 混合整数规划 凸松弛 网络流
📋 核心要点
- 现有任务与运动规划方法在处理复杂时序逻辑约束时，通常面临计算效率瓶颈，难以满足实时性要求。
- 论文提出“逻辑网络流”框架，将时序逻辑谓词编码为网络流边上的约束，实现更紧的凸松弛。
- 实验表明，该方法在车辆路径、多机器人协调等场景中，计算速度提升显著，并在四足机器人上验证了实时重规划能力。
📝 摘要（中文）
本文提出了一种基于优化的任务与运动规划框架，名为“逻辑网络流”，它将时序逻辑规范集成到混合整数规划中，以实现高效的机器人规划。受凸集图公式的启发，时序谓词被编码为网络流模型每条边上的多面体约束，而不是像传统逻辑树公式那样作为节点之间的约束。我们进一步提出了一种基于网络流的傅里叶-莫茨金消元过程，该过程消除了连续流变量，同时保持了凸松弛的紧性，从而实现了比逻辑树公式更紧的凸松弛和更少的约束。对于具有分段仿射动态系统的时序逻辑运动规划，在车辆路径规划、多机器人协调以及使用质点和线性倒立摆模型的动态系统时序逻辑控制方面的综合实验表明，计算速度提高了几个数量级。使用四足机器人的硬件演示验证了在动态变化的环境条件下进行实时重新规划的能力。
🔬 方法详解
问题定义：论文旨在解决机器人任务与运动规划中，如何高效地处理复杂时序逻辑约束的问题。现有方法，如基于逻辑树的公式，在处理复杂时序逻辑时，会导致混合整数规划问题规模庞大，凸松弛较弱，计算效率低下，难以满足实时性要求。
核心思路：论文的核心思路是将时序逻辑谓词编码为网络流模型中每条边上的多面体约束，而不是像传统方法那样作为节点之间的约束。这种基于“逻辑网络流”的表示方法，能够实现更紧的凸松弛，从而减少搜索空间，提高求解效率。同时，论文还提出了一种基于网络流的傅里叶-莫茨金消元过程，用于消除连续流变量，进一步提升凸松弛的紧性。
技术框架：该框架主要包含以下几个阶段：1) 将任务与运动规划问题建模为混合整数规划问题，其中时序逻辑规范被编码为网络流模型中的约束。2) 利用凸集图的思想，将时序谓词表示为网络流边上的多面体约束。3) 应用基于网络流的傅里叶-莫茨金消元过程，消除连续流变量，得到更紧的凸松弛。4) 求解得到的混合整数规划问题，得到满足时序逻辑约束的任务与运动规划方案。
关键创新：论文最重要的技术创新点在于提出了“逻辑网络流”的表示方法，以及基于网络流的傅里叶-莫茨金消元过程。与传统的逻辑树方法相比，“逻辑网络流”能够实现更紧的凸松弛，减少约束数量，从而显著提高求解效率。傅里叶-莫茨金消元过程则进一步提升了凸松弛的紧性，使得求解器能够更快地找到最优解。
关键设计：论文的关键设计包括：1) 如何将不同的时序逻辑算子（如Always, Eventually, Until）转化为网络流边上的多面体约束。2) 如何设计基于网络流的傅里叶-莫茨金消元过程，以有效地消除连续流变量，同时保持凸松弛的紧性。3) 如何选择合适的混合整数规划求解器，并调整其参数，以获得最佳的求解性能。
🖼️ 关键图片
📊 实验亮点
实验结果表明，与传统的逻辑树方法相比，“逻辑网络流”框架在车辆路径规划、多机器人协调以及动态系统时序逻辑控制等任务中，计算速度提高了几个数量级。例如，在某些场景下，求解时间从数分钟缩短到几秒钟。此外，在四足机器人上的硬件演示验证了该方法在动态变化的环境中进行实时重规划的能力。
🎯 应用场景
该研究成果可广泛应用于机器人任务规划、自动驾驶、多智能体系统等领域。例如，在自动驾驶中，可以利用该方法规划车辆在复杂交通环境下的行驶路径，同时满足交通规则和安全约束。在多智能体系统中，可以用于协调多个机器人完成复杂的协作任务。该方法具有实时重规划能力，使其在动态变化的环境中具有重要的应用价值。
📄 摘要（原文）
This paper proposes an optimization-based task and motion planning framework, named "Logic Network Flow", that integrates temporal logic specifications into mixed-integer programs for efficient robot planning. Inspired by the Graph-of-Convex-Sets formulation, temporal predicates are encoded as polyhedron constraints on each edge of a network flow model, instead of as constraints between nodes in traditional Logic Tree formulations. We further propose a network-flow-based Fourier-Motzkin elimination procedure that removes continuous flow variables while preserving convex relaxation tightness, leading to provably tighter convex relaxations and fewer constraints than Logic Tree formulations. For temporal logic motion planning with piecewise-affine dynamic systems, comprehensive experiments across vehicle routing, multi-robot coordination, and temporal logic control on dynamical systems using point mass and linear inverted pendulum models demonstrate computational speedups of up to several orders of magnitude. Hardware demonstrations with quadrupedal robots validate real-time replanning capabilities under dynamically changing environmental conditions. The project website is at https://logicnetworkflow.github.io/.