こんにちは、サーバーサイドエンジニアのいいだです。
もうすぐ夏ですね。私は夏になると決まって、ある問題に直面します。毎年試行錯誤を繰り返してはいますが、いまいちしっくりくる答えにたどり着くことができません。つまり、そうめんに合うおかずとは何であろうかということです。
ちなみに実家では目玉焼きが定番でした。いいえ、悪くはありません。今日は自動計画の話をします。
そうめんと自動計画とねこ
自動計画とは、そうめんに合うおかずを決定することです。いわゆるAIの一分野で、周囲の環境や自身のとれる行動などから既知ないし未知の問題を解決する具体的な手順を作り出すのがその役目です。
自動計画はロボットや産業機器などの真面目な分野でももちろん使われていますが、個人的な好みの問題からここではゲームにおける自動操作キャラクターの挙動とその計画を扱う仕組みとして紹介します。プレイヤーの体力が減った場合に攻撃を中断して回復アイテムを使ってくれる味方キャラクターという簡単なものから、アイテムを総取りしつつ崖際へ走ってプレイヤーの復帰を阻止する極悪非道のロゼッタ＆チコまで、自動計画はゲームの様々なところで活用されています。
今回は、与えられた環境で可能な限り長時間生存することを目標とするねこを作りました。（簡単な）ゴール指向の自動計画器を（それらしい）遺伝的ネットワーク計算によって学習し、横からレーザーを撃たれない限り死なないねこを目指します。
ねこについて
ねこです。72頂点あります。関節は全て固定されていて動きませんが、時速40km程度で移動することができます。
今回の設定では、ねこは最大で100の満腹度を持ちます。ねこが環境に存在する時、ねこは1秒ごとに2の満腹度を失います。これが50を下回った時、ねこは「はらへり」を認識します。その状態のまま何もせずにいると、やがて満腹度が0になり、体力を失い、死にます。
ねこも死にたくはありませんので、何かを食べたいかと思います。もちろん、この環境には食べるものも用意されています。
すしです。ねこは実際のところすしをあまり食べないそうですが、刺身にすると8頂点になりますので、ハイポリゴンなモデルを用いたリッチな体験を目指してすしにしました。16頂点あります。
ねこはすしを「食べる」ことにより、満腹度を30回復することができます。これによって満腹度が80を上回った時、「はらへり」は解消されます。また、満腹度が50以上のとき、体力は徐々に回復します。
つまり、すしを食べることでねこは永遠に生き続けるでしょう。大変喜ばしいことです。そのために、ねこには正しい食事を計画してもらいます。
ねこによる計画
ゴール指向の自動計画器は、ゴールを最初に決め、それを解決する行動を求めることによって計画を作成します。たとえば冒頭のそうめんのおかずを獲得する計画においては、「食卓に並べる」がそれにあたります。おかずを食卓へ並べるには、食べる準備の整ったおかずが必要です。然るに、私はその下位のゴールとして「薬味オンリーで行く」を選択するでしょう。計画が短く、調理や洗い物等のコストも少なく、とても効率的であるからです。このように、効率的な計画器は食後の満足度をも左右します。
海苔や小ねぎ、しょうがにも飽きましたか？ いいえ、わさびがあります。茹でた小麦粉をめんつゆで食べましょう。
ねこは行動を計画するための計画器として、有向グラフを一つ持ちます。これを計画グラフと呼びます。このグラフには「状態」「行動」の二種類の頂点が存在し、それらの接続（辺）を作成ないし変更することによって、計画器は「状態」の解消を目指します。
もし、ねことすしが十分に近ければ、ねこはすしをそのまま食べることができます。今回の設定では、ねこは2m以内のすしを0.17msで食べることができます。ちなみに、このねこは全長がおよそ1mあります。
しかしながら、往々にして、我々と食べ物との間には距離があります。ねこの口はねこと独立して移動できるようにはなっていないので、ねこがすしを食べるにはねこ自身がすしに近づく必要があります。つまり、すしが「食べる」の範囲内にあるかどうかを判断し、そうでない場合には「近づく」ことが求められます。
このため、計画では「状態」が自身のとれる「行動」によって解消できるか、またそもそもその「行動」ができるかを自身で判断しなければなりません。この場合では、「はらへり」を解消するためには「食べる」必要があり、「食べる」には「近づく」必要があります。
計画グラフはこのような「状態」と「行動」の接続を保持しておき、最終的に「現在すぐに実行できる行動」から「将来解消されるべき状態（課題）」までの道筋をねこに示すことができます。これによって、ねこはすしが近くにない時でも、自分ですしに近づき、それを食べることができるようになります。
ねこの提案グラフ
計画においては、ねこは自分がどのような行動をとれば課題を解決できるかをよくよくわかっている必要があります。「はらへり」状態から「（何かを）食べる」へ至るには、「（何かを）食べる」ことが「はらへり」を解消する行動であると知っていなければいけません。
このため、ねこは「現時点で解消できない状態」または「現時点で実行できない行動」に直面したとき、それを解消する新たな行動を探します。これにより、ねこはあらゆる問題に対して、最低限「直ちに実行できること」を見つけることができます。
しかしながら、直ちに実行できれば何でもよいわけではありません。「はらへり」になった時、「食べる」ではなく「近づく」を選択してしまったねこは、すしに近づくことはしますがそれ以上は何もせず、いずれ死んでしまうでしょう。
今回は、「すしは食べ物である」というのはねこにもわかっているものとして、「はらへり」→「食べる」や「食べる」→「近づく」の接続をねこ自身に発見してもらうべく、遺伝的ネットワーク計算による簡易的な学習の仕組みを用意します。これを提案グラフと呼びます。
提案グラフは、「状態」「行動」「条件」「選択」の四つの頂点を持った有向グラフです。提案グラフはねこが持つ全ての「状態」及び「行動」と同じ数が用意され、始点となるそれによって使い分けられます。提案グラフは計画グラフが「直ちに解消できない状態ないし直ちに実行できない行動」に直面したとき、それを解決するために使われます。
計画グラフは計画において、グラフの末端にある「状態」ないし「行動」が解決不可である場合、その時点の「状態」ないし「行動」を提案グラフに渡します。提案グラフはそれと同じ種類の「状態」ないし「行動」を始点として、別の「行動」へ辿り着くまで各頂点を辿って探索し、たどり着いた結果である「行動」を返します。もし探索中の頂点が次への接続を持っていなかった場合は、ランダムに別の頂点へ接続して探索を続けます。
| 頂点の種類 | やること |
|---|---|
| 状態 | なにもしない（始点以外には選ばれない） |
| 行動 | 始点でない場合、探索を終了する |
| 条件 | 環境を指定の条件で検査し、trueかfalseによってそれぞれ別の頂点へ移動する |
| 選択 | その目標にターゲット（モノ、場所、時間）を設定する |
この結果得られた「行動」が実行可能であればそれを実行し、そうでなければまた提案グラフを呼ぶことによって、最終的には実行可能な「行動」にたどり着く、というのが基本的な仕組みになります。これによって、計画グラフは自分ができる全ての行動が実行不可である場合を除き、あらゆる「状態」ないし「行動」からさしあたって実行可能な行動を導くことができます。
もちろん、それが価値ある行動かどうかは、今のところは考えません。ねこは精一杯に生きています。
ねこの天国
提案グラフを作ることによって、ねこは実行可能な「行動」を確実に得ることができるようになりました。しかしながら、現時点では新たな問題へ直面する度にランダムで行動を選ぶおもしろ計画器であり、それが正しく機能するかは疑問です。
死にそうだからといってみだりにレーザーを撃つべきではありません。空腹ならばなおさらです。ねこは正しくない行動をした時にそれを知り、正す必要があります。少なくとも来世では。
環境はねこの天国を持ちます。ねこの天国はまたたびの香りのフォグに包まれ、すしと比べて頂点数に優れる缶詰の山と、リアルタイム流体シミュレーションで流れるおやつの川、そして物理演算の宿った荒ぶるおもちゃの大地があります。さておき、全てのねこは死んだとき、その生存時間と自身が持っている提案グラフを天国に送ります。
天国は直近100件のねこの平均生存時間と、最大で100件の提案グラフを持っています。新しいねこが環境に生まれるとき、天国はねこに自身が持つ提案グラフをランダムで一つ与えます。ねこは天啓を受け、生まれた瞬間から比較的賢いかもしれない状態になります。
これにより、ねこは賢かったり、そうでなかったりする状態で人生を送ります。生きるうちに新たな発見をし、提案グラフに変更が加わるかもしれません。そうして大往生を迎えると、提案グラフと生存時間がまた天国に蓄積されていきます。
この繰り返しによって提案グラフが100件集まると、天国は「進化」を行います。世代を一つ送り、100件集まった提案グラフを長生きした順に並べ、以下の処理を行います。
| 範囲 | やること |
|---|---|
| 上位10件 | そのまま残す |
| 次の20件 | ランダムな2件ずつでペアを作る 双方にある辺を残す 片方にしかない辺は30%の確率で残す |
| 次の5件 | 全ての辺を10%の確率で消す |
| そのほか | 削除する |
この結果、残った提案グラフが次世代のねこたちに与えられます。これらは概ね前世代のご長寿ランキング上位勢ということになりますので、次世代のねこは比較的賢いことが期待できそうな状態から人生をスタートします。そしてそのねこがより長く生き、優秀な提案グラフを次世代に残し続けることによって、提案グラフが改善され、計画器がより適切な計画を立てられるようになります。
全てのねこが永遠に生きるようになったとき、天国はその役目を終えるでしょう。
おわりに
簡単なものではありますが、ゴール指向の自動計画器と遺伝的ネットワーク計算の学習装置を作ることができました。AIについては全くの門外漢なので調べていてもなるほどわからん状態でしたが、さしあたってねこが動いているので私は満足しています。
計画器やその学習には様々な手法がありますので、それらを参考に今後も改善を重ねつつ、より賢いねこになってもらえればと思っています。
