制約処理に関する ミニサーベイ 栗　原　正　仁.

Presentation on theme: "制約処理に関する ミニサーベイ 栗　原　正　仁."— Presentation transcript:

1 制約処理に関する ミニサーベイ 栗　原　正　仁

2 Contents Hard constraints Soft constraints Applications
Phase transition Decision repair algorithm Random solution generation Partial order CSP Soft constraints Weighted CSP Fuzzy CSP Semiring-based Soft CSP Applications More on fuzzy CSP: Con’flex

3 物理学の相転移（例：温度領域による氷→水→水蒸気という急変）に類似
Phase transition 実行結果 計算時間 グラフ彩色問題（NP完全問題） アーク数／ノード数（制約密度） ■指数関数的な時間がかかる領域（worst case)は限られている． ■アルゴリズムの性能は問題パラメータの微少変化で急変する． 物理学の相転移（例：温度領域による氷→水→水蒸気という急変）に類似 Gomes, Hogg, Walsh, Zhang: Phase transitions and structure in combinatorial problems, AAAI-02 tutorial, 2002.

4 Decision repair algorithm
Systematic (tree) search Local (heuristic repair) search ■完全な割当てを逐次修復 ■近傍の「傾斜」の利用 ■完全性なし ■早期の決定の誤りに強い ■部分的な割当てを逐次拡張 ■フィルタリング（後戻り，先読み） ■完全性あり ■早期の決定の誤りに弱い 矛盾する 割当て 一連のdecisionにより 部分的な割当てを逐次拡張 Conflictを解消する 任意のdecisionを修復 Jussien, Lhomme: Local search with constraint propagation and conflict-based heuristics, Artificial Intelligence 139, 21-45, 2002. (an extended version of a prize-winning paper at AAAI-2000)

5 Random solution generation
問題　CSPの解を一様分布にしたがってランダムに生成したい （例） A,B,C,D: {0,1} A≦B A≦C A≦D A≦E 17通りの解を 確率1/17で発生 最初にA=0,1を確率0.5でランダムに決定するのは誤り 応用 ハードウェアのテストケースの自動生成 Dechter, Kask, Bin, Emek: Generating random solutions for constraint satisfaction problems, Proc. AAAI-02, 15-21, 2002.

6 Partial order CSP 与えられた制約を満たす半順序を求める x1 1 x2 1 x3 1 1
半順序は閉路のない有向グラフで表現される 1 x2 1 x3 1 1 半順序＝推移性＋非反射性 与えられた制約が単調性を満たすとき 推移性を不要とする条件を導出 小さなサイズのBDDと いうグラフ構造で解く 応用 ソフトウェアの正しさの自動検証 Kurihara, Kondo: BDD encoding for partial order constraints and its application to expert systems in software verification domains, Proc IEEE Int. Conf. on Systems, Man and Cybernetics, , 2000.

7 Weighted CSP 過制約(over-constrained)な問題（解がない） W-CSP: 満たされた制約の重みの和を最大化する
原問題 弱問題 多項式時間で解く 緩和 W-CSP 2次 0/1 計画問題 半正定値 計画問題 弱問題の 実数解 SemiDefinite Programming 変数＝0/1 目的関数=２次関数 乱数丸め法 W-CSP 近似解 原問題の 0/1解 近似度が理論的に 保証される Lau: A new approach for weighted constraint satisfaction, Constraints, 7, , 2002.

8 Fuzzy CSP 過制約(over-constrained)な問題（解がない）
FCSP: 制約の満足度を[0,1]の実数値で表現． 満足度の最小値(ファジィ論理積）を最大化する(MAX-MIN基準） 元になるCSPに応じた２つの手法がある 反復改善 系統的探索 Meseguer, Larrosa: Solving fuzzy constraint satisfaction problems, Proc. IEEE Int. Conf. on Fuzzy Systems, , 1997. Wong, Leung: Extending GENET to solve fuzzy constraint satisfaction problems, Proc. AAAI-98, , 1998.

9 Semiring-based soft CSP
SCSP W-CSP, FCSP などのソフトCSPを統合した抽象モデル 半環という抽象代数構造を利用 制約半環＝< A, ＋, ×, 0, 1 > A:　集合（少なくとも0,1を要素として持つ） ＋： 交換則，結合則をみたす演算 ×：　結合則，＋に対する分配則をみたす演算 ０：　＋の単位元で，かつ×の吸収元 １：　×の単位元 満足度の表現 最小0，最大1 満足度の大小を表現 a<b ⇔a+b=b 論理ANDの抽象化 種々のソフト制約充足問題に適用できる探索手法を 同時に統一的に論じることができる Bistarelli, Codognet, Rossi: Abstracting soft constraints: framework, properties, examples, Artificial Intelligence 139, , 2002.

10 Applications (1) RCPSP/max と呼ばれる非常に現実性の高いスケジューリング問題を解くCSP解法アルゴリズムを開発した．その手法は最小競合集合を大域的に解析することによる競合解消を，反復サンプリングによる最適化アルゴリズムに組み込んだものである． RCPSP/max (resource constrained project scheduling problem with time windows) V: 仕事の集合．所要時間は固定．開始時刻が変数． E: ２つの仕事間i,jの時間制約の集合．一方の仕事の終了時刻と 　　他方の仕事の開始時刻は決められた時間内になくてはならない． R: 再生可能な資源の集合．資源毎に総量が決められる． 　　各仕事毎に必要な資源の種類と量が決められている． 問題　制約をすべて満たすように，かつ最小の時間ですべての仕事が 　　　　終了するように，各仕事の開始時刻を定めよ． Cesta, Oddi, Smith: An iterative sampling procedure for resource constrained project scheduling with time window, Proc. IJCAI-99, , 1999.

11 Applications　(2) ネットワークのセキュリティ・プロトコルの１つとして知られる Needham-Schroeder プロトコルの安全性はSCSP(ソフト制約充足問題）として定式化できる． SCSPの解の満足度がある値以下になると，そのネットワークはアタックされる危機にある． Bella, Bistarelli: SCSPs for modelling attacks to security protocols, Proc. CP2000, Workshop on Soft Constraints, 1-16, 2000.

12 Applications (3) ソフト制約充足問題の対話的ソルバーは，ユーザと対話しながらユーザの大域的な選好から局所的な制約を学習し，適切な満足度ユーザモデルを自動構築する． このようにユーザと学習モジュールを組み込んだソフト制約ソルバー間の対話を通して，モデリングとその解決が交互に入り組むことになり，ユーザの最も満足のいく解を効率よく提示できる現実的な問題解決に役立つシステムが構築できる． Rossi: Aquiring both global and local preferences in interactive constraint solving via machine learning techniques, Computer Science Seminar, University College Cork, 2002.

13 More on fuzzy CSP: Con’flex
変数には離散型や実数型がある． 区間算術により，変数ラベルの実数区間を縮小したり分割する． 満足度は離散化して通常のCSPに帰着？ 仏語のホームページでドキュメントとソフトを配布（それ以外の情報はない？）

14 Interval arithmetic