分散制約充足による分散協調問題解決の定式化とその解法

横尾 真  エドモンド H.ダーフィ  石田 亨  桑原 和宏  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.8   pp.704-713
発行日: 1992/08/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 特集論文 (並列/分散処理論文特集)
専門分野: AI/分散協調
キーワード: 
分散協調問題解決,  制約充足,  バックトラッキング,  

本文: PDF(742.6KB)
>>論文を購入


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