LTL-D*: 線形時相論理仕様における実行可能・不可能タスクのための漸進的最適再計画
LTL-D*: Incrementally Optimal Replanning for Feasible and Infeasible Tasks in Linear Temporal Logic Specifications
動的に変化する環境で線形時相論理(LTL)仕様を満たすタスク計画のため、D* Liteとオートマトン上の距離指標を用いて、仕様違反を最小化する最適な再計画を漸進的に行うアルゴリズムを提案した。
著者: Jiming Ren, Haris Miller, Karen M. Feigh, Samuel Coogan, Ye Zhao
分類: cs.RO, cs.FL
原文アブストラクト
This paper presents an incremental replanning algorithm, dubbed LTL-D*, for temporal-logic-based task planning in a dynamically changing environment. Unexpected changes in the environment may lead to failures in satisfying a task specification in the form of a Linear Temporal Logic (LTL). In this study, the considered failures are categorized into two classes: (i) the desired LTL specification can be satisfied via replanning, and (ii) the desired LTL specification is infeasible to meet strictly and can only be satisfied in a "relaxed" fashion. To address these failures, the proposed algorithm finds an optimal replanning solution that minimally violates desired task specifications. In particular, our approach leverages the D* Lite algorithm and employs a distance metric within the synthesized automaton to quantify the degree of the task violation and then replan incrementally. This ensures plan optimality and reduces planning time, especially when frequent replanning is required. Our approach is implemented in a robot navigation simulation to demonstrate a significant improvement in the computational efficiency for replanning by two orders of magnitude.
