特許
J-GLOBAL ID:200903041574893651
時間制限付き経路探索方法
発明者:
出願人/特許権者:
,
代理人 (1件):
斉藤 千幹
公報種別:公開公報
出願番号(国際出願番号):特願平10-312185
公開番号(公開出願番号):特開2000-136939
出願日: 1998年11月02日
公開日(公表日): 2000年05月16日
要約:
【要約】【課題】 制限時間内に最適経路あるいは準最適経路を探索する。【解決手段】 第1の地点(Start)からノードnを経由して第2の地点(Goal)に至る場合、経路ユニット4はノードnにおける評価値f(n)を次式f(n)=g(n)+ε・h(n)で表現し、対象ノードのうち評価値fが最小のノードを求め、該ノードを対象ノードから除外すると共に、該ノードに接続するノードを対象ノードに加え、以後、順次対象ノードのうち評価値が最小のノードを求めて第1の地点から第2の地点までの経路を探索する。かかる経路探索において探索時間が制限されている場合、経路ユニット4は経路探索中に現在の重み係数εを用いて制限時間内に探索が終了するか判定し、判定結果に基づいて重み係数εの値を増減し、制限時間内に探索を終了する。
請求項(抜粋):
第1の地点からノード(交差点)nを経由して第2の地点に至る場合、ノードnにおける評価値f(n)を、第1の地点からノードnまでのコストg(n)、ノードnから第2の地点に到達するまでに必要であると予測される最小コストh(n)、重み係数ε(≧1)を用いて次式f(n)=g(n)+ε・h(n)で表現し、対象ノードのうち評価値が最小のノードを求め、該ノードを対象ノードから除外すると共に、該ノードに接続するノードを対象ノードに加え、順次対象ノードのうち評価値が最小のノードを求めて第1の地点から第2の地点までの経路を探索する経路探索方法において、現在の重み係数εを用いて与えられた制限時間内に経路探索が終了するか経路探索中に判定し、判定結果に基づいて重み係数εの値を変更する、ことを特徴とする時間制限付き経路探索方法。
IPC (4件):
G01C 21/00
, G09B 29/00
, G09B 29/10
, G08G 1/0969
FI (4件):
G01C 21/00 G
, G09B 29/00 C
, G09B 29/10 A
, G08G 1/0969
Fターム (19件):
2C032HC08
, 2C032HD07
, 2C032HD16
, 2F029AA02
, 2F029AB01
, 2F029AB07
, 2F029AB09
, 2F029AB13
, 2F029AC02
, 2F029AC04
, 2F029AC08
, 2F029AC09
, 2F029AC14
, 5H180AA01
, 5H180BB13
, 5H180FF04
, 5H180FF05
, 5H180FF22
, 5H180FF27
前のページに戻る