Analyzing plans with conditional effects

Abstract

Several tasks, such as plan reuse and agent modeling, rely on interpreting a given or observed plan to generate the underlying plan rationale. Although there are several previous methods that successfully extract plan rationales, they do not apply to complex plans, in particular to plans with actions that have conditional effects. In this paper, we introduce SPRAWL, an algorithm to find a minimal annotated partially ordered structure that maximizes a given evaluation function for an observed totally ordered plan with conditional effects. The algorithm proceeds in a two-phased approach, first preprocessing the given plan using a novel needs analysis technique that builds a needs tree to identify the dependencies between operators in the totally ordered plan. The needs tree is then processed to construct a partial ordering that captures the complete rationale of the given plan. We also provide a polynomial-time algorithm to find non-optimal minimal annotated partial orderings of observed totally ordered plans with conditional effects. We provide illustrative examples and discuss the challenges we faced.