Covering Landmark Interactions for Semantically Diverse Plans

Prior approaches to generating diverse plans in domain-independent planning seek out variations on plan structure such as actions or causal links used, or states entered. As a result, these approaches can achieve great plan set diversity by synthesizing unnecessarily long plans. This type of misleading diversity may be useful if, for example, the plans are used as training data for a learner; however, they have arguably low value to a human decision maker. We present an approach to domain-independent diverse planning that systematically varies the semantic attributes of plans so that we do not arbitrarily inflate plan length to achieve diversity. Our contribution is based upon the fact that landmarks, which represent the minimally necessary subgoals (semantics) of a planning domain, can be disjunctive and hence satisfied in a number of ways. Varying the disjuncts that must be satisfied by alternative plans leads to a form of diversity that does not encourage irrelevant plan structure. We present an extension of the LAMA planner called DLAMA that generates multiple plans, each required to systematically satisfy alternative landmark disjuncts. We show that, in comparison with prior diverse planners, DLAMA reduces average plan length while achieving plan set diversity.