はじめてのGOAP
chobi_eごぶさたしておりますちょびえです。てっきりGOAPについて書いたと思ったけどそんなことはなかったので今日はGOAPについて書いてみようと思います。
GOAPに関してはわりと書いている方もいらっしゃいますのでここでは私の解釈という形で記します。すごい適当に書いているので間違ってるかもしれない。
Goal Oriented Action Planning
最近流行りのDeepLさんはいいました:目標指向型行動計画と
漢字ばっかりにするとそれはそれで趣が違ってまたいいですね。
現代社会におけるOKRやMBOとかGOAPの一種でもあると言えるのではないでしょうか。
そんな話はさておきGOAP、、、というか自立型エージェントの本質としては知覚、手段、行動、計画、評価です。大前提として
・知ることが出来ないと何も行動が出来ない
・手段を知っていなければ行動出来ない
・目指すべきゴールが分からなければ選択できない
・評価ができないと適切にゴールに向かっているか分からない
ということです。AIの話をしているのか人事考課の話をしているのかアレですがそういうAIなんです。
説明するよりも実際コード書いて考えてもらったほうが楽なんで、早速GOAPのコード例いってみましょう。
単純GOAP： ちょびえさんは行きて帰りしご飯を食べる
GOAPのキモとしてはAIの設定者は「ゴールに到達すべき手順の条件を知っている」です。
初期状態：ちょびえさん自席に座っています。ご飯は持っていません。自販機は10の位置にあります。
GOAL: ちょびえさんは満腹になる
知っている行動：
・席を立つ(状態：立つ、前提：座る)
・行く（状態：移動＋１、前提：立つ）
・帰る（状態：移動ー１、前提：立つ）
・自販機で食べ物を買う（状態：食べ物を所持、前提：自販機前にいる）
・座る（状態：座る、前提：立つ、自席前）
・ご飯を食べる（状態：満腹、前提：食べ物を所持、座っている）
さて、これでご飯が食べれる組み合わせをプランニングしてみましょう。
ストレートに総当りで実装します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
<?php // ☆）目的とすべき状態を定義します。 $goal = [ "manpuku" => true, ]; // ☆）現在の状態を定義します $state = [ //自席は0、自販機前は10とします。 "position" => 0, //立っているか座っているか "standing" => false, //食事を持っているか "meshi" => false, //満腹かどうか "manpuku" => false, ]; // ☆）次に先に示した、行動を定義します。 // 行動には前提条件となるprecondition, 行動した結果となるeffectが最低限必要です。 // なにかしらの行動には結果が伴うといえます。 // また、手段の選択のヒントとなるpriorityを今回追加しています。 // (priorityがない場合、条件をみたす手段が複数あった場合選択が難しいため） $actions = [ [ "name" => "席を立つ", "priority" => 5, "precond" => [ // 前提条件として座っていることを期待します "standing" => false, ], "effect" => [ // 行動の結果として立つ状態となります "standing" => true, ] ], [ "name" => "行く", "priority" => 5, "precond" => [ // ガードとして置きます。メシを持たねば行ってこいと "meshi" => false, "standing" => true, ], "effect" => [ "position" => 1, ] ], [ "name" => "帰る", "priority" => 6, "precond" => [ // ガードとして置きます。メシを持って帰ってこいと "meshi" => true, "standing" => true, ], "effect" => [ "position" => -1, ] ], [ "name" => "自販機で食べ物を買う", "priority" => 1, "precond" => [ "meshi" => false, "position" => 10, ], "effect" => [ "meshi" => true, ] ], [ "name" => "座る", "priority" => 6, "precond" => [ "position" => 0, "standing" => true, ], "effect" => [ "standing" => false, ] ], [ "name" => "ご飯を食べる", "priority" => 0, "precond" => [ "meshi" => true, "standing" => false, ], "effect" => [ "manpuku" => true, ] ], ]; // ゴール、行動、初期状態からプランを算出します。 $plan = goap($goal, $actions, $state); echo "PLAN:" . PHP_EOL; foreach ($plan as $act) { echo $act["name"] . PHP_EOL; } // GOAPによるプランの計算 function goap($goal, $actions, $state) { $plan = []; for ($tries = 0; $tries < 100000; $tries++) { // 状態がゴールにマッチしていれば終了とみなします $passed = 0; foreach ($goal as $key => $value) { if ($state[$key] == $value) { $passed++; }; } if (count($goal) == $passed) { return $plan; } // ゴール状態でなければ行動を抽出し実行します $available_action = []; for ($i = 0; $i < count($actions); $i++) { $action = $actions[$i]; $ok = 0; // 前提条件にマッチする行動を洗い出します。今回は単純にequalであるか。 foreach ($action["precond"] as $key => $precond) { switch ($key) { case "position": case "meshi": case "standing": if ($state[$key] == $precond) { $ok++; } break; } } if ($ok == count($action["precond"])) { $available_action[] = $action; } } // 取りうる行動がなければ詰んだ、ということですね if (count($available_action) == 0) { throw new Exception("Action not found"); } // 複数行動から適切な行動をソートして求めます。 // ソート以外でも適切な行動を取れれば何でも良いです。 usort($available_action, function ($a, $b) { return $a["priority"] < $b["priority"] ? -1 : 1; }); // 適切な行動の結果を状態に追加します。 $target_action = array_shift($available_action); $plan []= $target_action; foreach ($target_action["effect"] as $key => $effect) { switch ($key) { case "position": // 汎用的に書くと面倒なのでこういうふうに書いてるだけです。 // postion, type = add, value = 1みたいにパラメ増やすの面倒なんで $state["position"] += $effect; break; case "meshi": case "manpuku": case "standing": $state[$key] = $effect; break; } } } throw new Exception("max attempts exceeded"); } |
結果として
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
php .\goap_simulator.php PLAN: 席を立つ 行く 行く 行く 行く 行く 行く 行く 行く 行く 行く 自販機で食べ物を買う 帰る 帰る 帰る 帰る 帰る 帰る 帰る 帰る 帰る 帰る 座る ご飯を食べる |
無事ご飯を食べることができました。
コード例を踏まえて
ストレートに実装して全体で200行程度です。GOAPのプラン算出部分は70行。このぐらいのサイズであれば色々試しやすいですね。
試しにpriorityを外して実行するとどうなったりするか遊んでみたり、ゴールと手段を変えてみたりすると面白いですよ。
シンプルであるがゆえに奥が深く、強力なツール（かけた労力の何倍もの効用をだしてくれる）にもなりえるのがGOAPです。
とはいえ、雑な設定をすると無限ループなどに陥ったりするので事象の適切なモデル化が必要です。
今回のサンプルコードはGOAPの仕組みの紹介程度なので非常に雑です。実際に使う場合はA*等を利用した行動選択の最適化等を行ってください。
GOAPの強み
GOAPの強みは手段の前提条件があるため、既知の状態であれば強固な復帰力で最後までやり遂げられるという所にあります。
反面、未知の状態に陥った場合や、そもそもゴールへの到達手段を設定側が知らない場合は意味のない行動をしてしまいます。
今回の例の場合、外的要因等による影響がなく実装が間違っていなければ成功する状況でしたが実際のゲーム、例えば自動実行エージェントをGOAPで実現するとした場合マップギミックで移動させられたり、イベントの介入があったり、外敵との戦闘などが出てくるのでそれらの状況に対応できるように組まなければいけません。
モデル化の抽象度も具体的な手順まで落とし込むのか、メタ的な事象に抑えて下位エージェントに委ねるのか、はたまたどうするのか…
プランニング系は単一AIというよりかは既存システムやUtility系のAIと組み合わせて使うことに真価があります。
自由度とメタ度が高すぎて、最終的に個別ソフトごとに密結合となるのでいまいちライブラリとしては流行りませんが知ってると便利なので使いこなしてアプリにあわせた実装ができるようにするのがおすすめです。
そいでは良いAIライフを