JPH07225612A - 時間軸を探索空間に取り入れた経路探索方法，及び装置 - Google Patents

Abstract

(57)【要約】 【目的】 本発明は、移動ロボットの経路探索方法，及
び装置に関し、時間的に変化する事象の知識を経路探索
に取り込み、正確に到達の可能性を判断し、コスト最小
の経路を探索する。 【構成】 地図や，移動物体の情報が記述されていて、
移動ロボットの経路探索に使用される２次元，又は、３
次元の探索空間軸に、時間軸を追加して、時間的に変化
する事象を、空間軸での事象に置き換えて処理する。２
次元空間で時間によって存在位置が変化しない物体を、
時間軸を含む３次元空間上で、壁や柱に疑似化する。
又、決まった時間に正確に生起する事象、例えば、出入
り口，信号機付交差点を、上記３次元空間では、窓に疑
似化する。又、電車のように、時刻表に従って、定時運
転される移動手段を、上記３次元空間では、トンネルに
疑似化する。又、動く歩道のように、任意時間に利用可
能な一定速度で動く移動手段を、上記３次元空間では、
移動方向に制限のついた廊下，又は、トンネルに疑似化
する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、移動ロボットの経路探
索方法，及び装置に関する。現在実用化されている移動
ロボットには、工場内の部品搬送車のように、よく管理
された環境の中で、床に引いたラインなどでガイドされ
た一定のコースを一定のスケジュールで自動運転される
ものと、人の行けない悪環境の中をリモートコントロー
ルされて移動するものと、自律的に移動するものとがあ
り、本発明は、上記自律的に移動する移動ロボットでの
経路探索方法，及び装置に関するものである。

【０００２】

【従来の技術】図１４は、従来の移動ロボットの構成例
を示した図であり、太枠内は、全体構成を示し、点線の
枠内は、経路生成部の構成例を示している。

【０００３】移動ロボットには、環境の状況を観測する
ためのカメラや, 超音波センサ, タッチセンサ等のセン
サ類 13a,13bが搭載されている。リモートコントロール
を行う場合には、人間が、それらのセンサ類 13a,13bか
らの情報を基に、移動ロボットを動かす。

【０００４】上記リモートコントロールではなく、自律
的な移動を行わせる場合には、予め、与えておいた移動
ロボットが動き回る環境の地図を基に、経路生成部 14
において、経路計画が作成され、それに基づいた移動動
作が実行される。具体的には, 上記経路生成部 14 にお
いて決定された経路情報に基づいて、中央制御部(10)
が、駆動制御部 11 を起動し、駆動装置 12 によって、
上記決定された経路を移動する。

【０００５】該経路計画の作成方法は、次の様に行われ
る。即ち、壁や, 動かせない物体などの障害物の存在
や、その場所を単位距離通過するために要する時間等の
情報をコストに変換して記述した環境地図｛格子, 立方
格子単位に、コストが記述されたコスト地図｝を元に、
幾つかの経路の所要時間の合計等のコストを計算して、
到達の可能性等の制約条件を満たす様々な経路を見つけ
て、その中からコストが最小の経路を決定する。実際に
動き回るときには、地図に無い障害物や、人間や他の移
動ロボット等の移動物体が存在しており、それらの、上
記経路計画にないものに対する衝突回避は、中央制御部
10 での動作は例外処理として行われ、上記経路計画に
沿って移動動作とは別個にきめられている衝突回避動
作、例えば、迂回動作が実行される。上記迂回動作が不
可能な場合には、移動開始点に戻って、別の経路を決定
して、移動を行うことになる。

【０００６】

【発明が解決しようとする課題】上記のように、従来
は、経路計画に際して、移動ロボットが動き回る環境の
地図中の事象が、時間的に不変で、且つ、得られる情報
に欠落が無く、常に、正確であることが条件になってい
る。

【０００７】従って、定時に開閉する出入り口のドア
や, 一定速度で動く移動物体等の時間的に変化する事象
の知識を、上記経路計画のとき、具体的には、コスト地
図に基づいて、経路の候補を見つけて、その経路の中で
コストが最小の経路を決定するとき、上記経路計画に取
り込むことがでいない問題があった。従って、それらの
時間変化の事象が存在する場合、到達の可能性の判断を
誤ったり、コストを本当の最小にもっていくことができ
ない等の不都合が生じるという問題があった。

【０００８】又、前述のように、衝突回避行動は、設定
経路上の移動とは別個 (即ち、例外処理) に行われるの
で、その２種類の行動間の調整動作が複雑になるという
問題があった。例えば、衝突回避動作後の経路復帰を考
えると、新たなセンシングによる自移動ロボットの現在
位置，方向の認識と、目標経路への復帰の為の新たな経
路設定が必要であるという問題があった。

【０００９】ここで、動きの予測が十分正確に行える移
動物体への対応について、それらを経路計画に組み入れ
ることができれば、単なる例外処理としての衝突回避に
よる移動動作よりも、効率的な移動ができる筈である。

【００１０】本発明は上記従来の欠点に鑑み、移動ロボ
ットの経路探索方法，及び装置において、時間的に変化
する事象の知識を経路探索に取り込み、正確に到達の可
能性を判断し、コスト最小の経路を探索する経路探索方
法，及び装置を提供することを目的とするものである。

【００１１】

【課題を解決するための手段】図１は、本発明の原理構
成図である。上記の問題点は下記のように構成された時
間軸を探索空間に取り入れた経路探索方法，及び装置に
よって解決される。

【００１２】地図や，移動物体の情報が記述されてい
て、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索方法であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸
を追加して、時間的に変化する事象を、空間軸での事象
に置き換えて処理するように構成する。

【００１３】即ち、図１において、データベース部 1に
は、地図や, 移動物体のタイムテーブル, 移動物体の運
動法則等のある程度の固定的な知識を格納し、シミュレ
ーション部 2は、上記データベース 1からの情報を元
に、各々の事象毎にシミュレーションを行う。具体的に
は、移動ロボットが通過する際の、上記移動物体のタイ
ムテーブル, 移動物体の運動法則による確率分布を記述
した格子, 立方格子地図を生成する。このとき、移動ロ
ボット環境中に生起する事象間の相互作用は、処理を複
雑にするので考慮に入れない。又、正確な予測ができな
い場合には、現象の生起確率の分布の形式で予測を行
う。コスト計算部 3では、各々の事象毎の影響を総合し
て、探索空間中でのコストを算出し、上記確率分布を記
述した格子,立方格子地図を、コストで記述した格子,
立方格子地図に変換する。

【００１４】経路探索部 4では、上記コストで記述した
格子, 立方格子地図に基づいて、通常の経路探索方法、
例えば、CAD の分野等において良く使用される迷路法等
を用いて、幾つかの経路の候補を見つけた後、コスト合
計が最小の経路を決定して、最適経路を出力する。

【００１５】

【作用】先ず、移動ロボットが動き回る環境中の全ての
事象についての完全な知識を持ち、移動物体の行動予測
が正確に行われる場合について、その作用を考察する。
時間的に変化のない事象を含む、探索空間の座標軸に、
時間の座標軸を追加した探索空間と、時間的に変化しな
い事象だけを含む、空間軸だけの探索空間とを比較する
と、経路探索に関しては、以下の点を除いて、同じ扱い
をすることができる。

【００１６】即ち、時間を逆行することができないこと
と、移動物体の移動速度には、最大限度があることか
ら、上記時間軸を含んだ探索空間では、経路設定の方向
に制限が付く。又、到達目標点は、目的地点と制限時間
との組み合わせで決定される。

【００１７】このようにして経路計画を行うことによ
り、移動物体との衝突回避行動を、時間的に変化しない
障害物中での経路計画と統一して処理することができ
る。この方法では、経路計画時に、衝突回避を組み込む
ことができるので、効率的な動きができ、衝突回避後に
経路計画の立て直しの必要がなくなるとう効果が得られ
る。

【００１８】然し、実際には、正確な未来の予測は不可
能である。そこで、本発明においては、それらの予測の
不確実さを、存在確率分布として扱う。上記事象の存在
確率と、その危険度等の影響を総合して、経路計画に用
いるコストを算出する。

【００１９】未来の予測に関して、一番困難な問題は、
上記環境中に生起する事象同士の相互作用である。該相
互作用の予測を行うことは、単独の予測を行うことと比
較すると、膨大な計算量を必要とするので、重大な影響
があるもの以外の相互作用は無視する。更に、移動ロボ
ットと環境中に生起する事象間の相互作用は、探索空間
の内容が、経路探索中に変化するという問題を引き起こ
す。

【００２０】そこで、本発明では、該経路探索の手法
は、上記探索空間の内容が固定されていることが前提と
なっているので、該探索空間の内容が変化する場合に
は、経路探索を実行することができない。今、想定して
いる環境においては、相互作用の働く方向は、移動ロボ
ットに対しては衝突の回避をしてくれる等、協力的であ
るとしてよい。つまり、移動ロボットと環境中に生起す
る事象間の相互作用を考慮しない場合、効率は悪くなる
が、危険ではない筈である。この点を考慮して、本発明
による経路探索方法，及び装置では、移動ロボットと環
境中に生起する事象間の相互作用は、考慮に入れない
で、経路探索を行うようにしたものである。

【００２１】

【実施例】以下本発明の実施例を図面によって詳述す
る。前述の図１は、本発明の原理構成図であり、図２〜
図１３は、本発明の一実施例を示した図であり、各事象
の、時間軸を含む探索空間での表現形態の例を示してお
り、図２は恒常的事象の場合の表現例を示し、図３は定
時変化事象の場合の表現例を示し、図４は、定時運転の
移動手段の場合の表現例を示し、図５は、任意時刻に利
用可能な定速度移動手段の場合の表現例を示し、図６
は、任意時刻に利用可能な定速度移動手段が多数ある場
合の表現例を示し、図７は、任意時刻に呼び出して利用
する定速度移動手段の表現例を示し、図８は、正確に予
測可能な移動物体（等速度運動の移動物体）の表現例を
示し、図９は、確率的に予測可能な移動物体（等速度運
動）の表現例を示し、図１０は、確率的に予測可能な移
動物体が分岐する場合の表現例を示し、図１１は，確率
的に予測可能な移動物体の分岐を、時間的に固定な確率
分布へ置き換える場合の表現例を示し、図１２は、確率
的に予測可能な移動物体をセンシングにより発見した場
合の表現例を示し、図１３は、移動ロボットの進行経路
が、確率的に予測可能な移動物体に挟まれている場合の
表現例を示している。

【００２２】本発明においては、地図や，移動物体の情
報が記述されていて、移動ロボットの経路探索に使用さ
れる２次元，又は、３次元の探索空間において、幾つか
の経路の候補を見つけて、コストの最小の経路を決定し
て、上記移動ロボットが移動する経路を探索する経路探
索方法であって、上記２次元，又は、３次元の探索空間
軸に、時間軸を追加して、時間的に変化する事象を、空
間軸での事象に置き換えて処理する手段、具体的には、
時間軸を含む探索空間において、時間的に存在位置が変
化しない事象，決まった時間に正確に生起する事象、電
車のように時刻表に従って、定時運転されている移動手
段等を、該時間軸を含む探索空間において、該探索空間
で表現できる他の事象に疑似化して、その疑似化された
事象も考慮して、該探索空間の格子，或いは、立方格子
のコスト評価をして、経路探索を行う手段が、本発明を
実施するのに必要な手段である。尚、全図を通して同じ
符号は同じ対象物を示している。

【００２３】以下、図１を参照しながら、図２〜図１３
によって、本発明の時間軸も探索空間に取り入れた経路
探索方法，及び、装置の構成と動作を説明する。図１
は、本発明による時間軸も探索空間に取り入れた経路探
索装置の構成例を示している。

【００２４】即ち、本発明の経路探索装置は、地図や，
移動物体の情報が記述されていて、移動ロボットの経路
探索に使用される２次元，又は、３次元の探索空間にお
いて、幾つかの経路の候補を見つけて、コストの最小の
経路を決定して、上記移動ロボットが移動する経路を探
索する経路探索装置であって、地図，移動物体のタイム
テーブル，移動物体の運動法則等を格納しているデータ
ベース 1と、移動ロボットが移動するときの確率分布予
測値を備えた、格子,又は、立方格子からなる地図を生
成するシミュレーション部 2と、該移動ロボットに対す
る確率分布予測値を備えた、格子, 又は、立方格子から
なる地図を、コストの格子, 又は、立方格子からなる地
図に変換するコスト計算部 3と、上記時間軸を含む探索
空間において、幾つかの経路の候補を見つけて、コスト
が最小の移動経路を決定する経路探索部 4とから構成さ
れる。（請求項１６に記載の発明に対応） 以下、上記
経路探索装置を用いて、該時間軸を取り入れた探索空間
における各事象の処理例を以下に示す。ここで、説明の
便宜上、空間軸はｘ，又は、ｘ，ｙ、時間軸はｔで表し
ている。

【００２５】恒常的事象：（請求項１，２に記載の発明
に対応） ここでいう恒常的事象は、時間によって存在位置が変化
しない物体（障害物）の存在である。このような物体
を、本発明においては、図２に示した時間軸を含む３次
元の空間で捉えると、図示されているように、壁や柱と
して疑似化して扱うことができ、経路探索を行うことが
できる。従って、図示されている探索空間内において、
移動ロボットは、スリットの間を移動して、コスト最小
の経路を移動することができる。

【００２６】定時変化事象：（請求項１，３に記載の発
明に対応） ここでいう定時変化事象は、決まった時間に正確に生起
することが判っている事象である。その例として、毎
日、定時に開閉の行われる出入り口や、信号機付交差点
がある。図３は、定時に開閉する出入り口の例を示して
おり、このような出入り口を、時間軸ｔを含む３次元の
空間として捉えると、窓として疑似化して扱うことがで
き、経路探索を行うことができる。従って、図示されて
いる探索空間内において、移動ロボットは、その窓を通
してコスト最小の経路を移動することができる。

【００２７】定時運転の移動手段：（請求項１，４に記
載の発明に対応） 電車のように、時刻表（タイムテーブル）に従って、定
時運転されている移動手段の例である。図４は、このよ
うな移動手段を、時間軸ｔを含む３次元の空間での表現
例を示している。このように、このような移動手段は、
該３次元の空間として捉えると、図示されているように
トンネル、即ち、該移動手段に乗ってから所定時間待っ
た後、所定の速度で移動した後、所定の時間停止してい
るときに形成されるトンネルに疑似化して扱うことがで
き、移動ロボットは、該トンネルを通ってコスト最小の
経路を移動することができる。

【００２８】任意時刻に利用可能な定速度移動手段：
（請求項１，５に記載の発明に対応）この移動手段は、
ベルトコンベアや動く歩道のように、任意の時間に利用
可能な一定速度で動く移動手段である。この移動手段を
上記時間軸ｔを含む３次元空間として捉えると、図５に
示されているように、移動方向に制限のついた廊下，又
は、トンネルに疑似化して扱うことができ、移動ロボッ
トは、該移動手段を使用して、移動することができ、そ
の時の移動経路の軌跡は、例えば、図５に示したものと
なる。

【００２９】上記の移動手段は、近似的には、定時運転
の移動手段が、連続して運行されているものとみなし、
上記時間軸ｔを含む３次元空間として捉えたとき、図６
に示されているように、トンネルが多数密着しているも
のとして疑似化することもできる。（請求項１，６に記
載の発明に対応） 任意時刻に呼び寄せて利用する移動手段：（請求項１，
７に記載の発明に対応） この移動手段は、エレベータ等のように、任意の時刻に
呼び寄せて利用する移動手段である。この場合、呼び出
してから利用可能になるまでの時間が不確定であるの
で、確率的な扱いが必要である。呼び寄せてからの利用
は、一定速度であるので、図７に示されているように、
任意時刻に利用でき、一定速度の移動手段と同様な扱い
ができる。実際の移動ロボットの移動軌跡は、図７の実
線のようになる。即ち、該移動手段を利用した部分は、
移動手段を呼び出して待っている部分と、該呼び寄せた
移動手段を利用して、一定の速度で移動している部分と
に分けられる。

【００３０】経路計画の観点からは、移動手段を利用す
ることに決定してしまった後は、その利用仮定の詳細は
考える必要は無く、該移動手段を利用して、移動可能な
距離と、そのときの所要時間（コスト対応）だけが問題
となる。従って、これらの移動過程は、図７に示されて
いるように、見掛け上の速度を用いることで、任意の時
間に利用可能な一定速度で動作する移動手段と同様な疑
似化をすることができる。但し、待ち時間の部分は、不
確定であるので、平均待ち時間を求めるようにして、点
線で示されている見掛け上の移動速度を確率的に扱う必
要がある。

【００３１】正確に予測可能な移動物体：（請求項１，
８に記載の発明に対応） この移動物体は、時刻表（タイムテーブル）に従って移
動していたり、厳密な移動規則に従っていて、センシン
グして発見した時点で、正確に、その後の運動が予測で
きる移動物体（障害物）である。このような移動物体を
時間軸ｔを含む３次元空間として捉えると、図８に示さ
れているように、柱状の障害物として疑似化することが
できる。

【００３２】確率的に予測可能な移動物体：（請求項
１，９に記載の発明に対応） このような移動物体は、正確には予測することができな
いが、図１に示されているデータベース 1や, センシン
グによって得られた移動物体の情報を元に、シミュレー
ション部 2でのシミュレーションによって、確率的に
は、予測できる移動物体である。｛図９〜図１２参照） 先ず、等速度で移動する移動物体について例を上げる。
この等速度で運動している移動物体（障害物）を上記時
間軸ｔを含む３次元の空間で捉えると、図９〜図１２で
示したように、円錐や、その組合わせで構成された障害
物として疑似化することができる。上記図９〜図１２で
は、境界線の明確な円錐として描かれているが、実際に
は、該移動物体の予測精度や、該移動物体との接触の危
険度によって、上記のような境界線の明確な円錐として
疑似化する方法と、境界線の不明確な分布を持つ円錐と
して疑似化する方法とに使い分けが必要となる。

【００３３】図９は、等速度で移動する移動物体（障害
物）の予測の例である。円錐で疑似化されているのは、
センシングした速度の精度が悪く、不確実さがあること
による。（請求項９，１０，１１に記載の発明に対応） 図１０は、等速度で移動する移動物体が、ある時点で分
岐する可能性がある場合の予測の例である。実際の適用
分野では、平面内を自由に移動することはなく、該移動
物体（例えば、人間，電車等）の進行方向前方に障害物
が存在したり、廊下の交差点に到達したときなどに、該
進行方向の予測の分岐が発生する。該分岐が発生した後
の移動についての予測は、各々の分岐方向での確率的な
移動予測と、どちらの方向に分岐するかの確率的な予測
との総合確率によって、該移動物体（障害物）の移動位
置の確率分布が計算される。（請求項９，１２に記載の
発明に対応） 図１１は、等速度で移動する移動物体の分岐の可能性が
多数ある場合の予測の例である。全ての分岐の可能性に
ついて、全てシミュレーションを行うことは、計算量が
膨大になることと、各々の分岐の確率の値が減少するこ
とから現実的ではなく、それぞれの分岐確率の値が、予
め、設定した閾値以下になったら、図１１に示されてい
るように、時刻的に固定の確率分布と置き換える（具体
的には、前述の格子，立方格子に対して移動ロボットが
移動できる固定確率の値を設定する）必要がある。（請
求項９，１３に記載の発明に対応） 図１２は、等速度で移動する移動物体の分岐の予測をし
ているとき、ある時点でのセンシングによって、該予測
していた移動物体を発見し、その位置の確定がなされた
場合の例である。この場合には、位置の確定が行われた
時点で、それまで位置の予測をしていた該移動物体の以
後での予測を中止し、該検出された移動物体の予測シミ
ュレーション、即ち、具体的には、前述の格子，立方格
子に対して移動ロボットが移動できる確率の値を設定す
ることを開始する。（請求項９，１４に記載の発明に対
応） 図１３は、道路や廊下等の移動方向の制限された環境
で、確率的に移動位置の予測が可能な移動物体（障害
物）に、移動ロボットの移動経路が挟まれている状態を
示している。この場合には、先に行く程狭まるトンネル
として、該障害物を疑似化して、移動ロボットの経路探
索を行うことができる。（請求項９，１５に記載の発明
に対応） このように、本発明の時間軸も探索空間に取り入れた経
路探索方法，及び装置は、地図や，移動物体の情報が記
述されていて、移動ロボットの経路探索に使用される２
次元，又は、３次元の探索空間軸に、時間軸ｔを追加し
て、時間的に変化する事象を、空間軸での事象に置き換
えて処理する。２次元空間で時間によって存在位置が変
化しない物体を存在を、時間軸ｔを含む３次元空間上
で、壁や柱に疑似化する。又、決まった時間に正確に生
起する事象、例えば、出入り口，信号機付交差点を、上
記時間軸ｔを含む３次元空間では、窓に疑似化する。
又、電車のように、時刻表に従って、定時運転される移
動手段を、上記時間軸ｔを含む３次元空間では、トンネ
ルに疑似化する。又、動く歩道のように、任意時間に利
用可能な一定速度で動く移動手段を、上記時間軸ｔを含
む３次元空間では、移動方向に制限のついた廊下，又
は、トンネルに疑似化して、移動ロボットの経路を探索
するようにしたところに特徴がある。

【００３４】

【発明の効果】以上、詳細に説明したように、本発明に
よれば、時間的に変化する事象が含まれる環境における
経路探索に対して、時間軸を探索空間に取り入れて、空
間軸での事象に置き換えて取り扱うことで、該時間的に
変化する事象を、時間的に変化しない物体に疑似化して
いるのｓ、時間的に変化しない環境に対する経路探索
法、例えば、公知の迷路法等を用いることができる。
又、環境の中で、移動する物体 (障害物) 等との衝突回
避と、経路探索とを統一して、経路探索を行うことがで
きる効果がある。

【図面の簡単な説明】

【図１】本発明の原理構成図

【図２】本発明の一実施例を示した図（その１）

【図３】本発明の一実施例を示した図（その２）

【図４】本発明の一実施例を示した図（その３）

【図５】本発明の一実施例を示した図（その４）

【図６】本発明の一実施例を示した図（その５）

【図７】本発明の一実施例を示した図（その６）

【図８】本発明の一実施例を示した図（その７）

【図９】本発明の一実施例を示した図（その８）

【図１０】本発明の一実施例を示した図（その９）

【図１１】本発明の一実施例を示した図（その１０）

【図１２】本発明の一実施例を示した図（その１１）

【図１３】本発明の一実施例を示した図（その１２）

【図１４】従来の移動ロボットの構成例を示した図

【符号の説明】

1 データベース 2 シミュレー
ション部 3 コスト計算部 4 経路探索部

Claims (16)

【特許請求の範囲】
1. 【請求項１】地図や，移動物体の情報が記述されてい
   て、移動ロボットの経路探索に使用される２次元，又
   は、３次元の探索空間において、幾つかの経路の候補を
   見つけて、コストの最小の経路を決定して、上記移動ロ
   ボットが移動する経路を探索する経路探索方法であっ
   て、 上記２次元，又は、３次元の探索空間軸に、時間軸を追
   加して、時間的に変化する事象を、空間軸での事象に置
   き換えて処理することを特徴とする時間軸を探索空間に
   取り入れた経路探索方法。
2. 【請求項２】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、時間によって存在位置が
   変化しない恒常的事象を、時間軸を含む探索空間におい
   て、固定物に疑似化して、経路探索を行うことを特徴と
   する時間軸を探索空間に取り入れた経路探索方法。
3. 【請求項３】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、決まった時間に正確に生
   起する定時変化事象を、時間軸を含む探索空間におい
   て、窓に疑似化して、経路探索を行うことを特徴とする
   時間軸を探索空間に取り入れた経路探索方法。
4. 【請求項４】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、定時運転の移動手段を、
   時間軸を含む探索空間において、トンネルに疑似化し
   て、経路探索を行うことを特徴とする時間軸を探索空間
   に取り入れた経路探索方法。
5. 【請求項５】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、任意時刻に利用する定速
   度移動手段を、時間軸を含む探索空間において、移動方
   向に制限のついた廊下，又は、トンネルに疑似化して、
   経路探索を行うことを特徴とする時間軸を探索空間に取
   り入れた経路探索方法。
6. 【請求項６】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、任意時刻に利用する定速
   度移動手段を、時間軸を含む探索空間において、近似的
   にトンネルが多数密着しているものに疑似化して、経路
   探索を行うことを特徴とする時間軸を探索空間に取り入
   れた経路探索方法。
7. 【請求項７】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、任意時刻に呼び寄せて利
   用する移動手段を、時間軸を含む探索空間において、確
   率的な見掛け上の速度を有し、任意時刻に利用する定速
   度移動手段に疑似化して、経路探索を行うことを特徴と
   する時間軸を探索空間に取り入れた経路探索方法。
8. 【請求項８】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、正確に予測できる移動物
   体を、時間軸を含む探索空間において、柱状の障害物に
   疑似化して、経路探索を行うことを特徴とする時間軸を
   探索空間に取り入れた経路探索方法。
9. 【請求項９】請求項１に記載の時間軸を探索空間に取り
   入れた経路探索方法であって、確率的に予測できる移動
   物体を、時間軸を含む探索空間において、円錐や、その
   組合わせで構成された障害物に疑似化して、経路探索を
   行うことを特徴とする時間軸を探索空間に取り入れた経
   路探索方法。
10. 【請求項１０】請求項９に記載の時間軸を探索空間に取
    り入れた経路探索方法であって、確率的に予測できる移
    動物体を、時間軸を含む探索空間において、上記円錐
    や、その組合わせで構成された障害物に疑似化する際、
    境界線の明確な円錐を用いて、経路探索を行うことを特
    徴とする時間軸を探索空間に取り入れた経路探索方法。
11. 【請求項１１】請求項９に記載の時間軸を探索空間に取
    り入れた経路探索方法であって、確率的に予測できる移
    動物体を、時間軸を含む探索空間において、上記円錐
    や、その組合わせで構成された障害物に疑似化する際、
    推定進行方向を中心軸とした、存在確率分布を用いて境
    界線の不明確な円錐状に疑似化して、経路探索を行うこ
    とを特徴とする時間軸を探索空間に取り入れた経路探索
    方法。
12. 【請求項１２】請求項９に記載の時間軸を探索空間に取
    り入れた経路探索方法であって、確率的に予測できる移
    動物体を、時間軸を含む探索空間において、上記円錐
    や、その組合わせで構成された障害物に疑似化する際、
    進行方向に、複数の進行方向が存在する場合、該複数の
    進行方向に対する、所定の確率による分岐をした障害物
    に疑似化して、経路探索を行うことを特徴とする時間軸
    を探索空間に取り入れた経路探索方法。
13. 【請求項１３】請求項１２に記載の時間軸を探索空間に
    取り入れた経路探索方法であって、分岐の数が多い場
    合、時間的に固定した確率分布を持つ障害物に疑似化し
    て、経路探索を行うことを特徴とする時間軸を探索空間
    に取り入れた経路探索方法。
14. 【請求項１４】請求項９に記載の時間軸を探索空間に取
    り入れた経路探索方法であって、確率的に予測できる移
    動物体を、時間軸を含む探索空間において、上記円錐
    や、その組合わせで構成された障害物に疑似化する際、
    ある時点でのセンシングによって、該予測していた移動
    物体を検出した場合には、位置の確定が行われた時点
    で、以前に疑似化している障害物を消滅し、新たな、確
    率分布による円錐で構成された障害物に疑似化して、経
    路探索を行うことを特徴とする時間軸を探索空間に取り
    入れた経路探索方法。
15. 【請求項１５】請求項９に記載の時間軸を探索空間に取
    り入れた経路探索方法であって、道路や，廊下等の移動
    方向の制限された環境で、確率的に予測できる移動物体
    に挟まれた状態で、経路探索を行う場合、該移動物体
    を、該時間軸を含む探索空間において、先に行く程狭ま
    るトンネルに疑似化して、経路探索を行うことを特徴と
    する時間軸を探索空間に取り入れた経路探索方法。
16. 【請求項１６】地図や，移動物体の情報が記述されてい
    て、移動ロボットの経路探索に使用される２次元，又
    は、３次元の探索空間において、幾つかの経路の候補を
    見つけて、コストの最小の経路を決定して、上記移動ロ
    ボットが移動する経路を探索する経路探索装置であっ
    て、 地図，移動物体のタイムテーブル，移動物体の運動法則
    等を格納しているデータベース部(1) と、移動ロボット
    に対する確率分布予測値を備えた、格子, 又は、立方格
    子からなる地図を生成するシミュレーション部(2) と、
    該移動ロボットに対する確率分布予測値を備えた、格
    子, 又は、立方格子からなる地図を、コストの格子, 又
    は、立方格子からなる地図に変換するコスト計算部(3)
    と、上記時間軸を含む探索空間において、幾つかの経路
    の候補を見つけて、コストが最小の移動経路を決定する
    経路探索部(4) とからなることを特徴とする時間軸を探
    索空間に取り入れた経路探索装置。