分散制約最適化問題における代表的なアルゴリズムであるADOPTとその後継のアルゴリズムについて、それらが持つとされていた停止性と最適性という重要な性質に、反例が存在することを発見しました。また、その原因となる箇所を修正し、これら2つの性質を保証した修正版ADOPTを提案しました。
分散制約最適化問題 (Distributed Constraint Optimization Problem: DCOP) は、複数のエージェント（行動主体）が協調するマルチエージェントシステムをモデル化するフレームワークの一つです。これを解く代表的なアルゴリズムにADOPT (Asynchronous Distributed OPTimization) があります。ADOPTは、アルゴリズムが有限時間で停止する「停止性」と停止時に必ず最適解が得られる「最適性」という２つの重要な性質を持つとされ、ADOPTに基づく後継のアルゴリズムにおいても、同様の性質が成り立つと考えられていました。
本研究では、ADOPTとそれに基づくアルゴリズムの停止性と最適性に対する反例を示しました。これは、ADOPTや後継のアルゴリズムに対して与えられた証明に誤りがあり、実際にはアルゴリズムが停止しない、または、停止時に最適解が得られない可能性が存在することを意味しています。また、ADOPTにおいて反例が存在する原因を特定し、それを修正したアルゴリズム（修正版ADOPT）を提案しました。さらに、修正版ADOPTにおける停止性と最適性を証明しました。
修正版ADOPTを用いることで、ADOPTや後継のアルゴリズムで発生する可能性があった不具合が防止され、これらを応用したシステムの信頼性の向上が期待されます。
PDF資料
プレスリリース
研究代表者
筑波大学システム情報系
長谷部 浩二 准教授
野城 滉司 （理工情報生命学術院システム情報工学研究群博士前期課程１年）
掲載論文
【題名】 Counterexamples and amendments to the termination and optimality of ADOPT-based algorithms
（ADOPTに基づくアルゴリズムの停止性と最適性に対する反例と修正） 【掲載誌】 Artificial Intelligence 【DOI】 10.1016/j.artint.2024.104083