THIS PAGE DESCRIBES A FINISHED PROJECT AND IS NOT UPDATED ANYMORE

RTES

Real-Time Expert Systems

R.A. Vingerhoeds, A.J. Krijgsman, A.V. Jones, M.G. Rodd

Introduction

Because of the time-critical situation, extra demands are put when expert and other intelligent systems in the lower levels of automation: the supervisory and control level. In these layers, the expertise of process operators and control system designers should be integrated with the time-varying information obtained directly from the process by the measurements.

A real-time behaviour is often easier to recognise than to define. A formal definition of real time is offered here:

A hard real-time system is defined as a system in which the correctness of the system not only depends on the logical results of a computation, but also on the time at which the results are produced.
The most important item is the response time. If events are not timely handled, the process can get out of control. Thus, the feature that defines a real-time system is the ability to guarantee a response before a certain time has elapsed, where that time is related to the dynamic behaviour of the system. If, given an arbitrary event or state of the system, the system always produces a response by the time it is needed, then the system is said to be real time.

Real-time systems in general and expert systems have a number of incompatibilities. These incompatibilities have mainly to do wit the management of memory. In an expert system, garbage collection in the working memory disturbs the response times, while in real-time systems this is not allowed. The resources used in a real-time system are known and have predictable computation times. In expert systems this is not the case: response times are not guaranteed and unknown resources will be used. In the higher levels of plant automation, knowledge-based problem solving techniques have been applied in domains where the data was static. No time-critical responses were required. But in a time-critical system the problem must be solved in real-time, including the knowledge-based parts. Because the data is not static but changes as a function of time, interesting problems arise:

Nonmonotonicity: Incoming data does not remain constant throughout the complete run of the system. The data is either not durable or loses its validity during the run (by external events). Then all dependent conclusions have to be removed.

Temporal Reasoning: Time is a very important variable in real-time domains. A real-time system needs to reason about past, present and future events.

Interfacing to external software A real-time system must be integrated with conventional software for signal processing and application specific I/O.

Synchronous events: A real-time system must be capable of being interrupted to accept input from unscheduled or asynchronous events.

Focus of attention: When something serious happens, the system must be able to change its focus of attention. The system will be divided into several knowledge sources, each with its own area of attention. The system must be able to focus very fast on a specific knowledge source without the behaviour of interrupted tasks deteriorating.

These special requirements are not found in most commercially available expert system shells. For control engineering purposes, only a few toolboxes are available, offering the user some real-time primitives, such as scheduled execution of rules. Besides, they exhibit much overhead because they are developed for a wide range of applications.

In the following section, an expert system structured is described, based upon a blackboard architecture using a multiple number of expert system kernels.

Progressive Reasoning

In real-time (digital) control, an important parameter is the sampling period to be chosen. The minimum sampling period which can be used is defined by the amount of time required by the system to make the necessary calculations. The time required by the inference engine to evaluate the rule base directly determines the calculation time. Because the process itself and the changing number of inferences has a great influence on which sampling period should be used by the controller, progressive reasoning is implemented (see [LATT86]).

The idea behind progressive reasoning is that the reasoning is divided into several rule bases. Every part of the rule base goes into more detail about the problem. This approach can be summarised as progressive deepening. When a rule base has been evaluated and there is still time left, another deeper rule base is evaluated in order to try to produce a better conclusion. At any time, the system can make use of one of the intermediate solutions generated by the system, as long as at least one solution has been produced, determining the minimum sampling time.

The progressive reasoning principle is very well suited for process control purposes. With the application of a direct digital controller using AI-techniques, a problem arises when the sampling period is chosen smaller than the time required to evaluate the complete rule base. This will cause a situation where the inference engine cannot prove a hypothesis. Since all hypotheses are indirectly coupled to a control signal, the expert system will not be able to control the process. To solve this problem, the rule base is divided into a set of different knowledge layers, each with its own set of hypotheses and therefore its own set of control signals. The minimum length of the sampling period which can be used is now defined by the time required to evaluate the first knowledge layer. This first knowledge layer will generate a fairly rough conclusion about the control signal. The next layers are used to produce a better control signal using more information about the process to be controlled.

In a typical example using this progressive reasoning principle, the lowest (fastest) layers are used to implement a direct expert controller, while the next layers are used for a more advanced type of control (intelligent control) such as supervisory and adaptive control.

One of the assumptions made on the use of progressive reasoning is that the problem can be decomposed into smaller subproblems. However, this may not be easy or straightforward, it might even be impossible to define appropriate progressive reasoning levels. This problems is left to the system designer. The second problem which can arise is that the maximum time available for reasoning may be so small that only the lower levels are processed and the higher levels are never reached. This problem can be solved by introducing adaptive sampling. Whenever many things are happening in the system (start of a step response for example) a lot of information can be obtained from the system and fast sampling can be used for the controller. For steady state situations, the sampling frequency for the controller can be decreased, leaving more time for other procedures to be evaluated (optimisation, monitoring diagnosis, etc.).

Truth Maintenance System (TMS)

When knowledge is evaluate, for example a production rule, the consequent part is set true if the antecedent part was satisfied, else it will be set false. The consequent part will be stored as facts or knowledge in a database. Knowledge remains in this database until it is explicitly removed. In a real-time control system, we are dealing with time-dependent information: data can be valid during a certain period. A Truth Maintenance System (TMS) takes case of these problems. Such a TMS provides nonmonotonic reasoning, so the growth of knowledge is not monotonic with time. At certain time instants, knowledge can lose its validity and all dependent conclusions should therefore be removed. There are several events which can make knowledge invalid:

Knowledge can lose its validity, because new knowledge is acquired by evaluating the rule base. This new knowledge excludes the old knowledge. To remove the old knowledge, special commands must be added to the syntax of the expert system, in order to wipe knowledge out of the database of known facts. By removing this knowledge, all dependent information will be removed.
Knowledge can only be valid within a specific time interval, for values expressing the performance of a process. These values will only be valid with a limited period of time, due to the fact that the system can change, or the fact that the performance depends on the controller applied to the system. All knowledge which depends on these derived performance values, should be wiped from the database, containing all known facts, at the end of the interval during which the knowledge is valid.

The TMS has to keep track of every inference step in the reasoning process. In general this can be a time-consuming task, but necessary for the correct functioning of an automated reasoning program.

Temporal Representation

In real-time expert systems the use of logic which can express temporal information is an important issue. Time and its properties must be represented explicitly. Temporal models in AI can have either an explicit time representation based on time points or can be based on intervals. In literature several temporal logic-based models are proposed for both point-based (e.g. see [DEAN87] and [PERJ90]) and interval based models (see [ALLE84]). Allowing for temporal representations in an expert system requires the definition of object structures in which this information is stored. The main temporal information of an object is given by the past values of information, the current value and eventually a list of (predicted) future values. The values are also temporal information expressed in an object which stores the begin and end time of a value and the time which it was taken.

The Truth Maintenance System has to keep track of this temporal information in order to maintain the validity of the knowledge base and the database and offering temporal reasoning facilities.

Real-Time Expert System Architectures

A blackboard architecture is seen as one of the best alternatives to implement knowledge-based systems in a real-time framework (see [HAYE90]). In a blackboard system several knowledge sources are communicating (in parallel). In the blackboard database the values of some variables are stored, like in a memory. This blackboard database, or short term memory, can be accessed by several knowledge sources. Each knowledge source has the following features:

It contains the knowledge about one subproblem
Data is stored in a common structure
Knowledge sources share information through a mechanism by the blackboard
A knowledge source cannot access data of another source directly.

For a real-time expert system such an architecture using the multiple knowledge source idea to implement several expert systems running in parallel is convenient. Each knowledge source can be used to solve a subproblem.

A blackboard consists of three components: (a) the database of the blackboard, (b) the formalism of each knowledge source, and (c) the control component. Each of these components is described in more detail hereafter.

Blackboard Database

The database of the blackboard is used to store the data of the knowledge sources and provides means to manage them. The main problems are connected to the concurrent access of several parallel inference tasks, trying to access data (or objects) in the database. Important issues in the organisation of this database are:

a possible representation of temporal knowledge
updating and retrieving of information from the database
uncertainty management

A well-structured approach for the protection of data is the principle of message-passing between objects.

Formalism of Knowledge Sources

In a knowledge source, a collection of activities is combined. It represents a separate task which has to be executed using its own inference engine. The reasoning mechanism in such a knowledge source must be efficiently implemented. Several algorithms are proposed in literature, which were developed to provide real-time pattern matching. The best known algorithm is the Rete-algorithm (see [FORG82] and chapter Expert System Techniques).This method builds a network compiled from the conditional parts of the rules and inputs are changes in the working memory. Another formalism which fits into this concept is the progressive reasoning principle.

Control Component

This component plays an important role. It determines which knowledge is scheduled with the highest priority to meet the deadline. The control module decides when a knowledge source is allowed to access the blackboard database. Scheduling the tasks to be performed by the knowledge sources can be carried out in various ways common to solutions used in real-time operating systems. The most common solutions in literature are (see [YOUN82]):

Priority scheduling
Deadline scheduling
Progressive reasoning

Concluding remarks

A blackboard configuration using multiple knowledge sources allows for a distributed knowledge-based approach. Each knowledge source can use its own problem-solving technique. For a knowledge based control system, each knowledge source can be used to implement a view on the control system, using the appropriate tool to solve the problem. A typical knowledge-based control system, using a blackboard approach, will contain various methods in parallel solving subproblems from different views upon the system. These views correspond to various AI-related methods to solve the specific problems.

A State-Based Approach

Background

To overcome the problem that for existing expert system development tools it is not possible to guarantee any worst-case response times (see [JONE93]), an alternative approach to the development of expert systems for hard real-time applications has been proposed in [JONE94] and [JONE95a]. A state-based architecture is adopted, as opposed to the event-based approach used by existing real-time expert system shells. In a state-based system only one process is active at any time. Hence, every process has exclusive access to any global data and no process will be pre-empted. This eliminates the problems associated with controlling access to global data, such as the blackboard of an expert system.

The use of a state-based architecture overcomes some of the problems of predicting the execution times of expert systems. However, it does not solve the problem predicting the execution times of the inference process. To do this, a rule-set compiler has been developed, which converts an expert system rule-set into simple non-recursive procedural functions with an execution time that is largely unaffected by the input data (see [JONE94]). This allows guaranteed worst-case execution times for the expert system to be determined. In this way, searching within an expert system is for a large part performed off-line. On-line, a relatively simple search process remains. The rule-set compiler generates, from a given knowledge base, C or Fortran language functions with a known worst-case execution time, that are logically equivalent to the knowledge base.

Application of the State-Based approach for Flight Control

The NECTAR-project (Neural and Expert ConTrol of AircRaft) aims at investigating the application of artificial intelligence to flight control (see [VING94]). This application, subject to very strict real-time requirements, is characterised by a highly non-linear and time-varying behaviour. In the project, two main streams of research can be identified, neural networks / fuzzy systems, and real-time expert systems. The two independent developments will lead at the end of the project to one total approach to intelligent flight control. Here, the application of real-time expert system in the landing phase of aircraft is discussed.

In the project, expert systems will be used to serve three main goals:

Expert systems can be used as a supervisory layer over other (neural) controllers. Set-points can be set, the overall performance can be monitored and, if necessary, adjustments can be made.
In some flight phases, strict, imposed procedures, such as emergency procedures, have to be followed. In such situations, rule-based expert systems offer many advantages over neural networks. Expert systems are far better suited for controlling discrete tasks such as deflection of flaps and landing gear than a neural network.
One of the disadvantages of neural networks is that it is very difficult to predict the limits of their correct operation. This is a serious problem, especially in safety-critical control systems. An expert system can monitor the performance of the neural controller and take corrective action if needed. Hence, with the addition of an expert system, the overall control system guarantees good operation even outside the limits of validity of the neural controllers.

Within the overall architecture of the NECTAR system, the expert system performs a dual role:

it performs the high-level control tasks (for example, it can abort the landing in the event of an unacceptable situation arising),
it monitors the performance of the low-level control system and can impose changes if necessary.

To fulfil its second role, the expert system must be able to directly control the aircraft controls (elevator, ailerons, rudder, flaps, landing gear and engine controls), bypassing a (possibly defective) low-level controller. Within the framework of the current application, where a Cessna Citation II business jet is studied, the maximum time available for the expert system to generate a suitable answer is 33 milliseconds. The low-level control tasks are currently assumed by conventional PID controllers. Later in the project these will be replaced by neural networks.

This combination of neural network and expert system, allowing the use of symbolic and sub-symbolic reasoning techniques on data from different sources and in different representations, leads to a potentially, very powerful flight control system.

The Nectar Expert System

In this work, the real-time expert system approach as explained above and [Jone95a] is applied to flight control. Here the chosen control structure is explained.

The Structure of the Expert System

The expert system consists of a supervisor, several control modules and low-level controllers. The role of the supervisor is to assess the flight and health condition of the aircraft and to decide on the course of action to be taken. The supervisor does not perform direct flight control. This is handled by the control modules. Each phase of the landing procedure is controlled by a �control module�. In addition, special control modules have been developed to handle abnormal situations, emergency landings, or prescribed procedures. The supervisor detects occurring malfunctions and selects the appropriate control module. The following tasks are performed by the supervisor:

It performs fault detection. Proper operation of flaps, landing gear and engines are verified, by verifying the desired values against the actual values. The flaps, landing gear and engines cannot instantly reach new settings and so an allowance is made for the required time for the actuators to achieve the new position.

It assesses the current (health) state of the aircraft. This is based on the current aircraft status / position and the fault detection results. The supervisor then decides on the control module to be selected.

The supervisor safeguards the aircraft operation, using so-called 'watchdog' rules, specifying the limits of safe operation during each part of the landing. The watchdog rules specify permitted positions and attitudes for each stage of the landing. Exceedence of limits set by these rules will cause the landing to be aborted. When the main watchdog rule is fired, a suitable control module must be selected, taking into account the current aircraft condition (e.g. if an engine failure has occurred). The watchdog stage will override the status that was selected by the previous part of the supervisor.

The individual control modules assume responsibility for actions such as deflection / retraction of flaps and landing gear, etc.

Descent	This module brings the aircraft down to level flight at an altitude of 350m, for interception of the ILS signals.
Final Approach	An initial altitude of 350m is maintained until the Glide Slope signal from the ILS is intercepted. A smooth transition from level flight to a constant rate of descent is ensured after which the aircraft follows the glide slope. Below 50m, following the glide slope signal becomes difficult and a constant rate of descent is maintained instead, until the flare is initiated. The localiser signal is used to guide the horizontal position of the aircraft. If the ILS signals are temporarily lost, the expert system will hold the aircraft on its current flight path. To ensure touchdown at the runway threshold, a verification is made at an altitude 50m that the ILS signals are acceptable - otherwise, the landing is aborted.
Flare	At the end of the descent, the aircraft must be brought to an almost level flight for touchdown. The nose of the aircraft must be aligned with the runway orientation during the flare stage.
Roll out	After touchdown, the aircraft must be brought to a halt on the runway, using speedbrakes and footbrakes (when the speed allows).
Abort	In the event of an unsuccessful approach, or when air traffic control imposes, the aircraft must climb clear of the runway as rapidly as possible.
Go-around	After an aborted landing, when the aircraft is climbing safely, the aircraft must be brought at a constant rate of climb until an altitude of 1000m is reached. If the landing is aborted at an early stage in the approach the abort module is not selected and control is passed directly to the go-around module.

The modules described above are used to control the aircraft under normal conditions. A further set of modules are used for single engine landings and for landing with the flaps inoperative. These perform a similar function to the normal control modules, but also take account special requirements and imposed procedures.

Low-level Control Systems

Control of the control surfaces (rudder, elevator and ailerons) and of the throttles, may later in the project be done using neural networks based controllers, but are for the moment done using PID controllers. The low-level control module also contains a small expert system to select the most appropriate controller in a given situation. This allows a different control law to be selected, for example, at low speed. The expert system will also override a request from the high-level modules to maintain a particular altitude if the current altitude is greatly different from the required altitude. The expert system will instead select a rate of climb control until the required altitude is reached and then engage the altitude-hold controller. In this way, unacceptable vertical speeds are avoided. When symmetrical thrust is available (i.e. both engines operating), the heading of the aircraft is controlled using the ailerons, with the rudder being used simply to damp the yaw motion. In the case of a single-engine approach, rudder is also use to maintain the correct heading.

Implementation

Initial off-line testing of the system was performed on a Sun Sparc Workstation, using a version of the simulation software ported to the UNIX environment. After the off-line testing of the system, it was implemented on the Flight Simulator of Delft University of Technology, where a full blown simulation of the Cessna Citation is in use, based on FAA Phase II certified mathematical model of the aircraft. The flight simulator uses a Gould/Encore MPX 32/87 Super-Mini computer, driving the flight instruments, a vision system and a three degrees of freedom motion flight simulation.

For tests with the expert control system, both the generation of the control inputs by the expert control system and the simulation of the aircraft behaviour itself had to be done within the 33 milliseconds. Due to limitation of the existing infrastructure, unfortunately only a part of the complete expert control system could be tested. The maximum size of executable code (the load module) on the Gould/Encore computer is limited to 512 Kb. The MPX operating system requires 143 Kb of this memory, leaving only 369 Kb for the simulation software and the expert control system. When the complete expert control system is loaded together with the simulation software, an executable module is produced that is slightly larger than the permitted maximum. Extended memory is available, but can only be used for data storage, and not for executable code. To overcome this problem for the purpose of testing, the expert system was split into dedicated blocks; normal landings, landings with the flaps inoperative etc., to be tested separately. This not expected to have influenced the timing characteristics greatly, because of the state-based approach.

Results

The simulation software contains a facility to record the average CPU time for each routine. This feature allowed the average execution times of the NECTAR expert system to be measured during various manoeuvres. Table 1 gives the measured execution times of the expert system.

Flight Phase	CPU time (milliseconds)
Normal Landing	7.006
Aborted Landing	6.998
Flapless Landing	7.521
Single Engine Landing	7.027

Table 1 Measured CPU-times

Although these are measured average execution times, for a state-based approach this means that the worst-case execution times will not differ very much from these figures.

Concluding remarks

The combination of expert system technology with neural networks can lead to a powerful flight control system. The developed expert control system is able to control the aircraft safely under a variety of different flight conditions, including non-standard manoeuvres such as landing with one engine inoperative. The execution times of the expert system and low-level controllers are all well within the maximum allowed time, showing that real-time operation of the system can be achieved. Low-level control is currently being performed using PID controllers. These will later be replaced by neural network-based controllers, to pursue improved low-level control.

References

[ALLE84]	Allen J.F. (1984). Towards a General Theory of Action and Time. Artificial Intelligence, Vol. 23.
[DEAN87]	Dean T. and D. McDermott (1987). Temporal Database Management.Artificial Intelligence, Vol. 32.
[HAYE90]	Hayes-Roth B. (1990). Architectural Foundations for Real-Time Performance in Intelligent Agents. Real-Time Systems, Vol 2.
[JONE93]	Jones and Rodd 1993Jones, A.V. and M.G. Rodd (1993). Problems with Expert Systems in Real-time Control. Engineering Applications of Artificial Intelligence 7(3) pp. 499 - 506
[JONE94]	Jones and Rodd 1994Jones, A.V. and Rodd (1994). An Approach to the Design of Expert Systems for Hard Real-time Control, proc. IFAC Workshop on Safety, Reliability and Applications of Emerging Intelligent Control Techniques, Hong Kong 1994
[JONE95a]	Jones, A.V. (1995). An Approach to the Design of Expert Systems for Hard Real-time Applications. PhD-thesis, Dept. Electrical and Electronic Engineering, University of Wales Swansea.
[JONE95b]	Jones, A.V., R.A. Vingerhoeds and M.G. Rodd (1995). Real-Time Expert Systems For Flight Control. IFAC Workshop Artificial Intelligence for Real-Time Control, submitted for publication.
[KRIJ88b]	Krijgsman A.J., P.M. Bruijn and H.B. Verbruggen (1988). Knowledge Based Control. 27th IEEE Conference on Decision and Control, Austin, USA.
[LATT86]	Lattimer Wright M., M.W. Green, G. Fiegl and P.F. Cross (1986). An expert system for real-time control. in: IEEE Software, pp. 16-24, March.
[OREI86]	O'Reilly C.A. and A.S. Cromarty (1986). Fast is not "Real Time". in Designing Effective Real-Time AI Systems. Applications of Artificial Intelligence II 548, pp. 249-257. Bellingham.
[PERK90]	Perkins W.A. and A. Austin (1990). Adding Temporal Reasoning to Expert-System-Building Environments. IEEE Expert, February.
[VING94]	Vingerhoeds and Krijgsman 1994Vingerhoeds, R.A., A.J. Krijgsman (1994). Neural Networks for Flight Control, proc. Artificial Intelligence in Real-Time Control, Valencia, 5-10 oct.

Acknowledgements

R.A. Vingerhoeds, A.V. Jones and M.G. Rodd would like to acknowledge the generous support of British Council and the Dutch Science Foundation NWO. A part of the research presented in this paper was carried out under Joint Research Project JRP 068.

Updated by Rob Vingerhoeds (rob@kgs.twi.tudelft.nl)

Last Update 06-11-1997.

THIS PAGE DESCRIBES A FINISHED PROJECT AND IS NOT UPDATED ANYMORE