ATMSを用いた分散制約充足問題の解法
横尾 真, 石田 亨
情報処理学会論文誌, Vol. 31, No. 1, pp. 106-114, 1990.


本論文では, 複数のエージェントによる協調的な問題解決である分散協調問題 解決の新しいモデルを提案する. このモデルでは, 問題解決を行うエージェン トが仮説に基づく推論を行い, 推論結果をAssumption-based Truth Maintenance System (ATMS)を用いて管理する. エージェント間では, 仮説に 基づく推論結果および同時に成立しえない 仮説の組合せに関する情報 (nogood)が通信される. 本論文では, このモデルが複数のエージェントの関連 する制約充足問題(分散制約充足問題)を解くために有効であることを示す. 分散制約充足問題の一例である, 通信ネットワークにおける通信路のプランニ ング問題に対するこのモデルの適用について述べる. 分散制約充足問題の解法 として, 全体の解を取りまとめるエージェントが存在する階層的な解法と, 取りまとめのエージェントが存在しない非階層的な解法の2種類を想定する. それぞれの解法について, ATMSの適用方法を示す. また, ATMSの適用により, 階層的な解法では部分解の間の制約条件を求める処 理が不要になること, 非階層的な解法では不適切な資源の割当が回避されるこ とにより, 効率的に分散制約充足問題を解くことが可能になることを示す.