 |
Description  |
|
|
TECHNICAL FIELD
The present invention relates in a first aspect to expert systems, and in particular, to a domain independent expert system and method employing inferential processing within a hierarchically-structured knowledge base and non-inferential
accessing of information within one or more associated utilities. In another aspect, the invention relates to a unique hierarchical structure for representing information in a knowledge base for access by an inference kernel and to a knowledge editor
for facilitating development of such a knowledge base by a domain expert. In still another aspect, the invention relates to interactive multimedia/hypermedia systems and methods, particularly for training and certification applications.
BACKGROUND ART
CIM (computer-integrated manufacturing) is viewed as an emerging technology in the domain of manufacturing. The concept of CIM is that the whole performs better than the sum of the individual parts. In order to make a system run smoothly with
minimum delay (i.e., continuous flow manufacturing) it is necessary to have a diagnostic system for discovering any cause of system failure. It is desirable that this diagnostic system be capable of performing its task as fast as possible since the
duration of the system's down time is very closely related to productivity and cost. Thereby, there is a need for intelligent diagnostic systems. In artificial intelligence and expert systems, diagnosis has been given more attention in recent years,
including trouble-shooting in electronic circuits and medical diagnosis.
There have been a variety of approaches taken by various researchers for creating intelligent diagnostic expert systems. These approaches range from shallow reasoning using compiled rules to model-based deep reasoning systems that reason by
exploiting causal, structural, and functional relationships. Some approaches even combine shallow and deep knowledge reasoning. It has been hypothesized by some that the use of deep representations of entities to be diagnosed is superior to empirical
knowledge about associations between malfunctioning parts of an entity and symptoms. The rationale for such a conclusion is that one could not exhuastively catalog all such associations, and without such a catalog, a heuristic-based diagnostic system
becomes brittle and fails when presented with a case that it does not understand.
On the other hand, deep knowledge representation is based on models that are difficult to construct, especially models that exhibit the technology intent of the designer. Further, it is unlikely that models will mirror the future behavior of
entities of any complexity, particularly with regard to providing information about multiple perspectives. Moreover, models are likely to be domain specific and only some fraction of knowledge will be transferable from one diagnostic system's knowledge
base to another.
It is also recognized that rule-based systems become increasingly difficult to understand and maintain as the number of rules grow. While a reasonable rule-based expert system shell can assist a domain expert in formulating cause-and-effect
rules, a collection of such rules typically will not function as an expert system, except for the most simple cases. To overcome these limitations, some expert system shells allow the encoding of strategic and object-level knowledge as meta-rules.
However, this requires extensive knowledge of the programming paradigm and the development environment. Another class of tools provides a search algorithm for a flat problem-space representation. Although the problem representation is simplified, the
search complexity for a problem of solution length L, and a search space branching factor B has a worst case complexity O(B.sup.L).
As an alternative, it has been suggested that it is actually more fruitful in certain domains to concentrate on constructing models of belief organization for diagnosis rather than models of physical entities. The concept of belief potentially
has a wider scope than explicitly defined knowledge. A method of organization of beliefs has been proposed for diagnostic problems that provides explicit belief organization with implicit organization of knowledge about physical device characteristics,
functionality, and behavior. The method is claimed to provide reasoning about belief among alternatives, is extensible, and can be scaled to problem size. Further, it is asserted that belief manipulation coupled with information about fault history,
events, and symptoms is sufficient to secure a good diagnostic result. The approach presented herein modifies and combines behavioral knowledge presentation with structural knowledge presentation to identify a recommended action.
It has long been recognized that hierarchical problem solving can be used to reduce search space within an expert system. It has been shown that the complexity of search space for a problem of solution length `L` and search space branching
factor `B`, is reduced from O(B.sup.L) for single-level representation, to O(.sqroot.L) B.sup..sqroot.L for two-level representation, and to O(L) for multi-level representation. This analysis is based on the assumption that the abstraction divides the
problem into O(L) constant size problems that can be solved in order, without backtracking. It can be shown that even in domains that do not satisfy the assumption, the use of hierarchical problem solving still produces significant reductions in search
space. Hierarchical problem solving and knowledge processing techniques have been used in several reported expert systems. The concepts presented herein provide enhancements over such prior techniques.
Experienced engineers, technicians, and system operators typically develop their own diagnostic flowcharts, procedures and shortcuts over time. Such materials are utilized during daily activities, and only occasionally to such individuals refer
to basic principles and documented diagnostic procedures to solve problems. This has been a natural response to the large volume of maintenance and operation manuals offered by tool vendors and process developers of a manufacturing enterprise. Further,
the majority of expertise accumulated by technicians and operators is usually not shared among different teams and can be lost due to transfers or job changes. In addition, local upgrades/modifications, which might not be explained in a vendor manual,
can be scattered among personal notebooks or other notes near the machines or technician workbenches. The challenge of knowledge engineering in such an environment is to accommodate various sources of expertise and to guide and influence the expert
toward considering all aspects of the environment beyond the individual's usual activities and concerns.
The knowledge acquisition task is often complicated by the fact that human experts have not analyzed the contents of their thoughts, so that they are not explicitly aware of the structure of their knowledge. As a result, the intermediate steps
and the reasoning seems obvious to them and they cannot clearly provide an overall account of how decisions are made, at least not at a level of detail required for expert system development. There are a number of approaches to knowledge acquisition.
The three basic approaches are interview, interaction (supervised) and induction (unsupervised).
Historically, interview has been the most prevalent method of knowledge acquisition. It is, however, highly dependent on the knowledge engineer, is often time consuming and expensive, and is typically viewed as the knowledge acquisition
bottleneck. It is also recognized that for knowledge intensive and task oriented applications, supervised knowledge acquisition is more efficient. Large database and data intensive applications are good candidates for unsupervised knowledge
acquisition.
On the other hand, many expert systems use task-oriented shallow knowledge. In knowledge acquisition it is sometimes necessary to carry out excursions into deep knowledge in order to understand and validate associated shallow knowledge. This
requires involving experts in knowledge acquisition, since they are in a position to understand the deep knowledge and its relation to the shallow knowledge. In addition, studies performed on the quality, efficiency, and accuracy of knowledge bases have
shown that knowledge bases developed by the expert (versus the knowledge engineer) tend to be smaller, provide larger number of pathways associating evidence to diagnostic hypothesis, include more critical attributes, and provide richer clusters of
knowledge. This is another argument in favor of providing domain experts with a larger role in knowledge acquisition.
As a related problem, existing multimedia training applications are typically developed by a media production specialist, and are usually delivered on read-only storage medium (CD-ROM, video disk). Such applications exhibit huge initial start-up
costs, do not provide any intelligent feedback or control, and require specialized hardware and/or software, meaning that any modification and/or upgrade will be expensive and time consuming.
Manufacturing enterprises can employ hundreds and sometimes thousands of permanent and temporary system operators and technicians. Currently, a multitude of methods are used for educating and assisting such manufacturing personnel. These
methods include informal, unstructured training sessions, printed `in-house` manuals, classroom instruction, and walk-through orientations to name but a few. In the manufacturing environment, the student population grows with every group of new
employees, whether temporary or permanent. This student group is typically large and decentralized and cannot be released from the manufacturing line simultaneously to attend a standardized training course.
Interactive multimedia training and certification can present consistent subject matter, on a flexible twenty-four hour, seven day per week schedule. The subject matter delivered to the trainee is guaranteed to be consistent, thus avoiding
reliance on a thorough presentation of material by a knowledgeable technician. Use of an on-line computer based training methodology would eliminate a back-level problem. Currently, with the use of printed documents there is always an uncertainty as to
whether the line operator is using the most current version or whether an operator's training in fact covers a latest version of a processor tool upgrade. By making the information available on-line, positive control over the information being
disseminated is obtained.
Computer-based training and intelligent tutoring systems are typically based on a single, and rather simple user model. Regardless of the familiarity or lack of familiarity of the trainee with the topic, all trainees go through the same training
process. A new employee who has never worked in a similar environment is given the same training material as an employee who has many years of related experience and might have been transferred to a new assignment from a similar area. Certification and
qualification procedures are usually conducted orally in an ad-hoc fashion and are subject to a trainer's judgment and biases. In addition, there is no formal methodology for increasing the responsibility of a trainee as the training proceeds. In order
for a computer-aided training system to acquire the necessary flexibility, it should distinguish between several types of students and structure the training material according to a student's needs and background.
Multimedia in general, and motion video, animation and audio in particular, are believed very appealing to personnel involved in maintenance, diagnostics and training applications. However, in many cases a major drawback is the cost and
logistics of hardware and software required to implement such a multimedia system. This is complicated by the fact that most manufacturing facilities include tens if not hundreds of workstations. If an application requires special hardware and/or
software licensing, then cost becomes significant.
All the above drawbacks and problems associated with existing expert systems and multimedia/hypermedia applications are addressed by the systems and methods presented herein.
DISCLOSURE OF INVENTION
Briefly described, the present invention comprises in a first aspect an expert system responsive to provided external information. The expert system includes a first storage means and a second storage means. The first storage means stores a
hierarchically-structured knowledge base containing inferentially processable information, while the second storage means contains at least one utility comprising non-inferentially accessible information. A processor is coupled to the first storage
means and the second storage means for processing the hierarchically-structured knowledge base and accessing the at least one utility, respectively. The processing means includes means for inferential processing of information in the
hierarchically-structured knowledge base and means for non-inferential accessing of information in the at least one utility. The inferential processing means and the non-inferential accessing means are responsive to the provided external information.
In another aspect, the invention comprises a hierarchically-structured knowledge base for an expert system. The knowledge base comprises a hierarchical decomposition having a plurality of nodes coupled together in three distinct levels. An
uppermost level comprises a behavioral knowledge level, a middle level comprises a structural knowledge level and a lowermost level is an action level. The action level is implemented as at least one decision tree. The three distinct levels are
interconnected such that inference processing can occur through the hierarchically-structured knowledge base from the behavioral knowledge level through the structural knowledge level to the action level.
In yet another aspect, an intelligent system is presented responsive to provided external information. The system includes memory means for storing multimedia displayable information, which is non-inferentially accessible. An intelligent
control system, coupled to the memory means, includes a hierarchically-structured knowledge base containing inferentially processable information and processing means coupled to the hierarchically-structured knowledge base. The processing means includes
means for inferential processing of information in the hierarchically-structured knowledge base and means for non-inferential accessing of the multimedia displayable information in the memory means. The means for non-inferential accessing of multimedia
displayable information is responsive to the means for inferential processing of information and the means for inferential processing of information is itself responsive to the provided external information.
In a further aspect, a computer system is provided having memory means for storing multimedia displayable information and display means for displaying information to a user of the computer system. A processing means, coupled to the memory means
and the display means, includes hypergraphic processing capabilities associated with a predefined graphics image displayable on the display means. The hypergraphic processing capabilities include means for providing the user of the computer system with
an options menu upon user selection of the predefined graphics image when displayed by the display means. The options menu has at least two user selectable options, each of which is linked to a separate portion of the multimedia displayable information
stored in the memory means. Each separate portion of the multimedia displayable information presents information to the user in a different multimedia format.
In a still further aspect, a method for defining a hierarchically-structured knowledge base for an intelligent system is presented. The method includes the steps of: creating multiple knowledge trees from a plurality of nodes and associated
attributes including at least one action knowledge tree, at least one structural knowledge tree, and a behavioral knowledge tree; and linking the knowledge trees together to form a hierarchical decomposition such that the hierarchically-structured
knowledge base has three distinct levels, an uppermost level comprising the behavioral knowledge tree, a middle level comprising the at least one structural knowledge tree, and a lowermost level comprising the at least one action knowledge tree.
Also presented is a processing method for an expert system responsive to external information inputted by a user of the system. The processing method includes the steps of: inferentially processing information in a hierarchically-structured
knowledge base interactively with the external information inputted by the user of the expert system; and during the inferential processing, non-inferentially accessing information in at least one predefined utility separate from the
hierarchically-structured knowledge base. Additional methods and method enhancements are also provided herein.
To restate, provided herein is a domain independent expert system and processing method employing inferential processing within a hierarchically-structured knowledge base in conjunction with non-inferential accessing of information within one or
more associated utilities. Knowledge representation architecture is based on hierarchical knowledge representation principles with a novel decision tree architecture consistent with a proposed knowledge engineering methodology. Conflict resolution
employs an entropic based approach which allows domain experts to describe the heuristics practiced in resolving conflicts and unanticipated situations, taking into consideration the practicality and overall cost of the solution.
In a diagnostic implementation, knowledge processing provides useful information on the nature of a problem, even if the exact problem(s) remains unidentified. The knowledge engineering methodology is based on supervised knowledge acquisition
principles and provides a complete knowledge engineering strategy directed towards a domain expert. Acquisition guidelines and a Knowledge Editor provide a novel integrated solution for reducing the knowledge engineering bottleneck, and improving the
quality of the final system. Development and deployment of an interactive diagnostic expert system is possible on standard workstations, thereby providing a low cost delivery platform, as well as enabling the integration of multimedia capabilities of
graphical workstations into the diagnostic applications.
Also presented is a complete and integrated methodology and architecture for development of intelligent interactive multimedia/hypermedia computer-aided training/education and qualification/certification applications. A control and management
knowledge base serves as an intelligent tutoring system framework. Training, certification, and on-line documentation databases are integrated with the knowledge based control and management. Applications developed under this methodology and
architecture reside entirely on hard disk or removable/rewritable storage medium (such as optical storage), and can be used in stand-alone or network configuration.
BRIEF DESCRIPTION OF DRAWINGS
These and other objects, advantages and features of the present invention will be more readily understood from the following detailed description of certain preferred embodiments of the invention, when considered in conjunction with the
accompanying drawings in which:
FIGS. 1a, 1b & 1c are examples depicting the hierarchical data structure of a knowledge base in accordance with the present invention, wherein FIG. 1a depicts universal attributes, FIG. 1b shows global attributes and FIG. 1c is an example of a
Condition Action Tree (CAT);
FIGS. 2a, 2b & 2c depict examples of diagnosis pursuant to the present invention using various condition action trees;
FIG. 3 is one processing embodiment for defining a knowledge tree (BHKB, SHKB, CAT) in accordance with the present invention;
FIG. 4 depicts one embodiment of a main menu screen of a Knowledge Editor (KE) developed in accordance with the present invention to guide a user in partitioning and defining a diagnostic knowledge base;
FIG. 5 is an example of a Knowledge Editor screen facilitating the definition of nodes and their attributes, and how nodes may be linked together to define a system in accordance with the present invention, wherein both template-based and visual
programming capabilities of the KE are shown;
FIG. 6 is an example of a knowledge representation hierarchy pursuant to the present invention;
FIG. 7 is another example of a three level hierarchy in accordance with the invention, wherein structural level knowledge bases are linked to terminal nodes of a behavioral level knowledge base, and condition action trees are linked to the
terminal nodes of the structural level;
FIG. 8 depicts representation of events as time-stamped branches of corresponding condition action trees;
FIG. 9 is an example of a condition action tree (CAT) showing a root node, an entry node and various children nodes connected thereto;
FIG. 10 is a flowchart of one embodiment of inferential knowledge base processing by an inference kernel in accordance with the present invention;
FIG. 11 is a perspective view of a computer system upon which an expert system and/or a multimedia/hypermedia system in accordance with the present invention may be implemented;
FIG. 12 is a block diagram representation of possible component overlaps of both an expert system and a multimedia/hypermedia system in accordance with the present invention;
FIG. 13 is an example of one embodiment of a graphical user interface window in accordance with the present invention;
FIG. 14 charts IBM's common user access (CUA) guidelines and user interface design principles employed in a graphical user interface in accordance with the present invention;
FIG. 15 depicts one embodiment of a graphical user interface window partitioning in accordance with the present invention;
FIGS. 16a.varies.16p depict standardized programmable templates (referred to as "logical pages") proposed for use in a multimedia/hypermedia system in accordance with the present invention;
FIG. 17 is an example of a logical page partitioning of a multimedia/hypermedia module employing a template of FIGS. 16a-16p;
FIG. 18 is an image useful in explaining hypergraphic hot spot functions in accordance with the present invention;
FIG. 19 is one embodiment of a logical page attribute menu useful in customizing logical page templates in accordance with the present invention;
FIG. 20 is a block diagram representation of one embodiment of a knowledge-based multimedia training/certification system in accordance with the present invention;
FIG. 21 is a block diagram representation of a multilevel training/certification user model in accordance with a multimedia system pursuant to the present invention;
FIG. 22 is a display image representation useful in describing a hot spot pop-up menu for a hypergraphics implementation in accordance with the present invention;
FIG. 23 is a flowchart of one embodiment of processing to create a hypergraphic hot spot in accordance with the present invention;
FIG. 24 is a flowchart of one embodiment of processing to create a hypergraphic function pop-up menu in accordance with the present invention;
FIG. 25 is one embodiment of a main menu of a "poor man's video" (PMV) editor for authoring motion video clips in accordance with the present invention;
FIG. 26 graphically depicts PMV processing in both run-time and compile-time in accordance with the present invention;
FIG. 27 is a flowchart of one embodiment of compiler processing to create a PMV library block in accordance with the present invention; and
FIG. 28 is a flowchart of one embodiment of player processing for viewing a PMV in accordance with the present invention.
BEST MODE FOR CARRYING OUT THE INVENTION
Various terms used herein will first be explained. "Diagnosis" is defined as inferring system malfunctions from observable elements, factors, or circumstances or identifying the proper association between symptoms and their causes. In other
words, diagnosis is the process of finding the location and nature of a system malfunction and even suggesting a remedy. A "system" is defined as a complex of interacting objects that have some process behavior. The following are examples of systems: a
VLSI chip; a computer program; a manufacturing tool or machine (e.g., wafer polisher, oxide growth furnace, etc.); a manufacturing group; and a human.
By way of example, a semiconductor manufacturing process will be discussed herein. In a semiconductor fabrication environment, a "malfunction" can be an error in a computer program, a defect in a VLSI chip, an incorrect specification of a
manufacturing recipe, a failure of a manufacturing tool to function properly, etc. A "symptom" of a malfunction is observed when the system behaves in a way that is not expected. In other words, a symptom is a discrepancy between observed, or actual
behavior, and an expected, or predicted system behavior. A symptom is an observable condition which indicates an abnormal behavior or a possible malfunction. Hence, when a symptom exists, there must be a condition (fault) which causes the symptom. A
"condition" is an underlying, invisible, real problem. A symptom on the other hand, is a visible manifestation of one or more condition(s), i.e., evidence of a condition(s), such as a tool malfunction or a system error message. Diagnosis therefore
means identifying the conditions after observing or indirectly detecting the symptoms. An "initiative" is an action or a set of actions necessary to recover from a malfunction, or a set of actions (operations) that will transform a system to a desired
state.
As noted initially, experienced engineers, technicians, and operators usually develop their own diagnostic flowcharts, procedures, and shortcuts over the years. They utilize these during their daily activities and only occasionally refer to
basic principles or documented diagnostic procedures to solve problems. This has been a natural response to the large volume of maintenance and operation manuals offered by tool vendors and process developers of a manufacturing enterprise. The majority
of the expertise accumulated by technicians and operators is usually not shared among different teams and can be lost due to transfers or other job changes. In addition, local upgrades and modifications (which do not end up in the vendor manuals) can be
scattered among personal notebooks, notes on the machines, and technicians' workbenches. The challenge of knowledge engineering in such an environment is to accommodate various sources of expertise and to guide and influence the expert toward
considering all aspects of the environment, including those beyond the individual's activities and concerns. This is necessary for eliciting complete and accurate knowledge and associated reasoning strategies.
There are a number of approaches to knowledge acquisition. However, the three basic approaches are:
1) Interviewing;
2) Supervised interaction; and
3) Unsupervised induction.
Historically, interviewing has been the most prevalent method of knowledge acquisition. It is however highly dependent on the knowledge engineer, and is often time consuming and expensive. It is also recognized that for knowledge-intensive and
task-oriented applications, knowledge acquisition by supervised induction is more efficient than interviewing or unsupervised induction. Large database and data-intensive applications are good candidates for unsupervised knowledge acquisition.
The construction of a knowledge base is currently a bottleneck in the development of AI systems. This is because it usually involves interviews with an expert, analysis of the interview records and protocols, and then formulation of the decision
rules. Thus, the knowledge acquisition problem is time-consuming and does not always guarantee the validity of the rules obtained. An important method to overcome these problems is to employ inductive learning from examples. With this approach, the
expert is asked to provide good examples and counter examples of decisions, rather than to formalize his knowledge in terms of decision rules. These examples are then processed by the knowledge engineer or by a computer to produce decision rules.
The knowledge acquisition task is often complicated by the fact that human experts have not analyzed the contents of their thoughts, so they are not explicitly aware of the structure of their knowledge. As a result, the intermediate steps in
their reasoning seem obvious to them but they cannot clearly provide an overall account of how their decisions are made, at least not at the level of detail required for expert system development.
On the other hand, many expert systems typically use task-oriented shallow knowledge. Notwithstanding this, in knowledge acquisition it is sometimes necessary to carry out excursions into deep knowledge in order to understand and validate the
associated shallow knowledge. This traditionally requires involving experts in knowledge acquisition, since they are in a position to understand the deep knowledge and its relation to shallow knowledge. In addition, studies performed on the quality,
efficiency, and accuracy of knowledge bases have shown that knowledge bases developed by a domain expert (rather than by a knowledge engineer) tend to be smaller, provide a larger number of pathways linking evidence to diagnostic hypothesis, include more
critical attributes, and provide richer clusters of knowledge. This is another argument in favor of providing experts with a larger role in knowledge acquisition.
Considering the above difficulties, the nature of applications targeted by the present methodology, and an overall goal of enabling the domain expert to develop the diagnostic application, a supervised knowledge acquisition methodology geared
toward domain experts is proposed herein. This methodology is comprised of two stages, namely:
A) Compile, organize, partition, and document the knowledge and associated reasoning processes according to predefined guidelines (explained below); and
B) Use the Knowledge Editor software tool (presented below) for knowledge entry and verification.
The two stages of the present approach are accomplished in four steps. The first step is educating and familiarizing the potential user with the capabilities and limitations of the knowledge-based system (KBS) and multimedia technology
(discussed below). This step includes estab | | |
