分散制約充足問題(DisCSP),分散制約最適化問題(DCOP)は分散人工知能の基本的枠組みの1つとして,近年注目を集めている.複数のロボットの制御,センサーネットワークや交通システム制御などのアプリケーション分野の発達に伴い,自律分散協調あるいは分散人工知能の基本方式研究への期待も高まっているのである.

分散制約充足・最適化問題のための解法として,各種の完全アルゴリズム,近似アルゴリズムが提案されてきた.完全アルゴリズムとは最適解を求めることが理論的に保証されているアルゴリズムのことである.しかし分散制約充足・最適化問題における完全アルゴリズムは実行時間や通信コスト,必要メモリ量などに課題を持つことが多く,実世界の大規模な問題を解くためには必ずしも常に最良の方法とは限らない.アルゴリズムの実世界への応用を考えた場合,分散アルゴリズムとしての複雑度(コスト)が小さく,高い品質の解を導出可能で,頑健性,ボトルネック,プライバシー,動的な状況への対応などの要件も考慮しなければいけない

本研究では,分散制約充足・最適化問題とその解法について,現実世界の問題への適用を念頭にした汎用ソルバ開発を将来の目標とする.そのためにまず,分散制約充足・最適化問題解法の種類を増やすことを本研究の第1の目的とする.既存研究の完全アルゴリズムだけでは対応が難しい場合,あるいは既存研究の深さ優先探索木(Depth First Search 木: DFS 木)を前提としたアルゴリズムでは対応が難しい場合にも対応できるものとする.このため,先に挙げた各種要件をも考慮し,高速で高品質な解を得る近似アルゴリズムの開発を目指す.

本論文では2章で分散制約充足問題,分散制約最適化問題の定義を述べるとともに,分散制約充足・最適化問題解法の既存研究について概観し,その応用について述べる.さらに分散制約充足・最適化問題の解法に要求される項目について検討するとともに,本研究におけるアルゴリズム設計指針を立てる.

分散制約充足・最適化問題を分散アルゴリズムで解く時の課題の1つは,局所最適から抜け出すことであるが,分散環境における探索では局所最適であるかどうかの判断が難しい.この課題を解決するために,3章では分散制約充足問題において,緩い組織化により局所最適を避けることを特徴とするMulti-agent Tabu Search手法を提案する.提案する手法ではそれぞれのエージェントが同じ値を一定時間選択するのを禁止し,選択する値が無くなった場合は周囲のエージェントが協力するというルールにより,局所最適を避ける.提案手法による具体的アルゴリズムとして3章では,DSTSとDHTSの2つを提案し,実験による評価を通して効果を検証した.その結果,Multi-agent Tabu Search手法により局所最適を避けることで,提案した2つのアルゴリズムDSTS, DHTSは既存のアルゴリズムよりも短時間のうちに高い成功率で充足解を計算できることが確認できた.

分散制約最適化問題を解くためには,局所最適からの脱出と同時に,何らかの解に到達したところで停止する必要がある.この課題を解決するために,4章では分散制約最適化問題のための高速近似アルゴリズムとしてDiSTaS-Anneを提案する.DiSTaS-AnneはDSTSにSimulated Annealingの要素を加えることで,最適解に近い解へ到達して停止することを目指す.評価実験を行うことで,DiSTaS-Anneが高品質な解を高速に求めることが確認できた.また,DiSTaS-Anneは非常に大規模な問題でも高いパフォーマンスが得られることも確認できた.

5章では,分散制約充足・最適化問題のための分散近似アルゴリズムの効率を改善するために,分散アルゴリズムの多重化手法を提案する.分散アルゴリズムの計算時間の多くはメッセージ通信に費やされる,よって個々のノードの計算量やメッセージ長の多少の増加はアルゴリズム全体の効率に直接大きな影響を及ぼさないという前提のもとでは,分散近似アルゴリズムを多重実行することで効率を上げることが可能である.5章ではその効果について理論的解析を行うとともに,シンプルなアルゴリズムの多重化実験により検証を行った.その結果,計算時間の大幅な短縮や解の品質の向上とともに,計算結果のばらつきを小さくできる効果を確認した.また同じ品質の解が得られるようにパラメータを調整した場合,見かけ上,スーパーリニアに高速化される例を実験により示すとともに,そのメカニズムを理論的に解析した.このような効率化の実現は,近似アルゴリズムを実用化する場合に重要な成果と言える.多重化手法は前章までに提案したアルゴリズムのみならず,他の分散探索問題のための近似アルゴリズムにも応用が可能である.

最後に6章において,結論として以上のまとめを行う.

本論文は「分散制約充足・最適化問題のマルチエージェント協調による解法の研究」と題し, 分散制約充足問題, 分散制約最適化問題の高速近似解法について論じている. 分散制約充足・最適化問題は, 複数のエージェント間の分散協調問題解決を定式化するための, 分散人工知能における基本的な枠組みの1つである. 本論文では, 斬新な発想により分散制約充足・最適化問題の高速近似解法開発に取り組んでいる.

本論文は6章からなる.

第1章「序論」では研究の背景を述べるとともに, 汎用ソルバ開発を将来の目標に位置づけ, そのためのアルゴリズムの幅を広げることを研究の目的としている.

第2章「分散制約充足・最適化問題」では分散制約充足問題, 分散制約最適化問題の定義を述べるとともに, 分散制約充足・最適化問題解法の既存研究について概観し, その応用分野について述べている. さらに分散制約充足・最適化問題解法に要求される項目について検討するとともに, 本研究におけるアルゴリズム設計の指針を立てている.

第3章「分散制約充足問題の近似解法の提案と評価」では分散制約充足・最適化問題を分散アルゴリズムで解く時の課題の1つである, 局所最適からの脱出について論じている. 分散環境における探索では, それぞれのエージェントが局所最適であるかどうか判断することは難しい. この課題を解決するために, 3章では分散制約充足問題において, 緩い組織化により局所最適を避けることを特徴とするMulti-agent Tabu Search手法を提案している. 提案した手法では, それぞれのエージェントが同じ値を一定時間選択するのを禁止し, 選択する値が無くなった場合は周囲のエージェントが協力するという局所ルールにより, 局所最適を避ける. 提案手法による具体的アルゴリズムとして3章では, DSTSとDHTSの2つを提案し, 実験による評価を通して効果を検証している. その結果, Multi-agent Tabu Search手法により局所最適を避けることで, 提案した2つのアルゴリズムDSTS, DHTSが既存のアルゴリズムよりも短時間のうちに高い成功率で充足解を計算できることを確認している.

第4章「分散制約最適化問題の近似解法の提案と評価」では分散制約最適化問題を解くためのアルゴリズムの停止の課題について論じている. 分散制約最適化問題を解くためには, 局所最適からの脱出と同時に, 何らかの解に到達したところで停止する必要がある. しかし分散環境では, 個々のエージェントが局所最適解かどうかを判断することが難しい. 局所最適に陥っていると誤判断すればアルゴリズムはいつまでも停止しない.また,局所最適であるのに最適解に到達したと誤判断すれば得られた解の品質は低くなる. この課題を解決するために, 4章では分散制約最適化問題のための高速近似アルゴリズムとしてDiSTaS-Anneを提案している. DiSTaS-Anneは3章で提案したDSTSにSimulated Annealing手法の要素を加えることで, 最適解に近い解へ到達して停止することを目指すことを特徴とする. 評価実験を行うことで, DiSTaS-Anneが高品質な解を高速に求められることを確認している. また, DiSTaS-Anneは大規模な問題でも高いパフォーマンスが得られることも確認している.

第5章「分散制約充足・最適化問題近似解法のための多重化手法の提案と評価」では, 分散制約充足・最適化問題のための分散近似アルゴリズムの効率を改善することを目指し, 分散アルゴリズムの多重化手法を提案している. 分散アルゴリズムの計算時間の多くはメッセージ通信に費やされるため, 個々のノードの計算量やメッセージ長の多少の増加はアルゴリズム全体の効率に直接大きな影響を及ぼさないという前提のもとでは, 分散近似アルゴリズムを多重実行することで効率を上げることが可能である. 5章ではその効果について極値分布理論を用いた理論的解析を行うとともに, シンプルなアルゴリズムの多重化実験により検証を行っている. その結果, 計算時間の大幅な短縮や解の品質の向上とともに, 計算結果のばらつきを小さくできる効果を確認している. また同じ品質の解が得られるようにパラメータを調整した場合, 見かけ上, スーパーリニアに高速化される例を実験により示すとともに, そのメカニズムを理論的に解析している. このような効率化の実現は, 近似アルゴリズムを実用化する場合に重要な成果である. 多重化手法は前章までに提案したアルゴリズムのみならず, 他の分散探索問題のための近似アルゴリズムにも応用が可能であることも述べている.

第6章「結論」では論文の内容を総括し, 今後の課題を整理している.

以上を要するに, 本論文は分散制約充足・最適化問題のための各種解法を創案し, 従来研究との比較実験によりその有効性を示したものであり, この分野に少なくない貢献を果している. すなわち, 本研究は情報理工学に関する研究的意義と共に, 情報理工学における創造的実践に関して価値が認められる. よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.