TOP > 国内特許検索 > 経路探索方法および経路探索システム > 明細書

明細書 :経路探索方法および経路探索システム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2018-100945 (P2018-100945A)
公開日 平成30年6月28日(2018.6.28)
発明の名称または考案の名称 経路探索方法および経路探索システム
国際特許分類 G01C  21/34        (2006.01)
FI G01C 21/34
請求項の数または発明の数 4
出願形態 OL
全頁数 7
出願番号 特願2016-248407 (P2016-248407)
出願日 平成28年12月21日(2016.12.21)
発明者または考案者 【氏名】石田 好輝
出願人 【識別番号】304027349
【氏名又は名称】国立大学法人豊橋技術科学大学
審査請求 未請求
テーマコード 2F129
Fターム 2F129AA02
2F129AA03
2F129CC15
2F129CC16
2F129DD02
2F129DD21
2F129DD62
2F129EE52
2F129HH12
要約 【課題】画像における探索の環境が未知であり、探索に使用するリソースに制限があっても探索が可能な経路探索方法および経路探索システムを提供する。
【解決手段】画像情報に対し自己相似性に基づいて経路を生成する経路探索方法であって、使用するリソースによって経路の生成を制御するステップと、探索範囲を設定するステップとを備え、画像上の環境に適合させ所望の探索を逐次行う。経路の生成を制御するステップは、探索ノードの成長および収縮を制御し、使用するリソースの残量に応じて該収縮の確率を増減させる。
【選択図】図1
特許請求の範囲 【請求項1】
画像情報に対し自己相似性に基づいて経路を生成する経路探索方法であって、
使用するリソースによって経路の生成を制御するステップと、探索範囲を設定するステップとを備え、
画像上の環境に適合させ所望の探索を逐次行うことを特徴とする経路探索方法。
【請求項2】
前記経路の生成を制御するステップは、成長および収縮を制御するステップであって、
使用するリソースの残量に応じて該収縮の確率を増減させることを特徴とする請求項1に記載の経路探索方法。
【請求項3】
画像情報に対し自己相似性に基づいて経路を生成する経路探索システムであって、
使用するリソースによって経路の生成を制御する手段と、探索範囲を設定する手段とを備え、
画像上の環境に適合させ所望の探索を逐次行うことを特徴とする経路探索方法。
【請求項4】
前記経路の生成を制御する手段は、成長および収縮を制御する手段であって、
使用するリソースの残量に応じて該収縮の確率を増減させることを特徴とする請求項3に記載の経路探索システム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、画像データに対する経路の探索方法および探索システムに関するものである。
【背景技術】
【0002】
生物の構造がもつ自己相似性は効率よく空間を充填できることが知られている。少ない体積で多くの表面積が必要となる血管の分岐構造や腸の内壁なども自己相似の構造になっており、この性質を活かして探索問題へ応用する技術が提案されている。
【0003】
例えば、空間充填曲線法がある(例えば、非特許文献1を参照)。空間充填曲線法は巡回セールスマン問題の近似解法として用いられ、高速に解を求めることができるのが特徴である。
【0004】
また、探索問題を解決する代表的な手法として木探索アルゴリズムがあり、特に最初からデータが木構造で明示されていない場合は動的に木を生成する必要がある。探索空間が非常に大きなものになるため、評価関数を用いることが望ましいが、探索の空間あるいは目標状態の分布など探索の環境が未知であったり、探索領域を数学的な関数で記述するのが難しかったりする場合などの複雑環境下にある場合では適切な評価関数の設定が難しく、探索コストやリソースの制約によって解に辿りつけない場合がある。
【0005】
一方、地理情報における人工物である建物や道、自然物である木や川などの画像を生成する技術としてLindenmayer System(以下、L-systemという。)が用いられている(例えば、非特許文献2を参照)。L-systemは、植物の成長過程等を記述できる形式文法の一種である。植物等の画像を生成するために用いられているが、画像生成技術としてのL-systemは生成文法に基づくため、既存の画像構成要素に対しての探索は困難である。
【先行技術文献】
【0006】

【非特許文献1】「空間充填曲線とフラクタル」,ザーガン,H.著,鎌田 清一郎訳,シュプリンガー・ジャパン社,1998年12月出版
【非特許文献2】Gabriela Ochoa, ”An Introduction to Lindenmayer Systems“ インターネット(URL:https://s10.lite.msu.edu/res/msu/botonl/b_online/e28_3/lsys.html)
【発明の概要】
【発明が解決しようとする課題】
【0007】
上述した従来の技術には、探索の環境が未知であり、探索のためのリソースに制限がある場合(以下、複雑環境下という。)において、探索を十分に行えないという課題があった。
【0008】
本発明が解決しようとする課題は、前記課題を克服するためになされたものであり、自己相似性を示す構造を記述可能な文法(以下、単にルールということがある。)を基にして、複雑環境下においても解を求めることが可能な経路探索方法および経路探索システムを提供することである。
【0009】
具体的には、本発明係る経路探索は、L-systemを基に、成長および収縮のためのルールを付与して探索経路を生成し、リソース量を評価しながら、画像上で所望の探索を環境に適合させ、逐次、行うものである。
【課題を解決するための手段】
【0010】
本発明に係る経路探索方法は、画像情報に対し自己相似性に基づいて経路を生成する経路探索方法であって、
使用するリソースによって経路の生成を制御するステップと、探索範囲を設定するステップとを備え、
画像上の環境に適合させ所望の探索を逐次行うことを特徴とする。
【0011】
さらに、前記経路の生成を制御するステップは、成長および収縮を制御するステップであって、
使用するリソースの残量に応じて該収縮の確率を増減させることを特徴とする。
【0012】
本発明に係る経路探索システムは、画像情報に対し自己相似性に基づいて経路を生成する経路探索システムであって、
使用するリソースによって経路の生成を制御する手段と、探索範囲を設定する手段とを備え、
画像上の環境に適合させ所望の探索を逐次行うことを特徴とする。
【0013】
さらに、前記経路の生成を制御する手段は、成長および収縮を制御する手段であって、
使用するリソースの残量に応じて該収縮の確率を増減させることを特徴とする。

【発明の効果】
【0014】
本発明に係る経路探索方法および経路探索システムによれば、探索環境が未知であっても経路を求めることができる。

【図面の簡単な説明】
【0015】
【図1】本発明に係る経路探索方法のフロー図である。
【図2】本発明に係る経路探索方法における粘菌をモデルとした生成および収縮ルールの記述例である。
【図3】本発明の実施例に係る経路探索の結果を示す模式図である。自動車から中間点で徒歩に移動手段を変えた場合の経路探索の例である。
【図4】本発明の実施例に係る経路探索の結果を示す模式図である。高低差をリソース量の変化として粟原した場合の経路探索の例である。
【図5】本発明の実施例に係る経路探索の結果を示す模式図である。遠回りする場合の経路探索の例である。
【発明を実施するための形態】
【0016】
本発明を実施するための形態は、次のとおりである。本発明係る経路探索方法は、プログラム言語を用いてそのアルゴリズムが記述され、演算処理装置、メモリ、外部記憶装置および表示装置などが電気的に接続されてなる計算機上で、必要なハードウェアを制御してなり、本発明に係る経路探索システムは、該経路探索方法を実装したプログラムが動作する該計算機システムにより実現される。

【0017】
本発明に係る経路探索方法を以下に図を用いて説明する。本発明に係る経路探索方法では、粘菌を模擬した方法を実装する。該粘菌の成長において自己相似性が見られ、L-systemを基にして、粘菌の成長を任意のプログラム言語を用いて生成ルールとして記述する。

【0018】
従来のL-systemでは、非可逆的な生成しか表現されていなかったが、複雑環境下での探索を行うため、粘菌の収縮の概念を取り入れた死滅ルールを記述する。

【0019】
本発明に係る経路探索のフローチャートを図1に示す。
本発明に係る探索情報が実装されたプログラムが開始されると、始めにコンフィグファイルを読み込む。

【0020】
次に、図2に示す粘菌の生成ルールに記述されたパラメータが入力され、表示装置に探索領域を表示する。ユーザーにより探索開始地点と目標地点が指定され決定されると、探索ノード(図2中、粘菌ノード)を開始地点に設置する。探索ノードは、前記生成ルールに従い探索を実行する。表示装置には、探索の実行に応じて探索ノードを表示する。

【0021】
所定の間隔で区切られた領域を探索後、探索ノードの位置と目標地点を比較し、同じ座標でなければ探索および探索ノードの表示を繰り返し実行する。

【0022】
一方、探索ノードの位置と目標地点が同じ座標となったとき、開始地点と目標地点を結んで経路を生成した探索ノード以外の探索ノードを終了状態へ遷移させ、探索ノードを死滅させる。

【0023】
確認のため、終了状態となり死滅する探索ノードを表示装置へ表示させ、不用な探索ノードがなくなるまで、終了状態への遷移、死滅、表示を繰り返す。

【0024】
最後に、目標地点に辿り着いた探索ノードだけが残り、生成した経路情報(探索ノードの集合)、とくに該集合の長さと探索のステップ数を表示装置へ表示して、プログラムを終了する。

【0025】
本発明の実施に係る生成ルール(図2)は、変数の集合、定数の集合、初期状態、および前記変数の集合を変化させる置換規則のタプルにより表現され、自己相似性または再帰的な成長を表す文法である。

【0026】
図2に示すように、変数の集合を0,1,2,3,d,Dと表す。ここで、死滅の状態をd、目的地Dとしている。また、定数の集合として前方(すなわち順方向)に生成を文字^、右90度方向に生成を文字]、および左90度方向に生成を文字[、文字列の終端を$、任意の一文字を.で表す。本発明に係る経路の探索は前記文字の集合として表現される。

【0027】
探索制御のパラメータとして、死滅発生確率pd、生成促進確率ph、分岐確率pa,pb,pc(ただし、pa+pb+pc=1)を用いる。さらに、探索に使用するリソース量Rを定義する。リソース量は、すべての探索ノードで使用しているリソースの総和以上となる。探索ノードの集合をN、各探索ノードで使用しているリソース量をrn、総和をΣとすると、R≧ΣNrnと表される。

【0028】
探索の実行は次の通りである。
探索ノードの次の探索範囲に障害物があるとき、探索ノードは、その方向に経路を生成しない。また、探索範囲に高低差がある場合、高低差に応じて使用リソース量に差を設ける。たとえば、リソースの使用量を平坦時1とした場合、高い地点への生成時は2とする。

【0029】
分岐確率pa,pb,pcは、次のとおり設定する。
前方すなわち順方向への探索はpa、左右方向への探索はpb、順方向および左右方向(以下、全方向ということがある。)への探索はpcの値を設定することにより探索方向を制御できる。たとえば、(pa, pb, pc)=(0, 0, 1)と設定すると、探索ノードは全方向を探索し、可能であれば経路を生成する。

【0030】
以上により、複雑環境下であっても環境に適合させ、目標地点への経路生成を実現できる。
【実施例】
【0031】
地図画像上の経路探索を実施した。自動車から徒歩での移動を想定した場合の経路探索の結果を図3に示す。自動車は走行できる道幅が限られているため、分岐確率(pa, pb, pc)=(0.3, 0.6, 0.1)とした。その後、中間地点にて、自動車を降車し徒歩に変わるため、分岐確率(pa, pb, pc)=(0, 0, 1)とした。
【実施例】
【0032】
次に、高低差を考慮して探索に使用するリソースを制御した場合の経路探索の結果を図4に示す。高低差を有する地点を超えて経路探索を行う場合、消費リソース量をΔR=Mx1y1-Nx2y2+1と設定した。ここで、Mx1y1は現在地(x1, y1)の高さ、Nx2y2は経路を生成する地点(x2, y2)の高さである。
【実施例】
【0033】
最後に、遠回りのする場合の経路探索の結果を図5に示す。使用するリソースを制限し、探索ノードに収縮させる。設定したリソースの制限値は、収縮が発生する1350とした。
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4