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

状態（ state ）と演算 （ operator ） 人工知能（ AI) コンピュータで作業の自動化 プログラムを用いて作成 変数や定数, 演算を決めてモデル化

状態（ state ）と演算 （ operator ） 人工知能 (AI) 作業の 自動化 プログラミン グ 変数・定数・演 算を決めてモデ ル化

問題設定を行うこと 解くべき問題の決定 ↓ 解ける形に変形・単純化・離散化 、 …

状態と演算（作用） 状態 (state) → 次状態 (next state) ↑ 演算, 作用 (operator) 問題を状態遷移図（グラフ）化することで 解く

Example １ 積み木 A と C の間に B を入れ る A C B 方法 A を左手で持ち上げ, その間に右手で B を C の上 に置き, その上に A を載せる しかし 片手 しか使えない, 又は １台のク レーン で持ち上げる場合も存在する

例１ 積み木 A と C の間に B を入れる A を左手で持ち上げ, その間に右手で B を C の上に 置き, その上に A を載せる 片手 しか使えない, 又は１台のクレーンで持ち 上げる場合も存在する C B A A C B 方法

拘束条件 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 の場合は移動不可

拘束条件 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) つまり・・・

状態空間を定義 on(X,Y)=X は Y のすぐ上に乗っていることを 示す 状態 : 初期状態 {on(A,C),on(C,table),on(B,table)} Table

状態空間を定義 on(X,Y)=X は Y のすぐ上に乗っていることを 示す 状態 : 初期状態 on(A,C) & on(C,table) & on(B,table) Table

状態空間を操作 終了状態 :{on(A,B),on(B,C),on(C,table)} まで操作を行う. 状態 :1 {on(A,table),on(C,table),on(B,table)} Table

状態空間を操作 終了状態 :{on(A,B),on(B,C),on(C,table)} まで操作を行う. 状態 :2 {on(A,table),on(C,table),on(B,C)} Table

終了状態 終了状態 :{on(A,B),on(B,C),on(C,table)} なので操作終了. 状態 : 終了状態 {on(A,B), on(B,C), on(C,table)} Table

Example 2 ：ロボットの迷路抜 け（ Robot maze ） 入り口から出口への経路を見つける （ロボットは地図を知らない）

ロボットの迷路抜け 制約条件 道の真ん中を歩く（両壁から均等の距離を保 つ）

ロボットの迷路抜け 格子点上を一歩ずつ歩く：（ 1,1 ）から （ 4,4 ）へ (4,4) (1,1) (3,1) (1,4) (2,2) 注）この場合 分岐点に座標を 書く場合もある. A B C I D F H E Goal 注）また， 分岐点に名前を 適時つける場合も． Start

ロボットの迷路抜け （ 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)

状態空間移動 ( オペレータ利用 ) オペレータ 状態遷移＝状態空間の位置移動 （迷路問題と共通点） 「状態」「オペレータ」「拘束条件」の定 義が必要 ( 与えられているとは限らな い ) 「前提条件」「適用後に削除される状態記 述」「適用後に追加される状態記述」を定 義が必要

状態空間のグラフ表現 グラフの構成 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-1 ST -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 を展開し, 全子節点 n i を open の先頭に入れる ) n i から n へポインタを付けておく 7. ２へ ｝

例題： 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)

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)

Depth-1 ST 深さ優先探索（ 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 を展開し全子節点 n i を open の先頭へ ) n i から n へポインタを付けておく 7. ２へ ｝

Breadth-1 ST 幅優先探索（ 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 を展開し, 全子節点 n i を open の最後へ ) n i から 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 ） 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)