Formalizing plan justifications

This paper formalizes the notion of justified plans, which captures the intuition behind “good ” plans. A justified plan is one that does not contain operators which are not necessary for achieving a goal. The importance of formalizing this notion is due to two reasons. First, it gives rise to methods for optimizing a given plan by removing “useless ” operators. Second, several important concepts describing abstraction hierarchies are defined via justified plans. In the past, relatively few attempts have been made to formalize such a notion. This paper defines several different kinds of plan justifications, presents algorithms for finding a justified version of a plan, and shows that the task of finding the best possible justified version of a plan is NP-complete. Finally, it presents a greedy algorithm for finding a near-optimal justified plan in polynomial time.