OPS5 (Official Production System 5)

特徴


[Brownston 1985]

前向き型推論プロダクションシステム

構成要素1: WM要素


WM要素の形式: (<クラス名> ... ^<属性>_i <値>_i ...)

例: 個人のスケジュール管理の問題．

(空き時間 ^月 11 ^日 8 ^開始時刻 9 ^継続時間 8 ^終了時刻 17) (行動 ^確定?　no ^継続時間　3 ^詳細　研究会) (行動 ^確定?　no ^継続時間　2 ^詳細　会議) (行動 ^確定?　no ^継続時間　2 ^詳細　昼食)

構成要素2: PM要素


PM要素の形式: (P <プロダクション名> <LHS> → <RHS> )

<LHS>: パターンの並び

パターン: (<クラス名>... ^<属性>_i <値 >_i ...) または -(<クラス名>... ^<属性>_i <値 >_i ...)

<RHS>: 行動の並び

PM要素のLHS


条件の規定

1. ^<属性> <項>
2. ^<属性> <オペレータ> <項>
3. ^<属性> {<変数>...<オペレータ>_i < 項>_i ...} (中括弧{ } で囲まれたものは連言を表す)

項として指定できるもの

• <定数>： <アトム> (英数字の列で，それ自体が値)
• <変数>： <アトム>をカギ括弧で挟んだもの (i.e. <x>)
• <選言>： <<...<定数>/<変数> ...>>
• (compute <算術式>): <算術式> を計算した値を指す．

オペレータとして使える関係式

= (equal-to)
<> (not-equal-to)
< (less-than)
> (greater-than)
<= (less-than-or-equal-to)
>= (greater-than-or-equal-to)
<=> (same-type-as)

<LHS>のパターンとWM要素の照合


与えられた<LHS>のパターン(<クラス名> ...<属性 >_i <条件>_i)と WM要素(<クラス名> ...^<属性>_i <値>_i)に対して，<クラ ス名>が一致し，かつ<LHS>の各<属性>_iについて WMの対応する <値>_i が <LHS>の<条件 >_iで規定された条件を満足するとき，両者は照合(match)するという．

例1:

(空き時間 ^月 11 ^日 8) (行動 ^継続時間 3) -(予約 ^対象 レストラン)

例2:

(行動 ^継続時間 > 3) (空き時間 ^開始時刻 <t> ^終了時刻 <t> )

<RHS>の記述形式


<RHS>では<LHS> に対して照合したWM要素の集合に対する操 作を規定する．以下のものが用いられる．

(make <クラス> ... <属性 >_i <値>_i...): 新しい要素をWMに追 加

(modify <LHSのパターン番号> ... <属性 >_i <値>_i...): 既に存在するWMの属 性値を変更

(bind <変数> <項>): <変数 >に <項>で規定された値を束縛する．

(remove <LHSのパターン番号>): WM要 素を削除する

PM要素の例


例1

(p 昼食約束 (行動 ^確定? no ^継続時間 <p> ^詳細 昼食) (空き時間 ^月 <m > ^日 <d> ^開始時刻 {<s> <= 12} ^終了時刻 {<e> >= (compute 12+<p>)}) → (bind <lunch-end-time> (compute 12+<p>)) (make 空き時間 ^開始時刻 <lunch-end-time> ^継続時間 <(compute <e> - <lunch-end-time>)> ^終了時刻 <e>))

例2

(p 行動の確定 (行動 ^確定? no ^継続時間 <p> ^詳細 {<detail> <> 昼食}) (空き時間 ^月 <m > ^日 <d> ^開始時刻 <s> ^継続時間 {<e> >= <p>}) → (modify 1 ^確定? yes ^月 <m> ^日 <d> ^開始時刻 <s> ^継続時間 <p> ^終了時刻 (compute <s> + <p>)) (modify 2 ^開始時刻 (compute <s> + <p>) ^継続時間 (compute <e> - <p>))

例3

(p 行動の確定 {<activity> (行動 ^確定? no ^継続時間 <p> ^詳細 {<detail> <> 昼食})} {<avail-time> (空き時間 ^月 <m > ^日 <d> ^開始時刻 <s> ^継続時間 {<e> >= <p>}) → (modify <activity> ^確定? yes ^月 <m> ^日 <d>) (modify <avail-timey> ^終了時刻 (compute <s> + <p>) ^継続時間 (compute <e> - <p>)

例4

(p 不要WM要素の除去 (空き時間 ^月 <m> ^日 <d> ^継続時間 0) → (remove 1)

OPS5の基本動作


OPS5の基本動作




時刻タグ


OPS5の各WM要素には，それが生成された時刻を表す 時刻タグがつけられる．(make と remove は +1され，modify は +2 される)

例化 (instantiation) と衝突集合 (conflict set)


PM要素の LHS を満足する WM要素の集合を例化 と呼ぶ．

例化の集合を衝突集合(conflict set)と呼ぶ．

衝突解消(conflict resolution)


衝突解消の一般原則

refraction: 同一の例化は2回以上実行され ない．

recency: その条件要素が最も新しいWM要素 に照合した例化を優先する．

specificity: 最も詳細な LHSを持つ規則に 照合したWM要素を優先する．

arbitrary choice: ランダムに選択する．

LEX (Lexicographic sort)戦略

衝突集合から既に実行された例化を取り除く(refraction). 例化における時刻タグの最新性に基づいて例化をソートする．その中か ら最も新しい例化を選択する(recency)． 最も新しい例化が2個以上あれば, specificity の原則に基づいて選択す る． まだ唯一にならなければ任意に選択する．

MEA (Means End Analysis)戦略

衝突集合から既に実行された例化を取り除く(refraction). 最初の時刻タグの最新性に基づいて例化をソートする．最も新しい例化 を選択する(recency)． 例化における時刻タグの最新性に基づいて例化をソートする．その中か ら最も新しい例化を選択する(recency)． 最も新しい例化が2個以上あれば, specificity の原則に基づいて選択す る． まだ唯一にならなければ任意に選択する．

衝突集合の例 (instantiation-n は n番目の例化を意味する)

instantiation-1 rule-a 10 9 6 43
instantiation-2 rule-d 10 43 9
instantiation-3 rule-b 12 24 17
instantiation-4 rule-b 12 9 23
instantiation-5 rule-c 9
instantiation-6 rule-c 12

...Return

• 講義の詳細