A neural network approach to freeway network traffic control

ControlEng. Practice,Vol. 3, No. 12, pp. 1719-1726, 1995 Copyright @ 1995 Elsevier Science Ltd Printed in Great Britain. All tights reserved 0967-0661/95 $9.50 + 0.00

Pergamon 0967-0661(95)00184-0

A N E U R A L N E T W O R K A P P R O A C H TO F R E E W A Y N E T W O R K TRAFFIC CONTROL 1 M. Papageorgiou*, A. Messmer**, J. Azema*** and D. Drewanz*** *Dynamic Systems and Simulation Laboratory, Technical University of Crete, Greece **Ingenieurburo Dr A. Messmer ***Lehrst. fi Steuerungs- und Regelungstechnik, Technical University of Munich, Germany

(Received September 1994; infinal form September 1995)

Abstract. The paper investigates the application of a feedforward neural network approach to freeway network control via variable direction recommendations at bifurcation locations. A nonlinear control problem is formulated and solved first by use of computationally expensive nonlinear optimization techniques. A feedforward neural network is then trained by optimally adjusting its weights so as to reproduce the optimal control law for a limited number of traffic scenarios. Generalisation properties of the neural network are investigated and a discussion of advantages and disadvantages compared with alternative control approaches is provided. Key Words. Applied neural control; backpropagation algorithms; conjugate gradient method; feedforward networks; neural networks; optimal control; routing algorithms; traffic control.

1.INTRODUCTION

approaches (Morin, et al., 1991), comprehensive multivariable linear feedback (Messmer and Papageorgiou, 1994) and rigorous nonlinear optimal control approaches (Messmer and Papageorgiou, 1993; Messmer, 1994). This paper suggests a new approach to freeway network control that is based on the concept of feedforward neural networks. The basic motivation for utilisation of these universal approximator structures was the expectation of good training capacity, generalisation and robustness properties, and low computation times when applied as nonlinear regulators. It will become apparent in the analysis and discussion of this paper that only a few of the original expectations were actually verified by the approach attempted here.

Freeway network traffic control via the variable route recommendation signs that are installed at bifurcation locations, is a cost-effective means of ameliorating traffic conditions through optimal utilisation of the existing highway infrastructure (Balz and Zackor, 1991). In particular, in the very frequent cases of non-recurrent congestion (incidents), drivers typically suffer long unexpected delays on their usual or geometrically shortest routes while there are capacity reserves elsewhere in the freeway network. In these cases, variable route recommendation is a valuable means of reducing travel times, congestion, and the corresponding fuel consumption and air pollution. Suggested and applied control strategies for variable route recommendation include intuitive, naive strategies (Joeppen and Reichelt, 1981), simple switching or feedback laws for simple networks with only one origin, one destination and two alternative routes (Berger and Shaw, 1975; Sarachik and Ozgilner, 1982), fixed-structure nonlinear control laws (Cremer and Neumann, 1988), expert-system 1This paper was first presented at the IFAC Transportafic~ Systems Symposium (TS'94)

2. FEEDFORWARD ARTIFICIAL NEURAL NETS Among various types of suggested structures of artificial neural nets (Hopfield nets, Kohonen nets, cellular nets, etc.) for various uses, Feedforward Artificial Neural Nets (FFANNs) are perhaps the most popular. A single artificial neuron consists of a static nonlinear function f(x) that maps a scalar input 1719

M. Papageorgiou et al.

1720

x into a scalar output y according to a smooth 0-1switching curve such as y = f(x) = 1/[l+exp(-x)]

(1)

with the obvious property f(x) = df/dx = f(x)[1-f(x)].

(2)

Assume a multilayer structure of neurons with N layers and Mi, i=l ..... N, neurons per layer (see Fig. 1). Moreover there is one constant entry of- 1 at each (but the last) layer. Neuron No. j of layer i receives as its scalar input a weighted sum of the outputs of the neurons of the preceding layer

Xij

=

Mi-1

o iE --Wi,j + =

1

Wi,j "Yi-l,l

(3)

j=l,...,Mi, i=2 ..... N, where w ]i,i are the corresponding weights. This scalar input is passed through the nonlinear function (1) to produce the corresponding output Yij" The inputs of the neurons of the very first layer are weighted sums of the inputs XI, l=l,...,n, of the FFANN, and are obtained according to (3) with the definitions Y0,1=Xl, M0--n. The outputs YI, l=l,...,m, of the FFANN are just the outputs of the neurons of the N-th layer; hence MN is always equal to m. Note that there are only connections of neurons of successive layers (no connections within a layer, no feedback, and no bypassing of a layer); hence the name of this artificial neural structure. Because a particular FFANN structure is completely characterized by the numbers N and Mi, i=0 ..... N, it may be referred to by the sequence M0/M1/.../MN. Given the stucture described above, an overall nonlinear vector mapping of the FFANN inputs on the FFANN outputs is obtained Y = F(X,W)

(4) l

where Y=[YI...Ym] T, X=[Xl...Xn]T, W = [ w i , j , i=l ..... N;j=I,...,Mi; 1=0..... Mi.1] T. This nonlinear lit

LayQr

nlpUtS~x

2rid

Lo~r

.

3rd Loylr

(Output Lo~r)

structure has been shown to be a universal approximator. More precisely, a two-layer FFANN (i.e. with N=2) with suitable weights may approximate with arbitrary accuracy any continuous nonlinear function if a sufficient number of neurons is provided (Leshno, et al., 1993). On the other hand, empirical studies provide evidence that the overall number of neurons required may be reduced by introducing three or more layers (i.e. N>2). In application problems, the nonlinear function to be approximated is not analytically known. What is available, is a number M of couples or examples, ( x E , y i E ) i = I ..... M. A FFANN with a given structure (i.e. with given N and given Mi, i=l ..... N) may be trained to reproduce with maximum accuracy the outputs yE,i=I,...,M, if fed with the corresponding inputs X E, i=l,...,M. In mathematical terms, training of the FFANN is nothing but a curvefitting procedure that calculates the weights W which minimize the sum of squared output errors for all available examples J(W) = 21 ~ [YiE - F ( x E , w ) ] 2 ---> Min.w (5) i=l This is an unconstrained nonlinear optimization problem that may be efficiently solved by use of available iterative algorithms using e.g. conjugate gradient directions with optimized line search (Papageorgiou, 1991). In this way a batch learning procedure is obtained that computes all FFANN weights centrally and involves all available examples simultaneously in its computations, see (Johansson, et al., 1992) for details. Efficient minimization algorithms based on conjugate gradients can be found in any computer library. Gradients ~J/~W of (5), that are required in the minimization algorithms, can be easily obtained analytically, thanks to the described particular structure of FFANNs. An alternative learning procedure, that is by far more popular in the FFANN community, is the celebrated backpropagation. This is a sequential learning procedure that considers one example at a time and attempts minimization of (5) by use of the stochastic gradient OJJaW where

Ouptusty_

1

Ji(W) = ~[YiE-F(xE,w)] 2, i=l,...,M.

(6)

More precisely, backpropagation attempts to solve (5) by use of the iterations Wk+ 1 = W k - o'[~Ji(Wk)/aW ] Fig. 1. Structure of a FFANN with N=3, Ml=2, M2=3 , M3=l , n=2, m=l.

(7)

where (1 is a gradient step. Again, analytical expressions for the stochastic gradient aJ~/~W are readily obtained due to the specific structure of

Freeway Network Traffic Control FFANNs. Thus, passing each example output error Ji through (7) several times with appropriate steps ct, one eventually receives a solution of (5). The major advantage of backpropagation is that the learning iterations (7) may be readily shown to be decomposable due to the specific structure of FFANNs. In other words, computations within (7) may be performed for each neuron separately, with local information exchange between adjacent neurons. Hence, backpropagation permits parallel computation, e.g. with one processor for each neuron and with limited local information exchange, not only for the feedforward procedure (4) but also for the learning (7). The latter is not possible with the central batch learning procedure. Major disadvantages of backpropagation compared with batch learning are, first, the difficulty of specifying gradient steps a that guarantee convergence, and, second, the slow convergence provided by stochastic gradient directions. In fact, for the present and other studies, backpropagation was found to be a highly tedious and time-consuming procedure without guarantee of success. On the other hand, batch learning provides guaranteed convergence without any user intervention due to the automatically optimized line search. Moreover, computation times are typically far lower due to the application of the efficient conjugate gradient directions, which is not possible in backpropagation. For these reasons, batch learning has been used in the studies described in the paper. It should be noted that both learning procedures may lead to a local minimum of (5) due to the involvement of descent directions. Typical application examples for FFANNs include pattern classification and forecasting problems. In these applications, there is a possibility of on-line learning, by using the examples that become available during the application of FFANN. A crucial question related to FFANN learning is the ability to generalize, i.e. the ability of a trained FFANN to produce an adequate output Y when fed with an input X that was not included in the learned examples. Of course, FFANNs are not the only known universal approximators. Polynomial approximations, Fourier series and further functional approximations have been broadly used in recent decades for successful solutions to practical problems. The attractiveness of FFANNs is perhaps due to their simple structure and the direct possibility of parallel computation. There is no doubt that the efficiency and mystery behind their biological analogy has also contributed to the increasing popularity of FFANNs. On the other hand, in the face of the lack of any theoretical results, the

1721

suitability of the FFANN approach for particular problems can only be tested empirically. More than that, there is little theory providing information on the number of layers and/or neurons required for a particular application. Thus, the corresponding adjustments must be found empirically, which again emphasizes the need for efficient learning procedures.

3. LEARNING OPTIMAL CONTROL DECISIONS In recent years, an increased interest has been observed in the employment of FFANNs as control strategies. Figure 2 depicts a typical control system structure where the control strategy uses real-time measurements to produce suitable inputs so as to satisfy the prescribed control goal. A main problem when applying FFANNs as control strategies is due to the lack of a priori known control inputs to be used as examples for FFANN training. In a major class of classical control problems, the control goal is to drive and keep the process outputs in the vicinity of prescribed set values (Narendra and Parthasarathy, 1990). In another class of optimal control problems (OCP), given an initial condition x(0)=x 0 and disturbance forecasts d(k), k=0,...,K-1, k being the discrete time index, the objective is to find optimal control inputs u(k), k=0 ..... K-l, that minimize a cost criterion K-I

J = E q~[x(k), u(k), d(k)]

(8)

k=0

subject to the following process equations and constraints respectively x(k+l) = fix(k), u(k), d(k)]

(9)

h[x(k), u(k), d(k)] ~ 0

(10)

where xeO~ n is the process state. This optimal control problem may be solved with moderate computational effort by use of suitable iterative algorithms. Feasible direction algorithms based on quasi-Newton or conjugate gradient directions have proved to be particularly efficient for this kind of optimal control problems, see (Papageorgiou, 1991)

goal

I

t disturbances

;

~1

meosurements

Fig. 2. A control system structure.

M. Papageorgiou et al.

1722

for a detailed description; see also (Papageorgiou and Mayr, 1988).

Fig. 3 that includes only one origin and one destination.

From Dynamic Programming theory, it is well known that solution of OCP (8)-(10) may also be provided by a nonlinear control law

The inflow into the network may use one of two possible routes to reach the destination, where the main route L1-L2-L3 is clearly shorter than the alternative route L4-L5. However, due to its geometric characteristics, link L 2 has lower capacity and represents a bottleneck of the network. Therefore, if all vehicles follow the main route and if the inflow is strong enough, a congestion may appear in L 2 which leads to a corresponding delay on the main route, thus making the alternative route competitive. The control problem is to provide route recommendation at the network origin, based on realtime measurements, so as to satisfy a control goal•

u(k) = R[x(k); d(K), K=k,...K-1]

(11)

where the control law R is independent of any initial condition x o. Unfortunately, calculation of R is not feasible for large-scale problems due to the notorious curse of dimensionality. Therefore one may attempt to approximate R by use of a trained FFANN. In this case one has, according to (11), the FFANN input and output X T = [x(k)T; d(K)T,K=k..... k+K] and Y = u(k) respectively. The immediate advantage of a FFANN approach would be the low computational effort for on-line application as compared to a rolling horizon approach (Papageorgiou, 1988), i.e. compared to a repetitive solution of OCP (8)-(10) in real time. Examples for off-line FFANN training may be provided if OCP (8)-(10) is solved numerically for a number of representative scenarios, each scenario being completely characterized by x0 and d(k), k=0,...,K-1. Obviously, each scenario provides up to K examples (X~,Yi E ) for FFANN training, i.e. one example per time step k. It should be emphasized that such a procedure corresponds to off-line design of a nonlinear FFANN-regulator with no obvious possibility of on-line learning. It may also be noted that the degree of success of such an approach depends upon the choice of representative scenarios and the generalization properties of FFANNs. Similar approaches have been proposed e.g. by Parisini and Zoppoli (1991), and Goh (1993)• Of course, the suggested FFANN approach has a strong similarity to the specific optimal control problem (Eisenberg and Sage, 1966; Meghlaoui, et al., 1993) of finding optimal parameter values for a fixed-structure control law. As mentioned earlier, the efficiency of the particular FFANN structure as compared to alternative ones can only be investigated empirically• The next sections investigate the suitability of this approach for the particular freeway network control problem•

For modelling purposes, the freeway stretches are subdivided into segments of some 500m-1000m in length. The traffic state in segment i consists of traJfic density Pi (veh/km) and mean speed v i (km/h). Hence, the process state x includes densities and mean speeds of all freeway segments, which results in a large-scale system even for simple freeway networks like the one of Fig. 3. The control input for the network of Fig. 3 is the scalar variable 1~, 0_