時間付き半順序仕様に対する最適計画
Optimal Planning for Timed Partial Order Specifications
複数ロボットのタスク列を時間窓と優先順序制約の下で最短完了時間となるよう計画する問題を、時間付き半順序(TPO)で定式化し、混合整数線形計画(MILP)として解く枠組みを提案した。
著者: Kandai Watanabe, Georgios Fainekos, Bardh Hoxha, Morteza Lahijanian, Hideki Okamoto, Sriram Sankaranarayanan
分類: cs.RO, cs.LO
原文アブストラクト
This paper addresses the challenge of planning a sequence of tasks to be performed by multiple robots while minimizing the overall completion time subject to timing and precedence constraints. Our approach uses the Timed Partial Orders (TPO) model to specify these constraints. We translate this problem into a Traveling Salesman Problem (TSP) variant with timing and precedent constraints, and we solve it as a Mixed Integer Linear Programming (MILP) problem. Our contributions include a general planning framework for TPO specifications, a MILP formulation accommodating time windows and precedent constraints, its extension to multi-robot scenarios, and a method to quantify plan robustness. We demonstrate our framework on several case studies, including an aircraft turnaround task involving three Jackal robots, highlighting the approach's potential applicability to important real-world problems. Our benchmark results show that our MILP method outperforms state-of-the-art open-source TSP solvers OR-Tools.
