# 4 PART

上週 ADAS 跟這週所在的層級是 Application。

下面是這堂課所規劃的四個層級：

- [Part1]Preliminary
- [Part2]Applications
- [Part3]Intelligent Technology
- [Part4]Advanced Topic

更之前提到的 Timing Analysis 和 System Design 則是屬於 Part1 的部分。

Applications 的部分老師似乎都會用 5W1H 來介紹。

# Intersection Management

## 5W1H

- What is Intersection Management？
- 決定一個路口車子行走的順序
- 路口其實不侷限於十字路口，特殊的像是合併車道
- Why is Intersection Management？
- 讓路口更安全，讓交通更絲滑，更有效率
- When does Intersection Management work？
- 任何時候
- Where does Intersection Management work？
- Centralized 跟 Distributed 的運作地點不一樣
- Centralized 會有個中央的 Manager
- Distributed 則是大家共同協同運作
- Who develops Intersection Management？
- 基本上是由政府，或政府委託的外包廠商來做
- 進階的則是由自駕車跟車聯網來達成，但基本上目前尚未成真
- How does Intersection Management work？
- 就是本週的重頭戲

---

# Modeling

:::info
首先做名詞定義。下面提到的名詞在之後提到的 models 中會個別用到一些。
由於名詞定義大多有圖示，請詳閱老師的講義。
:::

- Tiels / Cells
- 把道路跟路口畫分成很多小區塊，用以方便定位、管理
- 劃分的越精細，可以做到更精細的調配，但要付出高複雜度的代價
- Trajectories
- 車子「預先規劃」的路徑，可以是直行、轉彎、或是圓環上的路
- Collision Zones / Conflict Regions / Conflict Zones
- Trajectories 的交點
- 不過車子通常具有體積所以大多會以該交點位於的 Tile 為 Zone
- Phase
- 一個路口中，車子可以行走的「方向」
- 例如如果是十字路口，可以「南北向直行或右轉」、「東西向直行或左轉」等等 Phase
- 上面是左駕

# Controlling Length of Traffic Lights

- Fixed Time Control
- 紅綠燈以固定的規律在運作
- Coordinated Control
- 除了固定的規律運作，同時考量到如果是同一個幹道，就讓幹道上的紅綠燈同時綠燈
- Adaptive Control
- 更進階的做法
- Design-Time approach
- 根據路段過往的流量資料，來制定紅綠燈的時間，例如上下班車流不一樣。
- Real-Time approach
- 根據即時的資料，例如車聯網或是路面感測器，來制定紅綠燈的時間

## Back-Pressure Method

這是一個最簡單的 Adaptive 做法。

下面是名詞定義：

- $\lambda_{i}$：道路的 index
- $Q_{i}$：道路 $i$ 的 Queue 長度，或者說道路上有多少車
- $P_{i}$：道路 $i$ 的 壓力
- 目前令 $P_{i}=Q_{i}$，但這就是下調味的地方
- $D_{i,j}：[0,1]$：是否有車正在道路 $i$ 等待，想開往 $j$
- $P_{i,j}$：道路 $i$ 往 $j$ 的壓力差
- $P_{i,j}=D_{i,j}\max(P_{i}-P_{j},0)$
- 首先要有車子想開過去才有壓力差
- 再來是 $i$ 一定要比 $j$ 更有通行壓力

有了上面的名詞，路口處在每個 Time slot 就是要挑選該路口的一種 Phase，使得：

$$
\sum_{i,j}V_{i,j}P_{i,j}
$$

達到最大。

:::warning
影片中有講解例子，也就是弄一個情境然後操作上面的模型。
$V_{i,j}$ 算是一個輔助的參數，他可以有很多用途；最基本的用途是，原本都令 $V_{i,j}=1$，但在某種 Phase 的時候，有些方向是不能通行的，此時就必須讓 $V_{i,j}=0$ 以免 $P_{i,j}$ 有值。
:::

:::info
- Capacity-aware Back-Pressure Control
- 上面的參數定義並沒有考慮到車道的「容量」，如果加以考量的話就要把 $P_i$ 修改的更複雜，例如車道快滿的話可能壓力就會特別大
- Adaptive Max-Pressure Control
- 會用某種機率分佈模擬車道的情形，使得 $P_i$ 的計算方法更複雜
:::

---

# Intelligent Intersection Management

:::warning
以下的所有 Approach 都是假設有車聯網並且有自駕功能
:::

## Goals

- 安全
- 交通效率
- 避免 deadlock 跟 starvation
- 溝通以及計算的複雜度要低
- 因為交通上分秒必爭
- 容易做「添加」
- 就像 CAN 容易添加新節點一樣
- 最好要有個標準協議
- 但是通常還是由政府帶領車廠來弄

# Centralized and Distributed Approaches

架構上都有四個模快：

- Receiver
- Sender
- Motion planning
- Controller

但是 Distributed 因為沒有 Manager，所以會多一個 Decision Making 的模快。

- Centralized：task 的週期以下面五個循環，但 Controller 為持續運作
- Communication：一開始先由車子跟 Manager 溝通
- Decision Making：接著由 Manager 做決定
- Communication：Manager 再將結果傳回車子
- Motion Planning：車子根據收到的信號決定如何動作
- Controller：執行新的動作
- Distributed：task 的週期以下面四個循環，但 Controller 為持續運作
- Communication：一開始先由車子跟外界的車子交換訊息
- Decision Making：接著由車子自己做決定
- Motion Planning：車子根據自己做的決定開始動作
- Controller：執行新的動作

## model 例子

這個是某個組織提出的 Centralized 的 model。

概念上就是在路口處有個 Manager，負責接收來車想通過路口的請求，然後 Manager 經過計算後做出回覆。

車子會有以下四種 Message types：

- REQUEST：向 Manager 請求通過路口，同時會傳大概幾秒之間抵達路口
- CHANGE-REQUEST：修改上一次的 REQUEST，例如將抵達路口的時間延後
- CANCEL：取消通過路口的請求
- DONE：通過路口後傳給 Manager 做確認

>要注意車子沒有說要靠近路口才傳訊息給 Manager。

Manager 會有以下四種 Message types：

- CONFIRM：告訴車子你可以通行，其中包含哪個時間點要在哪個 tile 等等資訊
- REJECT：拒絕車子的兩種 REQUEST ，要車子再等等，想通過的話請再次發出 REQUEST
- ACKNOWLEDGE：回應車子的 DONE 跟 CANCEL
- EMERGENCY-STOP：要所有車子立馬停下來

Manager 可能有以下的 Control Policies

- First Come First Serve
- 但是要先定義好何謂「先到」，例如檢查路口的第一輛車是誰
- Virtual stop sign
- 虛擬的 stop sign
- Virtual traffic light
- 虛擬的 traffic light

:::warning
- 上面的各種 message type 跟無線網路的 Protocols 一樣可以畫出狀態圖，請參見講義
- 由於車聯網依靠無線網路，所以一樣會有 Loss 跟 Delay 的問題，但是在交通中這兩點會更需要密切計算
:::

# Graph-Based Approach

核心上來說，就是將 Intersection Management 問題化為 Cycle-removal 問題。

但是 Graph-Based 不只可以解決 Intersection Management，只要是 Conflict-resolution Problem，例如兩條車要搶同個 tile，都可以轉換為 Cycle-removal 問題。

:::info
下面介紹時是搭配一個 Central Manager，不過 Graph-Based 也可以用在 Distributed 的情境，只要大家有相同處理 Graph 的演算法就好。
:::

## Timing Conflict Graph

此處參考講義的圖，請搭配服用。

在一個路口上，首先決定好 Conflict Zones，也就是上面提到 Trajectories 的交點所佔據的 tiles，不一樣的 tile 精分程度，就會產生不同的 Timing Conflict Graph。

- vertex 定義方式為 $V_{i,j}$，$i$ 是車子的 id，$j$ 是車子正處在的 conflict zone id
- edge 有三種：
- type 1：根據車子的 trajectories 經過的節點和順序所連成
- type 2：如果兩台車屬於相同的「路口」，經過了相同的 conflict zone
- 此時箭頭指向順位低的人，代表順位高的會先走
- type 3：兩台車屬於不同的「路口」，經過了相同的 conflict zone
- 就會有箭頭互相指著對方，箭頭一樣是指向順位低的

## Cycle Removal Algorithm

有了上面的 TCG，接著就是用一些 Cycle Removal Algorithm 把 type 3 的 edge 做修剪，來達成想要的目標：

- 可能是最小化最後一台車離開的時間
- 或是最小化車子平均的 delay 時間

演算法修剪完之後，因為去除了環所以可以確保不會有碰撞，但是 deadlock 則要透過一些方法來檢驗。

:::info
Deadlock 請參考講義的圖片。概念上就是有一台車 A 先進到的 conflict zone 1，擋住了另一輛也想進去的車 B，但是 A 想要前往下一個 conflict zone 2 必須要先等到 B 通過 conflict zone 2，可是 B 又會因為 A 卡在 conflict zone 1 過不去 conflict zone 2，產生 Deadlock。
:::

:::warning
這週不去細講如何修剪，這通常伴隨一些 heuristic 的做法；而是介紹如何驗證沒有 deadlock。
:::

## Resource Conflict Graph

TCG 沒有環，不能保證沒有 Deadlock，所以必須根據 TCG 建構出真的有「執行順序」意義的 Resource Conflict Graph。

Resource Conflict Graph 沒有環才確保沒有 Deadlock，有環的話就有 Deadlock。

建構方法如下：

- 對於 TCG 結構中所有的 type 1 箭頭，例如 $V_{i,j}\rightarrow V_{i,j'}$
- 就將他合併成一個節點 $V_{i,j,j'}$
- 例如 $V_{i,j}\rightarrow V_{i,j'}\rightarrow V_{i,j''}$，就可以合併成 $V_{i,j,j'}$ 跟 $V_{i,j',j''}$
- 因為這兩個節點共用了同個節點 $V_{i,j'}$，所以他們之間在 RCG 就有箭頭
- $V_{i,j,j'}\rightarrow V_{i,j',j''}$
- 如果合併後為 $V_{i,j,j'}$ 跟 $V_{i',k,k'}$
- 如果在 TCG 中 $V_{i,j}\rightarrow V_{i',k}$ 是 type 2 或 type 3 箭頭
- 對 $V_{i,j}$ 跟 $V_{i',k}$ 來說只要在 RCG 中有任何是由他們兩構成的 RCG node
- 就要有 $\rightarrow$ 的箭頭。例如 RCG 中有 $V_{i,j,j'}$ 跟 $V_{i',k,k'}$
- 那麼就要有 $V_{i,j,j'} \rightarrow V_{i',k,k'}$。代表 $V_{i,j,j'}$ 這個 RCG node 發生的順序是比較優先的。
- 別忘記箭頭指向順位低的

照上面的邏輯，就可以根據三種 type 的箭頭以及執行順序，構建出帶有實際先後意義的 RCG。

## Petri-Net-Based

這個是專門用來檢查 Deadlock 的酷東西，老師說有興趣可以去看看。

---

# Non-Cooperative Environment

如果現在的環境下車子不會互相合作，而是互相競爭，此時就可以套用 Game Theory。

Game Theory 有以下要件：

- Players：在這裡就是車子內的 Decision Makers，並且假設為理性的 Rational
- Actions：在這裡就是車子的抉擇 Decision
- Objectives：車子想要通過相同的路口或 tile

## Prisoner's dilemma

這是著名的一種遊戲理論。

| | 犯人 A 保持沉默 | 犯人 A 供出犯人 B |
|:---------------------:|:-----------------------:|:-----------------------:|
| **犯人 B 保持沉默** | A,B 都要坐牢 1 年 | A 可以釋放，B 判刑 3 年 |
| **犯人 B 供出犯人 A** | B 可以釋放，A 判刑 3 年 | 兩者都判刑 2 年(Nash Equilibrium) |

因為兩位犯人都是「理性的」，所以對 A 來說，如果沒有背叛 B，最糟會被判刑 3 年，如果背叛 B，最遭是被判刑 2 年，因此一定會選擇背叛 B，而 B 也同理。

因此最終兩者都會選擇背叛對方，該點又稱做 Nash Equilibrium。

## Two-Vehicle Scenario (without Manager)

如果是以車子的例子來講：

| | A 直接駛入 | A 停下 |
|:--------------:|:-----------:|:-------:|
| **B 直接駛入** | (-100,-100) | (-4,0) |
| **B 停下** | (0,-4) | (-3,-3) |

上面當中的 -4 代表要等待 4 個單位時間，停一次車需要 1 單位時間，等對方通過需要 4 單位時間。

兩者都停下會是 (-3,-3) 是因為兩個人都停一次車所以需要 2 單位時間，並且其中一人先通過需要 4 單位時間，兩個人平均來說就是要 (2 + 4) / 2 = 3 單位時間。

如果A,B具有優先順序，A>B，就會如下：

| | A 直接駛入 | A 停下 |
|:--------------:|:-----------:|:-------:|
| **B 直接駛入** | (-50,-150) | (-4,0) |
| **B 停下** | (0,-4) | (-1,-5) |

:::info
但是人往往是不理性的，上述理性的狀態只有在電腦上才辦的到
:::

## Three-Vehicle Scenario (with Manager)

Three-Vehicle strategy game。

下面是沒有人說謊的例子：

| Vehicle | Actual time | Reported time | Allocated time | Delay |
|:-------:|:-----------:|:-------------:|:--------------:|:-----:|
| A | 5 | 5 | 5 | 0 |
| B | 10 | 10 | 12 | 2 |
| C | 12 | 12 | 19 | 7 |

System Performance 為 2+7=9。

但如果 C 說謊：

| Vehicle | Actual time | Reported time | Allocated time | Delay |
|:-------:|:-----------:|:-------------:|:--------------:|:-----:|
| A | 5 | 5 | 5 | 0 |
| B | 10 | 10 | 19 | 9 |
| C | 12 | 6 | 12 | 0 |

System Performance 為 0+9=9

可以發現，C 雖然說了謊，但是系統的表現都一樣，這樣他就不會被 Manager 抓到。

---

# Lane Merging

路口的特例。

前提假設是車子都有 CACC，可以幫助車子在合併後持續跟車。

## 情境-Two-Lane Merging

- 假設現在左側有兩條路，要合併成右方一條路。
- 此時左方上車道有兩輛車，抵達路口的時間從左到右為 (3,1)
- 此時左方下車道有兩輛車，抵達路口的時間從左到右為 (4,2)
- 假設跟同車道的之間的間距只要 1 秒，跟不同車道的間距要 3 秒

有兩種方法：

- First-Come-First-Go
- 通常來說不會是最佳解
- 以上面情境來說，因為是上下車道交錯抵達，所以通過路口的時間會是(1,4,7,10)，因為不同車道的車要等 3 秒後才可跟車
- Optimal shceduled
- 這可以使用 DP 求解
- 最佳的配置是上方車道兩輛車先過，再來是下方兩輛車，這樣通過的時間就會是 (1,3,6,7)
- 也就是只需要上下車道換一次而已

:::info
另外還有 Three-Lane Merging、Consecutive Two-Lane Merging 的情境。
:::