Planning with 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. Cur-rent planners for TEGs prune the search space during plan-ning via goal progression. However, the fastest classical domain-independent planners rely on heuristic search. In this paper we propose a method for planning with propositional TEGs using heuristic search. To this end, we translate an in-stance of a planning problem with TEGs into an equivalent classical planning problem. With this translation in hand, we exploit heuristic search to determine a plan. We represent TEGs using propositional linear temporal logic which is in-terpreted over finite sequences of states. Our translation is based on the construction of a nondeterministic finite automa-ton for the TEG. We prove the correctness of our algorithm and analyze the complexity of the resulting representation. The translator is fully implemented and available. Our ap-proach consistently outperforms existing approaches to plan-ning with TEGs, often by orders of magnitute. 1