Tracing maps or other line-drawings for feature identification to obtain concurrent and subsequent identification is complicated by the difficulty in vectoring the tracing process in an optimal manner. The digitized features may have nearly infinite variation in size and shape, and it is important to measure the original shape including width, curvature, length, and continuity; thus image enhancement is undesirable. Without processing, including line-thinning, many traditional tracing algorithms result in backtracking or random wandering rather than following feature trends. The problem is especially acute in cases where features (such as lines) intersect. The necessity to intelligently monitor feature tracing is the subject of the current study presented in this paper. This paper reports on software development for an IBM PS/2 Model 80, with a 80386 processor, to control a mobile mask that focuses on a limited portion of the feature being traced. During tracing, the mask surrounds a portion of the feature, and an investigation of attributes becomes manageable since the field of view is restricted by the mask. After feature information has been extracted from the current location, the mask is vectored to a new location (based on current trend information) that is optimal for continually following the feature. Feature identification and trace vectoring is performed by using programming language (Turbo Pascal 5.0) manipulation of Boolean functions to simulate knowledge base rules. Program code is much more efficient during the software development stage than coupling an inference engine to the tracing software. In future research, integration with an inference engine will permit efficient user-initiated strategy changes for analyzing increasingly complex features.

An algorithm for finding a single good path through the set of edge points detected by the gradient of Gaussian operator is discussed. First, an algorithm for finding contours at one scale is presented, then extensions of that algorithm which use multiple scales to produce improved detection of weak edges are presented. Edge points are linked along the gradient maxima ridges using a weighted tree search algorithm. The weights at each point measure noise, curvature, gradient magnitude, and contour length. In the algorithm for multiple scales the search for a contour proceeds as for the single scale, using the largest scale, until a best partial contour at that scale has been found. Then the next finer scale is chosen and the neighborhood around the end points of the contour are examined to determine possible edge points in a direction similar to the end point of the contour. The original algorithm is then followed for each of the points satisfying the above condition, and the best is chosen as an extension to the original edge. A second algorithm uses gradient information obtained at multiple scales in the non-maxima suppression operation. The coarsest scale is used first. Then the edge points are shifted as the non-maxima suppression is applied at finer scales. Both algorithms improve the. detection of edge contours with little increase in noise. The second also reduces the delocalization occurring at larger scales.

Autonomous vehicles often perform navigation and path planning using hierarchical control systems. These systems separate high and low level reasoning through an abstraction of the planning problem. For reasoning about terrain information, we present a method of abstraction that retains the finest level of resolution while progressing through greater levels of abstraction. Abstraction arises from a continuum of Gaussian smoothed terrain surfaces; each smoothed surface describes the terrain at a different scale of abstraction. We refer to this continuum as scale-space. For each level of abstraction, important features can be extracted from land elevation data for planning purposes. In this paper, we present this abstraction method, a graph representation for retaining scale-space information, and examples of how features from various levels of abstraction influence planning at different levels of a hierarchical control system.

This paper extends our previous research on a highly structured and compact algebraic representation of grey-level images. Addition and multiplication are defined for the set of all grey-level images, which can then be described as polynomials of two variables. Utilizing this new algebraic structure, we have devised an innovative, efficient edge detection scheme.We have developed a robust method for linear feature extraction by combining the techniques of a Hough transform and a line follower with this new edge detection scheme. The major advantage of this feature extractor is its general, object-independent nature. Target attributes, such as line segment lengths, intersections, angles of intersection, and endpoints are derived by the feature extraction algorithm and employed during model matching. The feature extractor and model matcher are being incorporated into a distributed robot control system. Model matching is accomplished using both top-down and bottom-up processing: a priori sensor and world model information are used to constrain the search of the image space for features, while extracted image information is used to update the model.

This paper describes research aimed at developing an automatic cutup system for use in the rough mills of the hardwood furniture and fixture industry. In particular, this paper describes attempts to create the vision system that will power this automatic cutup system. There are a number of factors that make the development of such a vision system a challenge. First there is the innate variability of the wood material itself. No two species look exactly the same, in fact, they can have a significant visual difference in appearance among species. Yet a truly robust vision system must be able to handle a variety of such species, preferably with no operator intervention required when changing from one species to another. Secondly, there is a good deal of variability in the definition of what constitutes a removable defect. The hardwood furniture and fixture industry is diverse in the nature of the products that it makes. The products range from hardwood flooring to fancy hardwood furniture, from simple mill work to kitchen cabinets. Thus depending on the manufacturer, the product, and the quality of the product the nature of what constitutes a removable defect can and does vary. The vision system must be such that it can be tailored to meet each of these unique needs, preferably without any additional program modifications. This paper will describe the vision system that has been developed. It will assess the current system capabilities, and it will discuss the directions for future research. It will be argued that artificial intelligence methods provide a natural mechanism for attacking this computer vision application.

Intelligence analysts are frequently faced with the task of developing and maintaining systems for the classification of large, noisy, incomplete and highly dynamic datasets. Until recently, analysts have had only two methodologies to bring to bear upon this task. The first requires that the analyst manually work with the data until a "feel" is developed for it. The second involves the application of classical statistical techniques such as discriminant analysis and numerical taxonomy. Unfortunately, however, these techniques often yield unintuitive decision rules and clusterings, or can demand unrealistic distributional assumptions. Because these traditional techniques are not always applicable, knowledge acquisition has been a "bottleneck" for building rule-based system. However, new automatic techniques drawn from the domain of machine learning are being developed that address both of these problems: they do not require such distributional assumptions, and they tend to deliver readily interpretable clusterings and decision rules. This paper describes experiments that explore the applicability of two such systems, MOCA and CART, as tools to help analysts cope with large quantities of intelligence data.

A learning classifier system (LCS) that learns rules for controlling a mathematical model of the liquid level in a vessel has been developed by the Bureau of Mines. LCSs resemble familiar production rule-based systems that incorporate a human expert's knowledge. However, in classifier systems the production rules are represented by strings of characters rather than in linguistic terms. This paper presents two specific examples in which an LCS produces a rule set for controlling liquid level whose performance is comparable to the performance of a human expert's rule set. In the first example, the LCS learns a rule that has been deleted from an author-supplied data base of effective rules. In the second example, the LCS learns rules to supplement a set of rules provided by the authors which included one rule detrimental to controlling liquid level. The LCS-generated rule set obtains a higher level of control over the liquid level system.

Practical knowledge-based systems need to reason in terms of knowledge that is already available in databases. This type of knowledge is usually represented as tables acquired from external databases and published reports. Knowledge based systems provide a means for reasoning about entities at a higher level of abstraction. What is needed in many of today's expert systems is a link between the knowledge base and external databases. One such approach is a frame-based database management system. Package Expert (PEx) designs packages for integrated circuits. The thrust of our work is to bring together diverse technologies, data and design knowledge in a coherent system. PEx uses design rules to reason about properties of chips and potential packages, including dimensions, possible materials and packaging requirements. This information is available in existing databases. PEx needs to deal with the following types of information consistently: material databases which are in several formats; technology databases, also in several formats; and parts files which contain dimensional information. It is inefficient and inelegant to have rules access the database directly. Instead, PEx uses a frame-based hierarchical knowledge management approach to databases. Frames serve as the interface between rule-based knowledge and databases. We describe PEx and the use of frames in database retrieval. We first give an overview and the design evolution of the expert system. Next, we describe the system implementation. Finally, we describe how the rules in the expert system access the databases via frames.

CAUSA is an environment for modeling and simulation of dynamic systems on a quantitative level. The environment provides a conceptual framework including primitives like objects, processes and causal dependencies which allow the modeling of a broad class of complex systems. The facility of simulation allows the quantitative and qualitative inspection and empirical investigation of the behavior of the modeled system. CAUSA is implemented in Knowledge-Craft and runs on a Symbolics 3640.

We are developing a computer vision system to automatically detect and track human motion across the international border between the United States and Mexico. Fundamental requirements are that the system work in real time under varying environmental conditions with relatively inexpensive hardware. The work we describe is applicable to a wide range of multiple object tracking problems. This paper describes the algorithm we have developed to detect and track moving objects. The algorithm is based on the notion of path coherence. However, the algorithm presented there is not suitable for our application because it requires noise free images, all trajectories must be present from the first through last images, and it requires multiple passes throught the trajectory points as each new image is acquired. This procedure is not acceptable for real time applications. We have previously reported on the front end of our system which takes video images and determines the areas which represent changing objects'. Thus the input to the tracking portion of the system consists of a binary image representing the changing pixels. In this paper we present a detailed description of the tracking algorithm, its implementation in Smalltalk-80, and samples of its operation. We also discuss system performance as a function of trajectory complexity and image noise level.

This paper presents a detailed description and a comparative analysis of the algorithms used to determine the position and orientation of an object in real-time. The exemplary object, a freely moving gold-fish in an aquarium, provides "real-world" motion, with definable characteristics of motion (the fish never swims upside-down) and the complexities of a non-rigid body. For simplicity of implementation, and since a restricted and stationary viewing domain exists (fish-tank), we reduced the problem of obtaining 3D correspondence information to trivial alignment calculations by using two cameras orthogonally viewing the object. We applied symbolic processing techniques to recognize the 3-D orientation of a moving object of known identity in real-time. Assuming motion, each new frame (sensed by the two cameras) provides images of the object's profile which has most likely undergone translation, rotation, scaling and/or bending of the non-rigid object since the previous frame. We developed an expert system which uses heuristics of the object's motion behavior in the form of rules and information obtained via low-level image processing (like numerical inertial axis calculations) to dynamically estimate the object's orientation. An inference engine provides these estimates at frame rates of up to 10 per second (which is essentially real-time). The advantages of the rule-based approach to orientation recognition will be compared other pattern recognition techniques. Our results of an investigation of statistical pattern recognition, neural networks, and procedural techniques for orientation recognition will be included. We implemented the algorithms in a rapid-prototyping environment, the TI-Ezplorer, equipped with an Odyssey and custom imaging hardware. A brief overview of the workstation is included to clarify one motivation for our choice of algorithms. These algorithms exploit two facets of the prototype image processing and understanding workstation - both low-level (segmentation) and high-level (rule-based recognition) vision capabilities.

Automatic target recognition (ATR) is one of the most challenging tasks for a computer vision system. It involves the determination of objects in natural scenes in different weather conditions and in the presence of both active and passive countermeasures and battlefield contaminants. This high degree of variability introduces considerable uncertainty into the vision processes in an ATR. This mandates both a flexible control structure capable of adapting as conditions change and a method for managing the uncertainty to aggregate evidence. The desired flexibility can be achieved with a rule-based system in which the knowledge of the effects of scene content and ancillary information on algorithm choices and parameter values can be modeled and manipulated. In this paper, we describe such a system. The uncertainty is modelled by a combination of fuzzy set theory and Dempster-Shafer belief theory. Several variations of these methodologies within the rule-based structure are explored. The results are compared using sequences of forward looking infrared images.

Human subjects easily perceive and extensively use shape regularities such as symmetry or periodicity when they are confronted with the task of object description and recognition. A computer vision algorithm is presented which emulates such behaviour in that it similarly makes use of shape redundancies for the concise description and meaningful segmentation of object contours. This can be compared with the way in which designers proceed in using CAD/CAM. In order to make the problem more accessible to computer programming, the contours are analyzed in so-called 'arc length space'. This novel mapping facilitates the detection and elimination of regularities under a broad range of viewing conditions and yields a natural basis for the formulation of the corresponding model compression rules. Several of the regularities which have traditionally been treated separately, are given a unified substrate.

The success of knowledge-based image analysis methodology and implementation tools depends largely on an appropriately and efficiently built model wherein the domain-specific context information about and the inherent structure of the observed image scene have been encoded. For identifying an object in an application environment a computer vision system needs to know firstly the description of the object to be found in an image or in an image sequence, secondly the corresponding relationships between object descriptions within the image sequence. This paper presents models of image objects scenes by means of hierarchically structured classes. Using the topovisual formalism of graph and higraph, we are currently studying principally the relational aspect and data abstraction of the modeling in order to visualize the structural nature resident in image objects and scenes, and to formalize. their descriptions. The goal is to expose the structure of image scene and the correspondence of image objects in the low level image interpretation. process. The object-based system design approach has been applied to build the model base. We utilize the object-oriented programming language C + + for designing, testing and implementing the abstracted entity classes and the operation structures which have been modeled topovisually. The reference images used for modeling prototypes of objects and scenes are from industrial environments as'well as medical applications.

This paper describes the development by Digital Equipment Corporation of a tool to build expert systems for diagnosing problems in computer modules. The Expert's Toolkit (ET) consists of two parts: the Knowledge Acquisition,Tool (KAT) and the Intelligent Decision Engine (IDE). KAT enables expert technicians to capture their problem-solving strategies in a knowledgebase. IDE provides other technicians and operators on the manufacturing floor with access to the expertise captured in the knowledgebase. The ET system has evolved into a generic expert system building "shell." While ET has been used successfully to build diagnostic systems in other domains, this paper focuses on the computer module problem domain. It describes the problem domain, the design of ET, its basic features, constraints and limitations, the required hardware and software, and the lessons we learned.

An expert system which supports unexperienced users in the application of the SPIDER image processing software package is described in this paper. The proposed structure of the knowledge base allows a generalized approach to software configuration expert systems whicn is applicable in other problem domains, too. The system has been completely implemented and tested on a number of problems.

Thermal infrared images of the ocean obtained from satellite sensors are widely used for the study of ocean dynamics. The derivation of mesoscale ocean information from satellite data depends to a large extent on the correct interpretation of infrared oceanographic images. The difficulty of the image analysis and understanding problem for oceanographic images is due in large part to the lack of precise mathematical descriptions of the ocean features, coupled with the time varying nature of these features and the complication that the view of the ocean surface is typically obscured by clouds, sometimes almost completely. Towards this objective, the present paper describes a hybrid technique that utilizes a nonlinear probabilistic relaxation method and an expert system for the oceanographic image interpretation problem. A unified mathematical framework that helps in solving the problem is presented. This paper highlights the advantages of using the contextual information in the feature labeling algorithm. The paper emphasizes the need for the feedback from the high level modules to the intermediate modules in an automatic image interpretation system. The paper presents some important results of the series of experiments conducted at Remote Sensing Branch, NORDA, on the NOAA AVHRR imagery data. Key words: feature labeling, feature extraction, oceanic features, edge detection, knowledge based systems, expert system, relaxation, infrared imagery.

A General Expert Systems Package for Science and Engineering that is now being deve-loped consists of two Automatic Deductive, two Learning and eight Service Systems, each of which is an Expert System that can function independently. Operational prototypes exist for nine of the twelve systems. The Service Expert Systems perform operations that are common to many problems In science and engineering, such as high-speed information management, data compression, transporting high-level language code to different machine environments, curve-fitting and data description. The high-speed information management system, SOLID, which uses minimal storage, is both data (or information) and logically independent. SOLID executes all operations (retrieve, store, delete and update) at very high-speeds in bounded time. The data compression system, INTEGRAL, compresses and decompresses bit-strings at rates often in excess of 8 MBaud without loss of even a single significant binary-bit, to yield savings as high as 99.98%.

Mathematical morphology, "algebra of shape", is used in many image processing applications including machine vision recognition, visually guided robot vision systems, biomedical image processing, and low-level vision problems. The fact that mathematical morphology deals with shape characteristics of an image makes it a tool for object recognition, defect detection, and feature extraction. The analogy between the morphological operations for shape and the convolution operations for signals suggests the dominance of mathematical morphology in the image processing applications related to shape, especially in machine vision.

A novel technique is presented for segmenting seismic waveforms. The method produces waveform segments which closely correspond to explosion and earthquake signal onsets as well as additional structure of interest. Noise spikes or glitches are also successfully isolated. The approach uses threshold parameters obtained from human segmentation judgment tests and requires only simple, time domain calculations.

An algorithm for segmenting range images of industrial parts is presented in this paper. Range images, are unique in that they directly approximate the physical surfaces of a real world 3-D scene. The segmentation of images ( range or intensity ) is based on edge detection or region growing techniques. The algorithm presented in this paper segments the range images by detecting discontinuities. There are three types of discontinuities in range images: jump, crease and smooth edges. The detection of a jump edge is relatively easy and can be obtained using edge detection techniques used for intensity images. The crease and smooth edges are difficult to detect especially in the presence of noise. Our approach is based on the analysis of the difference between the input and the filtered images. We show that, at an edge, the difference after Gaussian smoothing has a maxima in a direction perpendicular to the edge. The close connected regions are then obtained by eroding the image once and an iterative region growing least square fit is used to obtain the final segmented image. The performance of the proposed algorithm on a number of range images is presented.

The segmentation problem in image processing still falls short of an optimal solution. Obtaining a suitable segmentation requires domain specific knowledge. The optimal insertion of this knowledge in the segmentation process is the major issue. The complex human visual system first extracts reliable intrinsic information from the input and then applies knowledge stepwise at each stage of visual processing from the retinal to the cognitive levels. A near optimal segmentation scheme should approximate this approach. In this paper we present a segmentation algorithm based on the above approach. Using only intrinsic information from a noise refined copy of the input image, we identify and group pixels that are geometrically related into regions. The partitioning is successively refined by region merging, using only general rules of perceptual grouping. Control strategies for judging connectivity and homogeneity are based on basic topological and geometric rules. This general geometry guided segmentation has the advantage of being domain independent. At an intermediate level we start introducing domain specific knowledge in further region merging. Our applications are in cell physiology and we first exploit general knowledge from cytology. Progressively, we increase knowledge use in the definition of merging rules. Higher up the segmentation heirarchy, we include rules specific to a given branch of cell physiology and directly linked to characteristics of cell organelle. Merging stops when all existing regions are matchable with particular features and/or further merging is senseless or impossible using the defined rules. The results presented are from insect physiology where for some time now there has been disagreement among researchers on the number, type and distinguishing characteristics of the various hemocytes identified so far. The idea is to bring the various parties to a compromise by producing a Computer Based Reference Classification of Hemocytes.

Split and merge is a computationaly efficient region segmentation technique suitable to detect objects or surfaces in a given image. Despite its superior performance, it suffers from large memory usage and excessive computation time. This paper describes parallel implementation of the split and merge algorithm in a 16 node hypercube processor in order to reduce processing time to an acceptable level in the real time applications. Three methods are proposed to parallelize the operation of the method using the nearest neghbor (mesh) topology that can be mapped onto the hypercube architecture. Comparison of the described techniques is given and processing results of the real world images are presented.

The Rational Tree Machine (RTM) is a type of graph reduction architecture, for the processing of logic programs, currently under development at Boeing's High Technology Center. The architecture is composed of three types of functional modules: tree memory, automata constructor, and automata simulation modules. A previous paper described the overall architecture and its functionality. This paper will concentrate on a detailed description of the automata constructor.

A parallel language has to match or reflect the hardware underneath to use these resources efficiently. Though every parallel language has to have some kind of parallel machine model, no existing language states this explicitly. The Parallaxis parallel programming environment introduces a different approach. The system comprises the specification of the parallel algorithm and the parallel hardware as well. Parallaxis has been designed for single instruction, multiple data (SIMD) system architectures, consisting of identical processing elements (PEs) with local memory. Data exchange is handled by message passing through a local network. In Parallaxis, the hardware structure is specified in the beginning of each program to establish the environment for coding the parallel algorithm. This is necessary for actually arranging this topology using a reconfigurable system, but it is also profitable for performing a simulation, or just stating the used topology. Parallelizable AI applications that demonstrate Parallaxis' usefulness include computer vision, productions systems, neural networks and robot control.

In this paper, an OR-Parallel Execution model based multiprocessor system is proposed. Our OR-parallel execution model addresses the following features: (1) Run-time Intelligent Backtracking, (2) Distributed process control and execution, (3) Minimization of data communication between processors, and (4) Minimization of parallel processing management overhead. Special hardware modules such as Intelligent Backtracking Controller, and Forward Execution Controller are designed to further enhance these features in run-time. A bus connected multiprocessor system is designed to experience the proposed OR-parallel execution model. Recent simulation results indicate that the OR-parallel execution model can be successfully used to conduct the parallel processing of most non-deterministic Prolog applications such as database systems, rule-based expert systems, natural language processing and theorem proving, etc.

This work explores a distributed problem solving (DPS) approach, namely the AM/AG model, to cooperative memory recall. The AM/AG model is a hierarchic social system metaphor for DPS based on the Mintzberg's model of organizations. At the core of the model are information flow mechanisms, named amplification and aggregation. Amplification is a process of expounding a given task, called an agenda, into a set of subtasks with magnified degree of specificity and distributing them to multiple processing units downward in the hierarchy. Aggregation is a process of combining the results reported from multiple processing units into a unified view, called a resolution, and promoting the conclusion upward in the hierarchy. The combination of amplification and aggregation can account for a memory recall process which primarily relies on the ability of making associations between vast amounts of related concepts, sorting out the combined results, and promoting the most plausible ones. The amplification process is discussed in detail. An implementation of the amplification process is presented. The process is illustrated by an example.

A highly accurate stereo vision has been developed, at the National Research Council of Canada, as part of an on-machine dimensional inspection system. The approach is designed to eliminate or minimize the well-known difficulties of stereo vision. Its main features, besides the potentially high accuracy, are the flexibility, cost effectiveness and speed.

A new technique for computing intrinsic surface properties is developed in this research. Intrinsic surface properties refer to those properties of a surface which are not affected by the choice of the coordinate system, the position of the viewer relative to the surface, and the particular parametric representation used to describe the imaged surface. Since intrinsic properties are characteristics of a surface, they are ideal for the purposes of representation and recognition. The intrinsic properties which we are interested in are the principal curvatures, the intrinsic distance, and the lines of curvature. We propose to adopt a structured lighting sensing configuration where a grid pattern is projected to encode the object surfaces for analysis. At each stripe junction, the curvature of the projected stripe on the object surface is computed and related to that of the normal section which shares the same tangential direction as the projected curve. The principal curvatures and their directions at the stripe junction under consideration are then recovered using Euler's theorem. Application of this technique to represent and discriminate several simple surface types is also addressed.

In this paper an uncertainty analisys is performed of a system for the estimation of visual motion and depth from known egomotion. The motion strategy of the observer is constrained such as to track the point in space which projects on the image center (the fixation point) during the movement. The estimation of the optic flow is performed in two steps: firstly the velocity field is computed for each image pair at the zero crossing points; secondly the optic flow of a long sequence is obtained by matching corresponding contours between successive images. The model used is analysed and the uncertainty of each partial flow is determined on the basis of the independent parameters. The matching between image pairs causes an error propagation in the estimated velocity; a method is proposed to reduce the error using the velocity estimate relative to successive images. In this way the variance of the global flow field (both in magnitude and direction) is determined and it is used to compute the uncertainty in depth. This formulation allows to estimate the precision of the algorithm and the improvement in the accuracy of the measures, which can be achieved varying some key parameters like the number of images used. An experiment, performed on a real image sequence, is presented.

This paper discusses a knowledge-based system for diagnostic problem solving based on a multi-level representational structure and associated reasoning methods. The motivation behind this approach is to combine shallow evidential models for fault diagnosis with deep qualitative models that derive behavior from structural descriptions. In addition, the reasoning scheme utilizes historical data based on past experience for diagnosis. Using this integrated framework, we concentrate on the following issues: (i) Multi-level knowledge based system design, and (ii) Reasoning systems that exploit the multi-level representational structure for diagnostic problem solving. This system is applied to the diagnosis of a complex electro-mechanical system, specifically, the upper cargo door of the DC-10 aircraft in use at Federal Express Corporation.

It is difficult to diagnose faults and maintain weapon systems because (1) they are highly complex pieces of equipment composed of multiple mechanical, electrical, and hydraulic assemblies, and (2) talented maintenance personnel are continuously being lost through the attrition process. To solve this problem, we developed a portable diagnostic and maintenance aid that uses a knowledge-based expert system. This aid incorporates diagnostics, operational procedures, repair and replacement procedures, and regularly scheduled maintenance into one compact, 18-pound graphics workstation. Drawings and schematics can be pulled up from the CD-ROM to assist the operator in answering the expert system's questions. Work for this aid began with the development of the initial knowledge-based expert system in a fast prototyping environment using a LISP machine. The second phase saw the development of a personal computer-based system that used videodisc technology to pictorially assist the operator. The current version of the aid eliminates the high expenses associated with videodisc preparation by scanning in the art work already in the manuals. A number of generic software tools have been developed that streamlined the construction of each iteration of the aid; these tools will be applied to the development of future systems.

This paper describes a knowledge based approach to automatically generate Lisp programs using the Greedy method of algorithm design. The system's knowledge base is composed of heuristics for recognizing problems amenable to the Greedy method and knowledge about the Greedy strategy itself (i.e., rules for local optimization, constraint satisfaction, candidate ordering and candidate selection). The system has been able to generate programs for a wide variety of problems including the job-scheduling problem, the 0-1 knapsack problem, the minimal spanning tree problem, and the problem of arranging files on tape to minimize access time. For the special class of problems called matroids, the synthesized program provides optimal solutions, whereas for most other problems the solutions are near-optimal.

A prototypical on-line model-based system, LASALLE1, developed at the University of Illinois in collaboration with the Illinois Department of Nuclear Safety (IDNS) is described. Its main purpose is to interpret about 300 signals, updated every two minutes at IDNS from the LaSalle Nuclear Power Plant, and to diagnose possible abnormal conditions. It is written in VAX/VMS OPS5 and operates on both the on-line and testing modes. In its knowledge base, operator and plant actions pertaining to the Emergency Operating Procedure(EOP) A-01, are encoded. This is a procedure driven by a reactor's coolant level and pressure signals; with the purpose of shutting down the reactor, maintaining adequate core cooling and reducing the reactor pressure and temperature to cold shutdown conditions ( about 90 to 200 °F). The monitoring of the procedure is performed from the perspective of Emergency Preparedness. Two major issues are addressed in this system. First, the management of the short-term or working memory of the system. LASALLE1 must reach its inferences, display its conclusion and update a message file every two minutes before a new set of data arrives from the plant. This was achieved by superimposing additional layers of control over the inferencing strategies inherent in OPS5, and developing special rules for the management of the used or outdated information. The second issue is the representation of information and its uncertainty. The concepts of information granularity and performance-level, which are based on a coupling of Probability Theory and the theory of Fuzzy Sets, are used for this purpose. The estimation of the performance-level incorporates a mathematical methodology which accounts for two types of uncertainty encountered in monitoring physical systems: Random uncertainty, in the form of of probability density functions generated by observations, measurements and sensors data and fuzzy uncertainty represented by membership functions based on symbolic , stochastic or numerical models estimating the "plausible", "possible" or "expected" values of the system parameters. Examples from both the on-line mode and the testing mode of the system will be discussed to illustrate the present methodology.

This paper presents a conceptual model of object-based knowledge representation for the inspection and evaluation of structural integrity. Use of the model is illustrated with a practical knowledge-based system(KBS) developed in the domain of bridge fatigue evaluation. An overview of the open-system architecture of the model is first introduced, followed by discussion of the object abstraction in the domain knowledge. Three major kinds of entities represented by objects are categorized in the model. They are : the physical objects for structural topology/interconnectivity as well as individual physical components, the equation objects for quantitative analysis, and abstract objects for qualitative assessment and reasoning. The knowledge representation scheme adapted by this KBS renders the notions of self-inferencing and self-indexing of knowledge in objects. Basic inferencing mechanisms of this model are also described in the paper. Finally, a critique of the hybrid representation is presented along with suggestions for its enhancement.

This paper describes the work in progress for scheduling and planning paths for map-guided robots (AGVs) maneuvering in a dynamic factory floor environment. A schedule of a group of robots consists of a set of paths to be traversed and the start, stop and wait time at each point of a single robot's path segment. The optimal schedule will minimize the finish time of all the robots's tasks. We will show that the optimal routing problem for multiple robots is computationally intractable (NP-Complete). Our methodology is to generate reasonably good schedules in time by combining techniques from two different disciplines. We use a time map management system from artificial intelligence (AI) research to generate an initial schedule quickly, then we pass the initial schedule to an iterative refinement loop (or local search) to gradually improve it locally using an optimization process from operations research (OR). We will briefly recount the basic principles for map-guided autonomous navigation, which has been published in [Meng88b].

Optimizing processing time in some contour-cutting operations requires solving the so-called no-load path problem. This problem is formulated and an approximate resolution method (based on heuristic search techniques) is described. Results for real-life instances (clothing layouts in the apparel industry) are presented and evaluated.

This paper deals with the use of the Potential Field Approach as a means of collision avoidance and path planning for the "Generalized Mover's Problem" in the presence of obstacles. Although an important and fundamental problem, relatively little has been done using this approach over the last several years. It can also be seen that only a few path planning algorithms developed work directly with continuous state-spaces. The potential field approach was developed by Khatib in 1980. There is, however, considerable room for improvement and expansion of Khatib's algorithm. Khatib's potential functions were not defined for interaction between two general objects, but only for interaction between a certain subclass of objects and a point. Thus in this paper the following goal will be sought: * Extend Khatib's potential function method to the case of the interaction between two general objects, rather than just between a point and an object.

Hierarchic decomposition has been shown to be an effective technique for efficiently generating near optimal paths through a defended area. The objective is to avoid the combinatorial difficulties associated with searching large graphs by confining the search to specific advantageous subregions. Within the subregions, paths are constructed using the A heuristic search algorithm. The decomposition into subdomains introduces local horizon effects to the path generation process. The local horizon problem arises as a consequence of the required connection of paths generated by independent search procedures in contiguous subdomains. Several techniques are introduced to facilitate the inter-region handoff. The effects of subdomain size and handoff technique on path quality and efficiency are analyzed.

To guide a robot in a time varying environment, the initially planned path must be updated as the contents of the scene change. This research addresses the problem of planning a collosion free path for efficient visual guidance in scenes involving moving obstacles. Here we present a time efficient path planing based on quadtree data structure and parallel processing techniques, which is applied to the top view of a dynamic environment. Motion analysis is performed on a sequence of images taken from the top view of the scene in certain time intervals. The extracted motion information is then used for selecting the best path as the shortest distance nearer to the obstacle which is moving away from a reference point (e.g., camera, robot or a segment of initially planed path).

Large software projects contain a wealth of tested code. By extracting and reusing portions of code from these projects, programmer productivity can be greatly increased. Software reusability relieves the programmer from rewriting existing code. Thus, a greater amount of time can be spent in more innovative tasks in the software life cycle. This paper presents the preliminary results of a knowledge-based software reusability (SR) system in an image processing application. Key issues in software reusability are addressed and the implementation of a vision based system is discussed. The results show that challenges do exist in measuring the closeness of algorithms to user specifications. However, the key factor in determining the effectiveness of software reusability is the time saved.

Artificial Intelligence (AI) has found its way into Computer Aided Education (CAE), and there are several systems constructed to put in evidence its interesting advantages. We believe that images (graphic or real) play an important role in learning. However, the use of images, outside their use as illustration, makes it necessary to have applications such as AI. We shall develop the application of AI in an image based CAE and briefly present the system under construction to put in evidence our concept. We shall also elaborate a methodology for constructing such a system. Futhermore we shall briefly present the pedagogical and psychological activities in a learning process. Under the pedagogical and psychological aspect of learning, we shall develop areas such as the importance of image in learning both as pedagogical objects as well as means for obtaining psychological information about the learner. We shall develop the learner's model, its use, what to build into it and how. Under the application of AI in an image based CAE, we shall develop the importance of AI in exploiting the knowledge base in the learning environment and its application as a means of implementing pedagogical strategies.

Our reflection, on the elements of existing Image Processing systems (currently Image Processing, Symbol interpretation level, control mode, level of extracted features) and corresponding use of Artificial Intelligence, leads us to the definition of the SARPI system. This system performs the extraction of features of intermediate level. In the present first step of implementation, we limit ourself to line segments. They are associated to a descriptor including several parameters: position, angle, length, cross contrast, ... and precision on all of these parameters. SARPI applies to single or multiple features detection, it finds the requested feature(s) and produces its (their) total or partial (as requested) description. SARPI takes as input the set of requested parameters and available values of some feature parameters (typically: qualitative measure of contrast). Its main part is a control module automatically generating an Image Processing sequence to solve the problem (extraction of requested feature parameters). Rules allow to divide the problem in elementary ones with respect to the kind of input parameters. They allow the selection of an elementary function set according to the requested feature parameters and the known parameters; in this way, if the known information is insufficient, the control module selects and executes elementary functions that look for the missing information. Each of these elementary functions is pre-associated to Image Procedures and heuristics that select the appropriate procedures according to thc values of the input parameters. The parameters of the image processes are controlled automatically by the precision on the requested feature parameters. Particularly, the sampling steps of the parameters ρ and θ of the 'lough transform are calculated from the requested precision of the feature parameters. The selected Image Processings are applied on a region of the image that is calculated from the approximated position of the features, if given, or on the entire image, if not. The system has been tested on images of industrial objects with different conditions of illumination and contrast.

In this paper, a method is proposed for the integration of information which can be derived from the thermal infrared and visual modes based on the use of edge (dissimilarity) properties of the two types of images. The method involves the use of the Sobel operator to extract and classify edge points according to their strengths. A point-by-point comparison of edges from the visual and TIR images is made. Heuristics, supported by the physical processes affecting the image formation, are employed to give a probabilistic interpretation to each point in the images based on the strengths of edge points detected in the two images at the point. The validity of this approach is tested in a laboratory environment.

Rule-based reasoning when applied to locating destination addresses on mail pieces can enhance system performance and accuracy. One of the critical steps in the automatic reading and sorting of mail by machine is in locating the block of text that is the destination address on a mail piece. This is complicated by the variation of global structure on mail piece faces, e.g., return and destination addresses can be anywhere on the mail piece, in any orientation and of any size. Compounding the problem is the addition of extraneous text and graphics such as advertising.

Interpretation of X-ray motion pictures of the heart (cineventiculograms of the left ventricle) is complicated by the low contrast of the images and the elastic motion of the heart. We describe a framework for the application of knowledge in the form of diagnostically relevant models of the heart in motion to the problem of placing the heart boundary in each frame of the motion sequence. We employ a blackboard architecture [Nii 86;Weymouth 87] as a basis for the image interpretation. In this framework, local features, such as edges, are grouped to build a complete description of the moving heart. The knowledge is organized in a hierarchy with Knowledge sources (KS's) operating on different levels of the hierarchy. Opportunistic problem-solving techniques are used to control the order of activation of both data-directed and goal-driven KS's.

The affine-transformation matching scheme proposed by Hummel and Wolfson (1988) is very efficient in a model-based matching system, not only in terms of the computational complexity involved, but also in terms of the simplicity of the method. This paper addresses the implementation of the affine-invariant point matching, applied to the problem of recognizing and determining the pose of sheet metal parts. It points out errors that can occur with this method due to quantization, stability, symmetry, and noise problems. By beginning with an explicit noise model which the Hummel and Wolfson technique lacks, we can derive an optimal approach which overcomes these problems. We show that results obtained with the new algorithm are clearly better than the results from the original method.

Artificial intelligence is becoming an increasingly important subject of study for computer scientists, engineering designers, as well as professionals in other fields. Even though AI technology is a relatively new discipline, many of its concepts have already found practical applications. Expert systems, in particular, have made significant contributions to technologies in such fields as business, medicine, engineering design, chemistry, and particle physics. This paper describes an expert system developed to aid the mechanical designer with the preliminary design of variable-stroke internal-combustion engines. The expert system accomplished its task by generating and evaluating a large number of design alternatives represented in the form of graphs. Through the application of structural and design rules directly to the graphs, optimal and near optimal preliminary design configurations of engines are deduced.

One of the most difficult tasks a warship crew has to undertake is the ship's own defense. Nowadays, a warship is threatened by a variety of threats, launched from long distances and different platforms. The problem space of the warship is thus a highly multiaxis space. On the other hand, the warship is equipped with a variety of defense systems. A successful defense can be considered as a mapping of the solution space onto the problem space. Unfortunately, there are no known algorithmic solutions to this mapping problem that can satisfy the warship defense problem.

The engagement of penaided, nuclear armed Ballistic Missile Re-entry Vehicles (RVs) by a Theatre Missile Defence (TMD) system requires the use of a robust and adaptive discrimination system to identify warheads from accompanying decoys and other penetration aids. TMD systems will be characterised by their electronic countermeasure environments, and short flight times of the ballistic missile threat. In such environments time is of the essence for TMD commanders to make effective decisions about the allocation of defence weapon systems. The identification and classification, i.e the discrimination, of warheads in a theatre environment is therefore especially stressing requiring detailed analysis and quantification.

Neural networks and expert systems provide different ways to reduce the programming effort required to build complex systems. Adaptive neural networks are programmed merely by training them with examples. Rule-based expert system are developed incrementally merely by adding rules. Although neural networks seem best suited for low-level sensory processing and expert systems seem best suited for high-level symbolic processing, strikingly similar issues arise when these approaches are used in large-scale applications. Illustrative examples of such applications are presented and discussed.

In the last several years at the Robotics Institute of Carnegie Mellon University, we have been working on two projects for developing autonomous systems: Nablab for Autonomous Land Vehicle and Ambler for Mars Rover. These two systems are for different purposes: the Navlab is a four-wheeled vehicle (van) for road and open terrain navigation, and the Ambler is a six-legged locomotor for Mars exploration. The two projects, however, share many common aspects. Both are large-scale integrated systems for navigation. In addition to the development of individual components (eg., construction and control of the vehicle, vision and perception, and planning), integration of those component technologies into a system by means of an appropriate architecture is a major issue.

In this talk I will describe recent progress in developing problem solving architectures that learn from interactions with external environments. Previous work in planning and problem solving has often ignored the special constraints and uncertainties that arise from interacting with a real environment. In addition, learning was seen as an add-on that could be ignored until the planning system was complete. Similarly, most learning work has been carried out in simulated domains, or at least in domains where interaction with an environment is mininized. Recently, several systems have been developed that attempt to integrate learning and problem solving while interacting with an external environment.

A robot vision system should perform a variety of tasks accurately and robustly. The system should posses the capabilities to acquire images in a complex environment, to perform low level image processing, to extract primative features and critical information such as depth information, and to derive high level description of the scene. This paper describes extensions of a practical vision system which can acquire and process images under different viewing geometries and extract 3-D information using a pair of stereo images acquired using a single camera mounted on the hand of robot, using region-based stereo matching scheme. The performance of the system is tested by conducting several experiments utilizing a laboratory testbed.

This paper describes an architecture for the control of robotic devices, and in particular of anthropomorphic hands, characterized by a hierarchical structure in which every level of the architecture contains data and control function with varying degree of abstraction. Bottom levels of the hierarchy interface directly with sensors and actuators, and process raw data and motor commands. Higher levels perform more symbolic types of tasks, such as application of boolean rules and general planning operations. The implementation of the layer has to be consistent with the type of operation and its requirements for real time control. In the paper we present one implementation of the rule level with a Boolean Artificial Neural Network which would have a response time sufficient for producing reflex corrective action at the actuator level.

This paper presents a new algorithm for determining the position and orientation of objects. The problem is formulated as an optimization problem using dual number quaternions. It is shown that this reduces to an eigenvalue problem for which standard software library routines can be used to obtain the solution.