Scale-space representation is a topic of active research in computer vision. Most of the work so far has concentrated on image reconstruction from the scale-space representation. In this paper we discuss the use of scale- space representation for object detection. We have proposed a model based approach and developed an algorithm to implement it. Channel integration is the heart of the algorithm and there are a number of unresolved issues in it. Object detection is possible only if the objects of interest are different from the noise and clutter in certain features. We have used two different images, one with good signal to noise ratio and the other with poor signal to noise ratio In the first image the distinguishing feature of the object is its signal strength and in the second image it is its size. Accordingly we have studied two approaches to the channel integration : (i) based on the contrast value and (ii) based on edge focusing and splitting. The results of both approaches are presented and discussed.

Accurate detection of unique objects with minimal false alarm rates is an important requirement for most reconnaissance tasks. This paper presents a methodology for developing an object detection system which examines the spectral, spatial and topographic features in a step-wise manner. The algorithms developed are tested using high resolution thermal infrared images. Multiresolution analysis to improve the performance this approach is also discussed. Results of these experiments show a definite promise for the approach.

Model-based scene interpretation systems can use non-monotonic reasoning to resolve many of the inherent ambiguities and uncertainties present in real world image data. Model-based systems perform object recognition by efficiently matching features extracted from image data to corresponding features in known object models. This matching process is based on the accuracy of the extracted features. It is typically the case, however, that these features are themselves uncertain. This uncertainty is present because the image processing algorithms used for feature extraction do not consider global context, are noise sensitive, and use scene dependent parameters. Non-monotonic reasoning can resolve these uncertainties by identifying global inconsistencies and providing the means to recover from them. It does this by retracting invalid deductions based on the underlying causes of inconsistencies as they arise during the model matching process. A non-monotonic system can also predict the existence of additional features to complete a partial match.

In the last few years, knowledge-based systems devoted to image understanding have proved very interesting applications of artificial intelligence to real-life domains. Purpose of this paper is to present the control strategies and knowledge representation for supporting backtracking techniques for error handling in this kind of system. Since neither low-level image processing nor high-level interpretation can be completely free from errors, the capability of detecting and correcting errors is of main importance to obtain high performances and reliability. Some examples of errors at both levels are considered and the mechanism to solve them is proposed. Experimental results in a medical application are presented and discussed.

The important shortcomings of existing computer vision systems are addressed in this paper. A coupled systems approach towards designing computer vision systems is proposed as a means of overcoming these shortcomings. An object-oriented framework is shown to be a natural way of implementing coupled systems. Two important issues in the design of object-oriented systems are considered : (i) indexing in an object-oriented hierarchy and (ii) parallel implementation of constraint propagation techniques. The problem of three-dimensional object recognition from range images in multiple-object scenes with partial occlusion is chosen as a candidate problem. Experimental results are cited and future directions are proposed.

An expert system is developed to aid in the selection of bakeout time and temperature during the manufacturing process of a heatpipe. Simplicity of this system allows it to be written in a low level programming language, instead of using a high level expert system shell. The expert system involves an interactive process using a forward chaining inference. The surface outgassing rate and the residual gas requirement are inherently uncertain. The uncertainty associated with the outgassing rate is represented graphically, and an appropriate uncertainty factor is used. The threshold of permitted residual gas is determined by the knowledge-based system. The expert system shows pass or failure at each inference. A summary graphic is generated showing the domain of success.

TEMPIC is a diagnostic expert system capable of providing process and device engineers with real time assistance in determining the origin of CMOS fabrication faults. The increased complexity of 1.25 and submicron CMOS processes presents the device engineer with large statistical data bases in which parametric relationships and dependencies must be analyzed and correlated. Corrective action is then initiated to remedy the identified process fault. The TEMPIC expert system functions as an advisor to the device engineer. Numerical data is gathered and is assigned qualitative descriptors with respect to the deviation of the experimental data from the process specification. Three related but independent data bases are used: Process control data, on-chip critical dimension data, and parametric electrical data. In this paper we discuss the knowledge engineering methodology used in developing the rules for the system and the way in which the system diagnostic architecture evolved from those sessions. The method by which the expert system determines candidate faults is presented. In cases where several possible faults are identified an interactive dialogue is initiated.

The Nuclear Engineering Department of the University of Tennessee is developing a prototype expert system to advise the operations personnel of a Nuclear power facility in the event of a severe accident. The development of the prototype, called SAIM (Severe Accident Information Advisor) is in a lisp environment using the expert system shell PC Plus by Texas Instruments. This is a rule based system using confidence factors and fuzzy logic to account for uncertainties. Verification of the system will be based on results of Severe Accident research and data from the Three Mile Island Unit 2 accident. The SAIM prototype is being developed to achieve three goals. It is designed to 1) monitor a Pressurized Water Reactor (PWR) facility for any indications of a severe accident (SA), 2) identify the mechanisms causing the SA, and 3) monitor the progression of the accident and alert operations personnel to any change in the severity of the accident. This paper includes a brief discussion of the Three Mile Island accident scenario which serves as background for developing the SAIM prototype. This paper also addresses the benefits of utilizing an expert system in this domain and then focuses on the design strategy used to accomplish the desired goals.

The VLSI design process consists of many highly specialized tasks. Algorithmic, compute-intensive and mundane tasks which used to be performed manually, have been automated by traditional VLSI CAD tools. These tools have automated many aspects of VLSI design synthesis, analysis, optimization and verification. However, the successful and efficient utilization of these tools has proved to be very knowledge intensive requiring the interaction and guidance of domain experts. In recent years many expert systems for VLSI design have been reported but these stand-alone expert systems have to be integrated with traditional CAD tools to be able to provide automated decision-making, judgment-based opportunity ranking and tighter data source integration. Furthermore, an integrated and distributed knowledge-base is essential for rapid prototyping of expert design assistants, design techniques and optimization heuristics. We report an experimental VLSI design environment based on a central object-oriented model-base. The object-oriented design kernel is capable of accommodating traditional CAD tools as well as knowledge-based tools.

A versatile model to diagnose the performance failures of a plasma arc welding machine is presented in this paper. The understanding of the functional structure of the machine under consideration plays a vital role in the use of an expert system as a tool. The torch is the focal point of action in such a welding machine. Therefore, the fundamental analysis is based on the torch with the rest of the functions built around it. We have introduced a dynamic learning concept based on the recurrence of problems. The learning model includes a facility index, a function based on the complexity of the troubleshooting associated with the machine under consideration. The increase in frequency of problem events can supersede the facility index. The probability parameters at each node of the structure is computed and dynamically updated at the end of each diagnostic operation. The system is designed to be used by a maintenance technician and tailored for an expert to interact and alter the probability parameters in the logical reasoning domain. The model can be implemented either on new machines without any historical background or on old machines with a troubleshooting history.

Range images incorporate 3-D surface coordinates of a scene and are well suited for a variety of vision tasks. For tasks, such as 3-D object recognition, a representation of the object(s) present in the image is derived. This representation is then matched with the stored models to determine the object identity. Surface based representation is the most widely used technique for range images. Surface based representation is generated by segmenting the object into a number of surfaces. The segmented surfaces are then classified into a number of primitives and the relations between these surfaces are defined. In this paper a number of techniques for the classification of range images of industrial parts are presented. Surface patches are classified into three primitives: planar, convex or concave. Four tests are presented two planarity tests, and two for classifying curved surface patches into convex, or concave. The first planarity test we is a variation of the Wald-Wolfowitz runs test. The second planarity test is based on the connected components formed after fitting a plane to surface patches. The nonplanar regions are then classified into convex or concave using multi-scale residual computation, and a goodness of fit test. The performance of the classification tests on a number of industrial parts range images is presented.

The Connection Machine has been demonstrated to be an efficient and fast computational engine for the solution of most vision problems. In this paper a system based on the Connection Machine is developed which is capable of computing the optic flow from image sequences at near real time, allowing the computation of one velocity field at a rate of 20 frames per second. Qualitative estimation of image motion allow the measurement of the "time to crash” of the objects in the scene; only local operations, which can be executed in parallel, are required. The system is shown to be robust with respect to a variety of noisy real image sequences; the optic flow can be computed with high accuracy, simply tuning the number of bits used for the computations and never changing much the computational speed. Several experiments performed on image sequences from real scenes are presented. An analysis of the performance of the system is carryed out together with a comparison with implementations of the same algorithm on other computing systems.

This paper describes a stereo-based multi-camera system for complete 3-D information extraction and surface reconstruction of objects in a robot workspace. The system consists of N number of cameras arranged in an N/2 number of periodic stereo pair structure. The common area of a camera pair and the number of cameras are determined based on a linear camera model and a calibration procedure that reguires only three known world points. The construction of the structural description is performed in two stages: (i) the 3-D data from different perspectives are inferred independently using a periodic stereo structure, and (ii) the extracted information from neighboring camera pairs are integrated to reconstruct the complete surface of the object.

In this paper, an octree geometric modeler is presented. It builds solid models on the basis of geometrical constraints; in fact, the system contains a set of routines which compute the distance from points, straight_lines and lines and define the part of the space cut by a plane or a surface. Besides, the system allows the combination of constraints in a boolean condition for building more complex solids. This system offers an object-oriented shell which allows the user to take advantages of the declarative and procedural paradigms of object-oriented languages for solid modeling. A solid is represent by a tree of objects (a composite object) where the root object contains the properties characterizing the full solid and the leaf objects contain the description of its elementary parts. The octree model is built from this object-oriented representation through "methods".

A flexible interface to an expert system shell called CLIPS is described in this paper. The advantages of such an interface are that it provides assistance to the knowledge engineer in all phases of the life cycle of expert system development. In other words, it facilitates the task of knowledge acquisition, knowledge refinement, knowledgebase(s) addition/modification, knowledgebase maintenance, and information management relating to specific expert system projects.

The acquisition of expert knowledge is a laborious task that could benefit from techniques which simplify and shorten the process without degrading the results. The expert domain under examination is a pilot's threat response, which includes skilled motor responses as well as expert knowledge. Standard knowledge acquisition techniques can be accelerated in several ways, including improvements in the expert interviewing and knowledge encoding processes, and in using cases of expert performance in addition to the experts' interpretation of the cases. Either approach to improving the acquisition process has costs associated with it. To maximize the usefulness of an interview knowledge engineers should exploit the time available before and after the interview to carefully prepare the questions and delicately analyze the responses. To extract rules or response patterns from cases, requires a learning algorithm (i.e. a Machine Learning or Neural Network (NN) system) or a person who can generalize from the observed behaviors. In order to obtain cases with as much recorded information as possible, we are using responses made by pilots "flying" in a full mission simulator. These responses can then be used to train NNs. A benefit of this second approach, in the acquisition of a pilot's tactical responses, is that it eliminates the difficult process of trying to recreate long forgotten reasons for making sensory classifications and selecting sensory guided behavior. There are also potential costs associated with this second approach. The computational cost of inferring rules from cases is generally high, and a large number of examples may be required to accurately deduce even a simple rule-base. One advantage to learning responses with a NN is that the response time of the NN system can be very fast. We are simultaneously pursuing both approaches for improving the acquisition of pilot responses. These approaches may be complementary to each other, they may be used to verify each other (to measure each one’s effectiveness), or they may be totally separate from one another, each providing valued knowledge gleaned from domain experts. Over the next year we will be comparing the cost and performance of Expert and Learning Systems.

One of the most significant problems currently facing the United States is the loss of scientific expertise. Many of the pioneers in such technical fields as flight medicine, ground operations, space propulsion, and safety began their careers during or shortly after WWII and are now approaching retirement age.1 While expert systems are recognized as a good vehicle for capturing technical knowledge, expert system developers often have difficulty acquiring the knowledge needed for systems. Because experts in most domains are rare and their time is limited, knowledge acquisition is a significant obstacle to system development. In many cases, however, the baseline knowledge for a system has already been captured in technical manuals written by the experts themselves. This paper describes an innovative system for Explosive Hazards Classification that is being developed for the Safety and Environmental Protection Subcommittee of JANNAF, the Joint Army-Navy-NASA-Air Force Propulsion Committee. The system, known as the Explosive Hazards Classification Expert System, is unique because of the knowledge acquisition strategy being used during its development and because of its integration of expert system and hypertext techniques.

Today, Software Engineering for classic software is an integral part of the daily life of the software programmer. So it's hardly surprising that same process may be undertaken for the Knowledge-Based Systems, to guarantee the quality and validity of these systems. We are concerned with the validation of the Knowledge Base by using testing methods. We propose a method for building test samples by compiling the Rule Base in a peculiar graph : the Precedence Graph. Also, this allows us to transpose some classic quality criteria to Knowledge Bases. We have implemented the described method : SYCOJET is an automatic sets of test builder for Knowledge Bases.

Qualitative reasoning is a collection of methods for building and simulating models of physical systems in spite of incomplete knowledge. The QSIM representation and simulation algorithm apply to models in the form of qualitative differential equations, which allow incompletely known quantity spaces and functional relations, and isolated behavioral discontinuities, to be described qualitatively. In the past few years, we have extended the early “limit analysis” methods for qualitative simulation to more sophisticated methods capable of simulating realistic systems. • The qualitative behavior description can be augmented and refined with incomplete quantitative information, producing more detailed predictions and detecting and excluding behaviors that are qualitatively plausible but quantitatively impossible. • The phase space representation, and the mathematical theory of dynamical systems, provides a more global perspective and more sophisticated filters on the set of qualitative predictions. • Complex systems must be hierarchically decomposed into simpler ones. In a time-scale abstraction hierarchy, fast mechanisms view slower mechanisms as constant, while slow mechanisms view faster ones as instantaneous (e.g. as functional relations). • Model-building methods based on device-centered and process-centered ontologies have been implemented as compilers which build qualitative differential equations for QSIM to simulate. • Applications of qualitative simulation are under development for monitoring and diagnosis of dynamic processes; and for recognizing and expressing teleological relationships in design.

We are investigating the feasibility of functional description as a knowledge representation for recognition of 3-D objects. This description can be used to recognize classes and identify subclasses of known categories of objects even if the specific object has never been encountered previously. Having conceptual models therefore allows the system the flexibility to learn new exemplars of a known class of object. The major goal of this work is to develop a knowledge representation which defines a class of objects in terms of its function. The system will interpret the possible functionality of an object by reasoning about its 3-D form. By using this more abstract conceptual representation instead of a concrete geometric representation, we feel we can reduce the potential search space involved in the recognition process and broaden the recognition capabilities of the vision system.

Recognition via alignment is a method for recognizing the general class of rigid objects, which includes vehicles, known terrain, and buildings. A candidate alignment transformation is computed from a minimal set of three corresponding points from model to image, and the transformation and model are accepted only after an expensive verification step. Methods are given here which can dramatically reduce the amount of computation required for recognition by alignment. First, the use of aspects is proposed to cut down on the combinatorics of point correspondence. Secondly, two practical constraints on orientation and size are shown to eliminate many alignment candidates before the expensive verification step. Simulations are reported which show the usefulness of the proposed methods in the context of automatic target recognition.

The relational pyramid representation is a hierarchical relational description of an object that can be used in recognition and pose estimation. In this representation, primitive features appear at the bottom of the pyramid, relations among primitives appear at level one, and, in general, relations among lower-level structures appear at the levels above the levels in which these structures were defined. We have constructed a pose estimation system that uses the relational pyramid representation for the view classes of a three-dimensional object and for the description of the unknown view of an object extracted from an image. A previously described system uses summary information to rank and select view classes to which the unknown view is compared. This paper describes a best-first search procedure to find correspondences between the selected view class pyramid and the image pyramid.

This paper describes research being performed in the area of visual surveillance. In the context of a project we call RAMBO - for Robot Acting on Moving Bodies - we are developing algorithms for object pose estimation, object motion estimation, and visual planning. Many of these algorithms are massively parallel algorithms that have been implemented on a Connection Machine II. We describe an overall system architecture for the types of visual surveillance tasks that RAMBO is to perform,and then provide an overview of our research in vision and planning.

In this note we identify some similarities and differences between two clustering models, viz., the fuzzy c-means (FCM) and Kohonen self-organizing (KSO) feature map approaches. This leads us to suggest that there is an important unknown relationship between the two methodologies. Consequently, we propose several avenues of research which, if successfully resolved, will strengthen both the FCM and Kohonen models and their utility for applications in clustering and classifier design.

In this note we describe and compare two fuzzy clustering algorithms based on optimizing penalty functions of relational data. More specifically, the AP algorithm of Windham is contrasted to the relational fuzzy c-means approach through a numerical example on a small artificial data set defined by Windham. Our results indicate that while the two algorithms seem to cluster objects using very different mathematical criteria, the numerical results can be quite similar. However, a second numerical example using a slightly distorted version of Windham's data seems to exhibit real differences between clusterings obtained by the two approaches. We discuss possible reasons for this, and pose some questions for further research.

During the past few years, artificial neural networks have been applied to problems such as pattern matching, associative memory recall, and optimization problems. A property common to all the network structures which have been proposed and studied is global interconnectivity among the neural processing nodes. While global interconnectivity presents few problems for implementing simulations of networks, it is a major factor which prohibits implementation using VLSI and or optical technology. In this paper, we present the results of a study which compares the performance of globally interlayer connected multi-layer neural networks with that of networks which employ local connections. The locally connected neural network contains multiple hidden layers and each neural processing node in a given layer connects to at most its three nearest neighbor processing nodes in the higher layer. The advantages of a locally connected network are reduced interconnection complexity, reduced I/O requirements for each neural processor node, and faster processing at each neural processing node. The locally connected and globally connected networks are compared with respect to training iterations, number of neural processor nodes needed, number of hidden layers needed, and error rate performance for a number of different problems.

This paper describes a hybrid neural network and rule-based pattern recognition system architecture which is capable of self-modification or learning. The central research issue to be addressed for a multiclassifier hybrid system is whether such a system can perform better than the two classifiers taken by themselves. The hybrid system employs a hierarchical architecture, and it can be interfaced with one or more sensors. Feature extraction routines operating on raw sensor data produce feature vectors which serve as inputs to neural network classifiers at the next level in the hierarchy. These low-level neural networks are trained to provide further discrimination of the sensor data. A set of feature vectors is formed from a concatenation of information from the feature extraction routines and the low-level neural network results. A rule-based classifier system uses this feature set to determine if certain expected environmental states, conditions, or objects are present in the sensors’ current data stream. The rule-based system has been given an a priori set of models of the expected environmental states, conditions, or objects which it is expected to identify. These models are represented as a directed graph of features vectors. The rule-based system forms many candidate directed graphs of various combinations of incoming features vectors, and it uses a suitably chosen metric to measure the similarity between candidate and model directed graphs. The rule-based system must decide if there is a match between one of the candidate graphs and a model graph. If a match is found, then the rule-based system invokes a routine to create and train a new high-level neural network from the appropriate feature vector data to recognize when this model state is present in future sensor data streams. A different high-level neural network is created for each model state identified by the rule-based system. Both the high-level neural networks and the rule-based system receive all subsequent feature vector data streams, and each of these classifiers provides an estimate of whether a certain model states exist in the data. If the high-level neural network finds that a model state is present and the rule-based system does not, then the rule-based system will alter its model of the state - the rule-based system learns from the high-level neural net. If the high-level neural network does not find that a model state is present and the rule-based system does, then the rule-based system will invoke a neural network retraining routine - the high-level neural network learns from the rule-base. A second research issue is whether the self-modification of models can be controlled, such that models are only altered to reflect new information and not erroneous information from noisy sensors.

The problem of automatically finding the optimal robot assembly sequence for a set of n parts that construct a mechanical object is presented. Generally, to assemble a mechanical object, the assembly operation involves precedence relation of jointing the parts; that is, the order of attaching pats together crucially determines whether the desired object is able to be constructed from the parts. The precedence relationship of assembling the object results from the geometric constraint of parts structure. A feasible assembly sequence is the sequence satisfying these geometric constraints to be able to construct the desired object. Thus, geometric constraints dominate generation of all the feasible assembly sequences and play an important role in planning the optimal one. The problem of obtaining all the feasible assembly sequences can be formulated as a constrained traveling salesman problem (CTSP). The proposed approach will show that all the feasible assembly sequences can be generated by transforming the geometric constraints of parts to the pattern-matching operation based on the concept of CTSP. The optimal assembly sequence can then be obtained from the set of generated feasible assembly sequences. A novel method proposed here is to obtain the optimal assembly sequence while in generating all the feasible assembly sequences. Two approaches, which are a traditional search method and an artificial neural network computational scheme, in obtaining the optimal sequence will be discussed. For the traditional search method, the set of constraints describing the geometric relationship among parts are properly transformed into the matching problem. While for the neural computation, these geometric constraints are transformed into the elements of the connection matrix specifying the connection strength among neurons. The designed algorithm can accommodate various constraints and applications. Detailed algorithms and analysis, examples and experiments will be presented.

Two major challenges exist for the development of dynamic control systems: first, the control system must be resourceful enough to provide problem-solving capabilities in unforeseen circumstances; second, it must be rapid enough to respond to dynamic environments. Most conventional control systems do not have the ability to “step back” and problem-solve, especially in environments with incomplete and uncertain models and data. Orthogonally, commercially available AI systems usually do not respond at the rates required to support “real-time” control. Hence, control systems are not available that respond to complex dynamic environments within appropriate time constraints. This paper describes work on an Al-based control system designed to address these challenges. A prototype system has been used, in a simulated environment, to control the robotic welding of aerospace components. This Al-based control system has demonstrated the ability to flexibly control a complex process within required time constraints by incorporating higher level reasoning and the ability to deal with uncertainty. Further work is in progress to expand the system’s problem-solving capabilities.

For a number of years Nottingham Polytechnic has been investigating the use of stereoscopic vision in robotic applications. The aim of the current project is to produce a robotic system which can locate an object in three dimensional space, move the arm to the correct position and then pick up the object without human intervention. The technique uses a pair of television cameras configured to give a stereoscopic view of the working envelope of the robot manipulator. A prototype vision guided robot manipulator control system has been produced. The system uses photogrammetric calibration procedures which can account for unknown camera position and/or orientation as well as the major components of lens distortion. The calibration mechanism also performs the eye- hand-coordination function. This prototype uses a stereoscopic camera arrangement to provide three dimensional position information. The stereo-correspondence problem is solved using a combination of structured light and dedicated electronic hardware. The result of the work is a prototype manipulator control system which uses vision to close the control loop. The overall effect is a robot arm which moves towards an object, correcting its position as it moves. This is similar in concept to the way human beings approach the problem of grasping an object.

This paper describes ongoing research into intelligent robot systems for application to manufacturing operations where short-term workplace or workpiece variations are unpredictable, are unavoidable or are desirable. The system used consists of a gantry robot which is controlled by a modular expert programming system implemented in Prolog. The expert system consists of three basic software modules: a design module, a sensor module and a motion module. The main advantage of this modular approach is that the modules can be easily modified to suit differing applications, in this case building timber frames for house walls and trimming operations on fish fillets. The rules-based approach has advantages when representing complex workplace and workpiece variations in the system.

All activities in an organisation require or produce information. Therefore, a document is not only the main information carrier but also the central aid for the integration of office functions /1/. The office of the future will be characterized by new fundamental tendencies which lie not only in a more comprehensive possibility for information interchange but also in an altered processing of the information /3/.

The Designer Fabricator Interpreter (DFI) is a knowledge-based distributed problem-solving architecture which models participants of processes as computerized agents. In the DFI system, the agents work cooperatively on a problem, each reasoning from its own specific viewpoint. The goal is to coordinate the agents’ problem-solving actions, utilizing both unique and shared agent knowledge, in a way that produces a better solution than if each agent worked alone without any knowledge of another agent. As an application, the DFI system attempts to address the lack of interaction among structural designers, fabricators and erectors in designing connections of structural members in buildings. During the connection evaluation process, agents reason from their viewpoints and propose alternative connections for consideration. This process may require agents to negotiate among themselves when they have differing views. If they cannot resolve their problems, an arbitrator agent is enlisted to help the conflicting agents reach an agreement.

The field of Artificial intelligence and especially the design of Knowledge bases is still experimental. Indeed there is no methodology for building knowledge bases. This paper is devoted to such an application, in which the inference engine is based on a pure object formalism (SHIRKA). Modeling in biology is not the easiest area to consider for the building of an expert system for assistance in modeling, see [Lebreton 82]. Our aim is to develop differents tools(methodological, graphical) taking in consideration the cognitive needs of the user during the modeling process. This paper show how a modular architecture of a knowledge base can assist during the mathematical modeling process. The system is composed by two module : The knowledge module and the assistance module. Both of them take into account the user point of view. This approach provides a framework for guiding the user during the modeling process.

In this paper, we propose a modified predicate completion scheme called the Partial Predicate Completion scheme. It is more general than the delimited predicate completion scheme. We also present a scheme for generalization that views the necessary properties as also sufficient. As a consequence, the extensions corresponding to the sufficient predicates are maximized. We also introduce the notion of maximal models that forms the basis for the generalization process.

In this paper we introduce the concept of a new knowledge base component - the Conceptual Object Manager - which manages execution model semantics related to application objects in a knowledge based way. Thus, applications can reuse persistent information independently of their individual paradigm commitment. The realization of this work is an important part of the European ESPRIT Project 2443 - STRETCH (Extensible KBMS for Large Knowledge Based Applications)1 which is located at the confluence between Data Base Technology and Artificial Intelligence. This project will design and prototype a unique KBMS for applications from the object-oriented and the rule-based paradigm, extend the KBMS by a paradigm semantics management component and include a high performance physical storage system.

In this paper, we present a new approach to solve the mobile robot path planning problem with the consideration of the adaptability to task environmental changes due to unexpected obstacles. In order to accommodate these changes, newly discovered obstacles must be represented and included to update obstacle information. We propose a problem representation method to model the path planning problem. In this method, spatial knowledge described in terms of visibility, interference, and target obstacle is used to model the solution process. The knowledge inference process is based on traversability vectors, a mechanism to analyze spatial relation between geometric objects. We assume that an obstacle can be represented by a set of half-planes. Coefficients of the half-planes are stored as the basic world description. Changes on the obstacles can be accommodated by updating the stored coefficients. Thus, the planning system can always utilize the most recently updated obstacle information to plan for the path. This planning procedure is capable of generating the shortest path efficiently. We use a simulation example to show the capability of the proposed work.

The problem of determining an obstacle-free path for an autonomous mobile robot in two dimensions is examined. In this paper we explore the fundamentals necessary to construct a free space graph representation suitable for the problem by processing an input image of the environment in a scanline fashion and breaking the graph construction process into subprocesses which could be pipelined. Our methods describe how obstacles in the image are processed to yield a form more suitable for computation and how these processed pseudo obstacles are used to detect prime convex regions (PCRs) and maximal overlap regions (MOvs) formed by them. We also present experimental results of free space graphs constructed using these ideas.

Weighted region problem is a generalization of the obstacle avoidance problem. By defining a midi pie-valued index, terrain patches can be distinguished on the basis of their traversability. This paper generalizes the weighted region problem by defining a probability distribution over the traversability indices hence reflecting one's uncertainty as to the true terrain condition. Path planning under uncertain traversability requires a proper framework for decision making. This paper proposes a formal approach to this problem using elements of decision analysis and states- of-the-world paradigm. The uncertainty over the traversability index, path length and planners preferences defined over the consequence space are all encapsulated into a single decision making step.

This paper describes a collision detection and path planning algorithm in 3D time-varying environment using octree data structure. The problem is decomposed into two operation steps. First, all the moving obstacles are removed from the environment so that a collision- free path is planned in the 3D stationary environment. Second, all the moving obstacles are returned to the workspace and the 3D volume swept by their motion is represented in the form of an octree. In case of a collision, the colliding obstacle is placed at the collision point as a new stationary pseudo-obstacle and a new path is planned from the last to the final position of the robot.

The robot path planning problem involves finding an acceptable path from the current state to the destination state by defining an obstacle-free path. In the literature, many path planning algorithms which are based on local or global minimization techniques have been discussed. These algorithms assume that the configuration of the work environment is known precisely. However, in reality, a precise description and location of obstacles might be difficult to acquire, represent and incorporate into a planning methodology. Even if a precise description of the work environment is desirable, such a description might not be obtainable because of insufficient knowledge of the environment. Also, noise in the measuring or sensing devices used would contribute to the imprecision in the description. Thus, the path planning problem should take into account an imprecise or "fuzzy” environment. An approach to treat an imprecisely described environment is presented in this paper. The proposed approach models every object in the work environment as a fuzzy obstacle. A 2-dimensional fuzzy obstacle is approximated as a convex polygon or as a circle. The lack of precision in defining the boundary of an obstacle is depicted by a membership function that indicates a degree to which a point in the work-space belongs to the obstacle. The uncertainty in the location of the obstacle is incorporated in the algorithm by assigning a fuzzy weight to the obstacle. A high value of the weight implies more uncertainty in the description and vice versa. In fuzzy goal programing formulation, a decision function as a fuzzy set is constructed which represents an aggregate of the goals of the problem. A path planning algorithm which uses local gradient information of the decision function is presented. Three examples of two-dimensional configuration are given to illustrate the fuzzy goal programming approach.

This paper discusses the design and implementation of PLAYMAKER: a knowledge base system for characterizing hydrocarbon plays. PLAYMAKER is a component of XX (eXpert eXplorer), a workstation-based tool that aids exploration geologists in a number of different tasks: sediment and carbonates simulation, play and field characterization, retrieval and storage of information in a geological database, comparison of play or field under study with other fields in the database, and report generation. PLAYMAKER is implemented using MIDST (Mixed Inferencing Dempster Shafer Tool), a rule-based expert system shell that incorporates mixed-iniative reasoning and inexact reasoning based on the Dempster-Shafer evidence combination scheme. This paper discusses the effectiveness of a two-level knowledge base structure adopted for the design and implementation of PLAYMAKER.

The objective of the automatic nesting problem is to find an arrangement for cutting irregularly shaped pieces that efficiently and quickly utilizes an available resource. The available resource, in this case, is highly irregular with not only irregular boundaries but also defective areas. In the solution of this problem, three subproblems must be considered: irregular resource/piece representation, search/match methods and localization of the search space. We propose an object-oriented representational scheme which describes pieces and resources in multiple ways. This object-oriented representational scheme can directly depict physical objects and mental concepts in a coherent manner, making it much easier to embed an expert’s knowledge into a system. We also present a novel hybrid search algorithm, an abstract heuristic search in combination with a best-first search using limited backtracking. A new way of localizing the search space called recursive look ahead is also introduced. This technique is a domain-dependent approach that sub-divides the world based on the locations of defects. This recursive look ahead procedure is a novel variant of the sub-goal technique. Several other inference procedures, such as intersection and overlap detection, try-to-fit procedures are also proposed. This system has been developed and the preliminary result is satisfactory. The testing has been performed by comparing the system against a human expert. The average yield difference has been within five percent.

In the development of PC-based expert systems for "niche" applications, a conflict exists between maximizing the value delivered to the customer and minimizing the development cost. Good expert systems must have an effective human-machine interface, be highly integrated within their operating environment, and have user credibility. Considerable engineering effort is required to provide this functionality on a PC within cost and schedule constraints. We illustrate our approach to resolving the value vs. cost dilemma by describing our development of a system called LESTER. Results achieved via the implementation of LESTER are discussed, as well as the areas in which we encountered development difficulties. From our experiences, we argue that the need exists for an implementation environment that simplifies the building of expert systems and thus lowers their cost. Tools for efficient prototyping, knowledge acquisition and code development are conceptualized. These tools address some of the more troublesome aspects of expert system development. Creating the right tools for an environment is an evolutionary process, one that will allow developers (and their customers) to ultimately achieve a high return from their investment.

A Control Laws Expert Assistant for Rotorcraft (CLEAR) which will assist flight control engineers design a specific set of flight control systems is described. This interactive knowledge-based system, when complete, will analyze rotorcraft and design the compensator necessary to achieve the system specifications. This paper discusses the system architecture, describes the knowledge-base modules developed or are being developed, and presents an example of how the present system functions.

An expert system for the configuration of special machines is described. The static domain knowledge is represented in the system by objects that are hierarchically organized in a part-of hierarchy that forms a model of the machine, and in several is-a hierarchies for the different types of machines and of its parts. The configuration knowledge consists of functions and relations between parameters representing mechanical laws and of heuristic rules. Both are represented as constraints that are attached to the objects in the model. The configuration process is a stepwise refinement of the model until all parameter values are determined. It is performed by direct evaluation of the constraints and is supported by a dependency controller. The search is guided by control strategies, the most important one is preferring standard solutions. The configuration system includes a simple diagnosis component and a special component for the feedback from diagnosis to configuration.

A method for symmetry detection of 2-D figures is presented. This approach uses eigenvector fitting to find the approximate directions of the axes of symmetry. A normalized error of distance-difference is used as the validity measure of candidate lines for symmetry axes. The complexity of the search space of lines of symmetry is a constant, while the complexity of the algorithm is O(n) where n is the number of pixels on the boundary of the figure.

In this paper, we develop a technique which applies the Green’s theorem to locate edges in images. Our method implements the traditional Laplacian of Gaussian operator over different resolution scales for edge detection. However, only the first derivatives of an image function—not the second-derivative Laplacian operators—are computed in our method. Gaussian kernels of different sizes are convolved with a raw image to generate smoothed images at different resolution scales. The first derivatives are calculated from the smoothed images. Equi-first- derivative pixel pairs in both the x and y directions are located. They are then grouped into closed contours in the derivative maps. The Green’s theorem states that if the Laplacian operator produces a smooth, continuous function, zero-crossings (edge points) will be enclosed in these equi-first-derivative contours. Implementation results show that our technique is capable of locating edges at different scales.

A cross-correlational algorithm for determining image correspondences is described. As is typical for such algorithms, correct determination of correspondences at a fairly high level of accuracy is relatively easy to achieve. The problem addressed in the algorithm is the development of consistency checking mechanisms that enable the detection and correction of the remaining relatively small number of incorrect match and non-match determinations. The image matching algorithm and its proposed consistency checking mechanism differ from more traditional relaxation-based methods in two ways: 1. the algorithm takes a more "committed" approach in terms of actively making discrete inferences about match and non-match hypotheses based on relatively local support, even at the earliest stages of the algorithm, and 2. the consistency checking mechanisms permit the detection and isolation of sets of match and non-match hypotheses that are inconsistent with neighboring hypotheses. Within the context of graph matching - with nodes being detected image features and edges the spatial relationship between features - the algorithm "commits" itself by creating "virtual" nodes, which function as hypotheses about where missing features should appear. The criterion for consistency embodies the notion that the result of the comparison process should consist of match information which represents the construction of the union out of the initial two graphs being compared - in contrast to the continuity criterion embodied in relaxation methods. The comparison algorithm should be of interest in areas of application where image differences are reconcilable, e.g., when missing features on one image may not have been detected correctly initially, but might be found via more focused processing. Model-based matching may be a candidate application. Preliminary results are presented on the application of this consistency methodology to the comparison of biological images of two-dimensional electrophoretic gels used in the detection of mutations.

A polynomial approach to the representation of binary and gray images for machine vision is introduced. Most of the standard image processing can be done by the template polynomial operations. However, we also develop some operators which rely on the intrinsic properties of polynomials and can be done at a considerable advantage using the polynomial representation of images. In particular, we develop an algorithm in parallel processing by template decomposition which uses the separability property of the template polynomial. There has been considerable interest in the past to develop a convenient algebraic environment to process digitized images. In this approach, each black-and-white picture is represented by a polynomial in the two variables X and Y with coefficients from the set {0,1}. Also, each gray digital picture is represented by a polynomial in two variables with coefficients from the set {0,1, ...,2n — 1} where the picture has 2n gray levels. The polynomials representing binary and gray pictures are referred to as picture polynomials. First we introduce algebraic operators to perform certain basic operations, like edge detection. Then, we apply the template polynomial approach to develop a method for decomposing the template which reduces the time complexity significantly for a large sized template in parallel processing.

A common method for storing knowledge in databases is in the form of attribute values. For databases with spatial and temporal knowledge however, it is not feasible to store all of the attribute values that one might be interested in. For example, in the spatial domain for a geographic database it is impossible to anticipate the very large number of queries regarding nearness, spatial adjacency, or the possibility of finding feasible paths between arbitrary locations. Similarly in the temporal domain it is impossible to anticipate all queries regarding the temporal duration, range, and overlap of complex temporal events. We have developed both spatial and temporal representations for databases to handle the inferring of attribute values as a result of possible queries. The temporal representation involves the creation of time tags for attribute values and information regarding the persistence of those values. The spatial representation consists of a labeled array in which each label corresponds to to a unique object (or class of objects) in the database. Preprocessing of spatial “scenes” allows the system to rapidly obtain paths, determine objects in a given region of interest, etc. These representations, and their application to typical geographic/temporal databases are described in the paper. A natural language interface, developed earlier, was extended to work with these spatial and temporal representations.

An application of a temporal model which allows the addressing of the temporal issues inherent in the natural language specifications of distributed systems is introduced. The proposed model is integrated into the SeCalc (State-Event Calculus) model for system specifications which was designed to permit the semi-automated conversion of natural language specifications into a system design. The paper presents a description of the temporal model as well as the constraint propagation method used to maintain and extend the knowledge. By using its knowledge of time-related vocabulary and the temporal model, the system constructs a meaningful network of events and temporal information, relating both relational and numeric temporal knowledge. Thus a capability for detecting inconsistencies in the temporal aspects of the specifications is provided. Key Words: Temporal Reasoning, Natural Language Processing, Consistency Checking, Software Engineering, Software Specifications.

Subcategorization enables each word to determine what type of complements it can take. For example, put takes an object plus a locative phrase; one can say I put the cat on my lap but not I put the cat nor I put on my lap. Subcategorization often involves discontinuous constraints (e.g., put and on my lap are discontinuous), which complicates overly sequential syntactic formalisms such as phrase structure rules or transition diagrams. Register Vector Grammar (RVG) is a formalism designed to model discontinuous constraints efficiently. By avoiding redundancy in the number of categories or rules, it keeps grammar size small. By insisting on fixed, finite resources for non-detenninism, it processes sentences in linear time. We haved extended RVG so that it represents subcategories in a manner that, rather than increase computational complexity, actually improves the performance of grammars.

During the design and fabrication of the Hubble Space Telescope (HST), Perkin Elmer generated substantial amounts of project documentation in a variety of forms including project memos, reports, correspondence, drawings, and videotapes. Over the fifteen-year scheduled mission lifetime, timely access to this extensive documentation will be critical for the successful operation and maintenance of the telescope. We have developed a prototype for a microcomputer-based document retrieval assistant (DRA) which integrates hypertext and natural language capabilities to facilitate access to a large multimedia knowledgebase generated from HST project documentation. The prototype's hypertext capability allows casual or unfamiliar users to "browse" through the various media associated with the OTA. An intelligent search capability allows rapid access to documents which address a particular topic or concept. This mode employs a natural language interface to permit users to express a domain- specific query without requiring the use of keywords. The natural language interface is the focus of the present discussion.

Neural networks can he used to solve highly nonlinear control problems. A two-layer neural network containing 26 adaptive neural elements has learned to back up a computer simulated trailer truck to a loading dock, even when initially “jackknifed. ’’ It is not yet known how to design a controller to perform this steering task. Nevertheless, the neural net was able to learn of its own accord to do this, regardless of initial conditions. Experience gained with the truck backer upper should be applicable to a wide variety of nonlinear control problems.

Group technology is a useful technique of general manufacturing systems that provides production efficiency in fabrication of similar but not identical devices on the same machines. In this paper, we extend this concept to computer-integrated- manufacturing of custom VLSI semiconductor devices, particularly in the area of multichamber and in-situ processing.

The classic Al approach to planning is fundamentally based on smart strategies in a discrete search space. In an analogic approach, on the contrary, basic representations are maps under the influence of complex dynamic systems and the role of "inference" and "reasoning" is taken by the simulation of their action. This approach has already been applied to Common Sense Reasoning and to Robotics. The key idea is that planning movements of redundant robots, which involves both robotic aspects as trajectory formation, navigation, obstacle avoidance, grasping, and AI aspects as action planning and representation of the world, can be solved by embedding these aspects into "analogic experts", that are concurrent procedures operating in a direct and fast way on the world representation. The power of this paradigm lies in treating simultaneously shapes, collision avoidance, trajectories, redundancy and sequence planning, possible dynamic environments, which is, so far, an open problem.

The paper describes the main ideas and principles of HAP (Hybrid representation of Actions and Plans), a system for hybrid representation and reasoning in advanced robotics. In this context, hybrid representation refers to the integration of both symbolic and analogic knowledge representation paradigms. In particular, the logic/symbolic component is based on a KL-ONE-like representation language. The system embeds "analogic experts", that are concurrent procedures operating in a direct and fast way on the world representation. These "experts" help the system in planning a correct temporal sequence of actions. As a reference scenario, assembly (and disassembly) problems are considered. The assembly problem can be decomposed in several suitable concurrent sub-tasks, which involves both robotic aspects as navigation, obstacle avoidance, grasping, and AI aspects as action planning and world representation. As a case study, the paper discusses the assembly of a complex object from parts as an experimental paradigm for planning movements of a redundant robot in an unstructured environment.

In this article we deal with the automated learning of tasks by a robotic system through observation of a human operator. Particularly, we explain what is meant by a learning ability in autonomous robots and in teleoperation systems, where several operators and several machines may work in cooperation to perform tasks. We discuss different approaches to learning in these systems and outline the features of the models they are based upon. This leads us to choose an analytical model suited for tasks analysis. We then present the software architecture for our proposed approach and show the first results obtained on sample tests.

A variety of problems must be overcome for a system that learns from examples to be useful. Such problems include reducing the dependency on the order of presented examples; reducing the number of examples required to learn a concept; pruning the generalization space; handling both conjunctive and disjunctive concept descriptions; and dealing with noisy training instances. This paper presents a system that effectively deals with many of these problems in a real-world domain by actively participating in the example selection process

The goal of the Partial Metrics Project is the automatic acquisition of planning knowledge from target code modules in a program library . In the current prototype the system is given a target code module written in Ada as input, and the result is a sequence of generalized transformations that can be used to design a class of related modules. This is accomplished by embedding techniques from Artificial Intelligence into the traditional structure of a compiler. The compiler performs compilation in reverse, starting with detailed code and producing an abstract description of it. The principal task facing the compiler is to find a decomposition of the target code into a collection of syntactic components that are nearly decomposable. Here, nearly decomposable corresponds to the need for each code segment to be nearly independent syntactically from the others. The most independent segments are then the target of the code generalization process. This process can be described as a form of chunking and is implemented here in terms of explanation-bas|d learning. Chunking has been shown to be an important vehicle for learning in other application domains as well . The problem of producing nearly decomposable code components becomes difficult when target code module is not well structured. The task facing users of the system is to be able to identify well-structured code modules from a library of modules that are suitable for input to the system. In this paper we describe the use of inductive learning techniques, namely variations on Quinlan’s ID3 system that are capable of producing a decision tree that can be used to conceptually distinguish between well and poorly structured code. In order to accomplish that task a set of high-level concepts used by software engineers to characterize structurally understandable code were identified. Next, each of these concepts was operationalized in terms of code complexity metrics than can be easily calculated during the compilation process. These metrics are related to various aspects of the program structure including its coupling, cohesion, data structure, control structure, and documentation. Each candidate module was then described in terms of a collection of such metrics. Using a training set of positive and negative examples of well-structured modules, each described in terms of the appointed metrics, a decision tree was produce that was used to recognize other well-structured modules in terms of their metric properties. This approach was applied to modules from existing software libraries in a variety of domains such as vision and numerical methods. The results achieved by the system were then benchmarked against the performance of experienced programmers in terms of recognizing well structured code. In a test case involving 82 modules, the system was able to discriminate between poor and well-structured code 99% of the time as compared to an 80% average for the 25 programmers sampled. The results suggest that such an inductive system can serve as a practical mechanism for effectively identifying reusable code modules in terms of their structural properties

This paper analyzes two different methodologies that were employed in the classification of a set of tonsillectomy/adenoidectomy patients into normal and abnormal diagnostic groups with respect to their predispositions to bleeding. An expert system was designed using conventional knowledge engineering strategies and an inductive learning technique was used to infer generalizations directly from the patient data. The former approach involved the development of a hematology expert system which serves as a preoperative filter to identify high risk patients. The system assesses bleeding tendencies as may occur with patients with certain hemostatic conditions such as platelet function defect, von Willebrand’s disease, and hemophilia. The specific inductive classification methodology used in this review was Quinlan’s ID3 induction algorithm which searches for underlying regularities in data sets. Quinlan’s method for inducing generalizations from a training set of events involves the creation of a classification tree whose root and intermediate nodes are decision points based upon the entropy measurements of the events’ attributes at those decision points. The generated leaf nodes correspond to the classification outcomes. This paper discusses the respective performances of the expert system and inductive learning methodologies including sensitivity and specificity measurements, reveals some of the problems encountered in the use of the two techniques, and suggests some possible remedies. The method used for the selection of the patient parameters for use by the ID3 algorithm is also discussed. The classification rules from both techniques are discussed and some computational and clinical (hematological) justifications are proposed concerning the disparity of the rule sets. Finally, some reflections are offered concerning the potential amalgamation of knowledge engineering strategies and inductive learning techniques

Intelligent robotic systems will need to have the capability to grasp, recognize, inspect and manipulate objects. Our experience in building an intelligent system with these capabilities has forced us to confront a number of important issues that we have found to be important in building an intelligent grasping system. The issues are 1) the need for multiple sensing capability in hands, 2) synchronization of actuation devices, and 3) coordinated contact movement on a surface. We demonstrate how these issues are overcome with an example of haptic sensing with our Utah/MIT hand system

The paper describes the main ideas and principles of HAP (Hybrid representation of Actions and Plans), a system for hybrid representation and reasoning in advanced robotics. In this context, hybrid representation refers to the integration of both symbolic and analogic knowledge representation paradigms. In particular, the logic/symbolic component is based on a KL-ONE-like representation language. The system embeds "analogic experts", that are concurrent procedures operating in a direct and fast way on the world representation. These "experts" help the system in planning a correct temporal sequence of actions. As a reference scenario, assembly (and disassembly) problems are considered. The assembly problem can be decomposed in several suitable concurrent sub-tasks, which involves both robotic aspects as navigation, obstacle avoidance, grasping, and AI aspects as action planning and world representation. As a case study, the paper discusses the assembly of a complex object from parts as an experimental paradigm for planning movements of a redundant robot in an unstructured environment.

In the near future, many large aspheric optics are required for space and astronomy applications. The use of computers to control the grinding and polishing of optical surfaces is necessary to increase the efficiency of such fabrication processes.

This paper deals with an important problem encountered in automating VLSI wafer probing. In this automation, vision is used for accurately guiding and lowering a probe to make contact with the wafer. The variance of pixel values of the probe and experimental observations are employed for determination of contact beteween the probe and the wafer. Analytical expressions are derived in the paper for the variance of the pixel values of the object with a uniform background and the variation of these values with respect to the distance of the object from the surface is studied. This relationship is experimentally verified for the detection of touch, when the probe is approaching the target pad.

Several weeks before each month begins, an airline pilot is issued a bid package describing the coming month's schedule. The pilot must turn in a bid on the schedule. Schedulers then assign a "line of time" based on the category seniority number of the pilot. (A category is defined by the base, aircraft type, and seat, i.e. captain, copilot, or flight engineer.) The most senior pilot in a category gets his/her first choice and need bid only one line. The second most senior pilot will get his first choice if it is different from the #1 pilot, or his second choice if their first choices are the same. And so it goes on down the seniority list. It is obvious that a pilot must bid at least as many lines of time as his category seniority to insure he is not assigned an undesired line. Many factors can enter into bidding the lines of time, and especially for pilots near the bottom of the category seniority, a lot of time is involved. Each pilot weighs the importance of each factor differently, and priorities of each pilot often change from month to month. This paper describes an expert system to help make the task easier and more exact. The system is programmed in OPS5 and runs on a VAX 8800 machine.

This paper discusses the application of using temporal constraint satisfaction in solving the scheduling problems from the operation management domain. The Logos constraint reasoning system implements the constraint propagation paradigm to solve the temporal constraint satisfaction problem. We will show that temporal relationships provide a richer model to express the scheduling constraints than the precedence relationship. Furthermore, temporal constraint system can model the dynamic perturbation of the events and their impact on the schedule. This paper presents examples that illustrate how Logos can model scheduling problems and how Logos can use this model to suggest rescheduling actions in response to schedule degradations. The domain model, expressed in Logos, recognizes the impact of the schedule perturbations and generates candidate solutions to reduce the impact. We conclude that Logos provides a concise, expressive representation of operations management scheduling problems and that the temporal reasoning component of Logos is suitable to a wide variety of applications.

In our continuing effort to incorporate state-of-the-art technologies into our services, Fluor Daniel evaluated some of its engineering activities to determine which ones will benefit the most from Expert Systems (ES) technology. Prototype Expert Systems were developed for selected activities such as conceptual cost estimating, project scheduling, hazard analysis, process control, etc. The objective of prototyping was not only to provide proof of concept, but also to identify a suitable expert system shell which would enable cost-effective Expert System development. Our experience demonstrates that an Expert System shell based on object-oriented knowledge representation is more suitable for some engineering applications than a purely rule-based system. We also found that the general purpose tools we used do not have the graphical capability necessary for some engineering applications and that the DBase interface and reporting capability need improvement.

This paper describes how high level, i.e. tactical, pilot knowledge can be represented, managed and used for real time decision making in a hostile environment. The basic knowledge unit is the action, which has a number of attributes, one of which is an executable algorithm. A number of actions that are combined in order to acheive a certain goal constitute a plan. Actions may be performed concurrently or sequentially. Plans are combined hierarchically as disjunctions of descendant plans. Selection and rejection of plans and actions for execution is done under continuous sensor data analysis by a dynamic scheduling mechanism. Our experience shows that all types of aircraft activities may be managed in this way, be it vehicle guidance, sensor information analysis, threat evaluation, navigation, combat or weapon control for military aircrafts. With this form of knowledge representation more functions can be automatized, as for example plan generation, selective information display, and supportive pilot aiding.

In this paper the task of designing a newspaper is discussed from the point of view of building a knowledge-based system. The characteristic features of the knowledge required in newspaper design are presented and the design goals together with the problem solving methods are described. The design process can frequently be seen as a task in which the aim is to fulfil the design goals using predefined problem solving methods and taking into account constraints which are specific to the problem. In newspaper design and pagination the constraints are imposed by the structure of the product i.e. the newspaper itself, the material (both editorial and ads) to be placed on the newspaper pages, the production equipment, and the actual production process.

The rough mill of a hardwood furniture or fixture plant is the place where dried lumber is cut into the rough parts that will be used in the rest of the manufacturing process. Approximately a third of the cost of operating the rough mill is the cost of the raw material. Hence any increase in the number of rough parts produced from a given volume of raw material can markedly affect profit margins of a company. To automate this initial cutup requires a computer vision system that can locate and identify surface defects on boards. This paper describes continuing research aimed at developing such a vision system. An important part of this research activity is the design effort going into creating a prototype hardware system, a system that will be able to scan variable width, variable length hardwood boards at industrial speeds of two to three linear feet per second. This system is being designed to handle full length boards up to sixteen feet long. The components of the prototype are a materials handling system, an imaging system, a image processing hardware system, and a software system for performing the necessary recognition tasks and for performing all the necessary control functions. The design of each of these components will be described with the emphasis placed on hardware development.

In this paper we discuss the role of tactile sensors in robotic manipulatory systems and present a number of techniques useful in processing tactile information acquired using passive as well as active sensing modes. Successful adaptation of touch in robotic manipulatory systems entails in both enhancing the tactile sensor technology, and developing techniques for efficient and accurate analysis of the tactile information. This paper attempts to emphasize the importance of adopting active tactile sensing scheme as against restricting to passive tactile sensing scheme. In an endeavor to demonstrate the utility of tactual perception for robotic systems, several experiments were carried out on tactile images of objects smaller as well as larger than the sensor size. The experimental results bring out the advantages of employing passive and active tactile sensing techniques to accomplish robotic manipulatory tasks. Further, based on the experimental results it becomes quite apparent that the use of Fourier descriptors over the use of complex moment invariants as shape descriptors is more advantageous for object recognition tasks using passively acquired images. A new least-square cross-correlation technique for generating composite images acquired through active exploration of objects larger than the sensor is also proposed. The implementation results clearly show that an ad hoc technique for generating composite images introduces more error than the technique proposed in this paper.

A complete autonomous legged robot is being designed at Carnegie Mellon University to perform planetary exploration without human supervision. This robot must traverse unknown and geographically diverse areas in order to collect samples of materials. This paper describes how thermal imaging can be used to identify materials in order to find good footfall positions and collection sites of material. First, we present the model that we developed for determining the temperature of materials in outdoor scene. By applying this model, we show that it is possible to determine a physical characteristic of the material: thermal inertia. Second, we describe experimental results that consist in recording thermal images of an outdoor scene constitued with sand and rock. Third, we present results and limitations of applying the model to experimental images. Fourth, we analyse how basic segmentation algorithms can be combined with the thermal inertia segmentation in order to improve the discrimination of different kind of materials.

For autonomous navigation of an unmanned vehicle on a rough terrain such as the surface of Mars, two elevation maps are available: a gross terrain map from aerial surveying or satellite observations, and a local measurement map observed with sensors onboard the vehicle. One can estimate from the gross map the skyline and the visible region of the terrain. It also provides information of what the vehicle’s sensors can not see. However, the sensory measurements yield fine details of the terrain, such as obstacles, in-path and cross-path slopes. The skylines can also be estimated from these measurements. Both maps are used for path selection purposes, to provide it a wider supply of information than is available from either map by itself. The advantages of this are: (1) The “unseen” terrain features on the back of the hills, though only grossly estimated, are provided and can be taken into account by the path selection process. (2) The features “seen” by local measurements provide obstacle avoidance and are given primary consideration in the path selection process. The location of the autonomous vehicle on the gross map is to be estimated by employing the skylines as reference space curves. As the vehicle changes its location on the gross map, different skylines are estimated and are used in the stochastic matching of the two maps.

We present here an oral dialogue system designed for air-traffic controller training. The system has to handle the dialogue with a student air-traffic controller and communicate the student’s requests to the air-traffic simulator in the form of a sequence of instructions expressed in a formal command language. The system has been developed with two main objectives in mind: we tried to make it both user-friendly and robust. Different knowledge sources including the vocabulary, the phraseology, the task model and the history of dialogue, are evolving during the dialogue. These knowledge bases are represented in a unified form of hierarchical frames. The message analysis and interpretation consist of two phases: categorisation and instantiation. Then, a validity control process uses a set of semantico-pragmatic constraints. Correction procedures have also been developed to improve speech recognition performance. The speech recognition system which is being used is AMADEUS developed at the LIMSI. It is a DTW-based continuous speech recognizer. The representation of the language model used to limit the DTW search space is described as well as the way it is modified by the dialogue manager in order to permit or prohibit messages and improve recognition. In system evaluation, the classical DTW approach is compared to a probabilistic approach using dynamically updated transition probabilities.

Recognition of images moving with respect to a constant background (possibly contaminated by a noise) may be considerably improved if a Neuronlike Network (NN) with specific dynamic properties is applied for preliminary data processing. Optimal design of a dynamic network containing thousands of interconnected, nonlinear elements requires development of special tools and algorithms. In our system, the optimization of the NN parameters for preliminary processing of moving images is performed using a model of the dynamic processes in the retina called ARTINA. A compromise between satisfactory contrasting and noise elimination defines a "quasi-optimal" structure of local connections in the NN. In this paper we present an experimental procedure (using ARTINA) for partial optimization of a NN performing contrasting and local features detection for images moving with velocities within a given range of values. A performance index for contrasting and edge enhancement is first selected. It is then shown that through appropriate selection of dynamic properties of the NN elements, it is possible to achieve a considerable (up to 10 times) improvement of the performance index. Proper selection of time constants, delays, and connection ranges results in a "cumulation" process. This process enhances contours of moving objects and improves detection of local features. A special optimization algorithm, using a selected performance index, permits the optimization both of the neuron time constants and of the structure of local connections defining the central and peripheral receptive fields. Relations between object speed, time constants describing the dynamics of the neuron, and dimensions of receptive fields are investigated. Results of the optimization and a discussion of possible methods for improving the preliminary dynamic image processing is presented.

Preliminary results of applying automated decision-making techniques for airborne early warning purposes are presented. The approach is based on modeling operator's decision process and representing in form of procedural knowledge. These techniques are embodied in Threat Assessment and Tactical Planning modules and they are demonstrated using an advanced simulation facility. Simulation results show that decision automation is a valuable tool in an airborne early warning environment

Expert system technology is applied to the problem of obtaining detailed, consistent, timely and accurate postflight performance analysis of a complex airborne vehicle tracking system. The operational complexity of the tracking system is described and a general methodology for automating post-flight performance analysis is outlined. An expert system is developed which is executed in a compiled language and utilizes generic rule modules with a rule attribute data base to achieve high processing speeds and enhance maintainability. The expert system is presently supporting the post-flight performance analysis of tracking system data from actual flights.

This paper briefly describes the spacecraft and ground systems monitoring process at the Jet Propulsion Laboratory and highlights some difficulties associated with the existing technology used in mission operations. A new automated system based on artificial intelligence technology is described which seeks to overcome many of these limitations. The system, called the Spacecraft Health Automated Reasoning Prototype (SHARP), is designed to automate health and status analysis for multi-mission spacecraft and ground data systems operations. The SHARP system has proved to be effective for detecting and analyzing potential spacecraft and ground systems problems by performing real-time analysis of spacecraft and ground data systems engineering telemetry. Telecommunications link analysis of the Voyager 2 spacecraft was the initial focus for evaluation of the system in a real-time operations setting during the Voyager spacecraft encounter with Neptune in August, 1989. The SHARP system will be delivered to the JPL Space Flight Operations Center for regular use by planetary flight projects, including the Galileo and Magellan spacecraft, and will also be applied to monitoring and control applications in the Deep Space Network's Network Operations Control Center.

There are many applications which may be done by an expert system in real time, if the system is capable of real time response. The Lisp and Prolog based expert systems have typically been too slow for real time response. This has lead to an effort to use other languages, the development of fast pattern matching techniques and other methods of improving the speed of expert systems. Another approach to developing faster expert systems is to make use of the emerging parallel processing computer technology. A further use for parallelism is to allow reasonable response time for large knowledge bases. The size of knowledge bases may become as large as 20,000 chunks of knowledge (and more) in the near future in medical and space applications. This paper describes the use of parallel processing in the EMYCIN backward chained rule-based model is used.

This paper describes a new RISC architecture being designed to take advantage of GaAs technology for high performance symbolic processing. First, we present our top-down methodology which starts from the study of applications requirements, technology constraints, and concludes with the choice of the most suitable architecture. Then, next paragraphs describe carefully the architecture and its originalities. It can be summerized as a tagged-RISC embedded processor, which is able to operate with a 200 Mhz clock rate. As a conclusion, we give performance goals and simulation results.

Inductive inference methods are applied to obtain approximate solutions to integer programming problems arising from the control of power electronic equipment. Divan demonstrated a novel power inverter circuit using a resonant link running at a fixed frequency. This circuit reduces waveform synthesis to specification of a binary sequence, which determines the state of the inverter’s switches, and results in a large 0-1 integer programming problem. DeMarco and Divan proposed to select an optimal sequence with respect to a linear cost function using a branch-and-bound method. We show that this is not an efficient approach for realistic problems and propose an alternate strategy using simulated annealing. We have incorporated machine learning to synthesize the control sequence in real-time. Results comparing the two methods and demonstrating on-line control synthesis are given.

When a complex plant is operating, the output of the plant sensors form a pattern of readings that represent the state of the plant. When disturbances occur, the sensor outputs form patterns that represent different states of the plant, depending on the nature of the disturbances. For safety reasons, it is important to identify changes in the state of operation at the earliest possible time. In this study, we have applied a neural network technique to data from a commercial nuclear power plant to detect changes in operational states. The Polynomial Discriminant Method, PDM, was used to identify operational states of a pressurized water reactor nuclear plant. The data consisted of temperature, pressure, power level, and coolant flow readings collected in one of the loops of the plant. The network was trained to discriminate among data collected during normal, steady-state, operating conditions; data collected during start-up; and transient data collected during a shut-down. The network was able to classify correctly 89 % of the cases in which it was tested. The algorithm, although intensively computational during training, exhibits rapid matching and great interpolating capabilities during recall.

Techniques have been developed for the extraction and characterization of absorption features from visible and infrared reflectance spectra and an expert system has been designed, implemented, and successfully tested that allows automated identification of minerals based on their spectral characteristics. A suite of laboratory spectra of common minerals was analyzed and the absorption band characteristics tabulated and used to develop a generalized knowledge base for analysis of the reflectance spectra. A tree hierarchy was designed to emulate the decision process followed by an experienced analyst for analysis of laboratory and field reflectance spectra and aircraft imaging spectrometer spectra. Good results were obtained with the expert system for all three types of spectra, with the critical factor in the analysis being the signal-to-noise ratio of the spectral data.

Satellite imagery of the oceans has become an invaluable tool for the oceanographer, adding the breadth of synoptic coverage to the depth of in situ measurements at a few points. New satellite systems will greatly increase the data volume, increasing the burden imposed by the labor-intensive nature of current processing methods. Consequently, standardization and optimization of interpretive techniques are highly desirable. We have designed an expert system as part of a system intended to aid the oceanographic image analyst, since the problem is not amenable to conventional automated image understanding methodology. The expert system's rule base comes from a new, comprehensive compilation of oceanographic information, and the expert system has other unique features. Tests of the expert system’s ring motion rules are encouraging and indicate some directions for improvements. Research to improve the expert system and transitions to operational use are both under way.

A prototype expert system program has been developed to assist in the identification of fluorescence materials from UV lidar returns. Features such as emission peak locations, peak broadness at half height, number of peaks, and decay lifetimes comprise the knowledge base for a particular category of substances. The expert system will ask the user for features from an unknown substance and then will compare these features with the knowledge base of known substances. Preliminary results show that the expert system is capable of discriminating single substances from a small data set of fluorescence substances with their associated features. To handle multicomponents, it is suggested that preprocessing of the data be performed in which only the peak locations of single substances and combinations of peak locations of multiple substances be searched.

For a long time, computer types have been saying ’’wait till next year's computer, then we will have lots of power.” And next year came, and things changed, but not as dramatically as we had been led to expect. The 90's will finally be when those computer-types won’t be crying wolf: the accompanying graph shows quite clearly that we are. finally, on the elbow of the "MIPS exponential." Those who translate the above graph onto log paper, get a straight line, and then say "so what," are missing the point: there is another, but much grander, threshold of usability that we are crossing. That is, we have seen in the last few years a veritable order of magnitude increase in the use of computers in everyday life: lots and lots of folks routinely use computers on a moment-by-moment basis. And those folks are now ready for the next increment of computer-based support. The above curve says that the pure horsepower is going to be there; the only issues, of course, are what to provide and how to build it.

We have developed a diagnostic system that employs the Dempster-Shafer (D-S) evidential reasoning technique to conduct malfunction diagnosis on semiconductor manufacturing equipment. This is accomplished by combining evidence originating from equipment maintenance records, from real-time equipment data, and from measurements on the finished product. Using this information, equipment malfunctions are analyzed and their causes are inferred through the resolution of qualitative and quantitative constraints. The qualitative constraints describe the "normal" operation of the equipment. The quantitative constraints are numerical models that apply to the manufacturing step in question. These models are specifically created and characterized through experimentation and statistical analysis. The violation of these constraints is linked to the evaluation of continuous "belief functions" for the calculation of the "belief' associated with the various types of failure. The belief functions encapsulate the experience of many equipment maintenance specialists. Once created, the belief functions can be fine-tuned automatically, drawing from historical maintenance records. These records are stored in symbolic form to facilitate this task. A prototype of this diagnostic system was implemented in an object-oriented programming environment. This implementation enables knowledge and functionalities to be shared by different pieces of manufacturing equipment. The D-S diagnostic method was first applied to a reactor used for Low Pressure Chemical Vapor Deposition (LPCVD) of undoped polysilicon films. Early results indicate that this diagnostic system is sensitive, stable, and accurate.

The advancement of VLSI technology has reached the stage where the automation of semiconductor manufacturing has become imminent. A natural step towards this end is to apply the available expert system technology to the task of intelligent control, monitoring and diagnosis of various processes and equipment for the IC manufacturing environment. This paper gives an overview of a machine learning program (GID3) and its use in automating the knowledge acquisition needed for the construction of an expert system for controlling the Reactive Ion Etching (RIE) process in IC manufacturing. We argue the appropriateness and necessity of machine learning to circumvent the “knowledge acquisition bottleneck”. We then motivate and describe the learning algorithm we developed. The GID3 system was applied to five different projects with several SRC industrial institutions. We describe some of the application areas where an acceptable level of success was achieved by the program. The application areas include: identification of relationships between RIE process anomalies and the corresponding parameter settings, acquiring a set of rules for correcting RIE process parameters contributing to abnormal output, and knowledge acquisition for an emitter piloting advisory expert system. The main theme of this paper is to bring attention to machine learning as a useful tool in the automation of the IC manufacturing process and as an aid to engineers in interpreting and assimilating experimental results.

In semiconductor manufacturing, there are many opportunities to improve productivity or reduce equipment downtime by implementing an expert system to perform diagnostic reasoning. Expert systems can be used to diagnose problems with the equipment used in manufacturing and testing as well as diagnosing process problems when production quality declines. Expert systems have been used in hundreds of applications for fault diagnosis. Many of the early systems developed employ a "rule-based” approach, where, typically rules are used to describe a set of symptoms that must exist in order to conclude that a certain problem exists. This type of knowledge is often called "heuristic" knowledge because it contains the expert’s own specialized rules for problem solving that have been developed from years of experience. But, before an expert develops a set of heuristics, problems are solved by understanding a "model" of how a system operates. This "model-based" approach to fault diagnosis has been an area of recent research and development. Both of these approaches to fault diagnosis have been used successfully in many applications, but there are weaknesses in both approaches. Rule-based approaches tend to be brittle (i.e. unable to provide a solution - or worse, provide a wrong solution) if there is knowledge missing from the system, and model- based approaches may take a long time to reach a solution for a large model and must always use that model (i.e. no shortcuts, even when evidence points to a specific problem). Additionally, there are problems which cannot be modelled well enough to be put into a model-based approach. This paper will describe HINTS (Harris Internal Troubleshooting System), a classification approach to fault diagnosis that uses concepts from both model-based and rule-based approaches but overcomes their limitations.

Qualitative simulation is a technique of artificial intelligence for the qualitative description of mechanism and the representation of incomplete knowledge of the structure and behavior in qualitative physics. Although quantitative simulation has been the main analytical tool in microelectronic materials processing, it is not adequate for real-time process/equipment monitoring and control. Qualitative simulation and modeling can be directly used in process monitoring/control expert systems and any part of CAD/CAE/CAT automation. The qualitative structure and behavior descriptions can be encoded directly as expert knowledge, and moreover used for model-based reasoning.

It is commonly recognized that there are three main causes of circuit yield losses: process related problems, design sensitivities, and point defects. Yield losses due to design sensitivity primarily occur during the early development phase of a VLSI circuit. Previous work in eliminating design sensitivities have concentrated on using statistical simulations which is computationally expensive for VLSI circuits with over million transistors. This paper describes an approach to detect design sensitivity using methods of pattern recognition and parsimonious hypothesis formation.

Diagnostic problem solving is a major application area of knowledge-based system research. However, most of the current approaches, both heuristic and model-based, are designed to identify single faults, and do not generalize easily to multiple fault diagnosis without exhibiting exponential behavior in the amount of computation required. In this paper, we employ a decomposition approach based on system configuration to generate an efficient algorithm for multiple fault diagnosis. The basic idea of the algorithm is to reduce the inherent combinatorial explosion that occurs in generating multiple faults by partitioning the circuit into groups that correspond to output measurement points. Rules are developed for combining candidates from individual groups, and forming consistent sets of minimal candidates.

Although diagnosis occurs in very different fields, the basic problem is always the same; diagnosis is searching for causes of failures. Introducing the task-specific Diagnosis Domain separates the basic problem from its application occurrences and provides a platform for formulating diagnosis problem solving application-independently. An application attains the platform via the Domain Abstraction. The Diagnosis Kernel addresses the basic problem and directly generates the minimal candidates (causes) of Incorrect observations (failures) in the Diagnosis Domain. The adder-multiplier example demonstrates the presented approach.

When a diagnosis system is used in a dynamic environment, such as the distributed computer system planned for use on Space Station Freedom, it must execute quickly and its knowledge base must be easily updated. Representing system knowledge as object-oriented augmented fault trees provides both features. The diagnosis system described here is based on the failure cause identification process of the diagnostic system described by Narayanan and Viswanadham. Their system has been enhanced in this implementation by replacing the knowledge base of if-then rules with an object-oriented fault tree representation. This allows the system to perform its task much faster and facilitates dynamic updating of the knowledge base in a changing diagnosis environment. Accessing the information contained in the objects is more efficient than performing a lookup operation on an indexed rule base. Additionally, the object-oriented fault trees can be easily updated to represent current system status. This paper describes the fault tree representation, the diagnosis algorithm extensions, and an example application of this system. Comparisons are made between the object-oriented fault tree knowledge structure solution and one implementation of a rule-based solution. Plans for future work on this system are also discussed.

A methodology is presented which couples expert systems to neural networks for the purpose of monitoring and diagnostics of large complex systems such as nuclear power plants. In order to provide timely, concise and task-specific information about the many aspects of the system's processes and to determine the state of the system based on the interpretation of potentially noisy data a model-referenced approach is utilized. In it a rule-based system performs the basic interpretation and processing of the data using heuristic reasoning. Having access to a set of pretrained neural networks that typify general classes of the system's state the expert system is able to perform diagnostic functions. It compares on-line data from the plant's sensors to the results of neural computations. This allows the diagnostic function to be performed with a speed comparable to that of the temporal evolution of the system. Hence corrective action can be taken by an operator. The set of pretrained neural networks provide implicitly a generalized model of the system which includes normal and off-normal states. Neural Networks are trained either by actual data or by data produced by a simulator. Coupling them to a rule-based system is a way of taking advantage of the best features of both. The speed and pattern recognition capabilities of the pretrained neural networks and the reasoning and interpretative power of symbolic computations. Information granules are used as the basic propositions that constitute the power plant's description in the knowledge-base of the expert system. They have the canonical form g = X is G is X, where X is a random variable described by a probability density function, G is a qualification or elastic constraint on the values of X; and X is a qualification of the proposition "X is G". This formulation encompasses two types of data: Data referring to observables or measured quantities from the system's sensors and calculated data coming from models of the plant such as from pretrained neural nets. Both the expert system and the neural networks are implemented in C and run in a VAX cluster.

A primary concern of target recognition systems is the actual detection of targets in a scene. Whereas identification assigns each detected target to a class, targets that go undetected are not considered. This leads to deteriorating system performance. This paper describes a neural network approach to the target recognition problem that exploits target composition in conjunction with structure to detect targets. An automatic target recognition architecture is presented to identify how the neural network environment may be integrated into existing systems. The neural network system is described in detail and the training process delineated to show the actual implementation and training issues involved. Performance of the system is documented through evaluative analysis of results generated using an infrared image database. The research performed to date is summarized and a discussion of future developments and their complement to the target recognition process is presented.

This paper presents an approach for edge segment based stereo analysis. In this, linear features are derived independently from a pair of stereo images and are matched using a relaxation labeling technique. The matching process integrates two global stereo matching constraints, figural continuity and disparity continuity. The results of the experiments show that the method is capable of solving the correspondence problem with reasonable accuracy. This segment based stereo analysis will be utilized as a component of a hierarchical stereo system currently under development. It is believed that the hierarchical stereo approach will attempt to capture the unique strengths of primitives of differing levels of abstraction in a systematic manner.