人工知能5

人工知能
GPS とハノイの塔,Logic Theorist
Ｌecture 11
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
GPS
(general problem solver)
および
計画
Newell, Shaw, Simon(1957)によるLTの続き
ハノイの塔：箱を積む場所を変える
• ロボットアームが箱を積み替えるオペレータ
• 机の上から箱を持ち上げる：PICKUP（x)
• 机の上の場所αに箱を置く：
PUTDOWN(x,α)
• 箱yの上に箱xを置く：PUTON(x,y)
• 箱yの上の箱xを持ち上げる：TAKEOFF(x,y)
ハノイの塔問題
• ３つの柱A，B，Cと中心に穴の空いた2枚の円板と
があり，円板1は円板2より小さい．
• 上から円板1，円板2の順に柱Aに置かれたのを柱B
に移す
条件：大きな円板を小さな円板の上に置くことは出来
ず，また，一回の動作で一枚の円板しか動かすこと
が出来ない
A
B
A
B
＜状態＞の記述
•
•
•
•
ON(x,y)：円板xが円板yの上にある状態
AT(x,Y)：円板xが柱Yの最下部にある状態
CLEAR(x)：円板xの上に何もない状態
VAC (X)：柱Xに円板が無い状態
動作オペレータ
MV1(x,y,Z)：円板xを円板yの上から柱Zに移す
P：ON(x,y),CLEAR(x),VAC(Z);
D：VAC(Z);
A：AT(x,Z),CLR(y)
MV2(x,Y,z)：円板xを柱Yから外し，円板zの上に載せる
P：AT(x,Y),CLEAR(x),CLEAR(z);
D：AT(x,Y),CLEAR(z);
A：ON(x,z),VAC(Y)
MV3(x,Y,Z)：円板xを柱Yから外し，空いている柱Zに移す
P:AT(x,Y),VAC(Z),CLEAR(x);
D:AT(x,Y),VAC(Z);
A::VAC(Y),AT(y,Z)
MV4(x,y,z)：円板xを円板yの上から外し，円板zの上に載せる
P:ON(x,y),CLEAR(x),CLEAR(z);
D:ON(x,y),CLEAR(z);
A::ON(x,z),CLEAR(y)
動作オペレータ
MV1(x,y,Z)：
円板xを円板yの上から柱Zに移す
P： ON(x,y),
CLEAR(x), VAC(Z);
D： VAC(Z);
A： AT(x,Z),CLR(y)
MV2(x,Y,z)：
円板xを柱Yから外し，円板zの上に
載せる
P：AT(x,Y),CLEAR(x),
CLEAR(z);
D：AT(x,Y),CLEAR(z);
A：ON(x,z),VAC(Y)
MV3(x,Y,Z)：
円板xを柱Yから外し，空いている柱
Zに移す
P:AT(x,Y),VAC(Z),CLEAR(x);
D:AT(x,Y),VAC(Z);
A::VAC(Y),AT(y,Z)
MV4(x,y,z)：
円板xを円板yの上から外し，円板z
の上に載せる
P:ON(x,y),CLEAR(x),CLEAR(z);
D:ON(x,y),CLEAR(z);
A::ON(x,z),CLEAR(y）
初期状態→（オペレータ）→目標状態
初期状態 S：
ONTABLE(A)
ONTABLE(C)
ON(B,C)
B
A
C
目標状態 G:
ON(A,C)
A
C
B
一般的な問題解決法
• 目標状態の状態記述のうちで、初期状態によって達成されて
いない命題を探し
• それを一つ達成する
という操作を繰り返す。
命題Cを達成するには、
Cを追加リストとする動作関数（オペレータ：O）を求める。
そのオペレータ：Oの前提条件が初期条件によって満たされてい
るかを調べ、
満たされていればOを適用
満たされていなければそれを満たすのに必要な命題を達成する
こと新たな目標にする
Local planning
function LocalPlanning(S,G)
．LOOP1: if satisfy G exit (S);
2．Sによって満たされないGの命題をgoal-listに入
3．LOOP2: if empty(goal-list) return(fail);
4．C=first(goal-list); remove(C,goal-list);
Cを達成するオペレータを全て求めoplistに入
5．LOOP3：if empty (oplist) goto LOOP2
6．operator=first(oplist); remove(operator,oplist);
if not applicable(operator), goto LOOP3
7．Gからoperatorの追加リストを除き、前提条件を加えた状態
をG1とする
8．G2= LocalPlanning(S,G1)
9．if G2=fail, goto LOOP3
10. S=operator(S)
11. Goto LOOP1
1
各LOOPの役割
LOOP1：function local-planning(S,G)
LOOP2: goallist に含まれる「状態」を実現する
動作オペレータを捜し、oplistに入れる
LOOP3： oplistに含まれる動作オペレータが
適用できる前提条件が満たされているかをチ
ェック
必要なoperatorsを定義する
•
•
•
•
PUTON(x,y)：xをyの上に置く
TAKEOFF（x,y)：yの上にあるxを掴む
PUTDOWN(x):xをテーブルの上に置く
PICKUP(x)：テーブルの上にあるxを掴む
各operatorに対するP,D,Aで定義
• P: Prerequisite condition （前提条件）
そのoperatorを適用できる状態
• D: Delete condition （削除状態リスト）
そのoperatorを適用後に削除される状態
• A： Add condition （追加状態リスト）
そのoperatorを適用後に追加される状態
各動作関数（operator）のP,D,A
• PUTON(x,y)
：xをyの上に載せる動作
P： HOLD(x),CLEAR(y)
yの上が空きxを保持
D: HOLD(x),CLEAR(y)
A： ON(x,y),CLEAR(x),EMPTY
yの上にｘが載り,上は空、手は空
• TAKEOFF（x,y)
:yの上からxを除去する動作
P： ON(x,y),CLEAR(x),EMPTY
ｘがｙに載り,その上は空き,手は空
D: ON(x,y),CLEAR(x),EMPTY
A： HOLD(x),CLEAR(y)
ｘを持ち, ｙの上は空
各operatorの前提条件,削除/追加リスト
• PUTDOWN(x): ｘをテーブルに置く動作
P： HOLD(x)
D: HOLD(x)
A： ONTABLE(x),CLEAR(x),EMPTY
• PICKUP(x)：xをテーブルから持ち上げる動作
P： ONTABLE(x),CLEAR(x),EMPTY
D: ONTABLE(x),CLEAR(x),EMPTY
A： HOLD(x)
最初のタスク：
１．【LOOP1】 SはGを満たさないので次に行く
2.
*
SG
ON(A,C)をgoal-listに入れる
3. 【LOOP2】 goal-listはemptyでないので次に行く
4.T=ON(A,C) としてgoal-listから外す
Tを達成するオペレータを全て求め、oplistに入れる
>>PUTON(A,C)をoplistへ
5. 【LOOP3】 oplistはemptyではないので次に行く
6. operator= PUTON(A,C)、これを適用するにはHOLD(A),CLEAR(C)
が前提条件として必要だが、満たされないので5へ
5 ここでoplistが空ならLOOP３を抜けて3に戻る
3. ここでgoallistが空ならLOOP２を抜けて7に行く
7. GからPUTON(A,C）の追加リストを除き、前提条件HOLD(A);CLEAR(C)
を加えた状態をG1として、LocalPlanning(S,G1）を解く
次のタスク：
*
S G1
2． HOLD(A);CLEAR(C)をgoal-listへ
4. goal-listを達成するのに必要なオペレータをoplistへ；
これらはHOLD(A);CLEAR(C)を追加条件とするTAKEOFF(A,C)
またはPICKUP(A)である
（pickup（A)を選んだ場合）
6. operator= PICKUP(A); (oplistから外しておく);
これを適用するには ONTABLE(A)とCLEAR(A)が必要（CLEAR(C)
も必要）、満たされないので５へ
5. oplistはemptyなのでLOOP3を抜けて3に行く
3. goallistはemptyなのでLOOP２を抜けて7に行く
7. HOLD(A) はG1から除かれ、代わりにG1に
ONTABLE(A),CLEAR(A),EMPTYを入れて
LocalPlanning(S,G1)を解く
これを繰り返す
初期状態→（オペレータ）→目標状態
初期状態 S
目標状態 G
A
A
B
B
C
α
C
β
α
β
ONTABLE(C,α)を消してONTABLE(C,β)を作る
EMPTY^CLEAR(A)^ON(B,C) )^ON(A,B)
の４条件はSとGで共通に存在する
Local-planning(S,G)の動作
Local-planning(S,G)の手順：
SからGへは直接行けない
ON(A,C)を生成するoperatorとして
PUTON(A,C)が必要
（step1)
PUTON(A,C)の前提条件として
HOLD(A)&CLEAR（C)が必要
(step5,6,7)
これらをsubgoal=G1として
local-planning(S,G1)を使う
(step2,3,4)
(step8)
Local-planning(S,G1)の動作
Local-planning(S,G1)の手順：
SからG1へは直接行けない。
HOLD(A)の生成には
PICKUP(A)
または
TAKEOFF(A,x) 等のoperatorが必要
CLEAR(C)の生成には TAKEOFF(B,C)が必要
PICKUP(A)を動作させる前提条件として
ONTABLE(A)&CLEAR(A)&EMPTY
が必要
TAKEOFF(B,C)を動作させる前提条件として
ON(B,C）&EMPTY&CLEAR(B)が必要
これらは初期条件Sにより満たされているので実行可能
ONTABLE（C）は最初からあるので、そのままいじらない
ON(A,C)
S → ON(A,C) goallistに
PUTON(A,C)
HOLD(A)＆CLEAR（C）
PICKUP(A)
TAKEOFF(A,x)
S → HOLD(A)＆CLEAR（C）
CLEAR(A)
ONTABLE(A)
EMPTY
CLEAR（C)
PUTDOWN(y)：y=B
CLEAR(A)
ON (A,x)
EMPTY
CLEAR（C)
S → CLEAR(A)＆
ONTABLE(A)＆
EMPTY&CLEAR(C）
PUTON(y,z)
HOLD(B)
CLEAR(A)
ONTABLE(A)
CLEAR(C）
CLEAR(C）が実現されないので
HOLD(y)
CLEAR(A)
ONTABLE(A)
CLEAR（C)
CLEAR(A)
Cの上に載っている物を下ろす
TAKEOFF(B,C)
S → HOLD(B)＆CLEAR（A)
＆ONTABLE(A)＆CLEAR(C）
EMPTY, CLEAR(A), ONTABLE(A), ON(B,C)
S → EMPTY & CLEAR(A)
&ONTABLE(A)&ON(B,C)
演習：ハノイの塔
• 大きさが順に大きくなる３つの円盤、A,B,Cと３つの
柱1,2,3. 最初円盤は全て柱１の上に、一番小さい
Aを一番上に、Cを一番下にして積み重ねられてい
る。これを柱３にAが一番上になるように移す、但し
一度に１個だけ円盤を動かせる、どの円盤もそれよ
り小さい円盤の上に置けない
• 最初に出来るのはAを柱2か柱3に移すことだが、そ
のあとAの上にはBもCも置けないので、つまりはA
を移さなかった柱にBを移して置いて、その上にAを
移し、空いた柱3にCを移すことができれば成功であ
る．次にそのCの上にBを載せ、その上にAを載せる
SはGではない、ならサブタスクG1
•
•
•
•
•
•
•
•
•
LOOP1では
Sは ON（A,B) & ON(B,C） & ONPOLE1（C)
Gは ON（A,B) & ON(B,C） & ONPOLE2（C)
Sで満たされていないGの条件はONPOLE2（C)
ONPOLE2（C) をgoallistにいれる（LOOP2へ）
goallistの先頭要素を取出し（goallistから消す）
これを実現するオペレータをoplistに入れる(LOOP3へ)
これは適用可能か？できなければLOOP3へ
可能ならこのオペレータを適用、goallistからこのオペ
レータの追加リストを除き（用済み）PCを加えた状態を
G1とする（G1をgoalとした問題を解く）
８段階を右の３段階と見る
１.ABC
１. BC
１.
C
１. C
2. ＿
2. ＿
2. B
2. AB
3.＿
3. A
3. A
3.＿＿
高さ２の山を1.
から2. へ移す
高さ１を1.から3.へ
１.＿＿
１. A
１. A
１.＿＿
2. AB
2. B
2. ＿
2.＿＿
3. C
3. C
3. BC
3. ABC
高さ２の山を2.
から3. へ移す
目標：高さ３の山を柱１から柱３へ移す
原始問題：
高さ1の山を
小目標：高さ2の山を柱1 柱1から柱3
へ移動
から柱2へ避難させる
高さ1の
高さ1の山を柱3
高さ1 山を柱1 から柱2
の山をから柱2 へ移動
柱1かへ移動
ら柱3
へ移動
小目標：高さ2の山
を
柱2から柱3へ移す
高さ1の山を
高さ1の山柱2から柱3
を柱2からへ移動
柱1へ移動
高さ1の
山を柱1
から柱3
へ移動
人工知能は要素技術では足りない
• 問題を要素に分解して緻密な仕事を行う、と
いう状況よりは、人間の行うグローバルな意
思決定が実用上は重要
• 人が近づきにくい災害現場、宇宙空間等へ
行って救助活動を行うロボット：複雑なタスク
• ロボットは、①移動する（直進する、回転す
る）②荷物を運ぶ③障害物をどける（戸を開
ける）④通信する⑤サブ・タスクを変更する
等様々な意思決定と行動を組み合わせる
別の例：Logic theorist
• 数学者の代わりをする人工知能プログラム
• Russel-Whiteheadの「数学原理」：公理から
構成する数学→コンピュータ向き
• 公理（AXIOM)：証明無しで使える命題：仮定
や定義に近い（例えばユークリッドの公理）
• 命題(proposition)：statement、｛Yes,No｝の
値をとる変数
• 定理(theorem）：証明の必要な命題
Logic Theorist (Newell,Shaw,Simon)の例
• 公理をいくつか仮定して
例えばSからGを導く。
• SとGの距離を縮める為、公
理1を適用してSをS1
とする。これで最後の部分が
Gと同じ形になった
• S1とGの距離を縮めるには
（）の中の演算子を同じにし
たい。公理6を用いてS1をS2
にし、公理３でS3にする
• 更に（）の中身をGに近づけ
る為、公理1を用いてS4に変
換。これでGとの差が消失
1.
2.
3.
4.
5.
6.
A  B  B  A 積は可換
A ∨B → B∨A 和は可換
２重否定
A  A
A∧B  (A∨B)
A  B  (A  B)
A  B  (A  B)
S : R  (P  Q)
G : (Q  P)  R
S1: (P  Q)  R
S2 : (P  Q)  R
S3: (P  Q)  R
S4 : (Q  P)  R  G !!!
論理演算
• 最初の目標：公理を用いてS→Gを導出： S : R  (P  Q)
G : (Q  P)  R
• S→S1で大まかな形の差異を縮めた
• 次の目標：S１→Gを導出：
S1: (P  Q)  R
• Ｓ１ →S2ではＳ１に公理6を適用して
A  B  (A  B)
結合子の差異を縮める（→が和演算に）
• Ｓ2に公理3を適用して２重否定を消しＳ3を得る
S2 : (P  Q)  R
• 次の目標： S3→Gを導出：
• Ｓ3とＧの距離を縮めるため、Ｓ3に公理１を適用してＳ4を作る
• 次の目標：Ｓ4→Ｇを導出：
S3: (P  Q)  R
• Ｓ4とＧの間に差異無し（解決して問題終了） S4 : (Q  P)  R
ＧＰＳの問題
• Ｇｅｎｅｒａｌ Problem Solverという名前ほどに
は一般的な問題解決はできない
• 単純な問題しか解けない→改良の工夫
• いくつかの距離を重要性の程度の順に並べ
て重要なものから順に距離を減らす
• 前提条件の重要度を最初から決めておく

Download Report