An Algorithm for Probabilistic, Totally-Ordered Temporal Projection
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Computer Programming and Software