A Heuristic Search Approach to Planning with Temporally Extended Preferences

Jorge A. Baier, Fahiem Bacchus, Sheila McIlraith

In this paper we propose a suite of techniques for planning with temporally extended preferences (TEPs). To this end, we propose a method for compiling TEP planning problems into simpler domains containing only final-state (simple) preferences and metric functions. With this simplified problem in hand, we propose a variety of heuristic functions for planning with final-state preferences, together with an incremental best-first planning algorithm. A key feature of the planning algorithm is its ability to prune the search space. We identify conditions under which our planning algorithm will generate optimal plans. We implemented our algorithm as an extension to the \tlplan ~planning system and report on extensive testing performed to evaluate the effectiveness of our heuristics and algorithm. Our planner, \hplanp{}, competed in the 5th International Planning Competition, achieving distinguished performance in the \emph{qualitative preferences} track.