最適経路探索装置
【課題】複数の経路から、先験的知識はないと仮定し、通行止めや進入禁止等を回避しつつ最短距離（時間）等の最適経路を選定する。
【解決手段】１回ターンのL字型経路から漸次的にLR型にターン回数を増やした経路を評価し、準最適経路を出力する手段、探索区域内で前進や予定方向のターンができない場合、パス・チェンジ・バックトラック方策を有する通行不可経路回避および循環経路回避をする手段、探索想定区域外や通行止めや渋滞等による動的通行不可経路変更区間には同じ経路の重複探索を防止し、不用な枝経路や不用になった循環経路を剪定する手段、直進優先方策を４方位の場合にはゴールの方向に応じた４種類の方位優先度調停法で探索を行う手段、ゴール方向に応じた優先度調停法に変更した方策で経路探索を行う手段、不用経路剪定と、最短等価距離経路判定と、最短探索時間判定と最短経路出力手段を有する。
【解決手段】１回ターンのL字型経路から漸次的にLR型にターン回数を増やした経路を評価し、準最適経路を出力する手段、探索区域内で前進や予定方向のターンができない場合、パス・チェンジ・バックトラック方策を有する通行不可経路回避および循環経路回避をする手段、探索想定区域外や通行止めや渋滞等による動的通行不可経路変更区間には同じ経路の重複探索を防止し、不用な枝経路や不用になった循環経路を剪定する手段、直進優先方策を４方位の場合にはゴールの方向に応じた４種類の方位優先度調停法で探索を行う手段、ゴール方向に応じた優先度調停法に変更した方策で経路探索を行う手段、不用経路剪定と、最短等価距離経路判定と、最短探索時間判定と最短経路出力手段を有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は最短距離もしくは最短時間等の最適な経路を選定して出力する経路再探索に関するものである。
【背景技術】
【０００２】
最適経路探索は古くから多くの研究や発明があり、試行錯誤無しで効率良く大域的最適解が得られカーナビ等に利用されているダイクストラ法が有名で、関連特許文献の中にもこれをベースにしたものがある。これを終点情報を用いるように改良したA*アルゴリズムも良く用いられている。古典的人工知能を利用したものには鉄道経路探索に利用計画のあったプロログのバックトラック法があり、これらを含む改良縦型探索法が、最近の非特許文献にある。また、Q学習法やPS学習法などの強化学習法を用いた迷路探索の研究も数多く行われており、さまざまな人工知能技術の評価問題としての側面もある。最近はA*や縦型探索法等を初期探索として未知の動的障害物にも対応できる強化学習法を統合する方法が注目されている。
【特許文献１】1) 浜口他（日立エンジニアリング株）：最適経路探索装置、特許出願２００４−１１１６６４、特許公開２００５−２９２０９４2)佐藤他（株富士通ソーシャルサイエンスラボラトリ）：最適経路探索方法、特許出願２００７−２７４３４、特許公開２００７−１７１２１１3)北岡他（株豊田中央研究所）：候補経路作成措置、方法、プログラム、交通シミュレーション装置、方法及びプログラム、経路探索装置、方法、及びプログラム、特許出願２００５−２１２６１４、特許公開２００７−３３０５７4)長谷山他：最適経路及び最適巡回経路探索方法、特許出願平１１−１５３５６８、特許公開２０００−１７２６６４5)西原他（日立電線株）：最適経路探索回路、特許出願平８−１９０８７１、特許公開平１０−３８５９５6)有田（オムロン株）：最適経路探索装置および最適経路の探索方法、特許出願平８−１８０２２１、特許公開平１０−２６９３２7)佐藤他（株富士通ソーシャルサイエンスラボラトリ）：最適経路探索方法、特許出願平８−１８１８２１、特許公開平１０−２６５３５8)川口他（大阪瓦斯株）：最適経路探索装置、特許出願平４−７１１３９、特許公開平５−２７４２９７9)白鳥（日産自動車株）：最適経路探索装置、特許出願平３−２６１１４２、特許公開平５−７３７９８10)大西（神鋼電機株）：移動ロボットの最適経路探索方法、特許出願平３−１０６１１１、特許公開平５−１０１０３５11)白附他（株東芝）：車両用経路探索装置、特許出願平３−２２７３５１、特許公開平５−６７１５１12)市川（アルパイン株）：経路探索方法、特許出願平４−１２３４６７、特許公開平５−３２３８６９13)市川（アルパイン株）：経路探索方法、特許出願平４−２７２７３８、特許公開平６−１２３６３６
【非特許文献１】1) 桶川・藤川・山田・志田：強化学習を用いた動的経路探索、電気学会産業計測制御研究会資料、IIC-01-32巻, 27-40号、pp.31-36, 2002 2)平岡・青柳：強化学習を用いた移動ロボットの障害物回避軌道の探索ーA*アルゴリズムと強化学習の統合ー、日本機械学会ロボテイックス・メカトロニクス講演会講演論文集、2P2-G05,20083)Y. Nakamura, S. Ohnishi, K. Ohkura and K. ueda: Instance-Based Reinforcement Learning for Robot Path Finding in Continuous Space, IEEE 0-7803-4053-1/97, 1997
【非特許文献２】１）K.Tanaka and M.Katoh: A Consideration on Ploblems of Two Points Passing and Moving Kinds of an Agent in a Course Search, Proceedings (5) of JSME Annual Conference, No.06-1, (2006), pp.477-478 (in Japanese) 2) Z. Liang, X. Jianmin and Z. Lingxiang: Designing Dynamic Path Guidance System Based on Electronic Maps by using Q-learning, Proc. of SPIE Vol. 5985 59855A pp.1-5, 2005
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明においては、始点から終点までに予め与えられた複数の経路の中から、先験的知識はないと仮定して、通行止めや進入禁止等の障害物を回避しつつ、最短距離もしくは最短時間等の最適な経路を選定して出力することが解決すべき課題である。
【課題を解決するための手段】
【０００４】
１）
位相的に最短時間経路であることが期待できる１回ターンのL字型もしくは逆L字型経路から漸次的にLR型（スタートからゴールに向かって近づく方向にターン方向を左右に変更していく方法）にターン回数を増やした経路を評価することによって、漸次同じターン回数毎に比較した準最適経路を記憶しつつ出力する手段
２）
探索区域内で前進や予定方向のターンができない場合（十字路以外のT字路や逆L字路や進入禁止路等）には、比較すべき最適経路候補から除外するパス（PS）方策か、それが尽きたら次善の方策として予定方向ターンができるまで進行方向を変えた枝を伸ばしていくチェンジ（CG）方策か、前進もターンもできない袋小路の場合や経路が交差する場合にはターンできるまでバックするバックトラック（BT）方策を有する通行不可経路回避機能および循環経路回避する手段
３）
探索想定区域外や通行止めや渋滞等による動的通行不可経路変更区間には通行可区域とは異なる初期マーキングを行ったQijtraテーブル(QT)を準備し、前項の通過経路にもQijtraに異なるAVマークを記入していくことによって、同じ経路の重複探索を防止する機能を有し、バックトラックした場合にはQijtraに異なるBTマークを記入して不用な枝経路を剪定し、経路が交差する場合には不用になった循環経路を剪定する手段
４） 以上の手段を有する従来と同様の直進優先方策を４方位の場合にはゴールの方向に応じた４種類の方位優先度調停法（例：ゴールが１２もしくは２１方向なら１２３４、２１４３、１２４３、２１３４の順）で探索を行う手段
５） 方位優先度に応じて定まるゴールに近づく方向のターン優先方策（例：１２３４ならLRRL）や行動選択確率可変方策なども同様に方位優先度調停法と組み合わせ、ゴール方向に応じた優先度調停法に変更した方策で経路探索を行う手段
６） 以上の手段を実施するための、ケース切替と、不用経路剪定と、それらの経路と探索時間記憶と、記憶した経路の中から等価進行距離の最も短い経路を選定する最短等価距離経路判定と、複数の経路の進行距離が等しい場合には剪定した経路探索も含めて探索時間の最も短い経路を選定する最短探索時間判定と最短経路出力手段
【発明の効果】
【０００５】
１）予め与えられた経路情報（各交差点での右左折直進の可否）に対して、予め設定された最適経路を、試行錯誤法では無く、位相的に最適経路が期待でき漸次的に複雑化していくアルゴリズムなので、所要時間が短縮できる。
２）重複経路や循環経路を無くすことができる。
３）複雑な迷路状経路や動的経路の場合には移動エージェントによる強化学習アルゴリズムに繋ぐことができる。
4)
探索経路が振動する場合にも、方位優先方策の変更とターン優先方策の変更によって、安定に収束する解を見出す確率が増える。
【発明を実施するための最良の形態】
【０００６】
１）経路情報（各交差点での右左折直進の可否）がビジュアルに入力し易い（通行止め設定区間、一方通行区間、壁等）ツールを備えていること
２）探索結果の判りやすい表示機能（アニメ等）を備えていること
【実施例】
【０００７】
1) 仮定
前提仮定
移動エージェントによる未知環境の試行錯誤探索では無く、監視エージェントによる、経路の位相および各交差点間の 距離が既知環境での計算探索である。
第１ステップ仮定
完全格子状経路
スタートからゴールまでL型経路のみで可到達である。
第２ステップ仮定
–スタートからゴールまでL型経路のみでは可到達ではないが、左右方向へのT字路L字路回避が２回までで、L型経路で可到達になる。経路 途中の障害物は考えない。
２）区域：縦４、横４
3)
位相座標：探索エリアを格子点に区分する２次元整数座標
交差点座標と経路番号：(i,j),i=1-5,j=1-5
(is,js)=開始座標=(2,2), (ie,je)=終端座標=(5,1)
交差点が無い位相交点には特殊記号を入れる。
方位と座標：北東の角に座標原点をとり、ｘ座標は南に、ｙ座標は西に伸びる座標の地図。
始点からみた終点の方向：南東の場合
4)
絶対座標：位相座標に対応する実数値座標
5)
行動テーブル（Q-table)
各位相交差点毎に次のQテーブルで表現される４方５行動で定義する。
Q(i,j,t,r,a)=as
i:横経路番号、j：縦経路番号、t:実行ステップ数、r:仮想方位、a:アクション種別、s:アクション実行状態
仮想方位：r=1:南、r=2:東、r=3:北、r=4:西
行動種別：a=0:停止、a=1:前進、a=2:左折、a=3:右折、a=4:後退
行動実行状態：as=0:許容できる行動、as=1:実行済み、as=9999:許容できない行動
一時変数：(k,s)は(i,j)の次ステップ変数
6)L空間構成法
探索経路はx座標を変えずにｙ座標のみ変える直進経路から最初に左折する特徴抽出点を符番し, 通過交差点を記述していくと、残りは自動的に決まるまでに1点の特徴点が必要ならそれらを成分とした2次元空間としてL2-空間が,2点の特徴点が必要ならそれらを成分として並べた4次元空間としてL4-空間が得られる。このサイズでは
L6-空間で終了する。
7)
シミュレーション結果
初期設定
仮想タウンと通行止め区間と始点(is,js) = (2,2),終点 (ie,je) = (5,1)
ルートサンプル：
５種類の各行動毎に方位順は４通り、計２０通り中５通りをサンプル
表１ 直進行動優先（仮想方位優先順＝南東北西）
表２ 直進行動優先 （仮想方位優先順＝東南西北）
表３ RLLR行動優先 （仮想方位優先順＝東南西北）
注）第３試行（直進優先の仮想方位優先順＝東南北西）、第４試行（LRRL行動優先の仮想方位優先＝南東北西）は
表２に示した第２試行と同様に探索経路が振動してタイムアウト（２０回）となったため記載を省略した。
振動せずに収束した結果では４ステップでゴールに達する表３の結果が最速であった。
【産業上の利用可能性】
【０００８】
１）カーナビ装置における経路探索機能
２）鉄道経路探索ソフト
３）道路経路探索ソフト
４）ファクトリーオートメーション用AGV等がレイアウト変更後の最適経路計算を行うソフト
【図面の簡単な説明】
【０００９】
【図１】発明の構成図
【図２】発明の第１の機能の経路分類の例示図 （機能１における開始点から終端点まで4回ターンL4と５回ターンL5のL空間を例示表現した図）
【図３】発明の第２の通行不可経路回避機能および循環経路回避機能の例示図 （機能２におけるパス方策による通行不可経路回避機能のL4とL5の例示図）
【図４】発明の第２の通行不可経路回避機能および循環経路回避機能の例示図 （機能２におけるチェンジ方策による通行不可経路回避機能のL4とL5の例示図）
【図５】発明の第２の通行不可経路回避機能および循環経路回避機能の例示図 （機能２におけるバックトラック方策および バックトラック&実行カット方策による通行不可経路回避機能の例示図）
【図６】発明の第３の不用経路剪定機能の例示図 （機能３における不用枝経路剪定方策と不用循環経路剪定方策による不用経路剪定機能の例示図）
【図７】発明の第３の不用経路剪定機能の例示図 （機能３におけるバックトラック&実行カット優先度調停法CG戦略による２段階Q迷路探索の例示図）
【図８】発明の第４の最短距離経路選定および最短探索時間経路選定機能の例示図 （直進優先ルールの例示図である図３の例と同じ環境で、ターン優先ルールにした場合の方が進行位相距離は同じでも探索ステップ数が小さくなるケースの例示図）
【技術分野】
【０００１】
本発明は最短距離もしくは最短時間等の最適な経路を選定して出力する経路再探索に関するものである。
【背景技術】
【０００２】
最適経路探索は古くから多くの研究や発明があり、試行錯誤無しで効率良く大域的最適解が得られカーナビ等に利用されているダイクストラ法が有名で、関連特許文献の中にもこれをベースにしたものがある。これを終点情報を用いるように改良したA*アルゴリズムも良く用いられている。古典的人工知能を利用したものには鉄道経路探索に利用計画のあったプロログのバックトラック法があり、これらを含む改良縦型探索法が、最近の非特許文献にある。また、Q学習法やPS学習法などの強化学習法を用いた迷路探索の研究も数多く行われており、さまざまな人工知能技術の評価問題としての側面もある。最近はA*や縦型探索法等を初期探索として未知の動的障害物にも対応できる強化学習法を統合する方法が注目されている。
【特許文献１】1) 浜口他（日立エンジニアリング株）：最適経路探索装置、特許出願２００４−１１１６６４、特許公開２００５−２９２０９４2)佐藤他（株富士通ソーシャルサイエンスラボラトリ）：最適経路探索方法、特許出願２００７−２７４３４、特許公開２００７−１７１２１１3)北岡他（株豊田中央研究所）：候補経路作成措置、方法、プログラム、交通シミュレーション装置、方法及びプログラム、経路探索装置、方法、及びプログラム、特許出願２００５−２１２６１４、特許公開２００７−３３０５７4)長谷山他：最適経路及び最適巡回経路探索方法、特許出願平１１−１５３５６８、特許公開２０００−１７２６６４5)西原他（日立電線株）：最適経路探索回路、特許出願平８−１９０８７１、特許公開平１０−３８５９５6)有田（オムロン株）：最適経路探索装置および最適経路の探索方法、特許出願平８−１８０２２１、特許公開平１０−２６９３２7)佐藤他（株富士通ソーシャルサイエンスラボラトリ）：最適経路探索方法、特許出願平８−１８１８２１、特許公開平１０−２６５３５8)川口他（大阪瓦斯株）：最適経路探索装置、特許出願平４−７１１３９、特許公開平５−２７４２９７9)白鳥（日産自動車株）：最適経路探索装置、特許出願平３−２６１１４２、特許公開平５−７３７９８10)大西（神鋼電機株）：移動ロボットの最適経路探索方法、特許出願平３−１０６１１１、特許公開平５−１０１０３５11)白附他（株東芝）：車両用経路探索装置、特許出願平３−２２７３５１、特許公開平５−６７１５１12)市川（アルパイン株）：経路探索方法、特許出願平４−１２３４６７、特許公開平５−３２３８６９13)市川（アルパイン株）：経路探索方法、特許出願平４−２７２７３８、特許公開平６−１２３６３６
【非特許文献１】1) 桶川・藤川・山田・志田：強化学習を用いた動的経路探索、電気学会産業計測制御研究会資料、IIC-01-32巻, 27-40号、pp.31-36, 2002 2)平岡・青柳：強化学習を用いた移動ロボットの障害物回避軌道の探索ーA*アルゴリズムと強化学習の統合ー、日本機械学会ロボテイックス・メカトロニクス講演会講演論文集、2P2-G05,20083)Y. Nakamura, S. Ohnishi, K. Ohkura and K. ueda: Instance-Based Reinforcement Learning for Robot Path Finding in Continuous Space, IEEE 0-7803-4053-1/97, 1997
【非特許文献２】１）K.Tanaka and M.Katoh: A Consideration on Ploblems of Two Points Passing and Moving Kinds of an Agent in a Course Search, Proceedings (5) of JSME Annual Conference, No.06-1, (2006), pp.477-478 (in Japanese) 2) Z. Liang, X. Jianmin and Z. Lingxiang: Designing Dynamic Path Guidance System Based on Electronic Maps by using Q-learning, Proc. of SPIE Vol. 5985 59855A pp.1-5, 2005
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明においては、始点から終点までに予め与えられた複数の経路の中から、先験的知識はないと仮定して、通行止めや進入禁止等の障害物を回避しつつ、最短距離もしくは最短時間等の最適な経路を選定して出力することが解決すべき課題である。
【課題を解決するための手段】
【０００４】
１）
位相的に最短時間経路であることが期待できる１回ターンのL字型もしくは逆L字型経路から漸次的にLR型（スタートからゴールに向かって近づく方向にターン方向を左右に変更していく方法）にターン回数を増やした経路を評価することによって、漸次同じターン回数毎に比較した準最適経路を記憶しつつ出力する手段
２）
探索区域内で前進や予定方向のターンができない場合（十字路以外のT字路や逆L字路や進入禁止路等）には、比較すべき最適経路候補から除外するパス（PS）方策か、それが尽きたら次善の方策として予定方向ターンができるまで進行方向を変えた枝を伸ばしていくチェンジ（CG）方策か、前進もターンもできない袋小路の場合や経路が交差する場合にはターンできるまでバックするバックトラック（BT）方策を有する通行不可経路回避機能および循環経路回避する手段
３）
探索想定区域外や通行止めや渋滞等による動的通行不可経路変更区間には通行可区域とは異なる初期マーキングを行ったQijtraテーブル(QT)を準備し、前項の通過経路にもQijtraに異なるAVマークを記入していくことによって、同じ経路の重複探索を防止する機能を有し、バックトラックした場合にはQijtraに異なるBTマークを記入して不用な枝経路を剪定し、経路が交差する場合には不用になった循環経路を剪定する手段
４） 以上の手段を有する従来と同様の直進優先方策を４方位の場合にはゴールの方向に応じた４種類の方位優先度調停法（例：ゴールが１２もしくは２１方向なら１２３４、２１４３、１２４３、２１３４の順）で探索を行う手段
５） 方位優先度に応じて定まるゴールに近づく方向のターン優先方策（例：１２３４ならLRRL）や行動選択確率可変方策なども同様に方位優先度調停法と組み合わせ、ゴール方向に応じた優先度調停法に変更した方策で経路探索を行う手段
６） 以上の手段を実施するための、ケース切替と、不用経路剪定と、それらの経路と探索時間記憶と、記憶した経路の中から等価進行距離の最も短い経路を選定する最短等価距離経路判定と、複数の経路の進行距離が等しい場合には剪定した経路探索も含めて探索時間の最も短い経路を選定する最短探索時間判定と最短経路出力手段
【発明の効果】
【０００５】
１）予め与えられた経路情報（各交差点での右左折直進の可否）に対して、予め設定された最適経路を、試行錯誤法では無く、位相的に最適経路が期待でき漸次的に複雑化していくアルゴリズムなので、所要時間が短縮できる。
２）重複経路や循環経路を無くすことができる。
３）複雑な迷路状経路や動的経路の場合には移動エージェントによる強化学習アルゴリズムに繋ぐことができる。
4)
探索経路が振動する場合にも、方位優先方策の変更とターン優先方策の変更によって、安定に収束する解を見出す確率が増える。
【発明を実施するための最良の形態】
【０００６】
１）経路情報（各交差点での右左折直進の可否）がビジュアルに入力し易い（通行止め設定区間、一方通行区間、壁等）ツールを備えていること
２）探索結果の判りやすい表示機能（アニメ等）を備えていること
【実施例】
【０００７】
1) 仮定
前提仮定
移動エージェントによる未知環境の試行錯誤探索では無く、監視エージェントによる、経路の位相および各交差点間の 距離が既知環境での計算探索である。
第１ステップ仮定
完全格子状経路
スタートからゴールまでL型経路のみで可到達である。
第２ステップ仮定
–スタートからゴールまでL型経路のみでは可到達ではないが、左右方向へのT字路L字路回避が２回までで、L型経路で可到達になる。経路 途中の障害物は考えない。
２）区域：縦４、横４
3)
位相座標：探索エリアを格子点に区分する２次元整数座標
交差点座標と経路番号：(i,j),i=1-5,j=1-5
(is,js)=開始座標=(2,2), (ie,je)=終端座標=(5,1)
交差点が無い位相交点には特殊記号を入れる。
方位と座標：北東の角に座標原点をとり、ｘ座標は南に、ｙ座標は西に伸びる座標の地図。
始点からみた終点の方向：南東の場合
4)
絶対座標：位相座標に対応する実数値座標
5)
行動テーブル（Q-table)
各位相交差点毎に次のQテーブルで表現される４方５行動で定義する。
Q(i,j,t,r,a)=as
i:横経路番号、j：縦経路番号、t:実行ステップ数、r:仮想方位、a:アクション種別、s:アクション実行状態
仮想方位：r=1:南、r=2:東、r=3:北、r=4:西
行動種別：a=0:停止、a=1:前進、a=2:左折、a=3:右折、a=4:後退
行動実行状態：as=0:許容できる行動、as=1:実行済み、as=9999:許容できない行動
一時変数：(k,s)は(i,j)の次ステップ変数
6)L空間構成法
探索経路はx座標を変えずにｙ座標のみ変える直進経路から最初に左折する特徴抽出点を符番し, 通過交差点を記述していくと、残りは自動的に決まるまでに1点の特徴点が必要ならそれらを成分とした2次元空間としてL2-空間が,2点の特徴点が必要ならそれらを成分として並べた4次元空間としてL4-空間が得られる。このサイズでは
L6-空間で終了する。
7)
シミュレーション結果
初期設定
仮想タウンと通行止め区間と始点(is,js) = (2,2),終点 (ie,je) = (5,1)
ルートサンプル：
５種類の各行動毎に方位順は４通り、計２０通り中５通りをサンプル
表１ 直進行動優先（仮想方位優先順＝南東北西）
表２ 直進行動優先 （仮想方位優先順＝東南西北）
表３ RLLR行動優先 （仮想方位優先順＝東南西北）
注）第３試行（直進優先の仮想方位優先順＝東南北西）、第４試行（LRRL行動優先の仮想方位優先＝南東北西）は
表２に示した第２試行と同様に探索経路が振動してタイムアウト（２０回）となったため記載を省略した。
振動せずに収束した結果では４ステップでゴールに達する表３の結果が最速であった。
【産業上の利用可能性】
【０００８】
１）カーナビ装置における経路探索機能
２）鉄道経路探索ソフト
３）道路経路探索ソフト
４）ファクトリーオートメーション用AGV等がレイアウト変更後の最適経路計算を行うソフト
【図面の簡単な説明】
【０００９】
【図１】発明の構成図
【図２】発明の第１の機能の経路分類の例示図 （機能１における開始点から終端点まで4回ターンL4と５回ターンL5のL空間を例示表現した図）
【図３】発明の第２の通行不可経路回避機能および循環経路回避機能の例示図 （機能２におけるパス方策による通行不可経路回避機能のL4とL5の例示図）
【図４】発明の第２の通行不可経路回避機能および循環経路回避機能の例示図 （機能２におけるチェンジ方策による通行不可経路回避機能のL4とL5の例示図）
【図５】発明の第２の通行不可経路回避機能および循環経路回避機能の例示図 （機能２におけるバックトラック方策および バックトラック&実行カット方策による通行不可経路回避機能の例示図）
【図６】発明の第３の不用経路剪定機能の例示図 （機能３における不用枝経路剪定方策と不用循環経路剪定方策による不用経路剪定機能の例示図）
【図７】発明の第３の不用経路剪定機能の例示図 （機能３におけるバックトラック&実行カット優先度調停法CG戦略による２段階Q迷路探索の例示図）
【図８】発明の第４の最短距離経路選定および最短探索時間経路選定機能の例示図 （直進優先ルールの例示図である図３の例と同じ環境で、ターン優先ルールにした場合の方が進行位相距離は同じでも探索ステップ数が小さくなるケースの例示図）
【特許請求の範囲】
【請求項１】
始点から終点までに予め与えられた複数の経路の中から、先験的知識はないと仮定して、通行止めや進入禁止等の障害物を回避しつつ、最短距離もしくは最短時間等の最適な経路を選定して出力する最適経路探索問題において、
１）
位相的に最短時間経路であることが期待できる１回ターンのL字型もしくは逆L字型経路から漸次的にLR型（スタートからゴールに向かって近づく方向にターン方向を左右に変更していく方法）にターン回数を増やした経路を評価することによって、漸次同じターン回数毎に比較した準最適経路を記憶しつつ出力する機能
２）
探索区域内で前進や予定方向のターンができない場合（十字路以外のT字路や逆L字路や進入禁止路等）には、比較すべき最適経路候補から除外するパス（PS）方策か、それが尽きたら次善の方策として予定方向ターンができるまで進行方向を変えた枝を伸ばしていくチェンジ（CG）方策か、前進もターンもできない袋小路の場合や経路が交差する場合にはターンできるまでバックするバックトラック（BT）方策を有する通行不可経路回避機能および循環経路回避機能
３）
探索想定区域外や通行止めや渋滞等による動的通行不可経路変更区間には通行可区域とは異なる初期マーキングを行ったQijtraテーブル(QT)を準備し、前項の通過経路にもQijtraに異なるAVマークを記入していくことによって、同じ経路の重複探索を防止する機能を有し、バックトラックした場合にはQijtraに異なるBTマークを記入して不用な枝経路を剪定し、経路が交差する場合には不用になった循環経路を剪定する機能
以上の機能を有する従来と同様の直進優先方策を４方位の場合にはゴールの方向に応じた４種類の方位優先度調停法で探索を行う以外に、方位優先度に応じて定まるゴールに近づく方向のターン優先方策や行動選択確率可変方策なども同様に方位優先度調停法と組み合わせ、ゴール方向に応じた優先度調停法に変更した方策で経路探索を行うケース切替部と、不用経路剪定部と、それらの経路と探索時間記憶部と、記憶した経路の中から等価進行距離の最も短い経路を選定する最短等価距離経路判定部と、複数の経路の進行距離が等しい場合には剪定した経路探索も含めて探索時間の最も短い経路を選定する最短探索時間判定部と最短経路出力部を有することを特徴とする最適経路探索装置
【請求項１】
始点から終点までに予め与えられた複数の経路の中から、先験的知識はないと仮定して、通行止めや進入禁止等の障害物を回避しつつ、最短距離もしくは最短時間等の最適な経路を選定して出力する最適経路探索問題において、
１）
位相的に最短時間経路であることが期待できる１回ターンのL字型もしくは逆L字型経路から漸次的にLR型（スタートからゴールに向かって近づく方向にターン方向を左右に変更していく方法）にターン回数を増やした経路を評価することによって、漸次同じターン回数毎に比較した準最適経路を記憶しつつ出力する機能
２）
探索区域内で前進や予定方向のターンができない場合（十字路以外のT字路や逆L字路や進入禁止路等）には、比較すべき最適経路候補から除外するパス（PS）方策か、それが尽きたら次善の方策として予定方向ターンができるまで進行方向を変えた枝を伸ばしていくチェンジ（CG）方策か、前進もターンもできない袋小路の場合や経路が交差する場合にはターンできるまでバックするバックトラック（BT）方策を有する通行不可経路回避機能および循環経路回避機能
３）
探索想定区域外や通行止めや渋滞等による動的通行不可経路変更区間には通行可区域とは異なる初期マーキングを行ったQijtraテーブル(QT)を準備し、前項の通過経路にもQijtraに異なるAVマークを記入していくことによって、同じ経路の重複探索を防止する機能を有し、バックトラックした場合にはQijtraに異なるBTマークを記入して不用な枝経路を剪定し、経路が交差する場合には不用になった循環経路を剪定する機能
以上の機能を有する従来と同様の直進優先方策を４方位の場合にはゴールの方向に応じた４種類の方位優先度調停法で探索を行う以外に、方位優先度に応じて定まるゴールに近づく方向のターン優先方策や行動選択確率可変方策なども同様に方位優先度調停法と組み合わせ、ゴール方向に応じた優先度調停法に変更した方策で経路探索を行うケース切替部と、不用経路剪定部と、それらの経路と探索時間記憶部と、記憶した経路の中から等価進行距離の最も短い経路を選定する最短等価距離経路判定部と、複数の経路の進行距離が等しい場合には剪定した経路探索も含めて探索時間の最も短い経路を選定する最短探索時間判定部と最短経路出力部を有することを特徴とする最適経路探索装置
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１１−４７６５２（Ｐ２０１１−４７６５２Ａ）
【公開日】平成２３年３月１０日（２０１１．３．１０）
【国際特許分類】
【出願番号】特願２００９−１９３７６２（Ｐ２００９−１９３７６２）
【出願日】平成２１年８月２５日（２００９．８．２５）
【出願人】（７０９０００４８０）
【Ｆターム（参考）】
【公開日】平成２３年３月１０日（２０１１．３．１０）
【国際特許分類】
【出願日】平成２１年８月２５日（２００９．８．２５）
【出願人】（７０９０００４８０）
【Ｆターム（参考）】
[ Back to top ]