This project addresses the problem of modeling time in dynamic domains given incomplete and uncertain information about the domain. The first objective is to construct a dynamic model within a belief-network paradigm and to demonstrate how well known time series concepts-such as backward smoothing forward filtering and forecasting - are implemented in this model. The dynamic model will be generated semiautomatically given a belief network that models the time-invariant relations of the domain. This will provide a semiautomatic method for extending existing belief network models to dynamic belief-network models that can be used in applications where consideration of the time evolution of system variables is crucial to making valid inferences about the domain. The second objective is to design an efficient randomized approximation scheme (RAS) for probabilistic inference in belief networks to be employed by the dynamic model. Certain features unique to a RAS, compared to other stochastic simulation algorithms for probabilistic inference, make the RAS desirable as an inference algorithm for a dynamic model. For example, in dynamic domains, the time required to make a decision enters the utility of the decision when this time becomes comparable to the expected time in which the system changes sufficiently to outdated a decision. A RAS provides an a priori bound on the running time required to achieve a predefined level of accuracy in the output. This information can be used to reduce the loss of utility due to delayed decisions. Existing RASs for probabilistic inference in belief networks are known to have a poor worst-case behavior, although it is conjectured that they have efficient average-case complexity. This research will characterize the class of belief networks or which existing RASs run efficiently, then will extend these algorithms to handle cases that fall outside of this class. The new RASs developed will be subsequently optimized specifically for computing inferences in the dynamic models developed.
