Freeman A. Kilpatrick Jr., kilpatrf@plk.af.mil
Gregg H. Gunsch, ggunsch@afit.af.mil
Eugene Santos, esantos@afit.af.mil
Abstract
Intelligent Tutoring System (ITS) development is a knowledge-intensive process, requiring a significant knowledge-engineering effort to encode the large amount of knowledge required for dynamic instructional interaction. We propose an generic architecture for intelligent training systems that requires less knowledge than other approaches because it only requires two domain-specific knowledge components, a operator expert knowledge base and a domain simulation. These components are only used at the interface level, allowing them to be developed independent of the training system, facilitating the transition of the system to a variety of domains, as well as the potential use of pre-existing knowledge.
Introduction
Traditionally, Intelligent Tutoring System (ITS) research has concentrated on the educational aspects of computer-based teaching; Shute (1994) cites the great ITS debates of the 1990's as:
Very little research has been done with respect to how we can make building ITSs easier; the current research has dealt more with how much we can build into an ITS. Like most AI endeavors, ITS construction is a knowledge intensive task, requiring a significant knowledge engineering effort to encode domain knowledge into a form usable by an ITS. Anderson (1985) estimates that traditional (non-intelligent) computer-aided instruction (CAI) systems require 200 hours of development per hour of instruction; he estimates ITSs require an order of magnitude greater. Orey (1993) provides another estimate of 500 hours development per hour of instruction for an ITS. Part of the reason for this huge development time is the fact that most ITSs are custom-built for a particular domain, requiring that the entire ITS framework be constructed from scratch for each application. Additionally, the knowledge requirements for an ITS are significantly greater than a traditional CAI system, because the depth of the instructional process is so much greater. Clearly, this huge development time is a bottleneck in the process of transitioning ITSs from the development lab to the classroom, and represents a serious impediment to the widespread use of ITSs.
Our research involves the subset of ITSs that are used for intelligent training of operators of Complex Dynamic Systems (CDS). We have developed a domain-independent architecture for an intelligent training system that only requires domain knowledge input in the form of a operator expert knowledge base and a simulation of the CDS. The interaction of these components, combined with a state-space search technique and machine learning induction provide the remainder of training knowledge required for procedural training. Additionally, these components are only accessed at the interface level, allowing them to developed with virtually any tool, and greatly facilitating the transition of the architecture to different domains. This approach requires less knowledge engineering than other approaches, and has the potential for greatly reducing the knowledge maintenance requirements for an intelligent training system as well. The remainder of this paper will discuss our architecture, followed by our techniques for simulation state-space search and rule induction.
Architecture
Our architecture is based on the standard ITS model (Wenger, 1987), consisting of an expert module to represent domain expertise, a tutor module to represent pedagogical expertise, and a student model to represent an estimate of the student's knowledge state. These components work in concert to provide an instructional interaction that dynamically adjusts to the needs of the student, both in content and form. This is in contrast to a conventional computer-aided instruction (CAI) system, which implements a pre-designed, static presentation. Our work differs from a conventional ITS, however, because we acquire the bulk of our training knowledge automatically through the interaction of a simulation and a knowledge base combined with an automated scenario exploration process and machine learning induction.
Figure 1 shows the architecture for our system, called SCIUS -- Self-Creating Intelligent "Un-authoring'' System. "Un-authoring" differentiates our system from a conventional authoring system that requires a course author to encode domain knowledge into a form compatible with the authoring system. The knowledge for SCIUS can be created (or pre-existing knowledge can be used) without any knowledge of the fact that it is going to be used for a training system. Essentially, a training system can be created in SCIUS without a course author. The SCIUS architecture is designed to integrate tightly with the operator's natural environment; the majority of the tutorial interaction is conducted through the normal operator interface to the CDS simulation. The Knowledge Acquisition Module (KAM) is the heart of the architecture; this module is responsible for governing scenario exploration through the simulation state space and rule induction from the knowledge base. This provides the bulk of the domain-specific knowledge used for student training; this knowledge fills out the expert module and the tutor module. These processes will be described below.
Figure 1
Scenario Exploration and Rule Induction
The purpose of scenario exploration is to explore the state space of the simulation to provide a set of scenarios that is representative of the situations the operator is likely to face. These scenarios are used for two purposes. First, they provide a broad set of scenarios to use for training and testing; this is in contrast to conventional scenario generation techniques that involve generation of scenarios "by hand,'' necessarily limiting the variety of scenarios that can be used. Additionally, scenario generation allows the automatic generation of new scenarios whenever the knowledge base or the simulation changes. The second purpose of scenario exploration is to find a set of scenarios of sufficient variety to allow for appropriate rule induction. Induction finds the rules implicit in the scenario-action pairs; the appropriateness of the induced rules is dependent upon having a representative set of scenarios to use as training examples.
Basically, scenario exploration works by treating the simulation as a transition graph; simulation states are nodes, and transitions between nodes are caused by either actions or time. The exploration process first finds an expert path through the simulation using the expert knowledge base as guidance. This is accomplished by setting the simulation to a state, then using the knowledge base to determine a recommended action for that state. Next, the action space, or the space of all possible control actions that the operator can implement, is sampled to provide a transition to a new state. This is accomplished by randomly generating an action from a pre-defined definition of the action space, then implementing that action in the simulation, taking the simulation to a new state. This process provides successively deeper permutations away from the ideal expert path, allowing us to constrain the space to a reasonable proximity to the expert path.
Rule induction uses a modified version of ID3 (Quinlan, 1986). The explored scenarios are represented as state-action pairs; all states leading to a particular action are treated as positive examples of a concept while other states are treated as negative examples. Induction finds the key relevant features (typically a small subset of the entire state vector) that lead to a particular action. This is key information, because it allows the system to teach why an action is called for in a particular situation instead of simply what action is appropriate. Induction iterates over the set of actions found during scenario exploration to find set of concepts that cover all the scenarios in the training set. These concepts form a set of flat "stimulus-response'' type rules; the induced rules form a knowledge base that is a representation of the original knowledge base, constrained within the space of interest in the scenario state-space.
Example
To illustrate the flavor of this approach, consider the domain of automobile driving -- a prototypical operator control task. A simulation in this domain would contain such state variables as speed, brake position, steering position, visible traffic signs, etc. Some simulation state vectors in this domain might be:
The scenario exploration process would start at some pre-defined start scenario (such as the fourth one above), and explore the simulation "expert path" by implementing the expert's recommended actions. Next, deviations from this expert path would be explored by implementing random control actions such as (brakes: on), or (steering: + 10 degrees). Most of these would lead to negative conditions, but this would provide valuable information for the induction process and the construction of the scenario library. Next, induction attempts to determine the key features in a state vector that distinguish it from other state vectors. For example, the action (brakes: on) might be called for at scenario 1; induction (ideally) determines the relevant state variables that distinguish this example from all the other scenarios in the library. This information defines an "induced concept." This information is critical because it allows the system to teach why an action is appropriate for a particular scenario, as opposed to simply what action is appropriate. For the driving domain, the induced concept might be (visible sign = Stop, distance < 50 ft).
Scenario generation and rule induction are domain-independent processes, operating on a specified interface to a domain-specific knowledge base and simulation. This allows these components to be developed independent of knowledge that they are going to be used in a training system, with any available tools that allow the components to meet the interface requirements. Additionally, whenever either of these components are changed, the process can update the scenarios and rules automatically, or other components can be substituted to provide knowledge in a new domain. If a simulation and knowledge base already exist for a particular domain, then an intelligent training system can be created with almost no knowledge engineering.
Preliminary Results & Conclusions
As a proof on concept, we have implemented the knowledge-acquisition aspects of SCIUS in a prototypical operator control domain involving a fictional reactor. Our system used a non-trivial simulation with 121 state variables and an expert system with 65 rules. The scenario exploration process found a wide variety of scenarios, sufficient to allow for successful induction and to provide a rich scenario library. Additionally, we found that the growth of scenarios found through deeper exploration was much less than the theoretical upper bound to the growth, suggesting that this approach is tractable. Induction performed generally well, discovering many concepts that were identical to the original expert rules. This is a testament to the power of induction because induction was able to isolate the small number of features (typically 2-5) that suggest an action from thousands of state vectors that were 121 elements long. However, some induced concepts were discovered that, while correct, were inappropriate for training. For example, one of the attributes for an induced concept might be (temp < 17654.32) when an attribute such as (relief valve = on) would have sufficed. Induction is a domain-independent process; there is no knowledge present in standard induction to allow it to choose between two attributes that have the same contribution to the information-theoretic value of a concept. We are investigating two complementary approaches to this problem. First, we are "tuning" ID3 to incorporate domain-independent training heuristics, such as the idea that we prefer nominal concepts over numeric concepts. Second, we are developing an approach to allow "post-processing" by a human course author. This approach would allow our system to present several alternative concepts to a course author, and allow him to select the most appropriate for training. This would still provide a huge savings over the complete human-authored approach while still allowing the human expert knowledge to be utilized in a highly efficient manner.
We have presented an architecture for an intelligent training system that requires less knowledge than other approaches. We utilize two basic domain-specific components, a simulation and knowledge base, at the interface level only, allowing wide latitude in the implementation of these components, and simplifying knowledge maintenance difficulties. The bulk of the domain-specific knowledge required for training is learned through an automated simulation state-space search process, and rule induction to extract shallow rules from the behavior of the knowledge base. Although this heavily procedural knowledge representation may not be appropriate for all training domains, we feel our approach fills a valuable niche for cost-constrained course designers.
Anderson, John R., et al. (1985). Intelligent Tutoring Systems. Science. 228:456-462.
Orey, Michael, et al. (1993). Development efficiency and effectiveness of alternative platforms for intelligent training. Proceedings of the 1993 Artificial Intelligence in Education Conference.
Quinlan, J.R. (1986). Induction of decision trees. Machine Learning. 1:81-106.
Shute, Valerie J. and Josepf Psotka. (1994). Intelligent tutoring systems: past, present, future. Technical Report AL/HR-TP-1994-0005, USAF, Armstrong Laboratory.
Wenger, Etienne. (1987). Artificial Intelligence and Tutoring Systems. Los Altos, California:Morgan Kaufmann Publishers, Inc.