特許

J-GLOBAL ID：200903000639367288

経路探索方法

発明者： 溝口 文雄
出願人/特許権者： 溝口 文雄 ,  アルパイン株式会社
代理人 (1件)： 斉藤 千幹
公報種別：公開公報
出願番号（国際出願番号）：特願平9-340959
公開番号（公開出願番号）：特開平11-173863
出願日： 1997年12月11日
公開日（公表日）： 1999年07月02日
要約：

【要約】【課題】 短い時間で最適経路あるいはそれに近い経路を探索する。【解決手段】 (1) 出発地からノードnを経由して目的地に至る場合、ノードnの評価関数f(n)を、出発地からノードnまでのコストg(n)、ノードnから目的地までの最小予測コストh(n)、重み係数ε(≧0)を用いて次式f(n)=g(n)+(1+ε)×h(n)で表現し、(2) 展開可能性のあるノードの集合をOPEN(初期値は出発地)とし、集合OPENの先頭ノードを取り出してA*アルゴリズムと同様のアルゴリズムを適用して新たな集合OPENを生成し、(3) 該新たな集合OPENを構成する各ノードの評価値のうち最小の評価値fを求め、(4) 評価値が(1+δ)×f以下のノードであって(δ≧0)、hが最小のノードを集合OPENより求め、(5) 該ノードを集合OPENの先頭ノードとして再度上記処理を繰り返し出発地から目的地までの経路を探索する。

請求項（抜粋）：

第1の地点から第2の地点までの経路を探索する経路探索方法において、出発地からノード(交差点)nを経由して目的地に至る場合、ノードnの評価関数f(n)を、出発地からノードnまでのコストg(n)、ノードnから目的地に到達するまでに必要であると予測される最小コストh(n)、重み係数ε(≧0)を用いて次式f(n)=g(n)+(1+ε)×h(n)で表現し、又、ノードnからノードmに至るコストをcost(n,m)、あるノードに接続する全ての子ノードを求める処理を展開すると表現する時、展開可能性のあるノードの集合をOPEN、既に展開済みのノードの集合をCLOSEDとし、初期時、集合OPENを構成するノードを出発地とし、集合CLOSEDを空集合とし、集合OPENの先頭ノードを取り出してnとし、ノードnが目的地であるかチェックし、目的地でなければ、nを展開して子ノードを全て求め、ノードnを集合CLOSEDに入れ、子ノードmについて、評価値を次式g(n)+cost(n,m)+(1+ε)×h(m)により計算すると共に、子ノードmが集合OPENあるいは集合CLOSEDを構成するかチェックし、子ノードが集合OPEN、CLOSEDのいずれをも構成してなければ、?@子ノードmから親ノードnへのポインタと、?A前記評価値と、?B子ノードmから目的地までの最小予測コストh(m)をそれぞれ関連付けて該子ノードmを集合OPENに入れ、子ノードmが集合OPENを構成するノードであれば、集合OPENの該ノードに関連付けられている第1の評価値と前記計算した第2の評価値を比較し、第2の評価値が小さければ、集合OPENの前記ノードの評価値を第2の評価値で更新し、かつ、親ノードがノードnとなるようにポインタを更新し、子ノードmが集合CLOSEDを構成するノードであれば、集合CLOSEDの該ノードに関連付けられている第1の評価値と前記計算した第2の評価値を比較し、第2の評価値が小さければ、集合CLOSEDにおけるノードの親ノードがノードnとなるようにポインタを更新し、かつ、該ノードの評価値を第2の評価値で更新して集合CLOSEDより集合OPENに戻し、しかる後、集合OPENを構成する各ノードに関連付けられている評価値であって、最小の評価値fを求め、評価値が(1+δ)×f以下のノードであって(δ≧0)、最小予測コストが最小のノードを求め、該ノードを集合OPENの先頭ノードnとして、上記処理を繰り返して出発地から目的地までの経路を探索する、ことを特徴とする経路探索方法。

IPC (4件)：

G01C 21/00 ,  G06F 17/00 ,  G08G 1/0969 ,  G09B 29/10

FI (4件)：

G01C 21/00 G ,  G08G 1/0969 ,  G09B 29/10 A ,  G06F 15/20 Z