ルールベース蟻コロニー最適化に基づく自律行動型ロボットの知能化
M2008MM032 山本勇作
指導教員：高見勲

1

はじめに

本研究の目的は，自律行動型ロボット知能化である．知能化とは，知識がない状態から学習を開始し，行動過程から得た経験を基に知識を蓄積しながら，より正確な判断を行うことである．その検証として迷路問題を例にとり，Ant Colony Optimization(ACO)[1] にウィルス感染[2] や Particle Swarm Optimization(PSO)[3] などの学習機能を融合させたアルゴリズムを提案する．本研究の特徴は以下の点である．

1. ACO にルールを適用し，探索回数の低減を図る．
2. ACO に PSO，ウィルス感染の概念を融合させ，局所解の回避を図る．
3. エントロピー概念を導入し，収束性を評価する．
有用性は以下の点である．
1. 探索領域のマップを作成しながら学習的に最短経路問題を解く．

達する過程を 1 試行とし，それを n 回繰り返す．

図 1 横 25 縦 17 の迷路
ACO を図 1 のような迷路に適用するために，以下のようなルールを制定する．
ルール 1 通過可能なノードを判別し，式 (1) によりマップを作成する．
ルール 2
進行方向の選択として，各ノードごとに通過した回数をカウントし，式 (2) により，同じ経路を何回も巡回する事を禁止する．
図 2 は，本研究で採用している基本的なアルゴリズムの流れである．

2. 進行方向を決定する手段として，確定的要素（ルール）と確率的要素のハイブリッド進路決定法の提案
により，ACO を環境認識し，最短経路を学習する過程に適用する．
3. 局所解に陥らず，大域的最適解を求める手段としてウィルス感染による部分空間探索を適用する．
ダイクストラ法などの確定的方法に比べて，ACO が必要となる問題は以下の点である．
1. 地図情報がない状態からスタートして，地図情報を獲得しながら，最短経路を求める問題．
2. 一旦得られた地図情報が時間と共に変化する条件が動的な問題．
3. 経路長だけでなく，目的地方向のベクトルや，進路の変更回数，価値観（例えばカーナビゲーションにおいて，運転手にとって右折より左折の方がストレスが少ない）などの複数の評価を考慮する必要がある問題．

図 2 アルゴリズムの流れ通行可能な (x, y) 集合を AR(Admissible Region) とし，通行不可な (x, y) 集合を IR(Inhibited Region) とする．
式 (1) はマップを作成する際，通行可否なノードであるか判定し，学習する式である．(v, w) は進行方向を操作するための変数であり，取りうる値は v, w = −1, 0, 1 で，|v| + |w| = 1 を満たす．
if (x + v, y + w) が通行可能なノードthen (x + v, y + w) を AR の要素に加える
if (x + v, y + w) が通行不可なノードthen (x + v, y + w) を IR の要素に加える
2.1 ルールベース蟻コロニー最適化(1)
本研究では図 1 のような迷路を想定する．1 マスを座式 (2) により，ループ探索を禁止している．また，式 (2)標 (x, y) としてとらえ，その座標をノードとし，白いマは各試行回数ごとの各蟻全てに対して別々に定義する．式スは通行可能なノード，黒いマスは通行不可なノードと(2) において，最小値が複数ある場合は，式 (3) で確率的し，この集合をマップとする．マップを探索する蟻の行に進行方向を決定する．移動方向 (v, w) の選択は，移動動では，前後左右のノードにのみ移動できるものとする．
先のフェロモン濃度に比例する．
また蟻のフェロモンは，従来法ではパスにフェロモンをmin
P C(x + v, y + w)
(2)
与えているが，本研究ではノードに与える．スタート座v,w
標 S から蟻 m 匹を放ち，ゴール座標 G に全ての蟻が到

2

本研究での蟻コロニー最適化手法(x+v,y+w)=AR

P C(x, y) は，ノード (x, y) を通過した回数である．ノード (x, y) から (v ∗ , w∗ ) の方向に行く確率 pv∗ ,w∗ (x, y) は式(3) で表す．
τ (x + v ∗ , y + w∗ )(x+v ∗ ,y+w∗ )∈AR
 X
τ (x + v, y + w)
pv∗ ,w∗ (x, y) =
v,w



0(x+v ∗ ,y+w∗ )∈IR(3)
τx,y は，ノード (x, y) のフェロモン濃度を示す．
試行回数 t 回目において，全ての蟻がゴールまで辿り着いたら，式 (4) によってフェロモンの更新を行う．試行
回数 t 回目の最短経路を発見した蟻だけにフェロモンを与える．これにより収束の高速化を促進している．
τx,y (t + 1) = ρτx,y (t) + ∆τx,y(4)ρ は蒸発に関するパラメータである．τx,y はフェロモン増加量であり，式 (5) のように定義する．
 1/L (x, y) ∈ BR
∆τx,y =(5)
 0(x, y) ∈/ BR
L は試行回数 t 回目の最短経路を見つけた蟻の経路長である．BR は試行回数 t 回目で得られた最短経路上の (x, y)集合であり，最短経路を発見した蟻だけにフェロモンを与えている事を示している．
2.2

ウィルス感染による部分空間探索フェロモンを調整することが考えられる．そこで，PSOとの融合アルゴリズムを提案する．
ACO において，Particle とは各蟻を示し，各蟻が試行回数 t までに学習した最短経路を pbest，群全体が試行回数 t までに学習した最短経路を gbest とし，式 (6)(7)(8)を定義する．

τx,y (t + 1) = ρτx,y (t) + C1・rand1mX

k−pbest∆τx,y+

k=1
gbest
C2・rand2 ∆τx,y(6)C1 ，C2 は重み，rand1 ，rand2 は 0〜1 の一様乱数，k −pbest は蟻 k が試行回数 t までに発見した最短経路である．
(1/Lk−pbest (x,y)∈k−pbest−routek−pbest∆τx,y=(7)0(x,y)∈k−pbest−route/Lk−pbest は蟻 k が試行回数 t までに発見した最短経路長，
k − pbest − route は蟻 k が試行回数 t までに発見した最短経路の座標集合である．
(1/Lgbest (x,y)∈gbest−routegbest∆τx,y=(8)0(x,y)∈gbest−route/
Lgbest は群全体が試行回数 t までに発見した最短経路長，gbest − route は群全体が試行回数 t までに発見した最短経路の座標集合である．

3

エントロピーの定義と解の収束性評価

スタート地点からゴール地点までの二地点間最短経路問題を解く場合，探索領域が大きくなると二地点間のノードが多数になり，局所解に陥りやすい．ACO の場合，大域的最適解を発見する前に局所解のフェロモン濃度が高くなってしまうことが問題である．局所解に収束することを回避するために，ウィルス感染の考え方を ACO に適用する方法を提案する．特徴は，部分空間をフェロモン濃度に関係なく徘徊するフェロモン鈍感期を設けた点である．以下にアルゴリズムの流れを示す．

進化計算法の一般的な評価方法は，求めた解と最適解の誤差率，適応度の比較や，最適解を求めるまでの時間などを比較している場合が多い．進化計算法において，多様性と収束性のバランスを保つことが必要不可欠であり，それによって誤差率や計算時間も大きく改善される．そこで，エントロピーを観測することで ACO の収束特性を解析する．
巡回セールスマン問題における ACO の収束特性については，フェロモン濃度情報のエントロピー変化を観測しstep1 蟻の集団をウィルス感染集団と非感染集団に分け， て解析している [4]．本研究では，学習経過の情報はフェ試行回数 z 回ごとにウィルスに感染させる．
ロモン濃度 τx,y (t) に保持されている．τx,y (t) のエントロ
step2 非感染集団は通常通りの探索を続け，ウィルス感 ピーを式 (9) 式 (10) と定義する．
染集団は部分空間をそれ以前のフェロモン濃度に関XX
E(t) = −px,y (t) log px,y (t)(9)
係なく探索する．

step3 部分空間の形成方法は，それまでの最短経路を利用する．経路上の 2 点をランダムで選択し，その 2点を対角とした 4 角形を形成する．部分空間でデッドロックになってしまった場合は，その試行に関する情報を破棄する．
2.3

PSO による学習機能強化

フェロモンの与え方について，ACO の基本モデル Ant
System(AS) では全ての蟻の経路にフェロモンを増加させ，本研究では試行回数 t 回目の最短経路を発見した蟻だ
けにフェロモンを与える方法を提案した．さらなる学習機能の向上を考えた場合，過去の行動履歴に従って動的に

x y6=xτx,y (t)px,y (t) = X X
τx,y (t)(10)

x y6=xE(t) の最大は，フェロモン濃度が一様に分布している
τx,y (0) のときで，その値は log n である．n は通過可能なノードの数である．そこで，式 (11) のように正規化エントロピー EN (t) を用いる．EN (t) は，[0, 1] の区間の値となる．
E(t)
(11)
EN (t) =log nエントロピーの解析方法について，フェロモンが均一に分布している時はエントロピーが高く，多様性がある状態である．また，フェロモン分布が片寄っている時はエントロピーが低いことを示し，解が収束している状態である．さらに，エントロピーの減少勾配を観測することで収束の速さを解析することができる．

4る．蟻 10 匹を試行回数 100 回繰り返し，それぞれの試行の最短経路を出力したグラフが図 4 である．

シミュレーション解析

シミュレーションには Intel(R)Core(TM)2 Duo CPU
T8300 2.4GHz と 4GB のメモリを持つ計算機を使用した．
図 4 ルールの有用性検証
図 4(A) は基本モデル AS のみのグラフである．計算時間
蟻がマップを作成しながら経路探索を進める過程を図 は 4 分 11.615 秒で，全体の最短経路長でも 41998 で最適3 に示す．本来の ACO は，多くの蟻に経路探索させ，群 解 412 には程遠く，試行回数 70 回目辺りから発散する体行動で最短経路を導くが，マップ作成過程を把握する 傾向も見られる．経路長が長くなる理由として，均一にために 1 匹の蟻で検証する．検証環境は，図 1 において， 分布された初期状態から進行方向を確率式だけで決める，左下のスタート座標 S からゴール座標 G までを探索する 前進後退を繰り返すような移動になり，またフェロモンまでを 1 試行とし，100 回繰り返す．最短経路長 60 であ の増加量は距離に逆数になるので微小で，最短経路へのる．黒い点は，それまでの全試行の中での最短経路であ 収束の速度が小さいことが原因である．図 4(B) は基本モる．アルゴリズムは本研究が提案するルールベース蟻コ デル AS に確定的要素 (ルール) を適用させたときのグラロニー最適化である．図 3 を解説する．図 3(A) は 1 匹の フである．計算時間は 0.658 秒で，確定的要素の適用で蟻が 1 回目の試行を終えた図である．通過可能な領域を 計算時間の改善が見られる．初めは大域的に探索し，試判別して徘徊し，通過した場所のみのマップを出力して 行回数 40 回目辺りから最適解に収束していることがわかいる．行き止まりの経路に進入し，戻って来ている．最短 る．ルールが有効に働き，前進後退を繰り返すような移経路ではない．図 3(B) は 2 回目の結果表示である．(A) 動を回避し，さらに通路の通過回数が少ない方向に移動とは異なる経路を通り，(A) よりもマップ作成は進んで するため，大域的探索を可能にしている．
いる．しかし，最短経路は発見できていない．図 3(C) は
図 5 は，図 4 におけるエントロピーの変化である．
30 回目の結果表示である．マップの作成は終了している．
経路の色が濃いほどフェロモンの濃度が高い事を示している．フェロモン濃度が最も高い経路は最短経路ではない．図 3(D) は 100 回目の結果表示である．最短経路に収束していることが分かる

4.1

マップ作成の検証

図 5 収束特性の比較
基本モデル AS は試行回数を重ねてもエントロピーが 0.9で収束してしまっているので，解の収束性が欠如し何回繰り返しても最適解への収束は見られない．本研究のアルゴリズムは，初期から徐々にエントロピーが収束し始め，最適解を発見した後もある程度高い値を保持している．これにより，探索領域がリアルタイムに変化する場合にも対応できる．

4.3
図 3 マップ作成検証

4.2

ルールベース蟻コロニー最適化の検証

確定的要素 (ルール) と確率的要素のハイブリッド進路決定法の有効性を検証する．検証環境は，図 1 のような迷路を縦 130 横 82 に拡大した迷路を使用する．最短経路は 1 通りしかなく，最短経路長は 412 である．大きな
マップで検証する理由は，探索領域が広がっても実用的な時間内で解を求めることができるか検証することであ

ウィルス感染による部分空間探索の検証

ウィルス感染による部分空間探索の有用性を検証する．
検証環境は図 1 のような迷路を縦 130 横 82 に拡大した迷路を使用する．スタートからゴールまでの経路が多数存在する迷路であり，最短経路長は 208 である．このようなマップを使用することにより，局所解に陥りやすい環境でもウィルス感染による部分空間探索が有効的に働くことを示す．蟻 100 匹を試行回数 100 回繰り返し，その過程を 10 回行い，平均値を取り，最適解との誤差率を出力させたグラフが図 6 である．

図 6 最適解との誤差率
ウィルス感染がない場合は局所解に陥っていることが多かったので，最終的な誤差率が高くなっているが，ウィルス感染ありの場合は，局所解に陥る場合があるが，前半の試行回数から効率的に学習を行い，素早く最適解付近に収束している事が分かる．改善された理由は，局所解に陥った場合，ウィルス感染による部分空間探索によって，ある区間を集中的に探索できるため，局所解を回避できたためであると考えられる．

4.4

リアルタイム変化迷路に対する検証

あらかじめマップの情報が得られており，マップが変化しない場合の最短経路を求めるならば，ダイクストラ法などの確定的方法が有効である．しかし，リアルタイムにマップが変化する場合，最初から計算し直す必要がある．知識の蓄積による利点として，探索領域が変化した場合でも学習の継続ができる点である．
図 7 は迷路の拡大図で，左下から右上までのパスについて，マップを変化させる前後の出力表示である．試行
回数 50 回，70 回を終えた時点で迷路を変化させる．図7(A) は 50 回目，図 7(B) は 55 回目，図 7(C) は 75 回目の結果表示である．

誤差が生じている．これは，ウィルス感染で部分空間に区切る際，ランダムで最短経路上の 2 点を選択するため，局所解に陥っている空間を部分空間探索できないためであると考える．そこで，ACO と PSO の融合アルゴリズ
ムを同じ迷路に適用し，ウィルス感染による部分空間探索と性能を比較する．蟻 100 匹を試行回数 200 回繰り返し，その過程を 10 回行い，平均値を取り，誤差率とエントロピーを図 8 に示す．

図 8 PSO とウィルス感染の比較
PSO を適用した場合，多様性を維持したまま学習が進み，誤差なく最適解に全て収束している．ウィルス感染に比べ，PSO を適用した場合はエントロピーの減少が緩やかで，収束速度はウィルス感染に劣るが，多様性の維持は十分見てとれる．

5

おわりに本研究で得られた成果は以下のとおりである．
1. 蟻コロニー最適化手法を迷路探索する行動過程に適用した．

2. マップを作成しながら学習的に最短経路を求める方法を提案し，通路や壁などの初期値を与えなくても探索を可能にした．
3. 蟻の進行方向の選択法として，確定的要素 (ルール)と確率的要素のハイブリッド進路決定法を提案し，迷路を効率的に探索することを可能にした．
4. ウィルス感染による部分空間探索法を提案し，大域的探索と最適解への素早い収束性を実現した．

図 7 リアルタイム変化迷路の検証
図 7(A) は 50 回目までにフェロモンが最短経路上に収束している．図 7(B) は 55 回目の結果表示である．50 回目終了時点で最短経路上の 2 箇所を通行不可にする．様々なパターンの迂回路を探索し，最短迂回路にフェロモンが収束している．図 7(C) は 75 回目の結果表示である．70
回目終了時点に，それまでの最短経路を更新するように離れた場所を 1 箇所通行可能にする．最短経路上を通行不可にして迂回路を探索するよりも，こちらの変化の方がフェロモン収束後の多様性を必要とされる．この検証により，試行回数が多くても多様性を維持し，常に新しい経路と最短経路を探索していることが分かる．

4.5

ACO と PSO の融合アルゴリズム検証

図 6 において，本研究が提案するウィルス感染による部分空間探索でも全て最適解が発見できず，最適解との5. ACO と PSO の融合アルゴリズムを提案し，過去の情報を学習機能に取り入れ，誤差なく最適解に収束することを示した．
6. フェロモン濃度のエントロピーを観測することで，解の収束性を評価した．
今回は最短経路探索手法を主体に研究したが，今後はカーナビゲーション等への応用を検討する．

参考文献[1] M．Dorigo，V．Maniezzo and A．Colorni：The Ant System: Optimization by a Colony of Cooperating Agents，IEEE Trans．on SMC-Part B，26-1，29/41 (1996)[2] 安藤貴彦：GA を用いた極配置による PID 制御，高速信号処理応用技術学会誌，10-2，74/80 (2007)[3] 石亀篤司：Particle Swarm Optimization-群れでの探索-，
計測と制御，47-6，459/465 (2008)[4] 筒井茂義：カニングアントシステムの収束特性について，情報処理学会研究会報告 数理モデルと問題解決 2008-MPS-70，2008-65，31/34(2008)