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

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

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

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

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

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

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

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

　本論文は「分散制約充足問題に関する研究」と題し,複数の自律的に動作する知的プログラム(エージェント)が,それぞれの持つ変数に対してエージェント間の制約を満足する値を割り当てる分散制約充足問題に関する研究について記している.

　分散協調問題解決とは人工知能の研究の一分野であり,複数のエージェントの協調的な問題解決を対象とする.従来の分散協調問題解決の研究では,典型的な応用問題を対象として,問題を解くために必要とされるエージェントおよびエージェント間の相互作用のモデル化を行う実験的なアプローチが中心であり,対象となる問題自体の定式化に関しては十分な考察がなされておらず,得られた結果の一般性に乏しいという問題点があった.本論文は人工知能における重要な問題である制約充足問題を分散環境に拡張することにより,分散協調問題解決で議論されてきた様々な問題を定式化する枠組を与え,さらに,これらの問題を解く一般的な解決を示したものである.

　第1章「序論」では,従来の分散協調問題解決の研究を概観し,本研究の位置付けを明らかにし,論文の構成について記している.

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

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

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

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

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

　第7章は「結論」であり,本論文の成果をまとめている.

　以上,これを要するに,本論文では分散協調問題解決における基本的な問題として認められる分散制約充足問題の定式化を示し,分散制約充足問題を解く各種のアルゴリズムを創案し,比較実験等を通じてその有効性を示したものであり,電子情報工学上貢献するところが少なくない.よって,本論文は博士(工学)の学位請求論文として合格と認められる.