Presentation is loading. Please wait.

Presentation is loading. Please wait.

人工知能 ( Artificial Intelligence ) 状態空間表現と探索 State Space Representation and Search Lecture 2 田中美栄子.

Similar presentations


Presentation on theme: "人工知能 ( Artificial Intelligence ) 状態空間表現と探索 State Space Representation and Search Lecture 2 田中美栄子."— Presentation transcript:

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)


Download ppt "人工知能 ( Artificial Intelligence ) 状態空間表現と探索 State Space Representation and Search Lecture 2 田中美栄子."

Similar presentations


Ads by Google