読者です 読者をやめる 読者になる 読者になる

WonderPlanet DEVELOPER BLOG

ワンダープラネットの開発者ブログです。モバイルゲーム開発情報を発信。

群知能のシミュレーション

アルゴリズム 人工知能

こんにちは、エンジニアの成田です。

皆さんは群知能(Swarm Intelligence)という言葉をご存じでしょうか?人工知能の一研究分野で、個々は単純で局所的な情報しか持たない人工知能が集団になると中央システムを持たないにも関わらず全体で高度な振る舞いをするシステムのことを呼びます。
このような振る舞いは自然界にもあり、アリやハチなどの巣作りや鳥が群れを成して飛行する様子などに見られます。

今回はこのような群知能を簡単なシミュレーションで再現してみることにしました。

1.アリのフェロモントレイル

子供の頃、地面を歩くアリを追いかけた経験は誰にでもあると思います。アリの行方を追っていくと地面に落ちた蝶や蛾の死骸、飴玉なんかが落ちていてアリたちが整然と行列を作ってそれらを巣に持ち帰ったりしますよね。あれも群知能の一つと言われています。

アリたちは巣の周辺地図を持っているわけでもないのに巣から餌へまっすぐ行列を作って餌を運ぶことができます。別に彼らは女王アリから命令されてるわけでもお互いに声を掛け合っているわけでもないのにどのようにルートを構築できるのでしょうか。

実は彼らは地面に残った仲間の道しるべ(フェロモン)を辿っていて、それによって餌まで辿り着くことができると言われています。(帰り道はフェロモンと太陽コンパス等を併用しているとも言われています。)
各々のアリはフェロモンの方向に導かれているだけなのですが、最終的に形成される巣穴から餌までのトレイル(行列)は途中の障害物等を回避した最短経路に近い形になっているらしく、面白い現象だと思います。

2.シミュレーション概要

今回はこのアリのフェロモントレイルをシミュレーションしてみようと思います。
シミュレーションの全体像は参考文献とほぼ同じですが、微妙に異なっている部分もありますので簡単に一通り説明していきます。

  • シミュレーション空間
  • ・150x150セルの平面とし、平面中央にアリの巣穴、また任意の地点に餌を設置する。
  • セル
  • ・セルは帰巣フェロモン値a(0 < = a)と餌フェロモン値b(0 <= b)の変数を持つ。 ・フェロモンは1ステップ毎に一定の割合で「蒸発」し、また周囲のセルに「拡散」していく。
  • アリ ・アリは現在位置、状態{探索,帰巣}、向き、残り体力、フェロモン感度{敏感,鈍感}の変数を持つ。 ・アリは巣穴上に出現し、初期状態は「探索」。 ・アリは1ステップ毎に、現在位置のセルから周辺セル8セルのうち、自分の向きに対して前方となる3セルについてフェロモン値・自分のフェロモン感度による計算式に応じて確率を計算し、そのうち1セルを選択、現在位置のセルのフェロモン値を加算(フェロモンの分泌)してから次のセルへ移動、残り体力を減算する(前方3セルのフェロモン値がすべて0であれば各セルが選択される確率は同値、つまり3セルについてランダムな移動となる)。 ant ・移動の結果餌を見つけたアリは「帰巣」状態になり、巣穴を目指して同じように移動を繰り返す。 ・アリが分泌するフェロモンには2種類あり、「探索」状態では帰巣フェロモン、「帰巣」状態では餌フェロモンを分泌しながら移動する。アリが分泌するフェロモンの量は残り体力に応じて減少していく。 ・フェロモン値による確率計算式では「探索」状態では餌フェロモン値について計算し、「帰巣」状態では帰巣フェロモン値について計算する。 ・アリの体力が0になるとそのアリは死亡し消滅する。アリが減った数に応じて巣穴から新しいアリが補給される。  
  • ・餌の量はここでは∞とする。

だいたいこんな感じです。このようにアリは巣穴と餌の位置関係は全く知りません。全シミュレーション空間上でどのセルがフェロモン値が一番高いか、といったメタ的な情報も与えられません。ただ一つだけ読み取れるのは周囲のフェロモン値という局所的な情報のみです。

プログラミング言語はビジュアルデザイン等に用いられていて2DCGを作成するのに手っ取り早いProcessingを使うことにしました。
ちなみに今回は計算速度の面からPC上で実行しましたが、Processingで書けばAndroidにもアプリケーションを簡単にポートすることができちゃいます。

ソースコード:aco_simulator.zip

3.結果

以下のスクリーンショットでは、画面中央の黒丸は巣穴、右上の黄丸が餌です。また、小さな黒点は敏感アリ、赤点は鈍感アリ、黄点は餌を持ち帰っているアリ、灰点は体力が残り少ないアリです。青紫色の地面は帰巣フェロモンの濃度、赤紫色の地面は餌フェロモンの濃度を表わしています。

pic1

1.当初は全てのアリがランダムに動き回っている。巣穴近くはアリの密度が高いため帰巣フェロモン値が高くなる。

pic2

2.いくつかのアリが餌を発見し、帰巣フェロモン値の高い方へ移動する。場合によっては巣穴を見つけて帰還できる。

pic3

3.帰還できたアリが徐々に増えてくると、餌から巣穴まで餌フェロモンの道が形成されはじめ、餌に辿り着くアリも増加していく。

pic4

4.さらに餌フェロモンが強化されていき、アリのトレイルが形成されはじめる。トレイルの形成が始まるとトレイル上の帰巣フェロモンも強化されるため、トレイルは一直線に収束していく。

pic5

5.フェロモントレイルの完成。餌が無くならない限りこのトレイルは消滅しない。

いかがでしたでしょうか。アリのフェロモントレイルはとても面白い習性だと思います。
たまにはこのようなシミュレーションを作ってみるのも面白いのではないでしょうか。

4.参考

中川寛之, 田尾知巳, 西森拓, 2003. 蟻の化学走性と役割分化の模型. 数理解析研究所講究録, 1305:15-23. http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1305-3.pdf