Safe and Secure Control of Swarms of Vehicles by Small-World Theory

Abstract

The present paper investigates a new paradigm to control a swarm of moving individual vehicles, based on the introduction of a few random long-range communications in a queue dominated by short-range car-following dynamics. The theoretical approach adapts the small-world theory, originally proposed in social sciences, to the investigation of these networks. It is shown that the controlled system exhibits properties of higher synchronization and robustness with respect to communication failures. The considered application to a vehicle swarm shows how safety and security of the related traffic dynamics are strongly increased, diminishing the collision probability even in the presence of a hacker attack to some connectivity channels.

1. Introduction

The fast development of new technologies in vehicle control and vehicle-to-vehicle (V2V) connectivity by advanced onboard sensors, presents the opportunity to optimize the collective behavior of a population of vehicles, improving the safety and also the security of the people and of the good mobility [1,2,3,4,5]. Safety relies on diminishing the probability of accidents because the vehicle-to-vehicle connectivity permits to transport the information on a long-range scale, with a better synchronization of the vehicle’s motion [6,7,8,9,10]. On the other hand, one of the critical elements of this extended connectivity is that communication can be delayed [3,11], accidentally disturbed or broken, or purposely disturbed interfering with some communication channels, distorting or canceling some transmitted information by a hacker attack [12]. This second element requires the collective behavior of the traffic is robust with respect to the insertion or removal of connections [4,9]. Both the safety and security needs represent big challenges [4,10,13,14,15] in the autonomous vehicle technology development, and government and regulatory institutions, as well as large private companies, have these actions in their strategic agenda.

The present paper considers a new paradigm for V2V [16] connectivity, based on the addition of a few random long-range connections, to take advantage of the big opportunity the emerging new technologies offer. These additional communication channels are superimposed to the car-following mechanism, considered in more conventional traffic dynamics [17,18,19,20,21,22,23]. The original contribution of this investigation can be summarized as follows: (i) it is shown how few long-range connections are highly beneficial for the safety of the traffic system, diminishing the probability of collisions, offering a higher level of traffic flow synchronization, (ii) this safety benefit can be made robust with respect to the failure of some communication channels, the system exhibiting an intrinsic security if simple connectivity paradigms are followed, (iii) the method is based on re-adapting the Small-World theory, originally introduced in social sciences [24,25,26] to a network of cooperating vehicles. These results have an important practical value. In fact, the proposed V2V telecommunication network is of moderate complexity, including only a small number of interconnected vehicles, that produce even better results than a more ramified and capillary connectivity, reducing the cost of communication and the chance of failure. Moreover, because of the randomicity of the connections, the system connectivity can be easily reconfigured, randomly in space and periodically in time, making it secured. An additional argument to support the utility of this analysis is that V2V communications will be an evolutive process in which, in the beginning, only a small fraction of vehicles will be autonomous, and mixed autonomous and manned vehicles with long- and short-range communications, respectively, will coexist together for the times to come.

The theoretical background for this investigation views the traffic dynamics as a complex lattice the nodes of which are occupied by vehicles, subjected to both a convective and oscillatory motion. In the actual single-autonomous-vehicle, the controller takes data from the surrounding environment through on board-sensors (vision, acoustic and radar-based) that imitate the human perception. The same happens in large groups of animals, like a swarm of birds or a shoal of fishes [27,28,29,30,31]. Those animals, in general, have a limited perception of the surroundings since they move in highly populated groups. Each individual of the swarm perceives only a few similar about him and no chances to elaborate any navigation information of other elements of the swarm at a far distance. Nevertheless, despite the local nature of these decisions, under certain conditions, the swarm seems to act as a single body, showing a swarm intelligence [27,30], i.e., the emergence of an organized global behavior is observed.

In a new generation of autonomous vehicles, the increasing possibilities of vehicle-to-vehicle (V2V) and vehicles-to-infrastructure (V2I) [32] communications permit the autopilot to use information coming from remote parts of the swarm, i.e., received from similar individuals at long distance. This can potentially increase the collective intelligence of the system reducing the occurrence of collisions.

For example, along a queue on a highway, normally every vehicle adjusts its motion evaluating the distance and the velocity of the vehicle ahead. This phenomenon, based on a short-range interaction, has been widely investigated in the case of human drivers and is called car-following [17,18]. However, a more realistic scenario should include vehicles of different nature, as for instance autonomous vehicles and human-driven vehicles [33,34,35]. To guarantee an efficient integration and coordination, control algorithms are often designed so to mimic the human-like driving behavior [36,37], and, given the always-increasing number of vehicles, a collective intelligence, interweaving autonomous and non-autonomous vehicles at short and long-distance, becomes crucial to mitigate phenomena known as traffic waves [38,39,40]. Nevertheless, collective motions might be dominated by instability, and suitable control analytical methods must be provided to achieve safe and efficient global traffic motion [41,42].

The V2V communication systems allow some autonomous vehicles to act like no human driver could, using signals from some cooperating vehicles at a far distance in the queue. Is it possible to introduce a connectivity widening to induce an enhanced swarm intelligence? One of the main focus of this paper is to answer this question. In the following, it is proven that revisiting the small-world theory, few random long-range interactions between vehicles produce a strong motion synchronization along the queue, which is shown to reduce the probability of accidents.

2. Brief Resume of Small-World Theory Relevant for Swarm of Vehicles

The term small-world has been introduced by Stanley Milgram in 1967 in his seminal work on social networks, entitled “The Small-World Problem” [24]. In that article, Milgram introduces the small-world problem analyzing the intermediate acquaintance chain that connects two randomly chosen people in the world. It could happen that two people don’t know each other directly, but they share a mutual acquaintance that is a person who knows both of them. In this case, only one acquaintance link connects the two people. Milgram’s formulates the problem in this form: “Given any two people in the world, person X and person Z, how many intermediate acquaintance links are needed before X and Z are connected?” The experiment that Milgram conducted, brought to assert that, taken randomly two people in the United States, these are separated by a chain of relationships involving six acquaintance links. For this reason, his study is often called six degrees of separation.

Although the problem has been initially studied in the field of social networks, later it has been reconsidered in several other scientific fields approaching a strict definition of a small world model, still studied as a branch of the theory of graphs. This model, defined by Watts and Strogatz [26], provides a robust mathematical basis to the Milgram experiment. Besides the mathematical foundation, in this article an innovative significant concept is introduced, crucial for the present investigation. In the ordinary theory of graph, the connection topology is assumed to be either completely regular or completely random. In [26], the authors fill the gap, considering regular networks rewired to introduce some amount of disorder. They show these structures exhibit small characteristic path lengths, like random graphs, but with a modest addition or random connections. The dynamic of such small-world is shown to be characterized by high propagation speed and strong synchronization, a key effect in the present paper.

Technically, Watts and Strogatz consider a network made of vertices and unoriented links, initially characterized by a strongly regular pattern (in our case the short-range interactions of a car-following dynamics) that is randomly modified until a completely random pattern is obtained. The process is pictorially described in Figure 1.

In Figure 1, p is the probability that in the network one of the initial regular connection has been changed to connect distant vertices (in our case, for the traffic network, the chance of including in communication between distant vehicles). This probability can be increased from p = 0, representing the regular connection architecture, up to p = 1, the case of a completely random graph.

The effects of this progressive modification are studied using two parameters:

• $C\left(p\right)$ Cluster coefficient, it quantifies the amount of local interaction, among local groups of close by nodes, that in our case is a measure of the car-following interaction in the swarm. To define the clustering coefficient, suppose that a vertex $v$ has $k_v$ neighbors: at most $k_v\left(k_v-1\right)/2$ edges can exist between them and this happens when every neighbor of $v$ is connected to every other neighbour of $v$. Let $C_v$ denote the fraction of these allowable edges that actually exist and define $C\left(p\right)$ as the average of $C_v$ overall $v$.
• $L\left(p\right)$: Characteristic length of the paths, is the characteristic separation that is present between two nodes of the graph, however, they are chosen. $L$ is the number of edges in the shortest path between two vertices, averaged over all pairs of vertices. This parameter provides an indirect measure of the collective behavior of the network, that in our case is related to the synchronization effects of the swarm of vehicles.

Figure 2 shows how the global feature $L\left(p\right)$ is very sensitive to $p$, while the local feature $C\left(p\right)$ is insensitive to $p$ variations, at least in the region of small $p$. One conclusion of great importance, and very attractive for vehicular traffic, is that the collective behavior of a network can be activated by insemination of a moderate perturbation of random connections, permitting the local information to travel much faster than possible in regular local connectivity architectures.

The basic idea of this paper is this effect can be used in the development of new connectivity architectures to be used among a swarm of autonomous vehicles. Namely:

(a)

The swarm dynamics are initially based on short-range regular interactions taking place between individuals. This effect is related to the natural imitation of the human behavior that controls the motion of his own vehicle elaborating the information of the surrounding vehicles, perceived by proximity sensors.

(b)

The synchronization of the vehicles of the swarm is a collective behavior that reduces the probability of collisions. It is related to the speed at which the information and the mechanical reactions propagate along with the swarm. Therefore, one winning strategy is based on promoting the collective effects in the swarm. This result can be achieved by introducing V2V long-range communications.

(c)

The intriguing result of the small-world theory is represented by the fact this activation is possible using a moderate number of random long-range connectivity, meaning the perturbation to be introduced with respect to more classical traffic management is low-cost and technically feasible by a small number of hyper-connected cars in the swarm.

(d)

An additional added value of this control strategy is related to the random nature of the additional connectivity. Since the driving parameter to activate the collective response is $L\left(p\right)$, controlled by $p$, it means if the connections are individually altered but leaving $p$ constant, the level of collective behavior remains constant. This clarifies that in a connected swarm, we have the chance of modifying the connectivity architecture still preserving the synchronization. This is the root of the robustness of such architecture control that claims for better security of such systems. In fact, the connectivity architecture can be periodically or continuously modified, making useless to attack deliberately specific connections. Moreover, since there is not a central control unit, the system uses a distributed control logic the is made by connections of the individual. The intelligent behavior is because of the sparse random long-range connections, that is less prone to interference.

3. Complex Network of Vehicular Traffic

Car-following models are designed for a one-dimensional path. The leader has an assigned velocity law that represents the forcing term to the system. Every vehicle considers the vehicle in front as its leader and adjusts its acceleration accordingly: each follower may consider, for instance, the distance and the difference of velocity (given a characteristic delay) with regard to its leader, then computes its own acceleration. Therefore, any car-following model can be schematized as an oriented graph, where the kinematic information regarding the first vehicle is progressively transmitted downstream, to the other ones, while no information can travel upstream, from the following to the vehicle ahead.

As can be seen in Figure 3, it is possible to consider the flow of information originated by the leader, to study its propagation along the line of vehicles. Considering the notation for the vehicles expressed in the figure, vehicle n = 1th is the leader, n = 2th is the first of the followers and so on. The state of the leader (position and velocity) is continuously monitored by the vehicle 2nd, which suitably adapts its state, then the reaction of vehicle 2nd is evaluated by vehicle 3rd so that variations of the leader’s motion are transmitted along the line of vehicles.

It is now introduced the distance, i.e., the number of steps needed so that the information emanated from the leader reaches a certain vehicle n along the line. For instance, vehicle 2 receives the information directly from the leader so its distance can be considered equal to one, vehicle 3 is one step behind in the line, so the leader’s input is indirectly received after two steps, and the vehicle $n$ is at a distance $D_n=n-1$ from the leader. The average distance from the leader is now introduced, as follows:

$$\overline{D}=\frac{{{\displaystyle \sum }}_{n=2}^N{D}_n}{N-1}$$

(1)

where $D_n$ is the distance between the vehicle n to the leader. Equation (1) evaluates the mean distance from the leader for a line of vehicles and represents a global information regarding how fast the leader state is known to the other vehicles.

In the standard car-following model shown in Figure 3, Equation (1) becomes a simple sum of powers evaluated with the Faulhaber’s formula:

$$\overline{D}=\frac{{{\displaystyle \sum }}_{n=2}^N\left(n-1\right)}{N-1}=\frac{\left(N-1\right)N}{2\left(N-1\right)}=\frac{N}{2}$$

(2)

The result carried out by Equation (2) is rather intuitive, indicating that the average distance from the leader linearly increases with the total number N of vehicles within the queue.

At this point, the standard car following model is modified, introducing a few random connections, to study if and how the findings of the small-world theory modify the average distance from the leader.

With reference to Figure 4, given a few, randomly chosen, vehicles, each one is connected not only with the vehicle ahead but also with a vehicle s-steps ahead (for the sake of simplicity, it will be briefly referred as the distant vehicle in the following), beings a random positive integer as well. The information regarding the states of the two vehicles is weighted so that the bi-connected vehicle adapts its state accordingly. The information continues to travel only in one direction, but random links between distant vehicles are added to the standard connection between neighbors.

For the modified model, the average distance (1) depends on the random, long-range connections that are introduced. For example as in Figure 4, if the vehicle 6th receives long-range information from the third vehicle, its distance from the leader can be calculated in two different ways:

• Minimum distance from the leader $D_m$: it considers the shortest path that the leader’s information covers. For the vehicle 6th, the input arrives faster from vehicle 3rd than 5th, then the distance of vehicle 6th is considered as if it would follow the vehicle 3rd only, so $D_6$ = 3.
• Weighed distance from the leader $D_w$: the information deriving from the vehicle 3rd is joined to the one coming from the vehicle 5th. Set $a$ and $b$ the weight assigned to the vehicle ahead and the one of the distant vehicle, respectively, where $a + b = 1$, the distance from the leader is weighed accordingly. In the example examined, the distance from the leader is equal to $D_6=a\left(D_3+1\right)+b\left(D_5+1\right)$.

By using these two indicators, a preliminary yet important understanding of how, random, small-world like, connections modifies the average distance, is obtained. To this aim, the modified model is numerically implemented in Matlab© (2019b, MathWorks company, Natick, MA, USA), which depends only on N, the total number of vehicles, and P, the density of long-range interactions. If, for instance, N = 100 and P = 0.2, then the generator randomly chooses 20 vehicles and for each of them, randomly assigns the distant vehicle connection with which communicate. Each vehicle can communicate with any of the vehicles ahead, so the vehicle n can have a long-range connection with vehicles between [2; n − 2], the leader is indeed excluded and n − 1 is the standard connection between n and the vehicle ahead, which is always present, as shown in Figure 4.

Following the previous definitions, the distances $D_m\left(N,P\right)$ and $D_w\left(N,P\right)$ are numerically evaluated: in order to limit the dependence of the result from a specific set of random connections, for each selected value of the density P, a hundred different trials are computed, i.e., 100 different randomly connected systems are considered, then, the mean value of each distance is computed, i.e., ${\overline{D}}_m\left(N,P\right)={\displaystyle \sum }_{k=1}^{100}\frac{D_{mk}\left(N,P\right)}{100}$, and P is increased by 0.5%. The analysis continues for each value of P studied. The distances are then normalized with the mean distance value for the standard car-following model, i.e., $\frac{N}{2}$ from Equation (2).

Figure 5 shows the results of the numerical analysis, for which comments follow below:

(1)

The overall behavior of the system, regarding the transmission of the information, changes significantly with the introduction of P: the two distances have a strong decaying trend with respect to P.

(2)

Even for low values of P, the distance from the leader diminishes rapidly, regardless of the formula used to compute it. For instance, considering P = 0.1, e.g., the random connections are only 10% in respect to the standard model, the Minimum normalized distance is roughly 0.06 and the Weighed normalized distance is 0.14, which mean the distances for the small world model are much shorter than the mean distance for the standard model, being 6% and 14%, respectively.

(3)

The local connections remain almost unchanged since the information from the vehicle in front is still used from each vehicle even if few of them give it less importance, as imposed by the weight coefficient previously introduced.

The results above are rather general since they are obtained without studying the controller but just analyzing the information flow. These findings allow to conjecture that, for the modified models, a control imparted to the leader can be efficiently transmitted to the rest of the vehicles, or, in other words, the state of the whole system can be easily controlled, acting on the leader only, if a small-world network of following vehicles is employed.

3.1. Mathematical Introduction to the Standard Car Following Model

With reference to Figure 3, for the standard model each following vehicle, from 2 to N, modifies its state only in function of the state of the vehicle in front.

The information needed to implement a control law is the position and velocity, which can be measured somehow for the vehicle ahead, and with a characteristic delay time τ which can’t be neglected. Then the equations that govern the dynamics of the standard model are now presented and commented:

$${\ddot{x}}_n\left(t\right)={\beta }_n\left(t\right)\left({\dot{x}}_{n-1}\left(t-\tau \right)-{\dot{x}}_n\left(t-\tau \right)\right),n=2,3,\dots ,N$$

(3)

with:

$${\beta }_n\left(t\right)=\frac{\alpha {\left({\dot{x}}_n\left(t\right)\right)}^m}{{\left(x_{n-1}\left(t-\tau \right)-x_n\left(t-\tau \right)\right)}^l},\hspace{1em}\hspace{1em}\alpha >0,\hspace{1em}\hspace{1em}m,l\ge 0$$

(4)

where x is the position of the vehicle with respect to a fixed reference frame, t is the time variable and $\tau$ is the characteristic delay of the model, also called the reaction time. Equation (3) shows that the acceleration of each vehicle linearly depends on:

The relative velocity with respect to the vehicle ahead, delayed by the reaction time.

A coefficient $\beta$, which measures the sensitivity to the velocity of the vehicle, evaluated at the time t since the velocity can be measured onboard with a neglectable delay, with respect to the relative, delayed distance.

$\alpha$ is a positive coefficient of proportionality, $m,$ and $l$ are nonnegative constants if $m=l=0$ the model is linear.

Equation (3) is rewritten introducing relative variables, i.e., relative distance and relative velocity. The relative state variables of the system are defined as follows:

$$\begin{array}{l}{y}_n\left(t\right)+b=x_{n-1}\left(t\right)-x_n\left(t\right)\\ {\dot{y}}_n\left(t\right)=v_n\left(t\right)={\dot{x}}_{n-1}\left(t\right)-{\dot{x}}_n\left(t\right)\end{array}$$

(5)

where b is the distance between the vehicles in stationary conditions. Substituting the (5) in the (3) the following is obtained:

$${\ddot{x}}_n\left(t\right)={\beta }_n\left(t\right)\left(v_n\left(t-\tau \right)\right),\hspace{1em}\hspace{1em}\hspace{1em}n=2,3,\dots ,N$$

(6)

where

$${\beta }_n\left(t\right)=\frac{\alpha {\left({\dot{x}}_n\left(t\right)\right)}^m}{{\left(y_n\left(t-\tau \right)+b\right)}^l}$$

(7)

In order to remove the dependence from ${\dot{x}}_n\left(t\right)$, Equation (7) is written in terms of relative variables:

$$\begin{array}{c}{v}_2+v_3={\dot{x}}_1-{\dot{x}}_2+{\dot{x}}_2-{\dot{x}}_3={\dot{x}}_1-{\dot{x}}_3\\ v_2+v_3+v_4={\dot{x}}_1-{\dot{x}}_2+{\dot{x}}_2-{\dot{x}}_3+{\dot{x}}_3-{\dot{x}}_4={\dot{x}}_1-{\dot{x}}_4\\ ⋮\\ {\displaystyle {\displaystyle \sum }_{j=2}^n}{v}_j={\dot{x}}_1-{\dot{x}}_n\to {\dot{x}}_n={\dot{x}}_1-{\displaystyle {\displaystyle \sum }_{j=2}^n}{v}_j\end{array}$$

(8)

where, for the sake of notation, the time dependence (t) has been omitted. Using the (8) in the (7) β_n is written as:

$${\beta }_n\left(t\right)=\frac{\alpha {\left({\dot{x}}_1\left(t\right)-{{\displaystyle \sum }}_{j=2}^n{v}_j\left(t\right)\right)}^m}{{\left(y_n\left(t-\tau \right)+b\right)}^l},\hspace{1em}\hspace{1em}n=2,3,N,\alpha >0,m,n\ge 0$$

(9)

Taking the derivative for the second of the (5):

$${\dot{v}}_n\left(t\right)={\ddot{x}}_{n-1}\left(t\right)-{\ddot{x}}_n\left(t\right)$$

(10)

then substituting Equation (6) in the right-hand side (rhs) variables of Equation (10) holds:

$${\dot{v}}_n\left(t\right)={\beta }_{n-1}\left(t\right)v_{n-1}\left(t-\tau \right)-{\beta }_n\left(t\right)v_n\left(t-\tau \right),\hspace{1em}\hspace{1em}n=3,4,\dots ,N$$

(11)

From the second of the (5) and the (7) the state equations are obtained:

$$\{\begin{array}{c}{\dot{y}}_n\left(t\right)=v_n\left(t\right)\hspace{1em}\hspace{1em}n=2,3,\dots ,N\\ {\dot{v}}_2\left(t\right)={\ddot{x}}_1\left(t\right)-{\beta }_2\left(t\right)v_2\left(t-\tau \right)\\ {\dot{v}}_n\left(t\right)={\beta }_{n-1}\left(t\right)v_{n-1}\left(t-\tau \right)-{\beta }_n\left(t\right)v_n\left(t-\tau \right),n=3\cdots N\end{array}$$

(12)

where $\beta$ is given by Equation (9). The model expressed by Equation (12) can be modified to introduce the small-world dynamics.

3.2. Mathematical Introduction to the Small-World Model

The small-world model is now introduced, adding random connections on the rhs of Equation (12) as depicted in Figure 4. After some algebra, fully worked out in Appendix A, the state equations for the small world model are found:

$$\{\begin{array}{c}{\dot{y}}_n=v_n\hspace{1em}\hspace{1em}n=2,3,\dots ,N\\ {\dot{v}}_2\left(t\right)={\ddot{x}}_1\left(t\right)-{\beta }_{2,1}\left(t\right)v_2\left(t-\tau \right)\\ {\dot{v}}_3={\beta }_{2,1}{v}_2\left(t-\tau \right)-{\beta }_{3,1}{v}_3\left(t-\tau \right)\\ {\dot{v}}_n=a_{n-1}{\beta }_{n-1,1}{v}_{n-1}\left(t-\tau \right)+b_{n-1}{\beta }_{n-1,s}{\displaystyle {\displaystyle \sum }_{j=1}^s}{v}_{n-1-j+1}\left(t-\tau \right)+\\ -\left(a_n{\beta }_{n,1}{v}_n\left(t-\tau \right)+b_n{\beta }_{n,s}{\displaystyle {\displaystyle \sum }_{j=1}^s}{v}_{n-j+1}\left(t-\tau \right)\right),n=4,5,\dots ,N\end{array}$$

(13)

for the sake of notation, the time dependence (t) has been omitted, the new coefficients $\beta$ are given by Equations (A8) and s is a positive random integer that ranges within [2, n − 2].

Comparing Equation (12) with Equation (13), the modified model is rather like the standard one, since, under the small world hypothesis only a few vehicles have also long-range connections. Both models, the standard and the small-world are delayed differential models that need the initial condition of the state, $y_i\left(0\right),v_i\left(0\right)$, and the input of the leader to be solved.

4. Numerical Analysis and Discussion

The responses of the standard model expressed by Equation (12) and the small-world model expressed by the Equation (13) are now studied, putting the systems out of their stationary equilibrium positions. In both models, the stationary state is given by a constant velocity for each vehicle and a constant distance between the vehicles, equal to the parameter “$b$” in Equations (12) and (13). Since the aim of this study is comparing the performance of two models, all the parameters will remain constant through the numerical solutions for both models. Therefore, the assigned parameters are: $\alpha =\tau =l=m=1$ and $b=40$ (equilibrium distance in meters); the equilibrium velocity is assigned at $10/\mathrm{s}$, this state is altered by varying the input i.e., the leader’s velocity. Please note that the equilibrium distance of $40 \mathrm{m}$ is quite large for normal driving conditions and in respect of the selected speed: this is a first attempt made in order to avoid the problem of string instability [35,36], which is actually under an in-depth investigation and will be the object of a forthcoming paper, which will show how the small world model is able to ameliorate the problem. Anyhow, a second experiment will be also provided at the end of the section, considering a much shorter distance, of $20 \mathrm{m}$, which is closer to the usual safety distance among adjacent vehicles.

Numerical solutions of Equations (12) and (13) are obtained using Matlab’s DDE23 function to solve the delayed differential equations. To study and compare the numerical results, two different inputs are assigned to the leader:

A harmonic perturbation of the Leader’s velocity:

$${\dot{x}}_1=10+3\sin \left(\frac{\pi }{10}t\right)\raisebox{1ex}{$\mathrm{m}$}\!\left/ \!\raisebox{-1ex}{$\mathrm{s}$}\right.$$

(14)

A constant deceleration of the leader

$$\{\begin{array}{ll}{\dot{x}}_1=10-4t& for t\le 2s\\ {\dot{x}}_1=2& for t>2s\end{array}$$

(15)

The harmonic velocity, Equation (14), has a mean value equal to the equilibrium velocity, an amplitude that prevents negative velocities (the minimum velocity is $7 \mathrm{m}/\mathrm{s}$) and a period of $20 \mathrm{s}$ that is long enough to represent a slow variation of the velocity.

The fast deceleration (Equation (15)) instead, varies the velocity from $10 \mathrm{m}/\mathrm{s}$ to $2 \mathrm{m}/\mathrm{s}$ in just $2 \mathrm{s}$ to represent a rather intense braking maneuver. These two cases allow analyzing the behavior of the vehicles both in normal and emergency conditions: from a traffic point of view, the main goal of a car-following model is that the queue of vehicles is able to replicate the input imparted by the leader, which is the vehicle in front of the queue so that the entire line of vehicles almost move as a rigid body. A sinusoidal function appears to be the natural input to analyze the capability of the model to synchronize its motion with that of the leader. The breaking maneuver allows studying how fast the queue of the vehicles is able to react to a sudden and unsteady input imparted by the leader.

4.1. Analysis of the Standard Model

The sinusoidal input stated in Equation (14), is considered for a standard model with 500 vehicles. Please note that the selection of a rather large number of cars is required in order to have a significant number of long-range connected vehicles along the queue. Indeed, the small-world theory has been originally introduced in social and complex networks, where the number of nodes is usually huge and the theory relies on a very small density of long-range connections. The velocity and relative distance from the vehicle ahead for the first 7 vehicles that follow the leader are plotted in Figure 6: these curves are characterized by sinusoidal trends, whose amplitudes diminish with the distance from the leader (considering the distance as the number of vehicles between the vehicle and the leader), and progressively become out of phase with the leader motion.

The state of each vehicle only depends on the motion of the vehicle ahead and starts following its state after a time delay equal to the delay $\tau$ that appears in the differential equations Equation (12). This is clearly visible in Figure 6 where each curve moves from the initial value with a constant delay from the preceding. For each vehicle, the mean value of the velocity is always equal to the mean value of the leader’s velocity, while the amplitude of oscillations decays rapidly from one vehicle to the next, because of the stability of the model as it is explained in Appendix B.

With reference to Equation (12) the coefficient $\beta$ plays the role of damping parameter, which increases going down the line of vehicles. As shown in Figure 7, farther vehicles show indeed a transient behavior, characterized by a small oscillation, close to $1\%$ of the leader’s amplitude, followed by stationary oscillations with very small amplitudes. The first oscillation of velocity shown in Figure 7 is indeed characterized by a peak velocity, due to the impulsive application of the load.

To analyze how the peak changes along the queue of vehicle, the maximum value of the velocity and the time at which takes place are shown in Figure 8 (the plot shows only the first 200 vehicles, over a total of 500, because the peak intensity quickly becomes negligible). The time at which the peak takes place linearly increases with the distance from the leader, the slope of the curve in Figure 8 is related to the characteristic time delay τ. The magnitude of the peak decays rapidly after the first vehicles, so that the harmonic perturbation emanated from the leader motion becomes, quickly, no longer detectable.

With reference to Figure 9, the motion of the barycenter of the whole queue of vehicles is almost constant, while the motion of the leader is oscillatory: as long as the number of vehicles increases, the oscillations of the barycenter becomes smaller and smaller until become negligible. For the standard model, the motion of the barycenter is related to leader motion only on average, i.e., same mean value, while it is not able to highlight the harmonic perturbation, i.e., the amplitude of oscillations is negligible.

Considering now the constant deceleration input imparted by the leader defined by Equation (15), for a set of 100 vehicles. As shown in Figure 10, the standard model responds to the braking maneuver in the most intuitive way: each vehicle starts breaking, following the vehicle ahead, after a time delay equal to the characteristic delay $\tau$. The deceleration intensity decreases from one vehicle to the next since the stability of the model damps the original, transient, input emanated from the leader. As a result, the barycenter has a much smaller deceleration with respect to the one of the leader: the queue of 100 vehicles reaches indeed the leader’s velocity after $450 \mathrm{s}$.

4.2. Analysis of the Small-World Model

Even if the small-world model has a random component that makes each realization unique, it has been conjectured that the system response mainly depends on the density of random long-range connections. This paragraph shows how, even for low values of the density of long-range interactions, the platoon manages to reach a swarm behavior.

Keeping all the parameters unchanged with regard to the standard model ($\alpha =\tau =l=m=1$ and $b=40$) a density P = 5% of random long-range interactions is assigned to a platoon of 500 vehicles. Therefore, 475 vehicles will follow the same law as the ones in the standard model and the remaining 25, randomly selected along with the platoon, have two inputs: the one from the preceding vehicle and one from a distant vehicle ahead.

In Figure 11 the response of the modified platoon to the harmonic input defined in Equation (14) is represented. The first four vehicles after the leader show the same trend already encountered in Figure 9 for the standard model: this is due to the fact that, in this realization, the first long-range connection involves the fifth follower. Then the velocities of the following vehicles are condensed in a cluster, which is characterized by the same, smaller and roughly in phase, oscillations. Even if only a few vehicles have a long-range interaction, nearly all the vehicles in the platoon reach a nearly synchronized state, in less than 15 s after the application of the perturbation, this property will be further appreciated with the comparison between the barycenter’s velocity for the standard and small-world model, carried out in Section 4.3 and shown in Figure 19.

The barycenter of the platoon is indeed clearly affected by the input of the leader, this shows that the small-world theory applied to a platoon of vehicles has the same effect as in any other field where it has been studied before: it allows the information to spread rapidly along with all the population. It should be noticed that the barycenter of the platoon in Figure 19 is roughly in the antiphase with respect to the leader motion.

The effect of the long-range interaction is even more evident for the transient input imparted by the leader, i.e., the deceleration introduced in Equation (15). To compare the standard and the small-world models, the platoon subject to the breaking is composed of the same number of vehicles, i.e., N = 100. In Figure 12 the 100 vehicles present 10% of random long-range connections that allow the platoon to follow the input of the leader after few seconds: the long-range interactions allow the farther vehicles to respond indeed to the leader’s input after just a few seconds.

Accordingly to the comments at the beginning of the section, the same experiments are repeated considering a much shorter distance, of $20 \mathrm{m}$, among adjacent vehicles, which is closer to the usual safety distance: results are shown in Figure 13, Figure 14, Figure 15 and Figure 16. The figures show that, even in this case, the small world model still preserves the outlined features and outperforms the standard one. In case of the harmonic perturbation, the velocities of the majority of vehicles for the modified model are still condensed in a cluster, characterized by the same, small and in phase, oscillations, and the barycenter of the platoon is also affected by the input of the leader, as shown in Figure 15. The synchronization effect is observed also for the braking manoeuvre, since the majority of vehicles still respond to the leader’s input after just a few seconds, as shown in Figure 15.

4.3. Comparison between the Two Models

Figure 17 shows a comparison between the time evolution of the standard car-following and the small world models, considering the braking maneuver of the leader stated by Equation (15); please note that in the modified model the first vehicle that has a long-range connection is the 13th linked with vehicle 10th. As shown in Figure 17a, at the time 0 s both models have the same spatial configurations and the leader starts braking. As time unfolds, the small world model allows an earlier braking maneuver for the upcoming vehicles. In fact, a misalignment, between the standard and the modified model, is observed for the 14th vehicle, as shown in Figure 17b. The misalignment becomes larger and larger along with the queue of vehicles, as shown in Figure 17c, making the group velocity much shorter in respect of the one of the standard model.

Even if the two models are rather similar, the response of the platoon to the leader’s input is substantially different. The leader’s information spreads along with the platoon in two different ways as shown in Figure 18. Regarding the distance from the leader defined in Section 3, for the standard model the distance linearly increases with the vehicle number, because $D_n=n-1$. For the small world models, the previous law holds between two consecutive long-range connections: the distance linearly increases with n up to the vehicle subjected to long-range connection, then the distance drop to a much lower value and then start to rise again, up to the next vehicle with the long-range connection. Regarding the average distance from the leader, the one of the small-world model presented in Figure 11 is roughly 38, which is much smaller than the one of the standard model, $D=N/2=250$.

The greater ability of the small-world model to spread the leader’s information gives to the platoon the ability to follow the leader’s input way better than the standard model as shown in Figure 19 and Figure 20. Figure 19 shows the comparison between the Barycenter’s velocity for the standard and the small world models, subjected to the sinusoidal perturbation of the leader stated in Equation (14). For the standard model, the barycenter’s velocity remains almost constant and does not highlight the harmonic perturbation imparted by the leader. For the small-world model, the amplitude of oscillations is much higher, as shown in Figure 11, many vehicles have synchronized oscillation, of the same amplitude: this swarming behavior has been obtained introducing only a 5% of long-range connections.

Regarding the braking maneuver introduced in Equation (15), the comparison in Figure 20 shows that the small-world model is much more reactive than the standard one. The random long-range interactions lead to a swarm behavior, which can hardly be obtained by a purposely designed controller, being able to follow the input given in a quarter of the time needed from the standard model. The small-world model is much more reactive and able to spread the leader’s information: this is due to the different patterns of communication, which affects the stability of the model as well, as it is shown in Appendix B.

4.4. Influence of the Random Connections on the Small-World Model

Each random realization of a small world model gives to the swarm a different ability to follow the leader’s input, with respect to the actual set of long-range connections. In order to evaluate the statistical validity of the properties highlighted in Section 4.2 and Section 4.3 and to further understand how the density of long-range connections may alter the motion of the platoon, an ensemble of 100 trials is considered for each density value. In particular, for the sinusoidal input introduced in Equation (14), where the leader velocity is characterized by oscillations of amplitude 3 m/s, the numerical experiment is performed with N = 500 and P that ranges within the interval [1,10] % with a step of size 1%, once P is fixed 100 randomly connected small-world models are considered, then P is increased and the analysis is repeated.

For a certain P, the peak velocity of the barycenter changes with each samples of the statistical ensemble: the non-dimensional barycenter’s velocity of the platoon, normalized with the amplitude of oscillations of the velocity of the leader, i.e., $3 \mathrm{m}/\mathrm{s}$, is then used as an indicator of the system sensitivity to the actual placement of the long-range connections, results are shown in Figure 21 and Figure 22. With reference to Figure 21, for low values of $P$, i.e.,$P<4\%$, each boxplot is small, the first, the second (median) and the third quartile are indeed packed and close to zero: most of the random samples have similar motions and the swarm behavior is not evident since the perturbation imparted by the leader has a low amplitude along the queue of vehicles. However, a few samples, i.e., the outliers marked with red crosses, show larger amplitudes, which means that even with very low values of $P$ is possible, even if unlikely, to have a swarm behavior for a certain combination of long-range connections.

This can be better appreciated from Figure 22, where the number of samples whose nondimensional barycenter’s velocity is greater than 10% (here briefly indicated with threshold level TL) is represented along the ordinate axes: up to $P=4\%$ less than $8\%$ of the samples go beyond TL.

For low to mid values of P, the median is very close to the first quartile, which means the samples are characterized by lower amplitudes. For the highest values of P, the median gets higher and further form the first quartile, so a collective behavior of the platoon is very likely to be observed among the vast majority of the samples. For values of P of the order of 6 ÷ 7%, the boxplots get indeed significantly larger, the quartiles not only get farther from one another, but also the median significantly increase its value, as shown in Figure 21: it means that the barycenter’s velocity of most of the small world samples is able to follow the leader’s input. Figure 22 shows that for P > 6% the number of samples that goes beyond TL suddenly grows increases from 10 to 20%.

4.5. Robustness of the Small-World Model

The robustness of the small world behavior can be analyzed evaluating the effects of a sudden interruption of a long-distance connection, for the model studied in Figure 11. In Figure 23 the vehicle 21 is subjected to a long-range interaction with vehicle 8 up to 100 s, then the connection is broken.

Figure 23 shows that the velocity of the vehicle 21 undergoes only a small fluctuation, due to the connection interruption.

However, the whole system keeps on oscillating in the same fashion, as shown in Figure 24: the large cluster of vehicles that oscillates roughly in-phase and the barycenter’s velocity are not appreciably affected by the connection broken.

5. Conclusions

In this paper, a car-following model has been examined. Due to the stability of the standard model, a large platoon of vehicles cannot be controlled simply altering the state of the leader vehicle and a sophisticated controller is generally required. In this regard, the small world theory has been introduced to analyze, if and how it is able to produce a collective behavior also in the case of vehicle platoons.

This work has shown that it is possible to deeply modify the behavior of a line of vehicles introducing a few random long-range connections: a swarm behavior is indeed achieved for a density of long-range interaction even smaller than 6%. The platoon exhibits a swarm behavior that makes the vehicles act, together, almost like a rigid body, able to quickly react to input commands imparted by the leader, as a sudden braking maneuver, i.e., the small-word model is able to reduce the breaking time of the platoon by a factor of 4, or to a cyclical perturbations of the velocity.

The properties of the small-world model have been also analyzed from a theoretical point of view, studying the stability properties of the standard and the small world linearized models. It was found that the small world model modifies the reactiveness and the stability of the original model: the eigenvalues corresponding to the vehicles subjected to the long-range interaction show smaller absolute values and the farther the long-range interaction the closer to zero the eigenvalue. The behavior of the platoon becomes indeed more reactive to the leader’s input with respect to the standard model.

The paper represents, to the authors’ knowledge, a first successful application of the theory, originally developed in the field of social networks, which has shown a rather effective way to regularize the traffic flow with a very small control effort: it was shown indeed that a swarm behavior can be achieved controlling only the leader vehicle if a few random, long-range connections, are considered. The modified models exhibit indeed properties of high synchronization and it is also robust to communication failures.

Thanks to these promising results, the authors are carrying out an effective control strategy, which relies on the small world theory and that requires a very small control effort. This will be the topic of a forthcoming paper, where the authors are investigating the main pros and cons provided by the small world model with respect to a queue of vehicles controlled via other algorithms already developed by the authors that use optimal control [15,43,44,45,46].