分散制約充足問題に関する研究
博士 (工学), 東京大学大学院 工学系研究科 電子情報専攻, 1995年6月15日


分散協調問題解決とは人工知能の研究の一分野であり, 複数の人工的な知的エー ジェントの協調的な問題解決を対象とする. 本論文では,分散協調問題解決の 様々な応用問題を定式化する一般的な枠組である分散制約充足問題に関して, 筆者がこれまでに行ってきた研究について述べる.

第1章ではまず研究の目的を明確化する. 従来の分散協調問題解決の研究では, 典型的な応用問題を対象として, 問題を解くために必要とされるエージェント およびエージェント間の相互作用のモデル化を行う実験的なアプローチが中心 であり, 対象となる問題自体の定式化に関しては十分な考察がなされていなかっ た. 様々な応用問題を表現可能な一般的な枠組を与えることは, 領域に依存す る異なる仮定のもとに研究されてきた種々のアプローチを比較するため, また, ある領域で得られた結果を, 異なる領域の問題で再現するために重要であ る. 本研究の目的は, 制約充足問題を分散環境に拡張することにより, 分散協 調問題解決で議論されてきた様々な問題を定式化する枠組を与え, これらの問 題を解く一般的な解法を提供することである.

第2章では, 分散制約充足問題の基礎となる制約充足問題に関して, 問題の定 義と, 従来提案されてきた制約充足問題の解法について概観する. さらに, 制 約充足問題の基本的な解法であるバックトラック型の探索アルゴリズムを改良 し高速化した, 弱コミットメント探索アルゴリズムを示す.

第3章では, 分散制約充足問題の定義を示し, この分散制約充足問題によって, 分散資源割当問題, 分散解釈問題, 分散知識ベースの整合性管理等の様々な分 散協調問題解決の応用問題が定式化されることを示す.

第4章, 第5章では分散制約充足問題の解法を示す. 第4章では解を求めるた めの分散探索アルゴリズムを示す. 通信/制御のボトルネックの回避, 処理の 並列性の追求, セキュリティ, プライバシーの保持のためには, 探索において, 情報を一つのエージェントに集中せず, 各エージェントが全体的な制御なしに, 非同期, 並行的に動作できることが望ましい. しかしながら, 全体的な制御な しでは一般にアルゴリズムの完全性を保証することが困難となる. 本論文では, 各エージェントが全体的な制御なしに, 非同期, 並行的に動作しながらも, ア ルゴリズムの完全性が保証されることを特徴とする非同期バックトラッキング アルゴリズムを示す. また, 非同期バックトラッキングアルゴリズムをベース として, 変数の優先順位を動的に変更することにより, 第2章で示した弱コミッ トメント探索アルゴリズムと同様な性質を持つ非同期弱コミットメント探索ア ルゴリズムが実現されることを示す.

第5章では探索の効率を高めるための前処理である分散consistencyアルゴリ ズムを示す. 分散consistencyアルゴリズムにおいては, エージェントはあら かじめ変数の領域に関する情報を交換し合い, 他の変数との制約により解にな り得ない値を取り除くことにより, 無駄な探索を減少させる. 仮説を用いた真 偽値管理システム(Assumption-based Truth Maintenance System, ATMS)を分 散化した分散ATMSを用いることにより, 分散consistencyアルゴリズムの実装 が可能であることを示す.

現実の問題を分散制約充足問題として定式化した場合, 与えられた制約が強過 ぎて解が存在しない場合が多く存在する. 第6章では, そのような場合に解の 定義を拡張し, 部分的に制約を満たす不完全な解を求めることについて議論す る. 具体的には, 制約の重要度という概念を導入することにより, 部分的に制 約を満たす解の評価基準を定式化する. また, 非同期バックトラッキングアル ゴリズムを繰り返し適用することにより, 制約の重要度により定義された評価 基準において最適な解を求める非同期段階緩和アルゴリズムを示す.

第7章では, 結論として以上についての成果のまとめを行う.