A Dynamic and Deadline-Oriented Road Pricing Mechanism for Urban Traffic Management

Due to the huge scale of the problem, great challenges are faced in finding the optimal policy function. Traditional machine learning methods require a comprehensive understanding of the environment. However, in our defined problem, traffic environment is complicated and constantly changing; it cannot be expressed by mathematical formulas. In addition, the characteristics of samples used by traditional machine learning usually need to be designed by human experts. As known, features have a crucial influence on the generalization of the model; however, traffic environment features cannot be expressed as the environment changes with time. Generally, with the increase of state and action space, the complexity of the reinforcement learning increases exponentially. Traditional reinforcement learning has a two-dimensional Q table presenting the value of state-action pair, but this problem has multidimensional and continuous state space and action space^{[ 22 ]}.

Hence, function approximators are generally adopted. There are many kinds of approximators such as linear function approximation or nonlinear function approximation. Deep neural networks as nonlinear function approximation have also been used for large reinforcement learning tasks. Deep neural networks have the ability of automatic feature extraction; thus, the use of deep learning is an advantage to represent the agent’s observation as an abstract representation in learning an optimal control policy. When faced with the high-dimensional state space and bounded and continuous^{[ 23 ]} action space, deep learning will have convergence problems. The policy gradient methods have advantages when dealing with this situation^{[ 24 , 25 ]}. The policy gradient uses gradient descent methods in finding the optimal policy. Policy gradient does not estimate the value of state-action functions; it learns the policy directly. Based on the above factors, we present our solution algorithm, which is the DADO policy gradient algorithm.

DADO is different from the Monte Carlo based policy gradient algorithm that observes the whole process of an episode and calculates the accumulative reward until the end of the episode. It uses the average reward of all episodes to estimate the reward of the current policy. The total reward from an episode is a random variable, and the Monte Carlo based algorithm uses the sum of the reward, leading to the large variance of the actual cumulative reward obtained by the Monte Carlo algorithm.

DADO adopts temporal difference learning, which has lower variance compared to the Monte Carlo algorithm. More specifically, DADO adopts a structure named “actor-critic”. Actor is the policy function aiming to approximate the optimal policy and choose the optimal action, while critic is the value function that evaluates the actor’s choice and guides the next choice. We use the advantage function that has a small variance compared with accumulative reward as the evaluation indicator of critic. The formula of advantage function is as follows:

(7) $$A_{\pi }(s,a)=Q_{\pi }(s,a)-V_{\pi }(s)$$

where $V_{\pi }(s)$ is the sum of the value of all possible actions taken in this state. $Q_{\pi }(s,a)$ is the action value function corresponding to the action in this state. $Q_{\pi }(s,a)-V_{\pi }(s)$ means the advantage of action value function over the current state value function.

The actor aims to maximize the sum of discounted rewards $J(\theta ,s_t)$ . $J(\theta ,s_t)$ is represented as

(8) $$E[\log {\pi }_{\theta }(a|s)(Q^{\pi }(s,a)-V_s^{\pi })]$$

where $\log {\pi }_{\theta }(a|s)$ is the logarithm of the probability of taking action given the state $s$ . $Q^{\pi }(s,a)$ is the action value when performing the action $a$ given the state $s$ . $V_s^{\pi }$ denotes the state value, and it is the output of the critic. The critic learns the state value, and we use Eq. ( 9 ) as loss function. The critic learns to minimize the difference between real action value and estimated value:

(9) $${\text{loss}}_{\text{critic}}={(Q^{\pi }(s,a)-V_s^{\pi })}^2$$

The state value of the traditional MDP will not change with time, but in the problem we studied, the amount of vehicles arriving at the destination depends on the specific time step and OD demand of the future time step. In addition, the action also depends on an exact time period. Hence, we updated its value function $v^t(s^t)$ and policy function ${\pi }^t(a|s,{\theta }^t)$ for each time period $t$ :

(10) $${▽}_{{\theta }^t}{v}_{\pi }(s)=Q^t(s^t,a^t){▽}_{{\theta }^t}\log {\pi }^t(a^t|s^t,{𝜽}^t)$$

where $Q^t(s^t,a^t)$ is the action value of executing action under a given state.

The actor training network of DADO uses a deep neural network with three full connection layers to approximate the policy function ${\pi }^t(a^t|s^t)$ . The critic network consists of two full connection layers. Connected parameters are trained separately and updated with the stochastic gradient descent method.

The data network required is independent and distributed. An asynchronous method is adopted that does not produce data at the same time to break the correlation between data and make the convergence easier. Each worker directly takes parameters from the global network and interacts with the environment to output the action. The gradient of each worker is used to update the parameters of the global network. Figure 3 depicts the architecture of the proposed DADO.

10.26599/TST.2020.9010062.F003 Fig. 3Architecture of the proposed DADO.

At each time step, the local agent extracts state representation from traffic dynamics and puts the state to the actor, and the actor performs an action based on the input state and policy. After that, the critic makes an evaluation of the action and updates the local parameters. After the update, the local agent will push the parameters to the global agent and pull the latest parameter from the global agent.

Algorithm 1 illustrates the processing of a single actor. In Algorithm 1, we assume the global shared network parameters are vectors $𝜽$ and $\mathit{\vartheta }$ . The thread-specific parameter vectors are ${𝜽}^{\prime }$ and ${\mathit{\vartheta }}^{\prime }$ . The input requires the decision-making horizon $H$ and the global shared counter $T$ . We need to initialize the step counter $t$ to perform an advanced update. Later, the algorithm starts the loop. In the loop, the agent resets the gradients, pulls the global parameter assignments to the local network, and starts a new episode. Post that, the agent interacts with the environment, and the action is selected based on the policy function $\pi (a_t|s_t;{\theta }^{\prime })$ . The agent will receive immediate rewards which are computed using Eqs. ( 3 )-( 5 ), and the environment will transform to the next state. If an episode has ended or the number of steps calculated in advance has been reached (Line 15), the algorithm then begins to calculate the total discount reward and updates the parameters at each time period with stochastic gradient descent method. $R$ means the sum of rewards from time $t_{\text{start}}$ to $t$ obtained from the interactions, representing the “real” value based on the policy. $V(s_i;{\vartheta }^{\prime })$ is the “estimated” sum of rewards approximated by the critic. After updating the local parameters, the local parameters will be pushed to the global network to update the global net. The whole process iterates until the number of episodes reaches a predefined global counter $T_{\max }$ .