グリッドマップを利用した経路生成装置及び方法
【課題】 制限されたメモリサイズを用いてグリッドマップに基づいた経路を生成する装置及び方法を提供する。
【解決手段】 元のグリッドマップを縮小して生成される縮小マップに基づいて概略経路を生成する。その後、概略経路を元のグリッドマップにマッピングし、該マッピングされて拡大された経路を経路計算に利用される可用メモリサイズに基づいて複数個の区間に分割する。該分割された区間別に設定された出発点及び目標点に基づいて区間別詳細経路を生成する。
【解決手段】 元のグリッドマップを縮小して生成される縮小マップに基づいて概略経路を生成する。その後、概略経路を元のグリッドマップにマッピングし、該マッピングされて拡大された経路を経路計算に利用される可用メモリサイズに基づいて複数個の区間に分割する。該分割された区間別に設定された出発点及び目標点に基づいて区間別詳細経路を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の一つ以上の態様は、経路探索システムに係り、より詳細には、グリッドマップを用いて障害物回避経路を生成する装置及び方法に関する。
【背景技術】
【０００２】
移動ロボットのような移動体の移動のために生成される経路は、通常グリッドマップ（ｇｒｉｄ ｍａｐ）を用いて設定される。グリッドマップは、移動体が移動する周り環境を小さな定義可能な領域またはグリッド（ｇｒｉｄｓ）に分け、各グリッドに物体がある可能性を確率的に表現したマップである。移動体は、特定位置に移動するために、グリッドマップを用いて障害物に衝突しない特定位置までの経路を利用する。掃除ロボットのような移動ロボットに対する従来の特定位置は、自動充電のための充電ステーションや特定タスクのための特定位置であり得る。
【０００３】
通常、経路を生成するためには、出発地から目的地までの最も早い経路を探すために、出発地から目的地までの可能なあらゆる経路を順次に探索する。グリッドマップが大きくない場合には、経路探索のための計算量が大きくないので、迅速に経路が生成されうるが、グリッドマップのサイズが大きくなるほどグリッドの個数が増えるので、要求されるメモリ量と計算量とがグリッドマップのサイズに比例して大きくなる。したがって、エンベデッドシステムのように制限されたメモリサイズまたは処理容量を有する装置では、迅速な経路探索が難しい。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、グリッドマップを用いて経路を探索するときに利用される必要なメモリサイズを減少させることができる装置及び方法を提供することである。
【課題を解決するための手段】
【０００５】
一態様による経路生成装置は、マップを縮小して生成される縮小マップに基づいてマップと関連して動く移動体に対する概略経路を生成し、マップを概略経路の分割に基づいて複数個の区間に分割し、該分割された区間別に概略経路に基づいて詳細経路を生成する経路生成部を含む。
【０００６】
他の態様による、マップで物体の経路を生成する方法は、マップを縮小して生成された縮小マップで概略経路を生成する段階と、概略経路の分割に基づいてマップを複数個の区間に分割する段階と、概略経路に基づいて分割された区間別に詳細経路を生成する段階と、を含む。
【０００７】
また他の態様による経路生成装置は、縮小マップに基づいてマップと関連して動く物体に対する概略経路を生成し、縮小マップに対する概略経路のマッピングに基づいて、マップを複数個の区間に分割し、該分割された区間別に少なくとも一つの探索アルゴリズムを用いて詳細経路を生成する経路生成部を含み、経路生成部は、概略経路からの点に基づいて分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成する。
【０００８】
また他の態様による、経路生成方法は、縮小マップのマップと関連して動く物体に対する概略経路を生成し、マップへの縮小マップの概略経路のマッピングに基づいて、マップを複数個の区間に分割し、該分割された区間別に少なくとも一つの探索アルゴリズムをそれぞれ用いて詳細経路を生成する段階を含み、マップを分割する段階は、概略経路からの点に基づいて分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成する。
【発明の効果】
【０００９】
本発明は、グリッドマップを用いて経路を探索するときに利用される必要なメモリサイズを減少させることができる装置及び方法を提供する。
【図面の簡単な説明】
【００１０】
【図１】一実施形態による経路生成装置を示すブロック図である。
【図２Ａ】通常の技術によるグリッドマップ縮小方法及び一実施形態によるグリッドマップ縮小方法を示す図である。
【図２Ｂ】通常の技術によるグリッドマップ縮小方法及び一実施形態によるグリッドマップ縮小方法を示す図である。
【図３】一実施形態によるグリッドマップ縮小方法による処理結果を説明するための図である。
【図４】一実施形態による詳細経路生成過程を示す図である。
【図５】一実施形態による詳細経路を生成するために概略経路を複数個の区間に分割したマップの一例を示す図である。
【図６】一実施形態による経路生成過程を示す図である。
【図７】図６に示された経路生成方法を詳細に示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、添付した図面を参照して、本発明の一実施形態を詳細に説明する。本発明を説明するに当って、関連した公知機能または構成についての具体的な説明が、本発明の要旨を不明にする恐れがあると判断される場合には、その詳細な説明を省略する。また、後述する用語は、本発明での機能を考慮して定義された用語であって、これは、ユーザ、運用者の意図または慣例などによって変わりうる。したがって、その定義は、本明細書全般に亘った内容に基づいて下されなければならない。
【００１２】
図１は、一実施形態による経路生成装置を示すブロック図である。
【００１３】
本明細書で、装置は、物理システムの要素と同義語であるが、あらゆる要素が単一エンクロージャーに具現せねばならないことではなく、他のエンクロージャーまたは他の位置に別途に離れるか、ともに具現可能である。他の例として、それぞれの装置／システムまたは方法は、一つ以上の処理要素／装置を通じて制御されることができ、分散されたネットワークによって具現可能であり、付加的かつ選択的な実施形態も利用可能である。
【００１４】
一実施形態で、経路を生成する装置は、グリッドマップ生成に対する感知要素及び生成された経路に沿って移動ロボットを移動させる移動要素をさらに含む。一実施形態で、適切なグリッドマップ生成過程は、移動ロボットが経路に沿って移動することを含む。また、実施形態が移動ロボットと関連して説明されることができるが、実施形態は、ロボットの周辺の移動が障害物エッジまたは領域と制限されたインタラクションを有するか、インタラクションがないように具現された場合、停止ロボットにも同様に適用可能である。一実施形態で、移動体は、コンピュータで生成された空間でのアバターであり得る。
【００１５】
一実施形態による経路生成装置１００は、経路生成部１１０及び保存部１２０を含む。
【００１６】
前述したように、装置１００は、移動ロボットであり、生成された経路に沿って移動ロボットを動かす移動要素を含みうる。例示の目的のために、経路に沿って移動を制御することは、詳しく論議しない。このような制御及び移動要素に対する論議については、“Ｍｅｔｈｏｄ ａｎｄ ａｐｐａｒａｔｕｓ ｆｏｒ ｍｏｖｉｎｇ ａｌｏｎｇ ｓｈｏｒｔｅｓｔ ｍｏｖｅｍｅｎｔ ｐａｔｈ ｕｓｉｎｇ ｇｒｉｄ ｍａｐ”と題された米国特許第２００４−０１１６８６４号明細書に開示されている。また、ここでは、グリッド位置識別システム（ｇｒｉｄ ｉｄｅｎｔｉｆｙｉｎｇ ｌｏｃａｔｉｏｎ ｓｙｓｔｅｍ）に基づいたマップ作成に関して説明しているが、マップ内で移動体の位置または他の客体と関連した非障害物領域から障害物または障害物領域の位置を識別するための他の位置識別基盤システムが利用されうる。
【００１７】
経路生成部１１０は、１次的にグリッドマップを縮小して生成される縮小マップに基づいて概略経路を生成し、２次的に縮小前の元の概略経路を複数個の区間に分割した後、該分割された区間別に詳細経路を生成する。以後に、これら分割された経路は、順次に組合わせられて元のグリッドマップに対する詳細経路が生成されうる。経路生成部１１０は、多様な経路生成方法を利用することができるが、ここでは、Ａスター（Ａ＊）アルゴリズムを用いて経路を生成すると仮定する。他の方法として、経路は、Ｄスター（Ｄ＊）アルゴリズム、他のアルゴリズムまたは他のアルゴリズムの組合わせを用いて生成されうる。
【００１８】
簡略に、Ａスターアルゴリズムは、与えられた初期ノードから（一つ以上の可能な目標のうち）一つの目標モードまでの最小コスト経路を探すベストファーストグラフ探索アルゴリズムである。開始点から目標点までのあらゆる可能な経路は、コスト増加順序によって順次に試験されうる。したがって、Ａスターは、ツリーからノードを訪問する探索順序を決定する距離−プラス−コスト発見的関数（ｄｉｓｔａｎｃｅ−ｐｌｕｓ−ｃｏｓｔ ｈｅｕｒｉｓｔｉｃ ｆｕｎｃｔｉｏｎ）（一般的に、ｆ（ｘ）で表わす）を利用する。距離−プラス−コスト発見的関数は、２個の関数の和であり得る。２個の関数は、開始ノードから現在ノードへのコストである経路−コスト関数（ｐａｔｈ−ｃｏｓｔ ｆｕｎｃｔｉｏｎ）（一般的に、ｇ（ｘ）で表わす）と目標までの距離の許容可能な“発見的予測（ｈｅｕｒｉｓｔｉｃ ｅｓｔｉｍａｔｅ）”（一般的に、ｈ（ｘ）で表わす）である。
【００１９】
Ａスターアルゴリズムは、Ｈａｒｔ，Ｐ．Ｅ．，Ｎｉｌｓｓｏｎ，Ｎ．Ｊ．，Ｒａｐｈａｅｌ，Ｂ．，“Ａ Ｆｏｒｍａｌ Ｂａｓｉｓ ｆｏｒ ｔｈｅ Ｈｅｕｒｉｓｔｉｃ Ｄｅｔｅｒｍｉｎａｔｉｏｎ ｏｆ Ｍｉｎｉｍｕｍ Ｃｏｓｔ Ｐａｔｈｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｆ Ｓｙｓｔｅｍｓ Ｓｃｉｅｎｃｅ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ，ｖｏｌ．ｓｓｃ−４，Ｎｏ．２（１９６８）で発見されうる。Ｄスターアルゴリズムは、Ａスターアルゴリズムの変形で走行間に概略経路で方向変化が発生する時、以前探索結果を再利用して素早い探索を可能にする。しかし、実際具現で、イメージピラミッドを利用したＡスターアルゴリズムは、通常、Ｄスターアルゴリズムに比べてさらに早い処理速度を表わすことができる。異なる分割されたグリッドマップの間に異なるアルゴリズムを利用することが可能であるが、効率的でないこともある。ここで、例えば、以前経路結果は、後続探索に利用されることができ、以前及び現在探索アルゴリズムが同一である必要はない。Ｄスターアルゴリズムは、“Ｏｐｔｉｍａｌ ａｎｄ Ｅｆｆｉｃｉｅｎｔ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｆｏｒ Ｐａｒｔｉａｌｌｙ−Ｋｎｏｗｎ Ｅｎｖｉｒｏｎｍｅｎｔｓ”，Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ，Ｓｔｅｎｔｚ，Ａｎｔｈｏｎｙ（１９９４）で論議されている。同様に、ここに統合されたＡスターアルゴリズム及びＤスターアルゴリズムだけではなく、他のアルゴリズムが、Ｈ．Ｃｈｏｓｅｔ，Ｋ．Ｌｙｎｃｈ，Ｓ．Ｈｕｔｃｈｉｎｓｏｎ，Ｇ．Ｋａｎｔｏｒ，Ｗ．Ｂｕｒｇａｒｄ，Ｌ．Ｋａｖｒａｋｉ，ａｎｄ Ｓ．Ｔｈｒｕｎ，“Ｐｒｉｎｃｉｐｌｅｓｏｆ Ｒｏｂｏｔ Ｍｏｔｉｏｎ，”ｐｐ．５２７〜５３６に論議されている。ここで、“Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｒｏｂｏｔ Ｍｏｔｉｏｎ”は、移動体が定義された経路によるプロセスについての説明を含んでいる。したがって、保存部１２０は、経路生成で利用されるグリッドマップ及び経路生成装置１００の動作に必要なアプリケーションデータなどを保存することができる。また、保存部１２０は、経路生成部１１０の経路生成動作過程で発生するデータの読み取り及び書き込みが実行される可用メモリ領域を含む。
【００２０】
経路生成部１１０は、マップ縮小部１１２、概略経路生成部１１４及び詳細経路生成部１１６を含む。
【００２１】
グリッドマップは、通常、赤外線センサー、超音波センサー、またはレーザセンサーなどの距離センサーを用いて獲得され、特定位置または領域で障害物がある確率情報を含む。このようなグリッドマップは、移動ロボットのような移動体のサイズを考慮しないものであって、このようなグリッドマップを用いて移動体が走行すれば、経路が障害物または障害物領域と衝突するように定義されていないとしても、移動体のフレーム部分が障害物に衝突することができる。したがって、マップ縮小部１１２は、移動体のサイズを考慮して、新たに生成される縮小されたグリッドマップで移動体を一点に縮小させて壁面またはエッジや障害物または障害物領域を移動体のサイズを考慮して厚くする。縮小されたグリッドマップの自由領域、すなわち、移動体が障害物または障害物領域と衝突せずに自在に動くことができる自由領域を決定して、自由領域情報を含むグリッドマップを生成する。
【００２２】
マップ縮小部１１２は、決定された自由領域情報を含むグリッドマップを縮小して縮小マップを生成する。グリッドマップの縮小時には、アンチエイリアシングフィルタリングプロセスを用いてグリッドマップを縮小することができる。
【００２３】
付加的なまたは代案的な要素が縮小されたグリッドマップを生成するが、具現されるように縮小を定義するときに考慮されうる。例えば、移動体のサイズが２０ｃｍであり、１ｃｍのグリッドセルが１ドット（ｄｏｔ）にマッピングされるとき、元のグリッドマップの縮小比率が１／２０以下に縮小されれば、存在する障害物が縮小されたグリッドマップに適切に反映されることができない。したがって、この場合、グリッドマップ縮小の比率は、移動体のサイズが１ドットにマッピングされるときの縮小比率に制限されうる。これは、グリッドマップを移動体のサイズに基づいて正規化すると考えられうる。簡略に、一実施形態で、経路を概略化する前に壁または障害物のサイズを増加させる理由は、移動体が壁または障害物から所定空間内で動く場合に対することであり得る。また、壁または障害物の幅を増加させる代わりに、壁及び障害物の幅を減少させることも可能であり、この場合に、経路計画は、移動体と壁または障害物との間の衝突が少なくとも防止されることができる最短距離に基づいて実行可能である。
【００２４】
縮小マップを用いた経路設定に必要な開始点と目標点の座標は、縮小されたグリッドマップに合わせて変換する。元のグリッドマップを１／Ｎ２に線形的に縮小するならば、それぞれの座標に１／Ｎを乗算する。開始点と目標点の場合、開始点と目標点のそれぞれの座標に１／Ｎを乗算した後、縮小されたグリッドマップ上で変換された座標と最も近い自由領域の座標とを捜して開始点と目標点とを設定することができる。
【００２５】
線形的縮小が説明されたが、元のグリッドマップの非線形的縮小も可能である。この場合に、特定グリッドマップが非線形的に縮小されて経路計画を経れば、グリッドマップは、経路探索のために拡大される時、例えば、単純に２倍に拡大する代わりに、非線形的縮小に反比例して非線形的に拡大されうる。
【００２６】
概略経路生成部１１４は、縮小マップを用いて開始点から目標点までの概略経路を生成する。概略経路は、設定された開始点から目標点までの経路としてＡスターアルゴリズムを用いて探索されうる。
【００２７】
詳細経路生成部１１６は、元のグリッドマップで探索された経路を少なくとも二つ以上の区間に分け、該分けられた区間別開始点から目標点まで経路を探索することで、詳細経路を生成する。以下で、詳細経路を生成する動作について詳細に説明する。
【００２８】
まず、詳細経路生成部１１６は、概略経路上の経路点を縮小前の自由領域情報を含むグリッドマップにマップ縮小部１１２によりマッピングする。例えば、開始点と目標点との間で移動体が移動する点になる経路点のうち、経路点３１と経路点３２とが図４のグリッドマップ４１０にある。移動体は、各経路点をそれぞれの目標点として経路点ごとに移動する。マッピングの結果として、縮小されたグリッドマップから元のグリッドマップ上でマッピングされた経路点のうち一部経路点（または、開始点または目標点）が、移動体が移動可能な自由領域の外側にマッピングされうる。したがって、詳細経路生成部１１６は、マッピングされた経路点のうち、経路点が自由領域の外部（例えば、障害物または障害物領域の内部）に位置する経路点の有無を確認し、自由領域の外部に位置する経路点がある場合、確認された経路点を元のグリッドマップでそれぞれ最も近い自由領域に位置調整する。
【００２９】
その後、詳細経路生成部１１６は、縮小されたグリッドマップの概略経路を複数個の区間に分割し、元のグリッドマップの分割された区間ごとに開始点及び目標点を設定して、分割された区間別に経路を再び設定して、最終詳細経路を生成することができる。
【００３０】
詳細経路生成部１１６は、経路計算に利用される可用メモリ領域のサイズ及び／または処理能力に基づいて経路区間を、例えば、決定された個数の区間及びそれぞれのサイズに分割することができる。
【００３１】
例えば、Ａスターアルゴリズムによる経路探索時、一つのグリッド当たり必要なメモリ量は１８バイト（Ｂｙｔｅ）であり得る。したがって、グリッドマップ上で経路点のうち開始点及び目標点が決定されれば、経路計算に必要なメモリサイズが計算されうる。一実施形態で、詳細な全体経路が単一経路プロセスを用いて従来の経路生成に比べて短時間に生成されるように、別個の区間に分割された経路区間に対して、あらゆる区間に対して並列経路生成プロセッシングが具現可能である。例えば、概略経路を元のグリッドマップに再びマッピングして元のグリッドマップを分割するより、元のグリッドマップが分割された概略経路に基づいてローカルマップに分割されることができ、適切な探索アルゴリズム、例えば、Ａスターアルゴリズムがそれぞれのローカルグリッドマップに適用可能である。各ローカルグリッドマップに対して結果的な詳細経路は、その後に元のグリッドマップ全体を経るのに必要な全体経路を通じて順に、移動体によって個別的に利用されうる。縮小グリッドマップからの概略経路点が、元のグリッドマップにマッピングされ、自由領域に位置調整された経路点をＰＳ、ＰＳ＋１、ＰＳ＋２、．．．ＰＳ＋Ｎ（ここで、Ｎは整数）で表わし、ＰＳが開始点であり、ＰＳ＋Ｎが目標点と仮定する。
【００３２】
詳細経路生成部１１６は、自由領域上に位置された経路上の元の開始点から目標点に向ける経路点のうち元の開始点（ＰＳ）からの経路計算時に可用メモリサイズを超えない経路点（例えば、ＰＳ＋１０）を目標点とする区間を設定し、該設定された区間を含むグリッドマップを用いて詳細経路を生成することができる。その後、詳細経路生成部１１６は、以前区間の目標点（ＰＳ＋１０）を開始点とし、可用メモリサイズを超えない範囲の経路点を目標点（例えば、ＰＳ＋２０）とする区間を設定し、該設定された区間を含むグリッドマップを用いて詳細経路を生成することができる。このように、区間設定時に最後の区間が開始点から元の目標点（ＰＳ＋Ｎ）までに設定されることができ、該設定された区間で詳細経路を生成することができる。
【００３３】
このような区間設定時に各区間は、一定部分重なるように設定しうる。例えば、最初の区間の目標点がＰＳ＋１０である場合、二番目の区間の開始点はＰＳ＋９に設定することができる。詳細経路生成部１１６は、このように設定された区間別詳細経路を組み合わせて最終経路を生成することができる。
【００３４】
詳細経路生成部１１６は、最終詳細経路上に位置する経路点のうちから方向が変わる地点に位置する経由点を選択することができる。移動体は、開始点、目標点及び選択された経由点情報を用いてグリッドマップ上の生成された経路を移動することができる。ここで、移動体は、物理的な移動ロボットであり、経路探索アプリケーションで探索された経路を探索するように設定された所定のオブジェクト、例えば、ゲームアプリケーションのキャラクターになり得る。
【００３５】
経路生成装置１１０または装置１００は、携帯電話、ＰＭＰ、ＰＤＡなど多様な電子装置として具現可能であり、経路を生成して移動可能な移動ロボットなどの移動体としても具現可能である。経路生成装置１１０は、移動体として具現されるとき、グリッドマップの生成、移動体の移動量の感知などのためのセンシングユニット、移動体を移動させるための走行ユニットなどをさらに含みうる。センシングユニットは、移動体周辺の２次元または３次元マップを生成することで、例えば、移動ロボット周辺の元のグリッドマップの一部または全部を潜在的に生成することができる。
【００３６】
前述したように、一実施形態によれば、グリッドマップのサイズを縮小して縮小グリッドマップ内で概略経路を生成する。概略的な経路を元のグリッドマップに反映される複数個の区間に分割する。該分割された区間で詳細経路を再び探索して、概略経路を補完する。
【００３７】
したがって、小さいサイズのメモリを数回使って元のサイズの全体グリッドマップ上で一回に経路探索することに比べて経路探索に必要なメモリ量を、グリッドマップを縮小させる比率に比例して減らしうる。縮小マップで経路を探索するか、または全体グリッドマップ上の区間別経路を探索するので、元の全体グリッドマップでの経路探索に比べて経路探索にかかる時間が短縮される。したがって、元の全体グリッドマップでの一回の経路探索に比べて、全体経路探索に必要な時間には大きな変化がない。
【００３８】
図２Ａ及び図２Ｂは、通常の技術によるグリッドマップ縮小方法及び一実施形態によるグリッドマップ縮小方法をそれぞれ示す図である。
【００３９】
グリッドマップから物体が自在に移動することができる領域を表わす自由領域情報を含むグリッドマップが生成されれば、グリッドマップを１／Ｎ２に縮小する過程が実行される。図２Ａ及び図２Ｂは、グリッドマップを１／４に縮小する方法を表わす。
【００４０】
図２Ａは、グリッドマップ２１０の１／４の情報のみ抽出して生成された縮小マップ２２０を生成する過程を表わす。このような方法によれば、図２Ａに示されたように、元の情報でＡ、Ｃ、Ｉ及びＫ情報のみ利用され、残り部分の情報がなくなってグリッドマップ縮小過程で元のグリッドマップの情報の損失によって正確な最終的経路の生成ができなくなる可能性が高い。
【００４１】
図２Ｂは、一実施形態によるアンチエイリアシングフィルタリングを利用したグリッドマップ縮小方法を表わす。一実施形態によれば、グリッドマップ２３０を４個のグリッドごとにグルーピングして、該グルーピングされたグリッドの平均を求めて縮小マップ２４０を生成する。その後、平均値を臨界値と比べてグリッドの平均値が臨界値以上である場合、１に設定し、平均値が臨界値未満である場合、０に設定する。ここで、グリッドの値が１に設定されれば、障害物があるということを表わし、０に設定されれば、障害物がないということを表わす。
【００４２】
図３は、一実施形態によるグリッドマップ縮小方法による処理結果を説明するための図である。３１０ないし３４０は、グリッドマップを表わし、白色領域は移動体が移動することができる領域を表わし、ハッチされた領域は障害物領域を表わす。グリッドマップ３１０で経路３０は、元のグリッドマップで開始点１０から目標点２０まで探索された経路である。
【００４３】
グリッドマップ３２０は、元のグリッドマップ３１０を図２Ａに示された方法を用いて１／４に縮小した図を示し、グリッドマップ３２０上では、元のグリッドマップ３１０の情報が消失されてグリッドマップ３１０の経路３０のような経路が生成されることができない。すなわち、グリッドマップ３２０のように元のグリッドマップ３１０の１／４の情報のみ抽出して生成された縮小マップを生成すれば、障害物情報がなくなって正確な経路を生成することができず、グリッドマップ３２０でのように実際に障害物を横切るようになって利用されることができない経路が生成される。
【００４４】
グリッドマップ３３０は、グリッドマップ３１０について、図２Ｂを参照して説明したようなアンチエイリアシングフィルターを利用したグリッドマップ縮小結果を表わす。グリッドマップ３３０に示されたような平均値を臨界値と比べてグリッドの平均値が臨界値以上である場合、グリッドの値を１に設定し、平均値が臨界値未満である場合、グリッドの値を０に設定すれば、図面３４０のような縮小グリッドマップが形成される。グリッドマップ３４０は、グリッドマップ３２０に比べて障害物情報の消失が少なく、元のグリッドマップ３１０でのような経路４０が生成されうる。
【００４５】
図４は、一実施形態による詳細経路生成過程を示す図である。
【００４６】
グリッドマップ４１０ないし４３０で障害物境界４０２の外部にハッチされた領域４０１は、障害物領域を表わし、障害物境界４０２の内部のハッチ領域４０３は、移動体が自在に移動することができる自由領域を表わす。
【００４７】
縮小マップで探索された経路を元のグリッドマップ上でマッピングすれば、図４のグリッドマップ４１０のように、自由領域以外の領域の外側にマッピングされる経路点３１、３２が存在することができる。
【００４８】
これを補正するために、一実施形態によれば、経路点のうち自由領域の外部に位置する経路点の有無を確認し、自由領域の外部に位置する経路点がある場合、確認された経路点をそれぞれ最も近い自由領域に位置調整する。経路点が自由領域にマッピングされれば、グリッドマップ４１０上の経路点は、グリッドマップ４２０でのように位置調整される。
【００４９】
しかし、グリッドマップ４２０に表示された経路点を繋げれば、グリッドマップ４３０の部分拡大図面４３５に示されたように、移動体が通り過ぎない領域（自由領域を超える領域）を通る直線経路が生じうる。したがって、一実施形態によれば、縮小マップで生成された概略経路を元のグリッドマップ上で再び計画する。すなわち、区間経路生成のために元のグリッドマップに再びマッピングされる概略経路の対応する部分は、定義された自由領域のみを通るように再定義されうる。
【００５０】
この際、例えば、縮小グリッドマップで概略経路の探索が完了した時、経路探索のためのＡスターアルゴリズムを実行するためのメモリサイズを考慮して、概略経路を前述したように複数個の区間に分離し、区間別に経路探索を遂行して最終経路を生成する。概略経路の分割は、縮小グリッドマップ内で遂行されることもあり、元のグリッドマップ上に概略経路を再びマッピングした時、元のグリッドマップ内で遂行されることもある。
【００５１】
図５は、一実施形態による詳細経路を生成するために、概略経路を複数個の区間に分割したマップの一例を示す図である。
【００５２】
元のグリッドマップ上の経路を複数個の区間に分けて経路探索をする時には、経路探索アルゴリズム、例えば、Ａスターアルゴリズムを実行するためのメモリの可用メモリ領域のサイズを考慮する。一実施形態によれば、Ａスターアルゴリズムで経路を探すことができる最大グリッドサイズがＳＸ（Ｘ軸グリッドサイズ）×ＳＹ（Ｙ軸グリッドサイズ）であれば、開始点（ＰＳ）から始めて、ＳＸ×ＳＹ範囲内に入る経路点ＰＥまでを一つのセットで決めることができる。ここで、ＳＸ及びＳＹは、可用メモリサイズ内で可変される。図５では、元のグリッドマップ５１０で分割された区間を含むグリッドマップ部分５１２、５１４、５１６別に経路が探索されるということを表わす。例えば、Ａスターアルゴリズムで経路を探すことができる最大グリッドマップのサイズが１２８×１２８である場合、図４の４１０ないし４３０内の経路点は、図５に示されたように分離されうる。
【００５３】
図５で、経路点５０１は、経路開始点を表わし、経路点５０４は、元のグリッドマップの最後の詳細経路に対する経路目標点を表わす。経路点５０２、５０３は、経路区間を分離する基準経路点を表わす。図５では、経路点５０１から経路点５０２までを第１区間とし、経路点５０２から経路点５０３までを第２区間とし、経路点５０３から経路点５０４までを第３区間として、各区間別に経路を探索することができる。各区間別に探索された経路を組み合わせれば、最終経路になる。
【００５４】
図６は、一実施形態による経路生成過程を示す図である。
【００５５】
グリッドマップを縮小して縮小マップを生成する（Ｓ６１０）。縮小マップに基づいて概略経路を生成する（Ｓ６２０）。概略経路を複数個の区間に分割する（Ｓ６３０）。複数個の区間は、経路生成過程で発生するデータの読み取り及び書き込みが実行される可用メモリ領域のサイズに基づいて分割される。該分割された区間別に詳細経路を生成する（Ｓ６４０）。これら詳細経路から最終詳細経路が生成されうる。
【００５６】
図７は、図６に示された経路生成方法を詳細に示すフローチャートである。
【００５７】
グリッドマップから生成された経路及び移動体のサイズを考慮して物体が自在に移動することができる自由領域を決定し、自由領域情報を含むグリッドマップを縮小して縮小マップを生成する（Ｓ７１０）。
【００５８】
縮小マップに基づいて概略経路を探索する（Ｓ７２０）。
【００５９】
探索された経路上の経路点を元のグリッドマップにマッピングし（Ｓ７３０）、該マッピングされた経路点のうち自由領域から外れている経路点があれば（Ｓ７４０）、マッピングされた経路上の経路点をそれぞれの経路点ごとに最も近い自由領域の位置に経路点の位置を調整する（Ｓ７５０）。
【００６０】
マッピングされた経路（すなわち、元のグリッドマップ上にマッピングされた経路）上の経路点を分離して経路を複数個の区間に分割し（Ｓ７６０）、該分割された区間別に開始点及び目標点を設定して、区間別に詳細経路を生成する（Ｓ７７０）。区間別詳細経路を組み合わせて最終詳細経路を生成する（Ｓ７８０）。最後に、最終詳細区間の経路が、以前に生成された区間経路から外れなければ、後続的な最終詳細経路生成が進行しうる。
【００６１】
前述した実施形態に付け加えて、実施形態がコンピュータ判読可能コード／命令語を通じて媒体、例えば、コンピュータ判読可能媒体内（ｉｎ）／上（ｏｎ）に具現されて、前述した実施形態を具現するための少なくとも一つのプロセッシングデバイスを制御することができる。媒体は、コンピュータ判読可能コードの保存及び／または伝送を許容する、ある定義された、測定可能であり、類型の構造に対応することができる。
【００６２】
コンピュータ判読可能コードは、磁気記録媒体（例えば、ＲＯＭ、フロッピー（登録商標）ディスク、ハードディスクなど）、光記録媒体（例えば、ＣＤ−ＲＯＭ、またはＤＶＤ）及びキャリアウェーブを伝達するか含む非一時的伝送媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ ｔｒａｎｓｍｉｓｓｉｏｎ ｍｅｄｉａ）のような、記録媒体を含む媒体だけではなく、例えば、インターネットのハードウェア構成要素などに、多様な方式で媒体に記録／伝送することができる。したがって、媒体は、例えば、一実施形態によって、ビットスツリームを伝達するデバイスのように、信号または情報を含むか伝達すると定義されて測定可能な非一時的な構造であり得る。媒体は、または分散ネットワークであり、したがって、コンピュータ判読可能コードが分散方式で保存されて実行可能である。また、プロセッシングエレメントは、プロセッサ、コンピュータプロセッサを含むことができ、プロセッシングエレメントは単一デバイスに含まれるか、分散されうる。
【産業上の利用可能性】
【００６３】
本発明は、グリッドマップを利用した経路生成装置及び方法関連の技術分野に適用可能である。
【技術分野】
【０００１】
本発明の一つ以上の態様は、経路探索システムに係り、より詳細には、グリッドマップを用いて障害物回避経路を生成する装置及び方法に関する。
【背景技術】
【０００２】
移動ロボットのような移動体の移動のために生成される経路は、通常グリッドマップ（ｇｒｉｄ ｍａｐ）を用いて設定される。グリッドマップは、移動体が移動する周り環境を小さな定義可能な領域またはグリッド（ｇｒｉｄｓ）に分け、各グリッドに物体がある可能性を確率的に表現したマップである。移動体は、特定位置に移動するために、グリッドマップを用いて障害物に衝突しない特定位置までの経路を利用する。掃除ロボットのような移動ロボットに対する従来の特定位置は、自動充電のための充電ステーションや特定タスクのための特定位置であり得る。
【０００３】
通常、経路を生成するためには、出発地から目的地までの最も早い経路を探すために、出発地から目的地までの可能なあらゆる経路を順次に探索する。グリッドマップが大きくない場合には、経路探索のための計算量が大きくないので、迅速に経路が生成されうるが、グリッドマップのサイズが大きくなるほどグリッドの個数が増えるので、要求されるメモリ量と計算量とがグリッドマップのサイズに比例して大きくなる。したがって、エンベデッドシステムのように制限されたメモリサイズまたは処理容量を有する装置では、迅速な経路探索が難しい。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明は、グリッドマップを用いて経路を探索するときに利用される必要なメモリサイズを減少させることができる装置及び方法を提供することである。
【課題を解決するための手段】
【０００５】
一態様による経路生成装置は、マップを縮小して生成される縮小マップに基づいてマップと関連して動く移動体に対する概略経路を生成し、マップを概略経路の分割に基づいて複数個の区間に分割し、該分割された区間別に概略経路に基づいて詳細経路を生成する経路生成部を含む。
【０００６】
他の態様による、マップで物体の経路を生成する方法は、マップを縮小して生成された縮小マップで概略経路を生成する段階と、概略経路の分割に基づいてマップを複数個の区間に分割する段階と、概略経路に基づいて分割された区間別に詳細経路を生成する段階と、を含む。
【０００７】
また他の態様による経路生成装置は、縮小マップに基づいてマップと関連して動く物体に対する概略経路を生成し、縮小マップに対する概略経路のマッピングに基づいて、マップを複数個の区間に分割し、該分割された区間別に少なくとも一つの探索アルゴリズムを用いて詳細経路を生成する経路生成部を含み、経路生成部は、概略経路からの点に基づいて分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成する。
【０００８】
また他の態様による、経路生成方法は、縮小マップのマップと関連して動く物体に対する概略経路を生成し、マップへの縮小マップの概略経路のマッピングに基づいて、マップを複数個の区間に分割し、該分割された区間別に少なくとも一つの探索アルゴリズムをそれぞれ用いて詳細経路を生成する段階を含み、マップを分割する段階は、概略経路からの点に基づいて分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成する。
【発明の効果】
【０００９】
本発明は、グリッドマップを用いて経路を探索するときに利用される必要なメモリサイズを減少させることができる装置及び方法を提供する。
【図面の簡単な説明】
【００１０】
【図１】一実施形態による経路生成装置を示すブロック図である。
【図２Ａ】通常の技術によるグリッドマップ縮小方法及び一実施形態によるグリッドマップ縮小方法を示す図である。
【図２Ｂ】通常の技術によるグリッドマップ縮小方法及び一実施形態によるグリッドマップ縮小方法を示す図である。
【図３】一実施形態によるグリッドマップ縮小方法による処理結果を説明するための図である。
【図４】一実施形態による詳細経路生成過程を示す図である。
【図５】一実施形態による詳細経路を生成するために概略経路を複数個の区間に分割したマップの一例を示す図である。
【図６】一実施形態による経路生成過程を示す図である。
【図７】図６に示された経路生成方法を詳細に示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、添付した図面を参照して、本発明の一実施形態を詳細に説明する。本発明を説明するに当って、関連した公知機能または構成についての具体的な説明が、本発明の要旨を不明にする恐れがあると判断される場合には、その詳細な説明を省略する。また、後述する用語は、本発明での機能を考慮して定義された用語であって、これは、ユーザ、運用者の意図または慣例などによって変わりうる。したがって、その定義は、本明細書全般に亘った内容に基づいて下されなければならない。
【００１２】
図１は、一実施形態による経路生成装置を示すブロック図である。
【００１３】
本明細書で、装置は、物理システムの要素と同義語であるが、あらゆる要素が単一エンクロージャーに具現せねばならないことではなく、他のエンクロージャーまたは他の位置に別途に離れるか、ともに具現可能である。他の例として、それぞれの装置／システムまたは方法は、一つ以上の処理要素／装置を通じて制御されることができ、分散されたネットワークによって具現可能であり、付加的かつ選択的な実施形態も利用可能である。
【００１４】
一実施形態で、経路を生成する装置は、グリッドマップ生成に対する感知要素及び生成された経路に沿って移動ロボットを移動させる移動要素をさらに含む。一実施形態で、適切なグリッドマップ生成過程は、移動ロボットが経路に沿って移動することを含む。また、実施形態が移動ロボットと関連して説明されることができるが、実施形態は、ロボットの周辺の移動が障害物エッジまたは領域と制限されたインタラクションを有するか、インタラクションがないように具現された場合、停止ロボットにも同様に適用可能である。一実施形態で、移動体は、コンピュータで生成された空間でのアバターであり得る。
【００１５】
一実施形態による経路生成装置１００は、経路生成部１１０及び保存部１２０を含む。
【００１６】
前述したように、装置１００は、移動ロボットであり、生成された経路に沿って移動ロボットを動かす移動要素を含みうる。例示の目的のために、経路に沿って移動を制御することは、詳しく論議しない。このような制御及び移動要素に対する論議については、“Ｍｅｔｈｏｄ ａｎｄ ａｐｐａｒａｔｕｓ ｆｏｒ ｍｏｖｉｎｇ ａｌｏｎｇ ｓｈｏｒｔｅｓｔ ｍｏｖｅｍｅｎｔ ｐａｔｈ ｕｓｉｎｇ ｇｒｉｄ ｍａｐ”と題された米国特許第２００４−０１１６８６４号明細書に開示されている。また、ここでは、グリッド位置識別システム（ｇｒｉｄ ｉｄｅｎｔｉｆｙｉｎｇ ｌｏｃａｔｉｏｎ ｓｙｓｔｅｍ）に基づいたマップ作成に関して説明しているが、マップ内で移動体の位置または他の客体と関連した非障害物領域から障害物または障害物領域の位置を識別するための他の位置識別基盤システムが利用されうる。
【００１７】
経路生成部１１０は、１次的にグリッドマップを縮小して生成される縮小マップに基づいて概略経路を生成し、２次的に縮小前の元の概略経路を複数個の区間に分割した後、該分割された区間別に詳細経路を生成する。以後に、これら分割された経路は、順次に組合わせられて元のグリッドマップに対する詳細経路が生成されうる。経路生成部１１０は、多様な経路生成方法を利用することができるが、ここでは、Ａスター（Ａ＊）アルゴリズムを用いて経路を生成すると仮定する。他の方法として、経路は、Ｄスター（Ｄ＊）アルゴリズム、他のアルゴリズムまたは他のアルゴリズムの組合わせを用いて生成されうる。
【００１８】
簡略に、Ａスターアルゴリズムは、与えられた初期ノードから（一つ以上の可能な目標のうち）一つの目標モードまでの最小コスト経路を探すベストファーストグラフ探索アルゴリズムである。開始点から目標点までのあらゆる可能な経路は、コスト増加順序によって順次に試験されうる。したがって、Ａスターは、ツリーからノードを訪問する探索順序を決定する距離−プラス−コスト発見的関数（ｄｉｓｔａｎｃｅ−ｐｌｕｓ−ｃｏｓｔ ｈｅｕｒｉｓｔｉｃ ｆｕｎｃｔｉｏｎ）（一般的に、ｆ（ｘ）で表わす）を利用する。距離−プラス−コスト発見的関数は、２個の関数の和であり得る。２個の関数は、開始ノードから現在ノードへのコストである経路−コスト関数（ｐａｔｈ−ｃｏｓｔ ｆｕｎｃｔｉｏｎ）（一般的に、ｇ（ｘ）で表わす）と目標までの距離の許容可能な“発見的予測（ｈｅｕｒｉｓｔｉｃ ｅｓｔｉｍａｔｅ）”（一般的に、ｈ（ｘ）で表わす）である。
【００１９】
Ａスターアルゴリズムは、Ｈａｒｔ，Ｐ．Ｅ．，Ｎｉｌｓｓｏｎ，Ｎ．Ｊ．，Ｒａｐｈａｅｌ，Ｂ．，“Ａ Ｆｏｒｍａｌ Ｂａｓｉｓ ｆｏｒ ｔｈｅ Ｈｅｕｒｉｓｔｉｃ Ｄｅｔｅｒｍｉｎａｔｉｏｎ ｏｆ Ｍｉｎｉｍｕｍ Ｃｏｓｔ Ｐａｔｈｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｆ Ｓｙｓｔｅｍｓ Ｓｃｉｅｎｃｅ ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ，ｖｏｌ．ｓｓｃ−４，Ｎｏ．２（１９６８）で発見されうる。Ｄスターアルゴリズムは、Ａスターアルゴリズムの変形で走行間に概略経路で方向変化が発生する時、以前探索結果を再利用して素早い探索を可能にする。しかし、実際具現で、イメージピラミッドを利用したＡスターアルゴリズムは、通常、Ｄスターアルゴリズムに比べてさらに早い処理速度を表わすことができる。異なる分割されたグリッドマップの間に異なるアルゴリズムを利用することが可能であるが、効率的でないこともある。ここで、例えば、以前経路結果は、後続探索に利用されることができ、以前及び現在探索アルゴリズムが同一である必要はない。Ｄスターアルゴリズムは、“Ｏｐｔｉｍａｌ ａｎｄ Ｅｆｆｉｃｉｅｎｔ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｆｏｒ Ｐａｒｔｉａｌｌｙ−Ｋｎｏｗｎ Ｅｎｖｉｒｏｎｍｅｎｔｓ”，Ｐｒｏｃｅｅｄｉｎｇ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ，Ｓｔｅｎｔｚ，Ａｎｔｈｏｎｙ（１９９４）で論議されている。同様に、ここに統合されたＡスターアルゴリズム及びＤスターアルゴリズムだけではなく、他のアルゴリズムが、Ｈ．Ｃｈｏｓｅｔ，Ｋ．Ｌｙｎｃｈ，Ｓ．Ｈｕｔｃｈｉｎｓｏｎ，Ｇ．Ｋａｎｔｏｒ，Ｗ．Ｂｕｒｇａｒｄ，Ｌ．Ｋａｖｒａｋｉ，ａｎｄ Ｓ．Ｔｈｒｕｎ，“Ｐｒｉｎｃｉｐｌｅｓｏｆ Ｒｏｂｏｔ Ｍｏｔｉｏｎ，”ｐｐ．５２７〜５３６に論議されている。ここで、“Ｐｒｉｎｃｉｐｌｅｓ ｏｆ Ｒｏｂｏｔ Ｍｏｔｉｏｎ”は、移動体が定義された経路によるプロセスについての説明を含んでいる。したがって、保存部１２０は、経路生成で利用されるグリッドマップ及び経路生成装置１００の動作に必要なアプリケーションデータなどを保存することができる。また、保存部１２０は、経路生成部１１０の経路生成動作過程で発生するデータの読み取り及び書き込みが実行される可用メモリ領域を含む。
【００２０】
経路生成部１１０は、マップ縮小部１１２、概略経路生成部１１４及び詳細経路生成部１１６を含む。
【００２１】
グリッドマップは、通常、赤外線センサー、超音波センサー、またはレーザセンサーなどの距離センサーを用いて獲得され、特定位置または領域で障害物がある確率情報を含む。このようなグリッドマップは、移動ロボットのような移動体のサイズを考慮しないものであって、このようなグリッドマップを用いて移動体が走行すれば、経路が障害物または障害物領域と衝突するように定義されていないとしても、移動体のフレーム部分が障害物に衝突することができる。したがって、マップ縮小部１１２は、移動体のサイズを考慮して、新たに生成される縮小されたグリッドマップで移動体を一点に縮小させて壁面またはエッジや障害物または障害物領域を移動体のサイズを考慮して厚くする。縮小されたグリッドマップの自由領域、すなわち、移動体が障害物または障害物領域と衝突せずに自在に動くことができる自由領域を決定して、自由領域情報を含むグリッドマップを生成する。
【００２２】
マップ縮小部１１２は、決定された自由領域情報を含むグリッドマップを縮小して縮小マップを生成する。グリッドマップの縮小時には、アンチエイリアシングフィルタリングプロセスを用いてグリッドマップを縮小することができる。
【００２３】
付加的なまたは代案的な要素が縮小されたグリッドマップを生成するが、具現されるように縮小を定義するときに考慮されうる。例えば、移動体のサイズが２０ｃｍであり、１ｃｍのグリッドセルが１ドット（ｄｏｔ）にマッピングされるとき、元のグリッドマップの縮小比率が１／２０以下に縮小されれば、存在する障害物が縮小されたグリッドマップに適切に反映されることができない。したがって、この場合、グリッドマップ縮小の比率は、移動体のサイズが１ドットにマッピングされるときの縮小比率に制限されうる。これは、グリッドマップを移動体のサイズに基づいて正規化すると考えられうる。簡略に、一実施形態で、経路を概略化する前に壁または障害物のサイズを増加させる理由は、移動体が壁または障害物から所定空間内で動く場合に対することであり得る。また、壁または障害物の幅を増加させる代わりに、壁及び障害物の幅を減少させることも可能であり、この場合に、経路計画は、移動体と壁または障害物との間の衝突が少なくとも防止されることができる最短距離に基づいて実行可能である。
【００２４】
縮小マップを用いた経路設定に必要な開始点と目標点の座標は、縮小されたグリッドマップに合わせて変換する。元のグリッドマップを１／Ｎ２に線形的に縮小するならば、それぞれの座標に１／Ｎを乗算する。開始点と目標点の場合、開始点と目標点のそれぞれの座標に１／Ｎを乗算した後、縮小されたグリッドマップ上で変換された座標と最も近い自由領域の座標とを捜して開始点と目標点とを設定することができる。
【００２５】
線形的縮小が説明されたが、元のグリッドマップの非線形的縮小も可能である。この場合に、特定グリッドマップが非線形的に縮小されて経路計画を経れば、グリッドマップは、経路探索のために拡大される時、例えば、単純に２倍に拡大する代わりに、非線形的縮小に反比例して非線形的に拡大されうる。
【００２６】
概略経路生成部１１４は、縮小マップを用いて開始点から目標点までの概略経路を生成する。概略経路は、設定された開始点から目標点までの経路としてＡスターアルゴリズムを用いて探索されうる。
【００２７】
詳細経路生成部１１６は、元のグリッドマップで探索された経路を少なくとも二つ以上の区間に分け、該分けられた区間別開始点から目標点まで経路を探索することで、詳細経路を生成する。以下で、詳細経路を生成する動作について詳細に説明する。
【００２８】
まず、詳細経路生成部１１６は、概略経路上の経路点を縮小前の自由領域情報を含むグリッドマップにマップ縮小部１１２によりマッピングする。例えば、開始点と目標点との間で移動体が移動する点になる経路点のうち、経路点３１と経路点３２とが図４のグリッドマップ４１０にある。移動体は、各経路点をそれぞれの目標点として経路点ごとに移動する。マッピングの結果として、縮小されたグリッドマップから元のグリッドマップ上でマッピングされた経路点のうち一部経路点（または、開始点または目標点）が、移動体が移動可能な自由領域の外側にマッピングされうる。したがって、詳細経路生成部１１６は、マッピングされた経路点のうち、経路点が自由領域の外部（例えば、障害物または障害物領域の内部）に位置する経路点の有無を確認し、自由領域の外部に位置する経路点がある場合、確認された経路点を元のグリッドマップでそれぞれ最も近い自由領域に位置調整する。
【００２９】
その後、詳細経路生成部１１６は、縮小されたグリッドマップの概略経路を複数個の区間に分割し、元のグリッドマップの分割された区間ごとに開始点及び目標点を設定して、分割された区間別に経路を再び設定して、最終詳細経路を生成することができる。
【００３０】
詳細経路生成部１１６は、経路計算に利用される可用メモリ領域のサイズ及び／または処理能力に基づいて経路区間を、例えば、決定された個数の区間及びそれぞれのサイズに分割することができる。
【００３１】
例えば、Ａスターアルゴリズムによる経路探索時、一つのグリッド当たり必要なメモリ量は１８バイト（Ｂｙｔｅ）であり得る。したがって、グリッドマップ上で経路点のうち開始点及び目標点が決定されれば、経路計算に必要なメモリサイズが計算されうる。一実施形態で、詳細な全体経路が単一経路プロセスを用いて従来の経路生成に比べて短時間に生成されるように、別個の区間に分割された経路区間に対して、あらゆる区間に対して並列経路生成プロセッシングが具現可能である。例えば、概略経路を元のグリッドマップに再びマッピングして元のグリッドマップを分割するより、元のグリッドマップが分割された概略経路に基づいてローカルマップに分割されることができ、適切な探索アルゴリズム、例えば、Ａスターアルゴリズムがそれぞれのローカルグリッドマップに適用可能である。各ローカルグリッドマップに対して結果的な詳細経路は、その後に元のグリッドマップ全体を経るのに必要な全体経路を通じて順に、移動体によって個別的に利用されうる。縮小グリッドマップからの概略経路点が、元のグリッドマップにマッピングされ、自由領域に位置調整された経路点をＰＳ、ＰＳ＋１、ＰＳ＋２、．．．ＰＳ＋Ｎ（ここで、Ｎは整数）で表わし、ＰＳが開始点であり、ＰＳ＋Ｎが目標点と仮定する。
【００３２】
詳細経路生成部１１６は、自由領域上に位置された経路上の元の開始点から目標点に向ける経路点のうち元の開始点（ＰＳ）からの経路計算時に可用メモリサイズを超えない経路点（例えば、ＰＳ＋１０）を目標点とする区間を設定し、該設定された区間を含むグリッドマップを用いて詳細経路を生成することができる。その後、詳細経路生成部１１６は、以前区間の目標点（ＰＳ＋１０）を開始点とし、可用メモリサイズを超えない範囲の経路点を目標点（例えば、ＰＳ＋２０）とする区間を設定し、該設定された区間を含むグリッドマップを用いて詳細経路を生成することができる。このように、区間設定時に最後の区間が開始点から元の目標点（ＰＳ＋Ｎ）までに設定されることができ、該設定された区間で詳細経路を生成することができる。
【００３３】
このような区間設定時に各区間は、一定部分重なるように設定しうる。例えば、最初の区間の目標点がＰＳ＋１０である場合、二番目の区間の開始点はＰＳ＋９に設定することができる。詳細経路生成部１１６は、このように設定された区間別詳細経路を組み合わせて最終経路を生成することができる。
【００３４】
詳細経路生成部１１６は、最終詳細経路上に位置する経路点のうちから方向が変わる地点に位置する経由点を選択することができる。移動体は、開始点、目標点及び選択された経由点情報を用いてグリッドマップ上の生成された経路を移動することができる。ここで、移動体は、物理的な移動ロボットであり、経路探索アプリケーションで探索された経路を探索するように設定された所定のオブジェクト、例えば、ゲームアプリケーションのキャラクターになり得る。
【００３５】
経路生成装置１１０または装置１００は、携帯電話、ＰＭＰ、ＰＤＡなど多様な電子装置として具現可能であり、経路を生成して移動可能な移動ロボットなどの移動体としても具現可能である。経路生成装置１１０は、移動体として具現されるとき、グリッドマップの生成、移動体の移動量の感知などのためのセンシングユニット、移動体を移動させるための走行ユニットなどをさらに含みうる。センシングユニットは、移動体周辺の２次元または３次元マップを生成することで、例えば、移動ロボット周辺の元のグリッドマップの一部または全部を潜在的に生成することができる。
【００３６】
前述したように、一実施形態によれば、グリッドマップのサイズを縮小して縮小グリッドマップ内で概略経路を生成する。概略的な経路を元のグリッドマップに反映される複数個の区間に分割する。該分割された区間で詳細経路を再び探索して、概略経路を補完する。
【００３７】
したがって、小さいサイズのメモリを数回使って元のサイズの全体グリッドマップ上で一回に経路探索することに比べて経路探索に必要なメモリ量を、グリッドマップを縮小させる比率に比例して減らしうる。縮小マップで経路を探索するか、または全体グリッドマップ上の区間別経路を探索するので、元の全体グリッドマップでの経路探索に比べて経路探索にかかる時間が短縮される。したがって、元の全体グリッドマップでの一回の経路探索に比べて、全体経路探索に必要な時間には大きな変化がない。
【００３８】
図２Ａ及び図２Ｂは、通常の技術によるグリッドマップ縮小方法及び一実施形態によるグリッドマップ縮小方法をそれぞれ示す図である。
【００３９】
グリッドマップから物体が自在に移動することができる領域を表わす自由領域情報を含むグリッドマップが生成されれば、グリッドマップを１／Ｎ２に縮小する過程が実行される。図２Ａ及び図２Ｂは、グリッドマップを１／４に縮小する方法を表わす。
【００４０】
図２Ａは、グリッドマップ２１０の１／４の情報のみ抽出して生成された縮小マップ２２０を生成する過程を表わす。このような方法によれば、図２Ａに示されたように、元の情報でＡ、Ｃ、Ｉ及びＫ情報のみ利用され、残り部分の情報がなくなってグリッドマップ縮小過程で元のグリッドマップの情報の損失によって正確な最終的経路の生成ができなくなる可能性が高い。
【００４１】
図２Ｂは、一実施形態によるアンチエイリアシングフィルタリングを利用したグリッドマップ縮小方法を表わす。一実施形態によれば、グリッドマップ２３０を４個のグリッドごとにグルーピングして、該グルーピングされたグリッドの平均を求めて縮小マップ２４０を生成する。その後、平均値を臨界値と比べてグリッドの平均値が臨界値以上である場合、１に設定し、平均値が臨界値未満である場合、０に設定する。ここで、グリッドの値が１に設定されれば、障害物があるということを表わし、０に設定されれば、障害物がないということを表わす。
【００４２】
図３は、一実施形態によるグリッドマップ縮小方法による処理結果を説明するための図である。３１０ないし３４０は、グリッドマップを表わし、白色領域は移動体が移動することができる領域を表わし、ハッチされた領域は障害物領域を表わす。グリッドマップ３１０で経路３０は、元のグリッドマップで開始点１０から目標点２０まで探索された経路である。
【００４３】
グリッドマップ３２０は、元のグリッドマップ３１０を図２Ａに示された方法を用いて１／４に縮小した図を示し、グリッドマップ３２０上では、元のグリッドマップ３１０の情報が消失されてグリッドマップ３１０の経路３０のような経路が生成されることができない。すなわち、グリッドマップ３２０のように元のグリッドマップ３１０の１／４の情報のみ抽出して生成された縮小マップを生成すれば、障害物情報がなくなって正確な経路を生成することができず、グリッドマップ３２０でのように実際に障害物を横切るようになって利用されることができない経路が生成される。
【００４４】
グリッドマップ３３０は、グリッドマップ３１０について、図２Ｂを参照して説明したようなアンチエイリアシングフィルターを利用したグリッドマップ縮小結果を表わす。グリッドマップ３３０に示されたような平均値を臨界値と比べてグリッドの平均値が臨界値以上である場合、グリッドの値を１に設定し、平均値が臨界値未満である場合、グリッドの値を０に設定すれば、図面３４０のような縮小グリッドマップが形成される。グリッドマップ３４０は、グリッドマップ３２０に比べて障害物情報の消失が少なく、元のグリッドマップ３１０でのような経路４０が生成されうる。
【００４５】
図４は、一実施形態による詳細経路生成過程を示す図である。
【００４６】
グリッドマップ４１０ないし４３０で障害物境界４０２の外部にハッチされた領域４０１は、障害物領域を表わし、障害物境界４０２の内部のハッチ領域４０３は、移動体が自在に移動することができる自由領域を表わす。
【００４７】
縮小マップで探索された経路を元のグリッドマップ上でマッピングすれば、図４のグリッドマップ４１０のように、自由領域以外の領域の外側にマッピングされる経路点３１、３２が存在することができる。
【００４８】
これを補正するために、一実施形態によれば、経路点のうち自由領域の外部に位置する経路点の有無を確認し、自由領域の外部に位置する経路点がある場合、確認された経路点をそれぞれ最も近い自由領域に位置調整する。経路点が自由領域にマッピングされれば、グリッドマップ４１０上の経路点は、グリッドマップ４２０でのように位置調整される。
【００４９】
しかし、グリッドマップ４２０に表示された経路点を繋げれば、グリッドマップ４３０の部分拡大図面４３５に示されたように、移動体が通り過ぎない領域（自由領域を超える領域）を通る直線経路が生じうる。したがって、一実施形態によれば、縮小マップで生成された概略経路を元のグリッドマップ上で再び計画する。すなわち、区間経路生成のために元のグリッドマップに再びマッピングされる概略経路の対応する部分は、定義された自由領域のみを通るように再定義されうる。
【００５０】
この際、例えば、縮小グリッドマップで概略経路の探索が完了した時、経路探索のためのＡスターアルゴリズムを実行するためのメモリサイズを考慮して、概略経路を前述したように複数個の区間に分離し、区間別に経路探索を遂行して最終経路を生成する。概略経路の分割は、縮小グリッドマップ内で遂行されることもあり、元のグリッドマップ上に概略経路を再びマッピングした時、元のグリッドマップ内で遂行されることもある。
【００５１】
図５は、一実施形態による詳細経路を生成するために、概略経路を複数個の区間に分割したマップの一例を示す図である。
【００５２】
元のグリッドマップ上の経路を複数個の区間に分けて経路探索をする時には、経路探索アルゴリズム、例えば、Ａスターアルゴリズムを実行するためのメモリの可用メモリ領域のサイズを考慮する。一実施形態によれば、Ａスターアルゴリズムで経路を探すことができる最大グリッドサイズがＳＸ（Ｘ軸グリッドサイズ）×ＳＹ（Ｙ軸グリッドサイズ）であれば、開始点（ＰＳ）から始めて、ＳＸ×ＳＹ範囲内に入る経路点ＰＥまでを一つのセットで決めることができる。ここで、ＳＸ及びＳＹは、可用メモリサイズ内で可変される。図５では、元のグリッドマップ５１０で分割された区間を含むグリッドマップ部分５１２、５１４、５１６別に経路が探索されるということを表わす。例えば、Ａスターアルゴリズムで経路を探すことができる最大グリッドマップのサイズが１２８×１２８である場合、図４の４１０ないし４３０内の経路点は、図５に示されたように分離されうる。
【００５３】
図５で、経路点５０１は、経路開始点を表わし、経路点５０４は、元のグリッドマップの最後の詳細経路に対する経路目標点を表わす。経路点５０２、５０３は、経路区間を分離する基準経路点を表わす。図５では、経路点５０１から経路点５０２までを第１区間とし、経路点５０２から経路点５０３までを第２区間とし、経路点５０３から経路点５０４までを第３区間として、各区間別に経路を探索することができる。各区間別に探索された経路を組み合わせれば、最終経路になる。
【００５４】
図６は、一実施形態による経路生成過程を示す図である。
【００５５】
グリッドマップを縮小して縮小マップを生成する（Ｓ６１０）。縮小マップに基づいて概略経路を生成する（Ｓ６２０）。概略経路を複数個の区間に分割する（Ｓ６３０）。複数個の区間は、経路生成過程で発生するデータの読み取り及び書き込みが実行される可用メモリ領域のサイズに基づいて分割される。該分割された区間別に詳細経路を生成する（Ｓ６４０）。これら詳細経路から最終詳細経路が生成されうる。
【００５６】
図７は、図６に示された経路生成方法を詳細に示すフローチャートである。
【００５７】
グリッドマップから生成された経路及び移動体のサイズを考慮して物体が自在に移動することができる自由領域を決定し、自由領域情報を含むグリッドマップを縮小して縮小マップを生成する（Ｓ７１０）。
【００５８】
縮小マップに基づいて概略経路を探索する（Ｓ７２０）。
【００５９】
探索された経路上の経路点を元のグリッドマップにマッピングし（Ｓ７３０）、該マッピングされた経路点のうち自由領域から外れている経路点があれば（Ｓ７４０）、マッピングされた経路上の経路点をそれぞれの経路点ごとに最も近い自由領域の位置に経路点の位置を調整する（Ｓ７５０）。
【００６０】
マッピングされた経路（すなわち、元のグリッドマップ上にマッピングされた経路）上の経路点を分離して経路を複数個の区間に分割し（Ｓ７６０）、該分割された区間別に開始点及び目標点を設定して、区間別に詳細経路を生成する（Ｓ７７０）。区間別詳細経路を組み合わせて最終詳細経路を生成する（Ｓ７８０）。最後に、最終詳細区間の経路が、以前に生成された区間経路から外れなければ、後続的な最終詳細経路生成が進行しうる。
【００６１】
前述した実施形態に付け加えて、実施形態がコンピュータ判読可能コード／命令語を通じて媒体、例えば、コンピュータ判読可能媒体内（ｉｎ）／上（ｏｎ）に具現されて、前述した実施形態を具現するための少なくとも一つのプロセッシングデバイスを制御することができる。媒体は、コンピュータ判読可能コードの保存及び／または伝送を許容する、ある定義された、測定可能であり、類型の構造に対応することができる。
【００６２】
コンピュータ判読可能コードは、磁気記録媒体（例えば、ＲＯＭ、フロッピー（登録商標）ディスク、ハードディスクなど）、光記録媒体（例えば、ＣＤ−ＲＯＭ、またはＤＶＤ）及びキャリアウェーブを伝達するか含む非一時的伝送媒体（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ ｔｒａｎｓｍｉｓｓｉｏｎ ｍｅｄｉａ）のような、記録媒体を含む媒体だけではなく、例えば、インターネットのハードウェア構成要素などに、多様な方式で媒体に記録／伝送することができる。したがって、媒体は、例えば、一実施形態によって、ビットスツリームを伝達するデバイスのように、信号または情報を含むか伝達すると定義されて測定可能な非一時的な構造であり得る。媒体は、または分散ネットワークであり、したがって、コンピュータ判読可能コードが分散方式で保存されて実行可能である。また、プロセッシングエレメントは、プロセッサ、コンピュータプロセッサを含むことができ、プロセッシングエレメントは単一デバイスに含まれるか、分散されうる。
【産業上の利用可能性】
【００６３】
本発明は、グリッドマップを利用した経路生成装置及び方法関連の技術分野に適用可能である。
【特許請求の範囲】
【請求項１】
マップを縮小して生成される縮小マップに基づいてマップと関連して動く移動体に対する概略経路を生成し、前記マップを概略経路の分割に基づいて複数個の区間に分割し、前記分割された区間別に、前記概略経路に基づいて詳細経路を生成する経路生成部を含むことを特徴とする経路生成装置。
【請求項２】
前記マップは、
前記移動体が障害物と衝突せずに自在に移動することができる自由領域及び障害物の情報を含むことを特徴とする請求項１に記載の経路生成装置。
【請求項３】
前記経路生成部は、
移動体のサイズを考慮して、前記移動体が障害物と衝突なしに自在に移動することができる領域を表わす自由領域を決定し、前記決定された自由領域の情報を含むマップを縮小して、前記縮小マップを生成することを特徴とする請求項１に記載の経路生成装置。
【請求項４】
前記マップは、グリッドマップであり、前記経路生成部は、前記グリッドマップの異なるグリッドについての情報をそれぞれアンチエイリアシングフィルタリングして、前記グリッドマップを縮小することを特徴とする請求項３に記載の経路生成装置。
【請求項５】
前記経路生成部は、
前記詳細経路を生成するために、前記縮小マップ上で生成された概略経路上の経路点を前記分割前のグリッドマップにマッピングすることを特徴とする請求項３に記載の経路生成装置。
【請求項６】
前記経路生成部は、
前記詳細経路を生成するために、前記縮小マップ上で生成された前記概略経路の経路点を前記マップの分割のためのマップにマッピングすることを特徴とする請求項３に記載の経路生成装置。
【請求項７】
前記経路生成部は、
前記マッピングされた経路点のうち、前記自由領域の外部に位置する一つ以上の経路点がある場合、前記自由領域の外部に位置する一つ以上の経路点をそれぞれ最も近い自由領域に位置調整することを特徴とする請求項６に記載の経路生成装置。
【請求項８】
前記経路生成部は、
前記概略経路の分割に基づいて、前記マップを複数個の区間に分割するとき、前記マップにマッピングされた経路点を前記それぞれの分割された区間によって複数個の区間に分割し、前記分割された区間別に開始経路点及び目標経路点を設定して、前記区間別に詳細経路を再び生成し、各区間別経路を順次に組み合わせて最終詳細経路を生成することを特徴とする請求項６に記載の経路生成装置。
【請求項９】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項８に記載の経路生成装置。
【請求項１０】
前記経路生成部は、
前記マップを縮小して生成された前記縮小マップを生成することを特徴とする請求項１に記載の経路生成装置。
【請求項１１】
前記マップは、グリッドマップであり、前記経路生成部は、前記グリッドマップの決定された自由領域の各グリッドを用いて、前記グリッドマップを縮小することを特徴とする請求項１０に記載の経路生成装置。
【請求項１２】
前記マップの縮小は、
前記マップの線形縮小であることを特徴とする請求項１０に記載の経路生成装置。
【請求項１３】
前記マップの縮小は、
前記移動体のサイズによって、前記マップを正規化することに制限されることを特徴とする請求項１０に記載の経路生成装置。
【請求項１４】
前記経路生成部は、
前記詳細経路を生成するために、前記縮小マップ上で生成された概略経路上の経路点を前記分割前のグリッドマップにマッピングすることを特徴とする請求項１に記載の経路生成装置。
【請求項１５】
前記経路生成部の動作過程で発生するデータの読み取り及び書き込みが実行されるメモリをさらに含むことを特徴とする請求項１に記載の経路生成装置。
【請求項１６】
前記経路生成部は、
前記メモリの可用領域のサイズに基づいて、前記概略経路を複数個の区間に分割することを特徴とする請求項１５に記載の経路生成装置。
【請求項１７】
前記それぞれの分割された区間別に、それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項１５に記載の経路生成装置。
【請求項１８】
前記それぞれの分割された区間別に、前記それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項１に記載の経路生成装置。
【請求項１９】
前記移動体は、
前記詳細経路を移動可能に制御される移動ロボットであることを特徴とする請求項１に記載の経路生成装置。
【請求項２０】
前記移動体は、
コンピュータが生成した環境でのアバターであることを特徴とする請求項１に記載の経路生成装置。
【請求項２１】
前記装置は、
携帯電話、ＰＭＰ及びＰＤＡのうち一つであることを特徴とする請求項１に記載の経路生成装置。
【請求項２２】
マップで物体の経路を生成する方法として、
前記マップを縮小して生成された縮小マップで概略経路を生成する段階と、
前記概略経路の分割に基づいて、前記マップを複数個の区間に分割する段階と、
前記概略経路に基づいて、前記分割された区間別に詳細経路を生成する段階と、
を含むことを特徴とする経路生成方法。
【請求項２３】
前記マップは、
前記物体が障害物と衝突せずに自在に移動することができる自由領域及び障害物の情報を含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項２４】
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす自由領域を決定し、前記自由領域情報を含むグリッドマップを縮小して、前記縮小マップを生成する段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項２５】
前記マップは、グリッドマップであり、前記グリッドマップを縮小する段階は、前記グリッドマップの異なるグリッドからの情報をそれぞれアンチエイリアシングフィルタリングして実行されることを特徴とする請求項２４に記載の経路生成方法。
【請求項２６】
前記概略経路を複数個の区間に分割する段階は、
前記概略経路上の経路点を前記マップにマッピングする段階を含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項２７】
前記概略経路を複数個の区間に分割する段階は、
前記マッピングされた経路点のうち、前記マップの自由領域の外部に位置する一つ以上の経路点がある場合、前記自由領域の外部に位置する一つ以上の経路点をそれぞれ最も近い自由領域に位置調整する段階を含むことを特徴とする請求項２６に記載の経路生成方法。
【請求項２８】
前記概略経路を複数個の区間に分割する段階は、前記元のグリッドマップにマッピングされた経路点を複数個の区間に分割する段階をさらに含み、
前記詳細経路を生成する段階は、前記分割された区間別にそれぞれ開始経路点及び目標経路点を設定して、前記区間別に詳細経路を再び生成し、各区間別詳細経路を順次に組み合わせて最終詳細経路を生成することを特徴とする請求項２６に記載の経路生成方法。
【請求項２９】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項２８に記載の経路生成方法。
【請求項３０】
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす自由領域を決定し、前記決定された自由領域の情報を含むマップを縮小して、前記縮小マップを生成する段階をさらに含むことを特徴とする請求項２６に記載の経路生成方法。
【請求項３１】
前記マップを縮小して生成された前記縮小マップを生成する段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項３２】
前記マップは、グリッドマップであり、前記グリッドマップは、前記グリッドマップの決定された自由領域の各グリッドを用いて縮小されることを特徴とする請求項３１に記載の経路生成方法。
【請求項３３】
前記マップの縮小は、
前記マップの線形縮小であることを特徴とする請求項３１に記載の経路生成方法。
【請求項３４】
前記マップの縮小は、
前記物体のサイズによって、前記マップを正規化することに制限されることを特徴とする請求項３１に記載の経路生成方法。
【請求項３５】
前記詳細経路を生成するために、前記縮小マップ上で生成された概略経路上の経路点を前記分割前のグリッドマップにマッピングする段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項３６】
メモリの可用領域のサイズに基づいて、前記概略経路が前記複数個の区間に分割されることを特徴とする請求項２２に記載の経路生成方法。
【請求項３７】
前記それぞれの分割された区間別に、それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項３６に記載の経路生成方法。
【請求項３８】
前記それぞれの分割された区間別に、前記それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項２２に記載の経路生成方法。
【請求項３９】
前記物体は、移動ロボットであり、前記方法は、前記移動ロボットが前記詳細経路を移動するように制御する段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項４０】
前記移動ロボットの環境を感知し、障害物情報及び前記移動ロボットが、前記障害物情報と表現される障害物と衝突せずに自在に移動することができる自由領域情報を含むマップを生成する段階をさらに含むことを特徴とする請求項３９に記載の経路生成方法。
【請求項４１】
前記移動体は、
コンピュータが生成した環境でのアバターであることを特徴とする請求項２２に記載の経路生成方法。
【請求項４２】
前記アバターが前記環境内で前記詳細経路に沿って移動するように制御する段階をさらに含むことを特徴とする請求項４１に記載の経路生成方法。
【請求項４３】
経路生成装置として、
縮小マップに基づいてマップと関連して動く物体に対する概略経路を生成し、前記縮小マップに対する前記概略経路のマッピングに基づいて、前記マップを複数個の区間に分割し、前記分割された区間別に少なくとも一つの探索アルゴリズムを用いて詳細経路を生成する経路生成部を含み、
前記経路生成部は、前記概略経路からの点に基づいて、前記分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成することを特徴とする経路生成装置。
【請求項４４】
前記経路生成アルゴリズムは、
Ａスターアルゴリズム及びＤスターアルゴリズムのうち少なくとも一つであることを特徴とする請求項４３に記載の経路生成装置。
【請求項４５】
前記経路生成部は、
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす前記マップの自由領域を決定し、前記決定された自由領域情報を含むマップを縮小して、前記縮小マップを生成することを特徴とする請求項４３に記載の経路生成装置。
【請求項４６】
前記経路生成部は、
前記詳細経路を生成するために、前記それぞれの開始経路点及び前記目標経路点を前記分割前のグリッドマップにマッピングすることを特徴とする請求項４５に記載の経路生成装置。
【請求項４７】
前記マッピングされた経路点のうち、前記自由領域の外部に位置する一つ以上の経路点がある場合、前記経路生成部は、前記自由領域の外部に位置する一つ以上の経路点をそれぞれ最も近い自由領域にそれぞれ位置調整することを特徴とする請求項４５に記載の経路生成装置。
【請求項４８】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項４３に記載の経路生成装置。
【請求項４９】
経路生成方法として、
縮小マップのマップと関連して動く物体に対する概略経路を生成し、前記マップへの前記縮小マップの概略経路のマッピングに基づいて、前記マップを複数個の区間に分割し、前記分割された区間別に少なくとも一つの探索アルゴリズムをそれぞれ用いて詳細経路を生成する段階を含み、
前記マップを分割する段階は、前記概略経路からの点に基づいて、前記分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成することを特徴とする経路生成方法。
【請求項５０】
前記経路生成アルゴリズムは、
Ａスターアルゴリズム及びＤスターアルゴリズムのうち少なくとも一つであることを特徴とする請求項４９に記載の経路生成方法。
【請求項５１】
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす前記マップの自由領域を決定し、前記決定された自由領域の情報を含むマップを縮小して、前記縮小マップを生成する段階をさらに含むことを特徴とする請求項４９に記載の経路生成方法。
【請求項５２】
前記詳細経路を生成するために、前記それぞれの開始経路点及び前記目標経路点が、前記分割前のグリッドマップにマッピングされることを特徴とする請求項５１に記載の経路生成方法。
【請求項５３】
前記マッピングされた経路点のうち、前記自由領域の外部に位置する一つ以上の経路点がある場合、前記自由領域の外部に位置する一つ以上の経路点がそれぞれ最も近い自由領域にそれぞれ位置調整されることを特徴とする請求項５１に記載の経路生成方法。
【請求項５４】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項４９に記載の経路生成方法。
【請求項５５】
請求項２２に記載の方法を具現した少なくとも一つのプロセッシングデバイスを制御するためのコンピュータ判読可能コードを含む少なくとも一つのコンピュータ判読可能媒体。
【請求項５６】
請求項４９に記載の方法を具現した少なくとも一つのプロセッシングデバイスを制御するためのコンピュータ判読可能コードを含む少なくとも一つのコンピュータ判読可能媒体。
【請求項１】
マップを縮小して生成される縮小マップに基づいてマップと関連して動く移動体に対する概略経路を生成し、前記マップを概略経路の分割に基づいて複数個の区間に分割し、前記分割された区間別に、前記概略経路に基づいて詳細経路を生成する経路生成部を含むことを特徴とする経路生成装置。
【請求項２】
前記マップは、
前記移動体が障害物と衝突せずに自在に移動することができる自由領域及び障害物の情報を含むことを特徴とする請求項１に記載の経路生成装置。
【請求項３】
前記経路生成部は、
移動体のサイズを考慮して、前記移動体が障害物と衝突なしに自在に移動することができる領域を表わす自由領域を決定し、前記決定された自由領域の情報を含むマップを縮小して、前記縮小マップを生成することを特徴とする請求項１に記載の経路生成装置。
【請求項４】
前記マップは、グリッドマップであり、前記経路生成部は、前記グリッドマップの異なるグリッドについての情報をそれぞれアンチエイリアシングフィルタリングして、前記グリッドマップを縮小することを特徴とする請求項３に記載の経路生成装置。
【請求項５】
前記経路生成部は、
前記詳細経路を生成するために、前記縮小マップ上で生成された概略経路上の経路点を前記分割前のグリッドマップにマッピングすることを特徴とする請求項３に記載の経路生成装置。
【請求項６】
前記経路生成部は、
前記詳細経路を生成するために、前記縮小マップ上で生成された前記概略経路の経路点を前記マップの分割のためのマップにマッピングすることを特徴とする請求項３に記載の経路生成装置。
【請求項７】
前記経路生成部は、
前記マッピングされた経路点のうち、前記自由領域の外部に位置する一つ以上の経路点がある場合、前記自由領域の外部に位置する一つ以上の経路点をそれぞれ最も近い自由領域に位置調整することを特徴とする請求項６に記載の経路生成装置。
【請求項８】
前記経路生成部は、
前記概略経路の分割に基づいて、前記マップを複数個の区間に分割するとき、前記マップにマッピングされた経路点を前記それぞれの分割された区間によって複数個の区間に分割し、前記分割された区間別に開始経路点及び目標経路点を設定して、前記区間別に詳細経路を再び生成し、各区間別経路を順次に組み合わせて最終詳細経路を生成することを特徴とする請求項６に記載の経路生成装置。
【請求項９】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項８に記載の経路生成装置。
【請求項１０】
前記経路生成部は、
前記マップを縮小して生成された前記縮小マップを生成することを特徴とする請求項１に記載の経路生成装置。
【請求項１１】
前記マップは、グリッドマップであり、前記経路生成部は、前記グリッドマップの決定された自由領域の各グリッドを用いて、前記グリッドマップを縮小することを特徴とする請求項１０に記載の経路生成装置。
【請求項１２】
前記マップの縮小は、
前記マップの線形縮小であることを特徴とする請求項１０に記載の経路生成装置。
【請求項１３】
前記マップの縮小は、
前記移動体のサイズによって、前記マップを正規化することに制限されることを特徴とする請求項１０に記載の経路生成装置。
【請求項１４】
前記経路生成部は、
前記詳細経路を生成するために、前記縮小マップ上で生成された概略経路上の経路点を前記分割前のグリッドマップにマッピングすることを特徴とする請求項１に記載の経路生成装置。
【請求項１５】
前記経路生成部の動作過程で発生するデータの読み取り及び書き込みが実行されるメモリをさらに含むことを特徴とする請求項１に記載の経路生成装置。
【請求項１６】
前記経路生成部は、
前記メモリの可用領域のサイズに基づいて、前記概略経路を複数個の区間に分割することを特徴とする請求項１５に記載の経路生成装置。
【請求項１７】
前記それぞれの分割された区間別に、それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項１５に記載の経路生成装置。
【請求項１８】
前記それぞれの分割された区間別に、前記それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項１に記載の経路生成装置。
【請求項１９】
前記移動体は、
前記詳細経路を移動可能に制御される移動ロボットであることを特徴とする請求項１に記載の経路生成装置。
【請求項２０】
前記移動体は、
コンピュータが生成した環境でのアバターであることを特徴とする請求項１に記載の経路生成装置。
【請求項２１】
前記装置は、
携帯電話、ＰＭＰ及びＰＤＡのうち一つであることを特徴とする請求項１に記載の経路生成装置。
【請求項２２】
マップで物体の経路を生成する方法として、
前記マップを縮小して生成された縮小マップで概略経路を生成する段階と、
前記概略経路の分割に基づいて、前記マップを複数個の区間に分割する段階と、
前記概略経路に基づいて、前記分割された区間別に詳細経路を生成する段階と、
を含むことを特徴とする経路生成方法。
【請求項２３】
前記マップは、
前記物体が障害物と衝突せずに自在に移動することができる自由領域及び障害物の情報を含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項２４】
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす自由領域を決定し、前記自由領域情報を含むグリッドマップを縮小して、前記縮小マップを生成する段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項２５】
前記マップは、グリッドマップであり、前記グリッドマップを縮小する段階は、前記グリッドマップの異なるグリッドからの情報をそれぞれアンチエイリアシングフィルタリングして実行されることを特徴とする請求項２４に記載の経路生成方法。
【請求項２６】
前記概略経路を複数個の区間に分割する段階は、
前記概略経路上の経路点を前記マップにマッピングする段階を含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項２７】
前記概略経路を複数個の区間に分割する段階は、
前記マッピングされた経路点のうち、前記マップの自由領域の外部に位置する一つ以上の経路点がある場合、前記自由領域の外部に位置する一つ以上の経路点をそれぞれ最も近い自由領域に位置調整する段階を含むことを特徴とする請求項２６に記載の経路生成方法。
【請求項２８】
前記概略経路を複数個の区間に分割する段階は、前記元のグリッドマップにマッピングされた経路点を複数個の区間に分割する段階をさらに含み、
前記詳細経路を生成する段階は、前記分割された区間別にそれぞれ開始経路点及び目標経路点を設定して、前記区間別に詳細経路を再び生成し、各区間別詳細経路を順次に組み合わせて最終詳細経路を生成することを特徴とする請求項２６に記載の経路生成方法。
【請求項２９】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項２８に記載の経路生成方法。
【請求項３０】
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす自由領域を決定し、前記決定された自由領域の情報を含むマップを縮小して、前記縮小マップを生成する段階をさらに含むことを特徴とする請求項２６に記載の経路生成方法。
【請求項３１】
前記マップを縮小して生成された前記縮小マップを生成する段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項３２】
前記マップは、グリッドマップであり、前記グリッドマップは、前記グリッドマップの決定された自由領域の各グリッドを用いて縮小されることを特徴とする請求項３１に記載の経路生成方法。
【請求項３３】
前記マップの縮小は、
前記マップの線形縮小であることを特徴とする請求項３１に記載の経路生成方法。
【請求項３４】
前記マップの縮小は、
前記物体のサイズによって、前記マップを正規化することに制限されることを特徴とする請求項３１に記載の経路生成方法。
【請求項３５】
前記詳細経路を生成するために、前記縮小マップ上で生成された概略経路上の経路点を前記分割前のグリッドマップにマッピングする段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項３６】
メモリの可用領域のサイズに基づいて、前記概略経路が前記複数個の区間に分割されることを特徴とする請求項２２に記載の経路生成方法。
【請求項３７】
前記それぞれの分割された区間別に、それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項３６に記載の経路生成方法。
【請求項３８】
前記それぞれの分割された区間別に、前記それぞれの詳細経路の生成は、少なくとも一つの探索アルゴリズムを通じて並列的にそれぞれ実行されることを特徴とする請求項２２に記載の経路生成方法。
【請求項３９】
前記物体は、移動ロボットであり、前記方法は、前記移動ロボットが前記詳細経路を移動するように制御する段階をさらに含むことを特徴とする請求項２２に記載の経路生成方法。
【請求項４０】
前記移動ロボットの環境を感知し、障害物情報及び前記移動ロボットが、前記障害物情報と表現される障害物と衝突せずに自在に移動することができる自由領域情報を含むマップを生成する段階をさらに含むことを特徴とする請求項３９に記載の経路生成方法。
【請求項４１】
前記移動体は、
コンピュータが生成した環境でのアバターであることを特徴とする請求項２２に記載の経路生成方法。
【請求項４２】
前記アバターが前記環境内で前記詳細経路に沿って移動するように制御する段階をさらに含むことを特徴とする請求項４１に記載の経路生成方法。
【請求項４３】
経路生成装置として、
縮小マップに基づいてマップと関連して動く物体に対する概略経路を生成し、前記縮小マップに対する前記概略経路のマッピングに基づいて、前記マップを複数個の区間に分割し、前記分割された区間別に少なくとも一つの探索アルゴリズムを用いて詳細経路を生成する経路生成部を含み、
前記経路生成部は、前記概略経路からの点に基づいて、前記分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成することを特徴とする経路生成装置。
【請求項４４】
前記経路生成アルゴリズムは、
Ａスターアルゴリズム及びＤスターアルゴリズムのうち少なくとも一つであることを特徴とする請求項４３に記載の経路生成装置。
【請求項４５】
前記経路生成部は、
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす前記マップの自由領域を決定し、前記決定された自由領域情報を含むマップを縮小して、前記縮小マップを生成することを特徴とする請求項４３に記載の経路生成装置。
【請求項４６】
前記経路生成部は、
前記詳細経路を生成するために、前記それぞれの開始経路点及び前記目標経路点を前記分割前のグリッドマップにマッピングすることを特徴とする請求項４５に記載の経路生成装置。
【請求項４７】
前記マッピングされた経路点のうち、前記自由領域の外部に位置する一つ以上の経路点がある場合、前記経路生成部は、前記自由領域の外部に位置する一つ以上の経路点をそれぞれ最も近い自由領域にそれぞれ位置調整することを特徴とする請求項４５に記載の経路生成装置。
【請求項４８】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項４３に記載の経路生成装置。
【請求項４９】
経路生成方法として、
縮小マップのマップと関連して動く物体に対する概略経路を生成し、前記マップへの前記縮小マップの概略経路のマッピングに基づいて、前記マップを複数個の区間に分割し、前記分割された区間別に少なくとも一つの探索アルゴリズムをそれぞれ用いて詳細経路を生成する段階を含み、
前記マップを分割する段階は、前記概略経路からの点に基づいて、前記分割された区間それぞれに開始経路点及び目標経路点を設定し、それぞれ設定された開始経路点及び目標経路点を用いてそれぞれの分割された区間に適用される経路生成アルゴリズムに基づいて、分割された区間のそれぞれで詳細経路を生成することを特徴とする経路生成方法。
【請求項５０】
前記経路生成アルゴリズムは、
Ａスターアルゴリズム及びＤスターアルゴリズムのうち少なくとも一つであることを特徴とする請求項４９に記載の経路生成方法。
【請求項５１】
前記物体のサイズを考慮して、前記物体が障害物と衝突なしに自在に移動することができる領域を表わす前記マップの自由領域を決定し、前記決定された自由領域の情報を含むマップを縮小して、前記縮小マップを生成する段階をさらに含むことを特徴とする請求項４９に記載の経路生成方法。
【請求項５２】
前記詳細経路を生成するために、前記それぞれの開始経路点及び前記目標経路点が、前記分割前のグリッドマップにマッピングされることを特徴とする請求項５１に記載の経路生成方法。
【請求項５３】
前記マッピングされた経路点のうち、前記自由領域の外部に位置する一つ以上の経路点がある場合、前記自由領域の外部に位置する一つ以上の経路点がそれぞれ最も近い自由領域にそれぞれ位置調整されることを特徴とする請求項５１に記載の経路生成方法。
【請求項５４】
前記少なくとも一つの分割された区間に対する目標経路点は、
他の分割された区間の開始経路点と重なることを特徴とする請求項４９に記載の経路生成方法。
【請求項５５】
請求項２２に記載の方法を具現した少なくとも一つのプロセッシングデバイスを制御するためのコンピュータ判読可能コードを含む少なくとも一つのコンピュータ判読可能媒体。
【請求項５６】
請求項４９に記載の方法を具現した少なくとも一つのプロセッシングデバイスを制御するためのコンピュータ判読可能コードを含む少なくとも一つのコンピュータ判読可能媒体。
【図１】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２Ａ】
【図２Ｂ】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１０−１９０８９７（Ｐ２０１０−１９０８９７Ａ）
【公開日】平成２２年９月２日（２０１０．９．２）
【国際特許分類】
【出願番号】特願２０１０−３３５９１（Ｐ２０１０−３３５９１）
【出願日】平成２２年２月１８日（２０１０．２．１８）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】ＳＡＭＳＵＮＧ ＥＬＥＣＴＲＯＮＩＣＳ ＣＯ．，ＬＴＤ．
【住所又は居所原語表記】４１６，Ｍａｅｔａｎ−ｄｏｎｇ，Ｙｅｏｎｇｔｏｎｇ−ｇｕ，Ｓｕｗｏｎ−ｓｉ，Ｇｙｅｏｎｇｇｉ−ｄｏ ４４２−７４２（ＫＲ）
【Ｆターム（参考）】
【公開日】平成２２年９月２日（２０１０．９．２）
【国際特許分類】
【出願日】平成２２年２月１８日（２０１０．２．１８）
【出願人】（３９００１９８３９）三星電子株式会社 (8,520)
【氏名又は名称原語表記】ＳＡＭＳＵＮＧ ＥＬＥＣＴＲＯＮＩＣＳ ＣＯ．，ＬＴＤ．
【住所又は居所原語表記】４１６，Ｍａｅｔａｎ−ｄｏｎｇ，Ｙｅｏｎｇｔｏｎｇ−ｇｕ，Ｓｕｗｏｎ−ｓｉ，Ｇｙｅｏｎｇｇｉ−ｄｏ ４４２−７４２（ＫＲ）
【Ｆターム（参考）】
[ Back to top ]