(57)【要約】【課題】複数の対象物があるエリアを通る車両のナビゲーションシステムを提供する。【解決手段】ボロノイ分解が障害物を囲む複数のエッジを有するようにエリア上に最初に構成される。０と有限値間に値を有するボロノイフィールドが障害物内の最大値に到達しエッジ上で最小値に到達するようにエリア内の幾何学的位置に対し計算される。車両の位置から目的地に向けたエリア内の隣接する位置の間の横断コストは、横断コストがフィールドの値に比例して増加するように計算される。ルートは車両の位置から目的地への横断コストを最小にするようにプランされる。【選択図】図１
2009104608.tif 000002
【特許請求の範囲】
【請求項１】
複数の障害物を有するエリアを通る車両ナビゲーション方法であって、
複数のエッジを有するボロノイ分解をエリア上に作成するステップと、
前記エリア内の幾何学的位置に対し０と上限値間に値を有するボロノイフィールドを該フィールドが前記障害物内の最大値に到達し、前記エッジ上で最小値に到達するように計算するステップと、
始点から目的地へ向かう前記エリア内の隣接する位置の間における横断コストであって前記ボロノイフィールドのコストに比例的に増加する横断コストを計算するステップと、
前記目的地への横断コストが最小となるルートをプロットするステップと、
を備えることを特徴とする障害物回避ナビゲーション方法。
【請求項２】
前記横断コストを計算するステップは、セル間の車両の方向が予め決定された車両の回転率の制限を満たすかを決定し、該制限を満たさない場合は前記計算された横断コストに高い値を割り当てるステップを備える、
請求項１に記載の障害物回避ナビゲーション方法。
【請求項３】
前記横断コストを計算するステップは、障害物が隣接する位置の間で出くわすときは何時でも前記計算された横断コストを高い値に割り当てるステップを備える、
請求項１に記載の障害物回避ナビゲーション方法。
【請求項４】
前記ボロノイフィールドは下式で定義される、
【数１】
2009104608.tif 000008
ここで、Ｐv ＝フィールド、α＝定数＞０、β＝定数＞０、γ＝定数＞０
請求項１に記載の障害物回避ナビゲーション方法。
【請求項５】
ルートをスムージングするステップを備える、
請求項１に記載の障害物回避ナビゲーション方法。
【請求項６】
前記始点は前記車両の前記位置に対応する、
請求項１に記載の障害物回避ナビゲーション方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して障害物回避用メカニズムを有する障害物エリアを通る車両ナビゲーション方法に関する。
【背景技術】
【０００２】
１つまたは複数の障害物を有するエリアを通る第１にロボットを案内する移動体ロボット用ナビゲーションシステムが知られている。このような公知のシステムはロボットを障害物から退けしたがって衝突を避ける種々の障害物に関連するポテンシャル場を提供する。これらの公知の試みはしかし動作上全てが満足するものではないことが分かった。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
これらのナビゲーションシステムの１つの欠点は、位置的フィールドが、横断できない狭い通路同様行き詰まりにおけるロボットを位置的に捕獲できる局所的最小の問題の対象となっていることにある。なお他の状況において、ロボットまたは自動車等の他の車両は障害物を避けるが走行中対象物に許容できないくらいに接近する。
【課題を解決するための手段】
【０００４】
本発明は障害物回避用の車両ナビゲーション方法を提供し公知の方法の上記欠点を克服するものである。
【０００５】
端的に、本発明のナビゲーションシステムは複数の障害物があるエリアで使用されるように設けられている。ボロノイ分解（Voronoi decomposition）は最初ボロノイ分解がエリア内における複数の対象物の各々を囲む複数のエッジを含むようにエリアを作成する。従来の計算手段がボロノイ分解を作成するために利用できる。
【０００６】
ボロノイフィールドは、０と上限の間の値を有し、エリア内の幾何学的位置の全てに対し計算する。ボロノイフィールドの値はエリア内に含まれる障害物内の最大値およびボロノイ分解のエッジ上の最小値に到達する。
【０００７】
車両の位置から目的地に向けたエリア内の隣接する位置またはグリッド間の横断コストが計算される。この横断コストはエリアを通った各隣接再配置におけるボロノイフィールドの値に比例して増加する。
【０００８】
ルートが車両の位置または任意の位置からプロットされ、現在の車両の位置または任意の位置から目的地への横断コストの合計を最小にする。
【０００９】
添付図面を参照しつつ以下に本発明を詳細に説明する。
【発明を実施するための最良の形態】
【００１０】
図１は本発明の具体例を示すボロノイ分解を示す図である。
【００１１】
図２はボロノイフィールドの具体例の正面図である。
【００１２】
先ず図１を参照すると、複数の障害物２２を有する幾何学エリア２０が示されている。これらの障害物は障害物（第１）セットＯを形成する。
【００１３】
さらに図１を参照すると、ボロノイ分解２４はエリア２０上に作成される。ボロノイ分解２４を作成する際、ボロノイ分解２４の複数のエッジ２６は各エッジ２６が２つの最も接近した障害物２２から等距離に離れるように形成される。これらのエッジ２６はさらに第２セットＶを形成する。
【００１４】
ボロノイ分解の作成後、何れの幾何学的位置（ｘ，ｙ）間の最小距離も下式（１）にしたがって決定できる。
【数１】
2009104608.tif 000003
【００１５】
その結果、図１における任意の点２８に対し最も接近した障害物２２への最小距離は３０で示される。
【００１６】
同様に各点とボロノイ分解２４のエッジ２６間の最小距離は下式（２）にしたがって決定できる。
【数２】
2009104608.tif 000004
【００１７】
このように、任意の点２８に対し、任意の点とボロノイ分解２４のエッジ２６間の最小距離は３２で示される。
【００１８】
各任意の幾何学的位置と最も接近したエッジ２６との間の最小距離ｄv 同様、エリア内の各幾何学的位置と最も接近した障害物２２との間の最小距離ｄo が計算された後、ボロノイフィールドは下式（３）にしたがって定義できる。
【数３】
2009104608.tif 000005
【００１９】
ここで、Ｐv ＝フィールド、α＝定数＞０、β＝定数＞０、γ＝定数＞０
【００２０】
結果として、ボロノイフィールドを計算する公式から分かるように、ボロノイフィールドは、この例において１として示される０と上限との間の値内で変化する。ボロノイフィールドは、さらに、障害物内にのみに１の最大値に到達し、逆にボロノイ分解のエッジ２６上にのみ０の最小値に到達する。１００に選択される定数α、１に選択される定数βおよび定数γを有するボロノイフィールドの例を図２に示す。
【００２１】
ボロノイフィールドｐv はエリア２０の形状に自動的に適合する。より特定的には障害物への距離ｄo は増加し、フィールドは狭く開いた領域においてすばやく減少する。逆に、フィールドは障害物が遠く離れた領域においてよりゆっくり減少する。さらに、球状の魅力あるポテンシャル（global attractive potential）がエリア２０内に設置されたとき、局所最小値が凸面対象物間で避けられる。
【００２２】
ボロノイフィールドｐv の計算は如何なる従来方式でも実行できる。しかしながら、Choset、Lynch、Hutchinson、Kantor、Burgard、KavrakiおよびThrun等（２００５）により開示されたように、２つの位相グリッドに基づいた局地的アルゴリズムは計算効率に好ましい。
【００２３】
エリア２４内のボロノイフィールドの計算に従い、エリア２０内の任意の点３４とエリア内の目的地３６との間の横断コストが計算される。より特定的には、１つのセルからその隣接するセルへの回転半径（turning radius）が下式（４）を実行することにより得られる回転半径の制限ｄθmax を満たすことを確実にするように、θにより横断方向が示されるグリッドセル（ｘ0，ｙ0，θ0）からその隣接するセル（ｘ1，ｙ1，θ1）への横断コストが、最初に調べられる。
【数４】
2009104608.tif 000006
【００２４】
車両３４の回転制限（turning constraints）が隣接するセル（ｘ1 ，ｙ1 ）への方向θ0 におけるセル（ｘ0 ，ｙ0 ）において方向θ1 だけ適合しないとき、これら２つの隣接するセル間の横断コストは例えば無限のように非常に高い値に設定される。
【００２５】
同様に、障害物２２が隣接するセル間で横断するときに出くわすならば、横断コストはこれら２つのセルに対し例えば無限のように非常に高い値に設定される。
【００２６】
しかしながら、車両の回転半径の制限が適合し出くわす障害物がないと仮定すると、横断コストΔ（ｘ0，ｙ0，θ0 ，ｘ1，ｙ1，θ1）は下式（５）にしたがって計算される。
【数５】
2009104608.tif 000007
【００２７】
上記横断コストは車両３４の位置のような選択された点から目的地３６へのエリア２０内の全てのグリッドに対して計算される。
【００２８】
始点から目的地へのルート３８はプロットされ、これら２つの位置の間の横断コストの合計を最小にする。プロットされたルートは車両の操作者を方向づけるかまたは車両の動作を自動的に制御するために使用できる。
【００２９】
ルート３８がプロットされた後、従来のスムージングアルゴリズムがプロットされたルート上で使用できる。
【００３０】
以上の説明から、本発明が新規な障害物衝突回避付き車両ナビゲーションシステムを提供し、すでに公知のシステムの欠点を克服することが理解できる。特に、フィールドは車両が障害物に接近するにつれて値が変化するので非常に近くの障害物の衝突が回避される。同様に比較的狭い通路を通る車両のナビゲーションは本発明の方法と適応できる。
【００３１】
以上、本発明を説明したが、当該技術分野に通常の知識を有するものが添付の特許請求の範囲における請求項により定義された発明の精神を逸脱することなく本発明を種々に変更できることは明白である。
【図面の簡単な説明】
【００３２】
【図１】本発明の具体例を示すボロノイ分解を示す図である。
【図２】ボロノイフィールドの具体例の正面図である。
【図１】
2009104608.tif 000009
【図２】
2009104608.tif 000010
【外国語明細書】
2009104608000001.pdf