An Algorithm for Probabilistic, Totally-Ordered Temporal Projection
Abstract
Temporal projection, defined as the prediction of what might happen when a plan is executed, is an important component of many planning algorithms. To achieve efficiency, it is desirable for a projection to be a totally ordered event sequence. To cope with uncertainty, the events must be generated using probabilistic rules. We require a rule language that allows us to specify what can happen when an event occurs, as well as what events can occur when certain propositions are true. The language has a formal semantics, which allows us to prove that a set of rules has a unique model (if it is consistent). This language supports a Monte Carlo style of projection, in which event sequences are sampled randomly using the probabilities in the rules. The output of the projector is a timeline that allows a planning algorithm to test the truth of propositions at arbitrary points. The algorithms for building and retrieving from the timeline can be shown to be correct. Experiments show that for a typical theory, the time to build a timeline is a quadratic function of the number of events in the timeline.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 31, 1994
- Accession Number
- ADA277341
Entities
People
- Drew McDermott
Organizations
- Yale University