制約充足と反復改良 (Constraint Satisfaction and Iterative Improvement) 人工知能の探索アルゴリズム（５） 先を読んで知的な行動を選択するエージェント 制約充足と反復改良 (Constraint Satisfaction and Iterative Improvement) 　制約充足 　後戻り法 　前向きチェック 　制約伝播 　反復改良 　山登り法 　焼きなまし法 　制約違反最小化 配布資料 pp.81-83, 110-113 別紙資料 pp.41-51 http://aibm4.main.eng.hokudai.ac.jp

制約充足(Constraint Satisfaction)

制約充足問題 (CSP: Constraint Satisfaction Problem) 状態：変数 x1,x2,…,xnの値で定義 ゴール検査：制約をすべて満たすかどうか 探索問題 制約充足問題

隣り合う地域の色が異なるように３色で塗り分けよ 制約充足の例：地図の塗り分け 　隣り合う地域の色が異なるように３色で塗り分けよ　 各地域が変数 変数の取りうる値が 領域 ◆　◆　◆ 隣り合う変数の値が異なるというのが 制約 すべての制約を満たす色の配置が解

Cxy ={(a,b),(c,d),…} 許される値の組 制約充足問題 x1 x2 … xn 問題 変数(variable)の集合　 各変数の領域(domain) 変数間の制約(constraint)の集合 D1 D2 … Dn Cxy ={(a,b),(c,d),…} 許される値の組 解 すべての制約を満たすような変数への値の割当て a1 a2 … an

制約充足問題の難易度 難易度＝NP完全 (NP-complete) ヒューリスティックで 平均的には実用的な時間で解く 解が与えられれば，それが確かに解であるかどうかは線形オーダーの時間で容易に判定できる． しかし，解を自力で見つけるのは，最悪のケースで指数オーダーとなり，非常に難しい． ヒューリスティックで 平均的には実用的な時間で解く

制約充足問題のその他の例 おもちゃの問題(toy problem) 現実世界の問題(real-world problem) ８クイーン問題 覆面算 クロスワードパズル 現実世界の問題(real-world problem) 線画解釈 VLSIレイアウト スケジューリング

８クイーン問題 x1=6 x2=8 x3=1 x4=4 x5=2 x6=5 x7=7 x8=3 制約 Q アタック！ x6=5 x7=7 x8=3

覆面算 解 FORTY ＋ TEN ＋ TEN ------------ SIXTY 29786 ＋　850 ＋　850 ------------ 31486

クロスワードパズル x1 x2 x1,x2間の制約： x1の３文字目＝x2の１文字目 1 2 3 4 5 6 7 8 単語ﾘｽﾄ AFT ALE EEL HEEL HIKE HOSES KEEL KNOT LASER LEE LINE SAILS SHEET STEER TIE x2 x1,x2間の制約：　x1の３文字目＝x2の１文字目

線画解釈（１） 解釈 線画 （２Ｄ） 立体 （３Ｄ）

線画解釈（２） 線分のラベル付けによる空間表現 両側に物体の表面が見える． 前方に凸． 両側に物体の表面が見える． 前方に凹． 矢線の右側だけに物体の表面が見える．

線画解釈（３） ジャンクションに許される全パターン

線画解釈（４） 制約充足による解釈の生成 変数：　辺 領域：　ラベル 制約：　ジャンクション 　　　　　のパターン 制約充足 解：　解釈

二項制約と他項制約 許される値の組 二項制約 x y z 三項制約 x y

理論的には二項制約のみ考える z a b c x y z y x p 三項制約 新しい変数の領域 二項制約に変換できる 二項制約 二項制約 新しい 変数

制約ネットワーク w z v x y u 頂点＝変数 辺　 ＝二項制約のある２つの変数を結ぶ

後戻り探索(backtracking search) バックトラック法＝深さ優先探索＋早めの後戻り a1 x1 a2 x2 a3 x3 a4 x4 部分解 k=5 a1 x1 a2 x2 a3 x3 a4 x4 k=5 前進 後退 x1 x2 x3 x4 x5 a1 x1 a2 x2 a3 x3 a’4 x4 k=4 a1 a2 a3 a4 a5 ＯＫ！ k=6 これまでの部分解との間に 制約違反がないように部分解を拡張 拡張できないときは， 後戻りをして最近の選択をやりなおす

バックトラック法のアルゴリズム ak = Skの要素を１つ選択 Sk = Sk －｛ak｝ S１ = D１ k = 1 現在x1の取れる値の集合 /* 前進 */ ak = Skの要素を１つ選択 S１ = D１ x1の領域 Sk = Sk －｛ak｝ k = 1 もし( a1 a2 …ak )が解なら それを記録 while (Sk≠φ) while (k > 0) k = k + 1 Sk＝ ( a1 a2 …ak-1 )との 　　　制約に違反しない 　　　ak ∈ Dkの集合 ただし， k=n+1のときは空集合 /* 後退 */ k = k －1

バックトラック法（再帰版） /* メイン */ BACKTRACK(空ベクトル, 1); /* 再帰的定義 */ BACKTRACK( vector, k ) { 　　if (vector が解) {解を記録する｝ local変数 Sk＝ vector に矛盾しない値∈ Dkの集合 　　　　　　　　　　　（ただし，k=n+1のときは空集合） 　　for ( a ∈Sk ) { 　　　　vector[k] = a; 　　　　BACKTRACK( vector, k+1 ); 　　} }

例：４クイーンをバックトラックで解く Ｑ Ｑ １ ２ ３ ４ Ｑ Ｑ 空 ３ ４ Ｑ Ｑ 空 １ ２ 解 Ｑ 空 ３

x1,x2の値を決めた時点で解に到達不能であるのに， x3,x4,x5,x6,x7のすべての組合わせに対して x8の値を見つけようとする 前向きチェックの動機 x1 1 2 3 4 5 6 7 8 AFT ALE EEL HEEL HIKE HOSES KEEL KNOT LASER LEE LINE SAILS SHEET STEER TIE H O S E S x2 H E x8に入る 単語が ない！ E T x1,x2の値を決めた時点で解に到達不能であるのに， x3,x4,x5,x6,x7のすべての組合わせに対して x8の値を見つけようとする

前向きチェック(forward checking) 前向きチェック＝先読み＋バックトラック a1 x1 a2 x2 a3 x3 a4 x4 部分解 いずれかの領域が空になったら 後戻り 部分解を拡張 前進 a1 x1 a2 x2 a3 x3 a4 x4 a5 x5 x6 x7 xn すでにＯＫ！ これ以降の変数の領域から a5と矛盾するすべての値を削除 アルゴリズムは省略

前向きチェックでうまくいく x1 x2 x8に入る 単語が ない！ 1 2 3 4 5 6 7 8 H O S E S H E E T AFT ALE EEL HEEL HIKE HOSES KEEL KNOT LASER LEE LINE SAILS SHEET STEER TIE H O S E S x2 H E x8に入る 単語が ない！ E T

アーク無矛盾性：サポーター 許される 値の組 x y 制約 サポーター y にサポーターがいない y にサポーターがいる

アーク無矛盾性(arc consistency) すべての変数のすべての値が， 制約のあるすべての変数にサポーターをもつ y x w z

制約伝播(constraint propagation) 一つの値の選択（削除）が制約によって次々と他の選択に波及する y 選択 x 領域が空 削除 アルゴリズムは省略 w z

反復改良(Iterative Improvement)

すべての変数に （ランダムに） 初期値を設定 反復改良の考え方 Q Q すべての変数に （ランダムに） 初期値を設定 改良をくりかえす （後戻りはしない） Q

評価関数 z=f(x,y) の山を登る 最適解 局所最適解 z y x

山登り法(Hill-Climbing) 近傍の状態のうち評価値が最大の状態に進む． 決して下り坂を降りない． 近傍 neighborhood

山登り法の欠点 高原 局所的最大 局所最適解で停止する． 高原では進むべき方向を判断できない．

焼きなまし法(Simulated Annealing) 近傍の状態から次の状態をランダムに選ぶ． エネルギが減少するなら，必ずそこに進む． エネルギが増加するなら，温度に応じた確率でそこに進む． 最小化すべき関数をエネルギと呼ぶ 局所解を ある確率で 脱出できる エネルギ 局所最適解 最適解

熱的なノイズによるランダムな揺れ 確率＝ 温度 ΔE 確率 大 エネルギ 増加分ΔE 小 温度 T 大 エネルギ 確率＝１ 温度はじょじょに 下げていく

冷却スケジュール T = schedule (k), k=1,2,… 線形冷却 指数冷却 T 対数冷却 k

焼きなまし法の最適性 温度T を十分ゆっくり下げるならば， 確率１で大域的最適解を見つける． 対数冷却 Tk=c/log(k+1) はこの条件を満たすが，収束時間はO(n!)より長い． 温度はすごくゆっくり 下げていく

反復改良による制約充足： ヒューリスティック修復(heuristic repair) y x 許される値の組 現在の状態 w z

制約違反最小化(min-conflict) 制約違反＝２ 制約違反＝１ 制約違反＝２ これを 選ぶ

制約違反最小化の実績 百万クイーン問題：　平均５０ｽﾃｯﾌﾟ ハッブル天体望遠鏡の観察スケジュール ３週間から１０分に短縮

まとめ 制約充足と反復改良 　制約充足 　後戻り法 　前向きチェック 　制約伝播 　反復改良 　山登り法 　焼きなまし法 　制約違反最小化