An increasing number of planners can handle uncertainty in the domain or in action outcomes. However, less work has addressed building plans when the planner's world can change independently of the planning agent in an uncertain manner. In this paper, I model this change with external events that concisely represent some aspects of structure in the planner's domain. This event model is given a formal semantics in terms of a Markov chain, but probabilistic computations from this chain would be intractable in real-world domains. I describe a technique, based on a reachability analysis of a graph built from the events, that allows abstractions of the Markov chain to be built to answer specific queries efficiently. I prove that the technique is correct. I have implemented a planner that uses this technique, and I show an example from a large planning domain.
html,
postscript.
(I'm currently having some problems with latex2html, so the postscript is
better.)