Nof S.Y. Springer Handbook of Automation

Подождите немного. Документ загружается.

Control of Uncertain Systems 11.6 Examples 215

Example 11.1:The nonlinear plant model used in this

example is given by

y = f(y,

y)+g(y)u +d

=16

sin(4π y)

4π y



sin(π





2+sin[3π(y −0.5)]



u +d ,

which, if d = 0, is the same plant model as in [11.27,

34,38], used as a testbed for proposed controllers. It is

easy to check that the above uncertain system dynamics

are in the form of (11.2) with x =[y,



. For the sim-

ulation, the disturbance d is selected to be band-limited

white noise generated using SIMULINK (version 6.6)

with noise power 0.05, sampletime 0.1s, andseed value

23341, which is shown in Fig.11.11.

The reference signal is the same as in [11.38],

which is the output of a low-pass ﬁlter with the

transfer function (1+0.1s)

−3

,drivenbyaunityam-

plitude square-wave input with frequency 0.4Hz and

a time average of 0.5s. The reference signal y

and

its derivatives

and

are shown in Fig. 11.12.

The grid boundaries for y and

y, respectively, are se-

lected to be (−1.5, 1.5) and (−3.5, 3.5), that is,

=(−1.5, −3.5)



and x

=(1.5, 3.5)



. The rest of

the network’s parameters are d

threshold

= (0.2, 0.3),

max

=0.005, T

=0.2s,ω

=25, ω

=−25, ω

=5,

=0.1, and η

=η

=1000. The controller’s param-

eters are k=(1, 2), Q

=0.5I

, d

=5, d

=2, d

=3,

ν = 0.01, and S = 50. The observer’s parameters are

= 0.001, α

=10, and α

=25. The initial conditions

are y(0) =−0.5and

y(0) = 2.0. The controller per-

formance without disturbance is shown in Fig.11.13,

whereas the controller performance in the presence of

disturbance is illustrated in Fig.11.14.

In order to demonstrate the advantages of the self-

organizing RBF network in the proposed controller ar-

chitectures, a different reference signal, y

(t) =sin(2t),

is applied at t =25s. It can be seen from Fig.11.15 that

the self-organizing RCRBF network-based direct adap-

tive robust output feedback controller performs very

well for both reference signals. There is no need to

adjust the network’s or the controller’s parameters of-

ﬂine when the new reference signal is applied. The

self-organizing RBF network determines its structure

dynamically by itself as the reference signal changes.

Example 11.2:In this example, the direct adaptive robust

output feedback controller is tested on a time-varying

system. The plant is the Dufﬁng forced oscillation sys-

Time (s)

Number of hidden neurons

100

Control input

–10

–20

0 50

Tracking error (magnified)

× 10

–3

–5

10 20 30 40 455152535

5010 20 30 40 455152535

0 50

Tracking error

0.5

–0.5

–1

10 20 30 40 455152535

Fig. 11.15 Output feedback controllerperformance with varying ref-

erence signals in Example 11.1

tem [11.28] modeled by

= x

=−0.1x

−x

+12cos(t)+u .

–5 0 5

–2

–4

–6

–8

–10

Fig. 11.16 Phase portrait of the uncontrolled system in Ex-

ample 11.2

Part B 11.6

216 Part B Automation Theory and Scientiﬁc Foundations

Time (s)

Number of hidden neurons

51510 20 25

3051510 20 25

Control input

–10

Tracking error of x

× 10

–3

× 10

–3

–5

Tracking error of x

Fig. 11.18 Output feedback controller performancein Example 11.2

The phase portrait of the uncontrolled system is

shown in Fig.11.16 for x

(0) = x

(0) = 2, t

= 0,

–2 –1.5 –1 –0.5 0 0.5 1 1.5 2 2.5

1.5

0.5

–0.5

–1

–1.5

Fig. 11.17 Phase portrait of the closed-loop system driven

by the output feedback controller in Example 11.2

and t

= 50. The disturbance d is set to be

zero.

The reference signal, y

(t) =sin(t), is used, which

is the unit circle in the phase plane. The grid bound-

aries for y and

y, respectively, are [−2.5, 2.5] and

[−2.5, 2.5]. The design parameters are chosen to be

thesameasinexample11.1except that e

max

= 0.05,

= 15, and ν = 0.001. The phase portrait of the

closed-loop system is shown in Fig.11.17. It follows

from Fig. 11.18 that the controller performs very well

for this time-varying system.

11.7 Summary

Novel direct adaptive robust state and output feedback

controllers have been presented for the output tracking

control of a class of nonlinear systems with unknown

system dynamics. The presented techniques incorpo-

rate a variable-structure RBF network to approximate

the unknown system dynamics. The network structure

varies as the output tracking error trajectory evolves in

order to ensure tracking accuracy and, at the same time,

avoid redundant network structure. The Gaussian RBF

and the raised-cosine RBF are compared in the sim-

ulations. The property of compact support associated

with the raised-cosine RBF results in signiﬁcant reduc-

tion of computations required for the network’s training

and output evaluation [11.61]. This feature becomes es-

pecially important when the center grid becomes ﬁner

and the dimension of the network input becomes higher.

The effectiveness of the presenteddirect adaptive robust

controllers are illustrated with two examples.

In order to evaluate and compare different pro-

posed control strategies for the uncertain system given

in (11.1), it is necessary to use performance measures.

In the following, a list of possible performance in-

dices [11.69]isgiven.

•

Transient performance

= max

≤t≤t



|e(t)|



•

Final tracking accuracy

= max

t∈[t

−2,t

]



|e(t)|



Part B 11.7

Control of Uncertain Systems References 217

•

Average tracking performance

(e) =



|e(τ)|

dτ

•

Average control input

(u) =



|u(τ)|

dτ

•

Degree of control chattering

(Δu)

(u)

where

(Δu) =



j=1



u( jΔT)−u[(j −1)ΔT]



The approach presented in this chapter has been

used as a starting point towards the development of di-

rect adaptive robust controllers for a class of MIMO

uncertain systems in [11.58]. The MIMO uncertain

system considered in [11.58] can be modeled by the

following set of equations

⎧

⎪

⎨

⎪

⎩

)

= f

(x)+

(

j=1

(x)u

)

= f

(x)+

(

j=1

(x)u

)

= f

(x)+

(

j=1

(x)u

(11.65)

where u =



, u

,...,u





is the system input vector,

y =



, y

,...,y





is the system output vector, d =



, d

,...,d





models the bounded disturbance, x =





, x



,...,x







∈R

is the system state vector with



,...,y

−1)





and n =

(

i=1

,and f

(x)

and g

(x) are unknown Lipschitz-continuous functions.

References

11.1 S.H.

Zak: Systems and Control (Oxford Univ. Press,

New York 2003)

11.2 D.W. Clarke: Self-tuning control. In: The Control

Handbook, ed. by W.S. Levine (CRC, Boca Raton

1996)

11.3 A.S.I. Zinober: Deterministic Control of Uncertain

Systems (Peregrinus, London 1990)

11.4 R.A. DeCarlo, S.H.

Zak, G.P. Matthews: Variabble

structure control of nonlinear multivariable sys-

tems: A tutorial, Proc. IEEE 76(3), 212–232 (1988)

11.5 V.I. Utkin: Sliding Modes in Control and Optimiza-

tion (Springer, Berlin 1992)

11.6 C. Edwards, S.K. Spurgeon: Sliding Mode Control:

Theory and Applications (Taylor Francis, London

1998)

11.7 S. Gutman: Uncertain dynamical systems – a Lya-

punov min-max approach, IEEE Trans. Autom.

Control 24(3), 437–443 (1979)

11.8 M.J. Corless, G. Leitmann: Continuous state feed-

back guaranteeing uniform ultimate boundedness

for uncertain dynamic systems, IEEE Trans. Autom.

Control 26(5), 1139–1144 (1981)

11.9 J.B. Pomet, L. Praly: Adaptive nonlinear regulation:

Estimation from the Lyapunov equation, IEEE Trans.

Autom. Control 37(6), 729–740 (1992)

11.10 F.-C. Chen, C.-C. Liu: Adaptively controlling non-

linear continuous-time systems using multilayer

neural networks, IEEE Trans. Autom. Control 39(6),

1306–1310 (1994)

11.11 M. Krstic, I. Kanellakopoulos, P.V. Kokotovic: Non-

linear and Adaptive Control Design (Wiley, New

York 1995)

11.12 K.S. Narendra, A.M. Annaswamy: Stable Adaptive

Systems (Prentice Hall, Englewood Cliffs 1989)

11.13 K.J. Åström, B. Wittenmark: Adaptive Control

(Addison-Wesley, Reading 1989)

11.14 S.S. Sastry, A. Isidori: Adaptive control of lin-

earizable systems, IEEE Trans. Autom. Control 34(11),

1123–1131 (1989)

11.15 I. Kanellakopoulos, P.V. Kokotovic, R. Marino:

An extended direct scheme for robust adap-

tive nonlinear control, Automatica 27(2), 247–255

(1991)

11.16 I. Kanellakopoulos, P.V. Kokotovic, A.S. Morse: Sys-

tematic design of adaptive controllers for feedback

linearizable systems, IEEE Trans. Autom. Control

36(11), 1241–1253 (1991)

11.17 D. Seto, A.M. Annaswamy, J. Baillieul: Adaptive

control of nonlinear systems with a triangular

structure, IEEE Trans. Autom. Control 39(7), 1411–

1428 (1994)

11.18 A. Kojic, A.M. Annaswamy: Adaptive control of

nonlinearly parameterized systems with a trian-

gular structure, Automatica 38(1), 115–123 (2002)

11.19 M. Krstic, P.V. Kokotovic: Adaptive nonlineaer

design with controller-identiﬁer separation and

swapping, IEEE Trans. Autom. Control 40(3), 426–

460 (1995)

Part B 11

218 Part B Automation Theory and Scientiﬁc Foundations

11.20 A.S. Morse, D.Q. Mayne, G.C. Goodwin: Applica-

tions of hysteresis switching in parameter adaptive

control, IEEE Trans. Autom. Control 34(9), 1343–1354

(1992)

11.21 E.B. Kosmatopoulos, P.A. Ioannou: A switching

adaptive controller for feedback linearizable sys-

tems, IEEE Trans. Autom. Control 44(4), 742–750

(1999)

11.22 E.B. Kosmatopoulos, P.A. Ioannou: Robust switch-

ing adaptive control of multi-input nonlinear

systems, IEEE Trans. Autom. Control 47(4), 610–624

(2002)

11.23 J.S. Reed, P.A. Ioannou: Instability analysis and ro-

bust adaptive control of robotic manipulators, IEEE

Trans. Robot. Autom. 5(3), 381–386 (1989)

11.24 M.M. Polycarpou, P.A. Ioannou: A robust adaptive

nonlinear control design, Automatica 32(3), 423–

427 (1996)

11.25 R.A. Freeman, M. Krstic, P.V. Kokotovic: Ro-

bustness of adaptive nonlinear control to

bounded uncertainties, Automatica 34(10), 1227–

1230 (1998)

11.26 H. Xu, P.A. Ioannou: Robust adaptive control for

a class of MIMO nonlinear systems with guaranteed

error bounds, IEEE Trans. Autom. Control 48(5),

728–742 (2003)

11.27 R.M. Sanner, J.J.E. Slotine: Gaussian networks for

direct adaptive control, IEEE Trans. Neural Netw.

3(6), 837–863 (1992)

11.28 L.-X. Wang: Stable adaptive fuzzy control of non-

linear systems, IEEE Trans. Fuzzy Syst. 1(2), 146–155

(1993)

11.29 C.-Y. Su, Y. Stepanenko: Adaptive control of a class

of nonlinear systems with fuzzy logic, IEEE Trans.

Fuzzy Syst. 2(4), 285–294 (1994)

11.30 M.M. Polycarpou: Stable adaptive neutral control

scheme for nonlinear systems, IEEE Trans. Autom.

Control 41(3), 447–451 (1996)

11.31 L.-X. Wang: Stable adaptive fuzzy controllers with

application to inverted pendulum tracking, IEEE

Trans. Syst. Man Cybern. B 26(5), 677–691 (1996)

11.32 J.T. Spooner, K.M. Passino: Stable adaptive con-

trol using fuzzy systems and neural networks, IEEE

Trans. Fuzzy Syst. 4(3), 339–359 (1996)

11.33 C.-H. Wang, H.-L. Liu, T.-C. Lin: Direct adap-

tive fuzzy-neutral control with state observer and

supervisory controller for unknown nonlinear dy-

namical systems, IEEE Trans. Fuzzy Syst. 10(1), 39–49

(2002)

11.34 E. Tzirkel–Hancock, F. Fallside: Stable control of

nonlinear systems using neural networks, Int. J.

Robust Nonlin. Control 2(1), 63–86 (1992)

11.35 A. Yesildirek, F.L. Lewis: Feedback linearization us-

ing neural networks, Automatica 31(11), 1659–1664

(1995)

11.36

B.S. Chen, C.H. Lee, Y.C. Chang: H

∞

tracking design

of uncertain nonlinear SISO systems: Adaptive fuzzy

approach, IEEE Trans. Fuzzy Syst. 4(1), 32–43 (1996)

11.37 S.S. Ge, C.C. Hang, T. Zhang: A direct method for ro-

bust adaptive nonlinear control with guaranteed

transient performance, Syst. Control Lett. 37(5),

275–284 (1999)

11.38 S. Seshagiri, H.K. Khalil: Output feedback control of

nonlinear systems using RBF neural networks, IEEE

Trans. Neural Netw. 11(1), 69–79 (2000)

11.39 M.I. EI–Hawwary, A.L. Elshafei, H.M. Emara,

H.A. Abdel Fattah: Output feedback control of

a class of nonlinear systems using direct adap-

tive fuzzy controller, IEE Proc. Control Theory Appl.

151(5), 615–625 (2004)

11.40 Y. Lee, S.H.

Zak: Uniformly ultimately bounded

fuzzy adaptive tracking controllers for uncertain

systems, IEEE Trans. Fuzzy Syst. 12(6), 797–811 (2004)

11.41 C.-C. Liu, F.-C. Chen: Adaptive control of non-

linear continuous-time systems using neural

networks – general relative degree and MIMO

cases, Int. J. Control 58(2), 317–335 (1993)

11.42 R. Ord

nez, K.M. Passino: Stable multi-input

multi-output adaptive fuzzy/neural control, IEEE

Trans. Fuzzy Syst. 7(3), 345–353 (2002)

11.43 S. Tong, J.T. Tang, T. Wang: Fuzzy adaptive control

of multivariable nonlinear systems, Fuzzy Sets Syst.

111(2), 153–167 (2000)

11.44 Y.-C. Chang: Robust tracking control of nonlinear

MIMO systems via fuzzy approaches, Automatica 36,

1535–1545 (2000)

11.45 Y.-C. Chang: An adaptive H

∞

tracking control

for a class of nonlinear multiple-input-multiple-

output (MIMO) systems, IEEE Trans. Autom. Control

46(9), 1432–1437 (2001)

11.46 S. Tong, H.-X. Li: Fuzzy adaptive sliding-mode con-

trol for MIMO nonlinear systems, IEEE Trans. Fuzzy

Syst. 11(3), 354–360 (2003)

11.47 H.K. Khalil, F. Esfandiari: Semiglobal stabilization

of a class of nonlinear systems using output feed-

back, IEEE Trans. Autom. Control 38(9), 1412–1115

(1993)

11.48 H.K. Khalil: Robust servomechanism output feed-

back controllers for a class of feedback linearizable

systems, Automatica 30(10), 1587–1599 (1994)

11.49 H.K. Khalil: Adaptive output feedback control of

nonlinear systems represented by input–output

models, IEEE Trans. Autom. Control 41(2), 177–188

(1996)

11.50 B. Aloliwi, H.K. Khalil: Robust adaptive output

feedback control of nonlinear systems without

persistence of excitation, Automatica 33(11), 2025–

2032 (1997)

11.51 S. Tong, T. Wang, J.T. Tang: Fuzzy adaptive output

tracking control of nonlinear systems, Fuzzy Sets

Syst. 111(2), 169–182 (2000)

11.52 J.-X. Xu, Y. Tan: Nonlinear adaptive wavelet control

using constructive wavelet networks, IEEE Trans.

Neural Netw. 18(1), 115–127 (2007)

11.53 S. Fabri, V. Kadirkamanathan: Dynamic structure

neural networks for stable adaptive control of

Part B 11

Control of Uncertain Systems References 219

nonlinear systems, IEEE Trans. Neural Netw. 7(5),

1151–1166 (1996)

11.54 G.P. Liu, V. Kadirkamanathan, S.A. Billings: Vari-

able neural networks for adaptive control of

nonlinear systems, IEEE Trans. Syst. Man Cybern.

B 39(1), 34–43 (1999)

11.55 Y. Lee, S. Hui, E. Zivi, S.H.

Zak: Variable neural

adaptive robust controllers for uncertain systems,

Int. J. Adapt. Control Signal Process. 22(8), 721–738

(2008)

11.56 J. Lian, Y. Lee, S.H.

Zak: Variable neural adap-

tive robust control of uncertain systems, IEEE Trans.

Autom. Control 53(11), 2658–2664 (2009)

11.57 J. Lian, Y. Lee, S.D. Sudhoff, S.H.

Zak: Vari-

able structure neural network based direct

adaptive robust control of uncertain systems,

Proc. Am. Control Conf. (Seattle 2008) pp. 3402–

3407

11.58 J. Lian, J. Hu, S.H.

Zak: Adaptive robust control:

A switched system approach, IEEE Trans. Autom.

Control, to appear (2010)

11.59 J.P. Hespanha, A.S. Morse: Stability of switched

systems with average dwell-time, Proc. 38th

Conf. Decis. Control (Phoenix 1999) pp. 2655–

2660

11.60 R.J. Schilling, J.J. Carroll, A.F. Al–Ajlouni: Approx-

imation of nonlinear systems with radial basis

function neural network, IEEE Trans. Neural Netw.

12(1), 1–15 (2001)

11.61 J. Lian, Y. Lee, S.D. Sudhoff, S.H.

Zak: Self-

organizing radial basis function network for

real-time approximation of continuous-time dy-

namical systems, IEEE Trans. Neural Netw. 19(3),

460–474 (2008)

11.62 M. Jankovic: Adaptive output feedback control of

nonlinear feedback linearizable systems, Int. J.

Adapt. Control Signal Process. 10, 1–18 (1996)

11.63 T. Zhang, S.S. Ge, C.C. Hang: Stable adaptive control

for a class of nonlinear systems using a modi-

ﬁed Lyapunov function, IEEE Trans. Autom. Control

45(1), 129–132 (2000)

11.64 T. Zhang, S.S. Ge, C.C. Hang: Design and perfor-

mance analysis of a direct adaptive controller for

nonlinear systems, Automatica 35(11), 1809–1817

(1999)

11.65 B. Yao: Integrated direct/indirect adaptive robust

control of SISO nonlinear systems in semi-strict

feedback form, Proc. Am. Control Conf., Vol. 4 (Den-

ver 2003) pp. 3020–3025

11.66 B. Yao: Indirect adaptive robust control of SISO

nonlinear systems in semi-strict feedback forms,

Proc. 15th IFAC World Congr. (Barcelona 2002) pp. 1–

11.67 F. Esfandiari, H.K. Khalil: Output feedback stabi-

lization of fully linerizable systems, Int. J. Control

56(5), 1007–1037 (1992)

11.68 N.A. Mahmoud, H.K. Khalil: Asymptotic regulation

of minimum phase nonlinear systems using output

feedback, IEEE Trans. Autom. Control 41(10), 1402–

1412 (1996)

11.69 B. Yao: Lecture Notes from Course on Nonlinear

Feedback Controller Design (School of Mechani-

cal Engineering, Purdue University, West Lafayette

2007 )

Part B 11

“This page left intentionally blank.”

221

Cybernetics a

12. Cybernetics and Learning Automata

John Oommen, Sudip Misra

Stochastic learning automata are probabilistic

ﬁnite state machines which have been used to

model how biological systems can learn. The

structure of such a machine can be ﬁxed or can

be changing with time. A learning automaton

can also be implemented using action (choosing)

probability updating rules which may or may not

depend on estimates from the environment being

investigated. This chapter presents an overview

of the ﬁeld of learning automata, perceived as

a completely new paradigm for learning, and

explains how it is related to the area of cybernetics.

12.1 Basics .................................................. 221

12.2 A Learning Automaton .......................... 223

12.3 Environment ........................................ 223

12.4 Classiﬁcation of Learning Automata ....... 224

12.4.1 Deterministic Learning Automata ... 224

12.4.2 Stochastic Learning Automata........ 224

12.5 Estimator Algorithms ............................ 228

12.5.1 Rationale and Motivation.............. 228

12.5.2 Continuous Estimator Algorithms ... 228

12.5.3 Discrete Estimator Algorithms ........ 230

12.5.4 Stochastic Estimator Learning

Algorithm (SELA)........................... 231

12.6 Experiments and Application Examples .. 232

12.7 Emerging Trends and Open Challenges ... 233

12.8 Conclusions.......................................... 234

References .................................................. 234

12.1 Basics

What is a learning automaton?Whatislearning all

about? what are the different types of learning automata

(LA) available? How are LA related to the general ﬁeld

of cybernetics? These are some of the fundamental is-

sues that this chapter attempts to describe, so that we

can understand the potential of the mechanisms, and

their capabilities as primary tools which can be used to

solve a host of very complex problems.

The Webster’s dictionary deﬁnes cybernetics as:

... the science of communicationand control theory

that is concerned especially with the comparative

study of automatic control systems (as the nervous

system, the brain and mechanical–electrical com-

munication systems).

The word cybernetics itself has its etymological ori-

gins in the Greek root kybernan, meaning to steer or

to govern. Typically, as explained in the Encyclopaedia

Britannica:

Cybernetics is associated with models in which

a monitor compares what is happening to a sys-

tem at various sampling times with some standardof

what should be happening, and a controller adjusts

the system’s behaviour accordingly.

Of course, the goal of the exercise is to design the

controller so as to appropriately adjust the system’s

behavior. Modern cybernetics is an interdisciplinary

ﬁeld, which philosophically encompasses an ensemble

of areas including neuroscience, computer science, cog-

nition, control systems, and electrical networks.

The linguistic meaning of automaton is a self-

operating machine or a mechanism that responds to

a sequence of instructions in a certain way, so as to

achieve a certain goal. The automaton either responds

to a predetermined set of rules, or adapts to the en-

vironmental dynamics in which it operates. The latter

types of automata are pertinent to this chapter, and

Part B 12

222 Part B Automation Theory and Scientiﬁc Foundations

are termed as adaptive automata. The term learning

in psychology means the act of acquiring knowledge

and modifying one’s behavior based on the experience

gained. Thus, in our case, the adaptive automaton we

study in this chapter adapts to the responses from the

environment through a series of interactions with it. It

then attempts to learn the best action from a setof possi-

ble actions that are offered toit bythe randomstationary

or nonstationary environment in which it operates. The

automaton thus acts as a decision maker to arrive at the

best action.

Well then, what do learning automata have to do

with cybernetics? The answer to this probably lies in

the results of the Russian pioneer Tsetlin [12.1, 2]. In-

deed, when Tsetlin ﬁrst proposed his theory of learning,

his aim was to use the principles of automata theory

to model how biological systems could learn. Little did

he guess that his seminal results would lead to a com-

pletely new paradigm for learning, and a subﬁeld of

cybernetics.

The operations of the LA can be best described

through the words of the pioneers Narendra and

Thathachar [12.3,p.3]:

... a decision maker operates in the random en-

vironment and updates its strategy for choosing

actions on the basis of the elicited response. The

decision maker, in such a feedback conﬁguration of

decision maker (or automaton) and environment, is

referred to as the learning automaton. The automa-

ton has a ﬁnite set of actions, and corresponding

to each action, the response of the environment can

be either favorable or unfavorable with a certain

probability.

LA, thus,ﬁnd applications in optimization problems

in which an optimal action needs to be determined from

a set of actions. It should be noted that, in this con-

text, learning might be of best help only when there are

high levels of uncertainty in the system in which the

automaton operates. In systems with low levels of un-

certainty, LA-based learning may not be a suitable tool

of choice [12.3].

The ﬁrst studies with LA models date back to the

studies by mathematical psychologists such as Bush and

Mosteller [12.4], and Atkinson et al. [12.5]. In 1961, the

Russian mathematician, Tsetlin [12.1, 2] studied deter-

ministic LA in detail. Varshavskiiand Vorontsova [12.6]

introduced the stochastic variable structure versions of

the LA. Tsetlin’s deterministic automata [12.1, 2]and

Varshavskii and Vorontsova’s stochastic automata [12.6]

were the major initial motivators of further studies

in this area. Following them, several theoretical and

experimental studies have been conducted by several

researchers: Narendra, Thathachar, Lakshmivarahan,

Obaidat, Najim, Poznyak, Baba, Mason, Papadimitriou,

and Oommen, to mention a few. A comprehensive

overview of research in the ﬁeld of LA can be found in

the classic text by Narendra and Thathachar [12.3], and

in the recent special issue of IEEE Transactions

[12.7].

It should be noted that none of the work described

in this chapter is original. Most of the discussions, ter-

minologies, and all the algorithms that are explained in

this chapter are taken from the corresponding existing

pieces of literature. Thus, the notation and terminology

can be considered to be off the shelf, and fairly standard.

With regard to applications, the entire ﬁeld of

LA and stochastic learning, has had a myriad of ap-

plications [12.3, 8–11], which (apart from the many

applications listed in these books) include solutions

for problems in network and communications [12.12–

15], network call admission, trafﬁc control, quality-

of-service routing, [12.16–18], distributed schedul-

ing [12.19], training hidden Markov models [12.20],

neural network adaptation [12.21], intelligent vehicle

control [12.22], and even fairly theoretical problems

such as graph partitioning [12.23].

We conclude this introductory section by empha-

sizing that this brief chapter should not be considered

a comprehensive survey of the ﬁeld of LA. In partic-

ular, we have not addressed the concept of LA which

possess an inﬁnite number of actions [12.24], systems

which deal with teachers and liars [12.25], nor with

any of the myriad issues that arise when we deal with

networks of LA [12.11]. Also, the reader should not ex-

pect a mathematically deep exegesis of the ﬁeld. Due to

space limitations, the results available are merely cited.

Additionally, while the results that are reported in the

acclaimed books are merely alluded to, we give spe-

cial attention to the more recent results – namely those

which pertain to the discretized, pursuit, and estimator

algorithms. Finally, we mention that the bibliography

cited here is by no means comprehensive. It is brief and

is intended to serve as a pointer to the representative

papers in the theory and applications of LA.

Part B 12.1

Cybernetics and Learning Automata 12.3 Environment 223

12.2 A Learning Automaton

In the ﬁeld of automata theory, an automaton can be de-

ﬁned as a quintuple consisting of a set of states, a set

of outputs or actions, an input, a function that maps the

current state and input to the next state, and a function

that maps a current state (and input) into the current

output [12.3,8–11].

Deﬁnition 12.1

A LA is deﬁned by a quintuple A, B, Q, F(·, ·), G(·),

where:

(i) A ={α

,α

,...,α

} is the set of outputs or

actions, and α(t) is the action chosen by the au-

tomaton at any instant t.

(ii) B ={β

,β

,...,β

} is the set of inputs to the au-

tomaton. β(t) is the inputat any instant t. The set B

can be ﬁnite or inﬁnite.In this chapter, we consider

the case when m = 2, i.e., when B ={0, 1}, where

β =0 represents the event that the LA has been re-

warded, and β =1 represents the event that the LA

has been penalized.

(iii) Q ={q

, q

,...,q

} is the set of ﬁnite states,

where q(t) denotes the state of the automaton at

any instant t.

(iv) F(·, ·) : Q × B → Q is a mapping in terms of

the state and input at the instant t, such that,

q(t +1) = F(q(t),β(t)). It is called a transition

function, i. e., a function that determines the state

of the automaton at any subsequent time instant

t +1. This mapping can either be deterministic or

stochastic.

(v) G(·) is a mapping G : Q → A, and is called

the output function. Depending on the state at

a particular instant, this function determines the

output of the automaton at the same instant as

α(t) = G(q(t)). This mapping can, again, be either

deterministic or stochastic. Without loss of gener-

ality, G is deterministic.

If the sets Q, B,andA are all ﬁnite, the automaton is

said be ﬁnite.

12.3 Environment

The environment E typically refers to the medium in

which the automaton functions. The environment pos-

sesses all the external factors that affect the actions of

the automaton. Mathematically, an environment can be

abstracted by a triple A, C, B. A, C,andB are deﬁned

as:

(i) A ={α

,α

,...,α

} is the set of actions.

(ii) B ={β

,β

,...,β

} is the output set of the envi-

ronment. Again, we consider the case when m =2,

i.e., with β = 0 representing a reward,andβ = 1

representing a penalty.

(iii) C ={c

, c

,...,c

} is a set of penalty probabili-

ties, where element c

∈C corresponds to an input

action α

The process of learning is based on a learning

loop involving the two entities: the random environ-

ment (RE), and the LA, as illustrated in Fig.12.1.In

the process of learning, the LA continuously interacts

with the environment to process responses to its vari-

ous actions (i.e., its choices). Finally, through sufﬁcient

interactions, the LA attempts to learn the optimal ac-

tion offered by the RE. The actual process of learning is

represented as a set of interactions between the RE and

the LA.

The RE offers the automaton with a set of possible

actions {α

,α

,...,α

} to choose from. The automa-

ton chooses one of those actions, say α

, which serves

as an input to the RE. Since the RE is aware of the un-

derlying penalty probability distribution of the system,

depending on the penalty probability c

corresponding

to α

,itprompts the LA with a reward (typically de-

noted by the value 0), or a penalty (typically denoted

by the value 1). The reward/penalty information (corre-

sponding to the action) provided to the LA helps it to

choose the subsequent action. By repeating the above

Random

environment

Learning

automaton

β ∈ {0, 1}α ∈ {α

, ..., α

}

∈ {c

, ..., c

}

Fig. 12.1 The automaton–environment feedback loop

Part B 12.3

224 Part B Automation Theory and Scientiﬁc Foundations

process, through a series of environment–automaton in-

teractions, the LA ﬁnally attempts to learn the optimal

action from the environment.

We now provide a few important deﬁnitions used

in the ﬁeld. P(t) is referred to as the action probabil-

ity vector, where, P(t) =[p

(t), p

(t),...,p

(t)]



,in

which each element of the vector

(t) =Pr[α(t) =α

], i = 1,...,r , (12.1)

such that



i=1

(t) =1 ∀t .

Given an action probability vector, P(t) at time t,the

average penalty is

M(t) = E[β(t)|P(t)]=Pr[β(t) =1|P(t)]



i=1

Pr[β(t) =1|α(t) =α

]Pr[α(t) =α

]



i=1

(t) . (12.2)

The average penalty for the pure-chance automaton is

given by



i=1

. (12.3)

As t →∞, if the average penalty M(t) < M

, at least

asymptotically, the automaton is generally considered

to be better than the pure-chance automaton. E[M(t)] is

given by

E[M(t)]=E{E[β(t)|P(t)]} = E[β(t)] .

(12.4)

A LA that performs better than by pure chance is said

to be expedient.

Deﬁnition 12.2

A LA is considered expedient if

lim

t→∞

E[M(t)]< M

Deﬁnition 12.3

A LA is said to be absolutely expedient if

E[M(t +1)|P(t)] < M(t), implying that E[M(t +1)] <

E[M(t)].

Deﬁnition 12.4

A LA is considered optimal if lim

t→∞

E[M(t)]=c

where c

=min

Deﬁnition 12.5

A LA is considered -optimal if

lim

n→∞

E[M(t)]< c

+ , (12.5)

where >0, and can be arbitrarily small, by a suitable

choice of some parameter of the LA.

It should be noted that no optimal LA exist.

Marginally suboptimal performance, also termed above

-optimal performance, is what LA researchers attempt

to attain.

12.4 Classiﬁcation of Learning Automata

12.4.1 Deterministic Learning Automata

An automaton is termed a deterministic automaton,if

both the transition function F(·, ·) and the output func-

tion G(·) deﬁnedin Sect.12.2 are deterministic.Thus, in

a deterministic automaton, the subsequent state and ac-

tion can be uniquely speciﬁed, provided that the present

state and input are given.

12.4.2 Stochastic Learning Automata

If, however, either the transition function F(·, ·)orthe

output function G(·) are stochastic, the automaton is

termed a stochastic automaton. In such an automaton,

if the current state and input are speciﬁed, the subse-

quent states and actions cannot be speciﬁed uniquely.

In such a case, F(·, ·) only provides the probabilities

of reaching the various states from a given state. Let

, F

,...,F

denote the conditional probability

matrices, where each of these conditional matrices F

(for β ∈ B)isas×s matrix, whose arbitrary element

=Pr[q(t +1) =q

|q(t) =q

,β(t) =β] ,

i, j =1, 2,...,s .

(12.6)

Part B 12.4