Since its inception, artificial intelligence has relied upon a theoretical foundation centered around perfect rationality as the desired property of intelligent systems. We argue, as others have done, that this foundation is inadequate because it imposes fundamentally unsatisfiable requirements. As a result, there has arisen a wide gap between theory and practice in AI, hindering progress in the field. We propose instead a property called bounded optimality. Roughly speaking, an agent is bounded-optimal if its program is a solution to the constrained optimization problem presented by its architecture and the task environment. We show how to construct agents with this property for a simple class of machine architectures in a broad class of real-time environments. We illustrate these results using a simple model of an automated mail sorting facility. We also define a weaker property, asymptotic bounded optimality (ABO), that generalizes the notion of optimality in classical complexity theory. We then construct universal ABO programs, i.e., programs that are ABO no matter what real-time constraints are applied. Universal ABO programs can be used as building blocks for more complex systems. We conclude with a discussion of the prospects for bounded optimality as a theoretical basis for AI, and relate it to similar trends in philosophy, economics, and game theory.

In a companion paper it was shown that the class of constant-depth determinate k-ary recursive clauses is efficiently learnable. In this paper we present negative results showing that any natural generalization of this class is hard to learn in Valiant's model of pac-learnability. In particular, we show that the following program classes are cryptographically hard to learn: programs with an unbounded number of constant-depth linear recursive clauses; programs with one constant-depth determinate clause containing an unbounded number of recursive calls; and programs with one linear recursive clause of constant locality. These results immediately imply the non-learnability of any more general class of programs. We also show that learning a constant-depth determinate program with either two linear recursive clauses or one linear recursive clause and one non-recursive clause is as hard as learning boolean DNF. Together with positive results from the companion paper, these negative results establish a boundary of efficient learnability for recursive function-free clauses.

Many studies have been carried out in order to increase thesearch efficiency of constraint satisfaction problems; among them,some make use of structural properties of the constraintnetwork; others take into account semantic properties of theconstraints, generally assuming that all the constraints possessthe given property. In this paper, we propose a new decompositionmethod benefiting from both semantic properties of functional constraints (not bijective constraints) and structuralproperties of the network; furthermore, not all the constraints needto be functional. We show that under some conditions, the existenceof solutions can be guaranteed. We first characterize a particularsubset of the variables, which we name a root set. We thenintroduce pivot consistency, a new local consistency which is aweak form of path consistency and can be achieved in O(n^2d^2)complexity (instead of O(n^3d^3) for path consistency), and wepresent associated properties; in particular, we show that anyconsistent instantiation of the root set can be linearly extended to a solution, which leads to the presentation of the aforementioned new method for solving by decomposing functional CSPs.

Theory revision integrates inductive learning and background knowledge by combining training examples with a coarse domain theory to produce a more accurate theory. There are two challenges that theory revision and other theory-guided systems face. First, a representation language appropriate for the initial theory may be inappropriate for an improved theory. While the original representation may concisely express the initial theory, a more accurate theory forced to use that same representation may be bulky, cumbersome, and difficult to reach. Second, a theory structure suitable for a coarse domain theory may be insufficient for a fine-tuned theory. Systems that produce only small, local changes to a theory have limited value for accomplishing complex structural alterations that may be required. Consequently, advanced theory-guided learning systems require flexible representation and flexible structure. An analysis of various theory revision systems and theory-guided learning systems reveals specific strengths and weaknesses in terms of these two desired properties. Designed to capture the underlying qualities of each system, a new system uses theory-guided constructive induction. Experiments in three domains show improvement over previous theory-guided systems. This leads to a study of the behavior, limitations, and potential of theory-guided constructive induction.

COMIX (configuration of mixing machines) is a system that assists members of the EKATO Sales Department in designing a mixing machine that fulfills the requirements of a customer. It is used to help the engineer design the requested machine and prepare an offer that's to be submitted to the customer. During the process of routine design, some design decisions have to be made with uncertainty. The success of the system can be measured by the increase in the quantity and the quality of the submitted offers.

Interactive simulation environments constitute one of today's promising emerging technologies, with applications in areas such as education, manufacturing, entertainment, and training. These environments are also rich domains for building and investigating intelligent automated agents, with requirements for the integration of a variety of agent capabilities but without the costs and demands of low-level perceptual processing or robotic control. Our current target is intelligent automated pilots for battlefield-simulation environments. This article provides an overview of this domain and project by analyzing the challenges that automated pilots face in battlefield simulations, describing how TacAir-Soar is successfully able to address many of them -- TacAir-Soar pilots have already successfully participated in constrained air-combat simulations against expert human pilots -- and discussing the issues involved in resolving the remaining research challenges.

It is clear from these discussions that the notion of context is far from defined and is dependent in its interpretation on a cognitive science versus an engineering (or system building) point of view. In identifying the two points of view, this workshop permitted us to go one step further than previous workshops (notably Maskery and Meads [1992] and Maskery, Hopkins, and Dudley [1992]). Once a distinction is made on the viewpoint, one can achieve a surprising consensus on the aspects of context that the workshop addressed -- mainly, the position, the elements, the representation, and the use of context. Despite this consensus on the aspects of context, agreement on the definition of context was not yet achieved.

The Association for the Advancement of Artificial Intelligence held its 1994 Fall Symposium Series on November 4-6 at the Monteleone Hotel in New Orleans, Louisiana. This article contains summaries of the five symposia that were conducted: (1) Control of the Physical World by Intelligent Agents, (2) Improving Instruction of Introductory AI, (3) Knowledge Representation for Natural Language Processing in Implemented Systems, (4) Planning and Learning: On to Real Applications, and (5) Relevance.

CLAVIER is a case-based reasoning (CBR) system that assists in determining efficient loads of composite material parts to be cured in an autoclave. CLAVIER's central purpose is to find the most appropriate groupings and configurations of parts (or loads) to maximize autoclave throughput yet ensure that parts are properly cured. CLAVIER uses CBR to match a list of parts that need to be cured against a library of previously successful loads and suggest the most appropriate next load. As one of the first fielded CBR systems, CLAVIER demonstrates that CBR is a practical technology that can be used successfully in domains where more traditional approaches are difficult to apply.

The vertical launch system (vls) tech-assist expert system is being used by the in-service engineering agent as a force multiplier to maintain the readiness, with fewer resources, of a growing population of vlss in the U.S. Navy fleet. This article describes the collaborative development of this knowledge-based system for diagnosis; its main features, including case-based and model-based reasoning; and the lessons we learned from the process.