# 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.

# Descriptors:

# Subject Categories:

- Computer Programming and Software