JP3218865B2

JP3218865B2 - 時間軸を探索空間に取り入れた経路探索装置

Info

Publication number: JP3218865B2
Application number: JP14649394A
Authority: JP
Inventors: 旭川村; 浩之岡田; 伸朗末松
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1994-06-28
Filing date: 1994-06-28
Publication date: 2001-10-15
Anticipated expiration: 2016-10-15
Also published as: JPH0816240A

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

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

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

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

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

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

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

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

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

【００１０】そこで、時間的に変化する事象も含めて経
路探索を行う為に、２次元，又は、３次元の空間軸の他
に時間軸を追加して経路の探索空間の拡張を行う。基本
的な考え方は、以下の通りであり、本願出願人が先願し
ている特願平 06-017702号「時間軸を探索空間に取り入
れた経路探索方法、及び装置」によって詳細に開示して
いる。

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

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

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

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

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

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

【００１７】図７〜図１８は、時間軸を取り入れた探索
空間における事象の扱いの例を示した図であって、上記
本願出願人が先願している特願平06-017702 号「時間軸
を探索空間に取り入れた経路探索方法、及び装置」で説
明した図であり、各事象の、時間軸を含む探索空間での
表現形態の例を示しており、図７は恒常的事象の場合の
表現例を示し、図８は定時変化事象の場合の表現例を示
し、図９は、定時運転の移動手段の場合の表現例を示
し、図１０は、任意時刻に利用可能な定速度移動手段の
場合の表現例を示し、図１１は、任意時刻に利用可能な
定速度移動手段が多数ある場合の表現例を示し、図１２
は、任意時刻に呼び出して利用する定速度移動手段の表
現例を示し、図１３は、正確に予測可能な移動物体（等
速度運動の移動物体）の表現例を示し、図１４は、確率
的に予測可能な移動物体（等速度運動）の表現例を示
し、図１５は、確率的に予測可能な移動物体が分岐する
場合の表現例を示し、図１６は、確率的に予測可能な移
動物体の分岐を、時間的に固定な確率分布へ置き換える
場合の表現例を示し、図１７は、確率的に予測可能な移
動物体をセンシングにより発見した場合の表現例を示
し、図１８は、移動ロボットの進行経路が、確率的に予
測可能な移動物体に挟まれている場合の表現例を示して
いる。

【００１８】以下、図７〜図１８によって、時間軸も探
索空間に取り入れた経路探索方法，及び、装置の構成と
動作を説明する。ここで、説明の便宜上、空間軸はｘ，
又は、ｘ，ｙ、時間軸はｔで表している。

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

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

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

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

【００２３】上記の移動手段は、近似的には、定時運転
の移動手段が、連続して運行されているものとみなし、
上記時間軸ｔを含む３次元空間として捉えたとき、図１
１に示されている（但し、図１１では、便宜上２次元で
示す）ように、トンネルが多数密着しているものとして
疑似化することもできる。

【００２４】任意時刻に呼び寄せて利用する移動手段：
この移動手段は、エレベータ等のように、任意の時刻に
呼び寄せて利用する移動手段である。この場合、呼び出
してから利用可能になるまでの時間が不確定であるの
で、確率的な扱いが必要である。呼び寄せてからの利用
は、一定速度であるので、図１２に示されているよう
に、任意時刻に利用でき、一定速度の移動手段と同様な
扱いができる。実際の移動ロボットの移動軌跡は、図１
２の実線のようになる。即ち、該移動手段を利用した部
分は、移動手段を呼び出して待っている部分と、該呼び
寄せた移動手段を利用して、一定の速度で移動している
部分とに分けられる。

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

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

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

【００２８】図１４は、等速度で移動する移動物体（障
害物）の予測の例である。円錐で疑似化されているの
は、センシングした速度の精度が悪く、不確実さがある
ことによる。

【００２９】図１５は、等速度で移動する移動物体が、
ある時点で分岐する可能性がある場合の予測の例であ
る。実際の適用分野では、平面内を自由に移動すること
はなく、該移動物体（例えば、人間，電車等）の進行方
向前方に障害物が存在したり、廊下の交差点に到達した
ときなどに、該進行方向の予測の分岐が発生する。該分
岐が発生した後の移動についての予測は、各々の分岐方
向での確率的な移動予測と、どちらの方向に分岐するか
の確率的な予測との総合確率によって、該移動物体（障
害物）の移動位置の確率分布が計算される。

【００３０】図１６は、等速度で移動する移動物体の分
岐の可能性が多数ある場合の予測の例である。全ての分
岐の可能性について、全てシミュレーションを行うこと
は、計算量が膨大になることと、各々の分岐の確率の値
が減少することから現実的ではなく、それぞれの分岐確
率の値が、予め、設定した閾値以下になったら、図１６
に示されているように、時刻的に固定の確率分布と置き
換える（具体的には、前述の格子，立方格子に対して移
動ロボットが移動できる固定確率の値を設定する）必要
がある。

【００３１】図１７は、等速度で移動する移動物体の分
岐の予測をしているとき、ある時点でのセンシングによ
って、該予測していた移動物体を発見し、その位置の確
定がなされた場合の例である。この場合には、位置の確
定が行われた時点で、それまで位置の予測をしていた該
移動物体の以後での予測を中止し、該検出された移動物
体の予測シミュレーション、即ち、具体的には、前述の
格子，立方格子に対して移動ロボットが移動できる確率
の値を設定することを開始する。

【００３２】図１８は、道路や廊下等の移動方向の制限
された環境で、確率的に移動位置の予測が可能な移動物
体（障害物）に、移動ロボットの移動経路が挟まれてい
る状態を示している。この場合には、先に行く程狭まる
トンネルとして、該障害物を疑似化して、移動ロボット
の経路探索を行うことができる。

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

【００３４】

【発明が解決しようとする課題】従って、正確な未来予
測は不可能であり、それらの予測の不確実さがある場
合、その不確実さは、生起確率分布として扱う必要があ
る。その場合、事象の影響が及ぶ時間的空間的範囲は、
予測の曖昧さに従って、広範囲に及ぶことになる。その
為、その事象と遭遇することを完全に達成したり、回避
することは困難となる。

【００３５】特に、事象が生起する可能性が少しでもあ
る領域を経路探索空間から排除することにより、移動可
能な領域が非常に狭くなるか、または存在しなくなる可
能性がある。例えば、図１８のように、道路や廊下等の
移動方向の制限された環境で、確率的に予測可能な移動
体に挟まれている状態を考える。この場合、先に行くほ
ど狭まるトンネルとして扱うことができ、経路の計画が
可能であるが、後述の図２のように、前後の移動体の進
路予測の幅が広くなって、進行方向前方を塞いでしまっ
た場合には、前後の移動体は壁として扱わなければなら
なくなり、それらの間をすり抜ける経路は生成できなく
なる問題がある。

【００３６】然し、実際の場面では、時々刻々のセンシ
ングによって移動体の進路予測が明確となり、分布範囲
が狭くなっていく場合とか、移動体との衝突回避の有効
な手段が存在する場合、例えば、迂回経路が存在する場
合とか、衝突のダメージが非常に小さい場合等には、移
動体の存在確率がある程度小さい領域への移動が、安全
性を保ったまま可能である。このような移動経路をとる
ことは、経路探索の効率上の観点からの要請でもある。

【００３７】このように、事象の生起確率の分布に対し
て、対象とする事象や状況に応じて違う対応をとること
が、経路探索上必要である。本発明は上記従来の欠点に
鑑み、時間軸を探索空間に取り入れた移動ロボットの経
路探索装置において、時間的に変化する事象の知識を経
路探索に取り込み、正確に到達の可能性を、事象の生起
確率の分布に対して、対象とする事象や状況に応じて違
う対応をとって判断し、コスト最小の経路を探索するこ
とができる経路探索装置を提供することを目的とするも
のである。

【００３８】

【課題を解決するための手段】図１〜図５は、本発明の
一実施例を示した図であり、図１は経路探索装置の構成
例を示し、図２は、２個の移動体の存在確率分布が進路
を塞いでいる状態の存在確率分布図を示し、図３は、２
個の移動体に挟まれた場合のコスト分布図を示し、図４
は閾値以下の領域をカットしたときの２個の移動体に挟
まれた場合のコスト分布図を示し、図５は、閾値以下の
領域をカットして、残った領域のコストを一定値とした
ときの２個の移動体に挟まれた場合のコスト分布図を示
している。上記の問題点は、下記の如くに構成した時間
軸を探索空間に取り入れた経路探索装置によって解決さ
れる。

【００３９】(1) 地図や，移動物体の情報が記述されて
いて、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索装置であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸
を追加した探索空間で、時間的に変化する事象を、空間
軸での事象に置き換えて処理するのに、上記地図，移動
物体のタイムテーブル，移動物体の運動法則等を格納し
ているシミュレーション用データ格納部 1a からなるデ
ータベース部 1と、上記データベース部 1に格納されて
いるシミュレーション用データを用いて、上記移動ロボ
ットに対する確率分布予測値を備えた格子, 又は、立方
格子からなる地図を生成するシミュレーション部 2と、
該移動ロボットに対する確率分布予測値を備えた格子,
又は、立方格子からなる地図を、コストの格子, 又は、
立方格子からなる地図に変換するコスト計算部3と、上
記コストの格子，又は、立方格子からなる地図から、幾
つかの経路の候補を見つけて、コストが最小の移動経路
を決定する経路探索部 4と、からなるように構成する。

【００４０】(2) 地図や，移動物体の情報が記述されて
いて、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索装置であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸
を追加した探索空間で、時間的に変化する事象を、空間
軸での事象に置き換えて処理するのに、上記地図，移動
物体のタイムテーブル，移動物体の運動法則等を格納し
ているシミュレーション用データ格納部 1a と、上記探
索空間での事象毎の、該経路探索に対する影響の質と量
によって異なる係数を格納しているコスト係数格納部(1
b)とからなるデータベース部 1と、上記データベース部
1に格納されているシミュレーション用データを用い
て、上記移動ロボットに対する確率分布予測値を備えた
格子, 又は、立方格子からなる地図を生成するシミュレ
ーション部 2と、該移動ロボットに対する確率分布予測
値を備えた格子, 又は、立方格子からなる地図を、コス
トの格子, 又は、立方格子からなる地図に変換する際、
上記移動ロボットに対する確率分布予測値に、上記デー
タべース部 1のコスト係数格納部1b に格納されている
経路探索に対する影響の質と量によって異なる係数を乗
じてコスト計算を行うコスト計算部 3と、上記コストの
格子，又は、立方格子からなる地図から、幾つかの経路
の候補を見つけて、コストが最小の移動経路を決定する
経路探索部 4と、からなるように構成する。

【００４１】(3) 地図や，移動物体の情報が記述されて
いて、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索装置であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸
を追加した探索空間で、時間的に変化する事象を、空間
軸での事象に置き換えて処理するのに、上記地図，移動
物体のタイムテーブル，移動物体の運動法則等を格納し
ているシミュレーション用データ格納部 1a と、上記探
索空間での事象毎の、該経路探索に対する影響の質と量
によって異なる係数と、上記事象毎に設定された生起確
率の分布領域が、所定の値以下の領域をカットしてコス
ト計算を行うときの閾値とを格納しているコスト係数格
納部 1c とからなるデータベース部 1と、上記データベ
ース部 1に格納されているシミュレーション用データを
用いて、上記移動ロボットに対する確率分布予測値を備
えた格子, 又は、立方格子からなる地図を生成するシミ
ュレーション部 2と、該移動ロボットに対する確率分布
予測値を備えた格子, 又は、立方格子からなる地図を、
コストの格子, 又は、立方格子からなる地図に変換する
際、上記移動ロボットに対する確率分布予測値に、上記
データべース部 1に格納されている経路探索に対する影
響の質と量によって異なる係数を乗じてコスト計算を行
うとき、上記事象毎に設定された生起確率の分布領域
が、上記データベース部 1のコスト係数格納部 1c が格
納している所定の閾値以下の領域をカットしてコスト計
算を行うコスト計算部 3と、上記コストの格子，又は、
立方格子からなる地図から、幾つかの経路の候補を見つ
けて、コストが最小の移動経路を決定する経路探索部 4
と、からなるように構成する。

【００４２】(4) (3) 項に記載の時間軸を探索空間に取
り入れた経路探索装置であって、上記コスト計算部 3
で、上記データベース部 1のコスト係数格納部 1c が格
納している所定の閾値以下の領域をカットしてコスト計
算を行う際、カットされなかった領域のコストを一定値
としてコスト計算を行うように構成する。

【００４３】

【作用】図１は、本発明の経路探索装置の構成例を示し
ている。本図に示されている、本発明による経路探索装
置においては、データべース部 1は、地図, タイムテー
ブル, 移動体の運動法則等のシミュレーションのための
知識を格納するシミュレーション用データ格納部 1a
と、事象や状況ごとにコスト計算時に用いる係数と閾値
を格納するコスト係数格納部 1b とから構成される。

【００４４】シミュレーション部 2は、上記シミュレー
ション用データ格納部 1a の情報を元に、各々の事象毎
にシミュレーションを行う。このとき、移動ロボットの
環境中に生起する事象間の相互作用は、考慮に入れな
い。事象の正確な予測ができない場合には、事象の生起
確率の分布の形式で予測を行う。

【００４５】コスト計算部 3は、各々の事象や状況毎
に、該事象の生起確率が、上記閾値以下である領域をカ
ットすることと、上記コスト係数格納部 1b のコスト係
数を事象の生起確率に掛け合わせることの片方, 或い
は、両方の処理を行うことによって、探索空間中でのコ
スト分布を算出する。

【００４６】経路探索部 4は、コストの合計を最小化す
る経路探索法により経路探索を行う。前述のように、未
来に生起する事象の予測を完全に行うことは不可能であ
り、予測は、確率分布の形式で記述されるが、その場合
に問題となるのが、事象の生起確率の分布の範囲の大き
さである。完全な障壁, 軌道, 速度制限手段・安全装置
等がある場合を除いて、ある事象の生起確率は、どの空
間, 時点においても、完全に“０”になることはなく、
確率分布の領域は広いものとなり、探索空間の全てを覆
い尽くす可能性もある。

【００４７】そのために、ある事象との遭遇（移動体と
の場合は衝突）の危険を完全に無くするために、その事
象の生起確率の分布領域を完全に避けて経路を設定する
ことは、効率的ではなく、最悪の場合には不可能とな
る。

【００４８】この問題を解決するために、本発明におい
ては、ある程度の危険を見込んだ経路計画を行うことと
する。即ち、経路計画を行うときのコスト計算に、その
時点，その場所でのある事象の生起確率を使用し、ある
程度以下の生起確率の分布領域の通過を許容して、経路
計画を行うようにする。

【００４９】一方、事象毎に、移動ロボットの移動に対
する影響度が異なる。非常に危険な為に、絶対に遭遇し
てはいけない事象がある一方で、全然影響のない事象が
ある。例えば、大洋を船が移動する場合を考えると、事
象として、台風，竜巻等があり、移動体である船にも、
ヨットの類から大型の船舶がある。小さいヨットが大型
の台風等に遭遇することは非常に危険であるが、大型の
船舶が小さい台風に遭遇しても何らの影響はない。

【００５０】従って、事象の生起確率を一律にコスト計
算に使用することは、非効率であるとともに、無害な事
象を避けるために、非常に危険な事象に遭遇する経路を
設定する可能性を生じさせることがある。

【００５１】そこで、本発明においては、経路のコスト
を計算する際に、事象の生起確率を使用するとき、事象
毎の影響の質（上記の例では、小さいヨットが大型の台
風等に遭遇することは非常に危険であるが、大型の船舶
が小さい台風に遭遇しても何らの影響はないといった影
響の質）と、量（影響度、即ち、この例では壊れ方）の
違いによって、異なる係数を、上記生起確率に乗じる手
段を採るようにしたものである。

【００５２】又、上記の計算を簡単化する為に、事象毎
に異なる閾値を設けて、該事象の生起確率が、その閾値
以下の分布領域をカットするようにする。更に、該コス
ト計算を簡単化する場合には、上記カットされなかった
領域内のコストを一定値とすることで、各経路でのコス
ト計算が簡単になる。

【００５３】上記のように作用するので、時間的空間的
に不確定な要素を持つ事象が含まれる環境における経路
探索に対して、時間的に変化しない環境に対するのと同
様なコスト最小化による経路探索を用いることが可能と
なる。又、事象毎の影響度の違いを経路探索に使用する
コストマップの計算に使用することができ、事象毎の影
響度の少ない経路を探索することができる。

【００５４】

【実施例】以下本発明の実施例を図面によって詳述す
る。前述の図１〜図５は、本発明の一実施例を示した図
であり、図１は、本発明の経路探索装置の構成例を示
し、図２は、２個の移動体の存在確率分布が進路を塞い
でいる状態の存在確率分布図を示し、図３は、２個の移
動体に挟まれた場合のコスト分布図を示し、図４は閾値
以下の領域をカットしたときの２個の移動体に挟まれた
場合のコスト分布図を示し、図５は、閾値以下の領域を
カットして、残った領域のコストを一定値としたときの
２個の移動体に挟まれた場合のコスト分布図を示してい
る。

【００５５】本発明においては、地図や，移動物体の情
報が記述されていて、移動ロボットの経路探索に使用さ
れる２次元，又は、３次元の探索空間において、幾つか
の経路の候補を見つけて、コストの最小の経路を決定し
て、上記移動ロボットが移動する経路を探索するのに、
地図，移動物体のタイムテーブル，移動物体の運動法則
等を格納しているシミュレーション用データ格納部 1a
と、上記空間軸での事象毎の該経路探索に対する影響の
質と量によって異なる係数と、上記事象毎に設定された
生起確率の分布領域が所定の値以下の領域をカットして
コスト計算を行うときの閾値を格納しているコスト係数
格納部 1b,1cとからなるデータベース部1と、上記移動
ロボットに対する確率分布予測値を備えた、格子, 又
は、立方格子からなる地図を生成するシミュレーション
部 2と、該移動ロボットに対する確率分布予測値を備え
た、格子, 又は、立方格子からなる地図を、コストの格
子,又は、立方格子からなる地図に変換するコスト計算
部 3と、上記コスト格子，又は、立方格子からなる地図
から、幾つかの経路の候補を見つけて、コストが最小の
移動経路を決定する経路探索部 4が、本発明を実施する
のに必要な手段である。尚、全図を通して同じ符号は同
じ対象物を示している。

【００５６】以下、図１〜図５を用いて、本発明による
経路探索装置の構成，及び、動作を説明する。前述のよ
うに、図１に示した本発明の経路探索装置においては、
データべース部 1は、地図, タイムテーブル, 移動体の
運動法則等のシミュレーションのための知識を格納する
シミュレーション用データ格納部 1a と、事象や状況ご
とにコスト計算時に用いる係数と閾値を格納するコスト
係数格納部 1b とから構成される。

【００５７】シミュレーション部 2は、上記シミュレー
ション用データ格納部 1a の情報を元に、各々の事象毎
にシミュレーションを行う。このとき、移動ロボットの
環境中に生起する事象間の相互作用は、考慮に入れな
い。事象の正確な予測ができない場合には、事象の生起
確率の分布の形式で予測を行う。

【００５８】コスト計算部 3は、各々の事象や状況毎
に、該事象の生起確率が、上記閾値以下である領域をカ
ットすることと、上記コスト係数格納部 1b のコスト係
数を事象の生起確率に掛け合わせることの片方, 或い
は、両方の処理を行うことによって、探索空間中でのコ
スト分布を算出する。

【００５９】経路探索部 4は、コストの合計を最小化す
る経路探索法により経路探索を行う。図２は、前述のよ
うに、２個の移動体の存在確率分布が進路を塞いでいる
状態の存在確率分布を濃淡によって示している。このよ
うな所定の存在確率が存在する場合、移動体ロボットの
進路を塞いでしまうとすると、移動体Ａと移動体Ｂの存
在確率の重なっている部分において、移動ロボットの進
路が塞がれてしまう。

【００６０】図３は、図２の存在確率分布に対応してコ
ストを計算した場合のコスト分布図で、この実施例で
は、移動体Ａが移動体Ｂより大きいため、移動体Ａのコ
スト分布が、移動体Ｂのコスト分布より大きい場合を示
している。このとき、図４に示したように、存在確率が
所定の閾値より小さい領域の存在確率をカットして、そ
の部分のコストを“０”とした場合のコスト分布図であ
る。このようなコスト計算をすることにより、移動ロボ
ットは、移動体Ａ，Ｂとの衝突を回避することのできる
進路を探索することができる。

【００６１】図５は、移動体の存在確率が所定の閾値よ
り小さい領域の存在確率をカットして、残った領域のコ
ストを一定とした場合のコスト分布図を示している。こ
のようなコスト計算をすることにより、探索空間でのコ
スト分布の計算を高速に行うことができ、且つ、経路探
索を容易に行うことができる。上記本発明による時間軸
を探索空間に取り入れた経路探索において、コストを計
算する場合、探索空間での、該移動体の存在確率をＰ_it
(ｉは領域を示し、ｔは時刻を示している）に対応し
て、移動体Ａ，Ｂ，〜と、移動ロボットとの間に発生す
る各事象毎の影響度の質、例えば、移動体Ａ，Ｂと、移
動ロボットの大きさによる影響度の違いと量、例えば、
移動体Ａ，Ｂに、移動ロボットが衝突したことによって
被る壊れ方の量によって、異なる係数α_itを掛けたも
の、即ちＰ_it×α_itを、その空間ｉ，時刻ｔでのコスト
Ｃ_itとし、移動ロボットが移動した経路での上記コスト
の集合ΣＰ_it×α_itが最小となる経路を探索する。

【００６２】上記のコスト係数α_itを決定する要素とし
ては、前述の移動体の大きさ以外に、移動体の重量_,速
度_,材質_,衝撃吸収装置の有無と、その性能_,壊れ易
さ、貴重度_,移動ロボットからのセンシングでの発見の
容易さ、移動体自身の機能しての衝突回避能力等が上げ
られる。

【００６３】このとき、移動体の探索空間での存在確率
Ｐ_itが、所定の閾値以下である探索空間での存在確率Ｐ
_itをカットすることで、効率の良いコスト計算を行うと
共に、経路探索を行うようにする。

【００６４】又、上記のようにしてコスト計算してカッ
トされた残りの領域のコストＣ_itを、所定の一定値｛図
５参照｝とすることで、探索空間での各格子、立法格子
でのコスト計算を容易にすることができ、移動ロボット
の移動コストの計算も高速化することができる。

【００６５】又、上記のコスト計算では、絶対値で計算
する例で説明したが、正規化されたコストで計算しても
良いことは言う迄もないことである。このように、本発
明における時間軸を探索空間に取り入れた経路探索装置
は、地図や，移動物体の情報が記述されていて、移動ロ
ボットの経路探索に使用される２次元，又は、３次元の
探索空間軸に、時間軸を追加した探索空間で、時間的に
変化する事象を、空間軸での事象に置き換えて経路探索
を行う経路探索装置であって、上記探索時間中の空間軸
での事象に置き換えられた確率的にしか記述でいない事
象要素のコストを計算するときに、該不確定要素の生起
確率を用いる。このとき、上記空間軸での事象毎の該経
路探索に対する影響の質と量によって異なる係数を乗ず
る。又、上記事象毎に設定された生起確率の分布領域が
所定の値以下の領域をカットしてコスト計算を行う。
又、上記のコスト計算において、カットされなかった領
域のコストを一定値とするようにしたところに特徴があ
る。

【００６６】

【発明の効果】以上、詳細に説明したように、本発明に
よれば、時間的空間的に不確定な要素を持つ事象が含ま
れる環境における経路探索に対して、時間的に変化しな
い環境に対するのと同様なコスト最小化による経路探索
を用いることが可能となる。又、事象毎の影響度の違い
を経路探索に使用するコストマップの計算に使用するこ
とができ、事象毎に影響度の少ない経路を探索すること
ができる。

【図面の簡単な説明】

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

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

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

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

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

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

【図７】時間軸を取り入れた探索空間における事象の扱
いの例を示した図（その１）

【図８】時間軸を取り入れた探索空間における事象の扱
いの例を示した図（その２）

【図９】時間軸を取り入れた探索空間における事象の扱
いの例を示した図（その３）

【図１０】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その４）

【図１１】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その５）

【図１２】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その６）

【図１３】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その７）

【図１４】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その８）

【図１５】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その９）

【図１６】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その１０）

【図１７】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その１１）

【図１８】時間軸を取り入れた探索空間における事象の
扱いの例を示した図（その１２）

【符号の説明】

1 データベース部 1a シミュレーション用データ格納部 1b,1c コスト係数格納部 2 シミュレーション部 3 コスト計算部 4 経路探索部

───────────────────────────────────────────────────── フロントページの続き (56)参考文献特開平７−225612（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G05D 1/00 - 1/12 G06N 3/00

Claims

(57)【特許請求の範囲】

【請求項１】地図や，移動物体の情報が記述されてい
て、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索装置であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸を追
加した探索空間で、時間的に変化する事象を、空間軸で
の事象に置き換えて処理するのに、上記地図，移動物体のタイムテーブル，移動物体の運動
法則等を格納しているシミュレーション用データ格納部
(1a)からなるデータベース部(1) と、上記データベース部(1) に格納されているシミュレーシ
ョン用データを用いて、上記移動ロボットに対する確率
分布予測値を備えた格子, 又は、立方格子からなる地図
を生成するシミュレーション部(2) と、該移動ロボットに対する確率分布予測値を備えた格子,
又は、立方格子からなる地図を、コストの格子, 又は、
立方格子からなる地図に変換するコスト計算部(3) と、上記コストの格子，又は、立方格子からなる地図から、
幾つかの経路の候補を見つけて、コストが最小の移動経
路を決定する経路探索部(4) と、からなることを特徴と
する時間軸を探索空間に取り入れた経路探索装置。
【請求項２】地図や，移動物体の情報が記述されてい
て、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索装置であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸を追
加した探索空間で、時間的に変化する事象を、空間軸で
の事象に置き換えて処理するのに、上記地図，移動物体のタイムテーブル，移動物体の運動
法則等を格納しているシミュレーション用データ格納部
(1a)と、上記探索空間での事象毎の、該経路探索に対す
る影響の質と量によって異なる係数を格納しているコス
ト係数格納部(1b)とからなるデータベース部(1) と、上記データベース部(1) に格納されているシミュレーシ
ョン用データを用いて、上記移動ロボットに対する確率
分布予測値を備えた格子, 又は、立方格子からなる地図
を生成するシミュレーション部(2) と、該移動ロボットに対する確率分布予測値を備えた格子,
又は、立方格子からなる地図を、コストの格子, 又は、
立方格子からなる地図に変換する際、上記移動ロボット
に対する確率分布予測値に、上記データべース部(1) の
コスト係数格納部(1b)に格納されている経路探索に対す
る影響の質と量によって異なる係数を乗じてコスト計算
を行うコスト計算部(3) と、上記コストの格子，又は、立方格子からなる地図から、
幾つかの経路の候補を見つけて、コストが最小の移動経
路を決定する経路探索部(4) と、からなることを特徴と
する時間軸を探索空間に取り入れた経路探索装置。
【請求項３】地図や，移動物体の情報が記述されてい
て、移動ロボットの経路探索に使用される２次元，又
は、３次元の探索空間において、幾つかの経路の候補を
見つけて、コストの最小の経路を決定して、上記移動ロ
ボットが移動する経路を探索する経路探索装置であっ
て、上記２次元，又は、３次元の探索空間軸に、時間軸を追
加した探索空間で、時間的に変化する事象を、空間軸で
の事象に置き換えて処理するのに、上記地図，移動物体のタイムテーブル，移動物体の運動
法則等を格納しているシミュレーション用データ格納部
(1a)と、上記探索空間での事象毎の、該経路探索に対す
る影響の質と量によって異なる係数と、上記事象毎に設
定された生起確率の分布領域が、所定の値以下の領域を
カットしてコスト計算を行うときの閾値とを格納してい
るコスト係数格納部(1c)とからなるデータベース部(1)
と、上記データベース部(1) に格納されているシミュレーシ
ョン用データを用いて、上記移動ロボットに対する確率
分布予測値を備えた格子, 又は、立方格子からなる地図
を生成するシミュレーション部(2) と、該移動ロボットに対する確率分布予測値を備えた格子,
又は、立方格子からなる地図を、コストの格子, 又は、
立方格子からなる地図に変換する際、上記移動ロボット
に対する確率分布予測値に、上記データべース部(1) に
格納されている経路探索に対する影響の質と量によって
異なる係数を乗じてコスト計算を行うとき、上記事象毎
に設定された生起確率の分布領域が、上記データベース
部(1) のコスト係数格納部(1c)が格納している所定の閾
値以下の領域をカットしてコスト計算を行うコスト計算
部(3) と、上記コストの格子，又は、立方格子からなる地図から、
幾つかの経路の候補を見つけて、コストが最小の移動経
路を決定する経路探索部(4) と、からなることを特徴と
する時間軸を探索空間に取り入れた経路探索装置。
【請求項４】請求項３に記載の時間軸を探索空間に取り
入れた経路探索装置であって、上記コスト計算部(3)
で、上記データベース部(1) のコスト係数格納部(1c)が
格納している所定の閾値以下の領域をカットしてコスト
計算を行う際、カットされなかった領域のコストを一定
値としてコスト計算を行うことを特徴とする時間軸を探
索空間に取り入れた経路探索装置。