#前書き
春休みの間を利用して安全工学に関する強化学習による研究を進めていたが、どうにも具体的な形にまで昇華できなさそうであるので、今回できた分までを背景と並べてここに示す。
#強化学習と研究背景
##迷路問題
強化学習において、迷路問題は良く取り扱われる問題の1例である。
実装の例としてはこちらを参考にした。
説明：
図で示したような迷路で、S(start)からG(Goal)までの道筋を学習することが目的となる。今回はQ学習でε‐greedy法を用いて学習を行っていく。
Q学習ではそれぞれのマス目に対して取れる移動の選択肢(方策)が定められていて、その方策ごとに行動価値が決まっている。あるマス目である方策をとった場合、その移動先の行動価値の最大値との差をある割合で増加させて、そのマス目におけるその方策の行動価値を更新する。
もう一つ、Goalにおいてはある一定の行動価値が定められていて、Goalに到着する方策はその報酬により行動価値を更新して迷路を解く1セットを終了する。
行動価値Qの更新式の基本形は以下のようになる。
$$Q(s,a)\leftarrow Q(s,a) + \alpha[r+\gamma*max_{a'}Q(s',a')-Q(s,a)]$$
$Q$：行動価値
$s$：状態(エージェントの位置、マス目)
$a$：行動
$\alpha$：学習率
$\gamma$：時間割引率
$r$：報酬
としてあたえられる。$s', a'$は1つ先の状態(すなわち、決定された行動先の行動価値)であることを表している。
上の式を見ればわかる通り、Q学習における更新は1つ先のマス目の行動価値Qとの差を更新の駆動力としているので、もし最初に与えられる各マス目のQの値が一律0であるならば、エージェントはstartから各マスをランダムに動き回り、偶然Goalにたどり着く方策を取得した場合のみそのマスの行動価値が更新される。
これは実際その通りであって、最初にうちはランダムな探索を行い報酬を得て、だんだんとGoalやその近辺のマスからStartへ向かって行動価値が伝播していく。
一方で、上式では一旦行動価値がStartからGoalまで決定された場合にその経路のみを絶対に通ってしまう(ほかのマスは0なのでそちらに移動する方策は選択されない)という欠陥がある。そこで、方策決定の際にある確率εでランダムに行動をとるようにして、だんだんとεの値を減らしていく計算方法がとられる。これがε‐greedy法の簡単な説明である。
##研究背景
安全工学のの中では火災という災害は1つの大きな研究対象である。火災時の避難について、既往の研究においては実験と計算から様々な報告がなされている。例としては、迷路を用いた火災避難行動の模擬などがある。計算においては
- 人間行動を粒子運動と解釈して運動方程式を解くモデル
- セルオートマトンモデル
などが頻繁に議論の俎上に上がるが、どちらも環境に対する情報や環境依存の顕著なルールが計算に用いられる現状がある。そのため、多くの研究が実際の火災事例の検証とともに論じられており、避難行動の予測に関しては疑問が浮かび上がる。
そこで、ここで考えるのはQ学習による迷路問題を応用して火災発生から避難までの最適経路の計算とその定量的な考察をしてみようというアイデアに基づく研究である。
この手法の一つの利点としては、事前に設定するパラメータの環境依存が少ないという特徴がある。また、報酬や方策の設定如何によりアルゴリズムのルール設定を増やすことなく大きな拡張性を持つことが予想される。
#Q学習による迷路問題
コードを張り付けることが早いだろう。
Q学習による解法
import numpy as np
import matplotlib.pyplot as plt
#decide the direction to move by Q table and random probability epsilon
#and convert it as movement on the map.
def decide_action(status, maze_row, q_table, maze_map, epsilon):
direction=["up", "right", "down", "left"]
if(np.random.rand() < epsilon):
#at random choice
direction_to=np.random.choice(direction, p=maze_map[status])
else:
#direction is selected at max Q value direction
direction_to=direction[np.nanargmax(q_table[status])]
#convert direction to map information at matrix
if(direction_to=="up"):
status=status-maze_row
action=0
elif(direction_to=="right"):
status=status+1
action=1
elif(direction_to=="down"):
status=status+maze_row
action=2
elif(direction_to=="left"):
status=status-1
action=3
return status, action
#q_learning function to update the Q_value
def q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward):
#setting of reward
if(next_status==goal):
r=reward
else:
r=0
#update fomula of Q_value
q_table[status][action]+=alfa*(r+gamma*(np.nanmax(q_table[next_status])-q_table[status][action]))
return q_table
#solve and update the maze at once
def goal_once(start, goal, maze_row, maze_map, q_table, alfa, gamma, reward, epsilon):
flag=True
history_move=[]
#initialize
status=start
#solve maze until it gets the goal
while(flag):
next_status, action=decide_action(status, maze_row, q_table, maze_map, epsilon)
q_table=q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward)
#record the history of action
history_move.append([status, action])
#flag of goal
if(next_status==goal):flag=False
#status update
status=next_status
return q_table, history_move
move_0=np.array([0, 0, 0, 0])
move_w=np.array([1, 0, 0, 0])
move_d=np.array([0, 1, 0, 0])
move_s=np.array([0, 0, 1, 0])
move_a=np.array([1, 0, 0, 1])
move_wd=np.array([1, 1, 0, 0])/2
move_ws=np.array([1, 0, 1, 0])/2
move_wa=np.array([1, 0, 0, 1])/2
move_ds=np.array([0, 1, 1, 0])/2
move_da=np.array([0, 1, 0, 1])/2
move_sa=np.array([0, 0, 1, 1])/2
move_wds=np.array([1, 1, 1, 0])/3
move_wda=np.array([1, 1, 0, 1])/3
move_wsa=np.array([1, 0, 1, 1])/3
move_dsa=np.array([0, 1, 1, 1])/3
move_wdsa=np.array([1, 1, 1, 1])/4
###input form###
maze_map=np.array([move_ds, move_dsa, move_dsa, move_dsa, move_sa, \
move_wds, move_wdsa, move_wdsa, move_wdsa, move_wsa,\
move_wds, move_wdsa, move_wdsa, move_wdsa, move_wsa,\
move_wd, move_wda, move_wda, move_wda, move_wa])
q_table=np.where(maze_map==0.0, np.nan, 0)
maze_row=5
maze_columns=4
start=0
goal=19
reward=1
time_of_episode=100
alfa = 0.10 # 学習率
gamma = 0.92 # 時間割引率
epsilon = 0.99 # ε-greedy法の初期値
probability_reduce_rate=1.04
###input form end###
history_move=[]
size_of_epi=[]
episode = 1
flag=True
while(flag):
q_table, history_move=goal_once(start, goal, maze_row, maze_map, q_table, alfa, gamma, reward, epsilon)
print("this is episode: {0:5d}, steps to goal are {1:5d}".format(episode, len(history_move)))
size_of_epi.append(len(history_move))
if(time_of_episode==episode):
flag=False
episode=episode-1
episode+=1
epsilon=epsilon/probability_reduce_rate
q_table=q_table/np.nanmax(q_table)
direcion=["↑", "→", "↓", "←"]
for i in range(len(history_move)):
print(direcion[history_move[i][1]])
plt.plot(size_of_epi)
plt.show()
q_table[goal]=1.0
np.set_printoptions(suppress=True, precision=4, floatmode='maxprec')
#print(maze_map)
print(q_table)
q_table_max=np.zeros(goal+1)
for i in range(len(q_table)):
q_table_max[i]=np.nanmax(q_table[i])
print(q_table_max.reshape(maze_columns, maze_row))
q_table_max=q_table_max.reshape(maze_columns, maze_row)
plt.figure(figsize=(10, 5))
plt.imshow(q_table_max, interpolation='nearest', vmin=0 ,cmap='YlOrRd')
plt.colorbar()
plt.show()
下に計算結果を示してあるが、左上から右下にゴールする迷路で極めて明瞭に行動価値が伝播してGoalまでの道筋ができていることがわかる。
##火災の模擬
これを拡張して、火災発生時の避難行動の学習を模擬してみる。
ここではGoalに報酬を置いただけのモデルであるが、簡単な拡張として火災に見立てたマスを用意してそこにたどり着いた時に負の報酬を与えるものとする。また、負の報酬を持つマスについた場合もゲームを1セット終了とする。すなわち、エージェントはStartから知識0の状態で出発して、何度も死に戻りをしながらGoalを目指すわけである。
###結果
上がその計算結果であるが、なかなか面白い結果が得られた。Q学習の更新式をもう一度見てみよう。
$$Q(s,a)\leftarrow Q(s,a) + \alpha[r+\gamma*max_{a'}Q(s',a')-Q(s,a)]$$
以上の式に基づいて各マス各方策の行動価値が更新されるが、上の式ではすべての更新が行動先の最大値を反映させるようになっているので、負の報酬を与えても周辺の1マス以外はMax関数で無視されてしまう。
Q学習の上の更新式は楽観的な行動価値の計算式なので、簡単に言えば隣に大きな負の報酬が存在しても最良の経路をとる。隣で炎が燃え盛っていても、そこが最短経路ならそこを通るように計算してしまうという問題点がある。
###悲観的な更新式
ここで少し悲観的なエージェントを考えてみる。Pessimismというパラメーターを与えて、
$$Q(s,a)\leftarrow Q(s,a) + \alpha[r+\gamma*max_{a'}Q(s',a')-Q(s,a)]$$
$$Q(s,a)\leftarrow Q(s,a) + \alpha[r+\gamma*(max_{a'}Q(s',a')/(1+pessimism)+min_{a'}Q(s',a')*pessimism/(1+pessimism))-Q(s,a)]$$
上の式を下の式のように改変する。つまり一定の割合で行動先の行動価値の最低値を見積もるように改変する。pessimism=0なら元の更新式と同じに、pessimism→∞なら各マスの行動価値の最低値のみを評価して学習するプログラムになる。
具体的には、
#q_learning function to update the Q_value
def q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward, pesimism):
r=0
#setting of reward
for i in range(len(goal)):
if(next_status==goal[i]):
r=reward[i]
#update fomula of Q_value
q_table[status][action]+=alfa*(r+gamma*(np.nanmax(q_table[next_status])-q_table[status][action]))
return q_table
該当箇所の関数を
#q_learning function to update the Q_value
def q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward, pesimism):
r=0
#setting of reward
for i in range(len(goal)):
if(next_status==goal[i]):
r=reward[i]
#update fomula of Q_value
q_table[status][action]+=alfa*(r+gamma*(np.nanmax(q_table[next_status])/(1+pesimism)\
+np.nanmin(q_table[next_status])*pesimism/(1+pesimism)-q_table[status][action]))
return q_table
と書き換える。
これで計算をしてみると。
きちんと火災発生個所を回避するような経路が選択されていることがわかる。
##中規模迷路の行動価値マップ(ポテンシャル)
以上の知見を踏まえて、迷路の規模をさらに拡大した状態で、迷路の各マスからGoalまでの道順を学習させ、さらにそこから得られた行動価値を平均化して、迷路全体からGoalまでのヒートマップを作製した。
ヒートマップ自体に本質的な意味はないが、火災の発生時にどの程度のリスクが生じて、どのような経路の選択の変化が起きるのかを分かりやすく示すうえで有用であると考えられる。
上部中央をゴールとしている。
火災なし：
火災あり：
フロア右側で火災を発生させた場合、右側のスペースの行動価値が著しく下がることがわかる。一方で中央下部の2本の経路のうち左側の通路がより行動価値が高く選好されることがわかる。
火災を単一の負の報酬マスとみなした場合でもなかなか面白い結果が得られた。
#問題点
冒頭で自主研究と宣言したが、これがまだ具体的な形にならないのには以下の問題点がある。
####マルチエージェント化
火災発生時の人の流動は言うまでもなくマルチエージェントなタスクを解く必要がある。また、実際の避難行動の特徴として
- 避難者はリーダー(知識のある係員)などに従う。(これは行動価値関数の共有とみなせる)
- 案内板や避難誘導などは一定の効果がある。(特定のマスに報酬や方策を設定する必要がある)
- 出口付近では混雑が発生して人の流動性が落ちる。(もちろん、逃げるのが遅れるので、あとから脱出する人ほど報酬を漸減するように設定する必要がある)
このような実際の避難行動の特性を考慮に入れたうえで学習を行う必要がある。それに比べると今回のプログラムはQ学習の改良で終わっている。
####火災の特徴の組み込み
火災時の避難行動では火災それ自体が時間とともに大きく変化する。避難行動における一番の大きな要因は煙である。
煙の横方向の移動速度は大体人間の歩行速度程度といわれるが、拡散の特性、移動速度や方向などはさらに吟味する必要がある。ターンごとに負の報酬領域を時間発展させることが有効なアルゴリズムとして考えられるが、実際の火災の避難行動の実験では、火災の煙が人の視界を遮ること、歩行速度を低下させることなどが指摘されており、その効果を負の報酬だけで表現していいものかは不明である。
####人間の避難行動のジレンマ
先ほど述べたように、人間の避難行動には実験から観測された特徴的な行動がある。影響力のあるリーダーについていくこと、とりあえず人についていく群集行動なども知られている。たとえ出口が狭くほかの出口に向かうほうが効率的でもこのような行動は起こりうる。
問題は強化学習で学習した最適な経路が、人間の非合理性や本能といった部分を鑑みたときに最適とは限らないということである。パニックに陥る人もいる中で果たしてどこまでの非合理的な行動を報酬に落とし込めば、それが人間行動にとって最適といえるのかが最大の問題となってくる。
##展望
結局計算のほうはサーバー側で高速に処理して、避難者それぞれに最適な避難経路を提示できるようになったら面白いかも程度に考えている。既往のセルオートマトン法などに比べて環境依存のアルゴリズムが少ないというのはこのあたりの拡張性にも効いてきそう。
都市交通や駅の乗り換えなど、この辺りの分野ではすでに実用化されているのだろうか？
何か有益な文献があれば教えていただけると幸いです。
####結び
※参考文献の数が多いので略させていただきます。参考文献に興味があれば御一報ください