Optimization-based Task and Motion Planning under Signal Temporal Logic Specifications using Logic Network Flow

📄 arXiv: 2409.19168v3 📥 PDF

作者: Xuan Lin, Jiming Ren, Samuel Coogan, Ye Zhao

分类: cs.RO, cs.FL

发布日期: 2024-09-27 (更新: 2025-09-30)

备注: Accepted to IEEE International Conference on Robotics and Automation (ICRA) 2025

💡 一句话要点

提出基于逻辑网络流的优化框架，解决信号时序逻辑约束下的任务与运动规划问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 任务与运动规划 信号时序逻辑 混合整数线性规划 逻辑网络流 多机器人系统

📋 核心要点

  1. 现有方法在处理信号时序逻辑约束下的任务与运动规划时，通常采用逻辑树结构，凸松弛不够紧凑，计算效率较低。
  2. 论文提出逻辑网络流框架，将时间谓词编码为网络流边上的约束，结合动态网络流，实现更紧凑的凸松弛。
  3. 实验表明，该方法在多机器人运动规划中，相比逻辑树方法，在计算时间和问题规模扩展性方面均有提升。

📝 摘要（中文）

本文提出了一种基于优化的任务与运动规划框架，名为“逻辑网络流”（Logic Network Flow），旨在将信号时序逻辑（STL）规范集成到高效的混合整数线性规划中。在该框架中，时间谓词被编码为网络流每条边上的多面体约束，而不是像传统逻辑树公式那样作为节点之间的约束。通过与动态网络流相结合，逻辑网络流相比于从这些STL规范导出的逻辑树，能够实现更紧凑的凸松弛。我们的公式在多个多机器人运动规划案例研究中进行了评估。实验结果表明，在几个规划问题中，我们的公式在计算时间方面优于逻辑树公式。随着问题规模的扩大，我们的方法仍然可以通过在分支定界过程中探索更少的节点来发现更好的下界和上界，尽管这会增加探索分支时每个节点的计算负担。

🔬 方法详解

问题定义：论文旨在解决在信号时序逻辑（STL）约束下，多智能体或机器人的任务与运动规划问题。现有方法，特别是基于逻辑树的公式，在将STL规范转化为混合整数线性规划（MILP）时，会产生较为松弛的凸近似，导致求解效率不高，尤其是在问题规模增大时。这些方法通常将时间谓词作为节点间的约束，限制了其表达能力和优化空间。

核心思路：论文的核心思路是将STL规范中的时间谓词编码为网络流的每条边上的多面体约束，而不是节点之间的约束。这种方式能够更精细地表达时间约束，并与动态网络流相结合，从而实现更紧凑的凸松弛。通过这种更紧凑的表示，可以更有效地利用MILP求解器，减少分支定界的搜索空间，提高求解效率。

技术框架：整体框架包括以下几个主要步骤：1) 将STL规范转化为逻辑网络流图；2) 将逻辑网络流图转化为混合整数线性规划（MILP）问题；3) 使用MILP求解器求解该优化问题，得到满足STL规范的任务与运动规划方案。其中，逻辑网络流图的构建是关键，它将时间谓词与网络流的边相关联，并利用动态网络流来保证逻辑一致性。

关键创新：最重要的技术创新点在于将时间谓词编码为网络流的边约束，并结合动态网络流。与传统的逻辑树方法相比，这种方法能够实现更紧凑的凸松弛，从而提高MILP求解器的效率。本质区别在于约束的表达方式，逻辑网络流利用边的信息，而逻辑树主要依赖节点信息。

关键设计：关键设计包括：1) 如何将不同的STL操作符（如always, eventually, until）转化为网络流的边约束；2) 如何设计动态网络流，以保证逻辑一致性，例如，确保如果一个谓词在某个时间点为真，那么相应的流必须通过该边；3) 如何选择合适的MILP求解器，并调整其参数，以获得最佳性能。论文中可能还涉及一些启发式方法，用于加速分支定界过程。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，在多机器人运动规划问题中，逻辑网络流方法在计算时间上优于传统的逻辑树方法。具体而言，在某些案例中，计算时间缩短了XX%。此外，随着问题规模的扩大，逻辑网络流方法能够通过探索更少的节点来发现更好的下界和上界，表明其具有更好的可扩展性。虽然每个节点的计算负担有所增加，但总体性能仍然优于逻辑树方法。

🎯 应用场景

该研究成果可应用于多机器人协同任务、自动驾驶车辆路径规划、智能制造生产调度等领域。通过将复杂的任务目标转化为可执行的运动轨迹，并保证满足时序逻辑约束，可以提高系统的自主性和可靠性，降低人工干预的需求，具有重要的实际应用价值和广阔的应用前景。

📄 摘要（原文）

This paper proposes an optimization-based task and motion planning framework, named "Logic Network Flow", to integrate signal temporal logic (STL) specifications into efficient mixed-binary linear programmings. In this framework, temporal predicates are encoded as polyhedron constraints on each edge of the network flow, instead of as constraints between the nodes as in the traditional Logic Tree formulation. Synthesized with Dynamic Network Flows, Logic Network Flows render a tighter convex relaxation compared to Logic Trees derived from these STL specifications. Our formulation is evaluated on several multi-robot motion planning case studies. Empirical results demonstrate that our formulation outperforms Logic Tree formulation in terms of computation time for several planning problems. As the problem size scales up, our method still discovers better lower and upper bounds by exploring fewer number of nodes during the branch-and-bound process, although this comes at the cost of increased computational load for each node when exploring branches.