Validating Generalized Plans in the Presence of Incomplete Information

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Planning

Let Robbie be an agent possessing a generalized plan for accomplishing a goal. Can Robbie use his plan to accomplish the goal without passing through any of a set of forbidden world states en route to the goal? This situation arises if, for example, Robbie must accomplish the goal with some additional constraints ("Can I get to the airport in time without speeding?"). There are two poles in the spectrum of methods Robbie can use to test his plan in the new world situation, each with its own advantages and disadvantages. At one extreme, Robbie can choose to express the new world constraints as additional preconditions on all the operators used for planning. At the other extreme, Robbie can attempt to prove that the new constraints are satisfied in every possible world that could arise during execution of the plan, from any initial world state that is consistent with his axioms. In this paper we examine the tradeoffs between these two opposing approaches, and show that the approaches are in fact very similar from a computational complexity point of view.