(57)【要約】【課題】少ない計算コストで、障害物から一定距離以上離れた位置に、移動環境内の全通路を網羅できる最小限の経由点を配置可能な自律移動装置の経路生成方法、並びに経路生成プログラムを提供する。【解決手段】現在位置から目的地に至る経路を生成するための自律移動装置の経路生成方法であって、輪郭抽出部が障害物の情報を含む地図情報から障害物の輪郭を求め、曲率計算部が前記輪郭を構成する点である輪郭点の曲率を求め、経由点設定部が曲率を利用して算出される輪郭点が予め定めた経由点追加条件を満たす場合に、輪郭点から予め定めた距離に経由点を設定し、経路作成部が現在位置から、経由点を通過して目的地に至る経路を作成する自律移動装置の経路生成方法。【選択図】図１
2020160831.tif 000002
【特許請求の範囲】
【請求項１】
現在位置から目的地に至る経路を生成するための自律移動装置の経路生成方法であって、
輪郭抽出部が障害物の情報を含む地図情報から障害物の輪郭を求め、曲率計算部が前記輪郭を構成する点である輪郭点の曲率を求め、前記輪郭点が予め定めた経由点追加条件を満たす場合に、経由点設定部が，前記輪郭点から予め定めた距離に経由点を設定し、経路作成部が前記現在位置から、前記経由点を通過して前記目的地に至る経路を作成する自律移動装置の経路生成方法。
【請求項２】
請求項１に記載の自律移動装置の経路生成方法であって、
前記障害物の輪郭は、前記地図情報に描画された障害物の領域を所定の量だけ肥大させた肥大領域の輪郭である自律移動装置の経路生成方法。
【請求項３】
請求項１または請求項２に記載自律移動装置の経路生成方法であって、
経由点追加条件とは、前記輪郭に沿って右回りまたは左回りのいずれか一方向に順に輪郭点を選択して経由点追加条件を満たすかを判別して経由点を設定していった場合に，選択した輪郭点と，同じ輪郭から設定された経由点のうち最新の経由点までを結ぶ線分から、障害物の輪郭がはみ出る長さが所定の長さ以上である自律移動装置の経路生成方法。
【請求項４】
請求項１または請求項２に記載の自律移動装置の経路生成方法であって、
前記経由点追加条件は、前記輪郭点の曲率の絶対値が、所定の値より大きいことである自律移動装置の経路生成方法。
【請求項５】
請求項１に記載の自律移動装置の経路生成方法であって、
前記経由点追加条件は、輪郭に沿って右回りに輪郭点を求める場合は、曲率が負であることであり、輪郭に沿って左回りに輪郭点を求める場合は、曲率が正であること、という条件を含む自律移動装置の経路生成方法。
【請求項６】
請求項１に記載の自律移動装置の経路生成方法であって、
前記経由点設定時の輪郭点と経由点の距離は、輪郭点での曲率に応じて変化する自律移動装置の経路生成方法。
【請求項７】
請求項５に記載の自律移動装置の経路生成方法であって、
経由点設定時の輪郭点と経由点の距離は、輪郭点での曲率が大きいほど、長く設定される自律移動装置の経路生成方法。
【請求項８】
請求項１に記載の自律移動装置の経路生成方法であって、
前記現在位置と前記目的地と前記経由点についての各点間を結ぶ線分のうち、前記障害物の輪郭に抵触しない線分と前記各点のうち一定距離内にある点間を結ぶ線分で前記障害物の輪郭に抵触しない線分のいずれかを抽出し、抽出した線分を用いて現在位置から目的地に至る経路を生成する自律移動装置の経路生成方法。
【請求項９】
現在位置から目的地に至る経路を生成するための自律移動装置の経路生成プログラムであって、
障害物の情報を含む地図情報から障害物の輪郭を求める輪郭抽出部と、
前記輪郭を構成する点である輪郭点の曲率を求める曲率計算部と、
前記輪郭点が予め定めた経由点追加条件を満たす場合に、前記輪郭点から予め定めた距離に経由点を設定する経由点設定部と、
前記現在位置から、前記経由点を通過して前記目的地に至る経路を作成する経路作成部とを備える自律移動装置の経路生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば構内で運用する自律移動装置の経路生成方法、並びに経路生成プログラムに関する。
【背景技術】
【０００２】
ロボットや自動搬送装置などの例えば構内で運用する自律移動装置には、複雑に入り組んだ環境で目標地点まで到達するための経路を自動的に生成するための経路生成手法が必要である。
【０００３】
この点に関して従来の経路生成手法の多くは、自律移動装置が移動する環境内の障害物や通行不可能な領域を記録した地図に対して、複数の経由点を配置し、経由点同士を結ぶ経路の組み合わせをグラフ化し、グラフ理論的探索手法で最短経路を見つける手法を用いている。
【０００４】
しかし、多くの従来手法のようにランダムに大量の経由点を配置したり、グリッド状に多数の経由点を配置したりすると、経由点のグラフ化の計算コストが膨大となり実用上好ましくない。計算コスト軽減のためには、経由点を移動環境の形状に合わせて適切な位置に、最小限の個数だけ設定することが重要である。
【０００５】
そこで、例えば、特許文献１に記載の経路生成手法のように、地図画像上の移動可能な領域を画像処理によって細線化し、細線化された線分の端点や分岐点を経由点とし、線分そのものを経路候補とする手法などが提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許第６３０４７７１号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
特許文献１のように、画像の移動可能な領域の細線化に基づいた経路生成手法では、例えば広場などでは、壁際を通ったほうが移動距離が短いような場合でも広場の中心に経路ができてしまい、最短経路を生成できない。また、細線化処理は計算コストが高く、大きな地図画像に対して実行することは実用的ではない。理想的には、計算コストの少ない方法で、障害物から一定距離以上離れた位置に、移動環境内の全通路を網羅できる最小限の経由点が配置されればよいが、いずれの従来方法においても実現されていない。
【０００８】
以上のことから本発明においては、少ない計算コストで、障害物から一定距離以上離れた位置に、移動環境内の全通路を網羅できる最小限の経由点を配置可能な自律移動装置の経路生成方法、並びに経路生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、代表的な本発明の経路生成方法は、「現在位置から目的地に至る経路を生成するための自律移動装置の経路生成方法であって、輪郭抽出部が障害物の情報を含む地図情報から障害物の輪郭を求め、曲率計算部が前記輪郭を構成する点である輪郭点の曲率を求め、経由点設定部が曲率を利用して算出される輪郭点が予め定めた経由点追加条件を満たす場合に、輪郭点から予め定めた距離に経由点を設定し、経路作成部が現在位置から、経由点を通過して目的地に至る経路を作成する自律移動装置の経路生成方法」としたものである。
【００１０】
上記課題を解決するために、代表的な本発明の経路生成プログラムは、「現在位置から目的地に至る経路を生成するための自律移動装置の経路生成プログラムであって、障害物の情報を含む地図情報から障害物の輪郭を求める輪郭抽出部と、輪郭を構成する点である輪郭点の曲率を求める曲率計算部と、曲率を利用して算出される輪郭点が予め定めた経由点追加条件を満たす場合に、輪郭点から予め定めた距離に経由点を設定する経由点設定部と、現在位置から、経由点を通過して目的地に至る経路を作成する経路作成部とを備える自律移動装置の経路生成プログラム」としたものである。
【発明の効果】
【００１１】
本発明によれば、少ない計算コストで、障害物から一定距離以上離れた位置に、移動環境内の全通路を網羅できる経由点を配置可能な経路生成手法が提供できる。上記した以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００１２】
【図１】本発明に係る経路生成方法の処理の流れの例を示す図。
【図２】本発明に係る経路生成方法を実行する経路生成システム１の一例を示す図。
【図３】障害物の輪郭を求める考え方を示す図。
【図４】輪郭点の曲率を求める考え方を示す図。
【図５】曲率計算時のパラメータ設定方法の一例を説明する図。
【図６】経由点追加方法の考え方を示す図。
【図７】移動経路作成の考え方を示す図。
【図８】グラフ作成方法を説明する図。
【図９】作成されたグラフの一例を説明する図。
【図１０】実施例２での経由点追加条件を説明する図。
【図１１】実施例３での経由点追加方法を説明する図。
【発明を実施するための形態】
【００１３】
以下、本発明の実施例について図面を用いて説明する。
【実施例１】
【００１４】
自律移動装置は、例えば工場などの構内で運用され、構内の地図を参照し障害物を避けながら現在地点から目標地点に至る、生成された経路に沿って自律的に移動する。
【００１５】
本発明の実施例１では、自律移動装置の効率的な経路生成方法について説明する。図１は、効率的な経路生成を可能とする本発明に係る自律移動装置の経路生成方法の処理の流れの例を示す図である。
【００１６】
図１において、ステップＳ１では、障害物を含む地図から、障害物の輪郭を求める。ここで、障害物とは、実環境で通行を妨げている障害物だけでなく、安全性や利便性の都合上、自律移動装置の侵入を防ぐために人為的に設定された領域も含むものである。ステップＳ１の処理について図３を用いて詳細に後述する。
【００１７】
ステップＳ２では、ステップＳ１で求めた輪郭を構成する点（輪郭点と称す）での曲率を求める。後述する通り、本発明ではここで求めた曲率を利用することで、最短経路の効率的な算出だけでなく、安全面や機能面でも有用な様々な効果を生むことができる。ステップＳ２の処理について図４、図５を用いて詳細に後述する。
【００１８】
ステップＳ３では、輪郭点の曲率を元に算出される状態が既定の経由点追加条件を満たすかどうかを評価する。本ステップでの、経由点追加条件の設定次第で、追加される経由点の性質を変えることが可能である。
【００１９】
ステップＳ３において輪郭点が経由点追加条件を満たしていれば、ステップＳ４へすすみ、輪郭点から既定の距離の位置に経由点を追加する。前記距離は、あらかじめ設定した一定の距離でもよいが、実施例３で述べる通り、曲率に合わせて可変な距離に設定することも、経路の安全性や機能性の調整に有効である。ステップＳ３、Ｓ４の処理について図６、図７、図８を用いて詳細に後述する。
【００２０】
ステップＳ３で経由点追加条件が満たされていない場合、あるいはステップＳ４の処理の後は、ステップＳ５へ進み、未調査の輪郭点が残っているかを調べる。
【００２１】
まだ輪郭点が残っている場合はステップＳ２へ戻り、先ほどの処理を繰り返す。輪郭点が残っていなければ、ステップＳ６へ進み、現在位置から、求めた経由点を経由して目標地点まで到達可能な経路を作成する。ステップＳ６の処理について図９を用いて詳細に後述する。
【００２２】
本実施例では、経由点同士を障害物と接触することなく線分で結ぶことが可能かを、一定距離以内にある経由点同士の組み合わせで評価し、可能であれば経由点同士をエッジで結ぶ。このようにして、経由点をノード、経由点同士を結ぶ線分をエッジとするグラフを作成し、グラフ探索手法によって現在地点から目標地点までの経路を生成する。
【００２３】
図２は、本発明に係る経路生成方法を実行する経路生成システム１の一例である。経路生成システム１はコンピュータで実現されることを想定しており、外部システムからの情報を入力するための入力装置２０と、外部システムへ情報を出力するための出力装置４０と、プログラムを記憶している補助記憶装置１０と、記憶装置と他の構成要素の間で情報を高速に媒介するための主記憶装置３０と、主記憶装置３０が読み取った情報に基づいて演算を行う中央演算装置５０を主たる構成要素として構成されている。
【００２４】
本発明はこのうち特に補助記憶装置１０の構成に関与するものであり、補助記憶装置１０は本発明に係る経路生成方法を実行するための経路生成プログラム１１と、アルゴリズムの動作を調整するための設定値１２と、地図画像や、地図画像の解像度や原点位置などを含む地図情報１３と、経路生成プログラム１１を利用する任意のユーザープログラム１４を記憶している。
【００２５】
また、経路生成プログラム１１は、設定値１２と地図情報１３を読み取って各処理部が利用可能な領域へ記憶するための記憶部１１１と、経路生成プログラム１１を利用するユーザープログラム１４から目標地点などの情報を入力する入力部１１２と、ユーザープログラム１４へ計算された経路を出力する出力部１１７と、地図情報１３に含まれる地図画像から輪郭を抽出する輪郭抽出部１１３と、抽出された輪郭から曲率を計算する曲率計算部１１３と、曲率を元に経由点を設定する経由点設定部１１５と、経由点同士を接続して目標地点まで到達可能な経路を探索する経路生成部１１６を備える。
【００２６】
なお、補助記憶装置１０としては、例えば、ハードディスクドライブやソリッドステートドライブ、フラッシュメモリなどを利用可能である。入力装置２０としては、例えば、マウスやキーボードなど人が直接操作可能なものや、他のコンピュータから接続可能なネットワークポートなどの入出力インターフェースを利用可能である。主記憶装置３０としては、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などを利用する。出力装置４０としては、例えば、モニタやスピーカ、他のコンピュータへネットワークを介して出力結果を送信する入出力インターフェースを利用可能である。中央演算装置としては、例えば集積回路やマイクロプロセッサを利用できる。なお、本システムはコンピュータを想定しているが、例えば、経路生成プログラム１０１１に相当するものを論理回路やＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）によって実装してもよい。
【００２７】
以降において、図１の各ステップの詳細について説明する。
【００２８】
図３は、障害物の輪郭を求める考え方を示す図である。図３を用いて、図１のステップＳ１あるいは図２の輪郭抽出部１１２における処理を説明する。図３において、Ｐ１はステップＳ１あるいは輪郭抽出部１１２において利用する地図の一例を表現した地図画像、Ｐ２は地図画像Ｐ１の障害物を肥大させた肥大画像、および、肥大画像Ｐ２から求めた輪郭Ｌを示している。また黒い領域Ｒは障害物を、白い領域Ｈは通行可能な領域を、Ｒｗは肥大化された障害物領域を示している。なお地図画像Ｐ１は補助記憶装置１０内に格納されている地図情報１３を利用している。
【００２９】
本実施例では、経由点と障害物Ｒとの間隔を、衝突の心配がなく十分安全と見なせる距離ｗ（推奨安全距離と称す）とするために、あらかじめ地図内の障害物の領域Ｒを距離ｗの分だけ肥大させて、この肥大させた領域Ｒｗに対して輪郭Ｌを求めている。また、図３の丸囲い部１１７では、障害物を肥大させることによって、地図画像Ｐ１上の小さな多数の障害物が、肥大画像Ｐ２においては単一の障害物に統合されている。このことは不要な経由点の設定を抑制する効果がある。
【００３０】
このように肥大させた領域Ｒｗの輪郭Ｌを利用することにより、後述するステップＳ４では輪郭点そのものを経由点に設定するだけで、肥大させる前の障害物の領域Ｒから一定の距離へ経由点を設定することとなるため、ステップＳ４での距離の計算が省略できるという効果がある。
【００３１】
図４は、輪郭点の曲率を求める考え方を示す図である。図４を用いて、図１のステップＳ２あるいは図２の曲率計算部１１４における処理を説明する。
【００３２】
ステップＳ２、曲率計算部１１４での輪郭点の曲率の求め方について、曲線の曲率Ｃは、数学的に（１）式で定義される。
【００３３】
【数１】
2020160831.tif 000003
【００３４】
なお（１）式において、ｓは曲線上の位置、Δｓは位置の微小な変化量、θは接線角度、Δθは接線角度の微小な変化量を示す。また、Ｒは曲率半径であり、曲率と逆数の関係になっている。この場合に、曲線が数式でパラメトリックに表現される連続的な曲線であれば、（１）式の定義どおりに曲率を計算すればよい。
【００３５】
しかし、コンピュータにおける画像処理では、図４に示すように障害物の領域Ｒについての輪郭Ｌを微少メッシュにて表記しており、画像処理の結果得られる輪郭Ｌは、図４に示すような画素の点列、すなわち輪郭点Ｅによって構成される。このような場合、例えば輪郭点ＥＭ（Ｍは輪郭点の個数Ｎ以下の自然数）と、輪郭点ＥＭ＋１のように１画素だけずれている部分では接線角度変化が必ず４５度の倍数となり、輪郭線の巨視的な曲率とかけ離れた曲率が算出されてしまう。
【００３６】
そこで、本実施例では、計算対象の輪郭点ＥＭを中心に、一定距離Ｔ以上離れた２つの輪郭点ＥＭ−Ｊと輪郭点ＥＭ＋Ｋ（Ｊ、Ｋは、０＜Ｍ−Ｊ＜Ｎ、０＜Ｍ＋Ｋ＜Ｎとなる自然数）を選択し、これらが作る線分ＦＭＪと線分ＦＭＫを接線とする円弧１２０の曲率を、計算対象の輪郭点ＥＭの曲率ＣＭと見なす。このとき、図４より曲率ＣＭは、（２）式で計算できる。
【００３７】
【数２】
2020160831.tif 000004
【００３８】
ここで、接線角度の変化量αは、一般的に左回りが正、右回りが負で計算される。したがって、曲率もこれに応じて、左曲がりが正、右曲がりが負となる。このように曲がる方向に応じて曲率の符号が変わることを利用して、例えば後述する実施例２で述べるように、輪郭点の凹凸を判断することも可能である。
【００３９】
図５は、曲率計算時のパラメータ設定方法の一例を説明する図である。図５を用いて、より公的なパラメータ設定の考え方について説明する。図４によれば、距離Ｔを長くするほど角度αの分解能が上がるが、例えば図５のＴＮＧのように長すぎると細かな曲率変化を表現できなくなるため適切に設定する必要がある。本実施例ではステップＳ１で肥大させた障害物の輪郭を利用しているため、１画素の障害物は、肥大させた幅ｗを半径とする円となる。したがって、少なくともこの半径ｗの円の曲率が検出できれば障害物の全ての凸部の曲率を検出できるので、例えば図５のＴＯＫのように、ＴＯＫ≦ｗなどとすれば、曲率を過不足なく計算可能である。
【００４０】
なお、上述の離散点列の曲率計算方法は、特に計算量が少ない方法として例示したものであって、本方法に限定されるものではない。例えば、輪郭点ＥＭ−Ｊ、ＥＭ、ＥＭ＋Ｋの３点を、円弧で補完し、前記円弧の曲率を輪郭点ＥＭの曲率とする方法などを用いてもよい。
【００４１】
図６は、経由点追加方法の考え方を示す図である。図６を用いて、図１のステップＳ３における経由点追加条件の設定方法、ステップＳ４における経由点追加方法、あるいは図２の経由点設定部１１５における処理を説明する。
【００４２】
移動環境の全域について、移動可能な経路を生成するためには、全ての通路が少なくとも１組以上の経由点同士で接続されなければならない。そこで、図６のように、障害物の領域Ｒを基準として肥大させた領域Ｒｗについての輪郭Ｌ上で、前回の計算で設けられた経由点１２３Ａと、現在計算対象である輪郭点１２３Ｂがなす線分１２４について、線分１２４に対する輪郭Ｌのはみ出し量ｂを計算する。
【００４３】
そして、障害物の領域Ｒを肥大させ、肥大させた領域Ｒｗを決定するのに用いた推奨安全距離ｗに対し、「ｗ−ｂが、自律移動装置が安全上障害物と離れなくてはいけない最短距離ｒ（必要安全距離と称す）以下である」ことを、経由点追加条件とする。
【００４４】
この条件を満たす場合に、ステップ４において輪郭点１２３Ｂの位置を経由点として設定し、この条件を満たさない場合には他の輪郭点に対して同様の判断を行い、基準を満たす経由店を探索していく。なお、線分１２４に対する輪郭Ｌのはみ出し量ｂは、（３）式で計算できる。ただし（３）式においてＣ（ｓ）は、輪郭Ｌ上の曲率、θ０は輪郭点１２３Ａでの接線と線分１２４が成す角度、ＳＭＡＸは、（４）式を満たす実数である。
【００４５】
【数３】
2020160831.tif 000005
【００４６】
【数４】
2020160831.tif 000006
【００４７】
以上によって、障害物と接触することなく全ての通路を経由点で接続することが可能となる。なお、余分な経由点を追加しないためには上述の通りに計算することが望ましいが、計算対象となる輪郭線が大量に存在する場合などは計算量が増加する。
【００４８】
そこで例えば、経由点の追加条件を「曲率の絶対値が一定値以上の場合かつ、隣り合う既存の経由点との距離が一定以上」などとしても、効率のよい経路生成が可能である。あるいは、上述の計算方法によらず、曲率を利用して閉じた輪郭を多角形などで近似し、頂点を経由点としてもよい。
【００４９】
また、計算対象の輪郭点１２３Ｂが、当該障害物の輪郭上で最初の計算対象であった場合は、曲率の絶対値が既定の数値より大きいことを経由点追加条件にすると良い。
【００５０】
図７は、移動経路作成の考え方を示す図である。図７を用いて、図１のステップＳ６における移動経路作成方法、あるいは図２の経由作成部１１６における処理を説明する。
【００５１】
図７は、構内の構成例を示しており、障害物の領域Ｒについての肥大領域Ｒｗを避けて現在位置１２５から目標地点１２６に至る経路を、経由点の情報を用いて探索する。図７に示すように、まず、ステップＳ５までに追加された経由点１２４Ｍ（図７内の白丸）と、自律移動装置の現在位置１２５、および目標地点１２６について、各経由点同士が障害物と衝突することなく経由点同士を線分で接続可能であるかを調べる。例えば、現在位置１２５と経由点１２４Ｍは障害物と衝突することなく接続可能であるが、現在位置１２５と経由点１２４Ｋについては、途中に障害物があるため接続できない。
【００５２】
各点同士を結ぶ線分と障害物との衝突を調べるためには、例えば、図８に示すように、地図画像Ｐ１の障害物を、前述の必要安全距離ｒだけ肥大させた領域Ｒｗに対し、点１２８と点１２９を結ぶ線分１３０上を一定距離Ｄずつ移動しながら、領域Ｒｗの画素を含むかを調査するなどの方法がある。距離Ｄは、必要安全距離ｒなどを考慮して好適に設定する。あるいは、障害物の領域が多角形で近似されている場合は、障害物の領域の各辺と線分１３０との交差を調べても良い。いずれの場合であっても、本実施例のように設定された経由点には無駄が少ないため、ランダムやグリッド状に経由点を設けるよりも大幅にグラフ作成時の計算量を減らすことが可能である。また、地図が広い場合などは、経由点同士の接続関係をすべての点同士の組み合わせで調査するのではなく、互いの距離が一定値以下の点同士で調査することによって、さらに計算量を減らすことも可能である。
【００５３】
図７、図８は現在位置１２５に着目して、ほかの経由点との間で障害物に抵触しない線分が引けることを確認したものである。これに対して現在位置１２５と目標地点１２６とすべての経由点についての任意の点間で、障害物に抵触しないすべての線分を網羅してみる。あるいは任意の点とこの点と一定距離の範囲内にあるすべての点の間で、障害物に抵触しないすべての線分を網羅してみる。このようにして各点同士の接続を調べ、障害物との衝突がない点同士を線分で結ぶと、図９のようなグラフを作成できる。
【００５４】
グラフ作成後は、例えば「Ｈｅｕｒｉｓｔｉｃｓ：  ｉｎｔｅｌｌｉｇｅｎｔ  ｓｅａｒｃｈ  ｓｔｒａｔｅｇｉｅｓ  ｆｏｒ  ｃｏｍｐｕｔｅｒ  ｐｒｏｂｌｅｍ  ｓｏｌｖｉｎｇ，  Ｊ  Ｐｅａｒｌ  -  １９８４，  Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂ．  Ｃｏ．，  Ｉｎｃ．，  Ｒｅａｄｉｎｇ，  ＭＡ」に記載のグラフ探索手法などを利用することによって、現在地点１２５から目標地点１２６までの経路１３１を高速に生成可能である。
【００５５】
なお、グラフ探索手法においては、経由点をノード、経由点同士を結ぶ線分をエッジと呼ぶ。グラフ探索手法においては、多くの場合、ノードやエッジに通過する際の移動距離や安全上のリスク、手間などを反映したコストを設定しておき、目標地点まで到達するまでのコストが最小限になるような経路を探索している。
【００５６】
また、曲率の絶対値が大きい輪郭点は、死角が大きい場合が多く、生成される経路自体も自律移動装置の急旋回を要するものが多い。そこで、例えば、経由点の設定の元になった輪郭点の曲率が大きいほど、大きなコストをノードへ設定すれば、死角の多い経路や、急旋回する経路を迂回するような経路を生成することが可能である。
【００５７】
以上に述べたように、障害物の輪郭の曲率を利用して経由点を設定することで、必要十分な経由点を設定し、少ない計算量であらゆる目標地点までの経路を算出可能である。
【実施例２】
【００５８】
実施例２では、本発明によって、障害物の凸部のみに経由点を作って最短経路を少ない計算量で計算可能な経路生成手法を説明する。なお、実施例２において、上述の実施例１と共通する部分については、重複した説明を省略する。
【００５９】
障害物を有する環境内に経路を生成する場合、衝突の可能性がある部分は障害物の凸部だけであるため、経路生成には凸部の周辺にだけ経由点が設定されていれば十分である。また、実施例１でも述べたとおり、曲率Ｃは左曲りが正、右曲りが負の符号として計算されるため、例えば図１０に示すように、輪郭Ｌに対する障害物の領域Ｒｗが、輪郭点の捜査の向き１３４に対して右（左）にある場合は、右曲り（左曲がり）、すなわち曲率の符号が負（正）の場合に凸部であると判断できる。
【００６０】
したがって、例えば実施例１で記載した経由点追加条件に、「輪郭点の探索の向きに対して障害物の領域が右側でかつ、曲率が負」あるいは「輪郭点の探索の向きに対して障害物の領域が左側でかつ、曲率が正」という条件を追加することにより、障害物の凸部にのみ経由点を設定することが可能となる。
【実施例３】
【００６１】
実施例３では、本発明によって、死角の大きい凸部では離れた位置に経由点を設定することで、より安全な経路を設定可能な経路生成手法を説明する。なお、実施例２において、上述の実施例１と共通する部分については、重複した説明を省略する。
【００６２】
図１１に示すように、障害物Ｒｗの曲率の絶対値が大きい輪郭点１３６の背後の死角１３８は、曲率の絶対値が小さい輪郭点１３７の背後の死角１３９に比べて大きい。これらの死角からは人や物が飛び出す可能性があるため、死角の多い部分からは通常よりも離れた位置に経路を作ることが望ましい。
【００６３】
そこで、図１のステップＳ４での経由点の設定において、輪郭点から経由点までの距離を、曲率の絶対値が大きいほど長く設定することで、死角から離れて移動する経路を生成可能である。例えば、輪郭点１３６に対し、接線１４０を計算する。接線１４０を（５）式のｌで表現できる。ただし、ａ，ｂ，ｔは任意の実数である。
【００６４】
【数５】
2020160831.tif 000007
【００６５】
そして、輪郭点１３６の座標が［ｘ，ｙ］，曲率がＣである時、輪郭点１３６を始点として接線１４０に直行し、曲率Ｃに応じて可変長なベクトル１４１は、（６）式のｐによって表せる。
【００６６】
【数６】
2020160831.tif 000008
【００６７】
ただし、ｋは任意の実数であり、曲率に対してどの程度経由点を障害物から離すかを調整可能とするパラメータである。また、（６）式では符号付きの曲率Ｃを利用することによって、自動的に輪郭の凸方向に離れた位置に経由点を設定することが可能となっている。上記ｐの位置に経由点を設定することにより、障害物の死角の多い部分から離れた位置に経路を生成することが可能である。
【００６８】
なお上記経路生成の処理は、自律移動装置を稼働する以前であればよく、構内の直近における障害物についての各種事情変更が適宜反映されていることが望ましい。
【符号の説明】
【００６９】
１：経路生成システム１
１０：補助菊装置
１１：経路生成プログラム
１２：設定値
１３：地図情報
１４：ユーザープログラム
２０：入力装置
３０：主記憶装置
４０：出力装置
５０：中央演算装置
１１１：記憶部
１１２：入力部
１１３：輪郭抽出部
１１４：曲率計算部
１１５：経由点設定部
１１６：経路作成部
１１７：出力部
【図１】
2020160831.tif 000009
【図２】
2020160831.tif 000010
【図３】
2020160831.tif 000011
【図４】
2020160831.tif 000012
【図５】
2020160831.tif 000013
【図６】
2020160831.tif 000014
【図７】
2020160831.tif 000015
【図８】
2020160831.tif 000016
【図９】
2020160831.tif 000017
【図１０】
2020160831.tif 000018
【図１１】
2020160831.tif 000019