Belief maintenance in dynamic constraint networks

Abstract

This paper presents a constraint network formulation of belief maintenance in dynamically changing environments. We focus on the task of computing the degree of support for each proposition, i.e., the number of solutions of the constraint network which are consistent with the proposition. The paper develops an efficient distributed scheme for calculating and revising beliefs in acyclic constraint networks. The suggested process consists of two phases. In the first, called support propagation, each variable updates the number of extensions consistent with each of its values. The second, called contradiction resolution, is invoked by a variable upon detecting a contradiction, and identifies a minimal set of assumptions that potentially account for the contradiction.