Accession Number:

ADA277341

Title:

An Algorithm for Probabilistic, Totally-Ordered Temporal Projection

Descriptive Note:

Research rept.

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1994-03-31

Pagination or Media Count:

58.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE