NAVAL POSTGRADUATE SCHOOL

ACKNOWLEDGEMENTS

I would like to express my sincere gratitude to my thesis advisor, Professor Neil C. Rowe, who provided guidance and assistance throughout this thesis research.

Writing a thesis is not just an intellectual endeavour, it is a time consuming and emotional experience; with the support and encouragement of my beautiful wife Maria Elena, this task has been easier to undertake. I would also like to thank my parents, although far away, their love and dedication is a key to what I have become.� Finally, but not least, thank you Carlos Andr�s, though being too little to understand, you have brought even more happiness into this exciting and exhausting episode of my life.

I. INTRODUCTION

During peacetime the top goal of any military organisation is to maintain its personnel and equipment ready to go into action whenever needed.� The best way to achieve personnel readiness is through continuous education and training.� In this effort almost 20 billion dollars were spent in 1988 by the US Defense Department in formal training, and almost 200,000 military and civilian personnel were required to provide instruction [Ref. 1].� With today's technological and economical complexities, the need for expertise has never been greater.� The increasing number of military systems together with their technological sophistication influences the military to look for more personnel to master complicated and varied subject material and skills.� The percentage of high-skill personnel required by the US Navy increased from 23 percent in 1945 to 42 percent in 1980 [Ref. 2].

Education in the military is becoming a problem nowadays for three major reasons.� First, teaching and training personnel in real world situations can result in many unnecessary expenses; e.g., damage or loss of expensive equipment, injuries of personnel, expenditure of fuel or other energy sources, and loss of valuable time.� Second, the number of military systems is increasing while the number of military personnel is decreasing in some countries; the military cannot afford to assign already available high-skilled personnel as instructors or tutors, for that would make the situation worse than it is.� Third, military units like ships are usually deployed and constitute autonomous units; their access to qualified instructors and instructional facilities is limited, if not impossible.

New approaches to military training and instruction are necessary if the goal of complete personnel readiness is to be achieved, If technology advances and sophistication are invading the modern world why not take advantage of them in the area of education.� Computers have become a widely used and easy-to-access commodity during the last decade, so it is not surprising that the idea of using computers for instructional purposes has already been introduced.� Computer-Based Instruction has been used for several years now for different applications.� The term Computer-Based Instruction, or CBI, refers to all uses of computers in instruction.

Originally CBI took the name of Computer-Assisted Instruction, or CAI.� As its name implies, this approach was designed to aid students in the process of learning, but it did not have a great impact primarily because the majority of these systems just printed prepared text and ran pre-stored drill-and-practice sessions [Ref. 3 pg. 225].� CAI systems do not usually, adapt well to the students' needs and speed of learning.� New advances in the area of Artificial Intelligence (AI) are giving new hope to this approach to instruction.� Computers can now be programmed to simulate a tutoring process similar to the human counterpart.� This new method is Intelligent Computer-Assisted Instruction, or ICAI.� An ICAI system is able to understand complex feedback from the student and modify its tutoring strategy according to the student's level of learning.

The purpose of this thesis is to examine the feasibility of an ICAI system that tutors two or more students at the same time and on the same application.� Underway Replenishment was chosen as the application domain since it is a military procedure, which requires the step-by-step interaction of two ships simultaneously in order to achieve its goal.

A. UNREP

The primary mission of a navy is to maintain its country's sea routes of supply open during peace and war times.� The most efficient way to accomplish this mission is to keep warships always at sea, well stocked and ready to go into action whenever necessary.� Underway Replenishment, also known as Replenishment at Sea, or simply UNREP, enables naval units to extend their operational time at sea.� Fuel, supplies, ammunition, and other types of cargo including personnel, are transferred from large ships to less self-sufficient ships while cruising side by side in the open seas, making it possible for a ship to remain at sea up to an entire period (theoretically) between major overhauls or dry-docking.

Useful and practical as this military concept seems, it is a complex procedure, requiring special knowledge and expertise from the officers in charge of executing the maneuver.� During replenishment operations the danger of collision is much greater than under normal circumstances.� The unusual proximity of the ships involved and the complex arrangement of lines and hoses connected between them reduces the maneuvrability and increases the vulnerability to attacks during wartime.� Open storage compartments, exposed material, and occasionally dangerous or explosive cargo, are some of the hazards to which personnel involved are exposed.

B.�� SCOPE OF THESIS

The UNREP ICAI system (referred to as the UNREP tutor) described in this thesis is by no means a complete course in UNREP operations.� The UNREP tutor has been designed to supplement the courses and training offered by a navy on the subject matter, not replace them.� The tutor focuses its instruction on orders issued by the Officers of the Deck (OOD's) aboard each UNREP ship, since they are the ones that monitor this procedure step by, step.� Potential users of this system could be Midshipmen or Junior Officers in the navy, who are training to get the COD qualification.

The UNREP tutor m-as implemented using artificial-intelligence techniques in the Prolog programming language.

C. PREVIEW

Chapter 11 provides background on Intelligent Computer-Assisted Instruction (ICAI) and its components, and describes ICAI systems sponsored or developed by the military, including the application-independent METUTOR program.� Chapter 111 provides background on Underway Replenishment (UNREP) and describes its procedure from the Officer-of-the-Deck's point of view.� Chapter IV discusses the actual design and implementation of the UNREP tutor.� Chapter V summarises the performance of the system, addressing issues such as memory requirements, time considerations, accuracy, and complexity.� Chapter VI discusses the major achievements and limitations of the system, providing recommendations for future system enhancements.� Appendices A and B contain test runs.� Appendices C and D contain the Prolog code for the knowledge representations of the UNREP system.� Appendix E contains the Prolog source code developed by Professor Rowe.

II.�� ICAI SYSTEMS IN MILITARY APPLICATIONS

Many ICAI systems have been designed and implemented.� Some of them have been tested and evaluated, proving to be successful and efficient under real training situations.� Others, on the other hand, are far away from practical.� This chapter gives an overview of Intelligent Computer-Assisted Instruction, and briefly describes military ICAI systems, pointing out features of interest.

A.�� OVERVIEW OF ICAI SYSTEMS

Intelligent Computer-Assisted Instruction, or ICAI, is the area of computer science that deals with the design, development, and implementation of computer-based systems that provide adaptive and dynamic instructional environments to a user, applying artificial-intelligence techniques [Ref. 4: pg. 15].

Computer-based instruction, or CBI, has not always has been considered a field of interest specific to computer science. CBI was first explored by educational psychologists under the name of Computer-Assisted Instruction, or CAI.� CAI systems on their early years were developed primarily as supplemental tools to the traditional methods of instruction.� The approach of CAI was that of using computers as an efficient method of translating a teacher's pedagogical decision into a program [Ref. 5], like a computer textbook, without checking the student's real understanding of the subject.� The human teacher was always taking care of the tutoring aspects, and the computer was merely a tool,

Later on, ICAI research was introduced into the computer-science field, and a more ambitious task was undertaken.� The interest of ICAI did not just comprise instruction and learning aspects, but also the development of computer systems that would "effectively capture human being's learning, and teaching processes" [Ref. 4: pg. 381]. "Adaptive" and 'dynamic' are key words in the definition of ICAI.� The former refers to the ability of the computer to adapt to the needs of the student depending on his/her level of understanding: some students will grasp a point quickly, while others will need a different approach to learn the same subject.� In order for a system to be adaptive, it must also be dynamic.� Through interactions with the student during the tutoring session, the ICAI system could determine to what level the student is assimilating the skill or subject being taught.� The system could not only get feedback on how many questions have been answered correctly by the student, but also evaluate these answers and try to define the problem area of the student.� Based on this e evaluation, the system could change its teaching style, speed, and depth.

Artificial Intelligence (AI) techniques are indispensable in the design of ICAI systems.� Natural-language understanding and representation for input and output is a necessary feature for a more efficient interaction between the student and the system.� Knowledge representation is also required in an ICAI system in order to encapsulate all the expertise on the subject being taught.� Methods of inference provide the system the ability to generate problems for the student.� Some applications require algebraic simplification, symbolic integrations, theorem proving, etc, AI techniques and methods make these tasks possible in an efficient way [Ref. 3: p. 227].

Although there are no definite and precise characteristics which specify whether a tutoring system is an ICAI system or not, four components are responsible for providing the basic features of most existing ICAI systems. These components are the expertise module, the tutorial module, the student model, and the inference engine [Ref. 3: pp. 229-235].� They represent respectively the subject to be taught, the tutoring strategy, the theorised model of the student's knowledge, and the method to determine how much the student has learned so far.� Some ICAI systems contain m-ell-defined and separate modules, while others encapsulate the function- of the four distinguishing components into one single module.

B.�� MIILITARY ICAI SYSTEMS

This section will discuss ICAI systems that have been, or are currently being developed by the military and for military training applications.� Fletcher [Ref. 61 has gathered a list of ICAI systems which meet our criteria.� We briefly describe seven of those systems plus another system that was developed at the Naval Postgraduate School and constitutes the backbone of this thesis.

The Sophisticated Instructional Environment (SOPHIE) ICAI system is one of the first and most important contributions, not only to the military training research community, but also to the ICAI field in general.� SOPHIE teaches problem-solving skills by having the student take measurements on a simulated electronic piece of equipment, which has a malfunction.� The student's goal is to find-the fault by troubleshooting the simulated circuit [Ref. 3: p. 297].� SOPHIE's contribution to the ICAI field is the introduction of device-based simulation to support checking of student inferences, as well as heuristic strategies to allow question generation and answering mechanisms. [Ref. 6 and Ref. 7: pp. 227-281).� STEAMER is another ICAI system that was developed in the late 1970's.� This system is based in the simulation of a ship's steam propulsion plant.� STEAMER's main goal is to train operators by helping them understand this complex application through interactive graphical interfaces [Ref. 4: pp. 114-115].� Although the actual implementation of reasoning mechanisms in the STEAMER project is purely mathematical, its underlying principles have inspired research in the areas of mental models and abstraction simulation in AI [Ref. 8: pp. 79-88].

QUEST (Qualitative Understanding of Electrical System Troubleshooting) is similar to the SOPHIE system in that the goal of the system is to provide the student with a learning environment so that he/she can solve circuit problems. QUEST, however, relies on graphic simulation as well as casual explanations of circuit behaviour to support the student's learning process [Ref. 8: pp. 88-89].� Like STEAMER, QUEST investigated the research area of mental models, but it also emphasised on the area of qualitative reasoning.

The Intelligent Maintenance Training System (IMTS) is intended to simulate the functions of different devices and train students in their maintenance, therefore acting as an operational maintenance trainer.� The system's current application is the simulation of the SH-3 helicopter's blade-folding mechanism. The main characteristic of IMTS is its emphasis on the interface with human instructors, allowing them to control some of the operating modes of IMTS.� This system builds a conceptual model of the student's skills and measures his general knowledge and learning preferences in order to select its tutoring strategy and type of problems. MACH-111 is the Maintenance Aid Computer for HAWK - Intelligent Institutional Instructor.� It provides training in maintenance of electronics and electromechanical systems in general; currently the subject domain is the maintenance of the high-powered illumination radar of the HAWK air defense system.� The MACH-111 system supports three modes of instruction: demonstration, step-by-step guided practice, and free form monitored practice.

TRIO, a Trainer for Radar Intercept Operations, includes real-time simulation, speech synthesis, and speech recognition capabilities in the training of F-14 interceptor pilots and radar officers.� The student's solution to an air-intercept problem is compared to the solution generated by an expert knowledge base.� TRIO is not only concerned with the tutoring of problem-solving methods, but it also trains students on how to react fast enough when confronted with radar warnings.� Specific function-modules generate warnings to the student while monitoring his performance.� Another system that has a time-constrained application is the Intelligent Conduct of Fire Trainer (INCOFT) system.� It is intended to train students in the operation of the engagement control station of the PATRIOT air defense system.� INCOFT uses basically the same approach as TRIO, with the exception of the speech capabilities since a spoken interaction is not that important in the INCOFT application as it is in the TRIO.

1. METUTOR

METUTOR is a general-purpose Means-Ends Tutor developed by Professor Rowe at the Naval Postgraduate School.� Three major applications have been adapted to the system so far: the MEFIRE, the CPR, and the Network-Mail tutors.� The first trains students on fire-fighting procedures aboard a Navy ship; the second uses the medical field of CPR as its subject-domain [Ref. 9]; the third teaches students to use the Arpanet MM mail facilities [Ref. 10].� The METUTOR system is written using the Prolog language and a� version of it is contained in appendix D.

The expertise module of an ICAI system is usually divided into knowledge base and domain-reasoning methods.� In the METUTOR system, the knowledge base is kept separate from the rest of the system since the tutor is intended for teaching or training various subject domains. The knowledge base used in this thesis research is part of the discussion of chapter 4. The domain-reasoning methods in the METUTOR use a means-ends analysis program[1] to reason top-down from abstract goals.� The top level is a recursive means-ends predicate which has four arguments: State, Goal, Oplist, and Goalstate.� The State is a complete list of facts, which are true in a state.� The Goal is a list of facts that are required to be true in the goal state.� The Oplist is a list of operators required to reach the goal state from the starting state.� The Goalstate is a complete list of true facts at the goal state [Ref. 11].

The tutorial module in the METUTOR encapsulates tutoring strategies and monitors the student model accordingly, guiding the dialogue between the system and the student.� Two general approaches are used by the METUTOR system.� The first one provides immediate corrective responses to the student's actions, while the second one temporarily allows the student to follow an incorrect path of actions commenting on the error only after the student has realised his own mistake.� The tutoring rules used in the METUTOR system are handled by the predicate handle_student_op[2].

The METUTOR student model uses a stack representation of the student's applied operators in order to determine the student's level of understanding.� This stack is compared to the expert's solution path of operators by the inference-engine module, and the tutoring strategy to be used is determined by figuring out what the student is actually trying to do at each step during the tutoring session.� The tutorial module in the METUTOR program uses the following tutoring replies:

� OK.�� The student's response matches that of the expert module means-ends analysis.

� The possible operators are: < list of operators >.�� The student requested a list of valid operators by entering a help word.

� I assume you mean < operator >.�� The student made a spelling error when entering the chosen operator.� The tutor recognises the operator though.

� Not a valid operator--please choose one of. < possible operators >. ��The student entered an invalid operator, or a string of nonsense characters, or made too many spelling errors.� He/she has to enter an operator again.

� That operator requires that < required precondition list >.�� The facts in the precondition list must first be achieved in order to apply the operator.

� That will not affect anything.� The student's chosen operator does not have any effect on the current state.

� You cannot ever succeed if you do that.�� The operator chosen by the student would create a state from where it would be impossible to reach the goal state.� The student has to type another choice of operator.

� That does not seem immediately helpful, but I will try it.� The student is allowed to follow his/her own solution path.� This tutoring strategy does not tutor immediately, but sets up a flag in the database, indicating that the student seems to be pursuing a digression.

� I will try it but it is not recommended first when < recommended operators >.� The student has picked an operator, which does help reach the goal state, but it is not the highest-priority operator.

� Not the operator I would choose, but let us try it anyway.�� The tutor cannot really figure out what the student is trying to do, but allows him/her to apply it any-way.

� You are returning to a previous state.� The student is returning from a digression. Works in conjunction with the "That does not seem immediately helpful, but 1 will try it" strategy.

� Do you see now that your first choice of action in the state with the facts < previous state description > was not the best choice; the < operator > action would have been better. �After allowing the student to continue with his/her solution path, the tutor hopes the student realized why his/her choice of operator was not a high priority one.

The inference engine module of the METUTOR is mixed in with the means-ends tutor code.� The means-ends tutor works in parallel with the student by asking an input operator before every action.� The inference engine checks if the student's choice of action agrees with the tutor's internal recommendation; if it does, the tutor immediately applies the student's operator; other-wise, the inference engine tries to figure out what the student is doing by means of a complex analysis of the hypothetical state created by the student.� The tutorial module then takes over again and tutors the student accordingly.

III.� OVERVIEW OF UNDERWAY REPLENISHMENT

Underway Replenishment (UNREP), also known as Replenishment at Sea, is the term applied to the transfer of fuel, munitions, supplies, and men from one vessel to another while ships are underway.� Most of the transfers are performed from special-purpose replenishment ships to combatant ships, and major combatants, like carriers for example, are also capable of refuelling smaller ships.� Even the smallest ships can and do exchange light freight, mail, and personnel with other smaller ships.� In any case, the larger ship, or the ship from where the cargo (fuel and personnel are also defined as cargo in this case) is transferred from, is called the delivery ship, and the smaller ship, or the destination of the cargo, is called the receiving ship.

The ability of men to work together smoothly is important in a replenishment operation.� The necessity for adequate training is increased in transfer operations by the fact that crews from different ships and from different nations are called on to work together although they may, never have had any contact with one another before.� A high degree of teamwork and coordination must be achieved.� Preparing the cargo to be transferred, rigging (setting up gear for working), and handling gear are all special skills and techniques which are not within the duties of the Officer of the Deck.� But certain aspects of replenishment do concern the Officer of the Deck, also referred as the OOD.� He should know who is responsible for rigging the special gear required, how long this preparation takes, when to station (assign positions) the special details (small group of personnel temporarily assigned to fulfil a precise requirement, in this case a job related to replenishment at sea), and particularly he should be familiar with the UINREP step-by-step procedure.

The tutoring program of this thesis specifically focuses on the Underway Replenishment procedure from the OOD's point of view.

A.�� PROCEDURES

The UINREP procedures for the U.S. Navy are described in detail in the NWP 14 [Ref. 12].� Replenishment is accomplished with both the delivery and receiving ships steaming side-by-side on parallel courses at a Predetermined speed.� But first, in order for the ships to be alongside (side-by-side), one of them must approach the other.

1.�� Making the approach

A typical Underway Replenishment begins when a task-force commander arranges a rendezvous at sea with the group, and then orders the start of the replenishment operation with a given ordered course and speed. The approach is executed as follows.� When steady on the ordered course and speed, the delivery, ship will fly (display or exhibit) the signal flag ROMEO at the dip (signal-flag hoisted about six feet down from the full-up position) on the rigged side.� She (ships are referred as feminine) will fly ROMEO close-up (signal-flag hoisted full up) when ready to receive, in other words, when the replenishment side has been rigged.� The receiving ship which is about 500 yards on the quarter (relative bearing halfway between astern and abeam on either side of delivery ship) will also fly ROMEO at the dip on the rigged side when ready to come alongside.� She will f1y ROMEO close-up when she is commencing her approach.� The receiving ship usually approaches the delivery ship because of the smaller ship's better maneuvrability.

Once both ships are alongside (actually separated by a distance of about 100 feet), the delivery, ship shoots the gun-line (one of the methods to send the first line from the delivery ship to the receiving ship) and the receiving ship receives and secures the gun line.� As soon as the first line is secured, and the transfer rigs are passed and connected, both ships haul-down ROMEO (lower signal flax completely). This step completes the approach phase of the UNREP procedure.

2. Replenishment and station-keeping

During the transfer of flammable or explosive items, such as gasoline, fuel oil, and ammunition, both ships involved fly BRAVO at the fore.� In order to reduce the probabilities of collision by having both ships maneuver to keep their distance and proper station, only the receiving ship is responsible for maneuvering.� The receiving ship must ensure that the specified distance between ships is maintained during the approach and during the replenishment, as well as keeping her station exactly abeam from the delivery ship.� The delivery ship is only responsible for maintaining the predetermined replenishment course and speed.

Keeping station abeam is simplified by watching the distance line and adjusting the course accordingly.� The distance line, among the first to be passed across, serves as an indicator for the distance between ships; by watching it, the OOD of the ship will know immediately that his ship is coming in too close or going out too far.� Also, by watching a mark in the other ship or observing the angle that the distance line makes with the ship's side, the OOD can determine if the delivery ship is bearing slightly ahead or behind, and get back into station by slowly adjusting the speed.

3.� Departure

Fifteen minutes prior to the completion of alongside refuelling or replenishment, the receiving ship hoists PREP at the dip.� Upon completion, the receiving ship hoists PREP close-up, meaning that she is starting to disengage from the delivery ship.� The receiving ship then slowly increases speed and clears ahead and away from the delivery ship,

4.�� Emergencies

Several emergency situations can arise during replenishment operations.� The prime objective during any emergency is to perform an emergency breakaway, in other words, disengage as soon as possible in order to avoid a collision or expose the lines to excessive tension and therefore endanger the involved personnel.

In the event of an emergency, both ships have to make sure that the personnel handling rigs and equipment know about the emergency so they can disengage couplings and other lines with dispatch.� The emergence should be announced over the ships' loudspeaker, and the EMERGENCY flag must be flown.� As soon as all the lines and couplings have been disconnected, both ships c1ear and sail away from each other.

B.�� APPLICATION COVERAGE

Trying to represent a complete real replenishment procedure can lead to an extensive and complicated model.� In order to simplify, this application, several assumptions have been made.

For purposes of this thesis, the UNREP procedures represented daytime operations. Night-time operations involve other signals and increased difficulties arise, making the model too complicated.� Also, it is assumed that the only method of communication between the two ships is by means of signal flags.� In reality, communications are crucial for the success of the operation, and that is why several means of communication are used, such as sound-powered telephones, radio, hand signals, visual light signals, and even megaphones.

Numerical data, such as actual speeds, courses, ship bearings, and distances between ships, are not used in the modelling since in reality each ship has different characteristics, so speeds and course adjustments would depend on the type of ship.

Emergencies in an actual UNREP could happen any time and in many different ways.� Again, for simplification purposes, only two types of emergencies are simulated. They are steering system failure and excessive line tensioning due to improper maneuvering of the ship.

IV.� UNREP: A MULTI-USER ICAI SYSTEM

A.�� SYSTEM ENVIRONMENT AND OVERVIEW

UNREP is an ICAI system developed and implemented on an Integrated Solutions Inc. (ISI) Optimum V Workstation computer, using the MPROLOG language. MPROLOG (Modular Programming in Logic) is a modular version of the logic programming language PROLOG.

Given that the Underway Replenishment application requires the interaction of two ships, the UNREP system was designed to handle two students simultaneously, each of them acting as the OOD aboard each of the ships involved, The UNREP system requires that each of the two students have access to individual workstations, both of them connected to a common memory base.� Two knowledge bases representing the UNREP procedures for the delivery and receiving ships' procedures, respectively, were written and adapted to the application-independent METUTOR11 program[3]. The multi-user approach was accomplished by adding to the METUTOR11 program the ability to handle several students (preferably not more than two as is discussed in chapter VI) at the same time, each of them playing different roles within the same application.� The multi-user capabilities of the system do not affect the original single-user tutoring facilities of the METUTOR11; as a matter of fact, a single-user version of the UNREP tutor can be readily obtained by slightly modifying the knowledge bases of the two-user system.

B.� UNREP KNOWLEDGE BASES

The knowledge bases for the UNREP tutor are contained in the files MEUNREPDEL and MEUNREPREC[4]. They represent the delivery ship and receiving ship Underway-Replenishment procedures respectively.

The first step in the development of the knowledge representations was to gather the subject matter required for the Underway Replenishment procedures.� The domain expertise for each of the knowledge bases was extracted from the NWP 14 Under-way Replenishment Procedures Manual [Ref. 12]. Although one of the main advantages of ICAI systems in general is the capability to bring together the knowledge of several experts into a single knowledge base, we thought that the information contained in the above mentioned publication was sufficient to meet the objectives of this thesis research.

Next, the expert knowledge was translated into a format that could be understood by the METUTOR11 program.� The Underway Replenishment procedure is an ordered sequence of actions, starting from an initial given state, the starting state, and ending at a final state called the goal state.� In order to reach the goal state, a recommended solution path must be followed from the starting state, and going through intermediate states.� This recommended path could be achieved by "performing" successive actions, or in other terms, by applying an operator at each given state, until the goal state is achieved.� A state is characterized by a set of facts, also considered a list of true facts.� Each of the facts in the goal state must be true by the end of a successful tutoring session.

Facts can be achieved (added to the true fact list of a state) by applying recommended operators for them.� A recommended predicate in the knowledge base summarizes such recommendations [Ref. 1l: pp. 268-269]:

recommended([ < fact to be achieved >], < operator >.

The recommended rules are ordered according to the priority in which the operators must be applied.

An operator can only be applied if the current state contains all facts that have been defined as prerequisites to that operator.� The precondition predicate serves this purpose.

precondition(< operator > ,[ < list of required facts > ]).

In this predicate, the second argument is the list of facts that must be present in the current state if the operator is to be applied in that state. The second argument can also be an empty list if there are no prerequisites needed to use that operator.

After an operator is applied, the list of true facts, also known as the state description, can change, adding new facts to the state, and deleting others.� Two predicates are defined in the knowledge base to handle these, changes:

addpostcondition( < operator > ,[ < list of facts to be added >]).

deletepostcondition( < operator > ,[ < list of facts to be deleted >]).

Again, the second argument lists can be empty lists depending on the operator postconditions.

It is important to mention that the METUTOR11 tutorial module checks the knowledge base before starting the tutorial session with the student.� It makes sure that each operator is defined by the required two-argument predicates (recommended, precondition, addpostcondition. and deletepostcondition predicates); in addition, it checks that a solution of operators exists to achieve the goal state, given a starting state.� These tasks are always performed due to the application-independent nature of the METUTOR11 program.

Other optional predicates may be defined in the knowledge base to add flexibility and enhance the realistic representation of the domain application.� Three and four-argument addpostcondition predicates may be defined for an operator.� These predicates are:

addpostcondition( < operator > ,[< list of prerequisite facts > ],[ < facts to he added > ]). addpostcondition( < oper. > ,[ < prereq. facts > ],[ < facts to be added > ], < message >).

The three-argument predicate adds the facts listed in the third argument only if the additional second argument facts are part of the current state description.� The fourth argument is a message that appears on the screen when the list of required facts is true in the state description.� The deletepostcondition predicate can also be defined using these three and four-argument formats, and they work similarly.

A nopref predicate is used when the priority of two operators in the recommended rules is not of importance; in other words, the order in which the operators may be applied is arbitrary for the tutor.� Its format is as follows:

nopref( < operator 1 >�� operator 2 >).

A very important optional predicate is the randsubst predicate:

randsubst( < operator > ,[[ < deleted fact > , < added fact > , < probability > ,< opt. message > ],[ < another opt. quadruple >],...]).

This predicate introduces the factor of randomness into the tutoring session.� If a randsubst predicate has been defined for an operator, the first fact of the list will be replaced by the second fact on the list after the postconditions of that operator have been applied.� The third element in the sublist is the value that determines the probability of occurrence of the random substitution.� Either of the two facts can be "none" to allow addition or deletion of facts in the state description.� The student is aware of a random substitution because a message is printed on the screen informing the occurrence of this change.� The fourth element in the sublist is an additional optional message that gets printed on the screen after a random change.

For the multi-user tutor, we have defined an additional format for the randsubst predicate:

randsubst( < operator > ,[...,[ < fact to be deleted > ,< opt. message >],...]).

This format is required in the UNREP system when a wait operator is used in the knowledge base.� In this case, the fact in the list is deleted from the true fact list; no probability weight is given because randomness is not a factor anymore.� Using this special format, the random change message does not appear on the screen.� An optional message may appear acknowledging the student in his decision to wait.� This format is equivalent to a normal randsubst with a "none" second fact and a probability weight of one.

This format can better be explained using an example.� Figure 1 shows the definitions for the operator wait until delivery ship shoots gun line.� This operator may be applied by the student acting as the receiving ship OOD whenever his ship is already alongside and the delivery ship has not shot the gun line yet (precondition definition).� The fact gun line is shot cannot be added in reality to the state description when the receiving ship student applies the wait operator, as the recommended and addpostcondition definitions suggest.� The delivery ship must apply the operator shoot gun line in order to assert this fact in the state description.� The reason why the wait operator seems to be asserting a fact that can only be added in reality by the delivery ship student, not by the receiving ship student, is because the METUTOR11 program must be able to solve the UNREP procedure completely before the tutoring session starts, to find if a solution path exists, for otherwise it would issue an error message advising there is no solution to the problem. The fact gun line is shot is deleted from the state description before the receiving ship student even gets to see it there, and a message acknowledges his decision to wait.� In summary, this special randsubst format allows a student to wait for an action that can only be performed by the other student.� The state description remains unchanged after a wait operator has been applied.

recommended([ shot(gun_1ine], wait(until,delivery,ship,shoots,gun,line)).

precondition(wait(until,delivery,ship,shoots,guln,line),[alongside(ships),not shot(gun line)]).

deletepostcondition(wait(until,delivery,ship,shoots,gun,line),[].).

addpostcondition(wait(until.delivery,ship,shoots,gun,line),[shot(gun _line)]).

randsubst(wait(until,delivery,ship,shoots,gun,line),

�� [[shoot(gun line),"Please wait for gun line to be shot']]).

Figure 1.�� Example of 'randsubst' Predicate

1.�� UNREP Definitions

Following is a list of operators that may be applied by a student during a typical UNREP tutoring session.� Each operator is described by giving first the type e of ship from which an OOD may apply the operator (either the receiving ship, or delivery ship, or both), and next, the facts that are asserted in the state description once the operator is applied.� The order in which the operators are listed is not necessarily the same in which they are applied, and the order may vary from session to session.

� Steer to ordered course and speed. �Delivery ship OOD may apply it; accomplishes the fact delivery- ship is steady on ordered course and speed.

� Rig replenishment side. �Both OODs may apply it; achieves the fact unrep side is rigged on delivery (receiving) ship.

� Wait until delivery ship flies ROMEO at dip. �Receiving ship OOD may apply it; does not assert any facts.

� Fly ROMEO at dip on rigged side.� Both ships may apply it; asserts ROMEO flag is at dip on delivery (receiving) ship.

� Wait until delivery ship flies ROMEO close up. ��Receiving ship OOD.

� Fly ROMEO close up. �Both OODs may apply, it; achieves ROMEO flag is close up on delivery (receiving) ship, delivery ship is ready to receive, and receiving ship is ready to approach.

� Wait for receiving ship approach. ��Delivery ship OOD may apply it.

� Approach delivery ship.�� Receiving ship ODD; asserts ships are alongside.

C.�� METUTOR11: A MULTI-USER APPROACH

1.�� General Description

The implementation of the UNREP system is based on the assumption that two students are tutored on the Underway Replenishment procedures at the same time.� One of the students is playing the role of an OOD aboard a delivery ship, while the other student acts as the OOD aboard a receiving ship.

The UNREP tutor system was tested using the PDSS (Program Development Support System, by Logicware Inc.) facility in the Optimum V Workstations.� A typical tutoring session is started by having each student load two files in the PDSS system.� The first file is the METUTOR11 and the second file is either the MEUNREPDEL, for the delivery-ship-OOD student, or the MEUNREPREC, in the case of the receiving-ship-OOD student.� Then, each student queries the predicate go.� By doing this, the top level of the means-ends tutorial module is activated in the METUTOR11, therefore invoking the system.� The tutor then prints on the screen an introduction[5] and then the tutoring session starts.� The tutor shows the student a list of all the true facts at a given state and prompts him to choose an operator.� The student then types in his choice of operator and waits for the tutor's nest request.� Three things can happen at this point: first, the tutor may accept the student's operator and apply it to the state in the simulation; second, the tutor may refuse an erroneous operator and ask the student for another; third, it may send a message to the student informing him that the chosen operator was ignored by the tutor because the state was changed by the other student's actions, and to please select an operator again.

The third alternative is a characteristic of the multi-user version of the METUTOR11 program.� The tutor has to analyse the situation again, based on the facts describing the new state.� Basically, of the two students, whoever enters first his choice of operator gets to continue the tutoring session normally without interruptions, while the other has to enter a new choice of operator.� While some facts in the state description can be asserted by any of the two students, others can only be asserted specifically by only one of the two students.� Each strident will reach different points in the tutoring session where they must wait until the other student applies an operator that will achieve the state description needed by the first student to continue his session.

2.�� Implementation

The UNREP system was implemented by modifying and adding some rules to the original METUTOR11 program.� The main implementation characteristic of the UNREP system is a single file common to both students using the tutor.� Stored in this file are a session's current time-stamp and state description.

The file used in the UNREP system is called FACTS.� Figure 2 shows an example of the contents of this file for a given state. This file is initialized at the top level of the means-ends tutor with an empty list as the state description (since the fact predicates are defined so that there are not any true facts yet at this point) and a time-stamp equal to zero.� Also, a time-stamp predicate is asserted in the tutor's database with an initial value of zero.

After the two halves of the tutor program have been activated on two terminals, the first student to input his choice of operator adds some facts to his current state description and the time-stamp is incremented by one.� The updated time-stamp and the new state description are saved in the FACTS file; also the incremented time-stamp value is asserted in the tutor's database for the first student, replacing the old value.� When the second student tries to input his choice of operator, his tutor program first compares the FACTS file time-stamp to the time-stamp fact asserted in the tutor's database for the second student.� When both time-stamps agree, the tutor accepts the second student's choice of operator and continues tutoring, but, since the first student changed the time-stamp:

1.�� a time-stamp violation predicate is asserted in the second tutor's database;

2.�� the second tutor ignores the operator chosen by the second student;

3.�� it reads the new state and the new time-stamp from the FACTS file;

4.�� it prints a message informing the student of the anomaly, and lists for him the new state description; and

5.�� it analyses the problem again to determine the best operator now, based on the new state description, before prompting the student for a new operator.

15 /* this is the current value of the time- stamp */

[ok(unrep_ships),ok(distance between-ships),rigged_on_delivery_ship(unrep side)]

�� /* and this is the current state description */

Figure 2.�� Sample FACTS File Contents

The behaviour just described is implemented using Prolog backtracking in the METUTOR11 program.� Figure 3 shows the actual implementation details that allow multi-user tutoring through time-stamp coordination.� This code is mixed with the means-ends tutor code.� When the recursive means-ends program pauses to ask the student his next choice of operator, the check_with_student predicate queries the check_time_stamp to compare the FACTS file time-stamp against the database's time-stamp (after reading the student's input from the screen). If both time-stamps agree, the cheek_with_student rule succeeds, causing the met rule to continue with its normal sequence:

1. delete and add postconditions,

2. perform random substitutions,

3. save the new time-stamp (after incrementing it) in the FACTS file, along with the new state description (after the tutor has applied the student's operator), and,

4. recursively call means_ends_tutor.

If there exists a disagreement between the time-stamps, the check_time_stamp rule fails (not without asserting first the time_stamp_violation predicate in the tutor's database), and so do the check_with_student and the originating met rules, forcing the program to try the next met definition.� In that case, the following steps take place:

1.�� ts violation is retracted from the database;

2.�� a message is sent to the student informing him that his operator has been ignored due to a change of state;

3.�� the new time-stamp and state description are retrieved from the FACTS file;

4.�� the new time-stamp is asserted in the database, and,

5.�� the new state description is included in the recursive call to means-ends-tutor.

met(STATE,GOAL,OPLIST,GOALSTATE,STACK,PRELIST,PREOPLIST,....) :-

�� check with student(OP,PRESTATE,D,NEWOP),

�� (additional code)

�� time_stamp(TS),

�� retract(time_stamp(TS)),

�� NTS is TS+1,

�� asserta(time_stamp(NTS)),

�� update_fact_file(NTS,POSTLIST),!,

�� means_ends_tutor(POSTLIST,GOAL,POSTOPLIST,GOALSTATE,....).

met(STATE,GOAL,OPLIST,GOALSTATE,STACK,PRELIST,PROPLIST,....) :-

�� ts_violation,retract(ts_violation),

�� retract(time_stamp(TS)),nl,

�� write("*** SORRY,IGNORED YOUR OPERATOR.� OTHER USER JUST $

�� $CHANGED THE TRUE FACT LIST"),nl,

�� write("here comes the new state:"),nl,

�� read_fact_file(NTS,NEWSTATE),

�� asserta(time_stamp(NTS)),

�� means_ends_tutor(NEWSTATE,GOAL,OPLIST,GOALSTATE,STACK, GOALSTACK).

check_wilth_student(O,S,D,NO) :-

�� write(********************),nl,

�� write("The following facts are now true:"),nl,

�� writelist(S,.state),write("."),nl,

�� write("What operator do you choose?"),nl,

�� niceread(AO2),!,check_time_stamp,

�� space_parse(AO2,O3),!,handle_student_op(O3,O,S,D,NO).

check-time-stamp :-

�� read_fact_file(TS,S),time_stamp(TS1),

�� asserta(ts_violation),!,compare(=,TS,TS1),

�� retract(ts_violation).

update_fact_file(NTS,NS) :-

�� set_channel(outfile(outf),name = "facts.pro'),

�� set_channel(outfile(outf),buffer= 1000,),

�� set_output(outfile(outf)),

�� write(NTS),nl,write(NS),

�� close_output(outfile(outf)).

read fact_file(TS,S) :-

�� set_channel(infile(d),name="work/salgado/meunrep.pro"),

�� set_channel(infile(inf),name = "facts.pro"),

�� set_input(infile(inf),skip_unread_input),

�� read(TS.),read(S,),close_input(infile(inf)).

Figure 3. Multi-user Implementation Details

V. RESULTS

A.�� MEMORY REQUIREMENTS

The required memory space for the UNREP system was 42K bytes on each of the two computers.� The breakdown for each component file was as follows:

�� METUTOR11�� 34000 bytes

�� MEUNREPDEL�� 7200 bytes

�� MEUNREPREC�� 7800 bytes

�� FACTS�� 100 bytes (maximum)

(Each student uses only one of the MEUNREPDEL and MEUINREPREC).

The amount of required memory space was insignificant compared to the space available in the ISI workstations.� If we wanted to adapt the UNREP system to work on a personal computer, additional memory would be required for a Prolog interpreter or compiler.� To give an idea, the Prolog-86 interpreter requires approximately 100 Kbytes of memory [Ref. . 13: p. 1]; even then, the UNREP system plus this interpreter could easily fit in a floppy disk.

B.�� TIME CONSIDERATIONS

With an interactive program such as the UNREP system, the total CPU time required for a tutoring session is not a meaningful measure of performance, because the run-time can vary considerably from one student to another, depending on their knowledge of the subject matter and their learning ability; a student's typing skills can greatly affect the total run-time since that can increase the amount of time spent by the tutor checking for input errors.� A tutoring session could last as little as five minutes, if both students always typed-in coordinated and correct answers, or as long as 45 minutes if the students did not have any idea of what an Underway Replenishment was all about, and they did not have typing skills.

A more meaningful measure of time performance is the time required by the tutor to reply to a student.� The time intervals, also called answering times, were measured starting from the moment a student entered his choice of operator (by depressing the enter or return key), until the moment the tutor replied a message on the screen.� The shortest answering time was of approximately 1 second (on the average), for the cases where the student entered the correct operator and the tutor accepted it with an OK, and also when the student entered a nonsensical string of characters and the tutor replied with the message "Sorry, ignored your operator ......". The longest answering times occurred when the student entered an operator which caused the inference engine to deeply analyze the student's hypothetical state (the resulting state description if the student's operator was to be applied) with calls to means-ends; in this case, the answering time could be anywhere between 5 and 30 seconds, depending on the severity of the student's misconception.� This extended answering time was also true when the operator entered by the student had some spelling errors, but this time was less than for the above mentioned case.� These answering time measures are important in ICAI applications since long periods of time waiting for a reply can decrease the student's interest in learning.

Another consideration is that of the time required by the tutor to read and write data into the common file FACTS.� It is important to avoid situations where one student's tutor would take a current state description, call it state-1, and use it to come up with a recommended operator, while meanwhile the second student's tutor could apply an operator and change state-1 into state-2; the recommended operator for student 1 would no longer be applicable.� Fortunately, the time required to read a sample FACTS file was approximately 0.22 seconds, and 0.1 seconds to write, meaning that the times were small compared to the times usually taken by the students to input operators.

Thorough testing was performed on the system to detect possible deadlocks or any other system malfunctions due to simultaneous (or at about the same time) inputs from both students.� Although we did not witness any problems during several test runs, this does not prove that they will not occur, it just makes them unlikely.

C. ACCURACY

We were concerned with the accuracy of the tutor's responses to a student's input.� We analyzed cases where a student would make spelling errors on the input operators, or input a nonsense string of characters, or aptly operators that did not agree with the tutor's recommended operator.� In all cases it was found that the system would tutor as expected.� During the first development stages of this thesis research, it was found that some tutoring statements made by the tutor did not make any sense, but it was only because the knowledge representation had some bugs, therefore causing a misinterpretation by the domain-reasoning methods.

D.�� PROBLEM COMPLEXITY

The application domain of the tutor is very complicated in reality.� The factors involved in a real-situation Underway Replenishment can be numerous and varied in type.� For purposes of this thesis, the knowledge representation was kept small to allow enough time to develop and test the system during nine months.� Even then, the steps required by a student to complete a successful UNREP procedure were 13 for both the delivery and receiving ship students, assuming that no emergencies have occurred, the students have applied all the "wait" operators, and they have not made any mistakes.

VI. CONCLUSIONS

A.�� MAJOR ACHIEVEMENTS

This thesis has developed a prototype of a new kind of computer tutor for naval training.� Traditional teaching methods involving classroom instruction can provide a student with the general knowledge in Underway Replenishment procedures, but they cannot cover all the necessary coordination skills to execute this difficult task, between two Officers of the Deck (OOD's) aboard each of the ships.� Alternatively, hands-on training is too expensive and may be dangerous.� The UNREP tutor teaches Underway Replenishment by using Artificial Intelligence (AI) techniques in an Intelligent Computer-Assisted Instruction program.� The system is capable of simulating an Underway Replenishment situation and training two students simultaneously on separate computer workstations, so that coordination skills are emphasized.� Other ICAI systems have been developed for military applications, but the novelty of the UNREP system is its ability to handle two students at the same time on a joint application.

The memory space requirements of the system have shown that the UNREP tutor is portable and can be adapted to smaller computer systems to allow training of personnel aboard ships, without expensive or hard to reach equipment.� The tutor runs sufficiently fast on the prototype machine to make speed not an issue.

B.�� WEAKNESSES AND RECOMMENDATI DNS

Although this research accomplished its major objectives, some minor weaknesses were found during the testing stage of the system.

The knowledge base representation of the UNREP procedure involved most of the important steps of the overall operation, and even an extra touch of reality was introduced to the system by adding some emergency situations.� However, a larger knowledge base would be needed if the system was to be more realistic.

The number of operators, and therefore the number of definitions in the knowledge base, have a direct impact on the time of execution, so if we wanted to have a more realistic simulation by expanding the knowledge base, we would need to figure out how to speed up the execution of the tutor program.� An alternative would be to compile the tutor instead of using the PDSS facility interpreter.� Quintus Prolog offers such a compiler, which is notable for its very high execution speed and its similarity to most Prolog syntaxes (MProlog among them).

The names of operators defined for this application were very long strings of characters.� The use of menus to display the operators and choose them is recommended for future enhancements of this system.

Tutoring would be more effective if a graphics interface was added to the system.� The current version of the UNREP system does not include actual distances between ships, bearings, speeds of ships, and colours of signal flags, among other necessary factors in a typical UNREP situation, These factors could easily be included in a graphics interface, therefore allowing better simulation and in-depth training.

[1] This means-ends program is included in the METUTOR11 listing of appendix D.

[2] This predicate is also contained in the METUTOR11 listing of appendix D.

[3] Chapter 11, section B. 1, reviews this program, and appendix E contains a listing of it.

[4] Appendices C and D contain the source code of the MEUNREPDEL and MEUNREPREC knowledge bases respectively.

[5] See appendices A and B for sample test runs.