信号時相論理仕様下でのロジックネットワークフローを用いた最適化ベースのタスク・動作計画
Optimization-based Task and Motion Planning under Signal Temporal Logic Specifications using Logic Network Flow
信号時相論理(STL)仕様を混合整数線形計画に統合するため、時間述語をネットワークフローの辺上の多面体制約として符号化する「ロジックネットワークフロー」を提案し、マルチロボット動作計画で従来のロジックツリーより計算時間を短縮できることを示した。
著者: Xuan Lin, Jiming Ren, Samuel Coogan, Ye Zhao
分類: cs.RO, cs.FL
原文アブストラクト
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.
