Fundamental concepts of qualitative probabilistic networks

Graphical representations for probabilistic relationships have recently received considerable attention in AI. Qualitative probabilistic networks abstract from the usual numeric representations by encoding only qualitative relationships, which are inequality constraints on the joint probability distribution over the variables. Although these constraints are insufficient to determine probabilities uniquely, they are designed to justify the deduction of a class of relative likelihood conclusions that imply useful decision-making properties. Two types of qualitative relationship are defined, each a probabilistic form of monotonicity constraint over a group of variables. Qualitative influences describe the direction of the relationship between two variables. Qualitative synergies describe interactions among influences. The probabilistic definitions chosen justify sound and efficient inference procedures based on graphical manipulations of the network. These procedures answer queries about qualitative relationships among variables separated in the network and determine structural properties of optimal assignments to decision variables.

Planning and Control

TL Dean and MP Wellman Morgan Kaufmann Publishers, 1991. Google Books ISBN-10: 1558602097 ISBN-13: 978-1558602090

Impediments to universal preference-based default theories

Research on nonmonotonic and default reasoning has identified several important criteria for preferring alternative default inferences. The theories of reasoning based on each of these criteria may uniformly be viewed as theories of rational inference, in which the reasoner selects maximally preferred states of belief. Though researchers have noted some cases of apparent conflict between the preferences supported by different theories, it has been hoped that these special theories of reasoning may be combined into a universal logic of nonmonotonic reasoning. We show that the different categories of preferences conflict more than has been realized, and adapt formal results from social choice theory to prove that every universal theory of default reasoning will violate at least one reasonable principle of rational reasoning. Our results can be interpreted as demonstrating that, within the preferential framework, we cannot expect much improvement on the rigid lexicographic priority mechanisms that have been proposed for conflict resolution.

A Logic of Relative Desire (Preliminary Report)

Although many have proposed formal characterizations of belief structures as bases for rational action, the problem of characterizing rational desire has attracted little attention. AI relies heavily on goal conditions interpreted (apparently) as absolute expressions of desirability, but these cannot express varying degrees of goal satisfaction or preferences among alternative goals. Our previous work provided a relative interpretation of goals as qualitative statements about preferability, all else equal. We extend that treatment to the comparision of arbitrary propositions, and develop a propositional logic of relative desire suitable for formalizing properties of planning and problem-solving methods.

Modular Utility Representation for Decision-Theoretic Planning

Specification of objectives constitutes a central issue in knowledge representation for planning. Decision-theoretic approaches require that representations of objectives possess a firm semantics in terms of utility functions, yet provide the flexible compositionality needed for practical preference modeling for planning systems. Modularity, or separability in specification, is the key representational feature enabling this flexibility. In the context of utility specification, modularity corresponds exactly to well-known independence concepts from multiattribute utility theory, and leads directly to approaches for composing separate preference specifications. Ultimately, we seek to use this utility-theoretic account to justify and improve existing mechanisms for specification of preference information, and to develop new representations exhibiting tractable specification and flexible composition of preference criteria.

From knowledge bases to decision models

In recent years there has been a growing interest among AI researchers in probabilistic and decision modeling, spurred by significant advances in representation and computation with network modeling formalisms. In applying these techniques to decision-support tasks, fixed network models have proven inadequately expressive to handle a broad range of situations. Therefore, many researchers have sought to combine the flexibility of general-purpose knowledge representation languages with the normative status and well-understood computational properties of decision-modeling formalisms and algorithms. One approach is to encode general knowledge in an expressive language, then dynamically construct a decision model for each particular situation or problem instance. We have developed several systems adopting this approach, which illustrate a variety of interesting techniques and design issues.

Explaining “Explaining Away”

"Explaining away" is a common pattern of reasoning in which the confirmation of one cause of an observed or believed event reduces the need to invoke alternative causes. The opposite of explaining away also an occur, where the confirmation of one cause increases belief in another. A general qualitative probabilistic analysis of intercausal reasoning is provided and the property of the interaction among the causes (product synergy) that determines which form of reasoning is appropriate is identified. Product synergy extends the qualitative probabilistic network (QPN) formalism to support qualitative intercausal inference about the directions of change in probabilistic belief. The intercausal relation also justifies Occam's razor, facilitating pruning in the search for likely diagnoses.

A market-oriented programming environment and its application to distributed multicommodity flow problems

Market price systems constitute a well-understood class of mechanisms that under certain conditions provide effective decentralization of decision making with minimal communication overhead. In a market-oriented programming approach to distributed problem solving, we derive the activities and resource allocations for a set of computational agents by computing the competitive equilibrium of an artificial economy. WALRAS provides basic constructs for defining computational market structures, and protocols for deriving their corresponding price equilibria. In a particular realization of this approach for a form of multicommodity flow problem, we see that careful construction of the decision process according to economic principles can lead to efficient distributed resource allocation, and that the behavior of the system can be meaningfully analyzed in economic terms.

The Automated Mapping of Plans for Plan Recognition

To coordinate with other agents in its environment, an agent needs models of what the other agents are trying to do. When communication is impossible or expensive, this information must be acquired indirectly via plan recognition. Typical approaches to plan recognition start with a specification of the possible plans the other agents may be following, and develop special techniques for discriminating among the possibilities. Perhaps more desirable would be a uniform procedure for mapping plans to general structures supporting inference based on uncertain and incomplete observations. In this paper, we describe a set of methods for converting plans represented in a flexible procedural language to observation models represented as probabilistic belief networks.

State-space Abstraction for Anytime Evaluation of Probabilistic Networks

One important factor determining the computational complexity of evaluating a probabilistic network is the cardinality of the state spaces of the nodes. By varying the granularity of the state spaces, one can trade off accuracy in the result for computational efficiency. We present an anytime procedure for approximate evaluation of probabilistic networks based on this idea. On application to some simple networks, the procedure exhibits a smooth improvement in approximation quality as computation time increases. This suggests that state-space abstraction is one more useful control parameter for designing real-time probabilistic reasoners.