条件付き時間付き部分順序：ロボットタスク仕様と計画のための表現力豊かで解釈可能なフレームワーク
Conditional Timed Partial Orders: An Expressive and Interpretable Framework for Robot Task Specification and Planning
時間付き部分順序（TPO）を拡張し、環境条件に基づく条件付きイベント活性化とより豊かな相対時間制約を導入した条件付きTPO（cTPO）を提案し、計画問題をMILPに帰着させるとともに、分解アルゴリズムにより計算効率を大幅に向上させた。
著者: Sebastian Escobar, Morteza Lahijanian
分類: cs.RO, cs.FL
原文アブストラクト
Timed Partial Orders (TPOs), originally proposed for workflows, provide an interpretable framework for robot task specification with planning algorithms based on mixed-integer linear programming (MILP). However, TPOs are limited in expressivity, capturing only partial-order events with simple timing constraints. In this paper, we introduce Conditional TPOs (cTPOs), which extend TPOs with richer relative-timing constraints and conditional event activations based on environmental conditions. We show that planning for cTPOs also reduces to an MILP problem; however, the added expressivity results in significantly larger MILPs that can become computationally intractable. To address this challenge, we propose a decomposition algorithm that partitions a cTPO into smaller sub-TPOs, yielding a sequence of smaller MILP problems. We prove that this decomposition is complete and preserves plan optimality while improving the interpretability of complex tasks. Experimental results demonstrate the effectiveness of cTPOs as a task specification framework and the efficiency of our decomposition approach, achieving up to four orders of magnitude speedup over the monolithic MILP.