Python
強化学習
DQN
MXNet
エレベータ

免責

ぜんぜんわからない、俺は雰囲気で強化学習をやっている。
まぁいろいろ間違ってるかもしれないけど、教えてくれれば直すから教えてね。

2018-05-17追記:シミュレータにバグがあったので修正したら、性能が下がりました

ことはじめ

私自身はこの人をフォローしていないのですが、リツイートによって私のTLに流れてきました。

あれ、エレベーターってたしかにむずいぞ…
ボタンが押されたりして状況が変わる度に最適化問題を解き直さないといけないよな。あれでも、そもそもの最適化がすげえNP困難っぽい感じだぞ?ていうかそもそも一つの階に何秒止まるのかとか客の数によるじゃん。アッ、これ強化学習なんじゃ?ん?強化学習だと思えばまだなんとかなるんじゃ…?というわけで強化学習で速いエレベータを求めたいっ!!

昔、The Towerっていうビルの経営シミュレーションゲームがあって、孫正義がビルの最上階のレストランで食事を食うから、専用のエレベータを設置して接待してたりしたんだけど、ゲームになるくらいむずいんだよな、エレベータの最適化ってのはさ!!でも最近の強化学習もすごいって聞くぞっ!!関係ないけど、当時の孫正義は、まだそこまで大金持ち感出てなかったよね。あの悪評高いYahoo! BBモデム配布あたりで頭角を表わし、そのままiPhoneの人みたいになって今に至るみたいな感じかな。どうでも良いですね。

ちなみにThe Towerに登場する客は、ほっとくと5Fのレストランのランチに行くためのエレベーターを1Fで夜まで待っていたりしやがるっ!!脳味噌が足りない。
このような悲劇を繰り返さないためにもエレベータ業界に殴りこみをかけないといけないと決心したのであります。42歳、厄年。モッズ系。
The Towerはエレベータの設置を含めたビルのデザインのゲームですが、私は上のツイートの通りエレベータそのものの動きのアルゴリズムを考えてみたいと思います。

良いエレベーターとは

まずは評価系から考えていきたいと思います。あるエレベータ制御プログラムがあった時にどうやってその良さを評価すれば良いか。人民はエレベータに何を求めているのかっ!

まぁ所要時間ですよね。10年以上前からすごく気にいってるラーメン屋があるんです。昔は神田川の近くにあって、今は四谷にあるラーメン屋なんですが、そこは数年前になんかのグルメ雑誌で紹介されてしまってからというものの1時間以上行列になるのが当たり前になってしまって、非常に悲しい思いをしています。所要時間ってのは大事なんです。

でも1Fから25Fに行く人の時間と1Fから3Fに行く人の時間を単純に比較することはできないですよね。なので、理想的な所要時間と比べてどのくらい遅くなったかを考えたいと思います。

ここではエレベータに乗る人をナンバリングして考えます。$i$番目にエレベータに現われた人を番号$i$で表わします。
まず、$i$番目の人が理想的なエレベータに乗った場合にかかる時間$T_i$を考えます。
エレベータの早さを$v$ (単位:フロア数/秒)、$i$さんの現われた階を$s_i$、$i$さんの目的階を$d_i$とすると、$T_i$はこんなふうに書けます。

T_i = \frac{|s_i - d_i|}{v}

時間は距離わる速度っ!!はい簡単ですね。$T_i$が定義できた後は、$T_i$と実際の所要時間の比を見てあげれば、エレベータがどのくらい快適だったかを表わせそうな気がします。ちなみに後述する世界設定では$v = 1$ (フロア/秒)ということになっているので計算はクソ楽です。んで、この理想所要時間$T_i$と実際にかかった時間の比$r_i$を取ります。

r_i = \frac{T_i}{t'_i - t_i}

ここで、$t'_i$は$i$さんの目的階への到達時刻、$t_i$は$i$さんがエレベータに並びはじめた時刻です。

まぁここまで定義しちゃうと、あとは簡単ですね。すべての人$i$にたいして、$r_i$の平均をなるべく大きくしてあげるようなエレベーターの制御アルゴリズムが良いアルゴリズムです。本当の顧客満足度は、たとえばエレベータが清潔かとか、ずっと乗ってる変なオッサンが居ないかとか、そういうのでも決まるんでしょうけど、工学の世界では一つの目標をシャープに達成しましょう。理想の所要時間と実際の所要時間の比を最大化する、それが私の最初の気持ち。

じゃあ実際に一等地にビルを買って、いろんなアルゴリズムでエレベータを建造して$r_i$の平均を計算してみましょう。実際の来客の分布も性能に依存してくるので、テナントも募集して人が個別の目的を持って各フロアに移動するようにしましょう。テナントからの家賃収入だけで食っていけるようになれば、エレベータの速度なんてどうでも良い些細な問題になっているはずです。これで問題解決ですね。

Hello World

このようにして私は、米の代わりにキャビアを食べ、味噌汁の代わりにシャンパンを飲む生活をしていたわけです。しかし、バブルを経て無一文になったその時、最初の疑問がまた戻ってきました。私が本当にしたかったのは、エレベータの理想の所要時間と実際の所要時間の比を最大化することだったハズ…金に踊らされていた私は本当に人間だったのでしょうか。謙虚な姿勢で速いエレベータのアルゴリズムについて研究し続けていれば、今ごろ、ささやかな幸せを得ることができたのではないだろうか。後悔しても、もう遅いのです。お金もビルもないのです。もうエレベータでの実験はできないのです。人生の転落はエレベータより速かった…

そういう時に役に立つのがシミュレータですね。
今回はシミュレータで25階建てのビルを10台のエレベータ(定員10名)で切り盛りすることを考えます。

エレベータ本体のシミュレーション

客が乗っている時のエレベータの動きは、かなりカッチリ決まっているので、実際のビルのエレベータを参考にして以下のように動きを定義しました。

  • 最初に乗った客に応じて上向き/下向きモードに切り替わる
  • 最後の客が乗った後3秒は扉をあけっぱなしにして次の客を待つ
  • 上向きモードの時は上に行く客/下向きモードの時は下に行く客しか受け付けない
  • エレベータ内部の客がボタンを押した階は必ず止まる
  • 一秒間に1フロア進む

ここまでかっちり決まっていると、逆にプログラムで制御できるところなんてほとんどないと思うのですが、まだ実は裁量があります。具体的には制御アルゴリズムは以下のようなことに関して判断を下さないといけません。

  • 外の客がボタンを押した時、何処に止まるか (止まらないでスキップしてもオーケー)
    • ただし、一回客を受けいれてしまうと進行方向については制御できなくなる。
  • 客が乗っていない時に、どこで待機すべきか

今回の目的はこの裁量を最大限に活かして、なるべく速いエレベーターを作ることだと言えます。一度失意のずんどこまで落ちた私を再度最上階に届けるために…

世界のシミュレーション

シミュレータで次に大事なのは乗る人と目的地のシミュレーションです。どういうテナントが何処に入っているのか。どういう客が何を目的に来るのか。コンピュータによるシミュレーションなので、単純化して扱いましょう。人間とは各時刻、各階ごとに異なる出現確率によって産み出される何かで、$i$番目に生まれた人は時刻$t_i$に$s_i$階に現われ、$d_i$階に行こうとしている、というレベルまで単純化します。1

そして人間の出現ですが、これはポアソン分布に従っていると考えます2
つまり、時刻$t$にフロア$f$に現われる人数を$n_{t, f} \sim Po(\lambda_{t, f})$とします。
現われた人間の目的地ですが、各時刻$t$、各$f$毎に25次元の離散確率分布$\theta_{t, f} \in \Delta^{24}$があって、それに従って$d_i \sim \theta_{t_i, s_i}$としましょう。同じ階から同じ階に行く確率はゼロとします。つまり$\theta_{t, s, s} = 0 \; (\forall s)$。

$\theta_{t, f}$と$\lambda_{t, f}$はシミュレータの設定ファイルに書いておくことにしました。
というわけで、こんな感じで以下の特徴を持った世界を作りました。Hello World!!

  • 一日は57600秒 (8:00から24:00の16時間を想定)
  • $0 \leq t < 7200$の時、つまり最初の二時間は朝モード
    • 朝モードは$\lambda_{t, 1} = 0.5$で$\lambda_{t, f} = 0.005\; (f \neq 1)$
      • この場合、$\lambda$は1秒間に来る人数の期待値なので、朝モードでは1Fに1秒に0.5人、つまりだいたい2秒に一人、その他のフロアではだいたい3分に一人来るくらいの感じ。
    • 朝モードでは$\theta_{t, f}$は一様 (ただし同じ階に行く確率はゼロ)
  • $10800 \leq t < 18000$、つまり11:00から13:00は昼モード
    • 昼モードでは$\lambda_{t, 1} = 0.1$, $\lambda_{t, 4} = 0.4$で他の$\lambda$は0.0005
    • 4Fにレストランフロアがあるという脳内設定
    • 行き先確率はどの階からでも4Fに行く確率が他の確率の10倍になるように調整
  • 最後の3時間は退勤モード
    • 退勤モードは$\lambda_{t, 1} = 0$で$\lambda_{t, f} = 0.02\; (f \neq 1)$
    • 行き先は1Fに行く確率が他に行く確率の10倍になるように調整
    • 21時でやっと退勤モード。この世界はかなりブラック企業で満ち溢れている。
  • 上のどのモードでもないときは普段モード
    • $\lambda_{t, 1} = 0.15$, $\lambda_{t, 4} = 0.02$で$\lambda_{t, f} = 0.01\; (f \notin {1, 4})$
    • 行き先階は一様、つまり朝モードと同じ

とまぁ、かなり恣意的に世界を作ったのでした。まぁ真面目にやりたいんだったら、この辺もデータからオンライン推定できんじゃねえの。

世界定義ファイルを以下のように用意しました。手書きで。
https://s3-us-west-2.amazonaws.com/dqn/lifts/src/world.yaml

余談ですが、JSONが嫌いです。私の祖父の代からの家訓でJavaScriptは使うな…と言われてきました。元はといえば祖父の両親がJavaScriptに惨殺されたらしいです。しかし、そんな家訓とは関係なく、以下の理由でJSONが嫌いなので、みなさんもっとYAMLを使いましょう。

  • コメントが書けない
  • カンマのせいでプログラムで生成するのが少しめんどう
  • JavaScriptとも微妙に違うのがめんどい

YAMLはYAMLで仕様が大きすぎるという難点はあるので、誰かコアの部分だけを抜き出したYAML-coreみたいなを作ってくれないかなぁ。3

目撃DQN

さて、アルゴリズムをどう考えるか。ここでは詳しい説明を省いてDQNを使います。DQNの詳しい説明はウィキペディアでも見てもらうとして、ここではどう使うかだけ書いていきます。強化学習あんまり自信がないからです。
詳しくは、DQNの生い立ち + Deep Q-NetworkをChainerで書いたを読んでください。私も熟読しました。

WIP? 気がむいたら強化学習の説明を素人なりに書くかも。

というわけで、以降は「報酬」をどう定義するか、エレベータの「行動」と「状態」とはなにか、「Q関数」をどういう関数で近似するかなどについて説明します。

報酬の設計

というわけで報酬は、客を送り届けた時に加算される$r_i$にしました。シンプル。
もしかしたら、客を迎え入れる時にも副次的な報酬を渡すようにしたら、もうちょっと学習が安定化したかも?

DQNの学習は安定性との戦いだと言われており、報酬は[-1, 1]の区間におさまっているほうが学習の安定性に寄与すると言われているのだけど、今回の場合、自然に0より大きく1未満の報酬が出てきたので安心しています。

あと、本当のエレベータなら消費電力とかも気になるだろうから、動きに小さなペナルティ(負の報酬)を与えても良いかもなーと思った。実際、リプレイデータを可視化してみると、強化学習版のエレベータはなんかおじいちゃんのようにプルプル震えている。

アクションの設計

各エレベータ毎に

  • 上に行け/下に行け/止まれ
  • 外で人が待っていたら止まるモード/ 外の人を無視するモード

の3 * 2 = 6通り。

エレベータは10機あるので可能なアクションの通り数は6^10になるけど、後述のとおり、DQNの出力は10*6になるようにした。各エレベータ毎に個別の判断を下す感じ。Q関数が線形関数だとこれは非常にまずいと思うが、DQNなら隠れ層がよしなにしてくれるハズ。

状態の設計

  • エレベータ毎の状態
    • 自分の位置 (one-hot; 25)
    • 自分自身のエレベータID (one-hot; 10)
    • 自分自身のモード (3通り:上向き/下向き/客なし) (one-hot; 3)
    • 中の人がボタンを押した階 (25)
  • 共通の状態
    • 時刻 (バイナリエンコード; 16)
    • 外に待っている人がいるか (上向き) (25)
    • 外に待っている人がいるか (下向き) (25)

次元数はエレベータ毎に63, 共通の状態が56なので、63 * 10 + 56 = 686次元。

ふと思ったんだけど、この構造だと24時間稼動できないのな。時刻が16ビットしかないから、18.2時間分くらいしか時刻を表現できない。

あと、外に待っている人がいるかどうかは、単なるBoolの列なんだけど、もし私が不動産王ならエレベータホールに監視カメラつけて、何人待っているかも推定したい。

Deep Qネットワークの設計

Deep Qネットワークはこんな形にしました。

Untitled Diagram.png

この構造が各エレベータ毎に10本あるんだけど、ポイントは全てのパラメータがエレベータ間で共有されている点。これによって、あるエレベータが特定の状況で学んだQ関数の値を他のエレベータが利用できるようにした。最初は単純に全ての状態をまとめてニューラルネットワークにつっこむっていうのをやっていたんだけど、学習がぜんぜん進まなかったので諦めた。ニューラルネット系の話はモデリングが無理筋なのか、それとも時間かければ上手く行くのかの判断がむずいのがしんどくて生きるのが辛い。まじやみ。

挙動が全てのエレベータで同じだと、ふとした弾みで膠着状態になってしまうことがあった。もし、全てのエレベータが同じ位置にいて、全て乗客がいない場合、状態変数が同一になってしまうので、次の挙動も一緒、結果として次の状態変数も一緒、みたいなことになってしまうのです。

今回はそれを状態ベクトルに位置IDを入れることで解決しています。解釈としては状態特徴を加えたというよりも、アフィン変換Bの出力にエレベータID依存のバイアスパラメタを加えたということになります。そこだけが唯一エレベータ間でパラメタ共有していない部分になります。

上の図で示したサブネットワークは普通のDQNと同様にアクションの数(6)と同数の次元数を持つベクトルを出力しているが、実際は上の図の構造が10個あることになります。Q関数は上のニューラルネットの$i$番目のエレベータに対応する出力を$y_i(s_i)$として、以下のように書けます。

Q(s, a) = \sum_{i = 1}^{10} \delta_{a_i}^T y_i(s)

$\delta_{a_i}$はクロネッカデルタのベクトル表現です、小難しい書きかたをしましたがベクトル出力$y_i(s)$から$a_i$番目の要素を取り出してるだけですね。

学習の方法

普通のDQNと同様, Neural Fitting Q-IterationとGrowing batchみたいなアルゴリズムで動いています。
ただ実装めんどかったので、もうちょっと交互最適的なアプローチにしました。

  1. $\Theta_1 \leftarrow$ ランダム初期化
  2. $k \leftarrow 1$
  3. $\Theta_k$を用いてランダムな時刻から3000秒分のシミュレーションを行なう
  4. 過去10回 (最大30000秒分) のシミュレーション結果を用いてQ関数のフィッティング
    1. ランダムに選んだ時刻集合 (ミニバッチ)の要素$t$に対して、$t+1$の最適行動$\hat a_{t+1} = \arg\max_{a'} Q(s_t, a_{t+1}; \Theta_{k+1})$を計算します。
    2. 時刻$t$で得られた報酬$r_t$を最適行動から得られる$t+1$に足して、時刻$t$でのQ関数の目標値$g_t$を得ます。 $g_t = r_t + Q(s_{t+1} , \hat{a}; \Theta_{k+1})$。
    3. $\Theta_{k+1}$を$\frac{1}{2} ||g_t - Q(s_t, a_t; \Theta_{k+1})||^2_2$を小さくする勾配方向に少し動かします (Adamを使いました)

Adamの設定は$r=0.0002, \beta_1 = 0.9, \beta_2 = 0.999, \epsilon=1e-08$です。mxnetのデフォルトに対して学習率$r$だけ調整した感じです。バッチサイズは128です。

世の中の強化学習の人達はシミュレーションとフィッティングを並列に動かしたりするのかな?私は実装がだるかったので交互にコマンドを呼び出してやるようにしました。

ステップ4-1のQの中の$\Theta$が$\Theta_k$でなくて$\Theta_{k+1}$になっているのがDouble DQNというテクニックです。DQNが二人でDouble DQN…

おソース

正直言ってPythonも嫌いだし、ニューラルネットのDefine-By-Runアプローチってやつも嫌いなんですよっ!!でも、まぁ上で既にJSONに対する愚痴を垂れたし、これ以上ネガティブなことは書かないようにします。というかむしろ女騎士みたいなもんなのかもしれない。"くっ…殺せっ…PythonでDefine-By-Runするくらいなら殺してくれ…"と、私の中の騎士がオークに向かって叫んでいるのかもしれない。

まぁこの辺の「僕が考えた最強のDNNツールキット」談義は今度飲みに行った時にでも。

実験

さて、私が手塩にかけて育てたDQNは上手く動いてくれるんでしょうか。上手く動かなくても良い。たくましく育って欲しい。

ベースライン: ルールベース

貪欲に客を取りに行くアプローチをベースラインにします。

  • 自分が空の時に、エレベータが呼ばれたら、呼ばれた方向に向かって動く
  • もし上と下の両方から呼ばれたら、エレベータIDによって挙動を変えて分担する (偶数番台は上優先/奇数番台は下優先)

期待累積報酬: $E[r_i] = 0.495289$

だいたいロス時間が最短時間と同じくらい。そんなに悪い値ではないのでは。実際のエレベーターってこれくらいの気がする。

シミュレータのリプレイデータを可視化してみました。
https://s3-us-west-2.amazonaws.com/dqn/lifts/viewer.html?https://s3-us-west-2.amazonaws.com/dqn/lifts/replay.rulebased.json.gz

2MB超のリプレイデータをダウンロードするので、そこそこ時間がかかりますが、ローディングの文字が消えてから"Start/stop"ボタンを押すとちょこちょこ動きます。

DQNの結果

上のスクリプトにもありますが、結構妙な$\epsilon$スケジュールをしました。

  • $\epsilon = 0.99$ $(k \leq 10)$
  • $\epsilon = 0.8$ $(10 < k \leq 20)$
  • $\epsilon = 0.6$ $(20 < k \leq 30)$
  • $\epsilon = 0.4$ $(30 < k \leq 40)$
  • $\epsilon = 0.2$ $(40 < k \leq 50)$
  • $\epsilon = 0.1$ $(50 < k \leq 130)$
  • $\epsilon = 0.01$ $(130 < k)$

最後のほうで$\epsilon = 0.01$と出来ているのはDouble DQNのおかげだと思います。DQNの普通のタスクでは$\epsilon = 0.1$で止めておくことが多いのですが、Double DQNでは、Q関数を過大評価しづらくなって安定性が増すため、これくらいの設定でも動くみたいです。

期待累積報酬:$E[r_i] = 0.441423$

うーん、あんまり良くない。手書きしたアルゴリズムに比べて10%くらい悪くなっていますね。

リプレイデータ:https://s3-us-west-2.amazonaws.com/dqn/lifts/viewer.html?https://s3-us-west-2.amazonaws.com/dqn/lifts/replay/300.json.gz

シミュレータのバグを直す前は0.6くらいまで上がってたんだけど、ベースラインが突いてないシミュレータのバグをDQNが見付けて、それを利用していたっていうだけの話だったので、しっかりやりなおしてみたらベースラインに負けてしまった。DQNがバグを見つけたっていうのもなかなか面白い現象ではあると思うのだけど。

まぁ自由研究としてはこのくらいで充分かなー。

おわりに

単なる自由研究のつもりが、意外と楽しかった。
エレベータ毎にパラメタ共有構造を入れる前はぜんぜん動いてなかったのが共有構造を入れた途端にすんなり動くようになった時とかは脳汁がドバドバ出て、「私はエレベータの女王…」などとわけのわからないことを短文投稿サイトツイッターに投稿しそうになってしまい、あわてて回線を切って首を吊ったということなどがありました。

DQNは本当に収束してんのかぜんぜんわからないなぁと思いました。これはQ学習全般そうなのかも?DQNの論文には報酬よりQの値を見たほうが収束わかりやすいよ、みたいなことが書いてありましたが、なぜQの値が増えてるのを見て収束性がチェックできるのか理解できず、やりませんでした。

なんにせよ強化学習は楽しいなぁと思いました。まる。
生まれ変わったら、不動産王としてリアルワールドでエレベータの最適化がしたい。


  1. 厳密にはこのモデルだと1Fに来て上に上がっていった人が全員戻っていない可能性も考えられる。というかその可能性のほうが高い。同様に人がいないはずの階から突如として人が出現したりも有り得る。 

  2. ポアソンはフランス語で「魚」の意味。フランス内陸部では魚は滅多に食卓に登ることのない貴重な食べ物だった。そのことから希少イベントの回数の分布にこの名前が付けられた。(民明書房刊「中国拳法と確率分布」より) 

  3. 参照: https://xkcd.com/927/