情報処理学会第 85 回全国大会

7M-07

勾配負荷を取り入れた粘菌アルゴリズムによる
数値標高地図上における径路探索
片岡 隼杜†

髙木 清二‡

公立はこだて未来大学 システム情報科学
公立はこだて未来大学 システム情報科学部複雑系知能学科‡

1.はじめに現在径路探索は目的地への径路や，避難径路など様々な場面で利用されている．一般に径路探索が使われているものとして，地図アプリやカーナビゲーションが挙げられ，多くの人が出発地から目的地への径路を確認するために用いている．このような 2 点間の径路探索にはダイクストラ法が主に使われている一方で，生物の形態形成を基にした径路探索アルゴリズムの研究が進められている．その中でも単細胞生物の真正粘菌の管ネットワーク形成を数理モデル化したアルゴリズムは出発点から目的地までのすべての径路を同時に比較する径路探索手法で，粘菌アルゴリズムと呼称する．粘菌アルゴリズ
ムに標高を避けるなどの効果を取り入れた研究が行われており，これは輸送ネットワークにおいて物を輸送する場合目的地の標高が高いほど標高に比例した位置エネルギー分の負荷を反映したものである．この場合，標高そのものが避ける条件となっているが，実際に輸送の負荷となるのは移動距離に対する標高差，つまり勾配であり，目的地までの標高差が同じであっても勾配が大きいほど負荷が大きくなる．
本研究は粘菌アルゴリズムに勾配から受ける効果を取り入れ，コンピュータ上で管形成のシミュレーションを行なうことで，坂道を移動する際の負荷を減らしつつ，全長を短くする効率の良い径路探索手法の開発を目的とする．さらに複数の径路を同時に探索するという特徴を活かし，様々な負荷強度の大きさにおける最適径路に加え，準最適径路を網羅的に探索し，移動効率の近い複数の径路を提案するシステムを構築する．
Optimal route search on a digital elevation map by slime moldalgorithm incorporating gradient load
†Hayato Kataoka ·Graduate School of Systems Information
Science, Future University Hakodate‡Seiji Takagi · School of Systems Information Science
Department of Complex and Intelligent Systems Future
University Hakodate

2.粘菌アルゴリズム
粘菌の管ネットワーク形成を数理モデル化したものを粘菌アルゴリズムという[1]．原形質が多く流れる管は太く成長し，流れの少ない管は分解され細くなるという粘菌の管の持つ性質を数式で表したもので，以下の様に定式化される．
粘菌のある地点𝑖, 𝑗の間の管を流れる原形質の流量𝑄𝑖𝑗 は Poiseuille 流から，管の長さ𝐿𝑖𝑗 を，管の太さを𝑎𝑖𝑗 ，静水圧をそれぞれ𝑝𝑖 , 𝑝𝑗 ，流体の粘性率を η として，4𝜋𝑎𝑖𝑗
𝐷𝑖𝑗 =8𝜂とおくと，𝐷𝑖𝑗
𝑄𝑖𝑗 =(𝑝 − 𝑝𝑗 )𝐿𝑖𝑗 𝑖と表される．管の時間発展は流量 に依存して成長する効果𝑓(𝑄)と自然に分解されて細くなる効果−𝐷によって決まる．これらの効果による𝐷の時間変化は次の微分方程式で表される．
𝑑𝐷𝑖𝑗= 𝑓(𝑄𝑖𝑗 ) − 𝐷𝑖𝑗𝑑𝑡
この方程式から，𝛥𝑡後の管の太さ𝐷𝑖𝑗 (𝑡 + 𝛥𝑡)は微分方程式を差分方程式で近似して，数値積分することにより得られる．
𝐷𝑖𝑗 (𝑡 + 𝛥𝑡) = 𝐷𝑖𝑗 (𝑡) + {𝑓(𝑄𝑖𝑗 ) − 𝐷𝑖𝑗 }𝛥𝑡3.勾配負荷の導入
本研究では，移動における勾配の影響は萩原ら [2]の研究における，人が斜面を歩行した際の血中乳酸濃度の値を参考にした．前章で示した
管の時間発展の式における減衰の項に負荷関数𝛼(𝜎)を取り入れることで負荷を表現する．ここで𝜎は地点𝑖, 𝑗の間の勾配である．
𝑑𝐷𝑖𝑗= 𝑓(𝑄𝑖𝑗 ) − 𝛼(𝜎)𝐷𝑖𝑗
𝑑𝑡
ある管が勾配の大きさに応じて減衰の値を大きくすることによって管が成長しにくくなる．この効果によって勾配から受ける効果を管形成における負荷として取り入れた．負荷強度パラメータを𝛽，勾配の大きさを𝜎，フィッティングパ

1-425

Copyright 2023 Information Processing Society of Japan.
All Rights Reserved.

情報処理学会第 85 回全国大会

ラメータを𝜖とすると，負荷関数𝛼(𝜎)は次の式で表される．
𝛼(𝜎) = (𝛽|𝜎𝑖𝑗 |)𝜖 + 1
ここで，𝜖 = 4.5として勾配から受ける効果を表現した．

けではない．例として，𝛽=2.8–3.2 における径路探索の結果を図 2 に示す．この径路探索では負荷強度が変わっても最適径路は変わらず，𝛽と共に準最適径路のみが変化する．これは𝛽=2.8–3.2 において安定解となる最適径路が存在し，その周りに多くの準最適解が存在していると考えられる．各径路の成長，衰退を解析し，準最適径路を4.クラスタリングによる径路の分類判別することで最適解のみの探索では見つからない
粘菌アルゴリズムによる径路探索は二点間の様々な径路を提案することが可能になった．
全ての径路を同時に探索し，勾配負荷などの条件を加えない場合は最終的に最短径路のみが成長し，他の径路はすべて衰退する．最短径路以外の径路の中で，距離の短い径路は衰退が遅く，距離の長い径路は衰退が早い傾向にある．ここで勾配負荷をかけると，急な勾配を避ける効果が現れるため，最短径路とは異なる径路が選択されるようになる．このように全長を短くしつつ急勾配を避けて最終的に選択された径路を最適径路と呼ぶ．そのため，最適径路に近く衰退の遅い径路は準最適径路と見なすことができる．
繰り返し計算を行なう過程で，管の太さ𝐷𝑖𝑗 と管の流量𝑄𝑖𝑗 に基づき，k-means 法を用いてクラスタリングを行ない，径路を最適径路，準最適径路，図 1 最適径路(緑)と準最適径路(青)とが衰退した径路の 3 つに分類した．
入れ替わる
5.結果と考察
様々な負荷強度𝛽における最適径路，準最適径路を網羅的に探索した結果を以下に示す．本研
究では観光地である函館市西部地区の道路網を対象に出発地を宝来町駅，目的地を護国神社として径路探索を行なった．グレースケールは標高を表し，明るい色ほど高い標高を表す．
負荷強度𝛽 =0 のとき最短径路が最適径路となり(図 1)，𝛽 =3.4 以上で最も勾配を避けた径路が最適径路となる(図 2)．𝛽の値を大きくすることで勾配を避ける効果が大きくなり，粘菌アルゴリズム本来の径路を短くする効果が相対的に小さくなる．そのため全長の長い径路が選択されるようになる．𝛽=0-3.4 の範囲で最適径路と準最適径路が𝛽と共にどのように変化するかを以下に示す．
𝛽が 0-2.8 の範囲のいくつかの値における最適径路と準最適径路を探索した結果を図 1 に示す．
𝛽=0.0–1.8 では最短径路が最適径路であるが，その準最適径路は𝛽=1.9 の最適径路が選択された．
逆に𝛽=1.9 の準最適径路は𝛽=0.0–1.8 の最適径路に近いものが選択された．同様の例として𝛽=2.7 と𝛽=2.8 の場合，𝛽の増加とともに準最適径路が次の最適径路に選択された．
しかし必ずしも図 1 のように負荷強度の上昇と共に現れた準最適径路が次の最適径路となるわ

図 2 最適径路が変わらず準最適径路のみ替わる
参考文献[1] Tero A., Kobayashi R. and Nakagaki T. :Physarum solver: A biologically inspired
method of road-network navigation, Physica A.,
363, 115-119 (2006).
[2] 荻原正大，山本正嘉 : 歩行路の傾斜，歩行速度，および担荷重量との関連からみた登山時の生理的負担度の体系的な評価 ～トレッドミルでのシミュレーション歩行による検討～, 体力科学，60(3), 327〜341 (2011)．

1-426

Copyright 2023 Information Processing Society of Japan.
All Rights Reserved.