We start by defining an approach to non-monotonic probabilistic reasoning in terms of non-monotonic categorical (true-false) reasoning. We identify a type of non-monotonic probabilistic reasoning, akin to default inheritance, that is commonly found in practice, especially in "evidential" and "Bayesian" reasoning. We formulate this in terms of the Maximization of Conditional Independence (MCI), and identify a variety of applications for this sort of default. We propose a formalization using Pointwise Circumscription. We compare MCI to Maximum Entropy, another kind of non-monotonic principle, and conclude by raising a number of open questions

To develop an approach to utilizing continuous statistical information within the Dempster- Shafer framework, we combine methods proposed by Strat and by Shafero We first derive continuous possibility and mass functions from probability-density functions. Then we propose a rule for combining such evidence that is simpler and more efficiently computed than Dempster's rule. We discuss the relationship between Dempster's rule and our proposed rule for combining evidence over continuous frames.

Scheduling in the factory setting is compounded by computational complexity and temporal uncertainty. Together, these two factors guarantee that the process of constructing an optimal schedule will be costly and the chances of executing that schedule will be slight. Temporal uncertainty in the task execution time can be offset by several methods: eliminate uncertainty by careful engineering, restore certainty whenever it is lost, reduce the uncertainty by using more accurate sensors, and quantify and circumscribe the remaining uncertainty. Unfortunately, these methods focus exclusively on the sources of uncertainty and fail to apply knowledge of the tasks which are to be scheduled. A complete solution must adapt the schedule of activities to be performed according to the evolving state of the production world. The example of vision-directed assembly is presented to illustrate that the principle of least commitment, in the creation of a plan, in the representation of a schedule, and in the execution of a schedule, enables a robot to operate intelligently and efficiently, even in the presence of considerable uncertainty in the sequence of future events.

There currently exists a gap between the theories proposed by the probability and uncertainty and the needs of Artificial Intelligence research. These theories primarily address the needs of expert systems, using knowledge structures which must be pre-compiled and remain static in structure during runtime. Many Al systems require the ability to dynamically add and remove parts of the current knowledge structure (e.g., in order to examine what the world would be like for different causal theories). This requires more flexibility than existing uncertainty systems display. In addition, many Al researchers are only interested in using "probabilities" as a means of obtaining an ordering, rather than attempting to derive an accurate probabilistic account of a situation. This indicates the need for systems which stress ease of use and don't require extensive probability information when one cannot (or doesn't wish to) provide such information. This paper attempts to help reconcile the gap between approaches to uncertainty and the needs of many AI systems by examining the control issues which arise, independent of a particular uncertainty calculus. when one tries to satisfy these needs. Truth Maintenance Systems have been used extensively in problem solving tasks to help organize a set of facts and detect inconsistencies in the believed state of the world. These systems maintain a set of true/false propositions and their associated dependencies. However, situations often arise in which we are unsure of certain facts or in which the conclusions we can draw from available information are somewhat uncertain. The non-monotonic TMS 12] was an attempt at reasoning when all the facts are not known, but it fails to take into account degrees of belief and how available evidence can combine to strengthen a particular belief. This paper addresses the problem of probabilistic reasoning as it applies to Truth Maintenance Systems. It describes a belief Maintenance System that manages a current set of beliefs in much the same way that a TMS manages a set of true/false propositions. If the system knows that belief in fact is dependent in some way upon belief in fact2, then it automatically modifies its belief in facts when new information causes a change in belief of fact2. It models the behavior of a TMS, replacing its 3-valued logic (true, false, unknown) with an infinite valued logic, in such a way as to reduce to a standard TMS if all statements are given in absolute true/false terms. Belief Maintenance Systems can, therefore, be thought of as a generalization of Truth Maintenance Systems, whose possible reasoning tasks are a superset of those for a TMS.

Two different approaches to dealing with probabilistic knowledge are examined -models and inductive inference. Examples of the first are: influence diagrams [1], Bayesian networks [2], log-linear models [3, 4]. Examples of the second are: games-against nature [5, 6] varieties of maximum-entropy methods [7, 8, 9], and the author's min-score induction [10]. In the modeling approach, the basic issue is manageability, with respect to data elicitation and computation. Thus, it is assumed that the pertinent set of users in some sense knows the relevant probabilities, and the problem is to format that knowledge in a way that is convenient to input and store and that allows computation of the answers to current questions in an expeditious fashion. The basic issue for the inductive approach appears at first sight to be very different. In this approach it is presumed that the relevant probabilities are only partially known, and the problem is to extend that incomplete information in a reasonable way to answer current questions. Clearly, this approach requires that some form of induction be invoked. Of course, manageability is an important additional concern. Despite their seeming differences, the two approaches have a fair amount in common, especially with respect to the structural framework they employ. Roughly speaking, this framework involves identifying clusters of variables which strongly interact, establishing marginal probability distributions on the clusters, and extending the subdistributions to a more complete distribution, usually via a product formalism. The product extension is justified on the modeling approach in terms of assumed conditional independence; in the inductive approach the product form arises from an inductive rule.

A model of knowledge representation is described in which propositional facts and the relationships among them can be supported by other facts. The set of knowledge which can be supported is called the set of cognitive units, each having associated descriptions of their explicit and implicit support structures, summarizing belief and reliability of belief. This summary is precise enough to be useful in a computational model while remaining descriptive of the underlying symbolic support structure. When a fact supports another supportive relationship between facts we call this meta-support. This facilitates reasoning about both the propositional knowledge. and the support structures underlying it.

The discovery that the minimax decision rule performs poorly in some games has sparked interest in possible alternatives to minimax. Until recently, the only games in which minimax was known to perform poorly were games which were mainly of theoretical interest. However, this paper reports results showing poor performance of minimax in a more common game called kalah. For the kalah games tested, a non-minimax decision rule called the product rule performs significantly better than minimax. This paper also discusses a possible way to predict whether or not minimax will perform well in a game when compared to product. A parameter called the rate of heuristic flaw (rhf) has been found to correlate positively with the. performance of product against minimax. Both analytical and experimental results are given that appear to support the predictive power of rhf.

In [12], Nilsson proposed the probabilistic logic in which the truth values of logical propositions are probability values between 0 and 1. It is applicable to any logical system for which the consistency of a finite set of propositions can be established. The probabilistic inference scheme reduces to the ordinary logical inference when the probabilities of all propositions are either 0 or 1. This logic has the same limitations of other probabilistic reasoning systems of the Bayesian approach. For common sense reasoning, consistency is not a very natural assumption. We have some well known examples: {Dick is a Quaker, Quakers are pacifists, Republicans are not pacifists, Dick is a Republican}and {Tweety is a bird, birds can fly, Tweety is a penguin}. In this paper, we shall propose some extensions of the probabilistic logic. In the second section, we shall consider the space of all interpretations, consistent or not. In terms of frames of discernment, the basic probability assignment (bpa) and belief function can be defined. Dempster's combination rule is applicable. This extension of probabilistic logic is called the evidential logic in [ 1]. For each proposition s, its belief function is represented by an interval [Spt(s), Pls(s)]. When all such intervals collapse to single points, the evidential logic reduces to probabilistic logic (in the generalized version of not necessarily consistent interpretations). Certainly, we get Nilsson's probabilistic logic by further restricting to consistent interpretations. In the third section, we shall give a probabilistic interpretation of probabilistic logic in terms of multi-dimensional random variables. This interpretation brings the probabilistic logic into the framework of probability theory. Let us consider a finite set S = {sl, s2, ..., Sn) of logical propositions. Each proposition may have true or false values; and may be considered as a random variable. We have a probability distribution for each proposition. The e-dimensional random variable (sl,..., Sn) may take values in the space of all interpretations of 2n binary vectors. We may compute absolute (marginal), conditional and joint probability distributions. It turns out that the permissible probabilistic interpretation vector of Nilsson [12] consists of the joint probabilities of S. Inconsistent interpretations will not appear, by setting their joint probabilities to be zeros. By summing appropriate joint probabilities, we get probabilities of individual propositions or subsets of propositions. Since the Bayes formula and other techniques are valid for e-dimensional random variables, the probabilistic logic is actually very close to the Bayesian inference schemes. In the last section, we shall consider a relaxation scheme for probabilistic logic. In this system, not only new evidences will update the belief measures of a collection of propositions, but also constraint satisfaction among these propositions in the relational network will revise these measures. This mechanism is similar to human reasoning which is an evaluative process converging to the most satisfactory result. The main idea arises from the consistent labeling problem in computer vision. This method is originally applied to scene analysis of line drawings. Later, it is applied to matching, constraint satisfaction and multi sensor fusion by several authors [8], [16] (and see references cited there). Recently, this method is used in knowledge aggregation by Landy and Hummel [9].

The ability to predict the future in a given domain can be acquired by discovering empirically from experience certain temporal patterns that tend to repeat unerringly. Previous works in time series analysis allow one to make quantitative predictions on the likely values of certain linear variables. Since certain types of knowledge are better expressed in symbolic forms, making qualitative predictions based on symbolic representations require a different approach. A domain independent methodology called TIM (Time based Inductive Machine) for discovering potentially uncertain temporal patterns from real time observations using the technique of inductive inference is described here.

One of the most important aspects of current expert systems technology is the ability to make causal inferences about the impact of new evidence. When the domain knowledge and problem knowledge are uncertain and incomplete Bayesian reasoning has proven to be an effective way of forming such inferences [3,4,8]. While several reasoning schemes have been developed based on Bayes Rule, there has been very little work examining the comparative effectiveness of these schemes in a real application. This paper describes a knowledge based system for ship classification [1], originally developed using the PROSPECTOR updating method [2], that has been reimplemented to use the inference procedure developed by Pearl and Kim [4,5]. We discuss our reasons for making this change, the implementation of the new inference engine, and the comparative performance of the two versions of the system.