分散制約充足による分散協調問題解決の定式化とその解法
横尾 真, Edmund H. Durfee, 石田 亨, 桑原 和宏
電子情報通信学会論文誌,Vol. J75-D-I, No.8, pp. 704-713, 1992.


本論文では, 複数のエージェントの関連する制約充足問題である分散制約充足問題 を定式化する. 分散制約充足問題は非常に一般的な問題であり, 分散協調問題解決で 議論されてきた多くの問題を定式化することができる. 本論文ではさらに, 分散制約充足問題の各種の解法を示す. 特に、制約充足問題を解く代表的な手法であるバックトラッキング法は本質的に 逐次的なものであるが、 本論文では新たに開発された, 各エージェントが非同期、並行に動作することが可能な 非同期型バックトラッキング法を示す. 実験結果により, 分散制約充足問題を複数のエージェントで分散的に 解くことは, 各エージェントが解く問題の独立性が高い場合に 有効であることを示す.