The emergence of autonomous vehicles is expected to revolutionize road transportation in the near future. Although large-scale numerical simulations and small-scale experiments have shown promising results, a comprehensive theoretical understanding to smooth traffic flow via autonomous vehicles is lacking. Here, from a control-theoretic perspective, we establish analytical results on the controllability, stabilizability, and reachability of a mixed traffic system consisting of human-driven vehicles and autonomous vehicles in a ring road. We show that the mixed traffic system is not completely controllable, but is stabilizable, indicating that autonomous vehicles can not only suppress unstable traffic waves but also guide the traffic flow to a higher speed. Accordingly, we establish the maximum traffic speed achievable via controlling autonomous vehicles. We also design an optimal control strategy for autonomous vehicles to actively dampen undesirable perturbations. These theoretic findings validate the high potential of autonomous vehicles to smooth traffic flow. Modern societies are increasingly relying on complex road transportation systems to support our daily mobility needs. In particular big cities, the traffic demand is placing a heavy burden on the existing transportation infrastructures, sometimes leading to severely congested road networks [1] . Traffic congestion not only results in the loss of fuel economy and travel efficiency, but also increases the potential risk of traffic accidents and public health [2] . Understanding traffic dynamics is essential if we are to redesign infrastructures, or to guide/control transportation, to mitigate road congestions and smooth traffic flow [3, 4] . The subject of traffic dynamics has attracted research interest from many disciplines, including mathematics, physics, and engineering. Since the 1930s, a wide range of models at both the macroscopic and microscopic levels have been proposed to describe traffic behavior [3] . Based on these traffic models, many control methods have been introduced and implemented to improve the performance of road transportation systems [4] . Currently, most control strategies rely on actuators at fixed locations. For example, variable speed advisory or variable speed limits [5] are commonly implemented through traffic signs on roadside infrastructure, and ramp metering [6] typically relies on traffic signals located at the freeway entrances. These strategies are essentially external regulation methods imposed on traffic flow. As a key ingredient of traffic flow, the motion of vehicles plays a fundamental role in road transportation systems. In the past decades, major car-manufacturers and technology companies have invested in developing vehicles with high levels of automation, and some prototypes of autonomous self-driving cars have been tested in real traffic environments [7] . The emergence of autonomous vehicles is expected to revolutionize road transportation. In particular, * Figure 1 : Response profiles to an impulse perturbation in traffic systems on a ring road. Vehicle no.2 has an initial perturbation, and the parameters of human-driven vehicles are chosen to resemble the wave behavior in the real-world experiment [23] . (a) All the vehicles are human-driven, where the perturbation is amplified and stop-and go waves will appear accordingly. (b) Vehicle no.1 is a CACC-equipped vehicle which adjusts its behavior passively according to its direct preceding vehicle. In this case, the perturbation is not amplified but small traffic waves still persist for a long period. (c) Vehicle no.1 adopts an optimal control strategy considering the global behavior of the entire mixed traffic flow to mitigate undesirable perturbations actively. In this case, the perturbation is attenuated, and the traffic flow becomes smooth quickly. the advancements of autonomous vehicles offer new opportunities for traffic control, where autonomous vehicles can act as moving actuators to influence traffic flow internally. Most research on the control of traffic flow via autonomous vehicles has focused on platooning of a series of adjacent vehicles or cooperative adaptive cruise control (CACC) [8, 9] . In the context of platoon control, all involved vehicles are assumed to be autonomous and can be controlled to maintain a string stable platoon, such that disturbances along the platoon are dissipated. Significant theoretical and practical advances have been made in designing sophisticated controllers at the platoon level [10] [11] [12] . While traffic systems with fully autonomous vehicles may be of great interest in the far future, the near future will have to meet a mixed traffic where both autonomous and human-driven vehicles exist. In fact, early autonomous vehicles need to cooperate in traffic systems where most vehicles are human-driven. This situation is more challenging in terms of theoretical modeling and stability analysis, and many existing studies are based on numerical simulations [13] [14] [15] . One recent concept is the connected cruise control that considers mixed traffic scenarios where autonomous vehicles can use the information from multiple human-driven vehicles ahead to make control decisions [16, 17] . More recently, Cui et al. first pointed out the potential of a single autonomous vehicle in stabilizing mixed traffic flow [18] , and they also implemented simple control strategies to demonstrate the dissipation of stop-and-go waves via a single autonomous vehicle in real experiments [19] . The control principle is essentially a slow-in fast-out approach, which is an intuitive method to dampen traffic jams [20] . More sophisticated strategies, such as deep reinforcement learning, have also recently been investigated to improve traffic flow in mixed traffic scenarios via numerical simulations [21, 22] . While the potential of autonomous vehicles has been recognized and demonstrated [18, 19, 21, 22] , a comprehensive theoretical understanding is lacking. In this paper, we provide a theoretical analysis on the potential of autonomous vehicles in smoothing mixed traffic flow from a complex system viewpoint. In principle, the behavior of traffic flow emerges from the collective dynamics of many individual human-driven and/or autonomous vehicles [3] , where autonomous vehicles can serve as controllable nodes. In the area of complex systems, controlling the collective behavior of dynamical agents interacting over networks has a long history, capturing phenomena from flocking of birds or fish to the synchronization of coupled oscillators [24] [25] [26] . From a complex system perspective, we first investigate analytical 3 stability results for traffic systems with only human-driven vehicles. After introducing an autonomous vehicle as a controllable node, we next establish basic notions of controllability and stabilizability of such mixed traffic flow. These theoretical results reveal the high potential of autonomous vehicles to guide the collective dynamics of mixed traffic flow to a desired state (e.g., a higher traffic speed). Accordingly, we design an optimal control strategy of autonomous vehicles to smooth mixed traffic flow. Instead of responding to traffic perturbations passively, the proposed optimal control strategy considers the global behavior of the entire mixed traffic flow to mitigate undesirable perturbations actively (see Figure 1 for illustration). Extensive numerical experiments validate our theoretical analysis and clearly demonstrates the high potential of autonomous vehicles on controlling and smoothing traffic flow. Theoretical framework of mixed traffic systems. We consider a single-lane ring road of length L and with n vehicles. As discussed in Cui et al. [18], the ring road setting has several theoretical advantages for modeling a traffic system, including 1) the existence of experiment results that can be used to calibrate model parameters [23] , 2) perfect control of average traffic density, and 3) correspondence with an infinite straight road with periodic traffic dynamics. We denote the position of the i-th vehicle as p i (t) along the ring road, and its velocity is denoted as v i (t) =ṗ i (t). The spacing of vehicle i, i.e., the distance between two adjacent vehicles, is defined as s i (t) = p i−1 (t) − p i (t). Note that we ignore the vehicle length without loss of generality. For simplicity, we assume that there is one autonomous vehicle and the rest are human-driven vehicles. The autonomous vehicle is indexed as no. 1. The scenario with multiple autonomous vehicles will be discussed at the end of this section. Real-world human car-following behaviors are typically modeled by nonlinear processes [3, 4]  ), but stability analysis around an equilibrium point can be performed via a linearization [27] . From a global complex system viewpoint, we arrive at the following canonical linear dynamics (see Methods) where u(t) ∈ R denotes the control input of the autonomous vehicle on the traffic system dynamics; the vector captures the error state of n vehicles at time t; the error state of vehicle i is defined as with s * , v * being the equilibrium spacing and velocity of each humandriven vehicle, i = 2, . . . , n, and denotes the error state of the autonomous vehicle with s * c being a tunable spacing. Note that for human-driven vehicles, the equilibrium traffic state (s * , v * ) satisfies , which implies a certain relationship between the equilibrium spacing and equilibrium velocity (see Supplementary Note 1). Considering the ring road setting of mixed traffic systems, the matrices A and B in (1) are where each block matrix is given by with parameters Considering the real driver behavior, we should have α 1 > 0, α 2 > 0 and α 3 > 0. It can be shown that ring road traffic with common car-following dynamics can be linearized into the form of (1)-(3) (see Supplementary Note 1). In (1), the evolution of each vehicle's state is determined by its own state and the state of its direct preceding vehicle only; see Figure 2 for a schematic model. In the following, we provide a theoretical analysis on the potential of the autonomous vehicle on smoothing the mixed traffic flow and design an optimal control input u(t) for the autonomous vehicle. Stability of traffic systems with human-driven vehicles only. If all the vehicles are driven by human, the traffic system dynamics (1) can be simplified intoẋ SinceÂ is block circulant, it can be diagonalized into a block diagonal matrix [28, 29] where each block is of size two. Then, we can show that there always exists a zero eigenvalue which corresponds to the ring road structure, indicating a constant value in the system evolution (see Methods). In addition, from the block diagonalization, we can derive the following analytical criterion for the other eigenvalues to have negative real parts, which guarantees stability of the traffic system (4) with any finite n (i.e., small perturbations will be attenuated in the system evolution) This result is consistent with the result in [18] where frequency analysis was used. The optimal-velocity model (OVM) is widely-used to describe human car-following dynamics (see Supplementary Note 1), and is given by , where α and β represent the driver's sensitivity to velocity errors and V (s) denotes an optimal velocity function according to the spacing s i (t) [30] . For this car-following model, the stability criterion (5) is reduced to α + 2β ≥V (s * ). To guarantee stability, this inequality indicates that human drivers should have a quicker response to velocity deviations than the sensitivity of the optimal velocity function with respect to spacing in the equilibrium; otherwise, the traffic system may become unstable and small perturbations would cause stop-and-go waves; see Figure 3 for an illustration of stable and unstable traffic systems. Controllability and stabilizability of mixed traffic systems. It is revealed that a traffic system with human-driven vehicles may be unstable and stop-and-go waves occur accordingly. Here, we address the potential of autonomous vehicles to suppress the instability of mixed traffic flow. Specifically, we consider two fundamental concepts, controllability and stabilizability, of the mixed traffic system (1). According to control theory, the controllability of a dynamical system captures the ability to guide the system's behavior towards a desired state using appropriate control inputs, and the system is stabilizable if all uncontrollable modes are stable [31] . Precisely, the linearized mixed traffic system (1) is controllable if and only if the controllability matrix Q c = B AB A 2 B . . . A 2n−1 B has full rank. As explained in the Methods, we prove that the mixed traffic system is not completely controllable and there always exists at least one uncontrollable mode. Precisely, we prove Furthermore, irrespectively of the values of α 1 , α 2 , α 3 , we show that one uncontrollable component exactly corresponds to the sum of each vehicle's spacing, which remains a constant value during the system evolution and is determined by the ring road circumference (see Supplementary Note 3). In other words, this uncontrollable mode corresponds to a zero eigenvalue. When α 1 − α 2 α 3 + α 2 3 = 0, the rest of modes are all controllable, and if α 1 − α 2 α 3 + α 2 3 = 0, the rest of modes are all stable considering the stability test (5). Therefore, the mixed traffic system (1) is always stabilizable when there exists a single autonomous vehicle in the system. Consequently, by choosing an appropriate control input, the autonomous vehicle can not only stabilize the global traffic flow, but also steer the system to a higher equilibrium traffic speed (a detailed analysis is presented in the next section). Numerical simulations in Figure 4 confirms our analysis, where the previous unstable traffic system with human-driven vehicles only (Figure 3(e) ) becomes stable (Figure 4(a) ), and the traffic speed can be increased from 15 m/s to 16 m/s (Figure 4(b) ). Reachability and system final state. We have shown that the mixed traffic system (1) is always stabilizable when there exists an autonomous vehicle. In fact, we can further predict the system final state, which sheds some insight on the reachability of the equilibrium traffic state (s * , v * ). Also, it is explicitly shown that the autonomous vehicle can indeed increase traffic equilibrium speed v * . Recall that we can design the desired spacing s * c for the autonomous vehicle. We assume a linear state feedback controller u(t) = −Kx(t), where K = k 1,1 , k 1,2 , k 2,1 , k 2,2, , . . . , k n,1 , k n,2 ∈ R 1×2n is the feedback gain. As explained in the Methods, we prove that irrespectively of the initial state x(0), the final state of the stable mixed traffic system must be in the following form: where s e and v e are the solution of (7). where α 1 , α 2 , α 3 are the parameters in car-following dynamics (3), and k i,1 , k i,2 are fixed feedback gains of the autonomous vehicle. Indeed, equation (7b)  In principle, since the mixed traffic system (1) is stabilizable, it can be guided to reach any equilibrium state with traffic speed v * via controlling the autonomous vehicle properly. In practice, however, the spacing of the autonomous vehicle cannot be negative, i.e., s * c > 0, which is equivalent to This sets up a maximum equilibrium traffic speed v * according to F (s * , 0, v * ) = 0 (see Supplementary Figure S1 for a typical relationship between s * and v * ), which is higher than the equilibrium traffic speed with only human-driven vehicles. A physical interpretation is that the autonomous vehicle can follow its preceding vehicle at a shorter distance and leave more space for its following human-driven vehicles, which in turn triggers the human-driven vehicles to travel at a higher speed in the equilibrium; see Supplementary Figure S2 for illustration. Designing an optimal control strategy. We have shown that a mixed traffic system with a single autonomous vehicle is stabilizable. Following standard control theory [31], we can design an optimal control strategy to reject perturbations in the mixed traffic system. This scenario is modeled by assuming that there exists a disturbance signal 8 w i (t) in each vehicle's acceleration signal. In other words, the linearized dynamics of human-driven vehicle (1) becomė Then, we design an optimal control input u(t) = −Kx(t) to minimize the influence of disturbances on the traffic system. Mathematically, we aim to solve an optimization problem min K G wz , where G wz denotes the transfer function from disturbance signal w(t) = w 1 (t), . . . , w n (t) T to the traffic performance state z(t) = γ ss1 (t), γ vṽ1 (t), . . . , γ ssn (t), γ vṽn (t), γ u u(t) Here, we consider a scenario with the presence of infrastructure bottlenecks or lane changing [19] , where one vehicle has a rapid deceleration representing a strong perturbation. In the beginning, the traffic flow is at the equilibrium state with the velocity 15m/s. And then at t = 20s, the i-th vehicle decelerates to 5m/s in two seconds. As shown in Figure 5 , we observe that if all the vehicles are human-driven, the perturbation may grow stronger during the propagation process, while the autonomous vehicle with an optimal control strategy can respond actively to attenuate the perturbation and stabilize the traffic flow. In Supplementary Note 5, we present the numerical results for the scenarios with different positions of the perturbation, i.e., the perturbation appears at vehicle 2, 3, . . . , n, respectively. We also compare the optimal control strategy and two other heuristic strategies (FollowerStopper and PI with Saturation [19]). Numerical experiments confirm that the optimal control method has the best performance in terms of control energy and settling time (see Supplementary Note 5). Traffic systems with multiple autonomous vehicles. The mixed traffic system with a single autonomous vehicle is stabilizable, which is independent of the number of vehicles n. Also, an optimal control strategy u(t) can be obtained by solving an optimization problem. However, it might be not practical to control a mixed traffic system consisting of many human-driven vehicles and a single autonomous vehicle. Under this circumstance, the energy and time required 9 for attenuating disturbances may be large, even when the autonomous vehicle adopts the optimal control strategy. Indeed, our previous analysis can be extended to a mixed traffic system with multiple autonomous vehicles. Specifically, we assume that there are n vehicles in the traffic flow with k autonomous vehicles (k < n). As explained in the Supplementary Note 6, similarly to system (1), there exists an uncontrollable mode in the mixed traffic system with k autonomous vehicles. As expected, the mixed traffic system with k autonomous vehicles is stabilizable. In addition, we can show that the reachable final traffic state is where s * j,c , j = 1, . . . , k denotes the desired spacing of the j-th autonomous vehicle. In this case, the maximum spacing for each human-driven vehicle in the equilibrium can be increased to and this corresponds to a higher equilibrium traffic velocity v * . We conduct numerical experiments for the scenario where the traffic system has two autonomous vehicles, and the results are shown in Figure 6 . It is clear that both the settling time and the control energy of each autonomous vehicle decrease by a factor of two approximately, when there are two autonomous vehicles in the traffic system uniformly. Based on the results, we may estimate the market penetration rate of autonomous vehicles to control traffic flow effectively when adopting the optimal control strategy. In the scenario of  10 As demonstrated in the pioneering experiments in [19] , unlike the traditional control methods that regulate traffic flow externally at fixed positions, autonomous vehicles can be used as moving actuators to control traffic flow internally. In this paper, we have introduced a comprehensive theoretical analysis to address the potential of autonomous vehicles on smoothing mixed traffic flow. Specifically, we have derived the criterion of stability for traffic systems with humandriven vehicles only, and analyzed the controllability, stabilizability, and reachability of mixed traffic systems. Also, an optimal control strategy has been introduced to actively smooth mixed traffic flow. From our analysis, we pointed out that the mixed traffic system is stabilizable, and is not completely controllable. Through controlling the autonomous vehicle properly, the entire traffic system can be guided to a desired traffic state. In particular, the desired equilibrium state (s * , v * ) can be designed to vary within a certain range. The setting is similar to the design of vehicle platoons, where all autonomous vehicles can be controlled to reach a desired spacing and a desired velocity [10] [11] [12] . In a mixed traffic system, the desired state (s * , v * ) for human-driven vehicles should satisfy the car-following models (see Supplementary Figure 1 ), while the desired state (s * c , v * ) for the autonomous vehicle can be designed separately. This leads to the reachability result, where we have shown a single autonomous vehicle can not only smooth traffic flow but also increase traffic speed. In our framework, we have proposed that the autonomous vehicle can respond to external perturbations actively to smooth traffic flow efficiently. For this objective, we computed an optimal control strategy by solving an optimization problem that considers the entire traffic state. The resulting controller can smooth the traffic flow more quickly than traditional passive control strategies [18, 19] (See Figure 1) . Note that in the design of optimal control strategies, we can choose three parameters, corresponding to the spacing deviation γ s , velocity deviation γ v and the control energy penalty γ u . These three parameters can be adjusted depending on different preferences. In addition, we have shown that controlling multiple autonomous vehicles has better performance for large-scale mixed traffic systems. Autonomous vehicles can cooperate with each other to reduce the time and energy for attenuating perturbations and smoothing traffic flow. In our framework, it is possible to identify an appropriate market penetration rate of autonomous vehicles from the perspective of settling time. Based on our simulations, autonomous vehicles have practical ability to smooth traffic flow at a low penetration rate (one autonomous vehicles per around 20 human-driven vehicles) when adopting the optimal control strategy. The ability of autonomous vehicles at a low penetration rate has been experimentally confirmed in [19] . A few other topics are worth further investigation. In our current analysis, we have assumed autonomous vehicles have access to the global the traffic state, i.e., the information of all other human-driven vehicles. Due to the limit of communication ranges, autonomous vehicles may be only able to obtain the information of its neighboring vehicles. It is interesting to design a localized optimal controller, and this leads to the notion of structured controller synthesis [32, 33] . For the tractable issue in theory, we have assumed homogeneous dynamics for human-driven vehicles, and potential time delays are ignored. One interesting direction is to consider heterogeneity and time delay in controlling mixed traffic systems. We note that some recent work has considered the effect of heterogeneity and time delays at the level of platoon control [34] [35] [36] , which may offer some insights for the controller design in mixed traffic systems as well. Finally, our current analysis focused on the single-lane ring road setting, and it would be interesting to extend our analysis to the scenarios with multiple lanes and lane-changing behavior. Methods Deriving the mathematical model of mixed traffic system. Using the first-order Taylor expansion, the general car-following model of human-driven vehicles, i.e.,v i (t) = F (s i (t),ṡ i (t), v i (t)), i = 2, . . . , n, can be linearized into  Combining (9) with (10) leads to the global linear dynamics (1). In Supplementary Note 1, we provide a detailed derivation of (1) as well as the linearization process for two typical car-following models (i.e., OVM and IDM). To analyze the stability of matrixÂ, it is necessary and sufficient to study its eigenvalues' distribution. SinceÂ is a block circulant matrix, it can be diagonalized to simplify the eigenvalue calculation. Define ω = e  where F * n denotes the conjugate transpose matrix of F n . By the definition of Fourier matrix, we know that F n and F * n are symmetric, i.e., F * n = (F * n ) T , F n = F T n , and that F n is a unitary matrix, i.e., F n F * n = I n , where I n denotes the n × n identity matrix. Then,Â can be diagonalized intô where ⊗ denotes the Kronecker product, . . , D n on its diagonal blocks. Then the eigenvalue λ satisfies Substituting the expression of ω into (11) leads to where e i−1 n ·2πj , i = 1, . . . , n are the complex roots of z n = 1. It means for all 2n values of λ, the values of H(λ) constitute n unit roots. When n or i changes, H(λ) corresponds to different unit roots. Then, the condition that the roots of |H(λ)| = 1 have negative real parts is sufficient to guarantee that the zeros of (11) lie in the left half plane, i.e., the system matrixÂ is stable. Following the strategy in [18] , we arrive at the stability condition (5). The interested reader is referred to Supplementary Note 2 for details. Controllability analysis via block circulant matrix diagonalization. For notational simplicity, we use a pair of matrices (A, B) to represent a linear system in the canonical form (1). First, we convert (A, B) into (Â, B) by using a virtual control inputû(t), defined asû(t) = u(t) − (α 1s1 (t) − α 2ṽ1 (t) + α 3ṽn (t)). This virtual control input can be viewed as the difference between the actual control value and the acceleration value when the vehicle is human-driven. Note that the controllability of a linear systems remains unchanged under feedback and linear transformations (see Supplementary Note 3), thus the controllability of (A, B) is the same as that of (Â, B). In the state-space formulation, the new system ( A, B) is of the following forṁ where B 1 = 0, 1 T . Upon denoting new state variablex(t) as x 11 ,x 12 ,x 21 ,x 22 , . . . ,x n1 ,x n2 T , this system can be decoupled into n independent sub-systems (i = 1, 2, . . . , n) We denote the controllability matrix of each sub-system as Q c,i . It is easy to see that rank(Q c,1 ) = 1, indicating that the first sub-system has an uncontrollable component. Therefore, system ( A, B) is not completely controllable and 13 has at least an uncontrollable component. In particular, the first sub-system is  is constant during the dynamic evolution. In conclusion, the mixed traffic system (A, B) is not completely controllable, and has at least an uncontrollable mode (13) corresponding to a zero eigenvalue. In particular, this mode (13) corresponds to the sum of each vehicle's spacing Therefore, we have (6) since the controllability rank is invariant under feedback and linear transformation. Note that the condition α 1 − α 2 α 3 + α 2 3 = 0 has a probability of one when considering α 1 , α 2 , α 3 randomly. Predicting the final state of mixed traffic systems. For a stable system, the state will approach to its equilibrium point. In our mixed traffic system, we analyze the dynamics of each vehicle (9) and (10) separately, leading tõ s 1 (t f ) = s e ,ṽ i (t f ) = v e ,s i (t f ) = α 2 − α 3 α 1 v e , i = 2, 3, . . . , n, where s e , v e are constant values, and t f is the time when the system reaches its equilibrium point. We next derive that (s e , v e ) should satisfy (7), from which we can calculate the exact value of s e and v e . In the final state, all the vehicles have zero acceleration, indicating that the control input u(t) must be zero, i.e., u(t) = −Kx(t) = 0, leading to (7a). Besides, according to the controllability analysis, we know that (s 1 (t) − s * c ) + n i=2 (s i (t) − s * ) remains constant; see (13). Together with the system initial state and final state, we can obtain (7b). Numerical experiments. Details of our numerical experiments and additional comparison with two heuristic control methods can be found in Supplementary Note 5. In our experiments, the standard OVM model was used to represent the human-driven car-following dynamics. All experiments were carried out in MATLAB, and the optimal control strategy was computed using the conic solver Moesk [37]. 14 Acknowledgements We thank A. Papachristodoulou, J. Wang, Q. Xu, L. Romao, S. Yan and C. Chen for comments and discussions. We would also like to thank R. Drummond for providing constructive feedback. Y
Ref. REF proved that a ring system is stabilizable by controlling only a single vehicle.
Smoothing traffic flow via control of autonomous vehicles
ArXiv
ArXiv
Mathematics Computer Science