用网络流方法优化机器人任务规划，速度提升数个数量级。
Towards Tighter Convex Relaxation of Mixed-Integer Programs: Leveraging Logic Network Flow for Task and Motion Planning
- 将时序逻辑转为网络流边上的多面体约束，替代传统树结构。
- 提出新消元法，在去除非连续变量时保持松弛紧致性。
- 在多机器人、车辆路径等场景中实现实时重规划，适合动态环境。
本文提出一种基于优化的任务与运动规划框架「Logic Network Flow」，将时序逻辑规范融入混合整数规划以实现高效机器人规划。受图-凸集（Graph-of-Convex-Sets）启发，时序谓词被编码为网络流模型每条边上的多面体约束，而非传统逻辑树中节点间的约束。进一步提出基于网络流的Fourier-Motzkin消元方法，在消除连续流量变量的同时保持凸松弛紧致性，从而获得比逻辑树方法更紧的凸松弛且约束更少。针对具有分段仿射动力学系统的时序逻辑运动规划，通过车辆路径、多机器人协同及点质量与线性倒立摆模型上的综合实验，验证了计算速度提升达数个数量级，并显著降低内存消耗。四足机器人硬件演示验证了在动态环境变化下实现实时重规划的能力。项目主页：https://logicnetworkflow.github.io/。
原文摘要 · Abstract (English)
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 polyhedral 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 dynamical 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, alongside reduced memory consumption. Hardware demonstrations with quadrupedal robots validate real-time replanning capabilities under dynamically changing environmental conditions. The project website is at https://logicnetworkflow.github.io/.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。