A new approach to plan-space explanation: analyzing plan-property dependencies in oversubscription planning

Eifler, Rebecca and Cashmore, Michael and Hoffmann, Jörg and Magazzeni, Daniele and Steinmetz, Marcel; (2020) A new approach to plan-space explanation: analyzing plan-property dependencies in oversubscription planning. In: Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press, Palo Alto, California USA, pp. 9818-9826. ISBN 9781577358350 (https://doi.org/10.1609/aaai.v34i06.6534)

[thumbnail of Eifler-etal-CAI-2020-plan-space-explanation-analyzing-plan-property-dependencies-in-oversubscription-planning]
Preview
 Text. Filename: Eifler_etal_CAI_2020_plan_space_explanation_analyzing_plan_property_dependencies_in_oversubscription_planning.pdf
Final Published Version
License: All rights reserved
Download (565kB)| Preview

Abstract

In many usage scenarios of AI Planning technology, users will want not just a plan π but an explanation of the space of possible plans, justifying π. In particular, in oversubscription planning where not all goals can be achieved, users may ask why a conjunction A of goals is not achieved by π. We propose to answer this kind of question with the goal conjunctions B excluded by A, i. e., that could not be achieved if A were to be enforced. We formalize this approach in terms of plan-property dependencies, where plan properties are propositional formulas over the goals achieved by a plan, and dependencies are entailment relations in plan space. We focus on entailment relations of the form ∧g∈A g ⇒ ⌝ ∧g∈B g, and devise analysis techniques globally identifying all such relations, or locally identifying the implications of a single given plan property (user question) ∧g∈A g. We show how, via compilation, one can analyze dependencies between a richer form of plan properties, specifying formulas over action subsets touched by the plan. We run comprehensive experiments on adapted IPC benchmarks, and find that the suggested analyses are reasonably feasible at the global level, and become significantly more effective at the local level.

CORE (COnnecting REpositories)