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