(57)【特許請求の範囲】
【請求項１】
複数の障害物を有するエリアを通る自動車の車両ナビゲーション方法であって、
複数のエッジを有するボロノイ分割をエリア上に作成するステップと、
前記エリア内の幾何学的位置に対して、０と上限値間に値を有するボロノイフィールドを、該フィールドが前記障害物内で最大値に到達し、前記エッジ上で最小値に到達するように計算するステップと、
前記エリア内の隣接する位置の間で、始点から目的地へ向かう横断コストを計算するステップであって、前記横断コストは前記フィールドの値に比例して増加する、横断コストを計算するステップと、
前記目的地への横断コストが最小となるルートをプロットするステップと、
前記ルートが前記ボロノイ分割の前記エッジからそれるように、前記ルートをスムージングするステップと、を備え、
前記コストを計算するステップはさらに、隣接する位置の間で障害物に遭遇するときは何時でも前記計算された横断コストに第１の値を割り当て、隣接する位置の間で障害物に遭遇しないときは何時でも前記第１の値より小さい第２の値を割り当てるステップを備え、さらに、前記ボロノイフィールドは下式で定義され、
【数１】
0005485533.tif 000007
ここで、Ｐｖ＝フィールド、α＝定数＞０、β＝定数＞０、γ＝定数＞０であることを特徴とする障害物回避ナビゲーション方法。
【請求項２】
前記横断コストを計算するステップは、セル間の車両の方向が予め決定された車両の回転率の制限を満たすかを決定し、該制限を満たす場合は、前記計算された横断コストに第１の値を割り当て、該制限を満たさない場合は、前記計算された横断コストに前記第１の値より大きい第２の値を割り当てるステップを備える、
請求項１に記載の障害物回避ナビゲーション方法。
【請求項３】
前記始点は前記車両の位置に対応する、
請求項１に記載の障害物回避ナビゲーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、障害物回避用メカニズムによって障害物エリアを通る、車両ナビゲーション方法に関する。
【背景技術】
【０００２】
１つまたは複数の障害物を有するエリアを通るロボットを案内する、主に移動体ロボット用のナビゲーションシステムが知られている。このような既知のシステムは、ロボットを障害物から退けしたがって衝突を回避するために、種々の障害物に関連するポテンシャルフィールドを提供する。これらの既知の試みはしかし動作上全てが満足できるものではないことが分かった。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
これらのナビゲーションシステムの１つの欠点は、ポテンシャルフィールドが、極小問題の影響を受け、潜在的にロボットをデッドエンドに捕獲し、同様に、狭小通路を横断できなくすることである。さらに他の状況においては、ロボットまたは自動車等の他の車両は障害物を避けるが、走行中、対象物に許容できないくらいに接近する。
【課題を解決するための手段】
【０００４】
本発明は、既知の方法の上記欠点を克服する、障害物回避用の車両ナビゲーション方法を提供する。
【０００５】
端的に言うと、本発明のナビゲーションシステムは複数の障害物があるエリアでの使用のために提供される。ボロノイ分割（Ｖｏｒｏｎｏｉ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ）がそのエリア内のそれぞれの対象物を取り囲む複数のエッジを含むように、そのエリアによって形成される。従来の計算手段がボロノイ分割を作成するために利用できる。
【０００６】
次に、０と上限の間の値を有するボロノイフィールドが、エリア内の幾何学的位置の全てに対して計算される。ボロノイフィールドの値は、エリア内に含まれる障害物内で最大値に到達し、ボロノイ分割のエッジ上で最小値に到達する。
【０００７】
次に、車両の位置から目的地に向っての、エリア内の隣接する位置またはグリッド間の横断コストが計算される。この横断コストは、そのエリア中の隣接するそれぞれの位置におけるボロノイフィールドの値に比例して増加する。
【０００８】
次に、現在の車両位置または任意の位置から目的地までの横断コストの合計が最小となるように、車両の位置または任意の位置からルートをプロットする。
【０００９】
添付図面を参照しつつ以下に本発明を詳細に説明する。
【発明を実施するための最良の形態】
【００１０】
図１は本発明の具体例を示すボロノイ分割を示す図である。
【００１１】
図２はボロノイフィールドの具体例の立面図である。
【００１２】
先ず図１を参照すると、複数の障害物２２を有する幾何学エリア２０が示されている。これらの障害物は共に、障害物セットＯを形成する。
【００１３】
さらに図１を参照すると、ボロノイ分割２４がエリア２０上に作成される。ボロノイ分割２４を作成する際、ボロノイ分割の複数のエッジ２６は、各エッジ２６が２つの最も接近した障害物２２から等距離に離れるように形成される。これらのエッジ２６はさらに第２セットＶを形成する。
【００１４】
ボロノイ分割の作成後、全ての幾何学的位置（ｘ，ｙ）間の最小距離を下式（１）にしたがって決定できる。
【数１】
0005485533.tif 000002
【００１５】
その結果、図１における任意の点２８に対し、最も近い障害物２２までの最小距離が３０で示される。
【００１６】
同様に、各点とボロノイ分割２４のエッジ２６間の最小距離を下式（２）にしたがって決定できる。
【数２】
0005485533.tif 000003
【００１７】
このようにして、任意の点２８に対し、任意の点とボロノイ分割２４のエッジ２６間の最小距離が３２で示される。
【００１８】
各任意の幾何学的位置と最も接近したエッジ２６との間の最小距離ｄｖと同様に、エリア内の各幾何学的位置と最も接近した障害物２２との間の最小距離ｄｏが計算されると、ボロノイフィールドは下式（３）にしたがって定義できる。
【数３】
0005485533.tif 000004
【００１９】
ここで、ｐｖ＝フィールド、α＝定数＞０、β＝定数＞０、γ＝定数＞０である。
【００２０】
その結果、ボロノイフィールドを計算する式から理解されるように、ボロノイフィールドの値は、０と、この例において１として示される上限との間で変化する。ボロノイフィールドは、さらに、障害物内でのみ最大値１に到達し、逆にボロノイ分割のエッジ２６上でのみ最小値０に到達する。定数αを１００として選択し、定数β及びγを１として設定したボロノイフィールドの例を、図２に示す。
【００２１】
ボロノイフィールドｐｖはエリア２０の形状に自動的に適合する。より具体的には、障害物までの距離ｄｏが増加するに従って、フィールドは、狭い開口領域において急速に減少する。逆に、フィールドは、障害物が遠くに離れている領域においてよりゆっくり減少する。さらに、広範囲の引力ポテンシャル（ｇｌｏｂａｌ  ａｔｔｒａｃｔｉｖｅ  ｐｏｔｅｎｔｉａｌ）がエリア２０内に形成されたとき、凸状の対象物間で極小値を避けることができる。
【００２２】
ボロノイフィールドｐｖの計算は、どのような従来方式であっても実行できる。しかしながら、Ｃｈｏｓｅｔ、Ｌｙｎｃｈ、Ｈｕｔｃｈｉｎｓｏｎ、Ｋａｎｔｏｒ、Ｂｕｒｇａｒｄ、ＫａｖｒａｋｉおよびＴｈｒｕｎ等（２００５年）により開示されたように、２位相グリッドベースの局地的アルゴリズムは、計算の効率化に対して好ましい。
【００２３】
エリア２４内のボロノイフィールドの計算の次に、エリア２０内の任意の点３４とそのエリア内の目的地３６との間の横断コストが計算される。より具体的には、下記式（４）を実行することによって、１つのセルからその隣接するセルへの回転半径（ｔｕｒｎｉｎｇ  ｒａｄｉｕｓ）が回転半径制限ｄθｍａｘを確実に満たす様に、θにより横断方向が示されるグリッドセル（ｘ０，ｙ０，θ０）からその隣接するセル（ｘ１，ｙ１，θ１）への横断コストを、最初に調べる。
【数４】
0005485533.tif 000005
【００２４】
方向θ０におけるセル（ｘ０、ｙ０）において、方向θ１の隣接するセル（ｘ１、ｙ１）への車両３４の回転制限（ｔｕｒｎｉｎｇ  ｃｏｎｓｔｒａｉｎｔｓ）が満足されていない場合、これら２つの隣接するセル間の横断コストは、例えば無限大のような非常に高い値に設定される。
【００２５】
同様に、隣接するセル間を横断するときに障害物２２に遭遇すると、横断コストはこれら２つのセルに対し、例えば無限大のような非常に高い値に設定される。
【００２６】
しかしながら、車両の回転半径制限が満足され且つ障害物に遭遇しないと仮定すると、横断コストΔ（ｘ０，ｙ０，θ０，ｘ１，ｙ１，θ１）は下式（５）にしたがって計算される。
【数５】
0005485533.tif 000006
【００２７】
上記横断コストは、例えば車両３４の位置である選択された点から目的地３６までの、エリア２０内の全てのグリッドに対して計算される。
【００２８】
始点から目的地への横断コストの合計を最小にするように、ルート３８がプロットされる。プロットされたルートは、車両のオペレータに指示するか、または車両の動作を自動的に制御するために使用できる。
【００２９】
ルート３８がプロットされた後、一般的なスムージングアルゴリズムをプロットされたルート上で使用することができる。
【００３０】
以上の説明から、本発明が新規な障害物衝突回避付き車両ナビゲーションシステムを提供し、既知のシステムの欠点を克服することが理解できる。特に、フィールドは車両が障害物に接近するにつれてその値を増加させるので、障害物との衝突の危険性が回避される。同様に、比較的狭い通路を通る車両のナビゲーションに対して、本発明の方法を適応させることができる。
【００３１】
以上、本発明を説明したが、当該技術分野に通常の知識を有するものが、添付の特許請求の範囲における請求項により定義された発明の精神を逸脱することなく、本発明を種々に変更できることは明白である。
【図面の簡単な説明】
【００３２】
【図１】本発明の具体例を示すボロノイ分割を示す図である。
【図２】ボロノイフィールドの具体例の立面図である。
【図１】
0005485533.tif 000008
【図２】
0005485533.tif 000009