Optimization-based incentivization and control scheme for autonomous traffic

Recent results show that the price of anarchy in vehicle traffic is essentially unbounded, i.e., traffic congestion can be arbitrarily worse as compared to the case when all vehicles on the road are routed by a central controller that aims to minimize congestion or average travel time [1, 2]. The development of autonomous vehicles (AVs) is creating new possibilities for traffic management and control [3] and can be utilized for reducing the cost of anarchy. Keeping in mind that, in the autonomous future, vehicles will retain their primary function of transportation of individuals, we must consider that the desire of AV passengers may sometimes be antagonistic to the goals of traffic improvement. For example, given a choice of whether or not to let their vehicle participate in traffic improvement, passengers would likely consider the cost of their own time or comfort and, for this reason, would likely require some sort of incentive in order to participate.

In this work, we present an incentive and control scheme for the use of AVs to control traffic on a single road segment. We contrast this to most previous works that have considered incentivization for traffic management by improved routing on multiple road segments, e.g., [4, 5, 6]; we instead focus on dynamic control of vehicles. Specifically, we model traffic as a flow and assume that a certain part of this flow can be incentivized to switch and cooperate in order to control traffic. This turns the problem of controlling traffic into both an incentivization and control problem. AV passengers must first be incentivized to cooperate, and then their vehicles must be controlled. We note that a related mixed traffic model using mean-field ideas was recently introduced in [7], however the focus in that work is on stability and not on incentivization.

The problem of computing appropriate incentives falls under the umbrella of mechanism design [8]. We are interested in developing an incentivization framework in the context of mixed-traffic control, where both cooperative and non-cooperative vehicles are present. As a first step towards this goal, in this work we consider the problem of selecting a subset of vehicles, periodically updated, that can be potentially incentivized, and hence optimally controlled to drive the overall vehicle density to be close to uniform. As part of the solution, the corresponding optimal controls for this subset are also computed. This problem is generally motivated by recent results [9, 10] showing that intelligent control of a small fraction of vehicles can significantly reduce congestion and attenuate traffic waves.

We propose a periodically updated, receding-horizon control scheme. During each period, we determine the distribution of incentive, i.e., which subset of the vehicles to control, as well as the control inputs to these vehicles over the fixed time-period. The receding horizon approach is used to address undesirable edge effects that typically appear at the end of the control time-horizon. The control history is determined according to the assumption that controlled AV flow can be directly controlled and that uncontrolled flow follows the conventional Lighthill-Whitham-Richards (LWR) model. The resulting problem is a variation of the mean-field optimal control problem [11] with congestion, where only a subset of the agents are controlled.

We consider two types of cost on vehicle density. The first is an $L^{2}$ cost, which penalizes the distance to the uniform density, and the second is an $\dot{H}^{-1}$ cost, which is a type of multiscale norm and used in fluid mixing to ensure uniformity. To show how one can implement our scheme, we perform a numerical simulation on a single, circular road scenario and use the optimization software cvx to solve the optimization problem. Our results show that the penalization of $L^{2}$ cost does not effectively achieve convergence to a uniform distribution while penalization of $\dot{H}^{-1}$ cost does. For this reason, we suggest that approaches from fluid mixing can be helpful in solving traffic optimization. Notably, we find that the scheme requires flow rates that are too high to achieve in a single lane; we therefore suggest that the practical implementation of our approach may require use of a dedicated lane.

The rest of the paper is organized as follows. In Section II, we present a detailed problem formulation and introduce the optimization framework. In Section III, we present a computationally feasible algorithm for solving the proposed optimization problem. In Section IV, we present detailed simulation results and provide a discussion on how one may implement the resulting scheme in practice. Section V is the conclusion.

We consider a two-population traffic scenario, consisting of heteronomous (non-cooperative) vehicles (HVs) and autonomous (cooperative) vehicles (AVs). The densities of HVs and AVs are given by $\rho_{1}(x,t),\rho_{2}(x,t)\in\mathbb{R}$, respectively, where $(x,t)\in\Omega\times[0,T]$ is the position $x$ of a vehicle at time $t$, and $\Omega$ and $[0,T]$ are the spatial and time domains, respectively. The vehicular dynamics of HVs are governed by the Lighthill-Whitham-Richards (LWR) model,¹¹1While in this paper we only report results for the LWR model, we note that it is straightforward to extend our algorithm to other models of uncontrolled traffic flow such as the Payne-Whitham and Aw-Rascle-Zhang (ARZ) models. with the dynamics given by,

$$\partial_{t}\rho_{1}+\nabla\cdot\left(\rho_{1}v_{1}(\rho_{1},\rho_{2})\right)=0,$$

(1)

where,

$$v_{1}(\rho_{1},\rho_{2})=u_{0}\left(1-\frac{\rho_{1}+\rho_{2}}{{\rho}^{*}}\right),$$

(2)

is the HV velocity field and the parameters $u_{0}$ and $\rho^{*}$ are the free-flow speed and the maximum density, respectively. The density evolution of AVs is governed by the continuity equation,

$$\partial_{t}\rho_{2}+\nabla\cdot m_{2}(\rho_{2},v_{2})=0,$$

(3)

where $m_{2}(x,t)\in\mathbb{R}$ is the controlled flux, given by,

$$m_{2}(\rho_{2},v_{2})=\rho_{2}v_{2},$$

where $v_{2}(x,t)\in\mathbb{R}$ is the controlled, AV velocity field. Note that the HV dynamics are affected by the AV dynamics but not vice versa.

Apart from being able to control the AV velocity field, we are able to assign the initial densities of AVs $\rho_{2}(x,0)$ over $\Omega$. We do this by assuming that a certain distribution of vehicles can be either an HV or AV, but must be incentivized to turn on AV capability. We assume that the total amount available for incentivization is fixed and an offer can be made only once over a time period $[0,T]$. As a consequence of optimality, there is no reason to not make an offer after the initial time $t=0$ since, if $v_{2}(x,t)=v_{1}(x,t)$ is optimal over $t\in[0,a]$ but not over $t\in[a,T]$, it will be equivalent to make an offer at any time $t\leq a$. In this work, we assume that each vehicle operator’s cost preference $\beta(x)$ is equal, i.e., $\beta(x)$ is constant over $x$.

We assume the initial density distribution $\rho_{0}=\rho_{1}(\cdot,0)+\rho_{2}(\cdot,0)$ is given and its average is $\bar{\rho}$, i.e., $\int_{\Omega}\rho_{0}(x)\text{d}x=\bar{\rho}$. We also assume that the initial density distribution of potential AVs $\hat{\rho}_{0}\leq\rho_{0}$, with average $\hat{\bar{\rho}}$, is given and therefore the initial distribution of AVs $\rho_{2,0}=\rho_{2}(\cdot,0)$ must satisfy the incentivization condition,

$$\int_{\Omega}\rho_{2}(x,0)\text{d}x\leq\int_{\Omega}\beta(x)\hat{\rho}_{0}(x)\text{d}x=\beta\hat{\bar{\rho}}.$$

(4)

In both cases above, the nonlinear dynamics (1)-(3) result in non-convex problems. This is because the flux expression obtained by multiplying (2) by the density $\rho_{1}$ cannot be converted to a linear PDE. We can see this when we discretize the dynamics using a conservative scheme, like that of Godunov, where the flux term becomes dependent on logical conditions.

The problem can be somewhat alleviated by using a discretization of the PDEs that is dissipative, such as that of Lax-Friedrichs. In this way, the map from the state $(\rho_{1}(\cdot,t_{k}),\rho_{2}(\cdot,t_{k}))$ at one time instant $t_{k}$ to the next time instant $t_{k+1}$ becomes linear. The drawback, however, is that the use of a dissipative discretization does not lead to a physically correct solution [15].

We propose to use a two step iterated approach in solving the optimization problem.

• •

  Step 1: Fix the density $\rho_{1}$ of the HVs (in space and time), and use the Lax-Friedrichs discretization to obtain an optimized control $v_{2}$ and AV density $\rho_{2}$.

• •

  Step 2: Propagate the HV dynamics using a first-order Godunov scheme to determine a new value for HV density, using the AV density obtained in step 1.

In this way, by keeping $\rho_{1}$ static in step 1, the corresponding optimization problem becomes convex and the dissipative components of Lax-Friedrichs can be compensated through vehicle actuation.

At the beginning of the algorithm, we set initial conditions $\rho_{1}^{(0)}$ and $\rho_{2}^{(0)}$ that satisfy the constraints (7). Then, during each iteration $i\geq 1$, we perform the two steps.

In the first step, we solve the optimization problem,

$$\min_{\rho_{2,0},m_{2}}\iint\frac{m_{2}(x,t)^{2}}{\rho_{2}(x,t)}\text{d}x\text{d}t+cV\left(\rho_{1}^{(i-1)},\rho_{2}\right),$$

(9)

subject to the constraints,

	$\displaystyle\rho_{2}(x,t),~{}m_{2}(x,t)$	$\displaystyle\geq 0,$		(10a)
	$\displaystyle\rho_{2}(x,t)$	$\displaystyle\leq\bar{\rho}-\rho_{1}^{(i-1)}(x,t),$		(10b)
	$\displaystyle\int_{\Omega}\rho_{2,0}(x)\text{d}x$	$\displaystyle\leq\beta\hat{\bar{\rho}},$		(10c)
	$\displaystyle\rho_{2,0}(x)$	$\displaystyle=\rho_{0}(x)-\rho_{1}^{(i-1)}(x,0),$		(10d)

for all $(x,t)\in\Omega\times[0,T]$, and dynamics (3). Upon discretization, the dynamics (3) are linear, of the form,

$$\rho_{2}(x_{k},t_{k+1})=D_{\text{LF}}\begin{bmatrix}\rho_{2}(\cdot,t_{k})\\ m_{2}(\cdot,t_{k})\end{bmatrix},$$

(11)

where $D_{\text{LF}}$ is the fixed, spatial discretization matrix obtained using the Lax-Friedrichs method and $t_{k}$ is the $k$-th time step.

In the second step, we use a first-order Godunov method to solve the dynamic equation,

$$\partial_{t}\rho_{1}+u_{0}\nabla\cdot\rho_{1}\left(1-\frac{\rho_{1}+\rho_{2}^{(i)}}{\rho^{*}}\right)=0,$$

(12)

with initial condition $\rho_{1}(x,0)=\rho_{0}(x)-\rho_{2,0}^{(i)}(x)$, alternating between steps until either a stopping criterion or the maximum number of iterations have been reached.

We perform numerical simulations to test and exhibit the properties of the algorithm just presented. In all simulations, the simulation parameters are set to the values given in Table I and the optimization problems are solved using the software package cvx. We begin with the initial distribution $\rho_{0}$ over $\Omega=S^{1}$ given in Fig. 1 as,

$$\rho_{0}(x)=3.5+2\sin(\pi x).$$

For comparison, the figure also shows the evolution of vehicle density without control, i.e., $v_{2}=v_{1}(\rho_{1},\rho_{2})$. We begin by considering the optimization of the $L^{2}$ cost on density and then the $\dot{H}^{-1}$ cost.

In this work, we presented an optimization-based control scheme for stabilizing traffic to a uniform state by incentivizing and controlling a group of autonomous vehicles. We considered two approaches, the first optimizing an $L^{2}$ cost and the second optimizing an $\dot{H}^{-1}$ cost.

We performed numerical simulations to determine the efficacy of the approach. The results showed that, by optimizing the $\dot{H}^{-1}$ cost, we are able to stabilize traffic to the uniform in finite time while, by optimizing the $L^{2}$ cost, we are not. We discussed the practicality of this approach and recommend the addition of a dedicated lane for implementability.

The authors acknowledge Dr. Saleh Nabi of Mitsubishi Electric Research Laboratories for technical discussions.