経路生成装置及び経路生成方法
【課題】障害物の特性に応じて始点から終点までの経路を生成することが可能な経路生成装置及び経路生成方法を提供する。
【解決手段】まず、始点より終点への到達性を保証できる手段により経路を生成し、次に、障害物の特性に応じた境界条件を用いて経路を変形する。
【効果】始点より終点への到達性を確保しつつ、障害物の特性に応じた経路を生成できる。
【解決手段】まず、始点より終点への到達性を保証できる手段により経路を生成し、次に、障害物の特性に応じた境界条件を用いて経路を変形する。
【効果】始点より終点への到達性を確保しつつ、障害物の特性に応じた経路を生成できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、始点から終点までの経路を生成する経路生成装置及び経路生成方法に関する。
【背景技術】
【０００２】
障害物を含む空間中の移動経路を生成する方法として、対象の空間にポテンシャルを定義し、最急勾配方向へ移動することで経路を生成する方法がある（例えば、非特許文献１参照）。
【非特許文献１】Connolly,“Path Planning Using Laplace's Equation”, proc. IEEERobotics and Automation Conference, pp2102-2106,1990
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来のラプラスポテンシャルによる経路生成では、始点より終点への到達可能な経路の生成を保証しようとすると、境界条件に拘束が必要なため、障害物の特性に応じた経路の制御が難しくなる。そこで、境界条件を任意に設定すると、障害物の特性に応じた経路の制御が可能であるものの、極小点への落ち込みによるデッドロックが発生し、終点への到達性を保証することが困難になる。
【０００４】
本発明は、上記の問題点を考慮してなされたものであり、障害物の特性に応じて始点から終点までの経路を生成することが可能な経路生成装置及び経路生成方法を提供する。
【課題を解決するための手段】
【０００５】
本発明による経路生成装置及び経路生成方法においては、所望の特性をもつ経路を得るために、まず、始点より終点への到達性を保証できる手段により経路を生成し、次に、障害物の特性に応じた境界条件を用いて経路を変形する。
【発明の効果】
【０００６】
本発明によれば、始点より終点への到達性を確保しつつ、障害物の特性に応じた経路を生成できる。
【発明を実施するための最良の形態】
【０００７】
障害物領域および非障害物領域が定義された二次元以上の空間が与えられたとして、始点および終点を非障害物領域内に定義する。始点および終点は非障害物領域のみを辿って到達できる領域内にあるものとする。
【０００８】
まず、第一のステップとして、大きく迂回させたい障害物か否かの区別をせず、全ての障害物を同一の扱いとして、公知のNeumannまたはDirichletの境界条件、或いは両者の混合境界条件を適用したラプラス調和関数を用いたポテンシャル場を生成する。同ポテンシャルの最急勾配により、始点より終点への経路を生成する。
【０００９】
次に、第二のステップとして、大きく迂回させたい障害物か否かなど、障害物の特性に応じた境界条件を設定し、ポテンシャル場を算出する。この第二のステップにて生成したポテンシャル値の勾配を用い、第一のステップで求めた経路を変形させる。
【実施例】
【００１０】
図１は、本発明の１実施例である経路生成装置を示す。入力装置１により、経路の始点や終点，障害物特性データなど、経路生成動作に関する可変データを入力する。始点，終点，境界条件，障害物フラグａ設定装置５により、障害物形状データ保持装置４のデータを参照しつつ、始点，終点，境界条件及び障害物フラグａを設定／保持する。ポテンシャル場ａ算出／保持装置６により、始点より終点への到達性のあるポテンシャル場を生成しその値を保持する。経路生成処理装置７により、上記ポテンシャル場ａの最急勾配を辿ることで経路を生成し、そのウェイポイントを経路データａ保持装置８にて保持する。境界条件，障害物フラグｂ設定装置１０において、障害物特性データ保持装置９のデータを参照しつつ、境界条件，障害物フラグｂを設定／保持する。ポテンシャル場ｂ算出／保持装置１１により、障害物の特性に応じたポテンシャル場を生成しその値を保持する。経路変形処理装置１２は、ポテンシャル場ｂ算出／保持装置１１にて保持しているポテンシャル場ｂ及び、経路データａ保持装置８にて保持している経路データａを用い、経路の変形処理を行い、その結果を経路データｂ保持装置１３に出力する。経路データｂ保持装置１３に保持される変形処理された経路データは、出力装置３により、画像データや文字データなどとして出力される。なお、入力装置１としてはキーボードやポインティングデバイスなどが適用でき、出力装置３としてはディスプレイ装置などが適用できる。また、経路生成処理装置２としては、ＣＰＵやＭＰＵなどの演算処理装置が適用でき、記憶装置としては半導体メモリやハードディスクなどが適用できる。
【００１１】
図１に示した経路生成装置において、入力装置１と出力装置３を一体化した端末装置とし、かつ一点鎖線で囲んだ部分をサーバー化することもできる。この場合、例えば、経路生成処理装置を内蔵するサーバーを管理センターやサービスセンターに設置し、サーバーで作成した経路データを、建物内などを歩行する歩行者が携帯する携帯端末や車両に搭載される移動端末に無線で配信する。
【００１２】
また、図１に示した経路生成装置は、入力装置１，出力装置３及び一点鎖線で囲んだ部分を、携帯端末及び移動端末に内蔵しても良い。
【００１３】
図２は、本発明の１実施例である経路生成方法を示す。図２（ａ）に示す概略フローのように、まず、始点より終点までの到達性を確保した方法により経路を生成し（ステップ１１０１）、次に、経路変形の制御性を重視した方法により、ステップ１１０１にて生成した経路を、障害物に付与した特性に応じて変形する（ステップ１１０２）。
【００１４】
図２（ｃ）は、経路生成の様子を概略図にて示す。１１１０は通行が出来ない障害物領域である。１１１１は通行が可能な非障害物領域である。ここで、移動体（例えば、歩行者）は始点１１１２（Ｓ）より出発し、終点１１１３（Ｇ）を目的地として移動するものとする。１１１４は、障害物領域のうち大きく迂回させたい領域（以下斥力オブジェクトと記す）である。逆に１１１５は接近させたい障害物領域(以下引力オブジェクトと記す)である。１１１６は図２（ａ）ステップ１１０１による経路生成結果で、障害物の特性とは無関係に始点１１１２より終点１１１３へ到達する経路となっている。１１１７はステップ１１０２による経路生成結果で、斥力オブジェクト１１１４より離れ、引力オブジェクト１１１５に近づく経路となっている。尚、接近させたい障害物領域１１１５は、内部通行が不可能な障害物として定義しても良いし、内部通行が可能な領域として定義しても良い。前者は、例えば視覚障害者向けの経路の生成において、安全な壁に沿った経路を生成する場合に適用できる。後者は、やはり視覚障害者向け経路の生成において、点字ブロック領域など内部の通行が可能な領域を通る経路を生成する場合に適用可能である。
【００１５】
図２（ｂ）は、本実施例のフローをより具体化した例を示す。図２（ａ）のステップ
１１０１の具体的一例として、極小点を持たないポテンシャルによる経路の生成が挙げられる（ステップ１１０３）。なお、ポテンシャルを用いた方法以外にも、空間を構造化することで、非障害物領域中に生成したノードを辿り、経路を生成する方法などがある。次に、図２（ａ）のステップ１１０２の具体的一例として、障害物の属性に応じた第二のポテンシャル場を用いて経路を変形する方法が挙げられる（ステップ１１０４）。
【００１６】
図３は図２の実施例の詳細フロー、図４は図３における各動作の説明図である。
【００１７】
図３の詳細フローの内、１２０２〜１２０４は、図２（ａ）のステップ１１０１又は図２（ｂ）のステップ１１０３に相当する。同様にステップ１２０５〜１２０７は、図２
（ａ）のステップ１１０２又は図２（ｂ）のステップ１１０４に相当する。まず、ステップ１２０１にて、始点１１１２および終点１１１３を設定する。次に、ステップ１２０２において、初期条件として、斥力オブジェクト１１１４及び、引力オブジェクト１１１５及び一般オブジェクト（上記二種のオブジェクト以外の引力及び斥力の何れも発生させない障害物領域）それぞれに、障害物フラグを設定する。また、非障害物領域に非障害物フラグを設定する。さらに、上記、障害物フラグを設定した領域と非障害物フラグを設定した領域との境界条件としてラプラス調和関数のNeumann境界条件、或いはDirichlet境界条件、或いは両者混合の境界条件を設定する。ここで、ラプラス調和関数によるポテンシャルとは（式１）を満たすポテンシャルである。
【００１８】
【数１】
【００１９】
（式１）において、Φがポテンシャル、ｘ，ｙは空間座標値である。同式では２次元の場合を示しているが、一般的に座標値をｎ個用いたｎ次元の場合についても同様の式で表される。次にNeumannの境界条件は（式２）で示される。
【００２０】
【数２】
【００２１】
ここで、∂Ωは障害物領域の輪郭、∂ｎは、障害物領域の法線ベクトルである。同境界条件は、障害物領域の境界から直角方向のポテンシャルの変化が無いことを示している。一方Dirichletの境界条件は（式３）で示される。
【００２２】
【数３】
【００２３】
ここで、∂Ωは障害物領域の輪郭である。同境界条件は、障害物領域境界でのポテンシャル値は常に一定であることを示している。Neumannの境界条件とDirichletの境界条件の混合境界条件とは、（式４）に示すとおり、係数ｋにより両者の境界値を混合するものである。
【００２４】
【数４】
【００２５】
一般にｋは適宜調整する。上記フラグ及び境界条件に基づき、極小点をもたないポテンシャル場を生成する（ステップ１２０３）。計算例としては、（式５）をイテレーションで解くガウス＝サイデル法などがある。
【００２６】
【数５】
【００２７】
ステップ１２０３で生成したポテンシャル場を用い、始点より最急勾配方向を辿ることにより、終点へ達する経路を生成し、同経路をある間隔でサンプリングしたウェイポイントを保存する（ステップ１２０８）。
【００２８】
次に、ステップ１２０５において、初期条件として、斥力オブジェクト１１１４及び、引力オブジェクト１１１５それぞれに、障害物フラグを設定する。また、一般オブジェクト及び非障害物領域に非障害物フラグを設定する。障害物フラグを設定した領域と非障害物フラグを設定した領域との境界条件として、斥力オブジェクトと非障害物領域との境界には斥力の境界値、引力オブジェクトと非障害物領域との境界には引力の境界値を設定する。上記境界値に設定する値は、以降のステップ１２０７におけるウェイポイントの修正で、−grad（Φ）方向に位置を修正すると仮定した場合、斥力オブジェクトに正の値、及び引力オブジェクトに負の値を設定する。ここでgrad演算とは、（式６）に示す演算である。
【００２９】
【数６】
【００３０】
符号を除く値の絶対値は、障害物の特性に応じ増減させる。例えば大きく迂回したい障害物には、小さく迂回したい障害物より大きな正の値を設定する。引力オブジェクトに関しても、同様に絶対値にて調整する。
【００３１】
上記フラグ及び境界条件に基づき、ポテンシャル場を生成する（ステップ１２０６）。ポテンシャル場の生成においては、空間中の着目点の周囲の障害物フラグをチェックすることにより、障害物領域或いは非障害物領域或いは両者の境界領域かの判定を行う。判定結果に基づき、前述のNeumann境界条件、或いはDirichlet境界条件、或いは両者の混合境界条件を適用し、演算を行う。
【００３２】
ステップ１２０６で生成されるポテンシャル場は、オブジェクトからの距離の増大に伴い、正のポテンシャル値が単調に減少する（負のポテンシャル値が単調に増加する）ものであれば良い。
【００３３】
次に、ステップ１２０８で保存された経路のウェイポイントの位置を、ステップ1206にて生成したポテンシャル場の勾配を用いて修正する（ステップ１２０７）。そして、ステップ１２０７で生成された、引力・斥力を考慮した経路のウェイポイントを保存する（ステップ１２０９）。以下にステップ１２０６における修正の具体例を示す。修正前の座標値を（ｘa，ｙa）とし、ステップ１２０６で生成されるポテンシャル場をΦb とする。
（式６）に示すGradient 演算により最急勾配方向が−grad（Φb）＝（ｘb，ｙb）のとき、変形後のウェイポイント（ｘ，ｙ）を（ｘ，ｙ）＝（ｘa＋ｃｘb，ｙa＋ｃｙb）とする。ｃは係数であり、引力／斥力オブジェクトに付与した境界値に依存して変わるため、実験的に調整する。
【００３４】
図４（ａ）は、図３のステップ１２０１に相当し、始点１１１２及び終点１１１３を連続する非障害物領域内に設定した例である。図４（ｂ）は、ステップ１２０２，１２０３で生成されたポテンシャル場の例である。同図は、ポテンシャル場の、最急勾配方向を、規格化した大きさのベクトル１３０３で示している。図４（ｃ）は、ステップ１２０４に相当し、障害物の特性とは無関係に始点１１１２より終点１１１３へ到達する経路を生成した例である。図４（ｄ）は、ステップ１２０５〜１２０６に相当し、斥力オブジェクト及び引力オブジェクトに、適切なポテンシャル値による境界条件を与え、算出したポテンシャル値に関し、最大勾配方向のみをベクトルで模式的に示している（便宜上、引力オブジェクト及び斥力オブジェクトの周囲のみ表示）。図４（ｅ）は、ステップ１２０７に相当し、ウェイポイントの位置の修正の例である。１３０１が位置修正前のウェイポイント（１２０８の保存データ）、１３０２が位置修正後のウェイポイント（１２０９の保存データ）である。１３０１の各ウェイポイント位置における第二のステップによるポテンシャルの勾配ベクトルの方向及び大きさにより（図４(ｄ)，ステップ１２０５〜１２０６）、位置をシフトさせることで、修正後のウェイポイント１３０２の位置としている。図４（ｆ）の１１１７が、障害物の特性を反映させ最終的に生成された経路である。
【００３５】
図５は、障害物フラグの利用方法及びポテンシャル値の演算の例を示すフローである。まず着目点を設定し２１０１、その座標点における障害物フラグをチェックする２１０２。チェックの結果、境界付近であれば、前述のNeumann境界条件、或いはDirichlet境界条件、或いは両者の混合境界条件など、所定の境界条件に従い、ポテンシャル値の演算を行う２１０４。自由空間内であれば、自由空間におけるポテンシャルの計算２１０３を行う。障害物フラグが設定されかつ、境界付近でない場合は、演算を行わない。これを次の着目点がなくなるまでループする２１０５。
【００３６】
本実施例の経路生成法を、視覚障害者向けの誘導経路の生成に適用すれば、危険箇所を大きく迂回させた経路を生成できる。同様に視覚障害者向けとして、点字ブロックや安全な壁など、位置を認識しやすい経路を生成することが可能であるため、安全性向上につながる。同様に、電動カートや電動車椅子，自動走行ロボットなど自律移動体向けの経路生成に適用した場合にも、走行に適さない箇所を大きく迂回し、走行に適した箇所を出来るだけ多く通行する経路を生成可能である。また、多関節ロボットアームの制御においてはクリアランスを大きく取りたい箇所がある場合に対応した経路を生成できる。
【００３７】
なお、上記実施例に限らず、本発明の技術的思想の範囲内において、種々の変形例が可能である。例えば、図２（ｃ）や図４に示したように、上記実施例においては、経路が生成される空間が２次元であったが、本発明は２次元以上の任意の次元の空間に適用可能である。また、本発明による経路形成方法は、コンピュータプログラムとして、コンパクトディスクなどのプログラム媒体に記録することができる。そして、このプログラム媒体からパーソナルコンピュータなどにソフトウェアをインストールすることにより、本発明による経路形成方法を実行することができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の１実施例である経路生成装置を示す。
【図２】本発明の１実施例である経路生成方法を示す。
【図３】図２の実施例の詳細フローを示す。
【図４】図３における各動作の説明図を示す。
【図５】境界付近での障害物フラグの利用方法及びポテンシャル値の演算を示すフロー。
【符号の説明】
【００３９】
１…入力装置、３…出力装置、４…障害物形状データ保持装置、５…始点，終点，境界条件，障害物フラグａ設定装置、６…ポテンシャル場ａ算出／保持装置、７…経路生成処理装置、８…経路データａ保持装置、９…障害物特性データ保持装置、１０…境界条件，障害物フラグｂ設定装置、１１…ポテンシャル場ｂ算出／保持装置、１２…経路変形処理装置、１３…経路データｂ保持装置。
【技術分野】
【０００１】
本発明は、始点から終点までの経路を生成する経路生成装置及び経路生成方法に関する。
【背景技術】
【０００２】
障害物を含む空間中の移動経路を生成する方法として、対象の空間にポテンシャルを定義し、最急勾配方向へ移動することで経路を生成する方法がある（例えば、非特許文献１参照）。
【非特許文献１】Connolly,“Path Planning Using Laplace's Equation”, proc. IEEERobotics and Automation Conference, pp2102-2106,1990
【発明の開示】
【発明が解決しようとする課題】
【０００３】
従来のラプラスポテンシャルによる経路生成では、始点より終点への到達可能な経路の生成を保証しようとすると、境界条件に拘束が必要なため、障害物の特性に応じた経路の制御が難しくなる。そこで、境界条件を任意に設定すると、障害物の特性に応じた経路の制御が可能であるものの、極小点への落ち込みによるデッドロックが発生し、終点への到達性を保証することが困難になる。
【０００４】
本発明は、上記の問題点を考慮してなされたものであり、障害物の特性に応じて始点から終点までの経路を生成することが可能な経路生成装置及び経路生成方法を提供する。
【課題を解決するための手段】
【０００５】
本発明による経路生成装置及び経路生成方法においては、所望の特性をもつ経路を得るために、まず、始点より終点への到達性を保証できる手段により経路を生成し、次に、障害物の特性に応じた境界条件を用いて経路を変形する。
【発明の効果】
【０００６】
本発明によれば、始点より終点への到達性を確保しつつ、障害物の特性に応じた経路を生成できる。
【発明を実施するための最良の形態】
【０００７】
障害物領域および非障害物領域が定義された二次元以上の空間が与えられたとして、始点および終点を非障害物領域内に定義する。始点および終点は非障害物領域のみを辿って到達できる領域内にあるものとする。
【０００８】
まず、第一のステップとして、大きく迂回させたい障害物か否かの区別をせず、全ての障害物を同一の扱いとして、公知のNeumannまたはDirichletの境界条件、或いは両者の混合境界条件を適用したラプラス調和関数を用いたポテンシャル場を生成する。同ポテンシャルの最急勾配により、始点より終点への経路を生成する。
【０００９】
次に、第二のステップとして、大きく迂回させたい障害物か否かなど、障害物の特性に応じた境界条件を設定し、ポテンシャル場を算出する。この第二のステップにて生成したポテンシャル値の勾配を用い、第一のステップで求めた経路を変形させる。
【実施例】
【００１０】
図１は、本発明の１実施例である経路生成装置を示す。入力装置１により、経路の始点や終点，障害物特性データなど、経路生成動作に関する可変データを入力する。始点，終点，境界条件，障害物フラグａ設定装置５により、障害物形状データ保持装置４のデータを参照しつつ、始点，終点，境界条件及び障害物フラグａを設定／保持する。ポテンシャル場ａ算出／保持装置６により、始点より終点への到達性のあるポテンシャル場を生成しその値を保持する。経路生成処理装置７により、上記ポテンシャル場ａの最急勾配を辿ることで経路を生成し、そのウェイポイントを経路データａ保持装置８にて保持する。境界条件，障害物フラグｂ設定装置１０において、障害物特性データ保持装置９のデータを参照しつつ、境界条件，障害物フラグｂを設定／保持する。ポテンシャル場ｂ算出／保持装置１１により、障害物の特性に応じたポテンシャル場を生成しその値を保持する。経路変形処理装置１２は、ポテンシャル場ｂ算出／保持装置１１にて保持しているポテンシャル場ｂ及び、経路データａ保持装置８にて保持している経路データａを用い、経路の変形処理を行い、その結果を経路データｂ保持装置１３に出力する。経路データｂ保持装置１３に保持される変形処理された経路データは、出力装置３により、画像データや文字データなどとして出力される。なお、入力装置１としてはキーボードやポインティングデバイスなどが適用でき、出力装置３としてはディスプレイ装置などが適用できる。また、経路生成処理装置２としては、ＣＰＵやＭＰＵなどの演算処理装置が適用でき、記憶装置としては半導体メモリやハードディスクなどが適用できる。
【００１１】
図１に示した経路生成装置において、入力装置１と出力装置３を一体化した端末装置とし、かつ一点鎖線で囲んだ部分をサーバー化することもできる。この場合、例えば、経路生成処理装置を内蔵するサーバーを管理センターやサービスセンターに設置し、サーバーで作成した経路データを、建物内などを歩行する歩行者が携帯する携帯端末や車両に搭載される移動端末に無線で配信する。
【００１２】
また、図１に示した経路生成装置は、入力装置１，出力装置３及び一点鎖線で囲んだ部分を、携帯端末及び移動端末に内蔵しても良い。
【００１３】
図２は、本発明の１実施例である経路生成方法を示す。図２（ａ）に示す概略フローのように、まず、始点より終点までの到達性を確保した方法により経路を生成し（ステップ１１０１）、次に、経路変形の制御性を重視した方法により、ステップ１１０１にて生成した経路を、障害物に付与した特性に応じて変形する（ステップ１１０２）。
【００１４】
図２（ｃ）は、経路生成の様子を概略図にて示す。１１１０は通行が出来ない障害物領域である。１１１１は通行が可能な非障害物領域である。ここで、移動体（例えば、歩行者）は始点１１１２（Ｓ）より出発し、終点１１１３（Ｇ）を目的地として移動するものとする。１１１４は、障害物領域のうち大きく迂回させたい領域（以下斥力オブジェクトと記す）である。逆に１１１５は接近させたい障害物領域(以下引力オブジェクトと記す)である。１１１６は図２（ａ）ステップ１１０１による経路生成結果で、障害物の特性とは無関係に始点１１１２より終点１１１３へ到達する経路となっている。１１１７はステップ１１０２による経路生成結果で、斥力オブジェクト１１１４より離れ、引力オブジェクト１１１５に近づく経路となっている。尚、接近させたい障害物領域１１１５は、内部通行が不可能な障害物として定義しても良いし、内部通行が可能な領域として定義しても良い。前者は、例えば視覚障害者向けの経路の生成において、安全な壁に沿った経路を生成する場合に適用できる。後者は、やはり視覚障害者向け経路の生成において、点字ブロック領域など内部の通行が可能な領域を通る経路を生成する場合に適用可能である。
【００１５】
図２（ｂ）は、本実施例のフローをより具体化した例を示す。図２（ａ）のステップ
１１０１の具体的一例として、極小点を持たないポテンシャルによる経路の生成が挙げられる（ステップ１１０３）。なお、ポテンシャルを用いた方法以外にも、空間を構造化することで、非障害物領域中に生成したノードを辿り、経路を生成する方法などがある。次に、図２（ａ）のステップ１１０２の具体的一例として、障害物の属性に応じた第二のポテンシャル場を用いて経路を変形する方法が挙げられる（ステップ１１０４）。
【００１６】
図３は図２の実施例の詳細フロー、図４は図３における各動作の説明図である。
【００１７】
図３の詳細フローの内、１２０２〜１２０４は、図２（ａ）のステップ１１０１又は図２（ｂ）のステップ１１０３に相当する。同様にステップ１２０５〜１２０７は、図２
（ａ）のステップ１１０２又は図２（ｂ）のステップ１１０４に相当する。まず、ステップ１２０１にて、始点１１１２および終点１１１３を設定する。次に、ステップ１２０２において、初期条件として、斥力オブジェクト１１１４及び、引力オブジェクト１１１５及び一般オブジェクト（上記二種のオブジェクト以外の引力及び斥力の何れも発生させない障害物領域）それぞれに、障害物フラグを設定する。また、非障害物領域に非障害物フラグを設定する。さらに、上記、障害物フラグを設定した領域と非障害物フラグを設定した領域との境界条件としてラプラス調和関数のNeumann境界条件、或いはDirichlet境界条件、或いは両者混合の境界条件を設定する。ここで、ラプラス調和関数によるポテンシャルとは（式１）を満たすポテンシャルである。
【００１８】
【数１】
【００１９】
（式１）において、Φがポテンシャル、ｘ，ｙは空間座標値である。同式では２次元の場合を示しているが、一般的に座標値をｎ個用いたｎ次元の場合についても同様の式で表される。次にNeumannの境界条件は（式２）で示される。
【００２０】
【数２】
【００２１】
ここで、∂Ωは障害物領域の輪郭、∂ｎは、障害物領域の法線ベクトルである。同境界条件は、障害物領域の境界から直角方向のポテンシャルの変化が無いことを示している。一方Dirichletの境界条件は（式３）で示される。
【００２２】
【数３】
【００２３】
ここで、∂Ωは障害物領域の輪郭である。同境界条件は、障害物領域境界でのポテンシャル値は常に一定であることを示している。Neumannの境界条件とDirichletの境界条件の混合境界条件とは、（式４）に示すとおり、係数ｋにより両者の境界値を混合するものである。
【００２４】
【数４】
【００２５】
一般にｋは適宜調整する。上記フラグ及び境界条件に基づき、極小点をもたないポテンシャル場を生成する（ステップ１２０３）。計算例としては、（式５）をイテレーションで解くガウス＝サイデル法などがある。
【００２６】
【数５】
【００２７】
ステップ１２０３で生成したポテンシャル場を用い、始点より最急勾配方向を辿ることにより、終点へ達する経路を生成し、同経路をある間隔でサンプリングしたウェイポイントを保存する（ステップ１２０８）。
【００２８】
次に、ステップ１２０５において、初期条件として、斥力オブジェクト１１１４及び、引力オブジェクト１１１５それぞれに、障害物フラグを設定する。また、一般オブジェクト及び非障害物領域に非障害物フラグを設定する。障害物フラグを設定した領域と非障害物フラグを設定した領域との境界条件として、斥力オブジェクトと非障害物領域との境界には斥力の境界値、引力オブジェクトと非障害物領域との境界には引力の境界値を設定する。上記境界値に設定する値は、以降のステップ１２０７におけるウェイポイントの修正で、−grad（Φ）方向に位置を修正すると仮定した場合、斥力オブジェクトに正の値、及び引力オブジェクトに負の値を設定する。ここでgrad演算とは、（式６）に示す演算である。
【００２９】
【数６】
【００３０】
符号を除く値の絶対値は、障害物の特性に応じ増減させる。例えば大きく迂回したい障害物には、小さく迂回したい障害物より大きな正の値を設定する。引力オブジェクトに関しても、同様に絶対値にて調整する。
【００３１】
上記フラグ及び境界条件に基づき、ポテンシャル場を生成する（ステップ１２０６）。ポテンシャル場の生成においては、空間中の着目点の周囲の障害物フラグをチェックすることにより、障害物領域或いは非障害物領域或いは両者の境界領域かの判定を行う。判定結果に基づき、前述のNeumann境界条件、或いはDirichlet境界条件、或いは両者の混合境界条件を適用し、演算を行う。
【００３２】
ステップ１２０６で生成されるポテンシャル場は、オブジェクトからの距離の増大に伴い、正のポテンシャル値が単調に減少する（負のポテンシャル値が単調に増加する）ものであれば良い。
【００３３】
次に、ステップ１２０８で保存された経路のウェイポイントの位置を、ステップ1206にて生成したポテンシャル場の勾配を用いて修正する（ステップ１２０７）。そして、ステップ１２０７で生成された、引力・斥力を考慮した経路のウェイポイントを保存する（ステップ１２０９）。以下にステップ１２０６における修正の具体例を示す。修正前の座標値を（ｘa，ｙa）とし、ステップ１２０６で生成されるポテンシャル場をΦb とする。
（式６）に示すGradient 演算により最急勾配方向が−grad（Φb）＝（ｘb，ｙb）のとき、変形後のウェイポイント（ｘ，ｙ）を（ｘ，ｙ）＝（ｘa＋ｃｘb，ｙa＋ｃｙb）とする。ｃは係数であり、引力／斥力オブジェクトに付与した境界値に依存して変わるため、実験的に調整する。
【００３４】
図４（ａ）は、図３のステップ１２０１に相当し、始点１１１２及び終点１１１３を連続する非障害物領域内に設定した例である。図４（ｂ）は、ステップ１２０２，１２０３で生成されたポテンシャル場の例である。同図は、ポテンシャル場の、最急勾配方向を、規格化した大きさのベクトル１３０３で示している。図４（ｃ）は、ステップ１２０４に相当し、障害物の特性とは無関係に始点１１１２より終点１１１３へ到達する経路を生成した例である。図４（ｄ）は、ステップ１２０５〜１２０６に相当し、斥力オブジェクト及び引力オブジェクトに、適切なポテンシャル値による境界条件を与え、算出したポテンシャル値に関し、最大勾配方向のみをベクトルで模式的に示している（便宜上、引力オブジェクト及び斥力オブジェクトの周囲のみ表示）。図４（ｅ）は、ステップ１２０７に相当し、ウェイポイントの位置の修正の例である。１３０１が位置修正前のウェイポイント（１２０８の保存データ）、１３０２が位置修正後のウェイポイント（１２０９の保存データ）である。１３０１の各ウェイポイント位置における第二のステップによるポテンシャルの勾配ベクトルの方向及び大きさにより（図４(ｄ)，ステップ１２０５〜１２０６）、位置をシフトさせることで、修正後のウェイポイント１３０２の位置としている。図４（ｆ）の１１１７が、障害物の特性を反映させ最終的に生成された経路である。
【００３５】
図５は、障害物フラグの利用方法及びポテンシャル値の演算の例を示すフローである。まず着目点を設定し２１０１、その座標点における障害物フラグをチェックする２１０２。チェックの結果、境界付近であれば、前述のNeumann境界条件、或いはDirichlet境界条件、或いは両者の混合境界条件など、所定の境界条件に従い、ポテンシャル値の演算を行う２１０４。自由空間内であれば、自由空間におけるポテンシャルの計算２１０３を行う。障害物フラグが設定されかつ、境界付近でない場合は、演算を行わない。これを次の着目点がなくなるまでループする２１０５。
【００３６】
本実施例の経路生成法を、視覚障害者向けの誘導経路の生成に適用すれば、危険箇所を大きく迂回させた経路を生成できる。同様に視覚障害者向けとして、点字ブロックや安全な壁など、位置を認識しやすい経路を生成することが可能であるため、安全性向上につながる。同様に、電動カートや電動車椅子，自動走行ロボットなど自律移動体向けの経路生成に適用した場合にも、走行に適さない箇所を大きく迂回し、走行に適した箇所を出来るだけ多く通行する経路を生成可能である。また、多関節ロボットアームの制御においてはクリアランスを大きく取りたい箇所がある場合に対応した経路を生成できる。
【００３７】
なお、上記実施例に限らず、本発明の技術的思想の範囲内において、種々の変形例が可能である。例えば、図２（ｃ）や図４に示したように、上記実施例においては、経路が生成される空間が２次元であったが、本発明は２次元以上の任意の次元の空間に適用可能である。また、本発明による経路形成方法は、コンピュータプログラムとして、コンパクトディスクなどのプログラム媒体に記録することができる。そして、このプログラム媒体からパーソナルコンピュータなどにソフトウェアをインストールすることにより、本発明による経路形成方法を実行することができる。
【図面の簡単な説明】
【００３８】
【図１】本発明の１実施例である経路生成装置を示す。
【図２】本発明の１実施例である経路生成方法を示す。
【図３】図２の実施例の詳細フローを示す。
【図４】図３における各動作の説明図を示す。
【図５】境界付近での障害物フラグの利用方法及びポテンシャル値の演算を示すフロー。
【符号の説明】
【００３９】
１…入力装置、３…出力装置、４…障害物形状データ保持装置、５…始点，終点，境界条件，障害物フラグａ設定装置、６…ポテンシャル場ａ算出／保持装置、７…経路生成処理装置、８…経路データａ保持装置、９…障害物特性データ保持装置、１０…境界条件，障害物フラグｂ設定装置、１１…ポテンシャル場ｂ算出／保持装置、１２…経路変形処理装置、１３…経路データｂ保持装置。
【特許請求の範囲】
【請求項１】
経路の始点及び終点を設定する入力装置と、前記始点から前記終点への経路を生成する処理装置とを有する経路生成装置において、
前記処理装置は、前記始点から前記終点への到達可能な経路を生成し、さらに障害物の特性に応じて、生成した前記経路を変形することを特徴とする経路生成装置。
【請求項２】
請求項１において、前記処理装置は、前記経路の生成及び変形において、それぞれポテンシャル場を用い、かつそれぞれ異なる境界条件を用いることを特徴とする経路生成装置。
【請求項３】
請求項２において、前記処理装置は、Neumannの境界条件或いはDirichletの境界条件或いは両者の混合境界条件を適用したラプラス調和関数を用いたポテンシャル場を用いて前記経路を生成し、障害物の特性に応じた境界条件を適用したポテンシャル場を用いて前記経路を変形することを特徴とする経路生成装置。
【請求項４】
始点から終点までの経路を生成する経路生成方法において、
始点より終点まで到達可能な経路を生成する第１のステップと、
前記第１のステップで生成された経路の変形を行う第２のステップと、
を含むことを特徴とする経路生成方法。
【請求項５】
請求項４において、前記第１及び第２のステップにおいて、それぞれポテンシャル場を用い、かつそれぞれ異なる境界条件を用いることを特徴とする経路生成方法。
【請求項６】
請求項５において、前記第１のステップにおいては、Neumannの境界条件或いは
Dirichletの境界条件或いは両者の混合境界条件を適用したラプラス調和関数を用いたポテンシャル場を用いて前記経路を生成し、前記第２のステップにおいては、障害物の特性に応じた境界条件を適用したポテンシャル場を用いることを特徴とする経路生成方法。
【請求項７】
入力装置によって設定される始点から終点への経路を生成する処理装置を有する経路生成装置において、
前記処理装置は、前記始点から前記終点への到達可能な経路を生成し、さらに障害物の特性に応じて、生成した前記経路を変形することを特徴とする経路生成装置。
【請求項８】
経路生成方法をコンピュータプログラムとして記録するプログラム媒体において、前記経路形成方法は、始点より終点まで到達可能な経路を生成する第１のステップと、前記第１のステップで生成された経路の変形を行う第２のステップと、
を含むことを特徴とするプログラム媒体。
【請求項１】
経路の始点及び終点を設定する入力装置と、前記始点から前記終点への経路を生成する処理装置とを有する経路生成装置において、
前記処理装置は、前記始点から前記終点への到達可能な経路を生成し、さらに障害物の特性に応じて、生成した前記経路を変形することを特徴とする経路生成装置。
【請求項２】
請求項１において、前記処理装置は、前記経路の生成及び変形において、それぞれポテンシャル場を用い、かつそれぞれ異なる境界条件を用いることを特徴とする経路生成装置。
【請求項３】
請求項２において、前記処理装置は、Neumannの境界条件或いはDirichletの境界条件或いは両者の混合境界条件を適用したラプラス調和関数を用いたポテンシャル場を用いて前記経路を生成し、障害物の特性に応じた境界条件を適用したポテンシャル場を用いて前記経路を変形することを特徴とする経路生成装置。
【請求項４】
始点から終点までの経路を生成する経路生成方法において、
始点より終点まで到達可能な経路を生成する第１のステップと、
前記第１のステップで生成された経路の変形を行う第２のステップと、
を含むことを特徴とする経路生成方法。
【請求項５】
請求項４において、前記第１及び第２のステップにおいて、それぞれポテンシャル場を用い、かつそれぞれ異なる境界条件を用いることを特徴とする経路生成方法。
【請求項６】
請求項５において、前記第１のステップにおいては、Neumannの境界条件或いは
Dirichletの境界条件或いは両者の混合境界条件を適用したラプラス調和関数を用いたポテンシャル場を用いて前記経路を生成し、前記第２のステップにおいては、障害物の特性に応じた境界条件を適用したポテンシャル場を用いることを特徴とする経路生成方法。
【請求項７】
入力装置によって設定される始点から終点への経路を生成する処理装置を有する経路生成装置において、
前記処理装置は、前記始点から前記終点への到達可能な経路を生成し、さらに障害物の特性に応じて、生成した前記経路を変形することを特徴とする経路生成装置。
【請求項８】
経路生成方法をコンピュータプログラムとして記録するプログラム媒体において、前記経路形成方法は、始点より終点まで到達可能な経路を生成する第１のステップと、前記第１のステップで生成された経路の変形を行う第２のステップと、
を含むことを特徴とするプログラム媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００７−１５５５６８（Ｐ２００７−１５５５６８Ａ）
【公開日】平成１９年６月２１日（２００７．６．２１）
【国際特許分類】
【出願番号】特願２００５−３５２８２７（Ｐ２００５−３５２８２７）
【出願日】平成１７年１２月７日（２００５．１２．７）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成１９年６月２１日（２００７．６．２１）
【国際特許分類】
【出願日】平成１７年１２月７日（２００５．１２．７）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]