古典的プランニングにおける削除効果緩和の簡約

古典的プランニングにおける削除効果緩和の簡約

A Simplification of the delete relaxation in classical planning

今井 達也

1∗

Tatsuya Imai

1

1

_{東京工業大学}

1

_{Tokyo Institute of Technology}

Abstract: We propose a simplification method for the delete relaxation in classical planning. Although the delete relaxation semantically changes some properties of a problem such as finiteness of fuel of a vehicle, useless propositions and actions remain in the delete relaxation. We show that our domain-based simplification method removes such useless properties and generates smaller domain models for the delete relaxations of some International Planning Competition benchmark domains.

1

はじめに

プランニング問題とは，与えられた目的を達成する ための行動の手順を求める問題であり，人工知能に関 する主要な問題の一つである．例えば，スライディン グパズルの盤面が与えられたときに初期盤面を終局盤 面に遷移させる手順を求める問題はプランニング問題 の一例である．この他にも，スケジューリング問題，ロ ボットの制御，物語生成など多様な問題をプランニン グ問題として定式化することができる [3]． 通常，最適化問題をなるべく高速に解くためには最 適コストの下界が必要である．また，下界を求めるた めには元の問題の制約を緩和した問題を用いることが 多い．プランニングにおいては削除効果緩和と呼ばれ る制約緩和手法が非常に良く研究されており，例えば [4]など，主要なプランニングアルゴリズムにおいて実 際に下界コスト計算のために削除効果緩和（あるいは その更なる緩和）が利用されている． 多くの場合，削除効果緩和は問題の性質を変化させ る．例えば有限の燃料を持つ車を操作して目的地を目 指すというプランニング問題が与えられたときに，削 除効果緩和を適用すると車の燃料が無限になる等の変 化が起こる．車の燃料が無限であれば実質的には車の 燃料を無視して問題を解けるはずであるが，元問題に 単に削除効果緩和を適用しただけではそれらの不要な 情報が残ってしまい，緩和問題を高速に解くための障 害となってしまう．そこで本研究では，削除効果緩和 された問題を不要な情報を取り除いた小さな問題に簡 約する手法について研究を行った．本稿では， ∗_{連絡先：東京工業大学} 〒 152-8550 東京都目黒区大岡山２丁目１２−１ Ｗ８−２５ E-mail: imai7(AT)is.titech.ac.jp • 削除効果緩和された問題の簡約手法の提案 • 簡約が最適コストを等価に保つ条件の証明 • 簡約の計算手法の提案

• International Planning Competition （IPC）の

ベンチマーク問題に実際に簡約を適用した結果 について述べる． 次節ではプランニング問題および削除効果緩和の形 式的な定義を行う．その次以降の節では上記の項目に 関して順に議論を行っていく．

2

準備

2.1

命題論理プランニング

本稿では次の４つ組 T =⟨P, A, I, G⟩ を命題論理プ ランニングタスクと呼ぶ．以下では T を単にプランニ ングタスクないしタスクと呼ぶ． • P：命題の集合．命題はそれ以上分解できない単 なる命題である．P の部分集合を状態と呼ぶ． • A：行為の集合．全ての行為は P の部分集合の３つ

組である．ただし∀a = ⟨pre(a), add(a), del(a)⟩ ∈

Aについて pre(a) を前提条件，add(a) を追加効 果，del(a) を削除効果と呼ぶ． • I ⊆ P ：初期状態． • G ⊆ P ：目標． 人工知能学会研究会資料 SIG-FPAI-B402-02

∀S ⊆ P および ∀a ∈ A について，pre(a) ⊆ S のと

き，a は S に適用可能という．状態 S および行為 a に 対し，S[a] := (S\ del(a)) ∪ add(a) と定義する．a を

適用可能な状態 S に対して S[a] を求めることを S に αを適用するという．状態 S および行為列 a1,· · · , ak に対し，任意の i について S[a1]· · · [ai₋₁] に ai が適 用可能であるとき，a1,· · · , ak は S に適用可能である という．G を包含する状態を目標状態と呼び，行為列 α =⟨a1,· · · , ak⟩ について I[a1]· · · [ak] が目標状態の とき，α をT の充足解と呼ぶ．また，行為列 α の長 さ k を α のコストと呼ぶ． プランニング問題とは，タスクT に対して最もコス トの小さい充足解を求める問題である．プランニング 問題，および，プランニングタスクの充足解の存在判 定問題は PSPACE 完全であることが知られている [2]． なお，タスクから陰に作られる状態空間において，プ ランニング問題は最短経路問題に帰着することができ る．状態空間とは状態の遷移関係を表す有向グラフで あり，頂点は状態に対応し，有向辺はその辺の尾に対 応する状態を頭に対応する状態に遷移させる行為に対 応する．状態空間には同一の行為が複数現れうること に注意せよ．多くの場合，状態空間はタスクのサイズ に対して指数的以上に大きく，ダイクストラ法等の全 探索アルゴリズムで解くことは難しい．これを少しで も高速化するために，状態からその最近傍の目標状態 へのコストの下界を用いて A* 探索を行う手法が近年 の主流なアプローチの一つである（[1, 4] など）． なお，以下の議論は各行為に 1 でない非負のコスト 値を割当て，充足解のコストを行為のコストの和と定 義しても簡単な変更によって成立させられるが，議論 を単純化するため以下では単に単位コストを用いる．

2.2

削除効果緩和

プランニングタスク T =⟨P, A, I, G⟩ に対し，タス ク T+=⟨P, A+, I, G⟩ を T の削除効果緩和と呼ぶ．た だし A+={⟨pre(a), add(a), ∅⟩ | a ∈ A} である．また， あるタスクの削除効果緩和かどうかに関係なく，削除 効果のないタスクを無削除タスクと呼ぶこととする． 無削除タスクにおいては行為を状態に適用するごと に状態中の命題は増す一方であり，タスク T の任意の 充足解はその削除効果緩和 T′ でも充足解である．よっ て T+ の最適コスト値は T の最適コスト値以下であ る．このことから削除効果緩和は状態空間で A* 探索 を行う際のコスト下界計算などによく用いられている． ただし，無削除タスクの最適コスト計算は NP 困難で あることが知られている [2]．このため先行研究のアル ゴリズムでは削除効果緩和を更に緩和した P 問題をコ スト見積もりに用いることが多い（例えば [1] など）．

3

無削除タスクの射影簡約

多くの場合，削除効果緩和はプランニングタスクに 質的な変化を与える．例えば，元問題では有限だった 車の燃料が削除効果緩和後には無限になったり，トラッ クの荷物容量が無限になったりする． このように緩和によって性質の変化がある問題の中 には，意味内容を吟味しながら人間がタスクを書き換 えれば内容を等価に保ちながらサイズを小さくできる ものも多い．例えば車の燃料が無限になれば「燃料=1」 「燃料=2」· · · という数多くの命題が不要になる．しか し，単に削除効果緩和を行っただけではそれらの不要 な要素は残ってしまう．そこで本稿では，最適コスト を等価に保ちながら削除効果緩和のサイズを縮小する 方法を提案する．まず本節では，簡約の計算効率や最 適コストの等価性は考えずに，一般的な簡約の枠組み を定義する．ただし，以降の定義や議論は幾分複雑で あるため，理解を助けるためにまずは後の定義に基づ いた具体的な簡約の例を与える． なお，個々の要素の厳密な定義は逐一与えるが，以 降の全てでは，記号中のダッシュ記号はそれが簡約後 の要素であることを表すこととする．

3.1

射影簡約の具体例

有限の燃料を持つ車でグラフ上の経路を探索するプ ランニング問題を考える．車は辺を一つ通過するごと に燃料を一単位消費する．グラフの頂点を v1,· · · , vn，

辺を e1,· · · , emとおいて，eiの端点を ei,1, ei,2とおい

たとき，例えば次のようなタスク T =⟨P, A, I, G⟩ が 考えられる．ただし p(v) は車の位置が頂点 v である という命題，f (x) は残りの燃料が x であるという命題 を表す． • P = {p(v1),· · · , p(vn), f (0), f (1),· · · , f(10)}． • a(U, V, F ) = ⟨ {p(U), f(F )}, {p(V ), f(F − 1)}, {p(U), f(F )}⟩ とおいたとき，A = { a(e1,1, e1,2, 1),

· · · , a(e1,1, e1,2, 10),· · · , a(em,1, em,2, 10)}． • I = {p(v1), f (10)}． • G = {p(vn)}． T に削除効果緩和を適用すると，a(U, V, F ) の削除 効果{p(U), f(F )} が消え，辺を通過しても燃料が初期 値から減らなくなる．よって，緩和問題は本質的には 単なる最短経路問題となる．しかし，行為は燃料の値 ごとに依然として多重化されており，計算の効率は良 くない． 各辺 ei について ei を通る行為の集合を Ai ⊆ A とおき，Ai の行為を単一の行為に置き換えることで，

次のような無削除タスク ⟨P′, A′, I′, G′⟩ を作ること ができる．ただし f0 = {{f(0)}, · · · , {f(9)}}, f1 = {{f(1)}, · · · , {f(10)}} である． • P′_{={{{p(v1)}}, · · · , {{p(vn)}}, f0, f1}．} • a′_{(U, V ) = ⟨{{{p(U)}}, f1}, {{{p(V )}}, f0}, ∅⟩} とおいたとき，A′ ={a′(e1,1, e1,2),· · · , a′(em,1, em,2)} • I′_={{{p(v 1)}}, f1}． • G′_={{{p(v n)}}}． 行為の個数は十分の一となっているが最適コスト値 は変わらないことが証明できる．{{p(v)}} は p(v) と 同一視できるし，f1 を「燃料がある」，f0を「燃料が ない」と読めば，この問題は「初期状態で十分な燃料 があるときに最短経路を探す問題」と読み替えられる．

3.2

射影簡約の定義

与えられた無削除タスク T =⟨P, A, I, G⟩ および A の分割A = {A1,· · · , Ak} （すなわち ∪k i=1Ai= Aお よび∀i ̸= j, Ai∩ Aj =∅）に対して新たな無削除タス クを定義する．以下を満たす T′=⟨P′, A′, I′, G′⟩ を T の射影簡約と呼ぶこととする．(1) A′ の要素 a′i は A の要素 Ai と一対一しており，任意の a′i ∈ A′ につい て∀p′∈ pre(a′i)および∀p′∈ add(a′i)は 2P の部分集 合．(2) G′ は{{{g}} | ∀g ∈ G} と定義される．(3) P′ は A′ および G′ で使用されている命題の集合である． 最後に (4) I′={p′∈ P′ | ∃q ∈ p′, q⊆ I} である． 新たな命題や行為が後で述べる条件を満たすならば， それらは元の命題や行為の商集合のような構造になる． 以下では命題の集合 P1,· · · , Px ⊆ P から新たな命題 p′={P1,· · · , Px} ∈ P′ を作ることを命題 P1,· · · , Px を p′に射影するといい，p′を P1,· · · , Pxの射影または 射影命題と呼ぶ．また，行為集合 Ai ={a1,· · · , ak} ⊆ Aから新たな行為 a′i∈ A′を作ることを行為 a1,· · · , ak を a′i に射影するといい，a′i を a1,· · · , ak の射影また は射影行為と呼ぶ．

4

射影簡約の最適コストの等価性

4.1

射影簡約

≥ 元の無削除タスク

補題１ 任意の無削除タスク T =⟨P, A, I, G⟩ および その任意の射影簡約 T′ = ⟨P′, A′, I′, G′⟩ に対し，次 の二条件 (α1), (α2)が成立するとき，T′ の任意の適用 可能行為列 a′1,· · · , a′l について，同コストの T の適 用可能行為列 a1,· · · , al が存在する．更に a′1,· · · , a′l が T′ の充足解のとき，a1,· · · , al もまた T の充足解 である．(α1) Ai とそれに対応する a′i ∈ A′ について {pre(a) | ∀a ∈ Ai} = { ∪|pre(a′ i)| i=1 qi| ∀(q1,· · · , q_|pre(a′_i)_|) ∈∏p′_∈pre(a′ i)p ′_{} が成立．ただし}∏ xxは x の直積で ある．(α2) 任意の a∈ Ai について，∀p′ ∈ add(a′i), ∃q ∈ p′_{, q⊆ add(a) が成立．} 証明：T′ の生成に用いられた A の分割を A とおく． a′1,· · · , a′l は Algorithm 1 によって T の適用可能 行為列 a1,· · · , alに変換可能である．作られた行為列 Algorithm 1変換アルゴリズム 1: a1· · · , alの保存場所を確保する; 2: for i = 1,· · · , l do 3: Iに a1,· · · , ai₋₁ を適用した状態を S とおく; 4: a′_i に対応するA の要素を Ai とおく; 5: Ai の行為のうち，S に適用可能なもの（複数あ る場合は任意）を ai に代入する; 6: end for のコストの等価性は明らかである．また，a′1,· · · , a′lが 充足解であれば，G′の各要素 g′={{g}} は I′ の要素 であるか，a′1,· · · , a′lのいずれかに達成されていること になる．もし g′ ∈ I′ であるならば射影簡約の定義 (4) より g∈ I であり，ある a′iが存在して g′ ∈ add(a′i)で あるならば (α2)より置き換えられた ai∈ Aiは必ず g を達成する．すなわち適用可能でさえあれば a1,· · · , al もまた充足解である．更に，アルゴリズムが５行目に 到達するたびに S に適用可能な行為が必ず一つ以上見 つかるのであれば最終的な行為列の適用可能性も明ら かである．そこで，適切な行為がループごとに必ず一 つ以上見つかることを示す． i 回目以前の for ループでは各段階で適用可能な行 為が一つ以上見つかってきたと仮定する．G′ の要素と 同様に，a′i が適用可能であるためには，pre(a′i) の各 要素 p′ が I′ に含まれているか，a′1,· · · , a′i−1 のいず れかの行為に達成されていることになる．p′∈ I′ の場 合，射影簡約の定義 (4) より，ある q ∈ p′ が存在し て q ⊆ I ⊆ S が成り立つ．j < i なる a′j に p′ が初 めて達成される場合，a′j の属する A の要素を Aj と おくと，仮定より a′j はある aj ∈ Aj に正常に置き換 えられている．この場合も，(α2)より，ある q∈ p′ が 存在して q⊆ add(aj)⊆ S が成り立つ．結局，任意の p′ ∈ pre(a′_i)について，ある q∈ p′ が存在して q ⊆ S が成立している．(α1)より，これはある ai∈ Ai が存 在して pre(ai)⊆ S も成立しているということである． そのような ai は S に適用可能である． □

4.2

射影簡約

≤ 元の無削除タスク

元のタスクの適用可能行為列 a1,· · · , al に対し，ai を含むA の要素を Ai とおき，Ai に対応する A′ の要 素を a′i とおく．このとき，以下が成り立つ．X は一 見奇妙だが後のために必要である． 補題２ 与えられた無削除タスク T =⟨P, A, I, G⟩ お よびその任意の射影簡約 T′ =⟨P′, A′, I′, G′⟩ に対し， 条件 (α1)および次の条件 (α3)が成立するとき，T の 任意の適用可能行為列 a1,· · · , alについて，同コストの T′ の適用可能行為列 a′1,· · · , a′l が存在する．更に，条 件 (α4)が成立するとき，a1,· · · , alが T の充足解のと き，a′1,· · · , a′lもまた T′の充足解である．(α3) P のう ち，絶対に達成できない命題の集合を X とおく．任意 の相異なる a′i, a′j∈ A′ について，a′i, a′j に対応するA の要素を Ai, Aj とおく．ある p′∈ pre(a′i), q∈ p′ およ び aj∈ Ajが存在して，(q∩ add(aj))\ (I ∪ X) ̸= ∅ が 成立するならば，p′∈ pre(a′j)∪ add(a′j)も成立．(α4) 任意の a′i ∈ A′ について，a′i に対応する A の要素を Ai とおく．ある ai∈ Ai および g∈ G が g ∈ add(ai) を満たすならば{{g}} ∈ add(a′i)． 証明：適用可能でさえあればコストは明らかに等しい． まず，a′1 から a′i−1 までが I′ に適用可能だったときに a′_i の適用可能性を考える． 条件 (α1)より，任意の p′∈ pre(a′i)について，ある q∈ p′が存在して，q⊆ pre(ai)が成立する．もし q⊆ I ならば，射影簡約の定義 (4) より p′ ∈ I′である．a′1に ついては必ずこれが成り立つ．q⊆ I でなければ，j < i なる aj が存在して (q∩ add(aj))\ (I ∪ X) ̸= ∅ が成 立する．よって条件 (α3)より，p′∈ pre(a′j)∪ add(a′j) が成り立つ．add(a′j)が p′ を達成するならば何も問題 は無い．そうでない場合，p′ ∈ pre(a′j)および a′1から a′_i−1 が I′ に適用可能であるという仮定より，a′1 から a′_j−1 のいずれかによって p′ は達成されている．すな わち，a′i は a′1,· · · , a′i−1 の後に適用可能である． また条件 (α4)より，ある aiが g∈ G を達成するな らば，a′i は {{g}} を達成する．a1,· · · , al が G を達 成するならば a′1,· · · , a′l は G′ を達成する． □

5

射影簡約の生成

上記のようにタスクが ⟨P, A, I, G⟩ の形で与えられ たときに，(α1) から (α4)を満たす良い射影簡約を探 索することは計算コストの高い問題であるように思わ れる．しかし，現実には IPC などではプランニングタ スクは 3.1 節のように引数によって抽象化された命題 および行為によって与えられることがデファクトスタ ンダードとなっている．これを利用して，ある射影簡 約を効率よく構成することができる．

5.1

述語論理プランニング

本稿では５つ組 Tp=⟨O, R, AS, I, G⟩ を述語論理プ ランニングタスクと呼ぶ． • O ：オブジェクトの集合．オブジェクトはそれ以 上分解できない単なるモノである． • R ：述語の集合．一階述語論理等で使用される 述語と同じものである．述語の全ての引数にオブ ジェクトを代入したものを命題と呼ぶ．全ての命 題の集合 P (Tp)は O と R から陰に定義される． • AS：行為スキーマの集合．行為スキーマ as ∈ AS は as ごとに定まった個数のオブジェクトの組から 行為への写像である．具体的には，as は写像の引 数を用いて実体化された命題の集合の三つ組（そ れぞれ前提条件 pre(as)，追加効果 add(as)，削除 効果 del(as)）から成り，pre(as), add(as), del(as) に as の引数を単純に代入したものが射影後の行 為 a の pre(a), add(a), del(as) となる．全ての行

為の集合 A(Tp)は O と A から陰に定義される． • 初期状態 I および目標 G はそれぞれ P (Tp) の 部分集合である． 以下，述語論理タスク Tp から作られる命題論理タス クを T (Tp)とおくこととする． 3.1 節の関数 a が行為スキーマ，p, f などが述語， e1,1などがオブジェクトの一例である．ただし，Tpから T (Tp)を作る際にはオブジェクトは意味を無視して全通 り a に代入されるため，3.1 節の P, A は P (Tp), A(Tp) ではない．

5.2

述語論理タスクの射影簡約の条件

以下では T (Tp)の射影簡約 T (Tp)′=⟨P′, A′, I′, G′⟩ を作ることを考える．P′, I′, G′ は定義に基づいて A′ および T (Tp)から自動的に定まるため，A′ にのみ注 意を払えばよい． 本稿では，G で使われている述語の集合を RG ⊆ R とおいたとき，述語論理タスクの R, AS, RG のみを用 いて O, I, G の値によらずに作ることのできる射影簡 約について考える．そのため，本稿では行為スキーマ の構造を利用して行為の射影を作る方法を提案する． 提案手法では，A′ の全ての行為は同一の行為スキー マから具象化された行為の射影であり，更に，同一の行 為スキーマから作られた射影行為は互いに対称的な構造

をとる．具体的には，各行為スキーマ as∈ AS の各引 数に束縛または自由の値を割当て，as から具象化された 行為のうち自由引数が等しい行為ごとに一つの a′∈ A′ を作ることとする．束縛引数の束縛作用素は∀ であり， a′ の元になった as の束縛引数が n 個であれば，a′ は |O|n_{個の行為から作られた射影である．前提条件につい} ては，まず行為スキーマ as∈ AS ごとに∪pre(as)j=

pre(as)を満たす pre(as)1,· · · , pre(as)n を定める．as

から具象化された行為 a における pre(as)j の値を pre(a)j とおいたとき，行為 a′i ∈ A′ に射影される元 の行為の集合 Ai⊆ A に対し，pre(a′i) ={{∀q′ | ∃a ∈ Ai, q′ = pre(a)j} | j ∈ {1, · · · , n}} と定める．これに よって同一の行為スキーマから作られた射影行為の対 称性が担保される．これらの pre(as)1, · · · , pre(as)n を pre(as) の射影と呼ぶこととする．add(as) の射影 add(as)1,· · · , add(as)mを用いて add(a′i)も同様に定

義する．ただし ∪add(as)j = add(as) は必ずしも満 たさなくてよい． この方法で作られたタスクが (α1)の左辺⊆ 右辺お よび (α2) を常に満たすことは明らかである．(α1)の 左辺⊇ 右辺については次が成り立つ． 補題３ 上記の方法で T (Tp)′ を作るとき，次の条件 (β) が成り立つならば任意の a′i ∈ A′ および a′i に対

応する Ai ⊆ A(Tp)について，{pre(a) | ∀a ∈ Ai} ⊇

{∪|pre(a′i)| i=1 qi | ∀(q1,· · · , q_|pre(a′_i)|)∈ ∏ p_∈pre(a′_i)p} が 成り立つ．(β) 各 as∈ AS について pre(as) に出現す る各束縛引数が pre(as)1, · · · , pre(as)n の高々一つに しか含まれない．

証明：as ごとに考えれば十分．∪pre(as)j= pre(as)よ

り，pre(as) に出現するそれぞれの束縛引数は pre(as)1, · · · , pre(as)nの少なくとも一つには必ず含まれている． よって仮定より，pre(as) の各束縛引数を含む pre(as) の写像はちょうど一つずつ存在する．よって，任意の (q1,· · · , q_|pre(a′_i)_|) ∈ ∏ p∈pre(a′_i)p について，q1, · · · , q_|pre(a′ i)|の中の各束縛引数の値を抽出して as に代入し たものを a とおくと，a は Ai の要素であり，pre(a) = ∪ qj を満たす． □ 次に，この射影簡約が (α3)を満たすための条件につ いて考える． 以下，述語のうちどの行為スキーマの追加効果およ び削除効果にも含まれない述語を静的述語と呼び，静 的述語から作られた命題を静的命題と呼ぶこととする． 反対に，静的述語，静的命題ではない述語，命題をそ れぞれ動的述語および動的命題と呼ぶこととする．無 削除プランニングタスクにおいては，個々の行為を改 変して add(a) に pre(a) の要素を任意に追加しても解 空間に変化は無いため，後の様々な不都合を解消する ために，以下，add(as) は pre(as) の全ての命題を必 ず含むものとする．付け加えた後も，動的／静的の区 別は元々の区別を使用することとする．

以下，Q ={pre(as)j | ∀as ∈ AS, ∀j} ∪ {add(as)j

| ∀as ∈ AS, ∀j} とおく．Q の任意の要素 p について， ins(p) ={{af, ab による p の 実体化| ∀p の束縛引数 ab} | ∀p の自由引数 af} とおく．任意の p1, p2 ∈ Q， および任意の q1∈ ins(p1), q2∈ ins(p2)について，(1) q1 = q2 または (2) ∀x ∈ q1,∀y ∈ q2, x∩ y = ∅ が成 り立つとき q1 と q2 は同型であると呼ぶこととする． q1= q2 でも同型ではない場合があることに注意せよ． また，任意の p1, p2∈ Q のうち，同じ行為スキーマに 属するものについて，p1 の束縛引数から p2 の束縛引 数への全単射が存在して，p1 の束縛引数を p2 の束縛 引数で置き換えたものが p2 と等しいとき（すなわち p1 と p2 に出現する自由引数が位置も含めて等しいと き），p1と p2 は等価であると呼ぶこととする．p1と p2 は同じ束縛引数を含んでいてもかまわない． このとき，次の補題が成り立つ． 補題４ 次の条件 (γ) が成り立つならば (α3)が成立す る．(γ) 任意の as0, as∈ AS（as は as0であり得る）お よび as0の前提条件の任意の射影 pre(as0)i⊆ pre(as0) について次の条件 (γ1), (γ2), (γ3)のいずれかが成立： (γ1) add(as)は pre(as0)i の動的述語を全く含まない． (γ2) pre(as0)iの任意の動的命題 p0および p0と同じ述 語からなる add(as) の任意の命題 p について，add(as) の射影のうち p を含むものの中に pre(as0)i と同型な ものが存在．(γ3) pre(as0)i の任意の動的命題 p0およ び p0 と同じ述語からなる add(as) の任意の命題 p に ついて，p と等価な命題を一つ以上含む pre(as) の射 影のうち p を含むものの中に pre(as0)i と同型なもの が存在． 証明：与えられた述語論理タスクおよびその射影簡約が 条件 (γ) を満たしていると仮定する．絶対に達成されな い命題の集合を X とおく．任意の相異なる a′i, a′j∈ A′ について，a′i, a′j に対応する A の要素を Ai, Aj とお く．また，a′i, a′j に対応する AS の要素を asi, asj と おく． ある p′i ∈ pre(a′i), q ∈ p′i および aj ∈ Aj が存在し て，(q∩ add(aj))\ (I ∪ X) ̸= ∅ が成立したと仮定す る．p′i の元になった pre(asi)の射影を pi とおく．各 as ∈ AS の add(as) に pre(as) を付け加えたとして も，任意の静的命題は I によらず必ず I∪ X に含まれ るため，(q∩ add(aj))\ (I ∪ X) の要素は全て動的命 題である．すなわち，add(asj) は p′i の動的述語を含 んでいるため (γ1)は成立しない．よって仮定より (γ2) または (γ3)が成立する． (q∩add(aj))\(I ∪X) のある要素を v とおき，v を生

み出した p′i および add(asj)の命題をそれぞれ wi, wj とおくと，wi ∈ pi である．また，wi と wj の述語は 同じであるから， (γ2)が成立している場合，wj を含 む add(asj)の射影のうち pi と同型なもの pj が存在 する．a′j における pj から作られた射影命題を p′j とお くと，p′i, p′j はそれぞれ ins(pi), ins(pj)の要素であり， q∈ p′_i, add(aj)∈ p′j が成り立つ．(q∩ add(aj))\ (I ∪ X)⊆ q ∩ add(aj)̸= ∅ より同型の条件の (2) は成り立 たないため，同型の条件 (1)，すなわち p′j= p′i が成り 立つ． (γ3)が成立している場合も，w と等価な命題を含む pre(asj)の射影のうち pi と同型なもの pj が存在し， 同様の議論が成立する． 以上より，p′_i∈ pre(a′_j)∪ add(a′_j)が成立． □

5.3

述語論理タスクの射影簡約の生成

前述の手法を用い，条件 (β), (γ), (α4)を全て満たさ なければならないとしても，射影簡約の生成は非常に 自由度の高い計算である．以下，本稿では以下のアル ゴリズムを提案する．ただし，p∈ pre(as) について， gr_pre(p) ⊆ pre(as) は p および p と束縛引数を共有 する命題の集合，p ∈ add(as) について，gradd(p) ⊆ add(as)は p および p と束縛引数を共有する命題の集 合である． 1. 各行為スキーマの全ての引数に [束縛] というラ ベルを設定． 2. r∈ RG の命題に含まれる引数を [自由] に設定． 3. as∈ AS ごとに pre(as) の複数の動的命題に含 まれる全ての引数を [自由] に設定． 4. as∈ AS について as のいずれの動的命題にも含 まれない全ての引数を [自由] に設定． 5. ある as ∈ AS について，pre(as) のある動的命 題 p1の [束縛] 引数 a1 と pre(as) の別の動的命 題 p2 の [束縛] 引数 a2の両方を含む静的命題が pre(as)に存在する場合，a1と a2 のうち一方を 任意に選んで [自由] に設定．そのような静的命題 が存在しなくなるまでこのステップを繰り返す． 6. 動的述語 r ∈ R ごとに，任意の as0, as ∈ AS について以下が成り立っているかどうかを調べ る：もし pre(as0)および add(as) が r の命題を 含むのであれば，pre(as0)の r の任意の命題 p0 と add(as) の r の任意の命題 p について，(γ2′) grpre(p0) と gradd(p) が同型であるか，(γ3′) あ る p1 ∈ pre(as) が存在して，p と p1 が等価で gr_pre(p0)と grpre(p1)が同型．この条件がもし成 り立っていないのであれば，p0または p または pと同型な pre(as) の命題を一つ選んで，選んだ 命題の [束縛] 引数を任意に一つ選んで [自由] と する．全ての r について，条件が成立するまで このステップを繰り返す． 7. 行為スキーマ as∈ AS について，前提条件の動的

命題 p∈ pre(as) ごとに grpre(p)を pre(as) の一

つの射影とする．また，束縛引数を全く含まない 静的命題 p∈ pre(as) ごとに p を一つの射影とす る．追加効果については，動的命題 p∈ add(as) ごとに gradd(p)を add(as) の一つの射影とする． 補題５ 上のアルゴリズムによって生成された射影簡 約は (α4), (β), (γ)を満たす． 証明：まず，ステップ 7 の定義より，全ての引数が自 由な命題は前提条件においても追加効果においてもそ れ単体で射影を構成する．よってステップ 2 の時点で (α4)が成立し，[自由] 引数を [束縛] 引数に戻すことは ないためアルゴリズムの終了時点でも (α4)は成立する． またステップ 3 によって全ての束縛引数は pre(as) の高々一つの動的命題にしか含まれなくなる．ステッ プ 4 によって全ての束縛引数はちょうど一つの動的命 題に含まれることになる．またステップ 5 によって各 静的命題の所属が一通りに定まるため，前提条件中の 各束縛引数は pre(as) の射影のうちの高々一つにしか 含まれない．すなわち (β) が成立．(α4)と同様にこの 性質は最後まで保たれる． 最後に，ステップ 6 の条件は (γ) そのものであるた め，条件が満たされないままステップ 6 が終了すると いうことがなければ，(γ) は明らかに満たされている． ステップ 6 が途中で条件を満たさずに最後まで処理を 繰り返した場合，全ての引数は [自由] となる．全ての 引数が [自由] のとき，射影簡約の各射影命題は P の単 一の命題から成る．よって同じ述語からなる全ての命 題は同型の二条件を満たすため，このアルゴリズムに よって生成された射影簡約は (γ) も満たす． □ なお，行為スキーマの前提条件または追加効果の二 つの射影が同型であるかどうかは以下の補題を利用す れば多項式時間で判定できる． 補題６ 二つの q1, q2∈ Q について，q1と q2が同型で あるための必要十分条件は，(1) q1の命題の数と q2の 命題の数が同じ．(2) q1 と q2 の述語の集合が等しい． (3) q1 と q2 のある順列 q1 = {p1,1,· · · , p1,n}, q2 = {p2,1,· · · , p2,n} が存在して以下を全て満たす：(3-1)

∀i ∈ {1, · · · , n} について p1,i の述語と p2,i の述語が

射が存在して，q1の束縛引数を q2の束縛引数に移して，

自由引数を無視したときに p1,1= p2,1,· · · , p1,n= p2,n．

(3-3) free(p1,1, p2,1) =· · · = free(p1,n, p2,n)．free(p1, p2)

は p1および p2 の自由引数の集合の分割であって，p1 の引数 a1 および p2 の引数 a2について，a1と a2が 同じ集合に属する ⇔ ある位置 j が存在して p1 の j 番目の引数が a1 で p2の j 番目の引数が a2． 証明：まず，q1と q2が同型であるときに (1), (2), (3) が成り立つことの対偶を示す．(1), (2), (3-1), (3-2) の いずれかが満たされない場合は明らかに同型の条件を 満たさない．任意の順列について (3-3) が成立しないと き，ある i, j∈ {1, · · · , n} が存在して，free(p1,i, p2,i)̸=

free(p1,j, p2,j)を満たす．なおかつ，q1 のある引数 a1

と q2 のある引数 a2 が存在して，free(p1,i, p2,i) では

a1, a2 は異なる集合に属し，free(p1,j, p2,j)では a1, a2

は同じ集合に属す．命題 p1, p2 について，free(p1, p2)

の分割ごとに同じ引数を代入すれば p1から実体化され

る命題 x と p2 から実体化される命題 y が等しく，そ

うでなければ x̸= y となる．よって free(p1,i, p2,i)の

分割ごとに値が同じである引数の値のうち，a1 と a2 が異なるようなものを選べば，実体化後に p1,i = p2,i かつ p1,j ̸= p2,iを満たす．すなわち，同型の条件の (1) も (2) も満たさないような実体化を作ることができる． 一方，(1), (2), (3) が成り立つならば，q1, q2 にどの ような引数を代入しても，全ての命題が等しくなるか 全く共通部分を含まないかのどちらかである． 以上より q1と q2 は同型． □

6

ベンチマークドメインへの適用

近年のプランニング研究では，作成したアルゴリズ ムを IPC のベンチマーク問題で評価することが通例と なっている．本研究は理論的研究ではあるが，IPC の ベンチマークドメインの削除効果緩和に射影簡約を適 用したときに問題がどのように変化するかを調査した． IPCでは通常，述語論理タスクの要素のうち，R, AS をドメインと呼んで一つのテキストファイルによって 提供し，個別の問題ごとに個別のテキストファイルで O, I, Gを定義する，という形式が取られている．つま り，IPC においては RG は個別の問題ごとに別々に定 義されているのであるが，本稿では，ドメインごとに 典型的な RG を選んで，R, AS および選んだ RG に対 して射影簡約を求めた． 射影簡約は提案アルゴリズムに従って著者が手作業 によって求めた．O や I の要素数がとても大きくなる ことはあっても，ドメインは人間が手作業で簡約を求 められる程度に十分小さい場合が多く，これは提案ア ルゴリズムがとても高速に簡約を作ることができるこ との証左である．ただし，各ステップにおいて束縛変 数へ変換する候補が複数ある場合，提案アルゴリズム は依然として多少の任意性があるが，候補が実際に複 数になった際には内容を吟味しながら著者が注意深く 選んだ．候補の選び方によっては異なる簡約が作られ る可能性が多分にある． 表 1 に IPC のドメインおよび著者が提案アルゴリズ ムを用いて生成した簡約による変化の一覧を示す．な お，いくつかのドメインは本稿の述語論理タスクの定 義を拡張した定義の元で記述されているが，それらは 本稿の定義の述語論理タスクに変換できることが知ら れているため，そのようなものも表に含めた．また，提 案アルゴリズムでは自明な射影簡約しか作れなかった ドメインも数多くあったが，IPC ベンチマークドメイ ンの中には問題の意味内容や我々の現実世界との対比 から考えると明らかに定義の誤りを持つものがいくつ か存在する．それらの定義を適宜修正すれば，表 1 の ドメインに加え，表 2 のドメインに対しても提案アル ゴリズムは射影簡約を作ることができた． 表 1, 2 の各ドメインでは，行為の個数および各行 為の引数の個数はそれぞれ数個ずつ程度であった．表 1, 2を俯瞰すると，削除効果緩和が燃料や容量といっ た個数や量の違いを無意味にするときに，提案アルゴ リズムがそれらの数量を消し去っていることが分かる． ただし，例えば mystery ドメインは no-mystery ドメ インと全く同型なドメインであるが，述語名や行為ス キーマ名が暗号化されていて，解説無しにドメインの 意味を判断することは大変難しい．そのようなドメイ ンに対しても，提案アルゴリズムを機械的に適用する ことによって問題を簡約することができた．

7

まとめと今後の課題

本研究では無削除プランニングタスクを簡約するた めの枠組み，および簡約を実際に求めるアルゴリズム を提案した．提案手法は問題のドメインのみから簡約 を作る方法であり，作られた簡約は問題の初期状態等 によらずいつでも使用することができる．また，ドメ インのサイズは通常とても小さく，提案アルゴリズム は人間が実行できるほどに高速である． しかし，より多くのドメインを更に簡約するために は，いくつかの課題が残っている．表 1, 2 以外の IPC ドメインは自明でないどのような簡約も作れないわけ ではなく，提案アルゴリズムに従わない簡約ならば作 ることのドメインがいくつかあった． 例えば trucks ドメインの問題は，述語論理タスクを 命題論理タスクに変換し，その後 [5] 等の手法を使っ て不要な命題や行為を消去すれば，命題論理の射影緩 和を作ることができる．あるいは，elevators ドメイン

表 1: IPC ドメインとその簡約 ドメイン ドメインの簡単な解説 削除効果緩和による変化 簡約による効果 備考 gripper 多腕ロボットによるボール運び． 腕は一つで十分になる． 腕が一つになる． no-mystery 宇宙船による荷物配送． 燃料と容量が無限になる． 燃料を省略． (mystery) 同上． 同上． 同上． 述語名等が暗号化． pathways 化学物質の反応経路探索． 各化合物は一個で十分． 化合物の個数を省略． TPP 商店の品物を倉庫に集約． 各商店で品物を一つ買えば十分． 品物の個数を省略． 候補が複数． transport 荷物を宅配する． トラックの容量が無限になる． トラックの容量を省略． 非単位コストを無視． 表 2: 定義の誤りを修正すれば簡約できる IPC ドメイン ドメイン ドメインの簡単な解説 削除効果緩和による変化 簡約による効果 備考 elevators エレベータの制御． エレベータの容量が無限． エレベータの容量を省略． 非単位コストを無視． no-mystery 宇宙船による荷物配送． 燃料と容量が無限になる． 燃料と容量を省略． (mystery) 同上． 同上． 同上． 述語名等が暗号化． openstacks 製造ライン数の最小化． 製造ラインは一つで十分． ２以上の製造ライン数を省略． の問題も，同様の手法を用いれば定義に誤りがあるま まで射影緩和を作ることができる．述語論理タスクか らの簡約は強力ではあるが，このように命題論理タス クに変換した後の情報を用いた簡約を作ることも重要 である． 一方，述語論理タスクの射影簡約を更に発展させる ことも重要な課題の一つである．例えば movie ドメイ ンは前提条件に動的命題を含まない行為スキーマを持 つドメインであるが，提案アルゴリズムを適用すると それらの行為スキーマの引数は自由引数になってしま い，自明な簡約しか得ることができない．しかし，種々 の条件さえ満たしていれば，複数の動的命題からなる 射影や束縛変数を含む静的命題の射影など，もっと自 由な形の射影命題も許されるはずである． また，表 2 では著者がドメインの記述に手を加えた が，近年ではエージェント自身に自動的に世界のモデ ルを生成させる試みも研究されており，いつでも健全 な定義のドメインが得られるとは限らない（例えば [6] など）．そのような状況でも利用できるような強力な 簡約も将来的には必要である．

謝辞

本研究は JSPS 特別研究員奨励費（課題番号 24・8506） の助成を受けたものです．

参考文献

[1] Blai Bonet and H´ector Geffner. Planning as heuristic search. Artificial Intelligence, 129(1):5–33, 2001. [2] Tom Bylander. The computational complexity of

propositional strips planning. Artificial Intelligence, 69(1):165–204, 1994.

[3] Malik Ghallab, Dana Nau, and Paolo Traverso.

Au-tomated planning: theory & practice. Morgan

Kauf-mann, 2004.

[4] M. Helmert and C. Domshlak. Landmarks, critical paths and abstractions: What’s the difference anyway? In Proceedings of the Nineteenth International

Confer-ence on Automated Planning and Scheduling (ICAPS 2009), pages 162–169, 2009.

[5] T. Imai and A. Fukunaga. A practical, integer-linear programming model for the delete-relaxation in cost-optimal planning. In ECAI, 2014.

[6] Q. Yang and Y. Jiang. Learning models from plan ex-amples with incomplete knowledge. In Proceedings of

the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005), pages 241–