【Python】強化学習を使って自動運転をシミュレーションしてみた話

# 0. はじめに
自動運転のシミュレーションを、機械学習を用いて行いたいと思い、やってみました。
[前回の記事](https://qiita.com/yk81/items/30cf8b6af0723db4bf7f)では機械学習を用いたモデル予則制御によって自動車の動きを制御しました。
今回は強化学習を用いて制御方針を学習し、自動車をよりよく制御できるようにします。

使用した環境は以下の通りです。
Google Colaboratory
python 3.7
numpy 1.19.5
pytorch 1.9.0

[ソースコード(Google Colab)](https://colab.research.google.com/drive/1FBOfvz5AIomncvHax5E3TFrkMEOePNxh?hl=ja)

# 1. 方針
##1.1 学習の流れ
今回は強化学習を使って、最適な制御ができるようにしていきます。
学習の流れは以下の通りです。

1. 自動車が壁にぶつかるまで、または一定時間走るまで自動車を走らせる
1. 1を複数回繰り返す
1. 2の結果に応じて方策を更新する

自動車の走らせ方は以下の通りです。

A. 自動車は壁を認識し、自動車からの距離を求める
B. 壁まで距離と自動車の速度に応じて制御を決める
C. Bの結果に応じて自動車の状態を更新する

ここで、Bで制御を決めるときにNeural Networkを用います。
また、Cでは予め決められたモデルに基づいて自動車の状態を更新します。


##1.2. 強化学習とは
**強化学習**とは、より高い報酬がもらえるようにエージェントの行動を決定する、機械学習の手法の一つです。エージェントはある状態を観測し、その観測に応じて行動を起こします。そしてエージェントの行動に応じて報酬を与えます。その報酬を最大化するように学習するのが強化学習です。

抽象的で何言ってるかよくわかりませんね。例えば、あなたが敵と戦うゲームをする時を思い出してください。敵と遭遇したプレイヤー（あなた）は、その敵に対して「戦う」か「逃げる」を選択することができます。敵を倒せば報酬が手に入りますが、敵に倒されるとゲームオーバーとなります。また、強い敵を倒せば報酬が多く手に入ります。

![discription_game.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/fa43fe6f-8fc4-d4cb-01fc-ee3f5fcc583a.png)

このとき、報酬を多く手にしたいあなたはどんな行動をとればいいでしょうか。そうです。勝てる敵と戦い、勝てない敵からは逃げればいいのです。では、弱い敵をずっと倒していけばいいでしょうか？確かに報酬はもらえますが、弱すぎると報酬も少ないので、ちょうどいい強さの敵を倒す方が効率が良いです。

![discription_game_policy.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/46783360-2296-92a2-0c47-8cc4ed439f4b.png)

つまり、より多くの報酬を得ようと思ったら、敵の強さを正確に見極め、強さに応じて行動を決定する必要があります。

しかし、ゲームを始めたての頃は

* （自分より）強い敵に挑んで負ける
* 弱い敵から逃げて報酬を逃す
* 弱すぎる敵に挑み続けるため報酬がたまらない

ということがあるかもしれません。ですが、ゲームを繰り返しプレイしていくうちに

* 強い弱いの判断が正確にできる
* 自分の強さに適した敵に挑むことで効率よく報酬をためることができる

ということができるようになります。

これを機械が行うのが強化学習です。すなわち、敵の強さを判断する材料（**状態**）を確認（**観測**）し、あなた（**エージェント**）が「戦う」か「逃げる」かを選択（**行動**）し、**報酬**を多くもらえるような判断ができるようになる（**学習**）のを機械が行うのが強化学習です。また、ゲームでは敵に倒されるかクリアするまでゲームが続きますが、ゲームが1回終了するまでのことを**エピソード**と呼びます。

![discription_rl.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/26652dfe-4210-18d6-4c97-6a65ebccc271.png)

上記のことを自動運転に置き換えると、周囲の状況（状態）を認識（観測）し、加減速やステアリング角度（行動）を決める際に、壁にぶつからずに走れる（高い報酬が得られる）ように学習します。

壁にぶつからずに走れるようにするために、今回は**方策勾配法**という手法を用います。自動車の制御には、自動車の状態を入力、加速度とステアリング角度を出力としたNeural Networkを用いており、方策勾配法によってこのNeural Networkを最適化します。

# 2. 使ったもの
##2.1. 自動車の運動モデル
自動車の挙動は自動車の位置、速度、向き、ステアリング、加速度によって決まります。今回はステリング角度と加速度の二つを操作することで自動車の挙動を制御します。
簡単のために、ステアリング角度は自動車の向きにのみ影響し、ハンドルを$\phi$だけ回転させると、自動車は1秒間に$\phi$だけ回転するとします。また、加速度は自動車の進行方向の速度にのみ影響するとします。
この仮定の下、自動車の状態の更新は下図のように行います。

位置の更新
![discription_update_position.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/cfdac679-226f-974f-688b-697356eda173.png)

速度の更新
![discription_update_velocity.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/3a171a88-362a-9b04-ef31-88ec15b5d471.png)

方向の更新
![discription_update_angle.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/6b1d736c-a0a7-6814-043d-c0a8be7d9613.png)

これを数式に表すと以下の通りです。

```math
\begin{align} 
x_{t+1} &= x_t + v_t\Delta t\cdot cos\theta_t \\
y_{t+1} &= y_t + v_t\Delta t\cdot sin\theta_t \\ 
v_{t+1} &= v_t + a\Delta t\\
\theta_{t+1} &= \theta_t + \phi\Delta t
\end{align}
```
ここで$x_t$および$y_t$は時刻$t$におけるx座標とy座標、$v_t$は自動車の進行方向の速度、$\theta_t$は自動車の進行方向のx軸からの角度です。$a$は自動車の加速度、$\phi$はステアリング角度です。自動車の状態を更新する際にはこの式を使って更新します。


##2.2. 壁の認識方法
壁の認識にはLiDARを想定します。

> LiDARとは（[「LiDAR」とは何か、自動運転で注目の光センサー技術をわかりやすく解説](https://www.sbbit.jp/article/cont1/36559)より引用）
>LiDARとは「Light Detection and Ranging」の略であり、「ライダー」と読む。
>LiDARは、レーザー光を走査しながら対象物に照射してその散乱や反射光を観測することで、対象物までの距離を計測したり対象物の性質を特定したりする、光センサー技術のことである。

ここでは自動車から前方に15本のレーザー光を照射することとします(下図参照)。壁の座標はレーザー光が描く直線と、壁となる直線の交点により求めます。また、レーザーの届く範囲を限定し、レーザーの届く範囲外の壁は認識しないようにします。
![discription_LiDAR.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/b2f0d578-b789-d2fa-39a3-b16aa049be6c.png)

図の黄色の点線がレーザー光、緑線が壁、赤の点線がレーザーの届く範囲を示しています。青丸は壁と認識した点を表し、黒丸はレーザーが壁に当たらなかったことを表しています。

壁に当たらなかった場合は壁までの距離をレーザーの届く距離とします。


##2.3. Neural Network
Neural Networkの入力には自動車の壁との距離と現在の速度を使います。出力はそれぞれの行動をとる確率です。

![discription_NN.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/d25df551-b4cf-1d69-8d51-2c81c2cf3d0f.png)
制御する際のステアリング角度は$-90°, -45°, 0°, 45°, 90°$の5通りあります。角度が正のときは左へハンドルを切り、負の時は右へハンドルを切ります。
また、加速度も5段階あり、$-1, -0.5, 0, 0.5, 1m/s^2 $です。加速度が正のときは加速し、負の時は減速します。
これより、取りうる行動は5x5通りあります。Neural Networkの出力はそれぞれの行動をとる確率を出力し、その確率に応じて次にとる行動を決定します。


Neural Networkのパラメータは、次式を目的関数として更新します(導出は[A.1 (A)式の導出](#a1-a式の導出)をご参照ください)。

```math
\begin{align} 
J(\theta) &= \frac{1}{M}\sum_{m=1}^{M}\frac{1}{T}\sum_{t=1}^{T}\log\pi_{\theta}(a_{m,t}|s_{m,t})~(r_{m,t}-b) \tag{A}  \\ 
where~ b &= \frac{1}{M}\sum_{m=1}^{M}\frac{1}{T}\sum_{t=1}^{T}r_{m,t}
\end{align}
```
ここで、$M$はエピソード数、$T$は1エピソードのステップ数です。$\pi_{\theta}(a_{m,t}|s_{m,t})$は方策パラメータを$\theta$に固定したとき、エピソード$m$のステップ$t$における状態$s_{m, t}$で行動$a_{m,t}$を取る確率です。$r_{m, t}$はエピソード$m$のステップ$t$で貰った即時報酬、$b$は全エピソード全ステップの報酬の平均です。



# 3. 実行結果
##3.1. 分岐を含まない場合
実際に走らせた結果を以下に示します。まずは単純な正方形の道路を走らせたときの結果です。
1エピソードは最大200ステップとし、壁にぶつかったらそのエピソードは終了します$(T\leq200 )$。
これを50エピソード行った結果を使ってNeural Networkを更新します$(M=50)$。Neural Networkの更新は50回行います。
Neural Networkの更新直後のエピソードでの自動車の軌跡を下図に示します。下図では10epochずつ表示しています。

![result_all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/b8178720-01eb-39d3-95e9-112516528559.png)


緑線が道路の壁、曲線が自動車の進んだ軌跡を表しています。これを見ると1エピソードの走行距離が少しずつ伸びている様子が見られます（前半にも走行距離が長いエピソードがあったり、後半にも短いエピソードがあったりしますが、自動車の挙動は確率で決まるのでそういうこともあります）。

下の図は各エピソードでもらった報酬のepoch毎の平均を表したグラフです。
![rectangle_003_mean_reward_label.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/e600ca56-23a2-7d94-0b42-3eb44669bbf0.png)
これを見ると、後半になるにつれて報酬の平均が高くなる様子がわかります。
これより、強化学習を用いて自動車が壁にぶつからないように制御することができました。


##3.2. 分岐を含む場合
次に、分岐を含む道路を走らせた場合の結果を示します。このときも道路以外は先ほどと同様の条件で強化学習を行いました。

![result_all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/1dbeec1e-95d7-fcc0-6be4-7639c5e481d3.png)
これを見るとほぼすべてのエピソードで、最初の分岐で左に曲がっていることがわかります。おそらく左に進んで長く走ることができたエピソードが序盤であったために、左に曲がるのがよいと学習してしまった結果だと思います。

下の図は各エピソードでもらった報酬のepoch毎の平均を表したグラフです。
![T_load_wo_barriers_004_mean_reaward_label.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/7480e437-e6b5-a1f5-371d-9cef148f38a8.png)
これも後半になるにつれてもらえる報酬が多くなっていますが、報酬の値は正方形の道路を走らせたときよりも小さくなっています。これは、ただの正方形のときとは異なり、T字路で左右のどちらかに曲がる判断が必要なため、そこでの学習のためにより多くの更新回数が必要だったからと考えられます。

# 4. 課題
今回は正方形は左回りのみを走らせましたが、右回りでも同様に学習することができるのか、左折と右折を繰り返すような道路ではどうなるのかを確認していないので、次回以降はこれらを試してみたいと思います。
さらに、分岐を含む道路を走らせるときは、分岐の片方だけを進むことが多いので、工夫して両方の道路を走らせられるようにしたいです。

# 5. おわりに
強化学習を用いて、自動車から壁までの距離を認識し、これをもとに自動車の挙動を制御することができました。



# Appendix
##A.1 (A)式の導出
**方策勾配法は**、$\theta$をパラメータとする方策$\pi_\theta $に対して、$\pi_\theta$を固定したときにもらえる1エピソードの報酬の期待値$J(\theta)$を確率的勾配法などで最大化する方法です。ここで、$J(\theta) $は次のように表せます。

```math
J(\theta) = V^{\pi_{\theta}}(s_0) \tag{A1} \\
```
$V^{\pi_{\theta}}(s_0)$は初期状態$s_0$の価値です。状態$s$の価値は、状態$s$にいることで将来報酬がどれほどもらえるかによって決まります。そして、状態$s$にいることでもらえる報酬の期待値は、状態$s$でとることのできるすべての行動$a$についての報酬の期待値であると言えます（下図参照）。
![discription_V(s).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1101413/17799298-831c-d141-9b4d-c4d7d8e25355.png)
上記を式としてあらわすと、次式のようになります。

```math
\begin{align}
V^{\pi_{\theta}}(s_0) &= \sum_{a}{\pi_{\theta}(a|s)Q^{\pi_{\theta}}(s,a)} \tag{A2}
\end{align}
```
ここで、$Q^{\pi_{\theta}}(s,a)$は方策を$\pi_{\theta}$で固定したとして、状態$s$で行動$a$をとったときにもらえる報酬の期待値です。
よって、$(A1)$式と$(A2)$式より次式が成り立ちます。

```math
\begin{align}
J(\theta) &= V^{\pi_{\theta}}(s_0) \\
&= \sum_{a}{\pi_{\theta}(a|s)Q^{\pi_{\theta}}(s,a)}   
\end{align}
```

この$J(\theta)$が最大となる$\theta$を確率的勾配法などを用いて求めます。
確率的勾配法を用いるときの$\theta $の更新式は次式のようになります。

```math
\theta \leftarrow \theta + \alpha \nabla_{\theta}J(\theta)\\
```

ここで$\nabla_{\theta}J(\theta)$は**方策勾配定理**を用いて次式のように表せます。

```math
\begin{align} 
\nabla_{\theta}J(\theta) &= \mathbb{E}\left[ \frac{\partial\pi_{\theta}(a|s)}{\partial\theta}\frac{1}{\pi_{\theta}(a|s)}Q^{\pi_{\theta}}(s,a) \right]\\
&= \mathbb{E}\Bigl[ \nabla_{\theta}\log{\pi_{\theta}}(a|s)~Q^{\pi_{\theta}}(s,a) \Bigr]
\end{align} 
```

方策勾配定理の導出は[こちら](http://seiya-kumada.blogspot.com/2018/02/blog-post_13.html)をご参照ください。

さて、上式には$Q^{\pi_{\theta}}(s,a)$が含まれますが、連続的な空間でそれぞれの行動の価値を計算するのは非常に難しいです。なぜなら、連続的な空間の場合、状態の数は無数にあり各状態で起こせる行動も無数にあるからです。このような場合には$Q^{\pi_{\theta}}(s,a) $を実際に貰った報酬で近似します。この方法を用いると$ \nabla_{\theta}J(\theta)$は次式で表せます。

```math
\begin{align}
\nabla_{\theta}J(\theta) &\approx \frac{1}{M}\sum_{m=1}^{M}\frac{1}{T}\sum_{t=1}^{T}\nabla_{\theta}\log\pi_{\theta}(a_{m,t}|s_{m,t})~(r_{m,t}-b)\\
where~ b &= \frac{1}{M}\sum_{m=1}^{M}\frac{1}{T}\sum_{t=1}^{T}r_{m,t}
\end{align}
```
ここでは$T$ステップからなるエピソードを$M$回繰り返し、得られた報酬の平均を取って$Q^{\pi_{\theta}}(s,a)$を近似しています。$r_{m,t}$は$m$番目のエピソードの$t$ステップ目で得られた報酬、$b$は得られた報酬の平均です。$T$はエピソードごとに異なっていても構いません。

右辺の$\nabla_{\theta}$は$\sum$の外に出すことができる[^1]ので以下のようになります。

```math
\nabla_{\theta}J(\theta) \approx \nabla_{\theta}\left[\frac{1}{M}\sum_{m=1}^{M}\frac{1}{T}\sum_{t=1}^{T}\log\pi_{\theta}(a_{m,t}|s_{m,t})~ (r_{m,t}-b)\right]\\ 
```
これより$(A)$式を導くことができました。

[^1]: 即時報酬rは状態に対してのみ与えられ、行動によらないので、どのような方策を取ろうが報酬には関係ないからです。

# 参考文献
* LiDARについて
 - [「LiDAR」とは何か、自動運転で注目の光センサー技術をわかりやすく解説](https://www.sbbit.jp/article/cont1/36559)
* 方策勾配法について
 - [強化学習の基本的な考え方](https://qiita.com/qiita_kuru/items/2c00a81b4b26bf9ad210)
 - [深層強化学習アルゴリズムまとめ](https://qiita.com/shionhonda/items/ec05aade07b5bea78081)
 - [【強化学習】方策勾配法の仕組みと学習のワークフロー](https://dajiro.com/entry/2020/05/19/170402)
 - [強化学習 〜方策勾配定理の導出〜](http://seiya-kumada.blogspot.com/2018/02/blog-post_13.html)


(この記事は研究室インターンで取り組みました：https://kojima-r.github.io/kojima/)