Rich Warren
Expert System technology is an advanced programming technique that provides a programming capability for incorporating symbolic representation of facts, data, and heuristic knowledge in conventional software packages. Expert systems capture and distribute the human expert's expertise in making judgments under various conditions. They clone experts by capturing knowledge that is perishable, scarce, and vague and difficult to apply, distribute, or accumulate. Expert systems afford cost-effective services in areas that require dymbolic processing of knowledge and rule-of-thumb judgmental problem-solving methods similar to those used to select common gamming strategies.
1.1 Permanent Storage
The expert system used in AEST is a proprietory system that consists of a knowledge base, an inference engine, and a forward chaining mechanism. Figure 1 shows that a number of knowledge bases may reside in permanent storage. These knowledge bases are engineered by the projects Subject Matter Expert working closely with a knowledge engineer through a number of formal knowledge acquisition sessions. Knowledge bases may, for example, be constructed for an threat assignment as well as offensive and defensive posturing and maneuvering.
1.2 Knowledge Base Management
Figure 2 and Figure 3 both show that a number of knowledge base management tools exist in support of this AEST expert system. Multible knowledge bases are supported which allow the systems knowledge to be neatly partitioned into separate data files and internal data structures. As a knowledge base is programmed using linked list programming constructs, as shown in Figure 4 , the additional overhead incurred in multiple knowledge bases is negligable. Further, these knowledge bases are loaded into the computers memory at execution time and the modular approach supports a blackboard expert system paradigm. Loading knowledge bases in this manner allow for the domain expert and knowledge engineer to more easily verify and validate the knowledge bases as no need for a software engineer familiar with software development, compiler and debugger environments is needed. That the system employs a rather simple grammar, adds to the ease with which the systems knowledge bases are constructed.
A knowledge base debugging environment has also been constructed. The systems error messages and user defined degugging comments may easily be turned on or off through a single execution time command. A print facility allows the contents of any of the systems variables or facts to be printed to the standard output device. Additionally, ASCII text strings of arbitrary length may also be printed to the standard output device. Finally, the use of in-line comments are encouraged so that the contents of the knowledge base may be explained or described in greater detail. Entire blocks of rules may also be commented out in debugging or verifying and validating the systems knowledge bases.
1.3 Inference Logic
The systems inferencing logic is driven by a forward chaining mechanism developed over forty years ago for production systems. When the rule interpreter is forward chaining, if premise clauses match the situation, then the conclusion clauses are asserted. Once the rule is used, or has fired , it will not be used again in the same search. However, the fact concluded as the result of that rule's firing will be added to the knowledge base. This cycle of finding a matched rule, firing it, and adding the concludion to the knowledge base will be repeated until no more matched rules are be found. Figure 5, below shows a more detailed logic flow diagram of the forward chaining inferencing mechanism used in the AEST inferencing system.
The expert systems logic also supports variable binding. Binding, as shown in Figure 6, is useful in reducing repeated computations within a function. If an expression needs to be evaluated more than once in a rule, the system's bind function will assign a local variable to the initial value and then evaluate that resultant expression throughout the remainder of the rules execution.
The four primary arithmatic operators are supported in the AEST inferencing environment. Multiplication allows rules to modify the contents of the system's registers temporarily while evaluating the left hand side of a rule. The rule may require, for example, that a condition exist where only half a distance to a given object exceed some threshold. In this example one may elect to state, within the rule, that the distance times one half must exceed a threshold or alternateively, devision may be used to assert that the distance devided by some number must exceed a given threshold. Addition and subtraction are likewise supported within the inferencing logic.
The three primary logical operators, as shown in Figure 7, are also supported in the AEST inferencing environment. These operators allow for values, possibly variable values, to be compared against one another for truth. With the inferencing logic available in this environment, one may query the truth of statements using the greater than, the less than or the equal to logical operators. Additionally, the Boolean operator AND is supported.
Often it is desirable, from a runtime performance and rulebase development cost, to impliment one or more functions external from the knowledge base. An example where such savings might be appreciated is found in computing the distance to a given object. If there are several rules that must compute a distance, it then becomes valid to program the range function in an external source file to be compiled at execution time. With this scheme, the knowledge base developer only need know that an external range function exist, and that there is a well defined interface to the function. The single external function may now be called frequently throughout rulebase execution without incurring additional runtime and development costs.
The inferencing logic also supports both real-time and recorded playback state updates. During the development and maintenance phases of the systems rulebases, it is convient and cost effective to run the inference engine in a stand alone mode separate from the full application development environment in which the AEST is normally hosted. This stand alone operation is achieved through a collection of data files captured while a number of trial runs are carried out. A parser has been built to read the data contained in these files and fill the appropriate application state vector element that one would expect to be filled during an integrated run. This user selected operator's mode switch is transparent to the execution of the systems inferencing mechanisms.
1.4 Fact Base Management
A number of fact base management tools as shown in Figure 8, have been developed to support the AEST inference engine. Assertion allows the system to insert a fact into the fact base. The proceedure used in the AEST inference engine takes advantage of a well proven and time tested B-tree insertion algorithm that gurarentees good run time performance.
Retraction is also supported to allow any fact whose value is no longer true to be removed from the factbase. This procedure is commonly refered to as truth maintenance and also uses a well proven and time tested B-tree deletion algorithm that gurarentees good run time performance.
As the forward chaining mechanism fires any and all rules in the knowledge base whose left hand side conditions are satisified there must be a method for traversing the fact base data struture. The AEST inference engine takes advantage of a well proven and time tested B-tree search algorithm that gurarentees good run time performance.
Figure 9, above shows that multiple fact bases may be maintained in the AEST inferencing system at any given time. This utility is useful for maintaining a System History Log where access to the state of the environment at some point in time past is required. As a fact base is programmed using linked list programming constructs the additional overhead incurred in maintaining a minimal number of C++ pointers is negligable.
Trade Off Analysis: run time eficiency or flexibility
Agent Inference Engine: showing perminant storage, knowledge base management, inferencing logic, fact base management, and dynamic memory
Closer Look: knowledge and fact base management and inference logic
Indepth Look: knowledge base development environment showing support for management of multiple knowledge bases loaded at execution
Indepth Look(cont.): debug and comment statements and playback
Data Structure: graphical representation of KB nodes
Parser: closer look at grammar and syntax
Fact Node: an expanded view of the fact node
Data Structure: a graphical representation of the fact graph
Fact Base Management: insertion, retraction, search
Inference Alorithm: from get next rule to execution complete
Supporting Algorithms: Forward chaining, parallel execution and variable binding
Supporting Algorithms: truth maintenance, logical operators, boolean operators, and external function calls
(c) Richard G. Warren - all rights reserved
