Planning with First-Order Temporally Extended Goals Using Heuristic Search

Abstract

Temporally extended goals (TEGs) refer to properties that must hold over intermediate and/or final states of a plan. The problem of planning with TEGs is of renewed interest because it is at the core of planning with temporal prefer-ences. Currently, the fastest domain-independent classical planners employ some kind of heuristic search. However, ex-isting planners for TEGs are not heuristic and are only able to prune the search space by progressing the TEG. In this paper we propose a method for planning with TEGs using heuris-tic search. We represent TEGs using a rich and compelling subset of a first-order linear temporal logic. We translate a planning problem with TEGs to a classical planning prob-lem. With this translation in hand, we exploit heuristic search to determine a plan. Our translation relies on the construc-tion of a parameterized nondeterministic finite automaton for the TEG. We have proven the correctness of our algorithm and analyzed the complexity of the resulting representation. The translator is fully implemented and available. Our ap-proach consistently outperforms TLPLAN on standard bench-mark domains, often by orders of magnitude. 1