進化計算と強化学習の紹介

自動着桟

自律運航船の実現に向けた重要な技術要素の一つとして，「自動着桟」が挙げられます．着桟とは，船舶を桟橋や岸壁の目標位置に安全に停泊させることを指します．大型船の着桟の様子は，大阪大学のグループが公開している動画を参照ください．自動着桟とは，自動的に着桟を実現する技術を指します．自動着桟を実現するためには，時々刻々と変化する制御対象となる船舶の状態（位置や速度など）と周りの環境（障害物や気象状況など）を観測し，次に取るべき制御信号（舵角やプロペラ回転数）を定める「ルール」を定める必要があります．船の状態や環境の状態をまとめて「状態 s」と呼び，制御信号を「行動 a」と呼ぶことにします．このとき，前述の「ルール」は，状態 s を入力にとり行動 a を出力する関数，もしくは各状態 s で各行動 a の選択確率を定める確率分布，などとして表すことが出来ます．これは「制御則（controller）」や「方策（policy）」などと呼ばれます．自動着桟を実現するということは，それを実現する方策を獲得する問題に帰着することになります．

強化学習

さて，方策はどのようにして獲得すれば良いでしょうか．その一つの方法が「強化学習」です．強化学習は，試行錯誤を繰り返していくことで，最適な方策を学習するための方法です．強化学習では，学習主体をエージェント，それ以外を環境と考えます．自動着桟の場合には，船舶がエージェント，それ以外が環境ということになります．船舶は何らかの方策に従って，行動を決定し，行動を取ります．その結果，船舶は動くことになります．また，行動とは無関係に風環境などの状態も変化することがあるでしょう．このようにある状態sである行動aをとったときに次の状態s'に変化することを，状態遷移と呼びます．状態遷移をすると，エージェントは次の状態を観測し，同時に現状態の良さを表す報酬を受取ります．なお，報酬は基本的に使用者が設計することになります．エージェントはこの情報をもとに得られる報酬が高くなるように方策を改善します．これを繰り返していくことで，得られる報酬を最大にするような方策を学ぶ方法が，強化学習です．

自動着桟の場合，実は単純に強化学習を適用することは現実的ではありません．強化学習では，試行錯誤を繰り返しますが，現実環境で試行錯誤を繰り返した場合，学習途中で必ずしも適切ではない行動をとってしまうかもしれません．これは，船舶が桟橋に衝突するなどの安全上の重大な懸念があります．また，実際に船舶を動かして学習するためには，金銭的・時間的なコストが膨大にかかります．これらの問題点に対する一つの解決策として，船舶の運動モデルを表すシミュレータを設計し，シミュレーション上で強化学習を実施する方法があります．この方法であれば，安全でない行動をとったとしても，シミュレーション上でクラッシュするだけであり，学習中における安全性の懸念はなくなります．また，一度シミュレータを設計してしまえば，金銭的にも時間的にもコストを大幅に削減することが出来ます．一方で，シミュレータが完璧では無い，などといった問題もあります．これについては重要な研究課題であり，我々も取り組んでいるところです．

機械学習と進化計算によるVideo Gameのレベル生成

Video Gameのレベル生成における進化計算の応用事例を紹介します．Video Gameのレベルとは，プレイヤーがプレイするステージやマップのことを指します．Video Gameのレベルを生成する際，そのレベルがプレイ可能であること（開始と同時にゲーム終了となってしまったり，ゲームを攻略することが不可能とならないこと）が最低限要請されます．加えて，プレイヤーの実力に対して適切な難易度であることや，プレイヤーにとって面白いと感じるようなレベルを生成することが求められます．前者については，生成されたレベルに対して形式的に評価することが可能です．しかし，後者二点のついての「望ましさ」は，生成されたレベルにおいてプレイヤーが実際にプレイを通して評価するか，既存のAIエージェントにプレイさせた結果を評価するなどの方法が必要となります．このとき，「生成されたレベル」とその「望ましさ」の関係はブラックボックスとなり，「望ましさ」を最大化するようなレベルを見つけ出す「ブラックボックス最適化」が必要となります．ここで，進化計算が活躍します．レベルの生成とその評価を繰り返すことで，望ましさの高いレベルを生成することが可能です．

ここでは，Science Birds（Angry Birdsの研究用クローン）のレベル生成を行った我々の研究 [Tanabe et al., GECCO2021][田邊ら, JSAI2021]を紹介します．まず，機械学習技術の一つであるSequential VAEと既存のレベルのデータセットを用いて，実数ベクトル x を入力するとそれに対応するプレイ可能なレベル L を出力する関数 G を学習しておきます．この関数をデコーダーなどと呼びます．デコーダーへの入力 x が変われば結果として生成されるレベル L = G(x) が変わり，その望ましさ U(L) はAIエージェントもしくは人力によって評価されます．進化計算は，Lを直接最適化する代わりに，xを最適化します．これにより，「プレイ可能である」という制約を常に満たすようにしながら，望ましさの高いレベル（に対応するx）を探索することが可能になります．デコーダーへの入力 x は実数ベクトルであり，実数ベクトルを最適化対象とする進化計算として広く利用されているCMA-ESというアプローチを用いて，関数 f(x) = U(G(x)) を最大化しました．CMA-ESは，候補となる解 x を正規分布から一度に複数生成し，その中から目的関数値が望ましいと判断された解集合を用いて，解候補を生成するための正規分布のパラメータ（平均ベクトルや共分散行列）を更新します．統計学的な観点から，パラメータ更新方法が設計されています．これを繰り返すことで，目的関数値が高い（最大化の場合）解の領域へと正規分布を収束させていきます．

以下の動画は，生成されたレベルをAIエージェントがプレイしている様子です．このレベルは，的（ブタ）とブロックの数は多く，しかし，１ショットで的だけを全て破壊できるように生成されています．レベルの評価（目的関数値）は，生成された各レベルに対してAIエージェントを実行し，その結果残った的の数やそれ以外のブロックの数をもとに計算されています．この目的関数f(x)はxの関数として明示的に書き下すことができないことは，容易にわかるかと思います．このようなブラックボックスな目的関数であっても解を発見できることが，進化計算の強みになります．