WonderPlanet DEVELOPER BLOG

ワンダープラネットの開発者ブログです。モバイルゲーム開発情報を発信。

遺伝的アルゴリズムで歩行学習させてみる

今回エンジニアブロクを担当する小瀬です。

先日、将棋のAIが現役のプロ棋士に勝つなど、なかなか話題を集めている人工知能ですが今回はGA(Genetic algorithm、遺伝的アルゴリズム)と呼ばれる手法で謎の生物に歩行学習をさせてみようかと思います。

Screen Shot 2014-04-10 at 12.48.52

■GAとは?
GA(遺伝的アルゴリズム)についてザックリと説明すると、ランダムで与えられた数値、アルゴリズムを用いて徐々に学習・遺伝させながら解を求めていく進化的アルゴリズムの一種です。

今回のケースでは、4本足を持ったモデルに関節の回転パラメータ等をランダムで与え、より効率よく歩けるよう学習させていきます。本来は決まった解の無い問題の最適解を探したり、ロジックそのものをランダムで組み換えより高度なアルゴリズムを自動で生成させたりなど、複雑なシチュエーションで利用される事が多いのかなと思います。

■進化(学習)のしくみ
それでは、実際にどのように進化させていくのか簡単に説明していきます。

◇0.初期生成
GAの解説などではあまり触れられませんが、一番初めの個体は完全にランダムで生成してしまいます。一般的には、一度に大量の個体を生成してしまったほうが効率が良いですがパフォーマンスや時間との兼ね合いで適度な数(N体)の個体を生成します。

◇1.淘汰
それぞれの個体を動作させ、求める解に基づいてスコアを算出し優秀な個体を選別します。選別する手法としてはスコアの高いエリートから順番に選択する方法や、スコアの高いものの確率を上げその中からランダムで選択する方法などがあります。

◇2.交叉
生き残った個体からランダムに2つの個体を選び、それぞれの要素を交叉させていきます。このフェイズは空間内の個体が最大数(N体)になるまで繰り返します。

cross

交叉の方法としては、上図のように個体Aと個体Bを選びそれぞれの個体からパラメータを受け継ぎ新しい個体Xを生成します。このAとBのパラメータを区切る方法によって2点交叉、一様交叉など様々な方法があります。

◇3.突然変異
交叉した個体の中を一定確率で突然変異を起こさせます(簡単に言ってしまえば一部のパラメータをランダムに変えたりします)。どの程度の頻度で突然変異するかによって結果は大きく変わってきますが、突然変異を無くしてしまうと「進化の袋小路」に陥り、途中で進化が止まってしまうことがあります。

◇4.繰り返し
この1〜3までのプロセスを望む結果が得られるまでひたすら繰り返していきます。求める解によっては非常に時間がかかる事もあります。

■歩行学習
今回は、4本足のモデルを用意し、Unity上でRigidbodyやCharactorJoint等を設定することで簡単に物理演算を行えるよう設定しています。

Screen Shot 2014-04-11 at 1.11.39

上記の0〜4の各プロセスについて簡単に説明すると、体と4本の足、それぞれ2箇所の関節を持ち、各関節にランダムで回転値(厳密には2〜5点の回転各をそれぞれ順番に補間しながらループ)を与えられた個体が50体生成されます。

それらの個体が、自らの手足の動きと物理演算によって移動して行くため、その結果として最もZ方向に進んだ個体により高いスコアを付けます。この際、移動中ににひっくり返ってしまったり、後ろ方向を向いてしまった個体にはペナルティとしてマイナス点を与えています。

計算されたスコアの中から上位10個体を選出し、それぞれ関節の回転角を交叉させて新しい個体を生成、そのうち20体は突然変異として1〜2箇所の関節にランダム値を与えています。

こういった計算を何百世代と繰り返し、より効率よく移動できるよう学習させて行きました。

■学習結果
第1世代目ではほとんど前に進むことも出来ず、その場でウネウネしているだけで回転してしまっている個体もいます。

380世代目の個体となると、完璧とは言えなくとも這うように歩くようになります。このように何世代も学習を重ねていくことでより良い結果を得ることが出来ます。

今回は、関節の回転角、脚の質量などを遺伝させ変化させてみましたが、脚を移動させる際の力の強度や脚そのものの大きさ等を変えてみるのも面白いかもしれません。
(ただ、残念なことに色々と設定を変更してみたものの、RigidbodyやJoinの作成の仕方が悪いのか、Unityの物理エンジンの精度の問題なのか分かりませが、同じパラメータの個体であっても実行する度に結果が微妙に異なり、2000世代ほど遺伝させてみてもあまり効率的な進化が行われていないようでした。この辺りの問題が解決すると、より良い結果が得られたのではないかなと思います。)

■まとめ
GA自体の考え方は難しくはないと思いますし、こういったシンプルなものであれば実装方法は非常に簡単でかなり面白い結果が得られる手法だと思います。望む結果を得るためには、スコアの計算方法や個体のパラメータ設定など色々と調整が必要な部分もありますが、AIに興味のある方は一度試してみてはいかがでしょうか?

■おまけ
煩雑なコードではありますが、今回作成したUnityプロジェクトをアップロードしておきます。
GAWalker.zip

Assetフォルダの中にSceneファイルが1つあるので、そのシーンをロードして実行すると勝手に遺伝が始まります。また、20世代毎にExportフォルダ以下に自動的に各パラメータが保存されるため、GenManagerのインスペクタにある「Import」からロードすることも可能です。