On Domain-Independent Heuristics for Planning with Qualitative Preferences

Jorge A. Baier, Sheila A. McIlraith

This paper describes a method for planning with rich qualitative, temporally extended preferences (QTEPs) using lookahead heuristics inspired by those employed in state-of-the-art classical planners. Key to our approach is a transformation of the planning domain into an equivalent but simplified planning domain. First, compound preference formulae are transformed into simpler, equivalent preference formulae. Second, temporally extended preferences are replaced by equivalent, atemporal preferences. These two simplifications enable us to propose a number of simple heuristic strategies for planning with QTEPs. We propose an algorithm that uses these heuristics and that furthermore is provably k-optimal, i.e. it finds all optimal plans of length no greater than a parameter k. We compare our planner against the \pplan planner, which does not use lookahead heuristics. Preliminary results show a significant improvement in performance.

Subjects: 1.11 Planning; 3.5 Qualitative Reasoning

Submitted: Jan 28, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.