This paper discusses the application of a conceptual clustering algorithm called ITERATE to improve complex problem solving. More specifically, we apply the ITERATE system to build a hierarchy of rule models from sets of rules defined for PLAYMAKER, an expert system for characterizing hydrocarbon fields and plays in terms of their essential geological characteristics for the purposes of prospect analysis. PLAYMAKER is built on MIDST, an expert system shell that employs task-specific reasoning structures. The rule model hierarchy derived by ITERATE is then used with the task-specific reasoning structures to develop a more efficient and focused reasoning mechanism. A set of case studies were conducted to demonstrate the improved performance of the reasoning system.

Automation of engine model calibration procedures is a very challenging task because (1) the calibration process searches for a goal state in a huge, continuous state space, (2) calibration is often a lengthy and frustrating task because of complicated mutual interference among the target parameters, and (3) the calibration problem is heuristic by nature, and often heuristic knowledge for constraining a search cannot be easily acquired from domain experts. A combined heuristic and machine learning approach has, therefore, been adopted to improve the efficiency of model calibration. We developed an intelligent calibration program called ICALIB. It has been used on a daily basis for engine model applications, and has reduced the time required for model calibrations from many hours to a few minutes on average. In this paper, we describe the heuristic control strategies employed in ICALIB such as a hill-climbing search based on a state distance estimation function, incremental problem solution refinement by using a dynamic tolerance window, and calibration target parameter ordering for guiding the search. In addition, we present the application of a machine learning program called GID3^* for automatic acquisition of heuristic rules for ordering target parameters.

Interpreting remotely sensed data typically requires expensive, specialized computing machinery capable of storing and manipulating large amounts of data quickly. In this paper, we present a method for accurately analyzing and categorizing remotely sensed data on much smaller, less expensive platforms. Data size is reduced in such a way as to retain the integrity of the original data, where the format of the resultant data set lends itself well to providing an efficient, interactive method of data classification.

The system diagnostic builder (SDB) is an automated knowledge acquisition tool using state- of-the-art artificial intelligence (AI) technologies. The SDB uses an inductive machine learning technique to generate rules from data sets that are classified by a subject matter expert (SME). Thus, data is captured from the subject system, classified by an expert, and used to drive the rule generation process. These rule-bases are used to represent the observable behavior of the subject system, and to represent knowledge about this system. The rule-bases can be used in any knowledge based system which monitors or controls a physical system or simulation. The SDB has demonstrated the utility of using inductive machine learning technology to generate reliable knowledge bases. In fact, we have discovered that the knowledge captured by the SDB can be used in any number of applications. For example, the knowledge bases captured from the SMS can be used as black box simulations by intelligent computer aided training devices. We can also use the SDB to construct knowledge bases for the process control industry, such as chemical production, or oil and gas production. These knowledge bases can be used in automated advisory systems to ensure safety, productivity, and consistency.

An explanation component has been developed for an existing oceanographic expert system that predicts the movement of mesoscale features associated with the Gulf Stream. The structure of the original system was not amenable to the incorporation of an explanation facility because the knowledge needed for explanation was not explicitly represented in the knowledge base. A set of design principles that facilitate the implementation of an explanation component were developed and used as a basis for revision of the rule base. The explanation component consists of an introspection module that `watches' the reasoning process and a presentation module that uses the information gathered by the introspection module to construct a detailed natural language trace of the rules or a shorter natural language summary of the reasoning used for the prediction.

An autonomous agent is a device (or being) that can cope effectively in a defined environment, despite the fact that the environment is not completely controlled or even certainly known by the agent. If an autonomous agent is to be robust in such an environment, it must be able to plan its activities, react quickly to unforeseen events, and execute planned or modified behaviors to achieve goals. Building such agents is not trivial, but can yield high payoffs in environments such as air combat. We have begun to develop autonomous agents which exhibit appropriate behaviors for simulated air combat. Simulated air combat is a forgiving environment that allows us to study issues in building autonomous agents, but also meets real Air Force needs for training. In this paper, we outline the requirements of autonomous adversaries for air combat simulation and describe two prototype systems we have developed to lay the foundation for a multi-faceted research thrust in autonomous agent technology.

In this paper we address the problem of partitioning the nodes of a random graph into two sets, so as to maximize the sum of the weights on the edges connecting nodes belonging to different sets. This problem has important real-life counterparts, but has been proven to be NP-complete. As such, a number of heuristic solution techniques have been proposed in literature to address this problem. We propose a stochastic optimization technique, simulated annealing, to find solutions for the max cut problem. Our experiments verify that good solutions to the problem can be found using this algorithm in a reasonable amount of time.

In this paper we propose an integrated model which is derived from the combination of a generic neuro-expert system model, an object model, and unix operating system process (UOSP) model. This integrated model reflects the strengths of both artificial neural nets (ANNs) and expert systems (ESs). A formalism of ES object, ANN object, UOSP object, and problem domain object is used for developing a set of generic data structures and methods. These generic data structures and methods help us to build heterogeneous ES-ANN objects with uniform communication interface. The integrated model is applied in a real-time alarm processing system for a non-trivial terminal power station. It is shown how features like hierarchical/distributed ES/ANN objects, inter process communication, and fast concurrent execution help to cope with real-time system constraints like, continuity, data variability, and fast response time.

This paper describes an intelligent user interface that is currently under development. The interface serves as a front end for real-time spacecraft monitoring software. The software operates under circumstances in which neither an intelligent human without automated assistance nor an automated system without intelligence are sufficiently effective. The user interface is supported by dynamic trade-off evaluation (DTE), a new technique that has been developed to automate general types of performance trade-offs in real-time problem solving systems. In this application, DTE is used to perform dynamic input data management for the purpose of determining which input data should be monitored in time constrained situations and how to present the monitoring information to a human analyst who has the ultimate responsibility for the spacecraft. This application has demonstrated that DTE can be used to dynamically vary the data that is monitored, making it possible to detect and correctly analyze all anomalous data by examining only a subset of the total input data. In carefully structured experimental evaluations that use real spacecraft data and real decision making, DTE provides the ability to handle a three-fold increase in input data (in real-time) without loss of performance and to intelligently present the information to a mission analyst.

An earlier paper identified satellite control as one of ten space applications suitable for artificial intelligence techniques. Building on this research, we outlined an approach to reasoning that integrates diverse reasoning paradigms for problem solving and discussed how such an approach could reduce the human intervention required for satellite control. Since that time, we have developed a prototype for the reaction wheel assembly of the Hubble Space Telescope to test our theories. This paper discusses (1) the domain of satellite control in general and the reaction wheel assembly in particular, (2) the four reasoning methodologies selected for integration in a reasoning system, (3) the integrating architecture, (4) a description of a sample operation, and (5) our conclusions.

In this paper we address the problem of detecting and diagnosing faults in physical systems, for which neither prior expertise for the task nor suitable system models are available. We propose an architecture that integrates the on-line acquisition and exploitation of monitoring and diagnostic knowledge. The focus of the paper is on the component of the architecture that discovers classes of behaviors with similar characteristics by observing a system in operation. We investigate a characterization of behaviors based on best fitting approximation models. An experimental prototype has been implemented to test it. We present preliminary results in diagnosing faults of the reaction control system of the Space Shuttle. The merits and limitations of the approach are identified and directions for future work are set.

This paper describes a system which will provide real-time failure analysis support to controllers in the NASA Johnson Space Center (JSC) Control Center Complex (CCC) for both Space Station and Space Shuttle on-orbit operations. The system uses monitored systems' models of failure behavior (digraphs) and model evaluation algorithms which are domain independent. The digraph models are being generated by various communities in support of design analyses; e.g., engineering design, systems integration, safety, and reliability. When adapted for operational use these models provide a means for capturing design knowledge of system failure behavior and transferring it to the operational environment. The described system differs from failure identification systems evolved from research efforts in that it has been designed from the outset to meet two sets of requirements. First, it must provide a useful failure analysis capability enhancement to the mission controller. Second, it must satisfy CCC operational environment constraints such as cost, computer resource requirements, verification and validation, etc. This paper discusses the underlying technology and how it may be used to support operations.

Structured top-down design can be viewed as a process of iterative step-wise representation changes wherein an initial specification passes through several levels of increasingly concrete representations. When viewed this way, many of the goals and difficulties of hardware CAD are strikingly similar to those addressed by the branch of AI problem solving known as `Problem Reformulation.' Our principal aim is to provide a common mathematical setting to the two disciplines and then to exploit problem reformulation results in the design and implementation of a CAD system that can reason about VLSI design as representational change. The CAD system builds on one that has a proof assistant at its core, so that circuits designed in the system are pre-verified. High-level design knowledge is captured by algebraic models; refinement transformations between levels and optimizing and partitioning functions within a level are algebraic homomorphisms. The use of algebra throughout allows us to add different kinds and levels of reasoning to the theorem prover without a loss of mathematical soundness. The formalization of the `design as representation change' idea involves bringing together various strands in abstract algebra, artificial intelligence, and formal methods for system design. In this paper we describe the algebraic background and give examples and results of this kind of analysis in artificial intelligence and multi-layered hardware description.

A knowledge based system has been developed to assist engineers in the design of compact heat exchangers. The main objectives of this project were to: (1) automate aspects of heat exchanger design; (2) produce multiple successful designs quickly; and (3) optimize these designs based on specific constraints or criteria. Productivity improvements from use of this system have been as much as two orders of magnitude. The design of heat exchangers is a time-consuming, iterative process. For a given set of requirements a design engineer uses his knowledge and experience to pick an initial design point and then calculates (with a large Fortran program) the performance for that design. If performance data do not meet requirements, various design parameters are modified and performance is calculated again. An expert system now embodies design expertise (rules for design decisions) allowing automation of this iterative process and substantial time savings for engineers. In addition, optimizing successful designs is now practical, whereas in the past it was generally infeasible due to the amount of labor involved. A configuration system was also developed that serves as a `front- end' for the design system. The configuration system matches design requirements to existing products and offers suggestions for initial design points. Both were developed with the KAPPA knowledge based system shell. The two KAPPA programs and the Fortran program for numerical calculations are integrated within a Windows 3.1 environment on a 486 PC.

In order to create a process plan from a workpiece description, a human expert thinks in a special terminology with respect to the given workpiece. The steps of human thinking during the generation process of a process plan are following the principles of heuristic classification: First using feature recognition an abstraction process is realized yielding a high level (qualitative) description of the current workpiece in terms of features. To these features certain (more or less) abstract (partial) process plans -- the so-called skeletal plans -- are associated. In the refinement step these skeletal plans are merged together to one complete process plan. In this paper we present a set of domain-oriented higher level representation formalisms for features and skeletal plans suitable for the modeling of this approach. When an expert's (process planner's knowledge has been represented using these formalisms, the generation of a process plan can be achieved by heuristic classification. This is demonstrated in the CAPP- system PIM, which is currently implemented as a prototype.

An integrated knowledge based system is proposed to automate the design of laminated composite plates in an object-oriented programming environment. The system consists of several different domain-specific programs and commercial software packages integrated via a generic interfacing mechanism. A prototype system dealing with the preliminary design of a laminated plate is demonstrated in this design environment and several issues for the improvement of the proposed framework are discussed.

The turbine design optimization system described here automates the turbine preliminary design process and stimulates designer interactions through the use of knowledge engineering. The turbine design optimization problem is an np-complete problem and needs to be solved iteratively. Automation of the design process permits search over a much larger domain than is possible for the human designer. In addition it allows designers to look beyond the horizons of the present, limited design subtask so that they can work on new ideas and concepts, testing hypotheses by using the system to answer what-if questions. The optimization system allows the user to make tradeoffs between multiple design objectives.

The purpose of this document is to describe and forecast the use of FHDL in order to help construct the roadmap for future use of the output of the Learning System for Pilot Aiding (LSPA) LSPA VHSIC (Very High Speed Integrated Circuit) Hardware Description Language (VHDL) program. It is important to get an understanding of the realism of the current and projected use of VHDL in order to aid some of the decisions for the overall technology roadmap. This forecast will look at the projected development of commercial tools along with projected standards development in order to arrive at a somewhat pragmatic forecast.

The generic model-based diagnostic system (GMODS) can use VHSIC hardware description language (VHDL) design models of structure and behavior to diagnose faults within digital sequential circuits. To produce a diagnosis, GMODS makes assumptions about the diagnostic health of each circuit component, propagates values through the design model over multiple clock intervals, and compares predicted and observed output values to identify sets of assumptions that explain the observations. In this paper, we describe the overall GMODS approach and project results, with an emphasis on the GMODS modeling techniques and VHDL interface. We also examine remaining issues to be addressed before GMODS can be applied on real applications.

Model-based diagnosis (MBD) is a technique to locate faults in a system with the aid of a model of that system. The model describes the correct behavior of the system, and possibly also the behavior in case of a fault. In the field of model-based diagnosis, most attention has been given to the problem of reasoning: how to derive diagnoses, given a model. When applying MBD in practice, modeling appears to be a problem of equal magnitude. In this paper, we analyze the modeling process, and show how design information can be used in this process. We investigated the use of information in two standard languages for information interchange: EDIF and VHDL. We expect that the results from this research carry over to other design formats.

Our learning diagnostic skills (LDS) system compiles an efficient diagnostic model for each power supply circuit presented to it. The inputs are individual schematics and a shared general causal model of power-supply failures. Because the general model is reused for each power supply design, knowledge acquisition for a new power supply is limited to adding diagnostic schema not already covered by the general model and providing an annotated circuit schematic. We have used an existing technique, partial evaluation (PE), to produce efficient diagnosis of power supplies. The use of PE compensates for the computational costs caused by the expressiveness and generality of the shared knowledge representation we use and therefore eases further the knowledge acquisition bottleneck in expert system development. Using PE, our system takes general knowledge, written in a highly expressive language, and automatically compiles the complete knowledge base for an efficient expert system diagnostician for each specific device.

In the presented work, we combine structure-based models with functional representation in one common framework. The combined model explicitly represents the causal process descriptions (cpds) by which functions are achieved, and these cpds are used to guide simulation based on a set of simulation goals. We demonstrate on some examples how this functional approach of simulation can lead to savings in simulation time.

For simulations that are to enable human understanding of the simulated system, inspectable models are highly desirable. A model is inspectable to the extent that its observer can access and interpret each of its reasoning steps. Development of an inspectable model requires an architecture that represents explicitly some of the key types of relationships among domain objects. Although there are formalisms that address some of these relationships, none attempts a representation for a dynamic simulation that is both comprehensive and general. This paper defines an architecture that meets these requirements for well-defined, engineered systems. The architecture combines features from two formalisms, namely, discrete event simulation modeling, and functional representation. Besides representing generalization-specialization and multi-level part-whole composition in a dynamic world, we provide an explicit representation for causality and functionality. We set up a framework for developing well-integrated systems, and an architecture for the core components of a `shell.' We use a complex but sparse class structure that allows for composition of elementary units into structures of arbitrary complexity. Our architecture is event-driven, but uses a distributed timing mechanism. The scope of our research includes definition of the problem and the solution method. Implementation of a prototype to validate key aspects of the architecture is in progress. We have named the architecture `IDEA' for inspectable discrete event architecture.

Knowledge-based systems typically require extensive knowledge about the domain in which they are to operate, including knowledge about the objects and systems which exist within the domain, their properties, architectures, capabilities, and interactions. This is particularly the case for systems that require complex reasoning—e.g., systems that perform explanation, model-based and qualitative reasoning, multilevel and integrated reasoning, design/redesign, training and tutoring, and certain systems for knowledge acquisition and machine learning. Acquiring and representing knowledge at the breadth and depth required for these approaches is especially challenging in complex, real-world domains such as industrial and aerospace applications. On the other hand, it is commonplace in these domains for equipment to be well documented, both before and after manufacture, with detailed specifications about its functionality and performance characteristics. It will soon be the case that most of these equipment specifications will be written and developed as executable software simulations in hardware description languages such as the VHSIC Hardware Description Language (VHDL). VHDL was developed during the early 1980's as a standard, vendor independent description of hardware. With the growing complexity of microelectronics, it was clear that schematic representations would no longer be adequate for description and subsequent support. VHDL was standardized by the IEEE in 1987, thereby giving the industry a standard hardware description language. VHDL supports multiple levels of abstraction, but is most useful at describing the functional or behavioral aspect of hardware. It allows the designer to write a high level description of a piece of hardware. This description can then be used for simulation, analysis, and by a multitude of other tools that need to understand the structure and behavior of a specific piece of hardware. Clearly, it would be of great benefit for knowledge-based systems to obtain some of their prerequisite knowledge from such sources. As one prominent researcher in the area of explanation based learning speculated: "We foresee a future in which manufacturers of component equipment themselves provide descriptions, in some standard knowledgebased formalism, of the functionality of their product just as today they provide technical descriptions in a form understandable to [equipment] designers. As the manufactu,rer makes available refined versions ofinstalled equipment, the old knowledge-based description of the component is simply supplanted with the new. The knowledge engineer need only oversee incorporation of the new knowledge insuring that there are no negative interactions that harm overall system performance." 1 Realizing this vision of the future involves several technical challenges. One challenge is it to bridge the representational gap between the syntax of hardware design languages and Al systems. We do not see this as a significant technical hurdle because several studies have already demonstrated that this can be done. These investigations have used Al reasoning systems to reason about hardware models 2,3,4,5 or have done model-based reasoning using VHDL 6,7 Amore significant challenge involves bridging a gap in semantics. By this we mean going from reasoning at a relatively well-defined and self-contained level of hardware devices to planning and executing actions in the real world involving uncertainties associated with external agents and incomplete, uncertain, and incorrect information. All the previous studies we have cited principally reasoned about behaviors and functions of a device and its subcomponents, not about the function of the device and its subcomponents in the real world. Although one can envision modeling the whole world as a device in which any given device is a subcomponent, this has generally not been a tractable approach. It is this gap between modeling plans and their execution in the real world and modeling the internal behavior of devices in hardware design languages that is the focus of this paper.

This report describes an ongoing effort to apply the functional modeling (FM) approach to the representation of and reasoning about engineered artifacts. The application domain is the external active thermal control system (EATCS) of the FREEDOM space station. The intuitions behind FM are threefold. First, knowing the purposes of a device allows organization of the causal understanding of how a device works. Second, in FM, causality is represented in modular chunks which are indexed by the purposes of the device and its interrelated subsystems. Finally, the global behavior of a device in a given situation can be understood by composition of the relevant causal net fragments. These starting intuitions provide a framework for organizing calculations about a device and for performing a limited type of simulation with the organized ensemble.

We present a prototype human assistant system for space crew assessment and mission management. Our system is based on case episodes from American and Russian space missions and analog environments such as polar stations and undersea habitats. The general domain of small groups in isolated and confined environments represents a near ideal application area for case-based reasoning (CBR) -- there are few reliable rules to follow, and most domain knowledge is in the form of cases. We define the problem domain and outline a unique knowledge representation system driven by conflict and communication triggers. The prototype system is able to represent, index, and retrieve case studies of human performance. We index by social, behavioral, and environmental factors. We present the problem domain, our current implementation, our research approach for an operational system, and prototype performance and results.

Reasoning about physical systems in operation is a difficult task, and any attempt to automate the process must overcome the problems of modeling normal behavior, diagnosing faults, and predicting future behavior. This paper describes a prototypical case-based reasoner (CBR) that operates in the domain of in-flight fault diagnosis and prognosis of aviation subsystems, particularly jet engines. The reasoner operates on the observation that the ability of a CBR program to reason about physical systems can be significantly enhanced by the addition to the CBR program of a model of the physical system to describe the system's structural, functional, and causal behavior.

We have studied the retrieve-and-propose problem-solving method, a specialization of the general case-based reasoning method, in terms of its tasks in the context of fault recovery domains. We analyzed the case retrieval and learning tasks that are primarily used in the retrieve-and-propose method, decomposed them into appropriate subtasks, associated decisions for selecting each subtask, and implemented methods for accomplishing each task. We have implemented a system, called REPRO for retrieve and propose, that incorporates the results of this analysis and facilitates the selection of the appropriate algorithms for implementing a case- based expert system. We have used REPRO to develop the CABER case-based fault recovery system.

In this paper we describe an intelligent tutoring system (ITS) called HYDRIVE (hydraulics interactive video experience). This system is built using several novel approaches to intelligent tutoring. The underlying rationale for HYDRIVE is based on the results of a cognitive task analysis. The reasoning component of the system makes extensive use of a hierarchical knowledge representation. Reasoning within the system is accomplished using a logic-based approach and is linked to a highly interactive interface using multimedia. The knowledge representation contains information that drives the multimedia elements of the system, and the reasoning components select the appropriate information to assess student knowledge or guide the student at any particular moment. As this system will be deployed throughout the Air Force maintenance function, the implementation platform is the IBM PC.

This paper discusses a retrieval scheme for an information retrieval system in which the feedback from a number of users of the system about its performance (global feedback) is stored in the form of clusters called user-oriented clusters. The clusters are described by using the description of its constituent documents. The clusters and queries are represented as vectors and the measure of similarity between them is represented as the cosine of the angle between the two. The clusters are retrieved as per decreasing order of similarity with respect to a query. An important problem that arises in the context of cluster description is the significance of an index term assigned to documents. This problem, called term refinement problem, is formulated and solved. The experimental results of the proposed retrieval scheme are compared with those of the vector space model and the results obtained are encouraging.

This paper presents a logic programming language W-Prolog based on the idea of a network of worlds for representing and manipulating knowledge. While maintaining multiple theories within a single system the language provides a rich collection of theory relations for creating new theories. Built-in theory relations implement versions of set theoretic operations and various types of accessibility relations. A notable feature of the language is that it enables users to define their own theory relations. W-Prolog also allows users to define a network of theories where the number and the type of the "network links" depends on the results of some computations.

For various projects (satellites) one must schedule transmissions to receiving antennas on earth for a one week planning horizon. Periods of time in which any satellite is `in view' of any antenna are known in advance. The scheduling problem is formulated as an integer linear program. This formulation includes a large number of non-conflict constraints stating that an antenna must not receive data from two or more satellites simultaneously. There are also a smaller number of service level constraints specif)ed by project managers to assure appropriate levels of service. For example, service level constraints might specify for a particular project: a maximum allowable gap between the end of one transmission and the start of the next, a minimum total number of minutes of transmission during a week, a minimum number of transmissions on any day, etc. Lagrangian Relaxation allows service level constraints to be relaxed (temporarily ignored). These constraints are replaced by economic penalties for not satisfying them. The resulting modified scheduling problem is easily solved. The paper concentrates on formulation, solution by Lagrangian Relaxation, and performance on an example using real data for a week in 1996.

This system is a practical application of intelligent reasoning about the planning and sequencing of inspection tasks performed by a coordinate measuring machine (CMM). This research is part of an Air Force supported effort to develop a feature-based concurrent engineering system using an object-oriented development platform. Manipulation of design, manufacturing, and inspection features (in this system) is unique in that features are transformed into domain specific objects rather than degraded into elementary geometry. The object-oriented platform provides a means for transformation through built-in qualities such as inheritance, tree-search, and a cohesive part/sub-part organization. Inspection features represent not only geometry, but references to a world coordinate system, proper probe approach, and preferred evaluation method. Reasoning through inspection rules forms a single data object which can then be transformed into CMM executable code.