[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink])

If a decision relies on an unknown property, every possible property value may yield another plan. If the property value becomes available somewhere within the plan, the plan has to branch for each important refinement. Planners that construct such branching plans are called contingency planners. Examples are Warren's WARPLAN-C [PUBLink], CNLP by Peot and Smith [PUBLink], Plinth by Goldman and Boddy [PUBLink] and Cassandra by Pryor and Collins [PUBLink].

An extension of this approach is probabilistic planning, where special probability distributions are considered as well. Work in this area includes Drummond and Bresina's synthetic projection [PUBLink], and the BURIDAN probabilistic planning by Kushmerick, Hanks and Weld [PUBLink] with its contingent extension by Draper, Hanks and Weld [PUBLink]. Recently, a lot of research in this area focuses on planning based on Markov decision processes (MDPs) (see [PUBLink] for an overview). Possible world states are represented explicitly for which an optimal policy is computed. This policy yields the optimal action for every possible state. Examples of MDP-based planning are approaches by Barto, Bradtke and Singh [PUBLink], Dean et al. [PUBLink] and Koenig and Liu [PUBLink].

The consideration/branching on multiple possibilities can be useful in terms of reliability. But this works only for smaller problems. Although the planners (especially the probabilistic ones) do not always search the whole search space, application to more complex problem domains, temporal planning and dynamic environments would largely overtax storage and computation power. Strong real-time requirements such as those for our agents are out of the question.

A solution is to consider only one plan with expected values instead of branching on several possible worlds. The expectations can be based on pessimism or optimism, as well as on estimated probabilities. Learning mechanisms can be applied, too. In the case of a failed prediction, the plan has to be changed. As long as no critical errors have been made, the iterative plan repair can automatically adapt the plan. The consideration of a single plan possibility instead of branching on multiple possibilities is close to the operator-parameterization approach of the Cypress system [PUBLink]. A non-branching plan can also represent incomplete knowledge regarding the states by using special values that represent the incomplete knowledge (see following sections).

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek