Models and Methods for Intelligent Highway Routing of Human-Driven and Connected-and-Automated Vehicles

Abstract

Connected and automated vehicles (CAVs) have seen a rapid surge in interest over the past few years. A lot of focus is being placed on improving the efficiency and robustness of transportation systems by leveraging the sensors and capabilities of CAVs. However, the integration of CAVs into existing traffic infrastructure would give rise to certain issues that must be addressed before the CAVs can be seen ubiquitously on public roads. Since the highway networks are considered permanent investments that are expensive to build and maintain, the priority is to improve the efficiency of the current traffic system. This chapter explores the integration of two of the most common traffic management strategies, namely, ramp metering (RM) and route guidance (RG), into existing highway networks with human-driven vehicles (HDVs). The introduction of CAVs to public roads will engender issues pertaining to safe interactions between CAVs and HDVs. The later part of the chapter addresses the specific problems of improving highway on-ramp merging efficiency by optimally coordinating CAVs. The chapter concludes by presenting a scenario that requires an explicit consideration of interactions between HDVs and CAVs.

1. Introduction

The ultimate goal of automating the driving process is to improve safety by reducing accidents caused by human errors. If all vehicles in a network are human–driven, the efficiency of traffic networks can be improved by the control of traffic signal lights and the routes that drivers can choose. Studying the literature on freeway traffic control for HDVs demonstrate that the integration of traffic control strategies such as ramp metering (RM) and route guidance (RG) improve the network performance in regards to travel time, travel distance, throughput and emissions.

Moreover, it seems unrealistic that all the HDVs will suddenly be replaced by the AVs in the near future. Rather, what seems more plausible is that the AVs will be introduced onto the roads in the presence of the HDVs. Therefore, there is a need to consider cases where it becomes necessary to model the interactions between AVs and HDVs. Delays caused at on-ramps and off-ramps are some of the major contributors to overall system efficiency degradation. In addition to the increase of congestion in the merge lane and outer freeway lanes, merging lanes can have an overflow effect which causes the entire freeway to become congested. However, with the advent of CAVs, a lot more information has been made available for improving this overall process.

Moving on to mixed–autonomy highway networks, as a specific example of the interaction between HDVs and CAVs, the overtaking behavior performed by a CAV is chosen as the target driving behavior for the last section of this chapter. The reason for this choice is that it is one of the more challenging driving behaviors when compared to car following and lane changing as it encompasses the combination of these behaviors.

This chapter is organized as follows: Section 2 reviews the integration of RM and RG, that have shown significant improvements on different control measures for highway networks with HDVs. Section 3 addresses the specific problem of improving freeway on-ramp merging efficiency by optimally coordinating CAVs. Finally, Section 4 explores the overtaking behavior accomplished by a CAV in the presence of HDVs.

2. Integration of ramp metering and route guidance for HDVs

This section will focus on providing a review on the combined RM and RG control as two of the most common traffic control management techniques. To do so, first, a review on traffic flow models will be provided and then, the most common RM and RG strategies will be explained, respectively. At the end of this section, a review on the studies with the focus on the integration of RM and RG will be presented.

2.1 Traffic flow models

Traffic flow models can be categorized into first order and second order models. The most frequently used models are first order models, such as Lighthill-Whitham-Richards (LWR) model [1], which is a continuous model, and the cell-transmission model (CTM) [2], which is a discretized version of the LWR model. The second-order traffic flow models, besides considering the dynamics of the traffic density, introduce a dynamic equation for the mean velocity. The most famous second order model is the Modèle d’Écoulement de Trafic sur Autoroute NETworks (METANET) model [3, 4]. In this section, a review on the CTM and METANET model, as the two most used discrete traffic flow models in the literature, will be provided. The notations adopted in this section are adopted from [5]. Tables 1 and 2 describe the model variables and parameters of these two models with their symbols, definitions, and units.

Symbol	Description	Unit/Range
$T$	Sampling time	$\left[h\right]$
$N$	Number of cells	int
$i$	Cell index	$i=\left\{1,\dots ,N\right\}$
$K$	Time horizon	int
$k$	Time index	$k=\left\{0,\dots ,K-1\right\}$
$L$	Length of each cell	$\left[\mathit{km}\right]$
$v_i$	Free-flow speed	$\left[\mathit{km}/h\right]$
${\omega }_i$	Congestion wave speed	$\left[\mathit{km}/h\right]$
$q_i^{\mathit{max}}$	Cell capacity (Maximum flow rate)	$\left[\mathit{veh}/h\right]$
${\rho }_i^{\mathit{max}}$	Jam density	$\left[\mathit{veh}/\mathit{km}\right]$
${\rho }_i^{\mathit{cr}}$	Critical density	$\left[\mathit{veh}/\mathit{km}\right]$
$l_i^{\mathit{max}}$	Maximum on-ramp queue length	$\left[\mathit{veh}\right]$
$r_i^{C,\mathit{max}}$	Maximum ramp metering rate	$\left[\mathit{veh}/h\right]$
${\rho }_i\left(k\right)$	Traffic density	$\left[\mathit{veh}/\mathit{km}\right]$
${\mathrm{\Theta }}_i^{+}\left(k\right)$	Total flow entering cell $i$	$\left[\mathit{veh}/h\right]$
${\mathrm{\Theta }}_i^{-}\left(k\right)$	Total flow exiting cell $i$	$\left[\mathit{veh}/h\right]$
${\varphi }_i\left(k\right)$	Mainstream flow entering cell $i$ from cell $i-1$	$\left[\mathit{veh}/h\right]$
$r_i\left(k\right)$	Flow entering cell $i$ from its on-ramp	$\left[\mathit{veh}/h\right]$
$s_i\left(k\right)$	Flow exiting cell $i$ through its off-ramp	$\left[\mathit{veh}/h\right]$
${\beta }_i\left(k\right)$	Split ratio	$\in \left[0,1\right]$
$l_i\left(k\right)$	Queue length in the on-ramp	$\left[\mathit{veh}\right]$
$d_i\left(k\right)$	Flow accessing the on-ramp	$\left[\mathit{veh}/h\right]$
$r_i^C\left(k\right)$	Ramp metering control variable	$\left[\mathit{veh}/h\right]$

Table 1.

CTM model variables and parameters of cell i during interval [kT,(k+1)T).

Symbol	Description	Unit/Range
$T$	Sampling time	$\left[h\right]$
$K$	Time horizon	int
$k$	Time index	$k=\left\{0,\dots ,K-1\right\}$
$M$	Number of mainline links	int
$m$	Mainline link index	$m=\left\{1,\dots ,M\right\}$
$N_m$	Number of sections of mainline link $m$	int
$i$	Section index	$i=\left\{1,\dots ,N_m\right\}$
$O$	Number of origin links	int
$o$	Origin link index	$i=\left\{1,\dots ,O\right\}$
$L_m$	Length of each mainline link $m$	$\left[\mathit{km}\right]$
${\lambda }_m$	Lane numbers of each mainline link $m$	int
$O_n$	Set of exiting mainline links from node $n$	-
$I_n$	Set of entering mainline links to node $n$	-
${\overline{I}}_n$	Set of entering origin links to node $n$	-
$J_m$	Set of destinations reachable from mainline link $m$	-
${\overline{J}}_o$	Set of destinations reachable from origin link $o$	-
${\stackrel{̿}{J}}_n$	Set of destinations reachable from node $n$	-
${\nu }_{m,i}^f$	Free-flow speed in section $i$ of link $m$	$\left[\mathit{km}/h\right]$
${\rho }_m^{\mathit{cr}}$	Critical density	$\left[\mathit{veh}/\mathit{km}\right]$
${\rho }_m^{\mathit{max}}$	Jam density	$\left[\mathit{veh}/\mathit{km}\right]$
$q_o^{\mathit{max}}$	Capacity of origin link $o$	$\left[\mathit{veh}/h\right]$
$\tau$	Model parameter	-
$\eta$	Model parameter	-
$\chi$	Model parameter	-
$\varphi$	Model parameter	-
$a_m$	Model parameter	-
${\delta }_{\mathit{on}}$	Model parameter	-
${\rho }_{m,i,j}\left(k\right)$	Partial density	$\left[\mathit{veh}/\mathit{km}\right]$
${\rho }_{m,i}\left(k\right)$	Total density	$\left[\mathit{veh}/\mathit{km}\right]$
${\nu }_{m,i}\left(k\right)$	Mean traffic speed	$\left[\mathit{km}/h\right]$
$q_{m,i}\left(k\right)$	Traffic flow leaving section $i$ of link $m$	$\left[\mathit{veh}/h\right]$
${\gamma }_{m,i,j}\left(k\right)$	Composition rate	$\in \left[0,1\right]$
$d_{o,j}\left(k\right)$	Partial origin demand at origin link $o$	$\left[\mathit{veh}/h\right]$
$d_o\left(k\right)$	Total origin demand at origin link $o$	$\left[\mathit{veh}/h\right]$
$l_{o,j}\left(k\right)$	Partial queue length at origin link $o$	$\left[\mathit{veh}\right]$
$l_o\left(k\right)$	Total queue length at origin link $o$	$\left[\mathit{veh}\right]$
${\gamma }_{o,j}\left(k\right)$	Composition rate	$\in \left[0,1\right]$
${\theta }_{o,j}\left(k\right)$	Portion of demand originating in origin link $o$	$\in \left[0,1\right]$
$q_o\left(k\right)$	Total traffic volume leaving origin link $o$	$\left[\mathit{veh}/h\right]$
$r_o^C\left(k\right)$	Ramp metering control variable	$\left[\mathit{veh}/h\right]$
$Q_{n,j}\left(k\right)$	Flow entering node $n$	$\left[\mathit{veh}/h\right]$
${\beta }_{m,n,j}\left(k\right)$	Split ratio	$\in \left[0,1\right]$

Table 2.

METANET model variables and parameters of mainline link m, section i, node n, origin link o, destination j during interval [kT,(k+1)T).

2.1.1 The cell transmission model (CTM)

The CTM was first developed by Daganzo [2] in 1992 and then, through out the following years, many other extensions of it were developed. The following version is the original version of the CTM with some minor modifications from [6] and the notations are borrowed from [5]. The CTM is characterised by the following equations:

$${\rho }_i\left(k+1\right)={\rho }_i\left(k\right)+\frac{T}{L}\left({\mathrm{\Phi }}_i^{+}\left(k\right)-{\mathrm{\Phi }}_i^{-}\left(k\right)\right)$$E1

$${\mathrm{\Phi }}_i^{+}\left(k\right)={\varphi }_i\left(k\right)+r_i\left(k\right)$$E2

$${\mathrm{\Phi }}_i^{-}\left(k\right)={\varphi }_{i+1}\left(k\right)+s_i\left(k\right)$$E3

$$s_i\left(k\right)=\frac{{\beta }_i\left(k\right)}{1-{\beta }_i\left(k\right)}{\varphi }_{i+1}\left(k\right)$$E4

The dynamic equation of the on-ramp queue length is:

$$l_i\left(k+1\right)=l_i\left(k\right)+T\left(d_i\left(k\right)-r_i\left(k\right)\right).$$E5

The mainline flows and on-ramp flows are:

$${\varphi }_i\left(k\right)=min\left\{\left(1,-,{\beta }_{i-1},\left(k\right)\right)v_{i-1}\left({\rho }_{i-1}\left(k\right)+r_{i-1}\left(k\right)\right),w_i\left({\rho }_i^{\mathit{max}}-{\rho }_i\left(k\right)-r_i\left(k\right)\right),q_i^{\mathit{max}}\right\}$$E6

$$r_i\left(k\right)=\left\{\begin{array}{l}min\left\{l_i\left(k\right)+d_i\left(k\right),{\rho }_i^{\mathit{max}}-{\rho }_i\left(k\right)\right\}\text{Uncontrolled}\mathrm{On}-\text{Ramps}\\ min\left\{l_i\left(k\right)+d_i\left(k\right),{\rho }_i^{\mathit{max}}-{\rho }_i\left(k\right),r_i^{C,\mathit{max}}\right\}\text{Controlled}\mathrm{On}-\text{Ramps}\end{array}\right.$$E7

Metering rate variables $r_i^{\mathrm{C}}\left(k\right)$ come from the RM control law which will be mentioned in detail in Section 2.2. All variables are bounded between zero and their maximum possible value.

Many extensions of the original CTM have been proposed in the literature in the last two decades. The CTM in a mixed-integer linear form [7], the CTM including capacity drop phenomena [8, 9], the CTM for a freeway network [10], the asymmetric CTM [6], the link-node CTM [11], and the variable-length CTM [12] are some of these extended versions. Although these models have been proposed in different years and are suitable for different networks and applications, the original CTM [2] is the underlying model in all of them and it proves how powerful the original CTM is.

2.1.2 The METANET model

The METANET model presented here is an improved version [4] of the original that was first presented in [3]. However, the notation has been adopted from [5] in order to agree with the other notations of this section.

Freeway Links

$${\rho }_{m,i,j}\left(k+1\right)={\rho }_{m,i,j}\left(k\right)+\frac{T}{L_m{\lambda }_m}\left[{\gamma }_{m,i-1,j}\left(k\right)q_{m,i-1}\left(k\right)-{\gamma }_{m,i,j}\left(k\right)q_{m,i}\left(k\right)\right]$$E8

$${\rho }_{m,i}\left(k\right)=\sum _{j\in J_m}{\rho }_{m,i,j}\left(k\right)$$E9

$${\gamma }_{m,i,j}\left(k\right)=\frac{{\rho }_{m,i,j}\left(k\right)}{{\rho }_{m,i}\left(k\right)}$$E10

$$\begin{array}{l}{\nu }_{m,i}\left(k+1\right)={\nu }_{m,i}\left(k\right)+\frac{T}{\tau }\left[V\left({\rho }_{m,i}\left(k\right)\right)-{\nu }_{m,i}\left(k\right)\right]+\frac{T}{L_m}{\nu }_{m,i}\left(k\right)\left[{\nu }_{m,i-1}\left(k\right)-{\nu }_{m,i}\left(k\right)\right]\\ -\frac{{\mathit{\nu }}^{\prime }\mathit{T}\left[{\rho }_{m,i+1}\left(k\right)-{\rho }_{m,i}\left(k\right)\right]}{\tau L_m\left[{\rho }_{m,i}\left(k\right)+\chi \right]}\end{array}$$E11

$$q_{m,i}\left(k\right)={\rho }_{m,i}\left(k\right){\nu }_{m,i}\left(k\right){\lambda }_m$$E12

$$V\left({\rho }_{m,i}\left(k\right)\right)={\nu }_m^{f}exp\left[-\frac{1}{a_m}{\left(\frac{{\rho }_{m,i}\left(k\right)}{{\rho }_m^{\mathit{cr}}}\right)}^{a_m}\right]$$E13

The speed reduction caused by merging phenomena near on-ramps (possible additional term to Eq. (11)):

$$-{\delta }_{\mathit{on}}T\frac{{\nu }_{m,1}\left(k\right)q_o\left(k\right)}{L_m{\lambda }_m\left[{\rho }_{m,1}\left(k\right)+\chi \right]}$$E14

The speed reduction due to weaving phenomena in case of lane reductions in the mainstream (possible additional term to Eq. (11)):

$$-\mathit{\varphi T}\mathrm{\Delta }\lambda \frac{{\nu }_{m,N_m}{\left(k\right)}^2{\rho }_{m,N_m}\left(k\right)}{L_m{\lambda }_m{\rho }_m^{\mathit{cr}}}$$E15

The virtual downstream density at the end of the link (for node $n$ at the end of link $m$ with more than one outgoing link):

$${\rho }_{m,N_m+1}\left(k\right)=\frac{{\sum }_{\mu \in O_n}{\rho }_{\mu ,1}{\left(k\right)}^2}{{\sum }_{\mu \in O_n}{\rho }_{\mu ,1}\left(k\right)}$$E16

The virtual upstream speed at the beginning of the link (for node $n$ at the beginning of link $m$ with more than one entering freeway link):

$${\nu }_{m,0}\left(k\right)=\frac{{\sum }_{\mu \in I_n}{\nu }_{\mu ,N_{\mu }}\left(k\right)q_{\mu ,N_{\mu }}\left(k\right)}{{\sum }_{\mu \in I_n}{q}_{\mu ,N_{\mu }}\left(k\right)}$$E17

Origin links

$$l_{o,j}\left(k+1\right)=l_{o,j}\left(k\right)+T\left[d_{o,j}\left(k\right)-{\gamma }_{o,j}\left(k\right)q_o\left(k\right)\right]$$E18

$$l_o\left(k\right)=\sum _{j\in {\overline{J}}_o}{l}_{o,j}\left(k\right)$$E19

$${\gamma }_{o,j}\left(k\right)=\frac{l_{o,j}\left(k\right)}{l_o\left(k\right)}$$E20

$$d_{o,j}\left(k\right)={\theta }_{o,j}\left(k\right)d_o\left(k\right)$$E21

For uncontrolled on-ramps:

$$q_o\left(k\right)=min\left\{d_o\left(k\right)+\frac{l_o\left(k\right)}{T},q_o^{\mathit{max}},q_o^{\mathit{max}}\frac{{\rho }_m^{\mathit{max}}-{\rho }_{m,1}\left(k\right)}{{\rho }_m^{\mathit{max}}-{\rho }_m^{\mathit{cr}}}\right\}$$E22

For controlled on-ramps:

$$q_o\left(k\right)=min\left\{d_o\left(k\right)+\frac{l_o\left(k\right)}{T},q_o^{\mathit{max}},r_o^C\left(k\right),q_o^{\mathit{max}}\frac{{\rho }_m^{\mathit{max}}-{\rho }_{m,1}\left(k\right)}{{\rho }_m^{\mathit{max}}-{\rho }_m^{\mathit{cr}}}\right\}$$E23

where $r_o^C\left(k\right)$ come from the RM control law which will be mentioned in detail in Section 2.2.

Nodes

$$Q_{n,j}\left(k\right)=\sum _{\mu \in I_n}{q}_{\mu ,N_{\mu }}\left(k\right){\gamma }_{\mu ,N_{\mu ,j}}\left(k\right)+\sum _{o\in {\overline{I}}_n}{q}_o\left(k\right){\gamma }_{o,j}\left(k\right)$$E24

$$q_{m,0}\left(k\right)=\sum _{j\in J_m}{\beta }_{m,n,j}\left(k\right)Q_{n,j}\left(k\right)$$E25

$${\gamma }_{m,0,j}\left(k\right)=\frac{{\beta }_{m,n,j}\left(k\right)Q_{n,j}\left(k\right)}{q_{m,0}\left(k\right)}$$E26

In presence of RG control, the splitting rates become the control variables and are calculated based on the RG control law. It will be mentioned in detail in Section 2.3.

Few research studies have developed different versions of the METANET model due to the complexity and non-linearity of the second-order models. However, the extensions of the METANET for a freeway network [13], and the multi-class METANET both for a freeway stretch [14] and for a freeway network [15] are examples of the extensions of this second-order traffic model developed in the recent years.

Both the first-order and second-order models are capable of developing the evolution of traffic flow in both urban and non-urban network. However, to highlight their difference, it is necessary to emphasize that first order models focus on the evolution of the density while the second-order traffic flow models, besides considering the dynamics of the traffic density, explicitly introduce a dynamic equation for the mean speed. Second order models have the distinct advantage over first order models that they can reproduce the capacity drop, which is the observed difference between the freeway capacity and the queue discharge rate. First order models, because they do not capture this phenomenon, are incapable of exploiting the benefits of increasing bottleneck flow. They can only reduce travel time by increasing off-ramp flow. The obvious disadvantage to second order models is that they lead to more complex optimization problems.

The focus of the rest of this section will be on ramp metering and route guidance control schemes as two of the most famous traffic management techniques.

2.2 Ramp metering

Ramp metering is achieved by placing traffic signals at on-ramps to control the flow rate at which vehicles enter the freeway. The ramp metering controller computes the metering rate to be applied. Ramp metering has various goals [16]: to improve or remove congestion, to alleviate freeway flow, traffic safety and air quality, to reduce total travel time and the number of peak-period accidents, to regulate the input demand of the freeway system so that a truly operationally balanced corridor system is achieved. Although the ramp metering provides many advantages, at the same time, it can have disadvantages too. The following are two of the most plausible ones [5]: (1) drivers may use parallel routes to avoid ramp meters which may lead to increased travel time and distance, (2) it can shift the traffic congestion from one location to another.

Ramp metering control strategies can be classified in the following categories [16]: (1) local system where the control is applied to a single on-ramp, (2) coordinated system where the control is applied to a group of on-ramps, considering the traffic conditions of the whole network, (3) integrated system where a combination of ramp metering, signal timing, and route guidance is applied as the control system. Also, from another point of view, there are two types of RM control schemes [16]: (1) pre-timed or isolated where metering rates are fixed and pre-defined, (2) traffic-responsive control where real time freeway measurements are used to determine the control variables.

A classification of ramp metering algorithms based on a study by Papageorgiou and Kotsialos [17] is presented in Figure 1. Fixed time metering is the simplest strategy which is usually adjusted based on historical data and applied during particular times of day. Reactive ramp metering techniques are based on real time traffic metrics. Local ramp metering uses traffic measures collected form the ramp vicinity. Demand-capacity, and occupancy-based strategies allow as much traffic inflow as possible to reach the freeway capacity. ALINEA and PI-AlINEA offer a more complex and more responsive strategy that, unlike capacity and occupancy strategies, generates smoother responses towards changes in metrics. Multi-variable regulator strategies perform the same as local strategies, but more comprehensively and independently on a set of ramps and usually outperform local strategies. METALINE can be viewed as a more general and extended form of ALINEA. Nonlinear optimal control strategy considers local traffic parameters and metrics as well as nonlinear traffic flow dynamics, incidents, and demand predictions in a freeway network and outputs a consistent control strategy. Knowledge-based control systems are developed based on historical data and human expertise. Integrated freeway network traffic control is a more general approach to nonlinear control that extends application of optimal control strategies to all forms of freeway traffic control. In case of knowledge based systems, inability to learn and adapt to temporal evolution of the system being controlled can be an issue, so knowledge based systems need to be periodically updated to remain efficient. Artificial intelligence and machine learning approaches like reinforcement learning (RL) and artificial neural networks (ANN) are new techniques being implemented recently for RM control [18].

Figure 1.

Ramp metering algorithms classification.

Two of the most common ramp metering strategies are described in the following. Here, the flow that can enter section $i$ of a freeway from the on-ramp during time interval $\left[\mathit{kT},\left(k+1\right)T\right)$ is shown by $r_i^{\mathrm{C}}\left(k\right)$ where $k$ is the time index and T is the sampling time.

2.2.1 ALINEA

ALINEA [19] is an I-type controller in which the metering rate is given by

$$r_i^{\mathrm{C}}\left(k\right)=r_i^{\mathrm{C}}\left(k-1\right)-K_R\left[{\rho }_i^{\ast }-{\rho }_i^{\mathit{\text{down}}}\left(k\right)\right]$$E27

where ${\rho }_i^{\mathit{\text{down}}}\left(k\right)$ is the density measured downstream the on-ramp, ${\rho }_i^{\ast }$ is a set-point value for the downstream density, and $K_R$ is the integral gain. Note that, in case the main objective of the traffic controller is to reduce congestion and to maximise the throughput, a good choice for the set-point is ${\rho }_i^{\ast }={\rho }_i^{\mathit{cr}}$.

2.2.2 PI-ALINEA

A very famous extension of ALINEA is the PI-ALINEA, in which a proportional term is added to result in a PI regulator. The metering rate is given by

$$r_i^{\mathrm{C}}\left(k\right)=r_i^{\mathrm{C}}\left(k-1\right)-K_P\left[{\rho }_i^{\mathit{\text{down}}}\left(k\right)-{\rho }_i^{\mathit{\text{down}}}\left(k-1\right)\right]+K_R\left[{\rho }_i^{\ast }-{\rho }_i^{\mathit{\text{down}}}\left(k\right)\right]$$E28

where $K_P$ is another regulator parameter.

Based on the stability analysis of the closed-loop ramp metering system provided in [20], it can be stated that PI-ALINEA is able to show a better performance than ALINEA.

2.3 Route guidance

Route guidance (RG) is an efficient technique to distribute the traffic demand over the network, by providing information about alternative paths to drivers. The variable message signs (VMSs) are one of the main actuators which can provide route information to drivers in the RG control scheme. In the RG control, the concepts of equilibrium play an important role. Wardrop has offered the two following principles [21]: (1) The system optimum (SO) is achieved when the vehicles are guided such that the total costs of all drivers (typically the TTS) is minimized, (2) The traffic network is in user equilibrium (UE) when the costs on each utilized alternative route is equal and minimal, and on routes that are not utilized, the cost is higher that on the utilized routes.

If the goal of a control strategy is defined as the travel time, it is typically defined as the predicted travel time or as the instantaneous travel time. The predicted travel time is the time that the driver will experience when he drives along the given route, while the instantaneous travel time is the travel time determined based on the current speeds on the route. In a dynamic setting, the instantaneous travel time may be different from the predicted travel time [5].

In route guidance control strategies, the control variable is the splitting rate at a given node. Considering the simple case of only two alternative paths [22], originating from node $n$, let us denote with $m$ and $m^{\prime }$ the two links exiting node $n$, corresponding respectively to the primary and secondary path. The primary path is the one characterised by the shortest travel time, in case of regular traffic conditions. In particular, the control variable is the splitting rate ${\beta }_{m,n,j}^{\mathrm{C}}\in \left[0,1\right]$, representing the portion of flow present in node $n$ at time instant $\mathit{kT}$ which should choose link $m$ to reach destination $j$. The other control variable is ${\beta }_{m^{\prime },n,j}^{\mathrm{C}}$, referred to link $m^{\prime }$, where it is easily computed: ${\beta }_{m^{\prime },n,j}^{\mathrm{C}}=1-{\beta }_{m,n,j}^{\mathrm{C}}$. The following feedback regulators of P-type or PI-type are the most used strategies for route guidance systems in the literature [5, 23]. According to a proportional control law, the portion of flow present in node $n$ at time instant $\mathit{kT}$ which should choose link $m$ to reach destination $j$ is computed as

$${\beta }_{m,n,j}^{\mathrm{C}}\left(k\right)={\beta }_{m,n,j}^N\left(k\right)+K_P\mathrm{\Delta }{\tau }_{n,j}\left(k\right)$$E29

where ${\beta }_{m,n,j}^N\left(k\right)$ is the nominal splitting rate, $K_P$ is a gain, $\mathrm{\Delta }{\tau }_{n,j}\left(k\right)$ is the instantaneous travel time difference between the secondary and primary direction from $n$ to $j$. In proportional-integral regulators, the splitting rate is

$${\beta }_{m,n,j}^{\mathrm{C}}\left(k\right)={\beta }_{m,n,j}^{\mathrm{C}}\left(k-1\right)+K_P\left[\mathrm{\Delta }{\tau }_{n,j}\left(k\right)-\mathrm{\Delta }{\tau }_{n,j}\left(k-1\right)\right]+K_I\mathrm{\Delta }{\tau }_{n,j}\left(k\right)$$E30

where $K_P$ and $K_I$ are other controller gains.

Another possible class of RG strategies is iterative strategies, where the splitting rate is computed by iteratively running different simulations in real time with different RG, in order to achieve conditions of either user equilibrium or system optimum [24, 25]. Iterative strategies are very beneficial, however, their high computational effort is a major drawback for this category of RG control techniques.

It is also interesting to describe how drivers react to travel time information and how they adapt their route choice. A well-known behavior model used for this purpose is the logit model [26], which is used to model all kinds of consumer behavior based on the cost of several alternatives. The lower the cost of an alternative, the more consumers will choose that alternative. In the case of traffic management, consumers are the drivers, and the cost is the comfort, safety, or travel time of the alternative routes to reach the desired destination. The logit model calculates the probability that a driver chooses one of more alternatives based on the difference in travel time between the alternatives. Assume that we have two possible choices $m_1$ and $m_2$ at node $n$ to get to destination $j$. For the calculation of the split rates out of the travel time difference between two alternatives, the logit model results in:

$${\beta }_{m,n,j}\left(k\right)=\frac{exp\left({\mathit{\sigma \theta }}_{n,m,j}\left(k\right)\right)}{exp\left({\mathit{\sigma \theta }}_{n,m_1,j}\left(k\right)\right)+exp\left({\mathit{\sigma \theta }}_{n,m_2,j}\left(k\right)\right)}$$E31

for $m=m_1$ or $m=m_2$, where ${\theta }_{n,m_1,j}\left(k\right)$ is the travel time shown on the DRIP at node $n$ to travel to destination $j$ via link $m$. The parameter $\sigma$ describes how drivers react on a travel time difference between two alternatives. The higher $\sigma$, the less travel time difference is needed to convince drivers to choose the fastest alternative route.

2.4 Integration of ramp metering and route guidance

The RM and RG controllers are both feedback and predictive controllers as they apply not only on the real-time measurements of the system to calculate the control actions, but they also use information about the prediction of the system evolution. The combination of RM and RG controllers has shown promising results in network performance from the point of view of different performance measures. The focus of this section is on providing a review on the related studies on the combination of these two main traffic management techniques.

In 1990, a study performed by Iida et al. [27] considered the development of an improved on-ramp traffic control technique of urban expressway. They extended the conventional LP control method to consider the multiple paths between on-ramps and off-ramps of the test case network and also the route choice behavior of drivers. They assumed that in the future, the drivers would have the travel information offered by the route guidance system. Their formulation combined the user equilibrium with the available LP traffic control formulation at the time. In their problem statement, the goal was to determine the optimal metering rate so that the system measures of the network would be maximized, while the drivers would choose the path provided by the RG control. They discussed their mathematical formulation in detail and provided the solution finding algorithm.

In 1999 and then with some modifications in 2002, Apostolos Kotsialos et al. in [28, 29], considered the design of an integrated traffic control system for motorway networks with the use of ramp metering, motorway-to-motorway control, and route guidance. They offered a generic problem formulation in the format of a discrete time optimal control problem. They assumed that both RM control measures and RG are available. The METANET model was used for the description of traffic flow. A hypothetical test network was considered to evaluate the performance of the proposed control system. The control measure considered was the minimisation of the travel time spent (TTS). The results showed the high efficiency of the proposed control system.

In 2004, Karimi et al. [30] considered the integration of dynamic RG and RM based on MPC. They used the dynamic route guidance panels (DRIPs) as both a control tool and an information provider to the drivers, and ramp metering as a control tool to spread the congestion over the network. This resulted in a control strategy that reduced the total time spent by optimally re-routing traffic over the available alternative routes in the network, and also kept the difference between the travel times shown on the DRIPs and the travel times actually realized by the drivers as small as possible. The simulations done for the case study showed that rerouting of traffic and on-ramp metering using MPC has lead to a significant improvement in performance.

In 2015, Yu Han et al. [31] proposed an extended version of the CTM first proposed in [2] with the ability to reproduce the capacity drop at both the on-ramp bottleneck and the lane drop bottleneck. Based on this model, a linear quadratic model predictive control strategy for the integration of dynamic RG and RM was offered with the objective of minimizing the TTS of a traffic network. In this paper, a RG model based on the perceived travel time of each route by drivers was also offered. If the instantaneous travel time of each route is provided to travelers, the perceived travel time is assumed to be the same as the instantaneous travel time. If not, the perceived travel time is assumed to be the free flow travel time. The splitting rates at a bifurcation are determined by the well-known Logit model [26, 30]. A test case network containing both on-ramp bottlenecks and lane drop bottlenecks was used to investigate the effectiveness of the proposed framework and the results showed the improvement the proposed control strategy brought for the network performance.

In 2017, Cecilia Pasquale et al. [22] offered a multi-class control scheme for freeway traffic networks with the integration of RM and RG in order to reduce the TTS and the total emissions in a balanced way. Their two controllers were feedback predictive controllers and it was shown how this choice for their controllers can benefit the performance of the controllers. They applied the multi-class METANET model and the multi-class macroscopic VERSIT+ model for prediction of the traffic dynamics in the network. In addition, they designed a controller gain selector to compute the gains of the RM and RG controllers. The simulation results showed significant improvements of the freeway network performance, in terms of reduction of the TTS and the total emissions.

In 2018, Hirsh Majid et al. [32] designed integrated traffic control strategies for highway networks with the use of RG and RM. The highway network was simulated using the LWR model. A control algorithm was designed to solve the proposed problem, based on the inverse control technique and variable structure control (super twisting sliding mode). Three case studies were tested in the presence of an on-ramp at each alternate route and where there was a capacity constraint in the network. The objective was to avoid congestion on the main road and to balance the traffic flow on the alternate routes. The obtained results showed that the proposed algorithms could establish user equilibrium between two alternate routes even when the on-ramps have different traffic demands.

In 2019, Martin Gregurić et al. [33] proposed the approach of coordination between controlling on-ramp flows with ramp metering (RM) and dynamic route guidance information systems (DRGIS), which reroute vehicles from congested parts of the motorway. DRGIS is used to inform drivers about current or expected travel times and queue lengths so that they may reconsider their choice for a certain route. It can be seen that DRGIS can directly impact on traffic demand at the urban traffic system by informing the drivers about travel times on its crucial segments. Reduced traffic demand on congested urban motorway section or at congested on-ramp in coordination with the adequate ramp metering control strategies can prevent “spill-back effect” and increase overall throughput of the urban motorways.

2.5 Summary

To conclude, in this section, a review on the integration of RM and RG controllers was presented. The section started by describing the two most commonly used discrete first-order and second-order traffic flow models. Then, it continued with an overview of the popular RM and RG control strategies and it finished by discussing most of the important studies on the integration of RM and RG. Most of them considered TTS as the performance metric and applied an MPC optimization framework since it reduces the computation efforts required to solve the optimization problem specially if the traffic evolution model used was the METANET model since it makes the formulation non-linear and non-convex. Overall, all the studies reviewed here have shown improvements in the network performance in comparison with the case of having either of these controllers alone.

The discussion so far has centered around the macro-level control of intelligent highways. However, an integral component of the transportation system of a smart city is the micro-level control of autonomous vehicles. It is, therefore, imperative that we cover some micro-level details pertaining to the CAVs. The following sections address problems related to the micro-level vehicle coordination. Commonly found interactions include highway merging, off-ramp exit, vehicle overtaking and lane changing. Focus is placed on on-ramp merging and overtaking in presence of incoming traffic, as these two tasks combined encompass most of the complexities involved in inter-vehicle interactions.

The selection of the on-ramp merging task (see Section 3) as a key area to be explored is due to both the extent of variables involved in coordinating this process and the dynamic nature of the process itself. In fact this is one of the tasks that today’s autonomous vehicles find difficult to carry out due to the need of reactive control and precise planning. The role of inter-vehicle coordination in efficient merging is also discussed in detail. While coordination of human-driven vehicles is mostly reactive, CAVs can be assigned goals proactively so as to optimize the merging process. Similarly, a detailed discussion is provided on the car overtake problem (see Section 4) to emphasize the need for explicit modelling of human behavior when designing algorithms for CAVs. This seemingly simple problem is specifically chosen to draw attention to the complexities that could arise due to the presence of human drivers on the road. A naive data-driven algorithm can fail catastrophically in scenarios where humans may behave unpredictably so an overview of algorithms that explicitly take human behavior into consideration is provided later on in this chapter.

3. Merging behavior at on-ramps and off-ramps for CAVs

In transportation networks, overall highway system efficiency can be severely reduced due to delays caused at on-ramps and off-ramps. If the merge process is incorrectly handled, merging lanes can have an overflow effect which causes the entire highway to become congested. This effect is caused by slower moving vehicles facing congestion in outer lanes near the merge junction deciding to switch into inner lanes in order to move faster. Therefore, even vehicles in the inner high speed lanes have to slow down. Overtime with continuing merge lane congestion, the entire freeway can become blocked.

In fact, in human-driven vehicles, this issue is further compounded due to the lack of cooperation and limited visibility for decision making. However, the introduction of CAVs has led to a lot more information becoming available for improving this overall merging process. In addition to the improved local sensing on-board modern CAVs such as ${360}^{\circ }$ radar and vision based sensors, most of the increased information comes from improvements in Vehicle to Vehicle (V2V) and Vehicle to Infrastructure (V2I) communication methods. These communication protocols enable individual vehicles to broadcast their intent and status, receive command velocities to enable optimal flow and also collaborate with each other to self-organize in such a way that freeway traffic flow is optimized.

Effectively managing the highway merge problem has multiple benefits, both to the end users and the entire transportation system as well. Reduced time in traffic at merge junctions means that overall throughput of the highway is increased, individual waiting time is reduced and the wastage of fuel (energy) in idling vehicles stuck in traffic is also reduced. Therefore, it is evident that improvements to intelligent highways will have an impact on the economy as well as helping combat environmental issues caused by excessive fuel consumption.

3.1 Standard problem formulation

Most approaches to solving the highway merging problem use a similar structure to model the physical highway on-ramp. Figure 2 shows an abstracted model of a highway on-ramp. A control zone is defined, where all vehicles in this zone communicate with a central controller and each other to decide individual optimum velocities and paths to be followed. The control zone encompasses both the main road and the on-ramp. Vehicles are allowed to merge from the on-ramp onto the main road in the merge zone, which is located at the end of the control zone.

Figure 2.

On-ramp merging regions and infrastructure model.

The vehicles involved are modelled based on simplistic second order dynamics given by,

$$\begin{array}{l}{\dot{p}}_i=v_i\left(t\right)\\ {\dot{v}}_i=u_i\left(t\right)\end{array}$$E32

where $p_i\left(t\right)$, $v_i\left(t\right)$, $u_i\left(t\right)$ denotes the position, velocity and acceleration/deceleration (control input) respectively for each vehicle. The vehicle state is then defined as,

$$x_i\left(t\right)=\left[\begin{array}{c}{p}_i\left(t\right)\\ v_i\left(t\right)\end{array}\right]$$E33

Furthermore, assuming that lateral control keeping the vehicle in lane is managed elsewhere, the vehicle can be modelled as a point mass moving along the center of the lane with the following state equation, where time $0$ is the point at which the vehicle enters the control zone.

$${\dot{x}}_i=f\left(t,x_i,u_i\right),x_i\left(t_i^0\right)=x_i^0$$E34

Additionally, all the methods discussed have the shared assumption that, the vehicle speed inside the merging zone is constant.

To compare these algorithms, the two main performance indicators are throughput (maximum number of vehicles that can merge onto the highway in an hour) and delay (average delay experienced by vehicles compared to the ideal travel time). In addition to these parameters, some research in this area also takes into consideration the savings in fuel consumption due to improvements in the highway merging process.

3.2 Various methods

So, let’s now explore some of the methods used in handling the highway merging problem in greater detail. Here, multiple approaches and methodologies to address this problem are discussed. Most of the work done in finding an optimal solution to automated freeway merging is based on posing the problem in the form of an optimization problem [34] with centralized control [35], virtual slot-based dynamics [36] problem or as broadcast communication [37] problem.

3.2.1 Optimal control method

This problem is posed as an unconstrained optimization problem [34] and then further extended to also consider the impact of fuel consumption [35]. The output was the ability to derive online an optimal closed-form solution for vehicle coordination at a merge intersection. The importance of safety constraints is also stressed here. Constraints in positioning, maximum velocity and maximum accelerations are imposed. Additionally, the algorithm only allows one vehicle to enter into the merging zone at any time.

The algorithm calculates the time at which each vehicle would enter the merge zone and requires that this time does not conflict with any of the other vehicles. This ensures that a lateral collision can never happen. Additionally, the algorithm also directs that vehicles maintain at least a specified gap between each other which ensures that rear-end collisions do not occur. Hamiltonian analysis is then used to convert the optimization problem into a system of four equations that can be solved in real time to output the optimal control for each vehicle.

Simulation of this system was then carried out to show that the algorithm performs as desired. It was found that compared to a baseline situation where on-ramp vehicles always give way to vehicles on the freeway this algorithm performs significantly better. An improvement of $52\%$ in fuel consumption when compared to the baseline situation was also reported.

Disadvantages: Only one lane of the freeway is in use and the benefits obtained from allowing/forcing vehicles to switch lanes in the freeway are ignored (i.e. full capacity of the freeway is not used). Additionally, vehicles are given merging rights based on a simplistic FIFO (First In First Out) queue which can cause additional delays and is definitely sub-optimal.

3.2.2 Slot based method

This method [36] primarily relies on creating virtual slots for each vehicle that moves along the freeway at a constant velocity. Then all changes to this behaviour such as switching lanes, on-ramp merging and exiting the highway on an off ramp are modelled as a switch from one virtual slot to another. A virtual slot $S$ is defined with five properties as is denoted by $S=\left\{z,p,t,b,o\right\}$, where $z$ is the size of the slot, $p$ is the position, $t$ is the time, $b$ is the behaviour of the slot and $o$ is the density status of the slot.

Slots are created by a central slot controller and vehicles can request to change from one slot to another. This change will then be approved by the slot controller as long as the slot is not already occupied or there is no other vehicle requesting to switch to that same slot. This approach was also shown to work in the absence of infrastructure at the merge junction since vehicles can use V2V communication to find an unoccupied virtual slot and perform the merging task.

An additional benefit of this slot based system is the ease by which the method can be extended to allow the entire bandwidth of the freeway to be used in order to further improve efficiency. For example, if the slot controller realizes that there are a lot of empty slots in the central lanes of the freeway, the controller can request that vehicles in the outer lane prior to the merge point to move into the empty inner lane slots. This creates more empty slots in the outer lane and provides more opportunities for vehicles on the on-ramp to merge successfully. This type of cooperative behaviour has been proven to drastically improve the throughput of vehicles through these freeway merge zones.

Using simulations, it has been shown that throughput at merge intersections can be increased and delay can be decreased drastically (throughput: $230\%$ increase and delay: $452\%$ decrease) vs. human driven vehicles under heavy traffic conditions.

Disadvantages: Many limitations brought about by having slot based systems include, difficulty in robustly handling emergency/breakdown situations, lack of flexibility in catering to different needs such as different vehicles requesting different speeds, inefficiency in heavy traffic density situations where not enough free slots are available to facilitate lane changes etc. Moreover, the slot based method places a lot of restrictions on the way vehicles can move about and position themselves on the freeway. Communication between vehicles and infrastructure also needs to be extremely good for this system to work and this type of perfect communication is rarely available in practice.

3.2.3 Broadcast communication based method

Some of the major issues in coordinating automated vehicles at merge intersections are the problems caused by imperfect communication. In these type of applications, delays of even a few seconds can have devastating results. Work on using Pseudo-perturbation based broadcast communication (PBC) [37] instead of unicast communication focuses on reducing the overhead on the V2I communication systems and leveraging the capabilities of V2V communication to handle any short term changes. In this method, a global controller (infrastructure) broadcasts an identical message to all vehicles in its vicinity. Each of these vehicles uses this information along with V2V data from other vehicles to select a suitable control strategy to safely perform the coordinated merging task. Vehicles send updates back to the central controller and the controller uses this feedback to decide its next broadcast message.

The key focus of this research was to extend available PBC capabilities to handle the multi-state vehicle dynamics and the multi-objective optimization required to solve a freeway merging coordination problem. The capability of this system to handle both CAVs as well as a mix of CAVs and human driven vehicles was also showcased. Here, the CAVs are controlled by the coordination system and are shown to be able to function even in the presence of human driven vehicles. The smoothness of the actual merging process was also evaluated through simulation. The main output of this research was to show that complex coordination problems such as freeway merging can be successfully solved with the use of minimal communication bandwidth.

Disadvantages: Lack of focus on the actual merging algorithm. Based on the broadcast signals, the decisions individual vehicles make may be sub-optimal and cause an unnecessary delay in the system. Also, very little work has been done on seeing whether this system actually has a effect on throughput.

3.2.4 Temporal logic based method

This method involves formalizing traffic rules using temporal logic [38] in order to ensure safety and robustness of automated highway vehicle control. This method helps with formulating existing traffic rules in a mathematical way in order to be easily applied in CAVs. While this method does not solely focus on the merging problem, the merge window is addressed in the metric temporal logic (MTL) formulas included. When the merge operation is formulated as a MTL formula, it leads the way to specifying safety guarantees in autonomous vehicles. Furthermore, the legality of trajectories generated by a motion planner can be easily checked using these MTL formulae. It also allows the use of standard verification and validation methods in order to ensure that there are no loopholes or issues in the generated logic.

3.3 Summary

While there are many methods to improve intelligent merging behavior, the core fundamentals of these algorithms are quite similar. They look into minimizing gaps or under-utilized space on the road while minimizing the control inputs (acceleration and braking) needed to achieve this. All algorithms also prioritize safety and fairness in the merging process. Additionally, there are extensions that focus on maximum capacity utilization by moving vehicles already on the highway to less congested lanes, which further improves the efficiency of the merging process. Each of the algorithms discussed in the section has its own advantages and disadvantages. Therefore, it falls on the highway regulatory agencies to decide which of these are most suitable to the conditions of each individual highway system.

4. The overtaking behavior with the combination of HDVs and CAVs

The final section of this chapter focuses on providing an in-depth analysis of a complex scenario in which the autonomous vehicle (AV) has to perform maneuvers in the presence of HDVs. Upon a cursory glance at the current state of AV research [39], it becomes obvious that not a lot of emphasis is being placed on explicitly modelling the varying behavior patterns of HDVs on the road. One such instance that highlights the need to model the varying HDV driving patterns is the car overtaking problem in a bidirectional traffic flow setting. In this problem, a scenario with three vehicles is considered; two HDVs and one AV (ego vehicle), as shown in Figure 3. The HDVs are travelling in opposite directions in adjacent lanes and the ego vehicle is following one of the HDVs. The objective of the AV is to safely overtake the vehicle travelling ahead while maintaining safety distances to the HDV in the adjacent lane, the HDV travelling ahead and the boundaries of the road.

Figure 3.

Overview of the car overtaking problem.

This is a particularly hard problem to solve because it involves a scenario composed of both human-driven and autonomous vehicles. The first major complication is the lack of global information because the V2X communication protocols cannot be leveraged in this scenario due to the presence of HDV. Then, there is the problem of uncertainty that arises due to the varying driving patterns so the algorithm needs to be robust enough to handle the different driving patterns of human drivers. Moreover, the traditional Supervised Learning based approaches cannot be applied directly to this problem due to a lack of labeled training data. Finally, the model-free Reinforcement Learning (RL) based techniques [40] cannot be employed due to a lack of safety guarantees while the model-based RL or Control techniques [41] cannot be employed since they require an accurate representation of system model and cannot capture uncertainties that arise due to varying driving patterns well.

In this chapter, a simplified stochastic control based formulation taken from [42] is laid out to provide a mathematical description of the problem. The formulation is followed by a brief discussion of a couple of algorithms to give the readers a glimpse of the possible avenues that could be taken to reach a solution. The references to detailed resources are also provided for the interested readers to explore further.

4.1 Stochastic control formulation

In this approach, the ego vehicle (Car 1, from Figure 3) has to first decide if it is feasible to overtake the HDV ahead (Car 2) once it gets “close enough”. In this simplified formulation, it is assumed that the Car 1 is able to measure its own relative velocity with respect to the HDVs with some additive noise. If the decision to overtake is made, then the AV has to generate the exact trajectory it will take to perform the overtake maneuver. An overview of these steps is outlined henceforth.

In the formulation below, it is assumed that the width of each of the lanes is defined to be a constant value $d$ and the minimum safety distance between cars is $L$. A collision is defined in terms of AV violating the minimum safety distance threshold with respect to the centroids of the cars. The positive velocities are defined towards the right in Figure 3 and positive $\theta$ is defined counterclockwise relative to the velocity vector of the car. Finally, the sets of admissible linear and angular speeds for the cars are considered to be finite.

4.1.1 Modelling

The states of Car i are $x_i$, $y_i$ and ${\theta }_i$ which respectively correspond to the longitudinal coordinate, lateral coordinate and orientation of Car i. The inputs to Car i are $v_i$ and $w_i$, the linear and angular velocities respectively of Car i respectively. An index $k$ is used to denote the time step.

Considering the initial states of the vehicles, it is assumed that initially at $k=0$, Car 1’s longitudinal coordinate is a random variable distributed normally with $\mu =0$ and $\sigma ={\mathrm{\Sigma }}_1$ while the lateral coordinate is fixed at the center of the bottom lane i.e. $y_1\left(0\right)=d/2$ and facing forward i.e. $\theta =0$. As for Car 2, it is assumed that initially at $k=0$, $x_2$ is distributed normally with ${\mu }_2={\tilde{x}}_2$ and $\sigma ={\mathrm{\Sigma }}_2$ where ${\mathrm{\Sigma }}_2$ is s.t. $x_2\left(0\right)>x_1\left(0\right)$ while the lateral coordinate is at $y_2\left(0\right)=d/2$ and facing forward i.e. $\theta =0$, identical to Car 1. Finally, for Car 3, it is assumed that initially at $k=0$, $x_3$ is distributed normally with ${\mu }_3={\tilde{x}}_3$ and $\sigma ={\mathrm{\Sigma }}_3$ where ${\mathrm{\Sigma }}_3$ is s.t. $x_3\left(0\right)>x_2\left(0\right)$ while the lateral coordinate is fixed at the center of the top lane i.e. $y_3\left(0\right)=3d/2$ and facing reverse (since $v_3<0$) i.e. $\theta =0$.

As for the dynamics of the vehicles, it is assumed that cars 2 and 3 keep travelling along the same lane i.e. ${\omega }_2$ and ${\omega }_3$, the angular velocities of cars 2 and 3 respectively, are identically zero for all time steps $k\ge 0$.

Based on the assumptions above, the dynamics for the cars are defined by the equations below:

$$x_1\left(k+1\right)=x_1\left(k\right)+v_1\left(k\right)cos\left({\theta }_1\left(k\right)\right)$$E35

$$y_1\left(k+1\right)=y_1\left(k\right)+v_1\left(k\right)sin\left({\theta }_1\left(k\right)\right)$$E36

$${\theta }_1\left(k+1\right)={\theta }_1\left(k\right)+\omega \left(k\right)$$E37

$$x_2\left(k+1\right)=x_2\left(k\right)+v_2\left(k\right)$$E38

$$y_2\left(k\right)=d/2$$E39

$${\theta }_2\left(k\right)=0$$E40

$$x_3\left(k+1\right)=x_3\left(k\right)+v_3\left(k\right)$$E41

$$y_3\left(k\right)=3d/2$$E42

$${\theta }_3\left(k\right)=0$$E43

To keep the problem as general as possible, it is assumed that at time step k, the AV has all the history of its past states, linear velocity and its relative position and velocity w.r.t the other two cars with some additive white Gaussian noise (AWGN). Therefore,

$$\mathcal{I}\left(k\right)={\left\{x_1\left(n\right),y_1\left(n\right),{\theta }_1\left(n\right),v_1\left(n\right),z_1\left(n\right),z_2\left(n\right),z_3\left(n\right),z_4\left(n\right)\right\}}_{n=0}^{n=k}$$E44

where

$$z_1\left(k\right)=x_2\left(k\right)-x_1\left(k\right)+n_1\left(k\right)$$E45

$$z_1\left(k\right)=x_3\left(k\right)-x_1\left(k\right)+n_2\left(k\right)$$E46

$$z_1\left(k\right)=v_2\left(k\right)-v_1\left(k\right)+n_3\left(k\right)$$E47

$$z_1\left(k\right)=v_3\left(k\right)-v_1\left(k\right)+n_4\left(k\right)$$E48

Here, $n_i$(k) are white Gaussian Processes with mean 0 and variances ${\sigma }_i^2\left(k\right)$. There is an assumption placed on the independence of ${\left\{n_i\left(k\right)\right\}}_{k\ge 1}$ from the distribution of initial longitudinal coordinates of the three cars i.e. $x_1\left(0\right)$, $x_2\left(0\right)$ and $x_3\left(0\right)$.

4.1.2 Control problem

Upon consideration of the control problem that the AV has to solve, it becomes apparent rather quickly that the AV simply doesn’t have to decide on linear and angular velocities. If that were the case, then the Car 1 could simply wait till Car 3 passes and then overtake Car 2 by having a velocity greater than Car 2. That is not an optimal solution for all possible scenarios. Therefore,the first thing that the AV needs to do is to get better estimates of position and velocity of Cars 2 and 3 rather than using the raw noisy data. With the better estimates of positions and velocities of the HDVs, the AV can perform a feasibility analysis to see if it is feasible to overtake the Car 2 or not. If the Car 1 deems the overtake maneuver to be infeasible, it can resort to the waiting strategy. If, however, Car 1 decides to overtake, then it has to decide on the time to start overtaking. Once the time to start overtaking is finalized, then the AV has to plan a trajectory that it will take to perform the maneuver such that it will not violate any safety margins. Finally, it needs to generate control commands i.e. linear and angular velocities to execute the overtaking maneuver. One typical problem that could arise is that the vehicle may have to return to its original lane, after starting the overtaking maneuver, but this scenario is beyond the discussion of this chapter.

4.1.3 Sample trajectory

A sample trajectory with a constant linear velocity for the AV is displayed in Figure 4. Between $k=0$ and $k=T1$, Car 1 is approaching Car 2. At $k=T1$, Car 1 decides to run the feasibility analysis and decides to overtake Car 2. Between $k=T1$ and $k=T2$, Car 1 has a positive constant angular velocity resulting in motion towards the adjacent lane. At $k=T2$, Car 1 has reached the divider between the lanes so it switches to a negative angular acceleration having the same magnitude as before, until the car reaches the center of adjacent lane at $k=T3$. Between $k=T3$ and $k=T5$, the angular acceleration remains at 0 for a straight line motion in opposite lane for overtaking. A negative angular acceleration having the same magnitude as before is applied between $k=T5$ and $k=T6$ followed by positive angular acceleration between $k=T6$ and $k=T7$. Car 1 continues its motion in a straight line after $k=T7$ with zero angular acceleration.

Figure 4.

Sample trajectory for car overtaking problem.

4.2 Solution methods

There were quite a few assumptions made to obtain the simplified model discussed above and some of those assumptions could be removed in order to obtain a rather complicated yet general framework. For instance, it might not be possible for the AV to store all the history of past states and actions so an attempt at modelling with limited information could be made. With this disclaimer, a brief overview of some of the possible solution methods for this problem is presented below.

4.2.1 Minimizing probability of collision

In this approach, taken from [42], it is assumed that the AV will travel at a constant speed throughout the overtaking maneuver. The estimates of positions and velocities of HDVs are obtained using Kalman filtering and a constant N is introduced to characterize the behavior of the AV with higher values corresponding to higher level of aggressiveness. Two feasible sets for the linear and angular velocities respectively of Car 1 are obtained by ensuring that the estimated position of AV after performing the maneuver will stay outside the estimated minimum safety region around the HDVs. Using the feasibility sets, probability of collision of Car 1 with the HDVs is obtained and the decision to overtake is based on those probabilities. If the decision to overtake is made, the linear and the angular velocities are chosen to minimize the probability of collision and the maneuver is performed as detailed in Section 4.1.3.

4.2.2 Reachability analysis-based with martingale-based HDV modelling

In this approach, taken from [43], the focus is on obtaining safety guarantees while overtaking. In this approach, the restriction on the constant speed of HDVs is also lifted, which was alluded to previously in Section 4.2. There are two different reachability analysis-based algorithms presented: one is a robust time-optimal algorithm such that it provides strict guarantees in regards to collision avoidance while the other is a stochastic algorithm that that yields a small collision probability with the advantage of shorter overtaking time. Moreover, the expected behavior of the human driver is modeled using a stochastic model based on martingales. It is shown that if the human driver is non-aggressive, the stochastic algorithm will yield a shorter overtaking time and if the driver is aggressive, the behaviors for stochastic and the robust algorithms will be identical.

4.3 Summary

The key takeaway from this section is that there is a need to place focus on explicitly considering the role of human drivers on the road while developing algorithms for autonomous vehicles. It was shown by the study of the simple car overtaking example that there are scenarios where the need to model human drivers on the road increases manifold. The algorithm presented in Section 4.2.2 explicitly models the behavior of human-drivers with martingales and provides overtaking algorithms with safety guarantees. The solution complexity of this approach is rather high due to the reachability analysis-based solutions so further research could be directed at improving the solution complexity or coming up with approaches that yield lower complexity while maintaining the safety guarantees. Furthermore, there is a prospect of exciting research in the direction of modeling human behavior with other approaches which may lead to various other interesting algorithms. The aim of this section was to provide motivation to the reader to explore research avenues that incorporate explicit modelling of human driving patterns yielding algorithms that will expedite the introduction of Autonomous Vehicles onto our roads.

5. Conclusions

The advent of improved communication, sensing and control in modern day vehicles and infrastructure creates a lot of opportunities to improve the efficiency and safety in many highway processes. Key areas of interest involve traffic routing and management, optimal highway merging and intelligent overtaking behaviours. This chapter examined some of the methods used in these areas and discussed the various improvements and shortcomings of each of them. The implementation of the algorithms discussed in this chapter, would lead to modern transportation systems becoming more effective, productive and safe. While there are many other methods worthy of merit not discussed in this chapter, the areas covered should give the reader a broad understanding of the extent of possibilities in this field and also spark further thinking which may lead to the generation of innovative new solutions.