Analyzing plans with conditional effects

April 2002

Analyzing plans with conditional effects

Authors:

Elly Winner and Manuela Veloso

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.

@conference{Winner-2002-8409,
author = {Elly Winner And Manuela Veloso},
title = {Analyzing plans with conditional effects},
booktitle = {Proceedings of 6th International Conference on Artificial Intelligence Planning Systems (AIPS '02)},
year = {2002},
month = {April},
pages = {23 - 32},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.