IDEAL (Influence Diagram Evaluation and Analysis in Lisp) is a software environment for creation and evaluation of belief networks and influence diagrams. IDEAL is primarily a research tool and provides an implementation of many of the latest developments in belief network and influence diagram evaluation in a unified framework. This paper describes IDEAL and some lessons learned during its development.

Knowledge elicitation is one of the major bottlenecks in expert system design. Systems based on Bayes nets require two types of information--network structure and parameters (or probabilities). Both must be elicited from the domain expert. In general, parameters have greater opacity than structure, and more time is spent in their refinement than in any other phase of elicitation. Thus, it is important to determine the point of diminishing returns, beyond which further refinements will promise little (if any) improvement. Sensitivity analyses address precisely this issue--the sensitivity of a model to the precision of its parameters. In this paper, we report the results of a sensitivity analysis of Pathfinder, a Bayes net based system for diagnosing pathologies of the lymph system. This analysis is intended to shed some light on the relative importance of structure and parameters to system performance, as well as the sensitivity of a system based on a Bayes net to noise in its assessed parameters.

A method of calculating probability values from a system of marginal constraints is presented. Previous systems for finding the probability of a single attribute have either made an independence assumption concerning the evidence or have required, in the worst case, time exponential in the number of attributes of the system. In this paper a closed form solution to the probability of an attribute given the evidence is found. The closed form solution, however does not enforce the (non-linear) constraint that all terms in the underlying distribution be positive. The equation requires O(r^3) steps to evaluate, where r is the number of independent marginal constraints describing the system at the time of evaluation. Furthermore, a marginal constraint may be exchanged with a new constraint, and a new solution calculated in O(r^2) steps. This method is appropriate for calculating probabilities in a real time expert system

When expert systems based on causal probabilistic networks (CPNs) reach a certain size and complexity, the "combinatorial explosion monster" tends to be present. We propose an approximation scheme that identifies rarely occurring cases and excludes these from being processed as ordinary cases in a CPN-based expert system. Depending on the topology and the probability distributions of the CPN, the numbers (representing probabilities of state combinations) in the underlying numerical representation can become very small. Annihilating these numbers and utilizing the resulting sparseness through data structuring techniques often results in several orders of magnitude of improvement in the consumption of computer resources. Bounds on the errors introduced into a CPN-based expert system through approximations are established. Finally, reports on empirical studies of applying the approximation scheme to a real-world CPN are given.

In this paper we present a framework for dynamically constructing Bayesian networks. We introduce the notion of a background knowledge base of schemata, which is a collection of parameterized conditional probability statements. These schemata explicitly separate the general knowledge of properties an individual may have from the specific knowledge of particular individuals that may have these properties. Knowledge of individuals can be combined with this background knowledge to create Bayesian networks, which can then be used in any propagation scheme. We discuss the theory and assumptions necessary for the implementation of dynamic Bayesian networks, and indicate where our approach may be useful.

In this paper we provide an overview of a new framework for robot perception, real-world modelling, and navigation that uses a stochastic tesselated representation of spatial information called the Occupancy Grid. The Occupancy Grid is a multi-dimensional random field model that maintains probabilistic estimates of the occupancy state of each cell in a spatial lattice. Bayesian estimation mechanisms employing stochastic sensor models allow incremental updating of the Occupancy Grid using multi-view, multi-sensor data, composition of multiple maps, decision-making, and incorporation of robot and sensor position uncertainty. We present the underlying stochastic formulation of the Occupancy Grid framework, and discuss its application to a variety of robotic tusks. These include range-based mapping, multi-sensor integration, path-planning and obstacle avoidance, handling of robot position uncertainty, incorporation of pre-compiled maps, recovery of geometric representations, and other related problems. The experimental results show that the Occupancy Grid approach generates dense world models, is robust under sensor uncertainty and errors, and allows explicit handling of uncertainty. It supports the development of robust and agile sensor interpretation methods, incremental discovery procedures, and composition of information from multiple sources. Furthermore, the results illustrate that robotic tasks can be addressed through operations performed di- rectly on the Occupancy Grid, and that these operations have strong parallels to operations performed in the image processing domain.

PIBNET is hard for NP, by reduction from 3-satisfiability in the propositional calculus [3]. That classification has focused research on approximate methods, special-case techniques, heuristics, and analyses of average-case behavior. There now exists a number of algorithms for exact probabilistic inference in belief networks: the message-passing algorithm of Pearl [ 12], the triangulation method of Lauritzen and Spiegelhalter [10], and others. Previous approximation algorithms include the Markov-simulation scheme of Pearl [13, 14], Henrion's logic sampling [7], and the randomized approximation scheme (ras), known as BN-RAS, which we have previously demonstrated [1]. Heckerman has proposed a special-case algorithm for certain kinds of two-level belief networks [6]. Each algorithm has computational properties that render it attractive for inference on certain kinds of networks. The NPhard classification suggests, however, that no algorithm can provide a definitive efficient solution for all inference problems.

In previous work (Fertig and Breese, 1989; Fertig and Breese, 1990) we defined a mechanism for performing probabilistic reasoning in influence diagrams using interval rather than point-valued probabilities. In this paper we extend these procedures to incorporate decision nodes and interval-valued value functions in the diagram. We derive the procedures for chance node removal (calculating expected value) and decision node removal (optimization) in influence diagrams where lower bounds on probabilities are stored at each chance node and interval bounds are stored on the value function associated with the diagram's value node. The output of the algorithm are a set of admissible alternatives for each decision variable and a set of bounds on expected value based on the imprecision in the input. The procedure can be viewed as an approximation to a full e-dimensional sensitivity analysis where n are the number of imprecise probability distributions in the input. We show the transformations are optimal and sound. The performance of the algorithm on an influence diagrams is investigated and compared to an exact algorithm.

We describe an environment that considerably simplifies the process of generating Bayesian belief networks. The system has been implemented on readily available, inexpensive hardware, and provides clarity and high performance. We present an introduction to Bayesian belief networks, discuss algorithms for inference with these networks, and delineate the classes of problems that can be solved with this paradigm. We then describe the hardware and software that constitute the system, and illustrate Ergo's use with several examples.

A significant problem in designing mobile robot control systems involves coping with the uncertainty that arises in moving about in an unknown or partially unknown environment and relying on noisy or ambiguous sensor data to acquire knowledge about that environment. We describe a control system that chooses what activity to engage in next on the basis of expectations about how the information re- turned as a result of a given activity will improve 2 its knowledge about the spatial layout of its environment. Certain of the higher-level components of the control system are specified in terms of probabilistic decision models whose output is used to mediate the behavior of lower-level control components responsible for movement and sensing.