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