Neural Computing for Numeric-to-Symbolic Conversion

in Kevin M. Passino,

ABSTRACT: Neural computing offers mas- sively parallel computational facilities for the classification of patterns. In this paper, a cer- tain type of neural network, called the mul- tilayer perceptron, is used to classify nu- meric data and assign appropriate symbols to various classes. This numeric-to-symbolic conversion results in a type of “information extraction,” which is similar to what is called “data reduction” in pattern recognition. After introducing the idea of using the neural network as a numeric-to-symbolic converter, its use in autonomous control is discussed and several applications are studied. The perceptron is used as a numeric-to-symbolic converter for a discrete-event system con- troller supervising a continuous variable dy- namic system. It is also shown how the per- ceptron can implement fault trees, which provide useful information (alarms) in a bi- ological system and information for failure diagnosis and control purposes in an aircraft example.

Introduction An important new branch of control theory

is concerned with the study of discrete-event systems, which include manufacturing sys- tems and traffic systems. Another relatively new area is the field of autonomous control theory, where “intelligent” controllers are used to control complex systems. Such sys- tems include certain space systems and au- tonomous land and underwater vehicles. In both cases, as is explained below, symbolic (automata-theoretic) formalisms, as opposed to conventional differentiaUdifference equa- tion approaches, are often used in controller development. Frequently, however, portions (or all) of the plant output are numeric data rather than symbols. There is then the need to convert the numeric data to symbolic in- formation, i.e., to perform numeric-to-sym- bolic conversion. Such a conversion is, for instance, inherently performed by fault trees

Kevin M. Passino, Michael A. Sartori, and Panos J . Antsaklis are with the Department of Electrical and Computer Engineering, University of Notre Dame, Notre Dame, IN 46556.

Control Systems Michael A. Sartori, and Panos J. Antsaklis

in chemical process control to detect failures from plant data. Another example of such conversion is to reject or accept items in a manufacturing system based on their com- pliance with a tolerance. In this paper, a cer- tain type of neural network, called the rnul- tilayer perceptron, is used to perform the numeric-to-symbolic conversion task. This paper is an expanded version of the work presented in [l].

The goal of this paper is to introduce the idea of using the multilayer perceptron as a numeric-to-symbolic converter to provide measurement information for specific control purposes; there is no contribution to the the- ory of neural networks or pattern recogni- tion. The work involves the application of a particular neural network to problems often encountered in some of the more recent de- velopments in control theory. In particular, the results of this paper show one alternative for implementing the interface between nu- meric and symbolic information, a problem of significant importance. The results here also suggest that the use of numeric-to-sym- bolic (and symbolic-to-numeric) converters is a possible starting point in system design (e.g., for “hybrid” systems). Other appli- cations of neural networks to control have been in adaptive systems, since neural net- works have an inherent learning capability. (See, for instance, the special section on neural networks for systems and control in [2].) Such applications are not studied here since the learning capabilities of the percep- tron used are not utilized.

Neural computing involves the use of neural networks to perform computations in a massively parallel fashion. A neural net- work is a model that represents the structure and function of the interconnected network of neurons in, for instance, a human brain. Researchers hope to emulate the highly ef- ficient “computing” that humans perform with ease. Here, a certain neural network, called the multilayer perceptron, is used to classify numeric data and assign appropriate symbols to the various classes. It is a feed- forward model that is restricted so that it does not self-adjust its weights or learn. The

classification it performs is a form of infor- mation extraction from given data. It is per- formed with massively parallel computing; hence, it is inherently faster than conven- tional sequential processing.

The conversion of numeric data to sym- bols is a form of information extraction. In- tuitively speaking, information extraction is the transformation of detailed information into abstract, generalized information; there is always a certain loss of information in the extraction process. Here, the detailed infor- mation is an n-dimensional vector of real numbers, the numeric data. The abstract in- formation is a set of symbols representing regions in the n-dimensional space. The in- formation extraction process is performed here using the multilayer perceptron. The type of information obtained is, for example, “signal 1 is greater than 0 and less than 5, and signal 2 is greater than -3 and less than 10.” The information lost in our extraction process is the exact value of the real num- bers. (The “symbols” we refer to may not satisfy various mathematical properties such as addition and multiplication; however, they are normally chosen to have a particular physical interpretation.) It is understood that there are other types of information extrac- tion, e.g., when the behavior of the system generating the data is characterized. Char- acterization of behavior could involve find- ing that “signal 1 is the derivative of signal 2.”

The process of information extraction via the neural network studied here is closely related to what has been called pattern rec- ognition. In fact, the multilayer perceptron solves what are called “deterministic clas- sification problems” [3]. Similar problems have also been studied using the threshold logic circuits (networks) described in [4], except that in these circuits the theory only allows a finite number of discrete inputs, U. The pattern recognition process is viewed as a three-step “data reduction” process [3], PI:

(1) Sensors make measurements of certain variables in the environment.

0272-1708189i0400-0044 $01 00 1989 IEEE

44 I E E E Control Systems Magazine

(2) Feature extraction is then used to obtain a more global, high-level description of the measured data.

( 3 ) Classijication algorithms are used to name the pattern.

The viewpoint can be taken that this com- plete process is performed by the multilayer perceptron. The patterns sensed are points in the n-dimensional space of real numbers. Feature extraction entails determining which region each element of the n-dimensional vector lies in. Classification involves taking logical combinations of these regions and at- taching labels to them. Rather than viewing the numeric-to-symbolic conversion process as a traditional pattern recognition problem, we prefer to view the multilayer perceptron as the device that performs only step 1 (in the preceding process) of a more abstract recognition process in which the goal is to take some action based on the pattern de- tected. For step l of the more abstract pro- cess, the perceptron senses data in the en- vironment and provides symbols as its measurements. These symbols are then used by a controller to make decisions on what to input into the plant. Clearly, the controller may need abstract, “symbolic” feature ex- traction and classification to complete the high-level pattern recognition so that it can make its decisions, but these problems are not studied here. A similar view of pattern recognition is taken in [6]. Note that the method used here does not employ the more complex pattern recognition techniques (e.g., statistical or syntactical) to recognize wider classes of patterns. For example, as indi- cated earlier, it will not characterize the dy- namical behavior of the environment over a period of time. For more information on pat- tern recognition techniques, see, for in- stance, [ 3 ] , [7]. An alternative view from the perspective of artificial intelligence that sup- ports the preceding ideas on the abstract classification process is given in [ 8 ] .

Numeric-to-symbolic conversion can be used in several different ways in control sys- tems. It can be used in the control of certain discrete-event systems, in autonomous con- trol applications, and to implement fault trees. The three applications summarized here are described in more detail in the next section. The first applications considered are certain discrete-event systems. Note that there are cases when discrete-event control- lers can he used for the control of continuous variable systems. In these instances, there is a need for a numeric-to-symbolic converter to provide the symbols to the controller. In the case of autonomous control, there is a “symbolicInumeric interface,” where high-

level, possibly “intelligent,” controllers are used to control continuous systems [9 ] , [IO]. The multilayer perceptron can be used to convert numeric information into more ab- stract symbolic information for use in, for instance, a planning system. Finally, the in- formation can be extracted by the perceptron so that it is useful in higher-level control decisions. For instance, the information pro- vided by afault tree on the failure status of a plant (what alarms should be on or off) can be used to generate appropriate control ac- tions so that the effects of the failures can be eliminated. It is shown here that the multi- layer perceptron can be used to implement a fault tree to produce alarms.

In the sections that follow, the theory of the multilayer perceptron is outlined. Next, three examples are presented. First, an ex- ample of the use of the perceptron as a nu- meric-to-symbolic converter for a surge tank is given. Next, it is shown how the percep- tron can be used for the implementation of fault trees for a biological system and an aircraft. The paper closes with some con- cluding remarks and future directions.

Information Extraction in Control Systems: The Numeric-to-Symbolic

Converter In this section, we discuss several ways in

which information extraction is used in con- trol theory. In practice, information is al- ways extracted-in the modeling of pro- cesses, for example. The extraction we discuss here is the transformation of numeric data to symbolic information, which is done dynamically in an on-line control system. There are three main applications to control theory discussed here.

The first is discrete-event systems. There are dynamic systems that either cannot be described by differentialidifference equa- tions, or it is not desirable to do so because subsequent analysis and design is very com- plicated, awkward, or simply inadequate. An alternative approach is to begin with a dif- ferent model. In [ I l l , the authors give an example of how to use a symbolic formal- ism-the nondeterministic finite-state au-

tomaton-to describe a plant (a surge tank) that is normally described with a nonlinear differential equation. Using this description, a finite-state controller was given and certain closed-loop properties were verified. In these cases, for controller implementation, a nu- meric-to-symbolic converter is needed to convert the sensor data to symbols for use in the discrete-event controller. The perceptron developed here is used to implement this converter. Another example of a combined study of discrete-event and continuous sys- tems is given in [12].

The discrete-event controllers considered in this paper will be referred to as symbolic controllers, since they are developed using a symbolic formalism (automata-theoretic) and have symbols as inputs and outputs rather than numeric data. (Of course, numbers are symbols too, but the symbols we refer to here may not possess mathematical proper- ties such as addition or multiplication.) The situation where we have a symbolic control- ler controlling a continuous variable dy- namic system is depicted in Fig. 1 . The syni- bolic controller uses Y, (symbols) as inputs and a reference input, say, R, (symbols), and generates the control inputs to the plant U, (symbols). The numericisymbolic converter transforms the measurement data y ( f ) into symbols Y, . The symbolicInumeric converter transforms the symbols U, into numeric plant inputs u(t) .

The numericIsymbolic converter can be thought of as analogous to the analog-to-dig- ita1 (AID) converter in digital systems. In the one-dimensional case, the real number line (numeric data) is partitioned into regions associated with, say, binary numbers (sym- bols), and the values of the input are con- verted into the appropriate binary numbers. Indeed, there have been neural network im- plementations of a 4-bit AID converter [ 131, [14]. The work here generalizes that appli- cation to the multi-input case using a differ- ent neural network. In addition to perform- ing a more general conversion process than AID conversion, the perceptron can operate in an asynchronous mode as well as in a synchronous one. Note that the perceptron can be expected to perform numeric-to-sym-

Fig. I . Symbolic/numeric conversion.

April 1989 45

bolic conversion quickly. This is very im- portant if it is to be placed in the control loop, because delays tend to cause instabil- ity. The symbolic controller’s control ac- tions on the continuous plant can be trans- lated into numeric inputs by a generalized method analogous to digital-to-analog (D/A) conversion. It may convert a symbol to a simple numeric value or to a sine wave, square wave, or some other more complex signal. This problem is not addressed here.

Autonomous controller architectures can be viewed as hierarchical with three main levels (see, for example, [9], [IO], and the references therein). These are the manage- ment and organization level, the coordina- tion level, and the execution level. The ex- ecution level contains the hardware and conventional control algorithms performing low-level feedback control. The manage- ment and organization level has the interface to the operator and the intelligent learning and planning systems for supervising the ac- tions taken at the lower levels. The cooi-di- nation level provides a link between the management and organization level and the execution level. Autonomous controllers are used in the control of very complex systems that are normally hybrid. A hybrid system is one that contains dynamics that can be de- scribed by, for instance, differential or dif- ference equations, and dynamics that are convenient to describe with some symbolic formalism. The controllers developed for such systems are also hybrid, with various numeric and symbolic components at each of the three levels. The numeric-type algo- rithms normally are used at the lower level of the architecture, the execution level, whereas the symbolic-type algorithms are operating at the highest level, the manage- ment and organization level. There is then a symbolicinumeric interface in the autono- mous controller much like the one in certain discrete-event systems discussed earlier. Consequently, the perceptron developed here will be useful in autonomous control appli- cations.

The results can also be used in the field of intelligent control called expert control. The “safety nets” in 1151 use information ex- traction of ranges of variables for making high-level control decisions in adaptive con- trol. The results of this paper provide a method to produce the information for such control decisions. In [lS], the authors pro- pose to use an expert controller, one that uses an expert system to emulate the actions a human operator would perform to maintain an adaptive controller’s operation. The hu- man in the control loop is being emulated. It is then natural to use a perceptron to em-

ulate the human’s pattern classification abil- ities.

In general, the multilayer perceptron can be used to classify data so that control de- cisions can be made. The symbols attached to various regions of the n-dimensional space of real numbers may have a particular phys- ical interpretation. The perceptron can pro- vide failure information such as “signal 1 is in range 4 AND signal 3 is in range S OR signal 7 is in range 1 I . ” This information may be quite useful in making control de- cisions. For instance, the values of signals 1, 3, and 7 may indicate that a certain failure condition is occumng and that a specific control action ought to be taken so that the failure will not degrade system performance. Failure information of the type described earlier is typically generated by fault trees [16], [17]. The low-level failures in fault trees are characterized by regions of certain variables, and fault-tree high-level failures are characterized by logical combinations of the low-level failures. Here, the multilayer perceptron determines in which regions cer- tain variables appear and performs the ap- propriate ANDing and ORing to indicate what high-level failure has occurred. In the following section, an outline of multilayer perceptron theory is given.

Multilayer Perceptron for Numeric-to-Symbolic Conversion The multilayer perceptron is a feedfor-

ward neural network used for neural com- puting (see, for example, [18]). The multi- layer perceptron considered here contains a single hidden layer between the input and the output layers, as illustrated in Fig. 2 for the case of two nodes at each level. This cascading concept is well understood in con- trol systems. For example, with two hidden layers, the output layer is measured directly, The first hidden layer feeds the output layer; the second hidden layer feeds the first hidden layer. The input of the perceptron is applied to the second hidden layer. The input to the multilayer perceptron considered here is the vector U with components U,, and it contains M continuous real-valued elements. The vector x’ (with components x,’), which con- tains M , binary elements, is the output of the input layer and the input to the hidden layer.

The vectorx”, which contains M2 binary ele- ments, is the output of the hidden layer and the input to the output layer. The vector y (with components y i ) , which contains N bi- nary elements, is the output of the percep- tron.

In Fig. 2 , the nodes are denoted with cir- cles and the biases with arrows that point downward. The biases on the input layer are denoted by b: , on the hidden layer by b,“ , and on the output layer by b,. The weights are denoted by all of the other arrows (which will be labeled with the weights) that are between U and the input nodal layer, between x’ and the hidden nodal layer, and between x” and the output layer. The element w,] of the M X M , matrix “denotes the weight on the arc from U, to the node with x; as its output. The M I X M, matrix W‘ denotes the weights on the arcs from each x,’ to the node with x;’ as its output. The M2 x N matrix W” denotes the weights on the arcs from each x: to the node with y j as its output. The weights on the arcs connecting the output nodal layer to the outputs y , are unity. For convenience, if the weight of any arc is zero, the arc will be omitted from the graphical representation of the perceptron.

Each node produces at its output a sum- mation of its weighted inputs and its bias, which is passed through a threshold nonlin- earity. The result is a binary output for each layer. Two typical threshold nonlinearities are illustrated in Fig. 3.

The input to the ith threshold nonlinearity of the input layer, denoted by f , ( t ) , is the weighted sum of the inputs added to the bias.

M

/ = 1 f , ( Z ) = c (W,,U/(tN + b: (1)

If f k , denotes a threshold nonlinearity of type k for the ith node, then the output of the input nodal layer is given by

x,’ (4 = f n , (1, (0) ( 2 )

The outputs of the hidden layer and the out- put layer are given by similar relations. With these equations, the input-output relationship for the multilayer perceptron is easily spec- ified. These equations were used for the de- velopment of the multilayer perceptron sim- ulations in the examples.

gI ..w

Fig. 2 . Multilayer perceptron for two nodes at each layer.

46 I € € € Control Systems Mogodine

(a) (b)

Fig. 3. multilayer perceptron.

Threshold nonlinearities f o r the

The multilayer perceptron is commonly used for pattern classification. In the classi- fication problem, one desires to identify cer- tain “decision” regions that the input vector U lies in. Examples of dividing a two-di- mensional input space into decision regions are illustrated in Fig. 4. An input pattern U

is presented to the perceptron. After pro- cessing, the output vector y represents cer- tain decision regions. In particular, if U is a member of one decision region, an appro- priate element of the output vector y be- comes a l (HI). If the input pattern U is not a member of a particular decision region, an appropriate element of the output vector y becomes a 0 (LO).

The weights and biases of the multilayer perceptron depend on the decision regions to be identified. The technique used to deter- mine the weights and biases (and number of nodes) for the multilayer perceptron will be referred to herein as the “Harvey method.” It is based on the results presented in [18] and is outlined as follows:

( I ) Determine: (a) decision regions (hyperplanes), and (b) symbols that characterize various re-

(2) To define the input nodal layer, for each gions.

hyperplane: (a) Add a node to the input layer, and (b) Define the weights and bias from

each perceptron input to the node using the hyperplane definition.

( 3 ) To define the hidden layer, use one node for each logical conjunction of input no- dal layer outputs needed to define the output symbols.

(4) To define the output layer, use one node for each logical disjunction of hidden

(a) (b)

Fig. 4. Examples of two-dimensional decision regions.

April 1989

nodal layer outputs needed to define the symbols output from the perceptron.

Notice that not only are the weights and biases determined, but also the actual num- ber of nodes in each nodal layer. As with the weights and biases, the number of nodes also depends on the decision regions to be identified. The three layers of the multilayer perceptron, as shown in Fig. 2, are named (from left to right) the inputlplane layer, the AND layer, and the ORioutput layer. The input/plane layer consists of nodes repre- senting the hyperplanes dividing the input space. For example, in Fig. 4(a), region A needs eight one-input input/plane nodes since the region is constrained by eight different lines. The AND layer consists of one AND node for each decision region defined by more than one hyperplane. For example, in Fig. 4(a), region A needs two four-input AND nodes, each to denote that U is below one line, to the left of another line, above one line, and to the right of still another line. In other words, each four-input AND node will indicate that U lies in one of the two boxes that define region A. The OR/output layer consists of nodes used to associate dis- joint decision regions. For example, in Fig. 4(a), region A needs one two-input OR/out- put node to indicate that U lies in one of the two boxes. Using the preceding method, the weights depend on which side of the plane the decision region lies, and the biases de- pend on the locations of the decision regions. As an alternative, the weights and biases could be determined by passing sample de- cision region data through the multilayer perceptron and updating the weights and biases based on a training (learning) algo- rithm (see [18]).

There are numerous other methods used to automatically adjust the weights and biases; these are considered to be learning algo- rithms. For instance, the Back-Propagation Training Algorithm, which is presented in [19], [20], can be used for perceptrons sim- ilar to the one shown in Fig. 2. This algo- rithm may be particularly useful if the input space must be divided into decision regions that are separated by curved borders. In [21], three other training procedures are intro- duced and compared to the Back-Propaga- tion Training Algorithm. In [22], an alter- native to the Back-Propagation Training Algorithm, called the Selective Update Back- Propagation Algorithm, is introduced and shown to work in cases where the Back- Propagation Training Algorithm will not. Through the presentation of input data, the multilayer perceptron’s output, and the de-

weights and the biases until they stabilize. Although the Back-Propagation Training Al- gorithm seems to work for most cases, con- vergence of the algorithm has not yet been proven for the fully interconnected multi- layer perceptron [ 191, [20]. Convergence for the lightly interconnected multilayer percep- tron is considered in [23].

Examples of Numeric-to-Symbolic Conversion in Control Systems

In this section, three examples of how nu- meric-to-symbolic conversion can be per- formed via the multilayer perceptron are given. A discrete-event system is studied in the first example, and fault trees are pro- duced for the last two.

Surge Tank

The first example, from chemical process control, involves a liquid-holding surge tank similar to the one studied in [ l l ] . The tank is viewed as a discrete-event system, and its liquid level is controlled by a symbolic con- troller. The controller is a simple map from the plant outputs (liquid levels) to the plant inputs (valve open or closed). The tank is depicted in Fig. 5 . The empty valve is un- predictably opened by some user, and the controller turns the fill valve on and off to keep the tank from becoming empty or full. The surge tank can be described with the first-order nonlinear differential equation WI,

dh( t ) /d f = { F ( ( t ) - k c ( t ) [ h ( f ) ] ” * } / p A

(3)

where p = 99.8, the fluid density of the liquid (water), A = I , the cross-sectional area of the tank, h(r) is the height of the liquid in the tank, and k = 1O00, a physical constant. The value of ~ ( t ) represents the variable outflow pipe cross-sectional area. The unpredictable user is modeled as c(t) = O.lc,,(t), where co(t) is a random variable uniformly distributed on 0 to 1. The value of F,(r) = 100&F(r), where F(t) is either 1 (indicating that the fill valve is on) or 0

fl Normal Empty \

L O W 9,

sired output, these algorithms train the Fig. 5. Surge tank.

’ Level

‘alve

4 7

(indicating that the fill valve is off). Notice that, with this choice, if the input valve is open, the liquid level will stay the same or rise.

The height of the liquid in the tank is dis- cretized into five regions, which are repre- sented with the symbols y,. i = I , 2, 3. 4, 5 . The case when F(t) = 1 will be repre- sented with the symbol u l ; F(t) = 0 with the symbol uo. The symbolic/numeric converter is simply a device that outputs 1 when it has as an input U , , and 0 when its input is U ” .

The controller that is the same as in [ 111 is given in Table 1.

Next, the numericisymbolic converter must be specified. Let h , = 0 (empty) and h, represent the case when the tank is com- pletely full. Also, let h2 and /i3 represent two particular levels in the tank that distinguish, respectively, a low liquid level from a nor- mal one and a normal level from a high one. Table 2 gives the necessary information to specify the classification problem.

The multilayer perceptron designed using the Harvey method is illustrated in Fig. 6. The arrows indicate amplifiers. The shaded and unshaded circles indicate a summing of the inputs to the circle (arrows pointing to- ward the circle) and that the sum is passed through one of the two nonlineanties shown in Fig. 3. The shaded circles refer to Fig. 3(a) (f,), and the unshaded circles refer to Fig. 3(b) (f2). Using Harvey’s method to specify the multilayer perceptron entails ap- propriately connecting nodes and arcs be- tween h(r) and y[. For instance, we choose the first output y I = f , ( h , - h(t)) so that yl = 1 when h(t) 5 h , ; consequently, yl = 1 (HI) when h(t) = h , = 0. The output y, = 0 (LO) when h(t) > h , = 0. The output yz

so that y2 = 1 (HI) if h , < h(r) < h 2 , oth- erwise y 2 = 0 (LO). Harvey’s method was used in a similar manner for y,. y4, and ys.

= f , ( - 1.5 + fm) - h , ) + fdh2 - W)))

Fig. 6. Numeric/syrnbolic converter f o r the surge tank.

The object of the controller studied in [ 1 I ] was to stabilize the height of the liquid in the surge tank around a particular level. In particular, it was desired that the steady-state behavior of the plant entail only a sequence of y, and y4 alternating. When the plant, the numeric/symbolic converter, the controller, and the symbolic/numeric converter were connected together as in Fig. I and simu- lated, the output of the plant behaved as de- sired. The plant was given two initial con- ditions, completely empty and at level y,. Each time, the controller first opened the fill valve and then closed the fill valve when the level rose to y4. The input valve was opened again when the lower level fell to y3 and closed again when the level rose to y4. The system continued in this fashion, with the controller attempting to keep the level just above y,. Consequently, the multilayer per- ceptron successfully implemented the nu-

Table l Surge Tank Controller

Controller

Controller Input ?‘I V? y3 Y4 ?‘S

Controller Output U1 U1 U1 U0 U0

Table 2 Surge Tank Numeric/Symbolic Converter Specifications

meric/symbolic converter for the surge tank and its symbolic controller.

Biological System

The second example involves a biological system where the multilayer perceptron is used as a fault tree to produce alarm infor- mation. To model a form of biological growth, one of Volterra’s population equa- tions is used. A simple model representing the spreading of a disease in a given popu- lation is given by the following equations [25], wherex,(r) is the density of the infected individuals, x2 ( t ) is the density of the unin- fected individuals, and a > 0, b > 0.

dx,(t)/dt = -ux~(z ) + bx,(t)x>(t) (4)

d ~ ? ( t ) / d t = -b.r,(r)x>(f) ( 5 )

Equations (4) and ( 5 ) are valid only for xl(t) 2 0 and x2(t) 2 0. Equation ( 5 ) intuitively means that the uninfected individuals be- come infected at a rate proportional to x l ( t ) x 2 ( t ) . This term is a measure of the in- teraction between the two groups. The term -ml(t) in Eq. (4) represents the rate at which individuals die from the disease or survive and become forever immune. The term bxl(r)xz(t) in Eq. (4) represents the rate at which previously uninfected individuals be- come infected. The initial conditions xl(0) 2 0 and x2(0) I 0 must also be specified.

The perceptron is to be designed to pro- duce alarms if certain conditions occur in the diseased population; it is to implement a simple fault tree. The perceptron uses .rl(t) and x2( t ) as inputs to produce the following alarms at its outputs:

(i) “Warning: the density of infected in- dividuals is unsafe”; this occurs if .rl(t) > al. where 01, is some positive real number.

(ii) “Caution: the density of the infected individuals is unsafe und the number of infected individuals is greater than the number of uninfected individuals”; this occurs if x , ( r ) > CY, and x , ( t ) 2 x,(t) + a: but .r,(r) < x z ( f ) + a,. where a? and ai are positive real numbers.

(iii) “Critical: the density of the infected individuals is unsafe and the number of

Numeric/ Symbolic Converter

Numeric/Symbolic yI P? Y i ?’, ?‘s Converter Output

Regions Plant Output h(t) = hl h , < h(t) < h2 h2 5 h(t) 5 h3 h3 < h(t) < hJ h(t) = h,

48 I € € € Control Systems Mogorine

infected individuals is much greater than the number of uninfected individuals”; this occurs if xl(t) > C Y , and XI(?) 2 x , (d + a.3.

The three alarms represent certain faults characterized by the decision regions shown in Fig. 7 .

The first fault mode occurs when the val- ues of XI(?) and x2(t) lie to the right of the line x , ( t ) = a, . The second occurs when x , ( t ) and x2( t ) lie to the right of x , ( t ) = 0 1 ,

and x2( t ) = XI(?) - a? [or on x2( t ) = x,(r) - cy2] and to the left ofx2(t) = XI(?) - aj. The third occurs when x , ( t ) and x2( r ) lie to the right of XI(?) = a , and x&) = x, ( r ) - a j [or on x,(r) = x , ( t ) - ai].

Using these decision regions, the Harvey method was used to produce the multilayer perceptron shown in Fig. 8. Each output be- comes high when its corresponding fault oc- curs. The parameters a , , CY,, and a j can be chosen according to the specific problem at hand.

Aircraji

The third example involves the implemen- tation of a fault tree for an aircraft. The mul- tilayer perceptron is used to indicate the fail- ure modes that depend on the aircraft’s inputs and outputs. The aircraft’s input vector U has two components: elevator (deg) 6,, and thrust (deg) 6,. The output vector y has three com- ponents: pitch rate (deg/sec) q, pitch angle (deg) 8, and load factor ( g ) 17:. Four aircraft failure modes are considered here. Each in- put and output is discretized into five re- gions, with four boundaries associated with the real number line. For example, the ele- vator 6,. is discretized as shown in Fig. 9. The G (for green) region denotes an area of safe operation, the Y, and Y, (for yellow) regions denote areas of warning, and the RI and R, (for red) regions denote areas of un- safe operation. Table 3 defines the five re-

x,(?) 4

t Fig. 7. biological system.

Decision regions for the

Fault Mode

Fig. 8. Numeric/symbolic converter for the biological system.

4 I I I 1 I I I I I 6,.

6 R I 6 Y I 0 6, 6 R ?

Fig. 9. Aircraji decision regions.

gions for the elevator 6 , . The four other air- craft variables (6,, q, 8, 7,) are discretized in a similar manner using similar notation.

Using the defined regions for the param- eters, four failure modes for the aircraft are identified as follows:

Load factor is in region R, (7: E R,). Load factor is in region Y, (7: E Yz) . Load factor is in region Y2 and elevator is in region Yl (7, E Y2 and 6, E Y, ) . (Pitch rate is in Y , and pitch angle is in Y , ) or (pitch rate is in Y, and pitch angle is in Yz) [(q E Yl and 8 E Y , ) or (q E Y, and 8 E Y2)] .

For the four failure modes, decision re- gions can be defined and a multilayer per- ceptron can be designed using the Harvey method. The perceptron’s inputs are the air- craft inputs and outputs, and the perceptron’s outputs are the four fault modes. For the first mode, the output is HI if the load factor 7: is in region R2. Notice that 9.- E R, is equiv- alent to 7: 2 q R z or 7: - 2 0. Using the last equation, the multilayer perceptron for the first fault mode is shown at the top of Fig. 10 (output 1). For the second fault mode, the output should be HI if the load factor vz is in region Y2. Let * denote equiv- alence. Notice that the condition qY2 5 7: < qRz is equivalent to

7: 2 O Y 2 * 1): - OY2 2 0

and

‘7: < OR2 e -7: + OR2 > (6)

Using the Eq. (6), the multilayer perceptron for the second fault mode is shown in the middle of Fig. 10 (output 2). For the third fault mode, the output should be HI if the load factor 7: is in region Y, and the elevator 6, is in region Y , . Notice that the first equa- tion for this fault mode is the same as Eq. (6). The second equation (which must be ANDed with the preceding equation) is dRI < 6,, 5 dYI, which is equivalent to

6, > 6 R I 6,. - 6 R I > 0

and

6 , I 6,, * -6, + 6 y , 2 0 ( 7 )

Using Eqs. (6) and (7), the multilayer per- ceptron for the third fault mode is shown in Fig. 10 (output 3).

For the fourth fault mode, the output should be high if either the pitch rate is in region Y , and the pitch angle is in region Y , . or the pitch rate is in region Y? and the pitch angle is in region Y2. The decision regions for the fourth fault mode are shown in Fig. 11. The shaded regions represent the regions that 8 and q must occupy for the fourth fail- ure to occur. To develop the perceptron, no- tice that the fourth failure mode can be char- acterized by

q - q R I > 0 and -q + qYl 2 0

and

8 - 8 ~ 1 > Oand -8 + BY, 2 0

or

q - qYz 2 Oand -q + q R 2 > 0

April 1989 4 9

Table 3 Elevator Decision Regions

Elevator 6, Regions ~~

Elevator Region RI Yl G y2 R2 Elevator Range 6, 5 6R1 6 R I < 6, 5 6 y l 6yl < 6, < 6 y 2 6yz 5 6, < 6R2 6 ~ 2 5 6,

Fig. 10. Numericlsymbolic converter for uircruji fault modes 1-3.

/

Fig. 1 I . fault mode 4.

Decision regions for uircruji

and

0 - OY2 2 0 and -0 + OR* > 0 (8)

Using Eq. (S), the multilayer perceptron for the fourth fault mode is shown in Fig. 12. The aircraft and the multilayer perceptron that implemented the fault tree were simu- lated. The multilayer perceptron appropri- ately identified all the fault modes.

Concluding Remarks and Research Directions

In this paper, we have shown how to use a multilayer perceptron to solve a numeric-

to-symbolic conversion task, which is often encountered in discrete-event and autono- mous systems. The proposed method is used for deterministic classification problems. An important research direction is to determine the applicability of more elaborate pattern recognition techniques to the symbolic-to- numeric conversion problem. Then, for in- stance, the recognition of system behavior could be achieved.

It appears that the idea of using numerid symbolic converters as a starting point in

certain discrete-event or autonomous system designs is novel. The idea is introduced and illustrated via examples. Furthermore, the symbolic-to-numeric conversion task was discussed only briefly. The development of a complete theory of numeric/symbolic con- version is quite important, and it seems that it will impact research in hybrid systems (e.g., combined discrete-event and continu- ous variable systems).

Clearly, another important problem is how to determine the level of quantization for the decision regions (i.e., the number of hyper- planes needed). This problem is analogous to the choice of the quantization levels and sampling period in conventional digital sys- tems; hence, it will impact many aspects of the system design. In general, the solution of this problem will be quite difficult because it depends on the plant, the controller, and the design objectives.

As noted, the technique proposed herein does not utilize the learning capability of the perceptron used. The problems encountered did not dictate the need for learning. In other problems, however, its use may be required; in that case, an algorithm that learns the boundaries of the regions is needed (for ex- ample, where there are curved decision re- gions). Several approaches to solve this learning problem were outlined. These

Fig. 12. Nurneric/symbolic converter for aircruji fault mode 4.

50 I E E € Control Systems Magazine

methods seem quite promising for the nu- meric/symbolic conversion task but require more investigation. Alternatively, the results in [26], [27] may contribute some ideas on the knowledge of region boundaries.

Acknowledgments This work was partially supported by the

Jet Propulsion Laboratory under Contract 957856 and by the U.S. Army Research Of- fice under Contract DAAL 03-88-K-0144. The authors would also like to thank the anonymous reviewers for their comments and suggestions.

References

[ I ] K. M. Passino, M. A. Sartori. and P. J. Antsaklis, “Neural Computing for Infor- mation Extraction in Control Systems.” Proc. 26th Annual Allerton ConJ on Cotn- municution, Control, and Comnputing, Univ. of Illinois at Urbana-Champaign, Sept.

131

171

[81

I91

. - 1988. Special Section on Neural Networks for Systems and Control, IEEE Contr. Syst. Mag., vol. 8, no. 2, Apr. 1988. K . S . Fu, Sequential Methods in Pattern Recognition and Machine Learning, New York: Academic Press, 1968. Z. Kohavi, Switching and Finite Automata Theor?, New York: McGraw-Hill, 1978. R. Forsyth and R. Rada, Machine Learn- ing, New York: Wiley, 1986. R. Wilson, “Is Vision a Pattern Recogni- tion Problem?,” in Puttern Recognition, Lecture Notes in Computer Science 301, J . Kittler, ed., Springer-Verlag, 1988. S . C. Shapiro. ed., Encyclopedia of Artifi- cial fritelligence, Volume 2, New York: Wiley, 1987. B. Chandrasekaran and A. Goel, “From Numbers to Symbols to Knowledge Struc- tures: Artificial Intelligence Perspectives on the Classification Task.” fEEE Trans. Syst., Mun, Cybern., vol. 18, no. 3, pp. 415-424, MayiJune 1988. P . J . Antsaklis. K. M. Passino, and S . J. Wang, ”Autonomous Control Systems: Ar- chitecture and Fundamental Issues,” Proc. Amer. Contr. Conf., Atlanta, GA, pp. 602- 607, June 1988. P. J . Antsaklis, K . M. Passino, and S. J . Wang, “Towards Intelligent Autonomous Control Systems: Architecture and Funda- mental Issues,” to appear in Journal c f f n - telligent and Robotic Sysiems. J . F. Knight and K. M. Passino, “Decid- ability for Temporal Logic in Control The- ory,” Proc. 25th Annual Allerton Conf. on Communication, Control. and Computing, Univ. of Illinois at Urbana-Champaign, vol. I, pp. 335-344, Sept. 1987. P. Peleties and R. DeCarlo, “Modeling of Interacting Continuous Time and Discrete

1141

1261

Event Systems: An Example,” Proc. 26th Allerton Con5 on Coinmunication. Control, and Computing. Univ. of Illinois at Urbana- Champaign, Sept. 1988. D. T. Tank and J. J . Hopfield. “Simple ’Neural’ Optimization Networks: An A/D Converter, Signal Decision Circuit, and a Linear Programming Circuit,” IEEE Trans. Circ. Syst., vol. CAS-33, no. 5 , pp. 533- 541. May 1986. D. L. Gray, Synthesis Procedures for Neural Networks, Master’s Thesis, Dept. of Electrical and Computer Eng., Univ. of Notre Dame, Notre Dame, IN, July 1988. K. J . Astrom et al., “Expert Control,” Au- tomatica, vol. 22. no. 3, pp. 277-286, 1986. Battelle Columbus Div., Guidelines for Hazard Evaluatiori Procedures. American Institute of Chemical Engineers, NY, 1985. R. E. Barlow et al., Reliability and Fault Tree Analysis, SIAM, Philadelphia, PA, 1975. R. L. Harvey, “Multi-Layer Perceptron Theory,” Dept. of Electrical and Computer Eng. Seminar, Univ. of Notre Dame, Notre Dame, IN. Mar. 1988; also in “An Intro- duction to Multi-layer Perceptrons.” Proj. Rept. NN-I MIT Lincoln Lab, Nov. 1988. D. E. Rumelhart, G . E. Hinton, and R. J . Williams, “Learning Internal Representa- tions by Error Propagation,” in Parullel Distributed Processing: Explorations in the Microstructure of Cognition, Vol. I : Foun- dations, D. E. Rumelhart and J . L. Mc- Clelland, eds., Cambridge, MA: MIT Press, 1986. R. P. Lippmann. “An Introduction to Com- puting with Neural Networks,” fEEE ASSP Mag., pp. 4-22, Apr. 1987. W. Y. Huang and R. P. Lippmann, “Neural Net and Traditional Classifiers,” presented at the IEEE Conference on Neural Infor- mation Processing Systems-Natural and Synthetic, Denver, CO, Nov. 1987. S . C. Huang, ”Supervised Learning with a Selective Update Strategy for Artificial Neural Networks.” Master’s Thesis, Dept. of Electrical and Computer Engineering, Univ. of Notre Dame, Notre Dame, IN. Aug. 1988. Y. Shrivatava and S . Dasgupta. “Conver- gence Issues in Perceptron-Based Adaptive Neural Network Models,” Proc. 25th An- nual Allerton Cotg on Communicarion, Control, and Computing, Univ. of Illinois at Urbana-Champaign, vol. 11, pp. 1133- 1141. Sept. 1987. A. Johnson, Process Dynamics Estimation and Control, London: Peregrinus, 1985. R. K. Miller and A. N. Michel, Ordinary Differential Equations, New York: Aca- demic Press, 1982. D. A. Waterman, “Generalization Leam- ing Techniques for Automating the Learn- ing of Heuristics,” Artif. fntellig., vol. I , pp. 121-170, 1970. M. E. Soklic, “Adaptive Model for Deci-

sion Making,” Pattern Recog.. vol. 15, no. 6, pp. 485-498, 1982.

Kevin M. Passino was born in Fort Wayne, In- diana, in 1961. He re- ceived the B.S. degree from Tri-State Univer- sity, Angola, Indiana, in 1983, and the M.S. de- gree from the University of Notre Dame in 1984. Both degrees are in elec- trical engineering. He has worked at Magnavox Electronic Systems in Fort

Wayne and at McDonnell Aircraft. St. Louis, Missoun, on research in flight control. He is cur- rently a Ph.D. candidate in electrical and com- puter engineering at the University of Notre Dame. His research interests include discrete-event sys- tems, temporal logic, neural networks, and auton- omous systems.

Michael A. Sartori was born in St. Louis, Mis- souri, in 196.5. He re- ceived the B.S. degree in 1987 and shall receive the M.S. degree in 1989 in electrical engineering from the University of Notre Dame. He worked for McDonnell Douglas Electronics during the summers of 1986 and 1987. He is currently in

the Ph.D. program in electrical and computer en- gineering at the University of Notre Dame. Hi5 research interests include autonomous systems, neural networks, discrete-event systems, and dig- ital image processing.

Panos J . Antsaklis re- ceived the diploma in me- chanical and electrical en- gineering from the National Technical Uni- versity of Athens. Greece, in 1972. and the M.S. and Ph.D. degrees in electri- cal engineering from Brown University, Provi- dence, Rhode Island, in 1974 and 1977, respec- tively. After holding fac-

ulty positions at Brown University, Rice Univer- sity, and Imperial College, University of London, he joined the University of Notre Dame, where he is currently an Associate Professor in the Depart- ment of Electrical and Computer Engineering. In

April 1989 51

summer 1986, he was a NASA Faculty Fellow at the Jet Propulsion Laboratory, Pasadena, Califor- nia. He was a Senior Visiting Scientist at the Lab- oratory for Information and Decision Systems of terns, and neural networks. Dr. Antsaklis has Control Systems Society. the Massachusetts Institute of Technology during

his sabbatical leave in 1987. His research interests are in multivariable system and control theory, and in discrete-event systems, autonomous sys-

served as Associate Editor of the Transucrions on Auromric Conrrol, and he is currently Chairman of the Technical Committee on Theory of the IEEE

News Call for Volunteers

The IEEE Control Systems Society is con- sidering candidates for Associate Editors for the IEEE Transactions on Automatic Con- trol and the IEEE Control Systems Magazine. We are also looking for people who wish to take an active part in Technical Committees and Working Groups and other Society com- mittees. If you are interested in serving the Control Systems Society in that capacity or some other capacity, please send a cover let- ter along with your resume to the Society President-Elect: Prof. William S. Levine, Department of Electrical Engineering, University of Maryland, College Park, MD 20742; phone: (301) 454-6841.

John E. Ward Memorial John E. Ward, recently retired from the

Massachusetts Institute of Technology (MIT), died unexpectedly on December 11, 1988. Throughout a distinguished career, he made many contributions to automatic control and to the control profession.

John Ward authored numerous reports and papers, contributed to several books and the Encyclopedia Britannica, and was coholder of a number of patents in the areas of con- trol and display. He helped organize the Pro- fessional Group on Automatic Control of the Institute of Radio Engineers in 1954, was its Chairman from 1958 to 1960, and served as President of the American Automatic Con- trol Council from 1963 to 1965. He was a Fellow of the IEEE (1968), was named a Distinguished Member of the IEEE Control Systems Society in 1983, and was a recipient of the IEEE Centennial Medal in 1984.

He was born in Toledo, Ohio, in 1920. He attended MIT, where he received the B.S. and M.S. degrees in electrical engineering in 1943 and 1947, and he has been associated with MIT since that time. At the end of the war, he joined the MIT Servomechanisms Laboratory; he became Laboratory Executive Officer in 1955, Assistant Director in 1959, and served as Deputy Director from 1967 through 1973.

John Ward wrote the history article entitled “Predecessors of the IEEE Control Systems Society,” which appeared in the February 1987 issue of the IEEE Control Systems Magazine, and his biography appears in the October 1987 issue of the Magazine, in honor of his retirement from MIT. We will miss him as a colleague and as a friend.

Sun Receives Award Rajan Suri has received an award of

$50,000 from Ford Motor Company “in recognition of outstanding contributions made to the field of perturbation analysis of discrete-event systems.” Professor Suri developed the first videocassette under the auspices of the Control Systems Society for the IEEE Home Video Tutorials, “Analysis and Modeling of Modern Manufacturing Systems.” He is also one of a team of people from his university who received the 1988 LEAD (Leadership and Excellence in Appli- cation and Development) Award from the Society of Manufacturing Engineers. In July 1988, Suri was promoted to Full Professor of Industrial Engineering at the University of Wisconsin-Madison.

1990 ACC Plans are proceeding for the 1990 American

Control Conference (ACC), which will be held several weeks earlier than usual, May 23-25, 1990, at the Sheraton Harbor Island Hotel in San Diego, California. The General Chairman is Dagfinn Gangsaas from Boeing Advanced Systems and the Program Chair- man is Eliezer Gai from Draper Laboratory. A call for papers will appear in the August 1989 issue of the Magazine. For more infor- mation, contact: Dagfinn Gangsaas, 1990 ACC Chair, Boeing Advanced Systems, MS 33-12, P.O. Box 3707, Seattle, WA 98124-2207, phone: (206) 241-4348.

Software in Control Education The International Federation of Automatic

Control has recently established a new Work- ing Group on the theme “Teachware for Con- trol.” One of the major goals of this group is to make a basic set of programs in control engineering available to every student. A first prototype of such a software package has been prepared with the help of many institu- tions and individuals at the IDA Center of ETH Zurich. It consists of some examples of training programs, basic simulation tools, and the public-domain version of MATLAB (C. Moler), and is available for Macintosh com- puters and IBM compatibles. A similar set consisting of XLISP (D. Betz), PROLOG (ABB), and small expert system shells is also available for introductory teaching of ar- tificial intelligence techniques. For further in- formation, contact: Prof. W. Schaufelberger,

Projekt-Zentrum IDA, ETH-Zentrum, CH-8092 Zurich, Switzerland.

Control Software for Netlib As one of his activities as Chairman of the

IEEE Control Systems Society Technical Committee on Computer-Aided Control Systems Design (CACSD), Doug Birdwell is setting up a sublibrary of the Netlib facility at the Argonne National Laboratory. If you have software that you believe can benefit a reasonably significant segment of the control systems community and would be willing to place the software in the public domain and distribute it through Netlib, Professor Bird- well will recommend the software’s inclusion in Netlib with the understanding that the in- tent is strictly to provide a collection and distribution service for Society members.

Authors of software will benefit by receiv- ing recognition for their software through its use. In addition, the expanded use of the soft- ware is highly likely to highlight limitations of the implementation or the theory on which the software is based, providing the author valuable feedback and an incentive to im- prove the software. The Society membership will benefit in general from the fast and free availability of software relevant to control systems problems.

The Society Technical Committee on CACSD is offering to maintain the Society sublibrary of Netlib as a service; however, there are a few disclaimers. First, we will not serve as a reviewer of any of the software; whatever representations the authors make about the software are included in the library, but no testing is done. Therefore, we make no warranties as to the utility of the software. Second, we will accept only software that is placed in the public domain by its authors and has no restrictions or limitations on its use or consequent distribution. Only the author of the software, o r the editor of a collection of software, may submit the software for in- clusion in Netlib.

If you are interested in contributing soft- ware, please contact: Prof. J. Doug Birdwell, Dept. of ECE, Ferris Hall, University of Ten- nessee, Knoxville, TN 37996-2100. His e-mail address can be any one of the following. (All will end up at the first address, so don’t send multiple messages.) birdwell @cascade.engr .ut k.edu birdwell@utkvx. bitnet jdb@msr .epm.ornl.gov

52 IEEE Control Systems Mogarrne