人工知能 (Artificial Intelligence) 状態空間表現と探索 State Space Representation and Search Lecture 2 田中美栄子 状態(state)と演算(operator) プログラミング 作業の 自動化 人工知能 (AI) 変数・定数・演算を 決めてモデル化 問題設定を行うこと • 解くべき問題の決定 ↓ • 解ける形に変形・単純化・離散化、… 状態と演算(作用) • 状態(state) → 次状態(next state) ↑ 演算,作用(operator) • 問題を状態遷移図(グラフ)化することで解く Example1 積み木 AとCの間にBを入れる A C B 方法 • Aを左手で持ち上げ,その間に右手でBをCの上に 置き,その上にAを載せる • しかし片手しか使えない,又は1台のクレー ンで持ち上げる場合も存在する 拘束条件 • 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)}と表現 Definition of States (状態の定義) on(X,Y) = X is on Y XがYのすぐ上に乗っている状態(定義) Table Initial State = on(A,C) & on(C,table) & on(B,table) Initial State →Next State(状態変化) Continue until FinalState:{on(A,B),on(B,C),on(C,table)} Table • State1 ={on(A,table),on(C,table),on(B,table)} Initial State →Next State(状態変化) Continue until FinalState:{on(A,B),on(B,C),on(C,table)} Table • State2 ={on(A,table),on(C,table),on(B,C)} Final State(終了状態) • Final State:{on(A,B),on(B,C),on(C,table)} → END. Table • State: Final State(終了状態) • {on(A,B), on(B,C), on(C,table)} Example 2:ロボットの迷路抜け (Robot maze) • Find Path :入口→出口へ (Robot does not have MAP) Robot maze(ロボットの迷路抜け) Constraint(制約条件):壁にぶつからない • Center of the Road(両壁から均等の距離) 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 注)また, 分岐点に名前を 適時つける場合も. Robot Maze • (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) 状態空間の移動(オペレータ利用) オペレータ(operator) • 状態遷移(Change of State) =状態空間の位置移動(Move in a State Space) (迷路問題と共通点) • 「状態」「オペレータ」「拘束条件」の定義が必要 (与えられているとは限らない) • 「前提条件」「適用後に削除される状態記述」 「適用後に追加される状態記述」を定義が必要 状態空間のグラフ表現 (Graphical Representation of the State Space) • Graph(グラフ)の構成 node(節),edge(枝) Directed graph vs. Undirected graph • 有向グラフと無向グラフ • tree(木) = graph without a loop 閉路(ループ)のないグラフ 状態空間のグラフ表現 (Graphical Representation of the State Space) • 始節点(start node)から目標節点(goal node)へ グラフの探索(graph Search) ・Forward:root→goal, Bottom up=前向き ・ Backward:goal→root, top down=後ろ向き (※:各状態を重要と考えれば区別なし) (graph Search)グラフ探索 • 目標節点(goal):探査を終了する節点 • open list :今後調べる節点を記載しておく (探査し終わった節点はopenから削除) • If(start=goal) go to END、 else start SEARCH Basic Search Algorithm(Tree) • • • • • • • • Search algorithm{ 1.Start node を openリスト に入れる 2. if(open==empty)break;(fail) 3. n=first(open); 4. if(goal(n))print(n);break;(end) 5. remove(n,open); 6. 次に調べるnodeをopen list に入れる 7. back to step2} Depth-1ST-search(木Treeの場合) Depth-first-search algorithm{ • 1.初期節点start node を openlist へ入れる • 2. if(open==empty)break;(探索失敗fail) • 3. n=first(open); • 4. if(goal(n))print(n);break;(探索終了end) • 5. remove(n,open); • 6. 次探査を行う節点nodeをopenlist へ入れる (nを展開し,全子節点niをopenの先頭に入れる) niからnへポインタを付けておく • 7. 2へ } Example: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{ • 1.初期節点をopenリストに入れる • 2. if(open==empty)break;(探索失敗) • 3. n=first(open); • 4. if(goal(n))print(n);break;(探索終了) • 5. remove(n,open); add(n,closed); • 6. 次探査を行う節点をopenへ (nを展開し全子節点niをopenの先頭へ) niからnへポインタを付けておく • 7. 2へ } Breadth-1ST幅優先探索(graph) Breadth-first-search algorithm{ • 1.初期節点をopenリストへ • 2. if(open==empty)break;(探索失敗) • 3. n=first(open); • 4. if(goal(n))print(n);break;(探索終了) • 5. remove(n,open); add(n,closed); • 6. 次探査を行う節点をopenへ (nを展開し,全子節点niをopenの最後へ) niからnへポインタを付けておく • 7. 2へ } 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)
© Copyright 2025 ExpyDoc