(57)【要約】  経路探索支援装置１０は、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための装置である。経路探索支援装置１０は、特定のエリアの地図情報、及びエリア内で移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、情報取得部１１と、地図情報及びタスク地点情報に基づいて、特定のエリアにおいて、タスク地点間の経路上に存在しないように、移動体の待避が可能となる待避地点を設定する、待避地点設定部１２と、を備えている。
2020110273.tif 000002
【特許請求の範囲】
【請求項１】
特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための装置であって、
前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、情報取得部と、
前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、待避地点設定部と、
を備えている、ことを特徴とする経路探索支援装置。
【請求項２】
請求項１に記載の経路探索支援装置であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記待避地点設定部が、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とする経路探索支援装置。
【請求項３】
請求項２に記載の経路探索支援装置であって、
前記待避地点設定部が、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援装置。
【請求項４】
請求項２に記載の経路探索支援装置であって、
前記待避地点設定部が、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援装置。
【請求項５】
特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための方法であって、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を有する、ことを特徴とする経路探索支援方法。
【請求項６】
請求項５に記載の経路探索支援方法であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記（ｂ）のステップにおいて、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とする経路探索支援方法。
【請求項７】
請求項６に記載の経路探索支援方法であって、
前記（ｂ）のステップにおいて、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援方法。
【請求項８】
請求項６に記載の経路探索支援方法であって、
前記（ｂ）のステップにおいて、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援方法。
【請求項９】
コンピュータによって、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するためのプログラムであって、
前記コンピュータに、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を実行させる命令を含む、プログラムを記録している、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１０】
請求項９に記載のコンピュータ読み取り可能な記録媒体であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記（ｂ）のステップにおいて、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１１】
請求項１０に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１２】
請求項１０に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自立して移動する移動体の経路探索を支援するための、経路探索支援装置、及び経路探索支援方法に関し、更には、これらを実現するためのプログラムを記録したコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来から、無人搬送車（ＡＧＶ：Automated guided Vehicle）は、作業効率及び生産効率を高めるため、種々の工場において導入されている。また、無人搬送車は、物流拠点においても、迅速な配送を実現するために導入されている。【０００３】
ところで、一般に、工場、物流拠点等において、運用される無人搬送車の数は、一台ではなく、複数台である。従って、複数台の無人搬送車を運用するにあたっては、衝突ができるだけ起こらないようにするために、荷物を積載していない無人搬送車（以下「空き走行車」と表記する）を待避地点に待機させることが行われている（例えば、特許文献１参照）。【０００４】
具体的には、特許文献１は、複数の無人搬送車の運行システムを開示している。特許文献１に開示された運行システムは、まず、空き走行車の検出を実行し、空き走行車を検出できた場合は、検出できた数と同数の待避地点を設定する。【０００５】
次に、特許文献１に開示された運行システムは、設定した待避地点から、検出された空き走行車までの経路を探索する。そして、運行システムは、探索した経路中に別の空き走行車が存在していない場合は、経路が探索された空き走行車に、探索した経路に沿って移動するように指示を与える。一方、運行システムは、探索した経路中に別の空き走行車が存在しる場合は、この空き走行車に、探索した経路に沿って移動するように指示を与える。【０００６】
このように、特許文献１に開示された運行システムによれば、空き走行車は全て待機地点で待避することになる。この結果、無人運転車同士の衝突の発生が抑制されることになる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１６−８１３７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ところで、特許文献１に開示されたシステムでは、待避地点の設定は、人手によって予め設定された待避地点候補の中から、一定のルールに沿って、空き走行車の数の待避地点を選択することによって行われている。このため、運行システムの管理者は、工場等のレイアウトが変わると、その度に、待避地点候補を改めて設定する必要がある。そして、レイアウトの変更は頻繁に行われることもあり、管理者にとって、待避地点候補の設定は負担となることもある。【０００９】
本発明の目的の一例は、上記問題を解消し、人手に頼ることなく、自立して移動する移動体の経路探索で必要な待避地点の設定を可能にし得る、経路探索支援装置、経路探索支援方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明の一側面における経路探索支援装置は、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための装置であって、
前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、情報取得部と、
前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、待避地点設定部と、
を備えている、ことを特徴とする。【００１１】
また、上記目的を達成するため、本発明の一側面における経路探索支援方法は、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための方法であって、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を有する、ことを特徴とする。【００１２】
更に、上記目的を達成するため、本発明の一側面におけるコンピュータ読み取り可能な記録媒体は、コンピュータによって、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するためのプログラムであって、
前記コンピュータに、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を実行させる命令を含む、プログラムを記録している、
ことを特徴とする。
【発明の効果】
【００１３】
以上のように、本発明によれば、人手に頼ることなく、自立して移動する移動体の経路探索で必要な待避地点の設定が可能となる。
【図面の簡単な説明】
【００１４】
【図１】図１は、本発明の実施の形態１における経路探索支援装置の概略構成を示すブロック図である。
【図２】図２は、本発明の実施の形態１における経路探索支援装置の具体的構成を示すブロック図である。
【図３】図３は、本発明の実施の形態１において移動体が移動するエリアの地図情報の一例を模式的に示す図である。
【図４】図４（ａ）〜（ｅ）は、本発明の実施の形態１における待避地点の設定処理を説明する図である。
【図５】図５は、本発明の実施の形態１における経路探索支援装置の動作を示すフロー図である。
【図６】図６（ａ）〜（ｃ）は、本発明の実施の形態２における待避地点の設定処理を説明する図である。
【図７】図７は、本発明の実施の形態２における経路探索支援装置の動作を示すフロー図である。
【図８】図８は、本発明の実施の形態１及び２における経路探索支援装置を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００１５】
（実施の形態１）
以下、本発明の実施の形態１における、経路探索支援装置、経路探索支援方法、及びプログラムについて、図１〜図５を参照しながら説明する。
【００１６】
［装置構成］
最初に、本実施の形態１における経路探索支援装置の概略構成について説明する。図１は、本発明の実施の形態１における経路探索支援装置の概略構成を示すブロック図である。
【００１７】
図１に示す、本実施の形態１における経路探索支援装置１０は、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための装置である。移動体としては、例えば、無人搬送車、ロボット等が挙げられる。また、特定のエリアとしては、例えば、工場、倉庫等が挙げられる。
【００１８】
また、図１に示すように、経路探索支援装置１０は、情報取得部１１と、待避地点設定部１２とを備えている。情報取得部１１は、特定のエリアの地図情報、及びタスク地点情報を取得する。タスク地点情報は、特定のエリア内で移動体がタスクを実行するタスク地点を特定する情報である。待避地点設定部１２は、地図情報及びタスク地点情報に基づいて、特定のエリアにおいて、タスク地点間の経路上に存在しないように、移動体の待避が可能となる待避地点を設定する。
【００１９】
このように、本実施の形態１では、特定のエリアの地図情報とタスク地点情報とから、自動的に、移動体の待避地点が設定される。つまり、本実施の形態１によれば、人手に頼ることなく、自立して移動する移動体の経路探索で必要な待避地点の設定が可能となる。
【００２０】
ここで、図２〜図４を用いて、本実施の形態１における経路探索支援装置１０の構成及び機能をより具体的に説明する。図２は、本発明の実施の形態１における経路探索支援装置の具体的構成を示すブロック図である。図３は、本発明の実施の形態１において移動体が移動するエリアの地図情報の一例を模式的に示す図である。
【００２１】
図２に示すように、経路探索支援装置１０は、移動体２１を管理する移動体管理装置２０に、データ通信可能に接続されている。図２の例では、移動体２１は、無人搬送車である。移動体管理装置２０と各移動体２１とは、無線通信によってデータ通信可能に接続されている。なお、本実施の形態１では、経路探索支援装置１０は、移動体管理装置２０に搭載されていても良い。
【００２２】
経路探索支援装置１０は、待避地点を設定すると、設定した待避地点を移動体管理装置２０に通知する。移動体管理装置２０は、待避地点の通知を受けると、各移動体２１に、経路と待避地点とを通知する。
【００２３】
また、図２に示すように、経路探索支援装置１０は、本実施の形態１では、上述した情報取得部１１及び待避地点設定部１２に加えて、情報記憶部１３を備えている。情報記憶部１３は、地図情報１４と、タスク地点情報１５とを格納している。
【００２４】
本実施の形態１では、図３に示すように、移動体２１が移動するエリア３０は、格子状に分割され、複数のグリッド３１で構成されている。地図情報は、このグリッド３１毎の情報で構成されている。図３の例では、塗りつぶされているグリッドには、装置、棚等が配置されている。タスク地点、経路及び待避地点は、塗りつぶされていないグリッド３１に設定される。
【００２５】
タスク地点情報は、本実施の形態１では、実際のタスク地点に対応するグリッドの位置（座標、通し番号等）を特定する情報である。待避地点設定部１２は、本実施の形態１では、待避地点となるグリッドを選択することによって、待避地点を設定する。
【００２６】
また、待避地点設定部１２は、本実施の形態１では、最小シュタイナー木アルゴリズムを利用して、待避地点を設定する。つまり、待避地点設定部１２は、全てのタスク地点を結び、且つ、含まれるグリッドの数が最小となる、経路を設定し、設定した経路上のグリッド以外のグリッドの中から、待避地点となるグリッドを選択する。なお、本実施の形態１におけるシュタイナー木アルゴリズムは一例であり、近似アルゴリズムである。また、本実施の形態１では、他のシュタイナー木アルゴリズムが用いられても良い。
【００２７】
図４を用いて、本実施の形態１での待避地点設定部１２による待避地点の設定処理について具体的に説明する。図４（ａ）〜（ｅ）は、本発明の実施の形態１における待避地点の設定処理を説明する図である。
【００２８】
まず、図４（ａ）に示すエリア３０が存在し、そこに３つのタスク地点Ａ〜Ｂが設定されているとする。また、図４（ａ）において、各グリッド３１をノードとすると、図４（ａ）に示すエリアは、図４（ｂ）のように表すことができる。また、図４（ｂ）において示される数値は、グリッド間の移動にかかるコストを示している。更に、図４（ｂ）において、タスク地点以外のグリッドのノードは、●で示されている。
【００２９】
そして、待避地点設定部１２が、移動体２１が、全てのタスク地点を結ぶ経路を探索するとする。この場合、待避地点設定部１２は、Ｂ→Ａ→Ｃという経路と、Ｂ→Ｃ→Ａという経路とを探索する。
【００３０】
続いて、待避地点設定部１２は、含まれるグリッドの数が最小となる経路を特定するが、本実施の形態１では、「含まれるグリッドの数」を経路長で近似して経路を特定する。よって、前者の経路長は７（＝３＋４）、後者の経路長は９（＝５＋４）となるので、待避地点設定部１２は、含まれるグリッドの数が最小となる経路として、経路Ｂ→Ａ→Ｃを特定する。この結果、Ｂ→Ｃの経路は採用されないので、待避地点設定部１２は、図４（ｃ）において枠線で示す位置のグリッド３１を待避地点として選択する。その後、待避地点設定部１２は、選択したグリッド３１（待避地点）を、移動体管理装置２０に通知する。
【００３１】
［装置動作］
次に、本発明の実施の形態１における経路探索支援装置１０の動作について図５を用いて説明する。図５は、本発明の実施の形態１における経路探索支援装置の動作を示すフロー図である。以下の説明においては、適宜図１〜図４を参酌する。また、本実施の形態１では、経路探索支援装置１０を動作させることによって、経路探索支援方法が実施される。よって、本実施の形態１における経路探索支援方法の説明は、以下の経路探索支援装置１０の動作説明に代える。
【００３２】
最初に、図５に示すように、情報取得部１１が、情報記憶部１３から、特定のエリアの地図情報、及びタスク地点情報を取得する（ステップＡ１）。
【００３３】
次に、待避地点設定部１２は、地図情報及びタスク地点情報に基づいて、全てのタスク地点を結ぶ経路を探索する（ステップＡ２）。そして、待避地点設定部１２は、探索した経路の中から、含まれるグリッドの数が最小となる経路、例えば経路長が最小となる経路を特定する（ステップＡ３）。
【００３４】
次に、待避地点設定部１２は、ステップＡ３で特定された経路上にないグリッドを、待避地点として選択する（ステップＡ４）。その後、待避地点設定部１２は、待避地点として選択したグリッドを、移動体管理装置２０に通知する（ステップＡ５）。
【００３５】
このように、ステップＡ１〜Ａ５が実行されると、特定のエリア３０において、タスク地点間の経路上に存在しないように、移動体の待避が可能となる待避地点が設定されることになる。本実施の形態１によれば、人手に頼ることなく、自立して移動する移動体２１の経路探索で必要な待避地点の設定が可能となる。
【００３６】
［プログラム］
本実施の形態１におけるプログラムは、コンピュータに、図５に示すステップＡ１〜Ａ５を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態１における経路探索支援装置１０と経路探索支援方法とを実現することができる。この場合、コンピュータのプロセッサは、情報取得部１１及び待避地点設定部１２として機能し、処理を行なう。また、本実施の形態１では、情報記憶部１３は、上記プログラムを実行するコンピュータ、又は外部の別のコンピュータに備えられたハードディスク等の記憶装置に、これらを構成するデータファイルを格納することによって実現可能である。
【００３７】
また、本実施の形態１におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、情報取得部１１又は待避地点設定部１２として機能する。
【００３８】
（実施の形態２）
続いて、本発明の実施の形態２における、経路探索支援装置、経路探索支援方法、及びプログラムについて、図６及び図７を参照しながら説明する。
【００３９】
本実施の形態２における経路探索支援装置は、図１及び図２に示した実施の形態１における経路探索支援装置１０と同様の構成を備えている。但し、本実施の形態２においては、待避地点設定部の機能が、実施の形態１と異なっている。以下、実施の形態１との相違点を中心に説明する。また、以下の説明では、適宜、図１〜図４を参照する。
【００４０】
本実施の形態２では、待避地点設定部１２は、最小連結支配集合を利用して、待避地点となるグリッドを選択する。つまり、待避地点設定部１２は、エリア３０を構成する複数のグリッド３１において、２つ以上のタスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した集合以外のグリッドの中から、待避地点となるグリッドを選択する。
【００４１】
図６を用いて、本実施の形態２での待避地点設定部１２による待避地点の設定処理について具体的に説明する。図６（ａ）〜（ｃ）は、本発明の実施の形態２における待避地点の設定処理を説明する図である。
【００４２】
まず、図６（ａ）に示すエリア３０が存在し、そこに２つのタスク地点Ａ及びＢが設定されているとする。また、図６（ａ）において、各グリッド３１をノードとすると、図６（ａ）に示すエリアは、図６（ｂ）のように表すことができる。また、図６（ｂ）において、タスク地点以外のグリッドのノードは、○で示されている。
【００４３】
そして、図６（ｂ）に示すように、待避地点設定部１２は、複数のグリッド３１の中から、２つ以上のタスク地点（図６の例ではタスク地点Ａ及びＢ）を含むグリッド集合を特定する。図６（ｂ）において枠線は、特定されたグリッド集合を示している。また、グリッド集合では、各グリッドは連結している。ここで、「連結している」とは、集合内の任意のグリッド間において、集合に含まれるグリッドのみを通って移動体２１が行き来できることをいう。
【００４４】
そして、図６（ｃ）に示すように、待避地点設定部１２は、特定したグリッド集合以外のグリッドを待避地点とする。図６（ｃ）において、△は待避地点である。特に、待避地点△は、他の待避地点によって経路を遮られることのない待避地点である。
【００４５】
ところで、グリッド集合は、全てのタスク地点を含み、且つ、各グリッドが連結していれば、特に限定されるものではない。よって、図６（ｂ）の例では、破線で示す枠線で囲まれるように、グリッド集合を特定することも可能である。この場合は、図６（ｄ）に示すように、待避地点が選択される。図６（ｄ）においては、△と▲が待避地点であり、特に、▲は、他の待避地点に経路を遮られる可能性のある待避地点である。
【００４６】
また、図６（ｄ）に示すように、破線で示す枠線でグリッド集合を特定した場合は、実線で示す枠線でグリッド集合を特定した場合に比べて、他の待避地点に経路を遮られることのない待避地点△の数が少なくなる。このため、図６（ｂ）の例では、実線で示す枠線のように、グリッド集合が特定されている。
【００４７】
［装置動作］
次に、本発明の実施の形態２における経路探索支援装置の動作について図７を用いて説明する。図７は、本発明の実施の形態２における経路探索支援装置の動作を示すフロー図である。以下の説明においては、適宜図１〜図４を参酌する。また、本実施の形態２においても、経路探索支援装置を動作させることによって、経路探索支援方法が実施される。よって、本実施の形態２における経路探索支援方法の説明も、以下の経路探索支援装置の動作説明に代える。
【００４８】
最初に、図５に示すように、情報取得部１１が、情報記憶部１３から、特定のエリアの地図情報、及びタスク地点情報を取得する（ステップＢ１）。
【００４９】
次に、待避地点設定部１２は、複数のグリッド３１の中から、２つ以上のタスク地点を含み、且つ、連結している、グリッドの集合（グリッド集合）を特定する。（ステップＢ２）。
【００５０】
次に、待避地点設定部１２は、特定したグリッド集合以外のグリッドを待避地点とする。（ステップＢ３）。その後、待避地点設定部１２は、待避地点としたグリッドを、移動体管理装置２０に通知する（ステップＢ４）。
【００５１】
このように、ステップＢ１〜Ｂ４が実行された場合も、特定のエリア３０において、待避地点が設定される。本実施の形態２による場合も、人手に頼ることなく、自立して移動する移動体２１の経路探索で必要な待避地点の設定が可能となる。
【００５２】
［プログラム］
本実施の形態２におけるプログラムは、コンピュータに、図７に示すステップＢ１〜Ｂ４を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態２における経路探索支援装置と経路探索支援方法とを実現することができる。この場合、コンピュータのプロセッサは、情報取得部１１及び待避地点設定部１２として機能し、処理を行なう。また、本実施の形態２では、情報記憶部１３は、上記プログラムを実行するコンピュータ、又は外部の別のコンピュータに備えられたハードディスク等の記憶装置に、これらを構成するデータファイルを格納することによって実現可能である。
【００５３】
また、本実施の形態２におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、情報取得部１１又は待避地点設定部１２として機能する。
【００５４】
（物理構成）
ここで、実施の形態１及び２におけるプログラムを実行することによって、経路探索支援装置を実現するコンピュータについて図８を用いて説明する。図８は、本発明の実施の形態１及び２における経路探索支援装置を実現するコンピュータの一例を示すブロック図である。
【００５５】
図８に示すように、コンピュータ１１０は、ＣＰＵ（Central Processing Unit）１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。なお、コンピュータ１１０は、ＣＰＵ１１１に加えて、又はＣＰＵ１１１に代えて、ＧＰＵ（Graphics Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）を備えていても良い。
【００５６】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【００５７】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００５８】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００５９】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体が挙げられる。
【００６０】
なお、本実施の形態における経路探索支援装置は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、経路探索支援装置は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【００６１】
上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記１２）によって表現することができるが、以下の記載に限定されるものではない。
【００６２】
（付記１）
特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための装置であって、
前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、情報取得部と、
前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、待避地点設定部と、
を備えている、ことを特徴とする経路探索支援装置。
【００６３】
（付記２）
付記１に記載の経路探索支援装置であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記待避地点設定部が、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とする経路探索支援装置。
【００６４】
（付記３）
付記２に記載の経路探索支援装置であって、
前記待避地点設定部が、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援装置。
【００６５】
（付記４）
付記２に記載の経路探索支援装置であって、
前記待避地点設定部が、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援装置。
【００６６】
（付記５）
特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための方法であって、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を有する、ことを特徴とする経路探索支援方法。
【００６７】
（付記６）
付記５に記載の経路探索支援方法であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記（ｂ）のステップにおいて、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とする経路探索支援方法。
【００６８】
（付記７）
付記６に記載の経路探索支援方法であって、
前記（ｂ）のステップにおいて、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援方法。
【００６９】
（付記８）
付記６に記載の経路探索支援方法であって、
前記（ｂ）のステップにおいて、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援方法。
【００７０】
（付記９）
コンピュータによって、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するためのプログラムであって、
前記コンピュータに、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を実行させる命令を含む、プログラムを記録している、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【００７１】
（付記１０）
付記９に記載のコンピュータ読み取り可能な記録媒体であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記（ｂ）のステップにおいて、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【００７２】
（付記１１）
付記１０に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【００７３】
（付記１２）
付記１０に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【００７４】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【００７５】
以上のように、本発明によれば、人手に頼ることなく、自立して移動する移動体の経路探索で必要な待避地点の設定が可能となる。本発明は、例えば、無人搬送車の管理システムにおいて有用である。
【符号の説明】
【００７６】
１０  経路探索支援装置
１１  情報取得部
１２  待避地点設定部
１３  情報記憶部
２０  移動体管理装置
２１  移動体
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2020110273.tif 000003
【図２】
2020110273.tif 000004
【図３】
2020110273.tif 000005
【図４】
2020110273.tif 000006
【図５】
2020110273.tif 000007
【図６】
2020110273.tif 000008
【図７】
2020110273.tif 000009
【図８】
2020110273.tif 000010
【手続補正書】
【提出日】令和3年5月24日(2021.5.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための装置であって、
前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、情報取得部と、
前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、待避地点設定部と、
を備えている、ことを特徴とする経路探索支援装置。
【請求項２】
請求項１に記載の経路探索支援装置であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記待避地点設定部が、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とする経路探索支援装置。
【請求項３】
請求項２に記載の経路探索支援装置であって、
前記待避地点設定部が、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援装置。
【請求項４】
請求項２に記載の経路探索支援装置であって、
前記待避地点設定部が、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援装置。
【請求項５】
特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するための方法であって、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を有する、ことを特徴とする経路探索支援方法。
【請求項６】
請求項５に記載の経路探索支援方法であって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記（ｂ）のステップにおいて、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とする経路探索支援方法。
【請求項７】
請求項６に記載の経路探索支援方法であって、
前記（ｂ）のステップにおいて、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援方法。
【請求項８】
請求項６に記載の経路探索支援方法であって、
前記（ｂ）のステップにおいて、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とする経路探索支援方法。
【請求項９】
コンピュータによって、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するためのプログラムであって、
前記コンピュータに、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を実行させる、プログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、自立して移動する移動体の経路探索を支援するための、経路探索支援装置、及び経路探索支援方法に関し、更には、これらを実現するためのプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
本発明の目的の一例は、上記問題を解消し、人手に頼ることなく、自立して移動する移動体の経路探索で必要な待避地点の設定を可能にし得る、経路探索支援装置、経路探索支援方法、及びプログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、コンピュータによって、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するためのプログラムであって、
前記コンピュータに、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を実行させる、
ことを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００７０
【補正方法】変更
【補正の内容】
【００７０】
（付記９）
コンピュータによって、特定のエリアにおいて自立して移動する、複数の移動体の経路の探索を支援するためのプログラムであって、
前記コンピュータに、
（ａ）前記特定のエリアの地図情報、及び前記エリア内で前記移動体がタスクを実行するタスク地点を特定するタスク地点情報を取得する、ステップと、
（ｂ）前記地図情報及び前記タスク地点情報に基づいて、前記特定のエリアにおいて、前記タスク地点間の経路上に存在しないように、前記移動体の待避が可能となる待避地点を設定する、ステップと、
を実行させる、プログラム。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００７１
【補正方法】変更
【補正の内容】
【００７１】
（付記１０）
付記９に記載のプログラムであって、
前記地図情報が、前記特定のエリアを格子状に分割して得られた複数のグリッドそれぞれ毎の情報で構成され、
前記タスク地点情報が、前記タスク地点に対応する前記グリッドの位置を特定し、
前記（ｂ）のステップにおいて、前記待避地点となる前記グリッドを選択することによって、前記待避地点を設定する、
ことを特徴とするプログラム。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００７２
【補正方法】変更
【補正の内容】
【００７２】
（付記１１）
付記１０に記載のプログラムであって、
前記（ｂ）のステップにおいて、全ての前記タスク地点を結び、且つ、含まれる前記グリッドの数が最小となる、経路を特定し、特定した前記経路上のグリッド以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とするプログラム。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
（付記１２）
付記１０に記載のプログラムであって、
前記（ｂ）のステップにおいて、前記複数のグリッドにおいて、全ての前記タスク地点を含み、且つ、連結している、グリッドの集合を設定し、設定した前記集合以外のグリッドの中から、前記待避地点となるグリッドを選択する、
ことを特徴とするプログラム。
【国際調査報告】
2020110273.tif 000011
2020110273.tif 000012
2020110273.tif 000013
2020110273.tif 000014