人工知能2 2005Apr26,May10

人工知能
（Artificial Intelligence）
状態空間表現と探索
State Space Representation and Search
Lecture 2
田中美栄子
状態（state）と演算（operator）
プログラミング
作業の
自動化
人工知能
(AI)
変数・定数・演算を
決めてモデル化
問題設定を行うこと
• 解くべき問題の決定
↓
• 解ける形に変形・単純化・離散化、…
状態と演算（作用）
• 状態(state) → 次状態(next state)
↑
演算,作用(operator)
• 問題を状態遷移図（グラフ）化することで解く
Example１積み木
AとCの間にBを入れる
A
C
B
方法
• Aを左手で持ち上げ,その間に右手でBをCの上に
置き,その上にAを載せる
• しかし片手しか使えない,又は１台のクレー
ンで持ち上げる場合も存在する
拘束条件
• on(A,C)のA, on(B,table)のBは移動可
• on(A,C)のCの場合は移動不可
A
C
B
C
A
状態変化例
• on(A,C)→on(A,table)
• on(B,table) →on(B,A)
つまり・・・
B
B
A
C
状態空間を定義
• on(X,Y)=XはYのすぐ上に乗っていることを示す
Table
• 状態:初期状態
• {on(A,C),on(C,table),on(B,table)}
状態空間を定義
• on(X,Y)=XはYのすぐ上に乗っていることを示す
Table
• 状態:初期状態
on(A,C) & on(C,table) & on(B,table)
状態空間を操作
• 終了状態:{on(A,B),on(B,C),on(C,table)}
まで操作を行う.
Table
• 状態:1
• {on(A,table),on(C,table),on(B,table)}
状態空間を操作
• 終了状態:{on(A,B),on(B,C),on(C,table)}
まで操作を行う.
Table
• 状態:2
• {on(A,table),on(C,table),on(B,C)}
終了状態
• 終了状態:{on(A,B),on(B,C),on(C,table)}
なので操作終了.
Table
• 状態:終了状態
• {on(A,B), on(B,C), on(C,table)}
Example 2：ロボットの迷路抜け
（Robot maze）
• 入り口から出口への経路を見つける
（ロボットは地図を知らない）
ロボットの迷路抜け
制約条件
• 道の真ん中を歩く（両壁から均等の距離を保つ）
ロボットの迷路抜け
• 格子点上を一歩ずつ歩く：（1,1）から（4,4）へ
D
(4,4)
E
B
(1,4)
Goal
注）この場合
分岐点に座標を
書く場合もある.
F
A
(2,2)
H
C
(1,1)
Start
(3,1)
I
注）また，
分岐点に名前を
適時つける場合も．
ロボットの迷路抜け
• （1,1）から（4,4）へ
S(1,1)
(2,4)
(1,4)
(3,4)
G(4,4)
A(2,3)
(2,3)
(3,3)
B(2,4)
C(2,2)
E(3,4)
D(1,4)
(2,2)
(3,2)
G(4,4)
S(1,1)
(3,1)
H(3,2)
F(3,3)
I(3,1)
状態空間移動(オペレータ利用)
オペレータ
• 状態遷移＝状態空間の位置移動
（迷路問題と共通点）
• 「状態」「オペレータ」「拘束条件」の定義が必要
(与えられているとは限らない)
• 「前提条件」「適用後に削除される状態記述」
「適用後に追加される状態記述」を定義が必要
状態空間のグラフ表現
• グラフの構成
node（節）,edge（枝）
• 有向グラフと無向グラフ
• ｔree（木）
閉路(ループ)のないグラフ
状態空間のグラフ表現
• 始節点(start node)から目標節点(goal node)へ
グラフの探索
・ rootから始める,Bottom up＝前向き推論
・ goalから始めるtop down=後ろ向き推論
(※:各状態を重要と考えれば区別なし)
グラフ探索（基本的には前向き推論）
• 目標節点(goal):探査を終了する節点
• open list :今後調べる節点を記載しておく
（探査し終わった節点はopenから削除）
• 始節点がgoalならば終了、
そうでなければ探査開始
探索の基本アルゴリズム（木の場合）
•
•
•
•
•
•
•
•
Search algorithm{
１．初期節点をopenリストに入れる
2. if(open==empty)break;（探索失敗）
3. n=first(open);
4. iｆ(goal(n))print(n);break;（探索終了）
5. remove(n,open);
6. 次に調べる節点をopenに入れる
7. ２へもどる｝
Depth-1ST-search（木の場合）
Depth-first-search algorithm{
• １．初期節点をopenリストへ
• 2. if(open==empty)break;（探索失敗）
• 3. n=first(open);
• 4. iｆ(goal(n))print(n);break;（探索終了）
• 5. remove(n,open);
• 6. 次探査を行う節点をopenへ
(nを展開し,全子節点niをopenの先頭に入れる)
niからnへポインタを付けておく
• 7. ２へ
｝
例題：S→A→B→D→E→G
• S（1,1）からG（4,4）へ
S(1,1)
B(2,4)
D(1,4)
E(3,4)
G(4,4)
A(2,3)
A(2,3)
(3,3)
C(2,2)
B(2,4)
E(3,4)
D(1,4)
(2,2)
(3,2)
G(4,4)
(1,1)
(3,1)
H(3,2)
F(3,3)
I(3,1)
Depth-1ST深さ優先探索（graph）
Depth-first-search algorithm{
• １．初期節点をopenリストに入れる
• 2. if(open==empty)break;（探索失敗）
• 3. n=first(open);
• 4. iｆ(goal(n))print(n);break;（探索終了）
• 5. remove(n,open); add(n,closed);
• 6. 次探査を行う節点をopenへ
(nを展開し全子節点niをopenの先頭へ)
niからnへポインタを付けておく
• 7. ２へ
｝
Breadth-1ST幅優先探索（graph)
Breadth-first-search algorithm{
• １．初期節点をopenリストへ
• 2. if(open==empty)break;（探索失敗）
• 3. n=first(open);
• 4. iｆ(goal(n))print(n);break;（探索終了）
• 5. remove(n,open); add(n,closed);
• 6. 次探査を行う節点をopenへ
(nを展開し,全子節点niをopenの最後へ)
niからnへポインタを付けておく
• 7. ２へ
｝
Open list の変化
• 深さ優先の場合
S→A→BC→DEC→EC→GF
• （状態遷移はS→A→B→E→G）
• 幅優先の場合
S→A→BC→CDE→DEHI→EHI→HIGF→
IGF→GF
• （状態遷移はS→A→B→E→G）

Download Report