Answer Set ProgrammingでDynamic Systemを表現する

はじめに

Vladimir Lifschitz氏によるAnswer Set Programming (Draft) (リンク)の第7章の要約です。作りたかったものがあって、そのために読みたかったので、ついでに要約・翻訳しておきました。CLINGOの文法がわかっている人や、同書の第1,2,6章を読んでいる人であれば理解できる内容となっています。そんな人いない

Dynamic System¹とは？

答え：何かアクションをすると状態が変わるようなシステム。

このシステムにおいて、予想とプラニングの二つのことができる

• 予想問題：アクションのシーケンスが与えられた時、その後の状態はどうなるか？
• プラニング問題：初期状態と目標状態が与えられたとき、その目標を達成できるようなアクションのシーケンスは何か？

例：The Block World

以降の例で使用するBlock Worldを紹介します。

• Block worldでは、ブロックが積み重なっていくつかのタワーをなしている。
• タワーは全てテーブルに支えられている。
• 例えば、3つのブロックa, b, cの場合は以下の13の状態が考えられる

 a     b     a     c     b     c
 b     a     c     a     c     b     a
 c     c     b     b     a     a     b c
----  ----  ----  ----  ----  ----  -----
 S1    S2    S3    S4    S5    S6    S7

 b      a      c      b      c
 a c    c b    a b    c a    b a    a b c
-----  -----  -----  -----  -----  -------
 S8     S9     S10    S11    S12     S13

• アクションはmove(x, y)のみ可能で、xをyの上に移動するという意味。xはブロックでyはブロックか机である。

状態遷移図

Dynamic systemは状態遷移図で表すことができる。これは次のような有向グラフである。

• 各頂点は状態を表す
• 辺はアクションを表す。

例えば次のような状態遷移図となる

      move(a, c)      move(a, table)
  S9 <----------- S7 ----------------> S13
                  |
                  |  move(c, a)
                  V
                  S4

• 予想問題は初期状態の頂点から、与えられたアクションが示す辺をたどっていった時の終点を求める問題として可視化できる。
• プラニング問題は、初期状態の頂点から、目的の頂点までのパス(道)を探す問題になる

時間

時間は0からhまでの整数で表す。move(a,c)が時間0と1の間に起きることをCLINGOではこのように書く²

occurs(move(a,c), 0).

Dynamic Systemはfluentsと呼ばれるパラメータで表すことができる。例えば、block worldの状態S7はaがbの上、bがテーブルの上、cがテーブルの上であることを以下のように表す。

loc(a, b), loc(b, tabel), loc(c, table)

ある時間Tに条件Cであることは、述語holdsで表す。例えば、状態S7が時間0で起ることは次のように示す

holds(loc(a, b), 0).
holds(loc(b, table), 0).
holds(loc(c, table), 0).

ある時間に各ブロックがただ一つの場所で表されることは、次のように表すことができる。

:- #count{L: holds(loc(B, L), T)} != 1, block(B), T=0..h.

アクションによる状態の変化

Block worldのアクションが行われた後の状態の変化は次のように表される。

holds(loc(B, L), T+1) :- occurs(move(B, L), T).

この例の時間T+1のfluentは、時間Tで行われたアクションのみに依存しているが、時間Tでの状態によって結果のfluentが変化する場合もある。

また、アクションに影響されないfluentは、前の時間の状態を保つことを示したいが、これが一般的に困難であり、the frame problem と呼ばれる。Block worldの場合は次のように表現できる。

holds(loc(B, L), T+1) :- holds(loc(B, L), T),
                         not not holds(loc(B,L), T+1),
                         T=0..h-1.

実行不可能なアクション

実行不可能なアクションは制約によって記述される。

• 同じブロックの上にブロックを置くことはできない

B1 = B2 :- holds(loc(B1, B), T), holds(loc(B2, B), T), block(B).

• ブロックの上にブロックがおいてある場合、ブロックは移動できない

:- occurs(move(B, L), T), holds(loc(_, B), T).

• 同じ場所に移動することはできない

:- occurs(move(B,L),T), holds(loc(B,L),T).

ここで、2つ目と3つ目はアクションを行う前の状態への制約(前提)となっている。1つ目はfluentsの条件であるが、アクションによる状態変化の制約からアクションの制約となる。アクションの制約として直接表現すると次のようになる。

:- occurs(move(_,B),T), holds(loc(_,B),T), block(B).

予想問題

ここまでのルールの記述から予想問題を記述することは簡単で、以下のルールを加えるだけ

holds(C,0) :- init(C).
final(C) :- holds(C,h).
#show final/1

最後に、存在するブロックblock/1、初期条件init/1、最大の時間h、アクションのシーケンスoccurs/2を定義すればよい。

プラニング問題

実行可能なアクションをaction/1で定義する。

action(move(B1,B2)) :-  block(B1), block(B2), B1 != B2.
action(move(B,table)) :- block(B).
{occurs(A,T) : action(A)} = 1 :- T = 0..h-1.

そして、初期条件のルールと目標条件の制約を加える。²

holds(C,0) :- init(C).
:- not holds(F, h), goal(F).
#show occurs/2.

さいごに、初期条件init/1、目標条件goal/1、存在するブロックblock/1、最大の時間hを定義すれば良い。

より短いシーケンス

ここまでのプラニング問題はちょうど時間hで実行可能なプランを求めるものであったが、実際は時間h以下のプランを求めたいことが多い。その場合、次のアクションを追加する。

action(wait).

また、より短いシーケンスを求めるには、次を追加する。

#maximize{T : occurs(wait,T)}.

同時実行

複数のアクションを同じ時間に実行できる問題を考える。そのためには

{occurs(A,T) : action(A)} = 1 :- T = 0..h-1.

を次のように書き換える

1 {occurs(A,T) : action(A)} m :- T = 0..h-1.

置きたい場所が移動していてはいけないという制約を加える。

:- occurs(move(_,B), T), occurs(move(B, _), T).

(同時実行可能な場合、実行不可能なアクションの制約3は前者の書き方でなければ動かなくなるので注意。)

waitのアクションを許可する場合、waitと他のアクションを同時実行することはそのアクションのみを実行することと等価なので、それを排除する。

A = wait :- occurs(wait, T), occurs(A, T).

まとめ

ASPがいかにdynamic systemを表現するのに適しているかがわかったと思います。手続き型言語だと後から変更したい制約があった時とか面倒だったりするのが、宣言型言語だと簡単なのがいいですね。

参考文献

Answer Set Programming (Draft) : Vladimir Lifschitz