JP7342697B2 - 経路生成装置 - Google Patents

Description

本発明は、経路生成装置に関する。

従来、特許文献１に記載される経路生成装置が知られている。
経路生成装置は、グリッドマップを縮小した縮小マップを生成するマップ縮小部と、縮小マップに基づき移動体の概略経路を生成する概略経路生成部と、概略経路に基づき詳細経路を生成する移動体の詳細経路を生成する詳細経路生成部とを有する経路生成部を含んでいる。

マップ縮小部は、グリッドマップの複数のグリッドをグルーピングして、該グルーピングされた複数のグリッドを平均することにより縮小マップを生成している。マップ縮小部は、複数のグリッドの平均値が臨界値以上である場合、障害物があることを示す情報である「１」を平均化されたグリッドに設定し、複数のグリッドの平均値が臨界値未満である場合、障害物がないことを示す情報である「０」を平均化されたグリッドに設定する。

特開２０１０－１９０８９７号公報

ところで、複数のグリッドの平均値が臨界値未満である場合に障害物がないことを示す情報が平均化されたグリッドに設定されていると、平均化されたグリッドに対応する現実の位置には、移動体が移動できないように配置された障害物が存在する虞がある。そのため、移動体が経路生成装置により生成された経路を移動しているときに移動体が立ち往生してしまうことがある。

本発明は、このような従来の技術に存在する問題点に着目してなされたものであり、その目的は、移動体が円滑に移動できる経路を生成できる経路生成装置を提供することにある。

上記課題を解決する経路生成装置は、グリッドマップに基づき移動体の概略経路を生成し、前記概略経路に基づき前記移動体の詳細経路を生成する経路生成装置であって、前記経路生成装置は、前記グリッドマップに設定された前記移動体が移動できる最小の幅となるグリッド数である移動体グリッド数に応じて前記グリッドマップの解像度を下げた低解像度グリッドマップを生成する第１処理と、前記低解像度グリッドマップのグリッドのうち障害物が設定されているグリッドに障害物があることを示す情報である第１情報を設定する第２処理と、前記低解像度グリッドマップにおいて、前記第１情報が設定されていないグリッドと、当該第１情報が設定されていないグリッドを挟み込む前記第１情報が設定された少なくとも２つのグリッドとにより形成される領域のうち最も小さい範囲を前記低解像度グリッドマップの第１領域と設定するとともに、前記第１領域に対応する位置を前記グリッドマップの解像度で表現したものを前記グリッドマップの第２領域と設定し、前記グリッドマップの前記第２領域において、前記第１情報が設定された一方のグリッドに対応する位置に存在する障害物が設定されている第１障害物グリッドと、前記第１情報が設定された他方のグリッドに対応する位置に存在する障害物が設定されているグリッドであって前記第１領域の前記第１情報が設定されていないグリッドに対応する位置に存在するグリッドを挟み込んで前記第１障害物グリッドに対向する第２障害物グリッドと、の間のグリッド数を求め、当該求められたグリッド数が前記移動体グリッド数を下回ることがあった場合に、前記第１領域の前記第１情報が設定されていないグリッドに前記移動体が移動できないことを示す第２情報を設定し、前記低解像度グリッドマップにおいて前記第１情報及び前記第２情報が設定されていないグリッドにより形成されるとともに前記移動体が移動できる領域である移動領域と、前記第１情報が設定されたグリッド及び前記第２情報が設定されたグリッドにより形成されるとともに前記移動体が移動できない領域である非移動領域と、を区別する第３処理と、前記移動領域において、前記移動体が移動を開始する開始点と、前記移動体の移動の目標点との間で前記概略経路を生成する第４処理と、を実施する。

これによれば、低解像度グリッドマップのグリッドにおいて障害物が設定されているグリッドには、障害物があることを示す第１情報が設定され、低解像度グリッドマップにおいて移動体が移動できないグリッドには、第２情報を設定している。そのため、概略経路を生成するときに移動体が移動できない経路を表現することができる。そして、低解像度グリッドマップにおいて、第１情報及び第２情報が設定されていないグリッドにより移動体が移動できる移動領域が明確になる。すなわち、生成した概略経路上に移動体の移動を妨げる要因がなくなる。当該概略経路に基づき詳細経路を生成するため、移動体が円滑に移動できる経路を生成できる。

上記の経路生成装置において、前記移動体グリッド数が偶数である場合、前記低解像度グリッドマップのグリッドは、前記移動体グリッド数を「２」で除した数の前記グリッドマップにおけるグリッドを縦横に有しているとよい。

上記の経路生成装置において、前記移動体グリッド数が奇数である場合、前記低解像度グリッドマップのグリッドは、前記移動体グリッド数に「１」を加算した数を「２」で除した数の前記グリッドマップにおけるグリッドを縦横に有しているとよい。

これらによれば、第３処理において、低解像度グリッドマップの第１領域は、最も小さい範囲で２つの第１情報が設定されたグリッドと、１つの第１情報が設定されていないグリッドとにより形成される。そのため、グリッドマップにおいて第１領域の最も小さい範囲に対応する位置を第２領域とすれば、グリッドマップ上では複数の第２領域が形成される。経路生成装置は、複数の第２領域それぞれに対して第２領域に存在する障害物間のグリッド数が移動体グリッド数よりも下回るか否かを判断する。これは、経路生成装置がグリッドマップ全域において障害物間のグリッド数が移動体グリッド数を下回るか否かを一括で判断する場合と比較して、移動体が移動できるか否かを判断するために使用するグリッド数が少ないため、経路生成装置の処理容量が少なくなる。よって、経路生成装置の演算負荷をより低減させることができる。

この発明によれば、移動体が円滑に移動できる経路を生成できる。

自律走行車を示す概略図。 経路生成装置の処理フロー図。 経路生成装置で用いられるグリッドマップを示した概略図。 経路生成装置の第１処理を示した概略図。 経路生成装置の第２処理を示した概略図。 経路生成装置の第３処理を示した概略図。 経路生成装置の第３処理を示した概略図。 経路生成装置の第４処理を示した概略図。 経路生成装置の詳細経路生成処理を示した概略図。 経路生成装置の詳細経路生成処理を示した概略図。 経路生成装置の詳細経路生成処理を示した概略図。 経路生成装置の詳細経路生成処理を示した概略図。 経路生成装置の詳細経路生成処理を示した概略図。

以下、経路生成装置を具体化した一実施形態を図１～図１３にしたがって説明する。なお、本実施形態の経路生成装置は、荷を搬送する搬送台車等の自律走行車に適用されている。そのため、自律走行車についての説明の中で経路生成装置について説明する。

図１に示すように、自律走行車１は、経路生成装置１０と、移動体として車体２０とを備えている。経路生成装置１０は、車体２０に搭載された制御装置である。経路生成装置１０は、ＣＰＵ１１と、ＲＡＭ及びＲＯＭ等からなるメモリ１２とを有している。メモリ１２には、車体２０を制御するための種々のプログラムが記憶されている。経路生成装置１０は、メモリ１２に記憶されているプログラムをＣＰＵに実行させることにより車体２０を制御する。

経路生成装置１０は、地図情報と車体２０の位置とに基づき車体２０を移動させる機能を有している。地図情報は、メモリ１２に記憶されている。地図情報は、例えば約５００メートル四方で囲まれる広範囲における障害物の情報、車体２０が移動できる走行可能路の情報、及び車体２０が移動できない走行不能路の情報が含まれた情報である。経路生成装置１０は、車体２０の位置をＧＰＳにより検出してもよいが、距離センサ等の車体２０に搭載されるセンサを用いて車体２０の周囲の物体を検出して地図情報と比較して推定してもよい。経路生成装置１０は、検出された車体２０の位置を開始点Ｓとして、車体２０の移動の目標点Ｇに向かうための経路を生成し、当該経路に沿って車体２０を移動させる。

図２に示すように、経路生成装置１０は、車体２０が走行するための経路を生成するにあたり、第１処理Ｓ１０１、第２処理Ｓ１０２、第３処理Ｓ１０３、第４処理Ｓ１０４、及び第５処理Ｓ１０５を実施する。各処理Ｓ１０１，Ｓ１０２，Ｓ１０３，Ｓ１０４は、車体２０の概略経路Ｒｏを生成するまでの処理である概略経路生成処理である。第５処理Ｓ１０５は、概略経路Ｒｏに基づき車体２０の詳細経路Ｒｄを生成する処理である。

図３に示すように、経路生成装置１０は、概略経路生成処理と、詳細経路生成処理とを実施するにあたり、グリッドマップＭ１を使用する。グリッドマップＭ１とは、メモリ１２に記憶された地図情報を等間隔の縦横線で格子状に区切られたグリッドに分割して表現したマップである。なお、グリッドマップＭ１の外枠部分は、自律走行車１が適用される工場等の壁部を示している。そのため、本実施形態では、グリッドマップＭ１の外枠部分には、障害物があるものとして取り扱う。

各処理Ｓ１０１，Ｓ１０２，Ｓ１０３，Ｓ１０４について図３～図８にしたがって説明する。なお、図４，５，７，８には、後述する低解像度グリッドマップＭ２を示しているが、説明の便宜上、グリッドマップＭ１のグリッドも記載している。

図４に示すように、第１処理Ｓ１０１は、グリッドマップＭ１から低解像度グリッドマップＭ２を生成する処理である。
図３に示すように、経路生成装置１０は、低解像度グリッドマップＭ２を生成するにあたり、車体２０をグリッドマップＭ１に設定したときに車体２０の幅に対応するグリッド数を確認する。本実施形態では、例えば車体２０の幅に対応するグリッド数を「６」とする。経路生成装置１０は、障害物Ｏｂ間を車体２０が安全に移動できるときの車体２０と障害物Ｏｂとの隙間等を考慮して、グリッドマップＭ１に設定された車体２０が移動できる最小の幅となるグリッド数である移動体グリッド数Ｎを確認する。本実施形態における移動体グリッド数Ｎは、「８」である。移動体グリッド数Ｎは、グリッドマップＭ１に車体２０を設定したときの車体２０の幅に対応するグリッド数よりも大きく設定される。なお、障害物Ｏｂ間を車体２０が安全に移動できるときの車体２０と障害物Ｏｂとの間の隙間の大きさは、車体２０の種類や経路生成装置１０を採用する顧客によって適宜変更される。そのため、グリッドマップＭ１に車体２０を設定したときの車体２０の幅に対応するグリッド数から移動体グリッド数Ｎへの増加量は、適宜変更される。

図４に示すように、経路生成装置１０は、グリッドマップＭ１における移動体グリッド数Ｎに応じてグリッドマップＭ１の解像度を下げた低解像度グリッドマップＭ２を生成する。低解像度グリッドマップＭ２は、移動体グリッド数Ｎが「８」であるため、移動体グリッド数Ｎを「２」で除した数のグリッドマップＭ１におけるグリッドを縦横に有するグリッドを有している。図４では、黒色中太の線で区切られたグリッドが、低解像度グリッドマップＭ２のグリッドである。

ここで、概略経路生成処理において低解像度グリッドマップＭ２を使用する理由を説明する。
地図情報のサイズが大きいほどグリッドマップＭ１に地図情報を設定するために使用するメモリ１２の容量が多くなる。上記の地図情報は、５００メートル四方という広範囲の情報であるため、グリッドマップＭ１のまま車体２０の概略経路Ｒｏを生成してしまうと、使用するメモリ１２の容量が多いため、経路生成装置１０の演算負荷が増え、ひいては経路生成装置１０の演算速度も遅くなる。すなわち、低解像度グリッドマップＭ２を使用する理由は、車体２０の概略経路Ｒｏの生成に使用するメモリ１２の容量を少なくするためである。

移動体グリッド数Ｎを除する「２」を使用する理由も概略経路Ｒｏの生成に使用するメモリ１２の容量を少なくするためである。移動体グリッド数Ｎを除する数値は、グリッドマップＭ１の解像度を下げるために設定される数値である。グリッドマップＭ１から低解像度グリッドマップＭ２を生成するときに解像度をより下げるためには、除する数値を可能な限り小さくすることが好ましい。グリッド数は整数であることを考慮すれば、「２」という数値がグリッドマップＭ１の解像度を下げるための最大値である。よって、概略経路Ｒｏの生成に使用するメモリ１２の容量を最も効率的に少なくするために「２」という数値が採用されている。

なお、本実施形態では、移動体グリッド数Ｎが偶数であるため、低解像度グリッドマップＭ２のグリッドは、移動体グリッド数Ｎを「２」で除した数のグリッドマップＭ１のグリッドを縦横に有していたが、例えば車体２０の幅によっては、移動体グリッド数Ｎが奇数となる場合もある。移動体グリッド数Ｎが奇数である場合、「２」で除すると整数とならない。そして、グリッド数は一般的に整数であるため、移動体グリッド数Ｎが奇数である場合、低解像度グリッドマップＭ２のグリッドは、移動体グリッド数Ｎに「１」を加算した数を「２」で除した数のグリッドマップＭ１におけるグリッドを縦横に有するように変更する。

図５に示すように、第２処理Ｓ１０２は、低解像度グリッドマップＭ２のグリッドのうち障害物Ｏｂが設定されているグリッドに障害物Ｏｂがあることを示す情報である第１情報Ｉ１を設定する処理である。図５では、斜線が設けられている低解像度グリッドマップＭ２のグリッドに第１情報Ｉ１が設定されている。本実施形態では、第１情報Ｉ１には「１」という数値が採用されている。すなわち、低解像度グリッドマップＭ２の１つのグリッドに含まれるグリッドマップＭ１の複数のグリッドのうち少なくとも１つに障害物Ｏｂが設定されている場合、低解像度グリッドマップＭ２の当該１つのグリッドの全域に障害物Ｏｂがあるものとして取り扱う。なお、第１情報Ｉ１は、「１」という数値でなくてもよく、例えば「０」という数値でもよい。また、第１情報Ｉ１は、数値に限らず文字であってもよい。すなわち、第１情報Ｉ１とは、障害物Ｏｂがあることを示す情報として低解像度グリッドマップＭ２のグリッドに設定されるのであれば、設定内容は適宜変更してもよい。

次に、第３処理Ｓ１０３について図５～図７にしたがって説明する。第３処理Ｓ１０３は、車体２０が移動できる領域である移動領域Ｍａと、車体２０が移動できない領域である非移動領域Ｍｕｎとを区別する処理である。

図５に示すように、低解像度グリッドマップＭ２は、第１情報Ｉ１が設定されていないグリッド、及び当該第１情報Ｉ１が設定されていないグリッドを挟み込む第１情報Ｉ１が設定されたグリッドにより形成される第１領域Ｒ１を複数有している。本実施形態では、第１領域Ｒ１は、低解像度グリッドマップＭ２において、第１情報Ｉ１が設定されていない１つのグリッドと、第１情報Ｉ１が設定された２つのグリッドとにより構成されている。すなわち、第１情報Ｉ１が設定されていないグリッド、及び当該第１情報Ｉ１が設定されていないグリッドを挟み込む第１情報Ｉ１が設定されたグリッドにより形成される領域のうち最も小さな範囲を第１領域Ｒ１としている。第３処理Ｓ１０３では、第１領域Ｒ１において車体２０が移動できるだけのグリッド数があるか否かを判断する。具体的には、図６を用いて説明する。

図６には、複数の第１領域Ｒ１のうちの１つを例示している。第３処理Ｓ１０３では、低解像度グリッドマップＭ２の第１領域Ｒ１と、第１領域Ｒ１に対応する位置を示すグリッドマップＭ１の第２領域Ｒ２とを比較する。具体的には、低解像度グリッドマップＭ２の第１領域Ｒ１に対応する位置だけをグリッドマップＭ１の解像度で表現し、障害物Ｏｂの配置を詳細に確認する。第３処理Ｓ１０３では、グリッドマップＭ１の第２領域Ｒ２に存在する障害物Ｏｂ間のグリッド数が移動体グリッド数Ｎを下回るか否かを判断する。例えば、図６では、障害物Ｏｂ間のグリッド数は、「６」である。そのため、図６に示す第１領域Ｒ１では、車体２０は移動できないように障害物Ｏｂが配置されていることが確認できる。

図７に示すように、第３処理Ｓ１０３では、グリッドマップＭ１の第２領域Ｒ２に存在する障害物Ｏｂ間のグリッド数が移動体グリッド数Ｎを下回る場合、第１領域Ｒ１の第１情報Ｉ１が設定されていないグリッドに車体２０が移動できないことを示す第２情報Ｉ２を設定する。図５と比較して斜線が追加されている低解像度グリッドマップＭ２のグリッドに第２情報Ｉ２が設定されている。本実施形態では、第２情報Ｉ２には「０」という数値が採用されている。第３処理Ｓ１０３では、低解像度グリッドマップＭ２の複数の第１領域Ｒ１それぞれに対して上記処理を実施する。これにより、第３処理Ｓ１０３では、低解像度グリッドマップＭ２において第１情報Ｉ１及び第２情報Ｉ２が設定されていないグリッドにより形成される移動領域Ｍａと、第１情報Ｉ１又は第２情報Ｉ２が設定されたグリッドにより形成される非移動領域Ｍｕｎとが区別される。なお、第２情報Ｉ２は、「０」という数値でなくてもよく、例えば「１」という数値でもよい。この場合、第１情報Ｉ１として「０」を採用するとよい。また、第２情報Ｉ２は、数値に限らず文字であってもよい。すなわち、第２情報Ｉ２とは、車体２０が移動できないことを示す情報として低解像度グリッドマップＭ２のグリッドに設定されるのであれば、設定内容は適宜変更してもよい。

図８に示すように、第４処理Ｓ１０４では、低解像度グリッドマップＭ２の移動領域Ｍａにおいて、車体２０が移動を開始する開始点Ｓと、車体２０の移動の目標点である目標点Ｇとの間で概略経路Ｒｏを生成する。経路生成装置１０は、多様な経路生成方法を採用することができるが、本実施形態では例えばＡ－Ｓｔａｒ探索アルゴリズムやダイクストラアルゴリズムを利用して開始点Ｓから目標点Ｇまでの最短の概略経路Ｒｏを生成している。なお、生成される概略経路Ｒｏは、開始点Ｓから目標点Ｇまでの最短経路である必要はなく、自律走行車１が経由すべき経由点があれば、移動領域Ｍａにおいて開始点Ｓから当該経由点を経由して目標点Ｇに至る概略経路Ｒｏを生成してもよい。また、開始点Ｓから目標点Ｇまでの概略経路Ｒｏを生成するときに使用するアルゴリズムは、適宜変更してもよい。

次に、第５処理Ｓ１０５について図９～図１３にしたがって説明する。
図９に示すように、第５処理Ｓ１０５では、低解像度グリッドマップＭ２において、概略経路生成処理において生成された概略経路Ｒｏの周辺部分を含む第１分割領域Ｓｄ１、第２分割領域Ｓｄ２、及び第３分割領域Ｓｄ３に分割する。上記の周辺部分とは、概略経路Ｒｏに周辺に存在する障害物Ｏｂの一部を含む部分を示している。第１分割領域Ｓｄ１は、概略経路Ｒｏにおける開始点Ｓを含んでいる。第３分割領域Ｓｄ３は、概略経路Ｒｏにおける目標点Ｇを含んでいる。第２分割領域Ｓｄ２は、第１分割領域Ｓｄ１と第３分割領域Ｓｄ３との間の領域である。第２分割領域Ｓｄ２は、第１分割領域Ｓｄ１及び第３分割領域Ｓｄ３と一部オーバーラップするように配置されている。

図１０に示すように、第５処理Ｓ１０５では、低解像度グリッドマップＭ２の第１分割領域Ｓｄ１に対応するグリッドマップＭ１の領域を確認し、車体２０が移動するための第１詳細経路Ｒｄ１を生成する。

図１１に示すように、第５処理Ｓ１０５では、低解像度グリッドマップＭ２の第２分割領域Ｓｄ２に対応するグリッドマップＭ１の領域を確認し、車体２０が移動するための第２詳細経路Ｒｄ２を生成する。このとき、第２分割領域Ｓｄ２には、第１分割領域Ｓｄ１における第１詳細経路Ｒｄ１の終点が含まれている。第５処理Ｓ１０５では、第１詳細経路Ｒｄ１の終点を第２詳細経路Ｒｄ２の始点として第２詳細経路Ｒｄ２を生成する。

図１２に示すように、第５処理Ｓ１０５では、低解像度グリッドマップＭ２の第３分割領域Ｓｄ３に対応するグリッドマップＭ１の領域を確認し、車体２０が移動するための第３詳細経路Ｒｄ３を生成する。第３分割領域Ｓｄ３には、第２分割領域Ｓｄ２における第２詳細経路Ｒｄ２の終点が含まれている。第５処理Ｓ１０５では、第２詳細経路Ｒｄ２の終点を第３詳細経路Ｒｄ３の始点として第３詳細経路Ｒｄ３を生成する。すなわち、図９に示すように、第２分割領域Ｓｄ２が第１分割領域Ｓｄ１及び第３分割領域Ｓｄ３と一部オーバーラップしているのは、各経路Ｒｄ１，Ｒｄ２，Ｒｄ３を連続的に構成するためである。

図１３に示すように、第５処理Ｓ１０５では、各分割領域Ｓｄ１，Ｓｄ２，Ｓｄ３で生成された各経路Ｒｄ１，Ｒｄ２，Ｒｄ３をグリッドマップＭ１上において連続させることにより詳細経路Ｒｄを生成する。すなわち、経路生成装置１０は、グリッドマップＭ１に基づき車体２０の概略経路Ｒｏを生成し、概略経路Ｒｏに基づき車体２０の詳細経路Ｒｄを生成している。なお、本実施形態では、低解像度グリッドマップＭ２を各分割領域Ｓｄ１，Ｓｄ２，Ｓｄ３に分割していたが、これに限らない。例えば、２分割でもよいし、４分割以上であってもよい。低解像度グリッドマップＭ２を分割する数が少ないほど、表現するグリッドマップＭ１のグリッド数が増大するため、各経路Ｒｄ１，Ｒｄ２，Ｒｄ３の生成に使用するメモリ１２の容量が多くなる。そのため、経路生成装置１０の各経路Ｒｄ１，Ｒｄ２，Ｒｄ３の生成に使用するメモリ１２の容量が多くなり、経路生成装置１０の演算速度が遅くなってしまう。よって、低解像度グリッドマップＭ２を分割する数は、経路生成装置１０のメモリ１２の容量によって適宜変更する。

本実施形態の作用を説明する。
低解像度グリッドマップＭ２のグリッドにおいて障害物Ｏｂが設定されているグリッドには、第１情報Ｉ１が設定され、低解像度グリッドマップＭ２において車体２０が移動できないグリッドには、第２情報Ｉ２を設定している。そのため、概略経路Ｒｏを生成するときに車体２０が移動できない経路が表現される。そして、低解像度グリッドマップＭ２において、第１情報Ｉ１及び第２情報Ｉ２が設定されていないグリッドにより車体２０が移動できる移動領域Ｍａが明確になる。すなわち、生成した概略経路Ｒｏ上に車体２０の移動を妨げる要因がなくなる。

本実施形態の効果を説明する。
（１）生成した概略経路Ｒｏ上に車体２０の移動を妨げる要因がなくなり、概略経路Ｒｏに基づき詳細経路Ｒｄを生成するため、車体２０が円滑に移動できる経路を生成できる。

（２）第３処理Ｓ１０３において、低解像度グリッドマップＭ２の第１領域Ｒ１は、２つの第１情報が設定されたグリッドと、１つの第１情報が設定されていないグリッドとにより形成される。そのため、グリッドマップＭ１において第１領域Ｒ１に対応する位置を第２領域Ｒ２とすれば、グリッドマップＭ１上では複数の第２領域Ｒ２が形成される。経路生成装置１０は、複数の第２領域Ｒ２それぞれに対して第２領域Ｒ２に存在する障害物Ｏｂ間のグリッド数が移動体グリッド数Ｎよりも下回るか否かを判断する。これは、経路生成装置１０がグリッドマップＭ１全域において障害物Ｏｂ間のグリッド数が移動体グリッド数Ｎを下回るか否かを一括で判断する場合と比較して、車体２０が移動できるか否かを判断するために使用するグリッド数が少ないため、経路生成装置１０の処理容量が少なくなる。よって、経路生成装置１０の演算負荷をより低減させることができる。

なお、本実施形態は、以下のように変更して実施することができる。本実施形態及び以下の変更例は、技術的に矛盾しない範囲で互いに組み合わせて実施することができる。
○ 低解像度グリッドマップＭ２において、第１領域Ｒ１は、２つの第１情報Ｉ１が設定されたグリッドと、複数の第１情報Ｉ１が設定されていないグリッドとにより構成されていてもよい。

○ グリッドマップＭ１の外枠部分は、本実施形態では工場等の壁部を示しているため、障害物Ｏｂがあるとして取り扱っていたが、これに限らない。グリッドマップＭ１に基づき車体２０が移動する経路を生成するにあたって、グリッドマップＭ１上に開始点Ｓ及び目標点Ｇがある。そのため、そもそも車体２０がグリッドマップＭ１外に離脱する経路を生成しないことから、グリッドマップＭ１の外枠部分は車体２０が移動できない領域として設定されることも考えられる。すなわち、低解像度グリッドマップＭ２の外枠部分には、車体２０が移動できないことを示す第２情報Ｉ２が設定されてもよい。このように変更するとき、低解像度グリッドマップＭ２において、第１情報Ｉ１が設定されていない１つのグリッドと、当該第１情報Ｉ１が設定されていないグリッドを挟み込む第１情報Ｉ１が設定されたグリッド及び第２情報Ｉ２が設定されたグリッドとにより形成される第３領域が形成される。経路生成装置１０は、第３領域に対応する位置のグリッドマップＭ１のグリッド数が移動体グリッド数Ｎを下回るか否かを判定し、移動体グリッド数Ｎを下回る場合、第３領域における第１情報Ｉ１が設定されていないグリッドに第２情報Ｉ２を設定する。よって、低解像度グリッドマップＭ２において移動領域Ｍａと、非移動領域Ｍｕｎとを区別することができる。

○ 自律走行車１は、搬送台車であったが、これに限らない。例えば、掃除ロボットのような移動ロボットであってもよい。
○ また、経路生成装置１０は、自律走行車１に適用されていたが、例えば自動車やフォークリフト等の車両に適用してもよい。また、経路生成装置１０が移動体としての車体２０が移動する経路を生成したが、例えばコンピュータで生成された空間でのアバターを移動体として、コンピュータで生成された空間でのアバターが移動する経路を生成してもよい。

１０…経路生成装置、２０…車体、Ｒｏ…概略経路、Ｒｄ…詳細経路、Ｍ１…グリッドマップ、Ｍ２…低解像度グリッドマップ、Ｓ１０１…第１処理、Ｓ１０２…第２処理、Ｓ１０３…第３処理、Ｓ１０４…第４処理、Ｉ１…第１情報、Ｉ２…第２情報、Ｒ１…第１領域、Ｒ２…第２領域、Ｍａ…移動領域、Ｍｕｎ…非移動領域、Ｓ…開始点、Ｇ…目標点、Ｏｂ…障害物、Ｎ…移動体グリッド数。

Claims (3)

1. グリッドマップに基づき移動体の概略経路を生成し、前記概略経路に基づき前記移動体の詳細経路を生成する経路生成装置であって、
   前記経路生成装置は、
   前記グリッドマップに設定された前記移動体が通過できる最小の幅となるグリッド数である移動体グリッド数に応じて前記グリッドマップの解像度を下げた低解像度グリッドマップを生成する第１処理と、
   前記低解像度グリッドマップのグリッドのうち障害物が設定されているグリッドに障害物があることを示す情報である第１情報を設定する第２処理と、
   前記第１情報が設定されていないグリッドと、当該第１情報が設定されていないグリッドを挟み込む前記第１情報が設定された少なくとも２つのグリッドとにより形成される領域のうち最も小さい範囲を前記低解像度グリッドマップの第１領域と設定するとともに、前記第１領域に対応する位置を前記グリッドマップの解像度で表現したものを前記グリッドマップの第２領域と設定し、前記グリッドマップの前記第２領域において、前記第１情報が設定された一方のグリッドに対応する位置に存在する障害物が設定されている第１障害物グリッドと、前記第１情報が設定された他方のグリッドに対応する位置に存在する障害物が設定されているグリッドであって前記第１領域の前記第１情報が設定されていないグリッドに対応する位置に存在するグリッドを挟み込んで前記第１障害物グリッドに対向する第２障害物グリッドと、の間のグリッド数を求め、当該求められたグリッド数が前記移動体グリッド数を下回ることがあった場合に、前記第１領域の前記第１情報が設定されていないグリッドに前記移動体が移動できないことを示す第２情報を設定し、前記低解像度グリッドマップにおいて前記第１情報及び前記第２情報が設定されていないグリッドにより形成されるとともに前記移動体が移動できる領域である移動領域と、前記第１情報が設定されたグリッド及び前記第２情報が設定されたグリッドにより形成されるとともに前記移動体が移動できない領域である非移動領域と、を区別する第３処理と、
   前記移動領域において、前記移動体が移動を開始する開始点と、前記移動体の移動の目標点との間で前記概略経路を生成する第４処理と、を実施することを特徴とする経路生成装置。
2. 前記移動体グリッド数が偶数である場合、前記低解像度グリッドマップのグリッドは、前記移動体グリッド数を「２」で除した数の前記グリッドマップにおけるグリッドを縦横に有していることを特徴とする請求項１に記載の経路生成装置。
3. 前記移動体グリッド数が奇数である場合、前記低解像度グリッドマップのグリッドは、前記移動体グリッド数に「１」を加算した数を「２」で除した数の前記グリッドマップにおけるグリッドを縦横に有していることを特徴とする請求項１又は請求項２に記載の経路生成装置。