---
# System prepended metadata

title: 步步為營對抗策略

---

## 位置處理
位置處理方面，由於所有傳感器皆有誤差以及延遲，為了令控制更為精準及快捷，我們採用了擴展卡爾曼濾波以進行信息融合，其優點為可到傳感器反饋信息的可信性來快速更正自身的錯誤。而在考慮算式方面，由於編碼器及陀螺儀的延遲較少，而影像則有較大延遲但相對高的精準度，因此以編碼器及陀螺儀計算出的速度用作輸入控制模型，而影像計算出的位置則用作觀測模型。
## 運動模型預測
實作方面，每次更新時，先以陀螺儀取得機身沿Z軸自轉的速率乘以時間，得出機身的旋轉角𝛳，以此得出旋轉矩陣: 
$$
R(\theta)=
\begin{bmatrix}
\cos{\theta} && \sin{\theta} && 0 \\
-\sin{\theta} && cos{\theta} && 0 \\
0 && 0 && 1
\end{bmatrix}
\quad
R'(\theta)=
\begin{bmatrix}
-\sin{\theta} && \cos{\theta} && 0 \\
-\cos{\theta} && -sin{\theta} && 0 \\
0 && 0 && 1
\end{bmatrix}
$$
再結合來自四個麥克納姆輪的編碼器的速率
$$u_t=\left(v_0,v_1,v_2,v_3\right)^\quad J=\begin{bmatrix}1&&1&&1&&1\\
-1&&1&&1&&-1\\
\frac{-1}{d}&&\frac{-1}{d}&&\frac{1}{d}&&\frac{1}{d}\end{bmatrix}$$
，可得機身相對棋盤的速率
$$v_t=
\begin{bmatrix}
v_x \\
v_y \\
v_\omega
\end{bmatrix}= \frac{r\cdot \pi}{4}
\cdot R(\theta)\cdot J \cdot u(t)$$
$$\bar{x}=(x,y,\theta)^T+(v_x,v_y,v_   w)^T⋅dt \text{ (運動模型預測)}$$
## 誤差協方差傳播
更新狀態後，亦需要更新其估計協方差矩陣，算式為:
$$\bar{P}_t=\nabla F_xP_{t−1}\nabla {F_x}^T+\nabla F_wQ\nabla {F_w}^T \text{(誤差協方差傳播)}$$



F為狀態轉移矩陣。考慮為狀態轉移矩陣。考慮(1)式對$(x,y,\theta)$作為偏導，取雅可比矩陣，並以冪級數作可得
$$\nabla f_x=I_3+\begin{bmatrix}O&&O&&M \end{bmatrix},
\quad M=R'(\theta)\cdot J\cdot u(t)
\quad 
O=\begin{bmatrix} 0\\0\\0
\end{bmatrix}$$

$$\nabla f_w=R(\theta)\cdot J\cdot I_4$$
至於Q則為編碼器的協方差矩陣，經實作試行後，由於編碼器於加或減速時有較大的誤差，我們决定把部份設為定值，部份與加速度成正比。
## 卡爾曼增益、錯誤協方差更新及狀態更新

由於估計誤差協方差矩陣和影像結果屬同一測量空間,$H=I_3$
而餘量協方差為$S=H\bar{P}H^T+R=\bar{P}+R$

R為實際以實際地點和影像量度之差計算出的實際方差，借此便能計算出卡爾曼增益，並更新狀態估計X和估計協方差： 
$$K=\bar{P}H^TS^{-1}=\bar{P}S^{-1} \text{(卡爾曼增益)}$$
$$X=\bar{X}+K(Z_k-\bar{X}) \text{(錯誤協方差更新)}$$
$$P=(I-KH)\bar{P}=(I-K)\bar{P} \text{(狀態更新)}$$
在得出估計位置後，車模便可算出其前往目標所需之向量。再將其轉換為電機所需的速率並正規化後，便可用作電機的PID操控。

# 步步為營對抗策略
基於DeepMind的AlphaGo Zero算法的成功，我們嘗試摹擬其以蒙地卡羅樹搜尋及Q學習算法提升深度學習算法的棋略。由於硬體方面的限制及步步為營的高度發散，Alpha-beta剪枝難以有很高的深度，而容易被有較遠視的玩家欺騙、如迫使其走回頭路，相對而言，蒙地卡羅樹搜尋及Q學習結合後可以搜索較深的空間，並如人類一樣重視較合理的的棋步。

AlphaGo Zero算法中深度卷積神經網絡同時給予Q學習選擇的機率和評測勝利的機率(用以去掉仿真的步驟及用於反向傳播)。但經計算後，發現以我們的計算力無法令"棋步選擇的機率"收斂，因此我們嘗試使用卷積神經網絡來預計棋步的Q值，蒙地卡羅樹搜尋時50%選擇最佳Q值的步法，50%按Q值加權隨機選擇，並在發現新節點時以神經網絡初始化其Q值，並作反向傳播。卷積神經網絡的部份先在電腦上作學習，再在機上實施。雖然神經網絡的計算時間不短，層樓亦只有8層，但相對仿真來說還是較快和較精準，因此有其效益。

## Q值算法

我方勝利Q值=1,對方勝利Q值=-1

計算對方Q值時，以對方視角給予卷積神經網絡數據，並取其負值作我方Q值


Q值反向傳播:
$$Q_{t}(s,a)=\frac{N(s,a)Q_{t-1}(s,a)+0.99\cdot \max\limits_{a}(-1\cdot Q_{t-1}(s_{t+1},a) )}{N(s,a)+1}$$
$$N_{t}(s,a)=N_{t-1}(s,a)+1\quad N_{t}(s)=N_{t-1}(s)+1$$



另一優點是蒙地卡羅樹搜尋可以一直演算，因此對比Alpha-beta剪枝來說可以用盡演算時間，直到人員按鍵確定出發後再從現時節點找最佳Q值的一步，並保留其子節點的Q值繼續演算。

電腦上以每步限制15秒的演算時間為測試時，能打敗以兩歩Alpha-beta剪枝的對手，亦在大部份時間取勝於筆者，結論來說，在硬件限制下，淺層的卷積神經網絡無法有如AlphaGo Zero的強大表現，但大致上相等於以特徵的線性組合估算Q值並以此限制搜索空間，令蒙地卡羅樹搜尋有較佳表現。