hasht's notes

ゲームAIやUnityの話題

GOAP（ゴール指向プランニング）

先に紹介したAI PlannerのようなシステムはゲームAIの分野だとGOAP（ゴール指向プランニング、Goal-Oriented Action Planning）と呼ばれるが、起源は「F.E.A.R.」にあるようだ。

元々人工知能分野でプランニング問題（ロボットアームで積み木を指定された並びに積むような、順序・依存性を考える必要がある行動計画）の定式化＆解法としてSTRIPSがあり、それをゲーム用にアレンジしてGOAPとなった。

STRIPS

まず論文に基づいて前身であるSTRIPSのことを書く。

環境の状態を一階述語論理で表現する。ブロックAがPの位置にあったらAT(A, P)など。述語論理ということは「（なにか）存在する」とか「すべて」を表現できる。Pに何かがあるのなら∃x AT(x, P)となる。まぁ細かい話はいいとして、とにかくこの手の式で表現する。

アクション（論文では操作、operation）の内容は

  • 前提条件の式
  • 状態から削除する式（そのアクションで成り立たなくなる条件）
  • 状態に追加する式（そのアクションで成り立つようになる条件）

で表される。 例えばブロックAを位置Pから位置Qに動かすアクションは

  • 前提条件：AT(A, P)
  • 削除：AT(A, P)
  • 追加：AT(A, Q)

といった風になる。

こうした表現のもと、初期状態とゴールを指定する。初期状態に前提条件の合うアクションを適用したり、ゴールに必要な条件を追加するアクションでサブゴールを設定したりして、プランニングを進めるのがSTRIPSになる。

箱を押すロボットの例

3.5節にある例を簡単に追ってみよう。

オブジェクトとしてBOX1～3が、場所としてa～dがある。 ATR(a)はロボット自身がaにいることを、AT(BOX1, a)はBOX1がaにあることをそれぞれ表している。 初期状態M₀は

  • ATR(a)
  • AT(BOX1, b)
  • AT(BOX2, c)
  • AT(BOX3, d)

が成り立っていて、一方ゴールG₀は

  • ∃x ( AT(BOX1, x) ∧ AT(BOX2, x) ∧ AT(BOX3, x) )

つまりある一ヶ所に全ての箱が集まっている状態と設定する。

f:id:hasht:20190524194409p:plain
初期状態とゴール

アクションとしては

  • push(k, m, n) : ロボットがオブジェクトkを場所mから場所nへ押す。

    • 前提条件 : AT(k, m) ∧ ATR(m)
    • 削除する式 : ATR(m), AT(k, m)
    • 追加する式 : ATR(n), AT(k, n)

  • goto(m, n) : ロボットが場所mから場所nへ移動する。

    • 前提条件 : ATR(m)
    • 削除する式 : ATR(m)
    • 追加する式 : ATR(n)

の二つがある。（押すときにロボット自身も動く想定なので、上に書いたアクションの例とは異なっている）

まず初期状態のAT(BOX1, b)に注目してみると、ゴールの状態に辿り着くにはAT(BOX2, b)とAT(BOX3, b)を成り立たせなければならない。 そこでpush(BOX2, m, b)を実行すると考えると（mはまだ未確定）、その前提条件からサブゴールG₁としてATR(m) ∧ AT(BOX2, m)が成り立っていてほしいことになる。 ここで初期状態のAT(BOX2, c)に注目するならば、m=cとしてATR(c)を成り立たせたくなる。

そのために実行するアクションをgoto(m', c)とすれば、必要な条件G₂はATR(m')となる。 ここでm'=aとすれば初期状態でATR(a)が成り立っているので、goto(a, c)が実行できるとわかる。また次のpush(BOX2, c, b)も実行でき、この2つのアクションで状態はAT(BOX1, b) ∧ AT(BOX2, b) ∧AT(BOX3, d)`になる。

文だとかなり分かりづらいが、つまりはgoto(a, c)とpush(BOX2, c, b)を実行して以下のような状態を辿るプランが生成されている。

f:id:hasht:20190524194653p:plain
探索されたプランの一部

元の論文では { M₀ ∪ ￢G₀ } から導出される式をM₀とG₀との「差」として見て、上のようなプロセスを機械的に処理できるようにしている。そこから矛盾（⊥）が導かれたら差はないという事になる。（P→Qは￢P∨Qと等価なので、古典論理だと￢(P→Q) ⇔ ￢(￢P∨Q) ⇔ P∧￢Qで実際成り立つ） またどの式に注目して探索を行うかは任意性があるが、STRIPSはヒューリスティックな選択機構を実装していて深さ優先的な挙動になっているという。

GOAP

GOAPを生み出したJeff Orkin氏の資料を参照する。

STRIPSの論理式による表現は、外部のソルバを使ったりするならば良いのかもしれないが自分で実装するには手間がかかる。 F.E.A.R.のGOAPは状態の表現としてシンプルな辞書的データ構造を使うことで、述語論理の柔軟性を代償に扱いやすくしたものと言えるのではないかと思う。

これにより式の削除・追加は単純な状態の書き換えとなる。ただ必要な情報を全て管理しておくのも大変なので、ゲーム世界の状態を直接調べることもできるようにしておく（procedural precondition）。

例えばいずれかのターゲットが生きている∃x IsTarget(x) ∧ IsAlive(x)といった条件は、単純にIsAnyTargetAliveといった真理値のフィールドとして表現することになる。IsAlive(A)といった個々の式を追加・削除するだけのSTRIPSと比べると多少使う側が考えて更新してやなければいけないが、実装としては簡単で分かりやすいだろう。

もう一つGOAPでの変更点として、アクションにコストを持たせた点がある。生成されるプランは一連のアクションのコストがなるべく小さくなっていなければならないが、これは状態をノード、アクションをエッジと考えるとナビゲーションメッシュ上で最適な経路を考えるのと同じ問題で、A*アルゴリズムを使って解くことができる。