Tech Report CS-93-31

Techniques for Handling Inference Complexity in Dynamic Belief Networks

Ann Nicholson and Stuart Russell

July 1993

Abstract:

Dynamic belief networks (DBNs) have been of interest recently as modelling tools for environments that change over time. In such networks, sets of nodes may be added automatically over time to represent current and future states. DBNs are typically multiply connected, and inference complexity is the biggest barrier to successful use. In this paper, we present both exact and heuristic techniques for state space reduction, thresholding and backtracking that can dramatically reduce inference costs without significantly reducing accuracy. We illustrate this in the domain of continuous monitoring of mobile robots. In order to control the costs and benefits of our heuristic methods, the system requires a good model of inference cost for any given network structure. We therefore also present results showing that Kanazawa's ``join-tree cost'' model gives a very good fit to actual inference costs in large networks.

(complete text in pdf or gzipped postscript)