博 士 （ 工 学 ） 川 村 秀 憲
学位論文題名
Design IVIethod of Pheromone Style Communication for Coordinated Agents Systems
（協調的エージェントシステムの為の フェロモン型コミュニケーションの設計法）
学位論文内容の要旨
本 学位 論文では 分散型問題解決システムとし てのマルチエージェントシ ステムに着目してい る 。マルチエージェントシス テムでは与えられたタスクを 解決すべく、多数のエージェン卜と呼 ば れる行動主体が自律的・適 応的に行動（動作）を行う。 各エージェントはボトムアップ的な設 計 によってデザインされ、単 に個々の和ではなく創発され た組織的振る舞いによって問題を解決 す ることが期待される。そこ では各工一ジェントが相互に 柔軟なコミュニケーションをとりなが ら 自律的に判断し、行動を行 うことが必然的に必要である 。しかし一般にそのようなシステムを 設 計するのは困難である。
そこで本論文では、柔軟な コミュニケーションによる組 織行動に基づくシステムの例として、
生 物のアりのコロニーに着目 する。アりは社会性昆虫と呼 ばれ、個々は単純な行動パターンに従 う が、群になると驚くべき能 カを持つことが知られている 。そこでは、生きていくために必要な 多 数のタスクをこなすために 適応的・自律的にアりの労働 カが配分され、それぞれが役割分担し な がら柔軟な組織をっくって いる。従ってアりのコロニー は究極的にマルチェージェン卜システ ム が目指すべきシステムの良 い手本であり、そのアナ口ジ ーはマルチエージェントシステムデザ イ ンにとって有効である。
アりのコロニーでは高い組 織カを示すために様々なコミ ュニケーションが行われているが、そ の なかでも特に重要な鍵を握っているのが化学物質（フェロモン）によるコミュニケーション（フ ェ ロモンコミュニケーション ）である。フェロモンコミュ ニケーションにおいては、フウロモン が ある明確な意味を持っと同 時に、群の集合行為によって 環境中に生成されるフェロモン場が集 合 行為を反映し、各個が群全 体の振る舞いを知覚すること なく、群全体の振る舞いから影響を受 け ることが可能であるという 特徴がある。ニれは従来のマ ルチエージェントシステムのコミュニ ケ ーション手法には見られな い特徴であり、このアナ口ジ ーを用いてコミュニケーションを設計 す ることは有効である。
そこで、環境中のフェ口モ ンをベクトル場として捉え、 フェロモン型コミュニケーションに基 づ くエージェントを入出カシ ステムとして以下のように定 義する。
イニくH，V X ツ Z f g h冫
甜：環境 入力，v：フェロ モン入カベ クトル，x:内部状態 ツ；環境 出力，z：フェロ モン出カベ クトル
x（f十1）〓/（x（f），u(t)， レ（f）），y（f十1）二ニニg（x（f），ll (t)，v（f）），z（r十1）＝ん（x（め，u(t)，v（f））
更 に時刻fにおけるf番目のエージェントのフェロモン人出カベク卜ルをり(t)，zf(t)とすると、
フェ 口モン場は以下のように定義 できる。
‑ 684―
P=くv，X，乏F>
X:フェロモン揚の内部状 態ベクトル
X（f十1）＝F（X（f）） 十とーz，(t），レ （f十1）＝X(t)
ただしIX｜＝izf｜：fリ1であるとする。本論文では一貫してこの定義に従ってフェロモン型コミュ ニケーションの設計を行っ ている。
従oて、本論文はマルチエ ージェン卜システムにおけ るフェロモン型コミュニケー ションの設 計法に関するものである。 特に提案した設計法に基づ く実問題への適用例として、いくっかの組 み合わせ最適化問題を解く マルチ工一ジェントシステ ムを開発し、数値実験を通してその有効性 を確認している。更に、フ ェ口モン型コミュニケーシ ョンと遺伝的アルゴリズムを組み合わせた マルチエージェントシステ ムを提案している。そこで は設計者が詳細な設計を行わなくても、エ ージ ェン ト群 が 自律 的に 合目 的的なフェ口モン型コミ ュニケーションを獲得するこ とが可能で あることが確認されている 。これらの結果から本論文 のフェ口モン型コミュニケーションの設計 法に基づくマルチエージェ ントシステムが有効である ことが示されている。本論文の各章の内容 は以下のように要約できる 。
第1章 は、 本研 究の 研究 背 景と して 生物 の アり のコ ロニーとマルチエージェント システムに ついて対比を行いながら、 フェロモン型コミュニケー ションに基づくマルチエージェン卜システ ムの設計法について述べて いる。また、これらのコンセプトに基づき従来の研究を概観している。
第2章 では 、本 研究 の出 発 点と して フェ 口 モン 型コ ミュニケーションを用いたマ ルチエージ エン 卜シ ステ ム のー っで あるColorni等に よ るAnt Algorithmに着目している。Ant Algorithm は巡回セールスマン問題の 近似的解法のーっとして提 案されているが、その欠点としてアルゴリ ズムの性格上探索の多様性 が低く、また探索が行われ る探索空間に偏りがある傾向がある。そこ でこの章ではこれらの欠点 を克服するために、Ant Algorithmに複数のコロニーの概念を導入し、
フ ェ ロ モ ン 型 コ ミ ュ ニ ケ ー シ ョ ン に 基 づ く コ 口 ニ ー 間 の 相 互 作 用 を 用 い たMultiple Ant Colonies Algorithmを提 案し てい る 。ま た、 計算 機実 験によって本提案がAnt Algorithmより 優れていることを示してい る。
第3章 では 、分 散型 問題 解 決の 例と して ー 般に 巡回 セールスマン問題よりも解く のが困難で あるとされる配送経路問題 を取り上げ、複数のエージ ェントによる分散型協調問題解決アルゴリ ズムを提案している。特に 各エージェントが分散的に 動作を行うため、どのように動作に整合性 を持たせ、協調的に問題解 決を行うかは非常に困難な 問題である。そこで本章ではエージェント 間のコミュニケーションと して、分散型協調問題解決 のためのフェ口モン型コミュニケーション の設計を行い、計算機実験 によってその有効性を確認 している。
第4章 では 、マ ルチ エー ジ ェン トシ ステ ム にお ける フェロモン型コミュニケーシ ョンの自律 的な獲得に関する研究につ いて述べている。ここでは 適応的なエージェントの資源配分、動的環 境に 対す る適 応 性、 限ら れた 環境 情 報か らの プラ ンニ ン グ等 の困 難な 状 況を含む 問題として Ants Warとい う エー ジェ ント 群の間で行われる競争を 提案している。この問題にお いてニュー ラルネットワークを用いて エージェントを設計し、更 に遺伝的アルゴリズムを適用することによ ってコミュニケーションの 進化的獲得が可能なモデル を提案している。また、計算機実験におい て 本 手 法 か ら コ ミ ュ ニ ケ ー シ ョ ン の 自 発 的 発 現 が 可 能 で あ る こ と を 示 し て い る 。 第5章では、本学位論文 の結諭について述べている。
―685−
学位論文審査の要旨
主 査 教 授 大 内 東 副 査 教 授 宮 本 衛 市 副 査 教 授 嘉 数 侑 昇 副 査 教 授 和 田 充 雄
学位論文題名
Design Ix/Iethod of Pheromone Style Communication for Coordinated Agents Systems
（ 協 調 的 エ ー ジ ェ ン ト シ ス テ ム の 為 の
フ ェロ モン型コミュニケーションの設計法）
本 学 位 論 文 で は 分 散 型 問 題 解 決 シ ス テ ム と し て の マ ル チ エ ー ジ ェ ン ト シ ス テ ム に 着 目 し て い る 。 マ ル チ エ ー ジ ェ ン ト シ ス テ ム で は 与 え ら れ た タ ス ク を 解 決 す べ く 、 多 数 の エ ー ジ ェ ン ト と 呼 ば れ る 行 動 主 体 が 自 律 的 ・ 適 応 的 に 行 動 （ 動 作 ） を 行 う 。 そ こ で は 単 に 個 々 の 和 で は な く 創 発 さ れ た 組 織 的 振 る 舞 い に よ っ て 問 題 を 解 決 す る こ と が 期 待 さ れ 、 各 エ ー ジ ェ ン ト が 相 互 に 柔 軟 な コ ミ ュ ニ ケ ー シ ョ ン を と り な が ら 自 律 的 に 判 断 し 、 行 動 を 行 う こ と が 必 要 で あ る 。 本 論 文 で は 、 柔 軟 な コ ミ ュ ニ ケ ー シ ョ ン に よ る 協 調 行 動 に 基 づ く シ ス テ ム の 例 と し て 、 生 物 の ア り の コ ロ ニ ー に 着 目 し て い る 。 ア り は 個 々 は 単 純 な 行 動 パ タ ー ン に 従 う が 、 群 に な る と 驚 く べ き 能 カ を 持 つ こ と が 知 ら れ て い る 。 そ こ で は 、 そ れ ぞ れ が 役 割 分 担 し な が ら 柔 軟 な 組 織 を っ く り 、 様 々 な タ ス ク を 行 っ て い る 。 従 っ て ア り の ア ナ ロ ジ ー は マ ル チ エ ー ジ ェ ン ト シ ス テ ム デ ザ イ ン に と っ て 有 効 で あ る 。
ア り の 協 調 行 動 で 重 要 な 鍵 を 握 っ て い る の が 化 学 物 質 て フ ェ ロ モ ン ） に よ る コ ミ ュ ニ ケ ー シ ョ ン で あ る 。 フ ェ ロ モ ンjミ ュ ニ ケ ー シ ョ ン に お い て は 、 フ ェ ロ モ ン が あ る 明 確 な 意 味 を 持 っ と 同 時 に 、 群 の 集 合 行 為 に よ っ て 環 境 中 に 生 成 さ れ る フ ェ ロ モ ン 場 が 集 合 行 為 を 反 映 し 、 各 個 が 群 全 体 の 振 る 舞 い を 知 覚 す る こ と な く 、 群 全 体 の 振 る 舞 い か ら 影 響 を 受 け る こ と が 可 能 で あ る と い う 特 徴 が あ る 。 こ れ は 従 来 の マ ル チ エ ー ジ ェ ン ト シ ス テ ム の コ ミ ュ ニ ケ ー シ ョ ン 手 法 に は 見 ら れ な い 特 徴 で あ り 、 こ の ア ナCジ ー を 用 い て コ ミ ュ ニ ケ ー シ ョ ン を 設 計 す る こ と は 有 効 で あ る 。
本 論 文 の 各 章 の 内 容 は 以 下 の よ う に 要 約 で き る 。
第1章 は 、 生 物 の ア り の コ ロ ニ ー と マ ル チ エ ー ジ ェ ン ト シ ス テ ム に つ い て 対 比 を 行 い な が ら 、 エ ー ジ ェ ン ト 環 境 中 の フ ェ ロ モ ン を ベ ク ト ル 場と して 定義 し、
フ ェ 口 モ ン 型 コ ミ ュ ニ ケ ー シ ョ ン に 基 づ く エ ー ジ ェ ン ト を 入 出 カ シ ス テ ム と し て 定 義 し て い る 。 ま た 、 そ の 定 義 に 従 っ て フ ェ ロ モ ン 型 コ ミ ュ ニ ケ ー シ ョ ン に 基 づ く マ ル チ エ ー ジ ェ ン ト シ ス テ ム の 設 計 法 に つ い て 述 べ て い る 。 更 に 、 関 連 研 究 を 概 観lし て い る 。
―686―
第2 章で↓まフェロモン型コミュニケーションを用いたマルチェージェントン ス テ ム の ー っ であ る
Colorni等 によ るAnt Algorithm に 着目 し、 その アルゴ リ ズ ムの 欠点 を克 服す るた めに、 複数のコ口ニーの概念を導入し、フェロモン型 コ ミ ュ ニ ケ ー シ ョ ン に 基 づ く コ ロ ニ ー 間 の相 互 作 用 を 用 い た
Multiple Ant Colonies Algorithmを提 案して いる。また、計算機実験によって本提案がより 優れていることを示している。
第3 章 では 、複 数の エー ジェ ント によ る分 散型 協調 問題解 決アルゴリズムを 提 案し 、配 送経 路問 題に 適用し ている。特に各エージェントが分散的に動作を 行 うた め、 どの よう に協 調的に 問題解決を行うかは困難な問題である。そこで 本 章で は分 散型 協調 問題 解決の ためのフェロモン型コミュニケーションの設計 を行い、計算機実験によってその有効性を確認している。
第4 章 では 、マ ルチ エー ジェ ン卜 シス テム にお ける フェロ モン型コミュニケ ー ショ ンの 自律 的な 獲得 に関す る研究について述べている。ここでは適応的な エ ージ ェン トの 資源 配分 、動的 環境に対する適応性、限られた環境情報からの プ ラ ン ニ ン グ 等の 困難 な状 況を 含む 問題 とし て
Ants Warと いう エー ジェン ト 群 の間 で行 われ る競 争を 提案し ている。この問題においてニューラルネットワ ー クを 用い てエ ージ ェン トを設 計し、更に遺伝的アルゴリズムを適用すること に よっ てコ ミュ ニケ ーシ ョンの 進化的獲得が可能なモデルを提案している。ま た 、計 算機 実験 にお いて 本手法 からコミュニケーションの自発的発現が可能で あることを示している。
第5 章では、本学位論文の結諭について述べている。
これ を要 する に、 著者 はフェ ロモン型コミュニケーションに基づくマルチエ ー ジェ ント シス テム の設 計法を 提案し、その有効性を明らかにすることで、マ ル チエ ージ ェン 卜シ ステ ムに関 する研究において新知見を得たものであり、シ ス テム 情報 工学 、及 び複 雑系工 学の進歩に寄与するところ大なるものがある。
よって著者は、北海道大学博士（工学）の学位を授与される資格あるものと認める。
ー687ー
