# Survey on Position Weighted Backpressure
林紹維 陳翰霆
## Abstract
從課堂上教過的backpressure演算法為出發點，我們看了論文[1]，提出了可以考慮空間分布的position weighted backpressure演算法，並在實驗中比較各種control policy的優劣，總結於這份report中。

## Motivation
我們認為BP過於簡化，不符合現實生活中的交通網路情況，需要改進，因此上網搜尋多種方法之後，決定研究考慮空間分布的PWBP。

### Why not BP
課堂中的Back Pressure演算法原本運用於Computer Network的範疇，而在該領域中，並不存在對"空間"的概念，因為封包以接近光速在移動，所以封包都會集中在router的地方，只有極短的時間處在路徑上；相反的，車流會分散在道路的不同位置，有些剛過前一個路口，有些則聚集在下一個路口的紅綠燈前，如左下圖所示。因此空間上的分配是兩者不能相比擬的地方，導致BP並不適合運用在車流上的規劃。
|  |  |
| --- | --- |
再者，我們可以從右上方的圖看見，若忽略了空間上的分布，會發生車流回堵的問題，主要是因為我們利用課堂上的BP演算法，會認為直行車的權重比較大(因為V比較大)，而使得路口的號誌優先讓直行車行走。但直行車此時被更靠近路口的左轉車阻擋，反而造成了路口沒有車流的窘境。

<div style="page-break-after: always;">
</div>

### Why PWBP
Position Weighted Back Pressure(PWBP)顧名思義，是針對不同的位置做加權，愈靠近路口的車被視為愈重要的個體，因此得到的權重愈高，離路口愈遠的則愈低。如此，在上述舉的例子中，接近路口的車更有機會被先安排處理，才能維持路口的通順，並防止車流的回堵。

## Details on PWBP
在正式進入PWBP之前，我們必須把問題用數學式子先定義清楚。
### Problem Formulation
#### Notation
我們將整個網路視為一個directed graph，裡面有
* $N$ , network nodes 代表路口
* $A \subset N \times N$ , arcs 代表道路
* $A^{src} \subset A$ , source arcs
我們定義從網路外開進來的車和要開出網路的車，是從source arc進來的，(整個網路的邊緣和停車場都會被視為source arc)，並且我們假設source arc是infinite queue。
Source arc存在的目的可以用來評估網路是否stable，若一個演算法不stable，代表長期而言，塞車會回堵到source arcs，從source arcs想要開進來的車也會無法開進來。
* $l_a$ , length of arc $a$
* $\rho_a^b(x,t)$ , traffic density at position $x$ along arc $a$ that is destined to arc $b$ at time instant $t$
車流密度，以連續的函數表示。
* $q_a^b(x,t)$ , flow rate at $x$ along arc $a$ that is destined to arc $b$ at time $t$
車流流速，以連續的函數表示。

而接下來的實驗不是在connected vehicle的環境下模擬，所以計算$\rho_a^b(x,t)$和$q_a^b(x,t)$會是路口controller的工作，controller可以用統計算出這些數據。

* $M_n$ denotes the set of allowed movements between inbound and outbound road segment, $\forall n \in N$.
$M_n$ 這個集合是由pairs $(a, b)$所組成，代表在n這個路口，可以從路a開到路b。
* $P_n \subseteq 2^{M_n}$ , the set of $allowable$ phases and $P \subseteq \mathop{\otimes}\limits_{n \in N}P_n$ , the set of allowable network schemes.
$P_n$ 代表對於一個路口n，一次可以被assign的phase。
$P$ 則是代表對於整個網路，一次各個路口要被assign成哪個phase。
<div style="text-align: center">

上圖是對於一個十字路口，allowable的phases的例子
</div>

* $\pi_{a,b}(t)$ , the percentage of flow into $a$ at time $t$ that is destined to adjacent arc $b$
代表在a這條路上，有多少比例的車要開往b。
#### Weight Definition
我們想要用$w_{a,b}(t)$來表示weighted queue的概念，考慮車子的密度和流速在空間上的分布不同，會算出不同的權重，下一步會利用此權重來計算heuristic function，其中這邊的$c_{a,b}$是常數。
將權重定義為兩項"position weighted backpressure"的相減。絕對值內其中左項是在$t$的時間點，考慮空間分布，從arc $a$ 移動到arc $b$車流密度；右項則是所有離開arc $b$ 在 $t$ 時間點的車流密度。

由上面對權重的定義我們可以發現，當 $a \in A^{Src}$時，因為我們假設source arc 是 infinite queue，所以不用考慮source arc 的空間分布；而當$a \notin A^{Src}$時，觀察左項，在越靠近路口的地方($x=l_a$)，此處的traffic density會貢獻越高的權重，在離路口最遠的地方($x=0$)，貢獻的權重會是0。也就是說，對於一條路a，權重會隨著$x$線性增加。

我們觀察到，設計出來的這個$w_{a,b}(t)$，當在a的downstream(接近路口的地方)車子很擠；在b的upstream(接近路口的地方)車子很空的地方，會使權重很大，這就是position weighted backpressure最主要的設計。
#### Heuristic Function
我們要解的問題，是given時間$t$，要找出一個好的allowable network scheme $P$，為此，我們設計以下的heuristic function來找出這個$P$
<div style="text-align: center">

$p_{PWBP}(t) \in \mathop{argmax}\limits_{p\in P}
\sum\limits_{(a,b) \in M}w_{a,b}(t)\mathop{\mathbb{E}}^{\rho(t)}q_{a,b}(p)$
</div>

這個phase $p$會使得在時間點$t$，讓整個網路$M$能開通過每個十字路口的車的總和最多，和backpressure演算法一樣直覺，要讓壓力最大的車子通行，不過這邊是使用$w_{a,b}(t)$，可以考慮到空間的概念。

接下來，我們可以進一步簡化這個問題。觀察可知，在一個時間點$t$，每個pair $(a,b)$, i.e.,要從a開到b的車，只會關係到一個路口，因此，這個optimization問題可以被拆解成對於每個路口$n \in N$的子問題，而且不失最佳解。也就是說，這個問題可以被寫成：
<div style="text-align: center">

$p_{n,PWBP}(t) \in \mathop{argmax}\limits_{p\in P_n} \sum\limits_{(a,b) \in M_n}w_{a,b}(t)\mathop{\mathbb{E}}^{\rho(t)}q_{a,b}(p)$
</div>

因此這個問題是decentralized，可以被平行化處理，而對於每個路口的controller，因為十字路口只有8個phases，所以可以直接窮舉找出local的最佳解。因此在distributed implementation的架構下，可以使用此演算法real-time的算出答案。

此外，對於每個路口，可以有不同的phase切換週期，已達成minimum greens(最短綠燈時間)和避免oscillation(若每個路口的周期都完全同步，可能會造成oscillation而導致塞車)。

### Network stability
論文中有對PWBP演算法的stability和loss free的特性提出嚴謹的數學證明。

#### Stability of PWBP
利用Lyapunov function的理論套用到我們要optimized的heuristic function上，可以導出，for each $t \geq 0$，maximize heuristic function的$p \in P$會是network stabilizing。

#### Guarantee on no loss of work
如果整個網路的scenario是satisfiable的(如果任何control policy都無法舒緩網路，需要re-route所有車子才可能有解的話，就是unsatisfiable)，PWBP可以保證no loss of work，因為heuristic function裡的兩項$w_{a,b}(t)$和$q_{a,b}(p)$都是非負，所以選擇了一個$p \in P$一定有車子能開過去(若p使heuristic function等於0，即是gridlock scenario)。

<div style="page-break-after: always;">
</div>

## Experiment
在這篇論文中，主要完成了兩部分的實驗。第一部分是對單一的路口做PWBP的實際操作，第二部分則是在不同的control policy下，透過電腦模擬一個交通網路的實際車流數據。以下是兩實驗中，路口及網路的示意圖。
<div style="text-align: center">

|  |  |
| --- | -- |
</div>

### 單一路口
上圖是在第一部分的實驗中，作者所採用的路口線道圖。作者將BP和原本運用於路口的SCOOT(Split, Cycle and Offset Optimisaton Technique)相比，在每小時可以處理的車流量及平均每位用路人的延誤時間，都是PWBP佔了上風，我們可以從以下兩張圖表看見。
<div style="text-align: center">


<div style="page-break-after: always;">
</div>

</div>

較上方的圖顯示在一天當中PWBP與SCOOT所能允許每小時經過路口的車流量比較，可以發現PWBP幾乎都略高於SCOOT；下方的圖怎可以看見，PWBP的運用使得用路人在一天當中的各個時段都可以在比較短的等待時間中經過該路口，因此可以得到PWBP在單一路口的運作上，是比現有的SCOOT體系來的好的。

### 交通網路
在第二部分的實驗中，主要是針對四種control policy，FT(Fixed Timing)、BP、CABP(Capacity Aware BP)、PWBP在四個項目的比較下做分析，包括車流處理、壅塞回堵、壅塞處理以及意外處理能力。
#### 車流處理
在對於相同的用路人等待時間中(這邊給定每輛車40秒)，我們從下圖(a)看見PWBP能允許的路口車流處理量相較於其他三種是最大的，分別在四個phase及八個phase的情境下，可以達到1580及1620輛車每小時。
有趣的觀察：可以發現BP和CABP在8 phases時會有更高的delay。原因其實就是他們無法分別同一條路上的直行車和左轉車，所以其中的4個phase(無法同時讓直行車和左轉車通過的phase)其實會造成反效果。因此BP和CABP其實只用4個phase效果會更好。

#### 壅塞回堵
論文中針對每小時1225、1570及1620三種不同的每小時車流量，做了壅塞回堵的模擬。此處我們只挑選了每小時1570輛車的實驗做分析，因為我們認為車流量在1570時有最明顯的差異。下圖中，橫軸代表的是時間，縱軸代表的是有多少百分比的車以大於或等於該速在前進，因此當100%的車都是以0.1%的速度在前進時，我們就視為交通網路已經癱瘓(gridlock)。四張圖表中，可以看到FT(fixed timing)的演算法下，交通最先癱瘓，僅花了兩個半小時；BP及CABP則將近六小時；PWBP則是經過六小時依舊維持交通網路的正常運作，因此我們可以得到PWBP是四者中，最有復原能力的。

<div style="page-break-after: always;">
</div>

下方折線圖以每小時1620輛車的需求量作圖，可以看出四種control policy在不同的時間點都會到達該網路的容量上限，當網路內的車不再增加時，及代表網路內的車都已經不能再行走了，結果顯示PWBP可以堅持最久的時間才會交通癱瘓。
<div style="text-align: center">

</div>

#### 壅塞處理
接著，針對壅塞處理的能力，我們從下方折線圖可以看見PWBP不僅僅在同樣的車流量下最不容易造成壅塞，也可以在最短的時間內恢復成流暢的狀況。
<div style="text-align: center">

</div>

#### 意外處理
針對之前上圖交通網路中的黃點位置發生意外，導致原本三線道的車道剩下一線道可以運行，原論文中也將四種control policy在意外發生10、40、70、90分後的車流分布狀況做了較，我們可以從接下來的四張圖比較觀察。
<div style="text-align: center">

Fixed Timing :

<div style="page-break-after: always;">
</div>

Back Pressure :

<div style="page-break-after: always;">
</div>

Capacity Aware Back Pressure :

<div style="page-break-after: always;">
</div>

Position Weighted Back Pressure :
</div>

從上面四張圖中可以看見FT、BP、CABP在意外發生時都不能有效疏解交通，而且在短時間內便會造成癱瘓；反觀，PWBP能夠順利疏解車流，原因就在於當意外發生在黃點時，車流會回堵到路口A，此時PWBP會防止車流繼續流入該路段，但BP及CABP都不能阻止這件事。同時，這段時間到B路口的車很少，因此PWBP並不會讓該路段燈號為綠燈，但BP、CABP並不能防止這件事。
綜合以上幾種實驗，我們可以得到PWBP的確在各方面的情境都佔上風，在現有的control policy中也的確最有效率。

<div style="page-break-after: always;">
</div>

## Further Questions
* 在設計$w_{a,b}(t)$時，為何權重的比例要以$x$位於一條路離路口遠近的比例來計算？這樣無法考慮到當每條路的長度不同時，在現實世界裡對於急迫性不同的考慮。
比較長度為100公尺的路和長度為10公尺的路時，位於整條路中點的車的權重(距離路口50公尺和距離路口5公尺的車)以PWBP來計算會一樣，這似乎不是很直覺，是否存在一個更好的heuristic function?
* 對於每個路口的controller在計算phase $p$的時候，因為heuristic沒有考慮到切換phases時的黃燈時間和中間過渡都是紅燈的時間，但以直覺來思考，太頻繁的phases切換不是有效率的，但PWBP沒有考慮到這個問題。

## Conclusion
對於課堂上提到的BP我們認為不夠貼近實際狀況，因此在閱讀完[1]論文之後，得到了另一種衡量路口壓力問題的方法--PWBP。在論文中，首先建立了PWBP的核心觀念，將道路上的位置做不同的權重，接著透過公式實作，並在多種實驗下證實PWBP的確比現有的control policy都完善，且能夠被各個路口獨立運算而不會有複雜度太大的問題，因此我們認為PWBP儘管還有些疑問值得討論，卻已經是一個很完整的路口control policy了。

## Reference
[1] Li Li and Saif Eddin Jabari. Position weighted backpressure intersection control for urban networks. 22 Jun 2019.