Signal Control Optimization for Congestion Relief

Overview

In the easy-to-learn optimization flow, we have taken an easy-to-explain problem and explained the process of performing combinatorial optimization processing with an annealing machine by defining requirements, formulation, input data preparation, and executing. Let's take your learning one step further by experiencing the development flow of a combinatorial optimization system using a CMOS annealing machine through a series of steps from problem requirements definition to executing.

This article provides an exercise to realize a signal control system to relieve traffic congestion as a signal control system by processing it with a CMOS annealing machine as a combinatorial optimization problem.

Although traffic signals are not currently controlled by processing them as a combinatorial optimization problem, the economic loss caused by traffic congestion is said to be enormous, and it is one of the social issues that need to be addressed. Eliminating traffic congestion is expected to be effective in reducing economic losses and energy consumption.

The contents of this page are based on the paper by Toyota Central R&D Labs., Inc. and the University of Tokyo [1] and the blog post by Jij Inc. [2], which is based on the paper, and are reorganized so that you can practice what you have learned in "Easy-to-learn optimization flow" as an exercise for CMOS annealing machines. The knowledge explained in "Easy-to-learn optimization flow" is added to the explanation of defining requirements, constraint setting, formulation, etc. defined in the above paper and blog, which are the preliminary steps to perform in CMOS annealing, aiming to provide both review and application.

References

• [1]Toyota Central R&D Labs, University of Tokyo, "Traffic Signal Optimization on a Square Lattice with Quantum Annealing".
  https://arxiv.org/abs/2003.07527
• [2] A blog by Jij Inc. that explains the same paper in detail.
  Signal Control Optimization on a Square Grid Intersection Cluster Using D-Wave

Defining requirements

Objective

What optimization problem can be formulated to solve the practical problem of reducing traffic congestion? The objective of the optimization problem discussed here is to reduce traffic congestion by making cars flow as smoothly as possible. In other words, what we want to achieve is to equalize the number of cars waiting vertically and horizontally at each intersection through signal control. For this problem, let's define the requirements, i.e., the language to communicate to the computer what we want to do.

Definition of Roads and Signals

Definition of car movement

Formulation takes into account time variation

One difficulty with this problem is that trying to eliminate the bias in the number of cars at an intersection can have a positive or negative impact on the number of cars at neighboring intersections, and the conditions for optimization change over time. How do we model this complex assumption?

First, we define "improving the state" for each and every intersection. To improve the condition of each and every intersection means to change one signal to green and the signal in the crossing direction to red.

However, it cannot be left to luck to determine whether operating a single intersection will move the entire area in the direction of eliminating traffic congestion. If a horizontal traffic signal is left green and left unattended, vertical traffic will naturally become congested. Next, we must define the "relationship between intersection $i$ and $j$" and the "relationship between time ($t$) and time ($t+1$)," taking into account time variation.

Formulation

Next, let us formulate the signal control as an Ising model. At this point, we will try to incorporate changes in the time direction by including the "time variation considerations" described in the previous section.

Assign Ising variables to signals

First we assign the Ising variables $+1$ and $-1$ to the signal control, which is the smallest element for "improving the state" of each and every intersection.

The direction (vertical or horizontal) of the signal to be green could be set as an Ising variable.

Next, for the ultimate goal of optimization, which is to eliminate traffic congestion, we consider modeling with consideration given to the flow of time and the state of each case.

Model the amount of cars

The object to be optimized, i.e., the state of the signal, is given by the quantity of cars at the next time. The amount of cars at the next time can be expressed using the signal assignment $\sigma$ at the immediately preceding time t and the ratio $a$ of the direction of car travel.

Quantity of cars $q_{ij}, x_i$

Two variables are defined for the quantity of cars: $q_{ij}$ and $x_i$. $q_{ij}$ is used to represent the quantity of cars moving from intersection $j$ to intersection $i$. On the other hand, $x_i$ is a variable that represents the amount of cars waiting at an intersection. Let's first take a closer look at the definition of $q_{ij}$.

where $s_{ij}$ is the road direction parameter, $s_{ij} = +1$ if road $j→i$ is vertical and $s_{ij} = -1$ if road $j→i$ is horizontal.

$q_{ij}$ represents the quantity of cars at the previous time, $-s_{ij}\sigma_i(t)/2$ represents the quantity of cars leaving, and $s_{ij}\alpha_{\sigma_j}(t)/2$ represents the quantity of cars coming in. In other words, equation (1) shows that the quantity of cars at time (t+1) represents the quantity of cars at the previous time plus the quantity of cars coming in and the quantity of cars going out. Note that $\alpha=2a-1$ is substituted to simplify the equation.

Next, let's look at how the variable $x_i$ is defined.

In other words, equation (2) represents the amount of vehicles heading from intersection $j$ to intersection $i$ and waiting at intersection $i$.

$s_{ij}$, which constitutes equation (2), is the directional parameter of the road, and $q_{ij}$ is the amount of cars entering intersection $i$ from intersection $j$. In other words, it adds up to the case where the vertical direction is red and cars are waiting, and the horizontal direction is red and cars are waiting.

Let us imagine where cars enter and exit in the four directions adjacent to intersection $i$ when $\sigma_i = +1$ and $\sigma_i = -1$, respectively. For intersection $i$, there are four possible intersections $j$. To account for the amount of cars from each of them, the formula is $\Sigma$.
Cars waiting vertically at intersection $i$ may come from the north or from the south. And the cars waiting horizontally at intersection $i$ may come from the east or from the west.
If the amount of cars waiting vertically and horizontally is not biased, it approaches $x_i(t) = 0$.

Now we have an equation that expresses the relationship between the color of the traffic light at an intersection and the amount of cars.

Cost function

We have been able to model the relationship between the amount of cars and the color of the signal. Now we can proceed to optimize it with a CMOS annealing machine. For the relational equation we have established, we can evaluate it as follows, taking into account what kind of operation "makes it better" to achieve our objective.

The optimization is to equalize the number of vehicles waiting horizontally and vertically at a given intersection.
In other words, it can be said to be a problem of determining the signal assignment $\boldsymbol{\sigma}(t)$ such that $\boldsymbol{x}(t+1)$ is close to $0$. By squaring this, $0$ is the minimum value. Therefore, the objective function can be set as follows

$$\tag*{Equation(5)} H= \boldsymbol{x}(t+1) ^T \boldsymbol{x}(t+1)$$

This is how the square of the matrix representation is written: the symbol $^T$ is called a transpose, which means to swap the rows and columns of a matrix; to square the vector $\boldsymbol{x}_i(t+1)$, the $\boldsymbol{x}(t+1)$ to be transposed is the row component, and the $\boldsymbol{x}(t+1)$ in the column direction is multiplied to it, indicating the operation. The reference link [4] describes it clearly.

Use of "matrices" to facilitate representation of repetitive calculations

This section explains that the relational expression in (3) can be rewritten in matrix form as (4). A matrix is "a collection of numbers and formulas with similar properties that can be written together in the form of a matrix to simplify computation."[4]

Reference[4] What is Matrix, Meaning/Purpose of Matrix

Although Equation (3) allows us to establish a relationship between the intersection and its four neighboring intersections (signal color and vehicle volume) at time $t+1$ at intersection $i$ and the previous time $t$, it does not express the objective of making the vehicle volume uniform at all intersections in the entire area. Furthermore, the energy function is not in the form that would result in the least amount of energy for the optimal solution. To solve all these problems at once, and to create an equation that calculates the state of all intersections, and to represent it simply, we will use "matrices" here.

For the sake of understanding, let us define 9 intersections arranged in a grid with 3 horizontal rows and 3 vertical columns, and represent them in matrix representation.

$$ \tag*{(3)} x_i(t+1) =x_i (t) + \frac{1}{4} \sum_{j \in N(i)} ( - \sigma_i (t) + \alpha \sigma_j (t) ) $$

$$ \tag*{(4)} \boldsymbol{x}(t+1) = \boldsymbol{x} (t) + (- \boldsymbol{I} + \frac{\alpha}{4} \boldsymbol{A} ) \boldsymbol{\sigma} (t) $$

$$ \tag*{(4')} \boldsymbol{x}(t+1) =\boldsymbol{x}(t) -\boldsymbol{I_\sigma}(t)+\frac{1}{4}a\boldsymbol{A}\boldsymbol{\sigma}(t) $$

$$ \tag*{(4'')} \begin{pmatrix} x_0(t+1) \\ x_1(t+1) \\ x_2(t+1) \\ x_3(t+1) \\ x_4(t+1) \\ x_5(t+1) \\ x_6(t+1) \\ x_7(t+1) \\ x_8(t+1) \end{pmatrix} = \begin{pmatrix} x_0(t) \\ x_1(t)\\ x_2(t)\\ x_3(t)\\ x_4(t)\\ x_5(t) \\ x_6(t) \\ x_7(t) \\ x_8(t) \end{pmatrix} - \begin{pmatrix} \sigma_0(t) \\ \sigma_1(t)\\ \sigma_2(t)\\ \sigma_3(t)\\ \sigma_4(t)\\ \sigma_5(t)\\ \sigma_6(t)\\ \sigma_7(t)\\ \sigma_8(t) \end{pmatrix} + \frac{1}{4}a \overset{\boldsymbol{A}}{\overset{\text{\textbardbl}}{ \begin{pmatrix} 0 1 0 1 0 0 0 0 0 \\ 1 0 1 0 1 0 0 0 0 \\ 0 1 0 0 0 1 0 0 0 \\ 1 0 0 0 1 0 1 0 0 \\ 0 1 0 1 0 1 0 1 0 \\ 0 0 1 0 1 0 0 0 1 \\ 0 0 0 1 0 0 0 1 0 \\ 0 0 0 0 1 0 1 0 1 \\0 0 0 0 0 1 0 1 0 \end{pmatrix}}} \begin{pmatrix} \sigma_0(t) \\ \sigma_1(t) \\ \sigma_2(t) \\ \sigma_3(t) \\ \sigma_4(t) \\ \sigma_5(t) \\ \sigma_6(t) \\ \sigma_7(t) \\ \sigma_8(t) \end{pmatrix} $$

Matrix representation of 9 intersections

The variables $x_i(t)$ and $x_i(t+1)$ in equation (3) represent the state of a single intersection, while $x(t)$ and $x(t+1)$ in the matrix notation of equation (4) are in vector notation and represent all intersections simultaneously, so the meaning is different. In addition to the fact that the $i$'s can be taken, the typefaces are often expressed differently in terms of appearance.

A *vector is a matrix whose components are in a single column or row.

(4") is the distribution of ( ) in (4), where $I$ is called the identity matrix, and is the matrix representation as $\sigma_i(t)$ outside of $\Sigma$, which was inside $\Sigma$ in (3), but. Since $\Sigma$ represents the addition of the terms of road $j$ in the four directions for each intersection $i$, the terms of $i$ can be calculated outside of $\Sigma$.

(4") is further rewritten as a matrix representation of the components, with each term corresponding to (4'). The last term on the right-hand side is the component of $j$ that adds up to $\Sigma$. $A$ represents the component matrix that specifies the intersection in the four directions relative to intersection $i$. In this case, we have the following nine intersections in matrix form: for intersection 1, it is the adjacent numbers 2 and 4 that are designated as $j$. In (4"), the $i=1$ relation computes the elements of the first row.

Now that we know what is involved in processing the matrix representation, we will process it to form it as a cost function at the next section.

Organizing Constraints

Speaking of constraints, the increase in the number of vehicles at an intersection may cause congestion at adjacent intersections, but these constraints have already been taken into account in the modeling up to this point, so there is no need to consider new ones.

There is something else to consider in this problem. In this problem, signals change to reduce vehicle congestion, but if they change too frequently, they can impede the flow of vehicles. Therefore, it is necessary to set a penalty (weighting) for cases where the signal changes at adjacent times. This is the optimal solution.

This is the matrix representation of $\boldsymbol{\sigma}$, i.e., the difference between time $t$ and the previous time $t-1$ for the entire area $\boldsymbol{\sigma}$, and then squared.

The value of $\boldsymbol{\sigma}(t)-\boldsymbol{\sigma}(t-1)$ is $0$ if it is the same at time $t$ and $t-1$, and $+2$ (or $-2$) if it is different.

Final form of cost function

With the derived cost and penalty functions, the energy function of the Ising model for obtaining the optimal solution is as follows

The annealing machine is now ready to be shaped in such a way that it can derive the optimal solution.

Input data preparation and execution of CMOS annealing machine

Now that we have defined the requirements and formulated the formulation (modeling, setting the objective function, and organizing the constraints).

From this point on, let's narrow down the range of roads and consider $3 \times 3 = 9$ intersections, and actually create and run the data to be input to the CMOS annealing machine.

How was it? Here is a video of an even larger road with optimized signal control. This demonstration shows the results of a simulation in which traffic congestion is eliminated by optimizing 64 x 64 = 4096 intersections using a large-scale CMOS annealing system to be exhibited in the Cooperative Research Building at Hitachi, Ltd.