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.