AH APPUBATEOH 0F SYSTEM THEORY TO THE OPTIMAL CONWOL 0F VEHIC‘ULAR TRAFFiC NEYWORKS Thesis far the Degree 0f Ph. 0.. HIGH 1W3 STATE. UMVERSS‘EY Jff’fflfi‘t' L GOOQNUFF 2967 ~ mutttiminmm» 31293093836268 : Michigat- State " Universiy stifle-Hiaaitow MMERSITY ‘ \ , This is to certify that the thesis entitled , ‘ An Application of System Theory I to the Optimal Control of Vehicular Traffic Networks _ presented by p I Jeffrey L. Goodnuff has been accepted towards fulfillment - .3 .A-.-_...,b of the requirements for ph. D. degree in E. E 3 z / - ' g ; Major professor ; 1lete May 12, 1967 0-169 d i I i .. w-..— __ .-.s4 ABSTRACT AN APPLICATION OF SYSTEM THEORY TO THE OPTIMAL CONTROL OF VEHICULAR TRAFFIC NETWORKS by Jeffrey L. Goodnuff Vehicular traffic demands are increasing so rapidly that merely increasing the physical size of freeway and street systems is not, in itself, a solution. Present and future traffic networks must be operated at or near their highest efficiency levels. This can only be accomplished through control. Rec0gnizing the inevitable need for control, this thesis investigates the problem of applying physical system theory to the analysis and control of vehicular traffic systems. Two complementary variable functions of time, traffic density, x(t), and traffic flow rate, y(t), are defined and used to characterize the dynamics of several traffic system components in the form of mathematical state models. These state models are combined, using the logically consistent procedures of system theory, into state models of traffic systems. As an example of the application of these state models to control, the special case of vehicular traffic control in a high density mode is considered. A state model of such a system is developed and a near time optimal control strategy is derived for a surface street grid of arbitrary size. AN APPLICATION OF SYSTEM THEORY TO THE OPTIMAL CONTROL OF VEHICULAR TRAFFIC NETWORKS BY ,1") Jeffre Lil Goodnuff Y A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 1967 ACKNOWLEDGEMENTS The author wishes to express his thanks to his major professor, Dr. H. E. Koenig, whose encouragement and con- structive suggestions were invaluable. Thanks are also due to Dr. J B. Kreer, whose many thought provoking discussions with the author proved to be most helpful. The author also wishes to thank the Division of Engi- neering Research and the Crouse Hinds Company, under whose sponsorship this research was done. ii TABLE OF CONTENTS Page LISTOFFIGURES....................... iv Chapter I INTRODUCTION . . . . . . . . . . . . . . . . . . . . 1 II A CHARACTERIZATION OF VEHICULAR TRAFFIC . 4 2.1 Fundamental Variables and Parameters . . . . . 6 2. 2 A Single Origin-Destination. . . . . . . . . . . . 10 2.3 Multiple Destinations . . . . . . . . . . . . . . . 12 2.4 The Eight-Way Intersection. . . . . . . . . . . . 14 III OPTIMAL CONTROL IN HIGH DENSITY MODES . . . 21 3.1 The System Model. . . . . . . . . . . . . . . . . 23 3.2 The Control Problem . . . . . . . . . . . . . . . 3O 3. 3 Solution of the Optimal Control Problem . . . . . 33 3.4 Cascaded Signals . . . . . . . . . . . . . . . . . 35 3. 5 The Single Intersection . . . . . . . ..... . . 39 3. 6 Arterials of Arbitrary Length . . . . . . . . . . 41 3.7 Rectangular Grids. . . . . . . . . . . . . . . . . 43 1V OBSERVATIONS AND CONCLUSIONS . . . . . . . . . 49 4.1 Summary . . . . . . . . . . . . . . . . . . . . . 49 4.2 Some Observations ...... . . . . . . . . . . 50 4. 3 Implementation Features . . . . . . . . . . . . . 53 4.4 Future Research . . . . . . . ..... . . . . . 54 REFERENCES.... ..... ............57 LIST OF FIGURES .1 Typical traffic detector output . 2 Uniform section of street ..... . . . ..... . 3 Steady state flow-density plot. . . .4 Experimental data from the John C. Lodge freeway . .5 System graph for two cascaded sections . . . . . . . .6 Single origin, dual destination system . . . . 7 Single origin, dual destination system graph. .8 Double exit ramp . .............. .1 Flow-density characteristics ............ . .2 m by n rectangular grid. . . . . . . ..... . 3 Series connection of two streets ....... .4a Phase plane for F2 > af‘l ........... .4b Phaseplaneforf‘zzafl.......... ..... .4c Phase plane for F1 2 y11 ..... .5 Single intersection. . . . ..... .6 Single intersection optimal trajectories . . . . . . . . 7 Single arterial. . . ..... . ....... . 8 Schematic diagram of arbitrary grid . . iv INTR ODUC TION Present day vehicular traffic demands are increasing so rapidly that merely increasing the size of physical street and free- way systems is not, in itself, sufficient. If new and existing traffic networks are to operate at their highest efficiency they must be con- trolled in the same technical sense that the operations of aircraft, powerplants, and other physical systems are controlled. It is this inevitable need for control which motivates the research des— cribed in this dissertation. Before any system can be controlled its dynamics must be characterized by a mathematically tractable state model. Such a model must do more than extrapolate the future from the past. It must go beyond simulation. It must reflect both the mathematical characteristics of each subsystem, or component part, and the interconnection pattern of these subassemblies. Many of the basic concepts used to characterize physical phenomena can be applied to develop models of the dynamics of vehicular traffic networks. However, quantitative aspects of systems, such as these, in which man is involved are not easily represented. There are a number of reasons for this difficulty. 0 Systems involving man as a component part are not as predictable as non-human systems. Certainly no general model characterizing the dynamics of man as a system component exist. 0 Systems with men as integral parts are, in general, not easily subjected to experiment. For moral, legal, and political reasons it is sometimes very difficult to perform experiments on these man-machine systems. 0 There are no universally agreed upon methods of quantitatively representing non-physical phenomena. For this reason communication between investigators in similar but distinct fields is often difficult and some... times impossible. Investigators attempting to model non- physical systems are. in a sense, in the same position as the early physical scientistsutheir first task is to define a set of standard measurements which will char- acterize the phenomena of interest. Even in the face of these difficulties considerable progress, at least in the form of qualitative or semiquantitative descriptions and hypothetical models, has been made [GR 1, GR 2, HE 1]. This thesis does not claim to have found an easy answer to the problems of quantitatively describing and controlling non-physical -3- systems. It does, however, offer a logically consistent formulation procedure which, when properly applied to certain types of vehicular traffic systems, results in state models useful in describing, simu- lating, and controlling these systems. In order that this thesis may serve as a basis for control, it examines the vehicular traffic phenomena and defines two quantitative measurements, traffic density and traffic flow rate, which are used to characterize vehicular traffic systems. These complementary measurements are used to model some of the basic components of traffic systems. The resulting component models are combined, using the logically consistent procedures of system theory, into a state model of the system. As an example of the application of mathematical models of this form to the control of traffic systems, the special case of optimal control of vehicular traffic in a high density mode is con- sidered in Chapter III. A state model of such a system is developed and a control scheme which results in a minimum number of control intervals is derived. II A CHARACTERIZATION OF VEHICULAR TRAFFIC A complete analysis of any metropolitan traffic system in- volves at least three major aspects. First, there must be an identification or analysis of traffic flow demands, as a function of time, between identified geographic regions as generated by the business, industrial, and other socio- logical activity of the populace. These flow demands depend on such parameters as the general economic level of a region, the distribution or mix of business and personal property in the region, and many other socio-economic factors. Furthermore, the flow demands are not independent of the traffic system, but are, at least in part, generated by it. This problem of flow demand identi- fication and prediction is generally classified under the heading of origin-destination studies, and receives considerable attention in the literature [CA 1]. The second major aspect of metropolitan traffic analysis is that of determining the distribution of known inter-regional flow demands over alternate paths and modes of transportation. This so called "mode split" problem is not only concerned with predicting the distribution of flow demand over the various transportation modes, but also with predicting the distribution of vehicular flow demand over alternate routes. The third aspect of vehicular traffic analysis is that of deter-. mining the dynamics of flow streams (i.e. , the stream flow rates, densities, and delays) from the known inter-regional demands. While all three aspects of the problem are inter related, the complexity of the problem and the present state of the art in traffic network analysis almost precludes the inclusion of this interdependence in a mathematical analysis or simulation of traffic systems. This chapter, therefore somewhat arbitrarily, assumes that the traffic flow rates over identified inter-regional paths of a traffic network are known as a function of time. It considers the problem of developing a state model characterizing the flow dynamics as an explicit function of these flows, the network structure, and inter- section controls. The following postulates must be satisfied before the methods of physical systems analysis may be applied [KO 1]. Therefore vehicular traffic systems must also satisfy these postulates. (l) The system must be an interconnection of identifiable sub- systems, or components. If this identification is not physi- cally possible, it must be at least conceptually possible. (Z) (3) (4) (5) (6) 2. These subsystems, or components, must be discrete in the sense that they must have a finite number of interfaces with other components (called terminals), and measurements taken at these terminals must completely characterize the component. All components must be such that they may be characterized by a pair of complementary variables, x satisfying postulate (5), and y satisfying postulate (6) following. All components with N terminals must be such that they may be characterized with N-l measurements made at the N terminals. The variable x must be such that the algebraic sum of all x measurements around a circuit vanish. The variable y must be such that the algebraic sum of all y measurements corresponding to a cutset vanish. Fundamental Variables and Parameters It is convenient to define a pair of complementary variable functions of time, x(t) representing traffic density and y(t) repre- senting the flow rate of the traffic system, which can be used to characterize the traffic phenomena. The units of these variables are chosen as: x - total vehicle length/total lane length, y - number of vehicles/minute. -7- In order to operationally define these variables, consider the output of a standard loop or overhead sonic type detector, (Mt), shown in Figure 2.1. <1>(t) 2.1 Typical traffic detector output Let (Ht) 2 1 when a vehicle is on the detector and <1)(t) : 0 otherwise. Define the integer valued functional J(¢(t), t t2) as l, J((t), t1, t2) = total number of O to 1 changes of <1>(t) for t1_<_ t 5 t2 The flow rate, y, is obtained as y _ we), t1, t2) ' - 2.1 (t2 t1) ( > while the traffic density, x, is 1 t2 x = S ¢(t)dt (2.2) t -t 2 l t From (2. 2) it is evident that x is the ratio of two lengths of time and assumes values between zero and one. The above definition of traffic density is essentially the same as lane occupancy. If the traffic mix (i.e. , average vehicle length) is known, other characteristics such as average stream speed may be computed from these flow and density measurements. Consider now a uniform section of street as shown in Figure 2. 2., and let Ya and yb represent the flow rates at the points A and B respectively. Furthermore, let :1:l represent the average i> — —- _b——1__ 2.2 Uniform section of street density in that street. In the special case when all densities and = constant, and x = constant) 1 flow rates are constant (1. e., ya = yb it is well established that a plot of flow rate vs density is of the form shown in Figure 2. 3 [GR 1] . It must be emphasized that the Yb X 1"— ‘ ‘ ' 1 l ' T'— 1 2. 3 Steady state. flow density plot -9- relation ~shown in Figure 2. 3 is valid Billy under steady-state condi- tions. Actual measurements of density-flow rate relationships have, in the past, been taken with very little attention given to the steady state requirement. Such measurements typically result in a cluster- ing of points similar to that shown in Figure 2.4 [JL 1]. Y 2.4 Experimental data from the John C. Lodge freeway In order to characterize the dynamics of a traffic stream it is clearly necessary to obtain density-flow rate relationships under known dynamic conditions. Until this is done there can be very little correlation between the theoretical analysis of traffic systems and their actual behavior. For the purpose of applying system theory to traffic analysis, assume that the flow density relationships fpr the short section of street' of Figure 2. 2 may be approximated by the terminal equations and graph (2.. 3). It is important to note that the density, x2(t), is -10.. a 2 b _ Yzit) — f(x1.xz) 1 dxlit) (2.3) yl(t) = CIT 8 a differential density and not an absolute density. The densities x1(t) and xz(t) are defined as x2(t) xa(t) - xb(t) x1e) xam , (2.4) where xa(t) and xb(t) are the absolute densities at points a and b. The exact form of the function f(x ,xz) can not be determined 1 until traffic stream data taken under known dynamic conditions is available. Even though this information must be known before there can be any correlation between the theoretical analysis of traffic systems and their actual behavior, the exact form of f(x1, x2) need not be known to demonstrate the application of system theory to vehicular traffic systems. To this end the next section identifies the model of one of the basic subassemblies. in vehicular traffic systems. 2. 2 A Single Origin-Destination Consider an origin and destination connected by a single expressway link with no intersections. Assuming the input flow rate, yo(t), is known, and considering the expressway as a cascaded sys- tem of two uniform sections, the system graph is as shown in Figure 2. 5. -11- 2. 5 System graph for two cascaded sections The terminal equations corresponding to the system graph are yo(t) - known dxlit) yi(t) : ciT i = 1,3 (2.5) . t ,= f.(x, ,x.) ' = 2,4 YJ( ) J J_1 J J x5(t) - known The vertices a and b correspond to the ends of the expressway while the vertex c represents the center. If the expressway is uniform throughout its length, the two sections are identical. In addition to yo, the terminal density, x , must be specified. 5 From the component equations (2. 5) and the circuit and cut- set equations of the system graph, the system model is easily derived as [KO 1, WI 1] x(t) NC 0 ’ y(t)-f(x,x-x) £1: 1 z 1 o 213 1 (2.6) x3(t) O ' l/c3 f2(x1,x3-x1) - f4(x3,x5-x3) -12- In the event the expressway is uniform and f2 and f4 are given as gum) = f4(!3.7) = (1 - k7) 3(3) (2. 7) where the function g is similar in form to Figure 2. 3, the state model (2. 6) becomes .53. x1(t) _ Hal 0 yo(t) [1 - k(x3~x1)] g(x1) d . _ .. t x3 0 fg(t) 0 e t (2. 17) = 0 t _<_ O and (2.16) becomes 00 P(turning left) = 5 0(1 - e‘Mt‘T))e'°tdt -oo ~UT k e : —— 2. 18 )\ + 0' ( ) -l where 0‘ is the average gap length between vehicles. In a similar manner it is easily shown that the probability of completing a left turn across N lanes of traffic is given by N )\ exp{- 2) Giff} P(turning left) = NH (2.19) x + E 0 . i 121 The four grade corner intersection differs from the clover- leaf described above in that the left-turn traffic experiences "interference" passing through the on-coming traffic in the adjacent lane. The total out of the left turn exit of an intersection is, there- fore, decreased by an amount that depends on the flow-rate in the adjacent on-coming traffic stream. When the model of the grade separation intersection given in (2.14) is altered to include this interference function, the model takes the form I Y' y f (Y :Y ) Z = EA? 2 - z 1 3 (2.20a) l y3 y3 f3(Y2’Y4) l Y4 Y4 f4(y3,y1) _ _l —- _I L. _ ._ .— and r- -1 r- ! y-' '1 “'h "l x1 x1 1(Y3’x4) x X' h (Y ,X') 2 z ‘A' Z + 3 4 1 (2.20b) l l I l The functions f1 and hi are defined as f1 : b1,1+1(1 ' 71+3) y1+1 and (2. 21) 1 = 1,2,3,4r h. = a. li(1-7'. )x 1 1- , 1+2 1+3 where bij and aij represent the entries of -At and A, respectively, and all subscripts are modulo 4. The factor Tj is a function of the flow yj, is called the "highway transparency'' and is a monotonic decreasing function of yj having the following properties 0 = 1 (1) Tj( ) (2) O E 'rj(yj) _<_1 for all yj (2. 22) It is to be noted that when the cross-traffic flow is zero (i.e. , 'r = l) or when there is no left-turn flow, (2. 20) reduces to the interference-free case of the Cloverleaf given in (2.14). This -20.. is to be expected since there can be no "interference" in the case when there is no cross traffic or in the case where there is no traffic with which to interfere. The transparency function, 7', may be taken as 'T = 1 - P(turning left) (2. 33) or, from (2.19) N N M1 +exp[-— Z O'iT]) + 2 0’1 i=1 i=1 7' _ N - I (2.34 x + Z a. . 1 1:1 This chapter does not claim that the component and state models introduced above are in a complete or final form. As pointed out in section 2. 1, considerable experimental research must be completed before a high degree of correlation between theoretical and actual results can be obtained. This chapter does, however, point the direction for such research and illustrates the potentials of a system theoretic approach. Using the fundamental variables and methods defined in this chapter, the particular problem of control of vehicular traffic in a high density mode is discussed in Chapter III. III OPTIMAL CONTROL IN HIGH DENSITY MODES It is the objective of this chapter to characterize the vehi- cular traffic phenomenon with a mathematically tractable model to which some of the procedures of optimal control theory may be applied. Consider the general character of vehicular traffic as characterized by traffic density, x(t), and traffic flow rate, y(t). When one plots traffic flow, y(t), vs traffic density, x(t), curves of the general form shown in Figure 3.1 result [GR 1]. y(t) sat ——————————— x(t) sat 3.1 Flow-density characteristics -21- _22- It should be noted that the curve plotted in Figure 3.1 is a plot of flow rate and absolute density, not differential density as previously defined. Curves of this form are obtained under free flow steady- state conditions, i. e., the time derivative of density is zero, and there is no interruption of the traffic stream. Again referring to Figure 3.1 observe that as the absolute density increases, the steady-state flow rate also increases. This relationship is nearly linear until y(t) reaches about 80% of the maximum possible flow rate, ysat' At this point the flow rate, y(t), begins to level off until, at y(t) = y , the slope, EX , is zero. At this point any sat dx further increase in traffic density clearly decreases the flow rate. Furthermore, it is well known that without external control, re- covery from a staurated condition takes a very long time [MA 1]. It is therefore 10gical to try, by some means of control, to keep the traffic density below this saturation level, xsat' Many attempts have been made in the past to implement control schemes with just this objective in mind [GR 2, MA 2]. In general these control schemes have improved existing traffic flow conditions during peak travel hours on the order of 20%. They are very attractive for particular bottlenecks which cover a small area, such as a tunnel or short section of limited access eXpress - way, as they are easy to implement, realize substantial improve- ments in a short time, and are very inexpensive when compared to the only other alternative--addition of more road surface. -23- These volume-control techniques, however, have been limited to a few distinct locations, where conditions are unusually bad. No attempt has been made to implement a general control scheme which could be applied to an arbitrary area. With this thought in mind let the vehicular traffic flow be divided into three distinct modes; (1) high density mode, (2) low density mode, and (3) transition or medium density mode. The particular mode of a given street is determined by monitoring queue lengths. When the length of the queue is such that each vehicle must wait for one or more complete traffic signal cycles before passing the intersection (i. e. , the queue length does not go to zero during any given cycle), that section of street is assumed to be operating in the high density mode. When traffic is free flowing (i. e. , each vehicle must wait no longer than one traffic signal cycle), the system will be controlled under the low density mode. In any other situation the system is said to be in the medium density or transition mode. Inasmuch as the greatest cost-benefit returns are potentially realizable at high densities of operation, this thesis places primary emphasis on the high density mode of operation. 3.1 The System Model Consider the problem of controlling an m by n grid of inter- secting surface streets under these conditions. Such a grid is shown schematically in Figure 3. 2. The area under control is -Z4- le Y23 y14 r‘tt r ‘1 —-h——-——_ I I I I I I I I I _I _1 l I I I I I I I l I l I I I I I L. y22 y13 V24 3. 2 m by n rectangular grid shown within the dotted boundary, all streets are assumed to be one way, and the small circled numbers on the diagram serve to identify each "stub. ” It is further assumed that the input flow rates, y1i(t)' are known as a function of time. Since the streets are short (i. e. , the street transit time is small with respect to the rates of change of the traffic flow rate and density), and the high density conditions exist (i. e. , queues are always present), the transit time for each street stub may be neglected and a control scheme based only on queue lengths. Furthermore, since the high density traffic control mode is designed to operate with streets in a saturated condition, it is extremely useful in recover- ing from catastrophic disturbances. -25- For the m by n rectangular grid of Figure 3. 2, the flow rates at the ith grid input and output are designated as yli and 3'21 respectively. The density (or in this case, queue length) in the ith street will be denoted as xi. Let the components, Xi' of the state vector, 3?, represent the densities at the respective streets in the grid. The state of the grid, as a function of time, and the inputs to the grid can be expressed as a vector difference equation of the form: R'Ik) = F[3<'(k-1), Y(k-l)] (3.1) where the vector—DER) represents the state vector at the kth con- trol interval, which is of duration T(k). If the grid is to be controlled, rather than just modeled and simulated, a set of control variables must be identified. Suppose ui(k) signifies the number of vehicles to be removed from street section i during the kth control interval. Then the detailed form of (3.1) is: -26- 3; Ex. Eves Em: EN... 3:. c: C: 2:: :2 NH :t: x :t: - r... VQHM 3.5:? :2? Steps Stu-Vex :3me Sit-Vex :3me :3me - :t: x I' -Z7- where the output flows are given by: k l1 _O O O 0 0 O '1’? k 7 + Y21( ) 0 b4 0 a7 0 0 ul( ) k+l b O O y22( ) 0 0 o 0 0 0 0 0 9 2‘10 112(k) k+l = 0 0 0 O O k y23( ) O O 0 O 0 b6 a11 u3( ) k+l 0 O O O O O k y24( ) O O 0 0 b5 3.12 u4( ) y25(k+l) O O 0 0 0 0 O O O O 0 0 _I __ _ . k u12( ) L. ._J (3. 2b) and the constants, bi’ are the percent of vehicles in street i which turn. ai 2 l- bi (3.2c) When the grid of Figure 3. 2 is extended to an arbitrary m x n rectangular grid the state model is of order N = 2(m + n + mn + 1) and of the form: Sim-+1) =x(k)+ U ?(1.:I+ -U o 371(k) (3.3) 0 A B 372(k) Indeed, for any complete m by n rectangular lattice there clearly are m(n+l) +- n(m+l) = m + n + Zmn edges. For a grid of the form shown in Figure 3. 2 there exist, in addition to the closed lattice, m+1+n+1edges. Thussz+n+2mn+m+1+n+l= 2(m + n + mn + 1). The N dimensional state model will always be of the form of (3. 3) if the stub numbering system is chosen so that -28- the m + n + 2 external stubs are numbered first. Consider now the general N dimensional discrete state model 3?(k+1) = ciak) +D-;(k), k:0,1,2,... (3.4) Under the assumption that the matrix D is N by N, recursive solution of (3.4) gives 35“.) = ck§(0)+[Hl, D] F1 . (3.5) F2 where the submatrix, H1, and the subvectors, 1:1, and F2 are k_1 —> ”—u "‘ —> -—> Hl=[c D....,D]; r1: y(O) ; F2=y(k) (3.6) 31(1) L-flk-l) _J . -1 . -’ . Assuming D ex15ts we can solve (3. 5) for F2 and obtain E: = D'1[3’<(k) .. 635(0) .. Hl'fl] . (3.7) Theorem 3.1: A discrete state model in the form shown in (3. 3) is controllable if and only if B-1 exists. Proof: From the definition of controllability [GO 1] it is clear that any discrete state model of the form (3.4) is controllable if and only if it can be solved for T2. Equation (3. 7) implies an explicit solution exists for $1.2 if and only if D.1 exists. Observe that the form of D in (3. 3) is: -29- Using the fact that the determinant of a product is equal to the product of the determinant yields |D|= -UO UO-UO -UO (3. 8) The strategy used as a basis of control, is to select the control vectors, ?1(k) and 372(k), in (3. 3) in such a manner that the state is driven to the origin in minimum time subject to cer- tain constraints imposed on the variables in the model by physical considerations. These constraints are considered next. First of all, since each section of street is of finite length, the state variables must satisfy the contraint Oixi(k)£Xiforallk, andi, i=1, 2, ...,N (3.9) where the constants Xi represent the maximum storage capacity of the ith section of street. Secondly, since more vehicles cannot be removed from a street than exist in that section the controls must be constrained such that O-<-ui(k)—<-Xi(k) for allkand i, i: l, 2, ..., N (3.10) Finally, each intersection can transmit only a finite number of vehicles in a given time, therefore -30- Mi_<_ui(k):1—‘i for allkand i, i: 1, 2, ..., N (3.11) The constants Mi and Fi’ are the minimum and maximum number of vehicles which are permitted to cross through the ith intersection in time T(k). Psychological factors will dictate the values of M and P for each intersection. These values, together with such traffic stream parameters as vehicular acceleration time, will in turn determine the time, T(k), associated with the kth control interval. It is very important to note that each control interval is not necessarily of the same duration as the other intervals. As is shown later, each control interval is complete when Pi vehicles have been counted through the ith intersection, i = l, 2, . . ., N. 3. 2. The Control Problem Stated as an Optimal control problem, the high density vehicular traffic control problem becomes: For the system in (3. 3) find the control, u(k), from the admis sable set 9, s2 = {ui(k))05ui(k)5x1(k): forizl, N; k=1,2,...,£}fl H H 2 w II .—a N h L-J {u,(k)l M. < u,(k) < F.2 forj J J'— J _ J such that: —. (l) X(£) = Ofor minimum I, and (Z) O -—> —o- -+ N (4) the matrix U + a F[X, u]/ BX is non-singular on E x9, (5) the set {F[X, u] l u 69} is convex for all X 6E . =:< In general condition (5) may be considerably relaxed, but in this context it is not restrictive [HO 1]. -32- It is also necessary to define an initial set {Xlai(X) : 0, 121,2, .5, s<_N}, a terminal set {Meg—x.) = 0, 1: 1,2, ..,t, tiN}, --> And an object function fO(X). The scalar functions (1,165), Bid?) must be twice continuously differentiable. —-> The sequences 3(1), 3(2), . . . , 2(2) and 2(1), 23(2), . . . , KM) are said to be optimal controls and trajectories respectively if they satisfy the conditions: (1) ai(‘}£(l)) = O for i = 1,2,...,s, -. (2) X(k+i) .. 33k.) = P(Xuc), TI(k)) for all k = i,2,...,i, (3) Qk)€§2f0ra11k:1,2,...,l, (4) (5153(2)) = 0 for i = l,2,...,t, and if the functional 2 J = )3 f (X(k')) k=l 0 attains its minimum value, for X(i<) : _}_((k), subject to these constraints. If the function fO is unity, the control which minimizes the func- tional J is that which satisfies constraint (4) with minimum 2 . In order to state the Pontryagin maximum principle it is necessary to augment the N state equations with the scalar equation -33- x (k+l) - x (k) : f (35m), k: i,2,...,i O O O which results in the NH equations xi(k+1) - xi(k) = fi(3<’(k).3'3 f.[§(k). 3110] p.(k+l)> Z f.[_3£(k). U(k)] P.(k+1). for allk= 1,2,...,2 andalluESZ, -D —b a —->-—b _ (2) P(k+1) - P(k) : - for allkz l,2,...,£. Condition (1) is, of course, the maximization of Hamiltonian, while the adjoint equations are represented by (2). For a proof of the Maximum Principle in this form see [HA 2]. 3. 3 Solution of the Optimal Control Problem The traffic control problem as formulated in Section 3. 2 is in a form to which the discrete maximum principle may be applied. Let the state model for the traffic control system of (3. 3) be augmented to include the object function f0. Further, let f0 be -34- unity, then the state model for the minimum interval case becomes: _xo(k+l)— flxo(k)— - i _ F o 0— _yo(k)- 351(k+1) - 351(k) = “('3' + -U o 371(k) (3.12) 322(k+i) 322(k) 0 A B 720.: IfthegridisnbymletN=2(m+n+mn+l)and0=m+n+2, then the state model in (3.12) is N + 1 dimensional. The vectors 3:1, (3’, and .371 have 0 components while x2 and yz have N - 0 components. The Hamiltonian is —. -. —o N -—>—o- —-> -—> —-> —-> —> : f = + 0P - P + A + B 0P .1 PUP. X. u) E p. . PO (3 1 71' l ( Y1 Y2) 2 (3 3) i=0 J where the vector Pl has 0‘ components and P2 has N - 0 components. The adjoint equations are II 0 p-a Z N . pgk+i)- pgk) = - z --i- pgk+it i (3.14.) j=0 i k: l,2,...,£ . Clearly, since 5.65,?) is independent of the state variable 35, (3. 14a) becomes Po(k+1) (3 (k) 0 ”131(k+1) - 331(k) = o . (3.14b) P2(k+l) P2(k) The co-state variables, pi, corresponding to time optimal control are all constants. It follows that (3.13) can be written as —> —‘> —-v ——>—* —.-t—.§ -'> —-> H(P, x, u): p +(3op +Dy +Ety (3.15) O 1 1 2 where D = (P.2 A - Plt) and Et : PZtB. H(P, X, ) is a maximum when the ith components “—771 and—)7Z are max[ sign(d,l)‘y,l] and max[sign(e.l)y.l], respectively. This is simply the familiar result that all time Optimal controls for linear systems are on the boundary of the admissable set 9[ PO 1]. This fact allows Optimal trajectories for a number Of traffic systems to be sketched. 3. 4 Cascaded Signals Let 0 : 1 and N = 2. Equation (3. 3) then reduces to the two scalar equations x (k+l) x (k) -l O [y (k) y l _ 1 : -. l 11 (3.16) + I x2(k l) x2(k) a b Ly2(k) O _J where a is the percent Of 7'1 which enters street 2, while b = -1. This corresponds to an array of streets of the form shown in Figure 3. 3, that is, a series connection Of two streets. 3. 3 Series connection of two streets -36- The admissable set 82 is :2: {in Oiyiimin(Fi, xi), fori: 1, 2} (3.17) Consider now the Optimal trajectories resulting from the control 7’1 = F1 and 72 = F . Equation (3.16) becomes 2 xl(k) = xl(O) - k(I"l - yll) (3.18a) x2(k) = xz(0) - kaI‘1 - kFZ (3.18b) Substitution of (3.18a) into (3. 18b) yields (provided F1 - y11 )5 O): (FZ-aFI) (Fz-aI‘I) x (k) = x (k) - x (O) - x (O) (3.19) 2 (Fz-Yn) 1 2 (F1 'Yii) 1 Under the assumption that yll is constant, the phase plane plot is as shown in Figures 3.4a and 3.4b. \ 3.4a Phase plane for F2 > afl -37- +— "J l I .1. 3.4b Phase plane for F = a1" When yll = F (3.18a) reduces to: l x (k) = x (O) = const. (3.20) Therefore, for this case the phase plane plot takes the form shown in Figure 3. 4c. X Z I l ‘ i i (V v v 1) 1) r'____ _____ .. l a]? ___-.|.--.-(t.-__..---_..__.-.i-___-_i-___i ______ 1 i 131 X1 3.4c Phase plane for F1 2 yll The arrows on the Optimal trajectories indicate the direction of increasing k (time). Clearly when the input demand to the system is so great that y” > Fl there exists no control, 'yl, in the admissable set Sbwhich will reduce the initial value of XI. For this reason, and because queue lengths are not restricted outside of the control region, yll will always be selected so that (1" )3 0. Similarly, if 1 " y11 F2 < aFl there exists no admissable control, yz, which will reduce the initial value of x2. Furthermore, in the event F2 < aFl the maximum capacity of the system is determined by F2. Therefore, in the event P2 < a? the value of F1 will be decreased so that 1’ F2 3 aFl. Under these assumptions an Optimal control may always be selected which will monotonically decrease any initial state toward the origin. Referring to Figures 3. 4 note that as the optimal trajectories cross the lines x (k) = F or x2(k) : F their slope is no longer 1 1 2' constant. This is a consequence Of the fact that the admissable set, 9, is a function of the state of the system. Furthermore, if the state of the system is such that, for at least some 1, xi 5 Fi’ the ith queue may be dissipated in one light cycle. If this is the case the density obviously is not high enough for transit time to be neglected (a basic assumption for the high density mode Of operation). Notice, however, that application of the prOper Optimal -39.. control monotonically decreases any initial state to the point (F1, F2), at which time the control mode will be transferred to one Of low or medium density. 3. 5 The Single Intersection Consider the case of the single intersection as shown in Figure 3.5. y 21 *2 ...a 3.5 Single intersection The state model for this arrangement of streets is: x (k+1) x (k) 1 - 1 = + (3.21) I- x2(k+1) x21) y12 Solving (3. 21) recursively yields: x1(k)= k(y11- yl) +xl(0) (3.22a) x2(k) = k( )+ x7(0) (3.22b) y12 ‘ 7’2 In the event that, for some i, yl.l _>_ F1, it is clear that no admis- sable control exists which will decrease the initial state of xi. -.-40- For this reason yli is restricted so that y“ < Pi for all i (3.23) Substituting (3. 22a) into (3. 22b) yields, under the control (yliyz) : (F1! F2)! x2(k) = 0.x1(k) + x2(0) - 0.x1(0) (3.24) where 0., the Optimal trajectory slope, is given as: (T -y ) a z 1‘2 17-) (3.25) ( 1 ‘ y11 The phase plane plot of the Optimal trajectories is shown in figure 3.6. x2 3. 6 Single intersection optimal trajectories In this case, as in the case of two series connected streets, the optimal trajectories are straight lines only for X1 > F1 and x2 : 1‘2. Notice that as the phase plane point, (x1, x2) approaches -41- the point (yll, ) the optimal trajectories asymtotically approach y12 the lines x and x These trajectories are clearly all lzyll 2=Y12’ monotonic decreasing, and all pass through the point (yll, ylz). Furthermore, note that the point (yll, ) is always ”inside the Y12 pOint (F1, F2), that is y11< F1 and y12 < I‘Z. This assures that an admissable optimal control always exists which will drive the system, in a monotonic decreasing manner, to a point where the control may be changed to a low or medium density mode. 3. 6 Arterials of Arbitrary Length Consider now the case of a long arterial. That is, assume that the area to be put under control consists of a series connection of N one way street sections, as shown in figure 3. 7. Let y11 be the input to the end of the arterial, and assume that there is no input to the arterial except at that end. All of the results of the following develOpment can easily be extended to the case where known inputs are allowed at points other than at the end, however, for notational convenience only the single input case will be con- sidered. @1 ®( @1— ———®(— 3. 7 Single arterial Equation (3. 3) for this street arrangement becomes ” — -42- xl(k+1) X1(k) yll -l 0 O O O 'y1(k) - O O x2(k+l) x2(k) 0 a2 1 O y2(k) _ : + _. x3(k+l) x3(k) O 0 a3 1 0 O 'y3(k) xN(k+l) xN(k) 0 o 0 . aN -i yN(k) _ _J — _ |-— _i b _J (3. 26) Notice that the control matrix is triangular (in fact bidiagonal) with . N determinant (-1) . Recall from the previous analysis of two series connected streets that, although the optimal trajectory is a function of the in- put, the Optimal control is independent of any input. Input y11’ levels are only bounded by the requirement that the Optimal tra- jectory be monotonic decreasing. With this in mind, consider the N section series connected street. Using a technique very similar to dynamic programming [DR 1] each subsection of the arterial will be independently Opti- mized starting at the ”output" end (i. e. , at i = N) and working back until bounds on the input, are obtained. y11’ Since, by the definition of the control region, there is assumed to be an infinite sink at the end Of the arterial x (3.27) YN min[ TN, N]. Furthermore, the state variable, x , is monotonically de- N-l creasing when YN satisfies 1 -43- ('yN - aN'yN_l) 3 0. (3.28) Equation (3. 28) together with the fact that yN 1 must come from the admissable set, S2, requires yN-l = min[ min(1_‘N_1, XN~1)' yN/aN] (3.29) Applying the above argument to the ith section of street yields 31.1: min[min(1",l,xi), yi+l/ai+1] for i =1, 2,. . . , N-l (3. 30) where yN is specified by (3.27). An optimal control recursively derived by (3. 27) and (3. 30) is clearly one which results in mono- tonically decreasing optimal trajectories and satisfies the necessary conditions of the Pontryagin Maximum Principle. 3. 7 Rectangular Grids Consider now the most interesting, and probably most use- ful, grid configuration, a simple grid of intersecting arterials. An example of such a grid is shown schematically in Figure 3. 8. -44- 3.1.1 T3 V4 1 10 7 I f (73 £1272 I0133,13)— 0 The inequality (3. 33) forces 7’2 to be Y2 : min[min(I_‘2,x2), ('y In a similar manner 711 = min[min(F1,x1), (y The equations for Y4: 715, Y6 are: ‘< O\ l - min(F6, X6) 'y5 = min[min(F5,x5), (y6 - ‘i ..p. H 4 4 3- 2- min[min(f ,x ),Q(‘y5 - b213yi3)/a ] b 78ml] 14Y14Va5 ] b7Y7')/a4] (3.33) (3.34) (3.35) (3.36) (3.37) (3.38) Equations (3. 32) through (3. 38) present. no problem until attempting to solve for 71 and 74- Ln order to solve (3. 35) and (3. 38) know- ledge Of y8 and y? is needed. Therefore consider the remaining two arterials. Immediately we see 2 min(F , x V9 9 9) 78 = min[min(F8, x8), (y - b Y117a8] (3.39) (3.40) -46- and =min(]_" ,x ) (3.41) 710 10 10 77 min[min(f‘7, x7), ('ylo - b4y4)/a7] (3.42) As would be expected, it is necessary to solve (3. 35) and (3.40) as a pair of simultaneous inequalities in order to obtain 71 and y8. Similarly (3. 38) and (3. 42) must be solved simultaneously tO Obtain 'y4 and 717. Therefore examine (3. 35) and (3.40). Recall the inequalities which resulted in the right hand terms of (3. 35) and (3.40). Written as a matrix inequality they become ‘5 9 (3.43) The assumption that the square matrix in (3.43) is nonsingular (i.e., a +a8 -1# 0) yields 1 7 a -b 7 8 < i 1 1 9 (3.44) -(a+a-l) i 8 _b a V1 8 8 Yzi The above inequality together with the left hand terms in (3. 35) and (3. 40) implies 78 min[min