(57)【要約】  経路計画装置１は、移動体２０に対応する目標場所までの第一の経路の探索において、単位時間ごとに、移動体２０それぞれの状態を表す状態情報を生成する、状態情報生成部２と、状態情報の生成を停止させる条件になると、状態情報の生成を停止させる、停止部３と、状態情報の生成を停止した後、状態が遷移する前の状態情報に基づいて、目標場所までの第二の経路を探索する、経路探索部４と、を有する。
2020157990.tif 000002
【特許請求の範囲】
【請求項１】
移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、状態情報生成部と、
前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、停止部と、
前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、経路探索部と、
を有することを特徴とする経路計画装置。
【請求項２】
請求項１に記載の経路計画装置であって、
前記状態情報生成部は、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とする経路計画装置。
【請求項３】
請求項１又は２に記載の経路計画装置であって、
前記経路探索部は、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とする経路計画装置。
【請求項４】
請求項１から３のいずれか一つに記載の経路計画装置であって、
前記経路探索部は、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とする経路計画装置。
【請求項５】
請求項１から４のいずれか一つに記載の経路計画装置であって、
前記状態情報の生成を停止させる前記条件を入力する、停止条件入力部を有する
ことを特徴とする経路計画装置。
【請求項６】
請求項５に記載の経路計画装置であって、
前記停止条件入力部は、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とする経路計画装置。
【請求項７】
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を有することを特徴とする経路計画方法。
【請求項８】
請求項７に記載の経路計画方法であって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とする経路計画方法。
【請求項９】
請求項７又は８に記載の経路計画方法であって、
前記（ｂ）のステップにおいて、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とする経路計画方法。
【請求項１０】
請求項７から９のいずれか一つに記載の経路計画方法であって、
前記（ｂ）のステップにおいて、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とする経路計画方法。
【請求項１１】
請求項７から１０のいずれか一つに記載の経路計画方法であって、
（ｄ）前記状態情報の生成を停止させる前記条件を入力する、ステップを有する
ことを特徴とする経路計画方法。
【請求項１２】
請求項１１に記載の経路計画方法であって、
前記（ｄ）のステップにおいて、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とする経路計画方法。
【請求項１３】
コンピュータに、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【請求項１４】
請求項１３に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１５】
請求項１３又は１４に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１６】
請求項１３から１５のいずれか一つに記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１７】
請求項１３から１６のいずれか一つに記載のコンピュータ読み取り可能な記録媒体であって、
（ｄ）前記状態情報の生成を停止させる前記条件を入力する、ステップを有する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【請求項１８】
請求項１７に記載のコンピュータ読み取り可能な記録媒体であって、
前記プログラムが、前記コンピュータに、
前記（ｄ）のステップにおいて、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路計画を行う経路計画装置、経路計画方法に関し、更には、これらを実現するためのプログラムを記録しているコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
従来から、無人搬送車（ＡＧＶ：Automated Guided Vehicle）は、作業効率及び生産効率などを向上させるため、種々の工場において導入されている。また、無人搬送車は、種々の物流施設においても、作業効率及び迅速な配送などを実現するために導入されている。【０００３】
非特許文献１、２には、複数の無人搬送車が互いに衝突しないような経路計画を求める最適化アルゴリズムが開示されている。例えば、非特許文献１には、Ａ＊＋ＯＤ（A-Star with Operator Decomposition）アルゴリズムが開示されている。また、非特許文献２には、ＣＢＳ（Conflict-Based Search）アルゴリズムが開示されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Trevor Standley, “Finding Optimal Solutionsto Cooperative Pathfinding Problems”,［online］，AAAI， 2010，［november 21, 2018検索］，＜URL：https://pdfs.semanticscholar.org/2529/f40c4f79ef24165dbb1a8327770e37cced2d.pdf＞
【非特許文献２】Guni Sharon  Roni Stern  Ariel Felner  Nathan Sturtevant, “Conflict-Based Search For Optimal Multi-Agent Path Finding”,［online］，AAAI， 2010，［november 21, 2018検索］，＜URL：https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5062/5239＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１、２に開示されている最適化アルゴリズムは、すべての無人搬送車が、対応する目標場所に到着するまでの移動時間の合計の最小化を行うような問題に対して、ＮＰ困難（NP-hardness ：Non-deterministic Polynomial-timehardness）である。【０００６】
すなわち、非特許文献１、２に開示されている最適化アルゴリズムは、最適な経路計画を得るまでに、長時間の演算時間が必要である。そのため、非特許文献１、２に開示されている最適化アルゴリズムは実用的でない。【０００７】
本発明の目的の一例は、経路計画の演算途中において演算を停止しても経路を得ることができる、経路計画装置、経路計画方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【０００８】
上記目的を達成するため、本発明の一側面における経路計画装置は、
移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、状態情報生成部と、
前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、停止部と、
前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、経路探索部と、
を有することを特徴とする。【０００９】
また、上記目的を達成するため、本発明の一側面における経路計画方法は、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を有することを特徴とする。【００１０】
更に、上記目的を達成するため、本発明の一側面におけるプログラムを記録したコンピュータ読み取り可能な記録媒体は、
コンピュータに、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
を実行させる命令を含むプログラムを記録していることを特徴とする。
【発明の効果】
【００１１】
以上のように本発明によれば、経路計画の演算途中において演算を停止しても経路を得ることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、経路計画装置の一例を示す図である。
【図２】図２は、経路計画装置を有する（１）システムの一例を示す図である。
【図３】図３は、経路計画装置を有する（２）システムの一例を示す図である。
【図４】図４は、グリッドマップの一例を示す図である。
【図５】図５は、Ａ＊における状態情報の生成の一例を示す図である。
【図６】図６は、ＣＢＳにおける状態情報の生成の一例を示す図である。
【図７】図７は、状態情報の停止の一例を示す図である。
【図８】図８は、経路計画装置の動作の一例を示す図である。
【図９】図９は、経路計画装置を実現するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
（実施の形態）
以下、本発明の実施の形態について、図１から図９を参照しながら説明する。
【００１４】
［装置構成］
最初に、図１を用いて、本実施の形態における経路計画装置１の構成について説明する。図１は、経路計画装置の一例を示す図である。
【００１５】
図１に示す経路計画装置１は、経路計画の演算途中において演算を停止しても経路を得ることができる装置である。また、図１に示すように、経路計画装置１は、状態情報生成部２と、停止部３と、経路探索部４とを有する。
【００１６】
このうち、状態情報生成部２は、移動体に対応する目標場所（ゴールポイント）までの経路（第一の経路）の探索において、単位時間ごとに、移動体それぞれの状態を表す状態情報を生成する。停止部３は、状態情報の生成を停止させる条件になると、状態情報の生成を停止させる。経路探索部４は、状態情報の生成を停止した後、状態が遷移する前の状態情報に基づいて、目標場所までの経路（第二の経路）を探索する。
【００１７】
なお、条件とは、例えば、停止までに生成する状態情報の数、又は、状態情報の生成開始から停止までの時間、又は、それらの二つを含む条件である。
【００１８】
このように、本実施の形態においては、あらかじめ設定した条件に基づいて、状態情報の生成を停止し、再度、目標場所までの第二の経路を探索するので、探索の途中（経路計画の演算途中）で演算を停止しても経路を得ることができる。
【００１９】
従来のような経路計画は、最適な経路計画を得るまでに、長時間の演算時間を必要とするため、実用的ではない。対して、本実施の形態においては、経路計画を任意に停止しても、その停止時において、ある程度の品質の解を出力できる。すなわち、経路計画の演算時間が短くても、最適ではない（移動時間の合計が最小ではない）が経路を得ることができる。
【００２０】
従って、どのタイミングでも経路を得ることができるので実用的である。なお、経路計画の演算時間を長くするほど、より最適な経路を得ることができる。
【００２１】
更に、経路（第二の経路）を設定した後、移動体を動かしながら、より良い経路を探索する運用も可能である。
【００２２】
［システム構成］
続いて、図２、図３を用いて、本実施の形態における経路計画装置１の構成をより具体的に説明する。図２、図３それぞれは、経路計画装置を有する（１）（２）システムの一例を示す図である。図２、図３それぞれに示すように、本実施の形態におけるシステムは、経路計画装置１と複数の移動体２０とを有する。
【００２３】
（１）移動体制御装置主体型のシステム
図２は、経路計画装置１を移動体制御装置１０に設けたシステムである。図２に示されている移動体制御装置１０は、経路計画装置１、通信部１１、指示部１２を有する。そのうち経路計画装置１は、状態情報生成部２と、停止部３と、経路探索部４とに加えて、停止条件入力部５を有する。移動体２０は、通信部２１、センサ部２２、位置推定部２３、移動制御部２４、移動部２５を有する。
【００２４】
（２）移動体主体型のシステム
図３は、経路計画装置１を移動体２０に設けたシステムである。図３の例では、移動体２０のいずれか一つをマスタとし、マスタとなる移動体２０に経路計画装置１を設ける。図３に示されている移動体制御装置１０は、通信部１１、指示部１２を有する。移動体２０は、経路計画装置１、通信部２１、センサ部２２、位置推定部２３、移動制御部２４、移動部２５を有する。そのうち経路計画装置１は、状態情報生成部２と、停止部３と、経路探索部４とに加えて、停止条件入力部５を有する。
【００２５】
なお、システムの構成は、上述した（１）（２）に示したシステム以外の構成でもよい。具体的には、状態情報生成部２、停止部３、経路探索部４、停止条件入力部５を、移動体制御装置１０と移動体２０とに分散させてもよい。その場合、移動体制御装置１０と移動体２０との構成内容に応じて、通信部１１と通信部２１との通信内容を変更する。
【００２６】
移動体制御装置について説明する。
移動体制御装置１０は、移動体２０それぞれに対して、移動体２０を目標場所まで移動させるための制御をする。なお、移動体制御装置１０は、例えば、サーバコンピュータなどの情報処理装置である。
【００２７】
通信部１１は、移動体２０の通信部２１と通信をする。具体的には、通信部１１は、（１）（２）のシステムにおいて、移動体２０を移動させるための指示を表す指示情報などを、移動体２０へ送信する。また、通信部１１は、（１）のシステムにおいて、移動体２０の位置を表す位置情報などを、移動体２０から受信する。
【００２８】
指示部１２は、移動体２０に対して、移動体２０を移動させるために用いる指示をする。具体的には、指示部１２は、移動体２０を目標場所へ移動させるために用いる指示を表す指示情報を生成し、移動体２０へ通信部１１を介して送信する。
【００２９】
経路計画装置１は、移動体２０を目標場所に移動させるための経路（第二の経路）を計画する。具体的には、経路計画装置１は、位置情報と、地図情報と、移動体２０が到達する目標場所を表す目標場所情報とを用いて、目標場所に移動体２０を移動する場合に用いる経路（第二の経路）を表す経路情報を生成する。
【００３０】
地図情報は、対象の施設内の配置図などを表す情報である。地図情報は、例えば、工場、物流施設において移動体２０が移動する経路、移動体２０が到達する目標場所などを表す情報を有する。また、地図情報として、例えば、グリッドマップなどを用いることが望ましい。更に、地図情報は、移動体制御装置１０内部、又は移動体２０内部、又はそれら以外に設けられた不図示の記憶部に記憶されている。
【００３１】
図４は、グリッドマップの一例を示す図である。グリッド範囲４１（以降、グリッドと呼ぶ）に、移動体２０（Ｍａ）（Ｍｂ）、目標場所（Ｇａ）（Ｇｂ）、移動不可場所（網掛け範囲）が示されている。
【００３２】
移動体について説明する。
移動体２０は、移動体制御装置１０から指示情報を取得し、目標場所まで移動する。具体的には、移動体２０として、無人搬送車、自動走行車両、自動飛行体、自動航行船舶、ロボットなどが考えられる。
【００３３】
通信部２１は、移動体制御装置１０の通信部１１と通信をする。具体的には、通信部２１は、（１）のシステムにおいて、位置情報などを移動体制御装置１０へ送信する。また、通信部２１は、（１）（２）のシステムにおいて、移動体２０を移動させる指示を表す指示情報などを、移動体制御装置１０から受信する。
【００３４】
センサ部２２は、移動体２０の状態、対象物（例えば、トレイ、棚など）、移動体２０の移動を補助する標識、実際の経路上の障害物などを検知するセンサなどである。具体的には、センサ部２２は、レーダ、超音波センサ、撮像装置、ジャイロ、エンコーダ、ＧＰＳ（Global Positioning System）などの装置のうち一つ以上を有する。
【００３５】
位置推定部２３は、移動体２０の自己位置を推定する。具体的には、位置推定部２３は、センサ部２２の計測結果を表す計測情報を取得し、取得した計測情報に基づいて、移動体２０の自己位置を推定し、位置情報を生成する。
【００３６】
移動制御部２４は、移動体２０に設けられた、移動体２０を移動させる移動部２５を制御する。具体的には、移動制御部２４は、上述した経路情報を用いて、移動部２５を制御し、移動体２０を目標場所へ移動させる。
【００３７】
移動部２５は、移動体２０を移動させる装置である。具体的には、移動体２０が電気車両であれ場合、移動部２５は、モータ、車輪、電池などの電気車両を移動させるために必要な手段である。
【００３８】
経路計画装置について説明をする。
図５、図６、図７を用いて、経路計画装置１について説明をする。図５は、Ａ＊における状態情報の生成の一例を示す図である。図６は、ＣＢＳにおける状態情報の生成の一例を示す図である。図７は、状態情報の停止の一例を示す図である。
【００３９】
状態情報生成部２は、移動体２０それぞれに対応する目標場所までの経路（第一の経路）の探索において、単位時間ごとに、移動体２０それぞれの状態を表す状態情報を生成する。単位時間は、移動体２０が次のグリッドへ移動するために要する時間である。
【００４０】
具体的には、状態情報生成部２は、最適化アルゴリズムを用いて、移動体２０から目標場所までの経路（第一の経路）を探索する。最適化アルゴリズムは、例えば、Ａ＊（A-star）、ＣＢＳ（Conflict-Based Search）などを用いることが考えられる。
【００４１】
また、状態情報生成部２に、停止部３から状態情報の生成を停止させる指示を取得した場合、状態情報の生成を停止する。
【００４２】
Ａ＊を適用した場合について説明をする。
Ａ＊においては、状態情報生成部２は、状態を遷移させ、遷移させて得られた複数の状態のなかに、すべての移動体２０が目標場所に到達している状態が検出された場合、その検出された状態から状態を逆に辿り、それらの状態に対応する移動情報（ACTION）を用いて、経路（第一の経路）を生成する。
【００４３】
すなわち、状態情報生成部２は、状態を状態情報（STATE）とし、移動体２０それぞれの移動距離と移動方向とを遷移情報（ACTION）として、目標場所までの経路（第一の経路）を探索する。
【００４４】
具体的には、図５に示すように、状態（STATE0）を基点とした場合、状態（STATE0）の遷移（ACTION1、ACTION2、ACTION3）先として状態（STATE1、STATE2、STATE3）が生成される。なお、図５において、遷移（ACTION1）は移動体２０（Ｍａ）の右への移動を表し、遷移（ACTION2）は移動体２０（Ｍｂ）の左へ移動を表し、遷移（ACTION3）は移動体２０（Ｍａ）の右へ移動を表している。
【００４５】
ＣＢＳを適用した場合について説明をする。
ＣＢＳにおいては、状態情報生成部２は、移動体２０それぞれの進入禁止の位置と、進入禁止の追加とを用いて、移動体２０それぞれについて経路（第一の経路）を探索する。
【００４６】
すなわち、状態情報生成部２は、進入禁止の位置の状態を状態情報（STATE）とし、移動体２０それぞれの追加する進入禁止位置を遷移情報（ACTION）として、目標場所までの経路を探索する。
【００４７】
具体的には、図６に示すように、時刻ｔ２における状態（STATE0）を基点とした場合、時刻ｔ３における状態（STATE0）の遷移（ACTION1、ACTION2）先として状態（STATE1、STATE2、）が生成される。なお、遷移（ACTION1）は時刻ｔ３における移動体２０（Ｍｂ）の進入禁止位置を表し、遷移（ACTION2）は時刻ｔ３における移動体２０（Ｍｃ）の進入禁止を表している。
【００４８】
なお、最適化アルゴリズムとして、Ａ＊＋ＯＤ（A* with operatordecomposition）を用いてもよい。
【００４９】
停止部３は、状態情報の生成を停止させる条件になると、状態情報の生成を停止する。具体的には、停止部３は、あらかじめ停止までに生成する状態情報（STATE）の数、又は、状態情報生成から停止までの時間、又は、それらの二つを含む条件に基づいて、状態情報生成部２の状態情報の生成を停止させる。
【００５０】
図７は、状態情報生成部２が状態（STATE0）を基点に状態を遷移させた場合に、条件に達したため、停止部３が状態情報生成部２へ状態の遷移を停止させたことを示す図である。
【００５１】
経路探索部４は、初期状態において、多項式アルゴリズムを用いて、初期位置の移動体２０それぞれから対応する目標場所までの初期の経路（第二の経路）を探索する。また、経路探索部４は、状態情報の生成を停止した後、状態が遷移する前の状態情報に基づいて、目標場所までの経路（第二の経路）を探索する。そして、経路探索部４は、探索した経路（第二の経路）に基づいて、状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、状態が遷移する前の状態情報から基点となる状態情報を選択する。
【００５２】
具体的には、経路探索部４は、多項式アルゴリズムを用いて、目標場所までの経路（第二の経路）を探索する。なお、多項式アルゴリズムは、移動距離が最小（最適解）ではないが、高速に経路を算出できるアルゴリズムである。
【００５３】
多項式アルゴリズムとして、例えば、ＣＡ＊（Cooperative A-star）を用いることが考えられる。ＣＡ＊については、例えば、David Silver, “Cooperative pathfinding”, In Proceedings of the First AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE’05, 117?122. AAAIPress. ＜URL：http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/coop-path-AIIDE.pdf＞などに記載されている。
【００５４】
また、多項式アルゴリズムとして、Parallel Push & Swapなどを用いてもよい。
【００５５】
初期状態における探索について説明をする。
経路探索部４は、初期状態において、多項式アルゴリズムを用いて、移動体２０それぞれから対応する目標場所までの経路を探索し、探索した経路を用いてコストを算出する。
【００５６】
コストは、例えば、移動体２０それぞれの経路ごとに、移動体２０の位置から対応する目標場所までの距離を算出し、移動体２０ごとに算出した距離を合計した値である。距離は、例えば、経路上のグリッドの数などを用いて表す。なお、図７の例では、初期状態（STATE0）におけるコストを１０と仮定する。
【００５７】
状態情報の生成を停止後における探索について説明をする。
経路探索部４は、状態情報生成部２が状態情報の生成を停止したことを検知した場合、停止時の状態のうち状態が遷移する前（未展開）の状態を取得する。すなわち、図７に示す太線網掛けの円形で表されている状態を取得する。
【００５８】
続いて、経路探索部４は、取得した未展開の状態それぞれに対して、多項式アルゴリズムを用いて、目標場所までの経路（第二の経路）を探索する。
【００５９】
続いて、経路探索部４は、探索した経路（第二の経路）に基づいて、状態が遷移する前の状態情報ごとのコストを算出する。図７の例では、未展開の状態それぞれに対してコストを示している。
【００６０】
続いて、経路探索部４は、算出したコストを用いて、状態が遷移する前の状態情報から基点となる状態情報を選択する。具体的には、経路探索部４は、初期状態（STATE0）におけるコストと、未展開の状態それぞれのコストとを比較し、未展開の状態それぞれのなかで最小のコストで、かつ初期状態（STATE0）のコストより小さい状態情報を選択する。
【００６１】
図７の例では、未展開の状態それぞれのなかで最小のコストが９で、初期状態（STATE0）のコストが１０であるので、状態（STATEn）が選択される。なお、複数のコストに対応する状態を選択してもよい。
【００６２】
また、未展開の状態それぞれのコストが、初期状態におけるコスト以上である場合には、経路探索部４は初期状態を継続する。更に、未展開の状態のコストの最小が、初期状態におけるコストと同じ場合には、経路探索部４はいずれかのコストに対応する状態を選択する。
【００６３】
なお、状態情報生成部２は、選択したコストに対応する状態情報（STATEn）を初期状態に設定し、最適化アルゴリズムを用いて、状態情報の生成をする。
【００６４】
停止条件入力部５は、状態情報の生成を停止させる条件が入力される。具体的には、停止条件入力部５は、利用者により入力された条件があらかじめ設定した所定条件でない場合、再入力を促す。例えば、入力された条件が、状態情報生成部２が生成する状態情報の数である場合、その数があらかじめ設定された所定値（所定条件）以下であるなら、利用者に正しい入力をするよう、不図示の出力装置に表示させる。又は、入力された条件が、状態情報を生成する時間である場合、その数があらかじめ設定された所定時間（所定条件）以下であるなら、利用者に正しい入力をするよう、不図示の出力装置に表示させる。
【００６５】
［装置動作］
次に、本発明の実施の形態における経路計画装置の動作について図８を用いて説明する。図８は、経路計画装置の動作の一例を示す図である。以下の説明においては、適宜図２から図７を参照する。また、本実施の形態では、経路計画装置を動作させることによって、経路計画方法が実施される。よって、本実施の形態における経路計画方法の説明は、以下の経路計画装置の動作説明に代える。
【００６６】
図８に示すように、最初に、経路計画装置１は、初期設定を取得する（ステップＡ１）。具体的には、ステップＡ１において、経路探索部４は、初期状態において、多項式アルゴリズムを用いて、初期位置の移動体２０それぞれから対応する目標場所までの経路（第二の経路）の探索と、探索した経路を用いてコストを算出する。
【００６７】
コストは、例えば、移動体２０それぞれの経路ごとに、移動体２０の位置から対応する目標場所までの距離を算出し、移動体２０それぞれの距離の合計した値である。距離は、例えば、経路上のグリッドの数などを用いて表す。なお、図７の例では、初期状態（STATE0）におけるコストを１０と仮定する。
【００６８】
続いて、状態情報生成部２は、移動体２０それぞれに対応する目標場所までの経路の探索において、単位時間ごとに、移動体２０それぞれの状態を表す状態情報を生成する（ステップＡ２）。単位時間は、移動体２０が次のグリッドへ移動するために要する時間である。
【００６９】
具体的には、ステップＡ２において、状態情報生成部２は、最適化アルゴリズムを用いて、移動体２０から目標場所までの経路（第一の経路）を探索する。最適化アルゴリズムは、例えば、Ａ＊、ＣＢＳなどを用いることが考えられる。
【００７０】
Ａ＊を適用した場合について説明をする。
ステップＡ２において、状態情報生成部２は、状態を状態情報（STATE）とし、移動体２０それぞれの移動距離と移動方向とを遷移情報（ACTION）として、目標場所までの経路（第一の経路）を探索する。
【００７１】
具体的には、図５に示すように、状態（STATE0）を基点とした場合、状態（STATE0）の遷移（ACTION1、ACTION2、ACTION3）先として状態（STATE1、STATE2、STATE3）が生成される。なお、図５において、遷移（ACTION1）は移動体２０（Ｍａ）の右への移動を表し、遷移（ACTION2）は移動体２０（Ｍｂ）の左へ移動を表し、遷移（ACTION3）は移動体２０（Ｍａ）の右へ移動を表している。
【００７２】
ＣＢＳを適用した場合について説明をする。
ステップＡ２において、ＣＢＳにおいては、進入禁止の位置の状態を状態情報（STATE）とし、移動体２０それぞれの追加する進入禁止位置を遷移情報（ACTION）として、目標場所までの経路（第一の経路）を探索する。
【００７３】
具体的には、図６に示すように、時刻ｔ２における状態（STATE0）を基点とした場合、時刻３における状態（STATE0）の遷移（ACTION1、ACTION2）先として状態（STATE1、STATE2、）が生成される。なお、遷移（ACTION1）は時刻ｔ３における移動体２０（Ｍｂ）の進入禁止位置を表し、遷移（ACTION2）は時刻ｔ３における移動体２０（Ｍｃ）の進入禁止を表している。
【００７４】
なお、最適化アルゴリズムとして、Ａ＊＋ＯＤ（A* with operatordecomposition）を用いてもよい。
【００７５】
続いて、停止部３は、状態情報の生成を停止させる条件になると、状態情報の生成を停止する（ステップＡ３）。具体的には、停止部３は、生成する状態情報の数、又は、状態情報生成から停止までの時間、又は、それらの二つが、状態情報の生成を停止させる条件に一致した場合（ステップＡ３：Ｙｅｓ）、状態情報生成部２の状態情報の生成を停止させる（ステップＡ４）。対して、条件に一致しない場合（ステップＡ３：Ｎｏ）は、ステップＡ２の処理を継続する。
【００７６】
続いて、経路探索部４は、状態情報の生成を停止した後、状態が遷移する前の状態情報に基づいて、多項式アルゴリズムを用いて、目標場所までの経路（第二の経路）を探索する（ステップＡ５）。なお、多項式アルゴリズムは、移動距離が最小（最適解）ではないが、高速に経路をえることができるアルゴリズムである。
【００７７】
具体的には、ステップＡ５において、経路探索部４は、状態情報生成部２が状態情報の生成を停止したことを検知した場合、停止時の状態のうち状態が遷移する前（未展開）の状態を取得する。すなわち、図７に示す太線網掛けの円形で表されている状態を取得する。
【００７８】
続いて、ステップＡ５において、経路探索部４は、取得した未展開の状態それぞれに対して、多項式アルゴリズムを用いて、目標場所までの経路（第二の経路）を探索する。
【００７９】
続いて、経路探索部４は、探索した経路（第二の経路）に基づいて、状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、状態が遷移する前の状態情報から基点となる状態情報を選択する（ステップＡ６）。
【００８０】
具体的には、ステップＡ６において、経路探索部４は、探索した経路（第二の経路）に基づいて、状態が遷移する前の状態情報ごとのコストを算出する。図７の例では、未展開の状態それぞれに対してコストを示している。
【００８１】
続いて、経路探索部４は、算出したコストを用いて、状態が遷移する前の状態情報から基点となる状態情報と、当該状態情報に対応する経路（第二の経路）を選択する（ステップＡ７）。
【００８２】
例えば、経路探索部４は、初期状態（STATE0）におけるコストと、未展開の状態それぞれのコストとを比較し、未展開の状態それぞれのなかで最小のコストで、かつ初期状態（STATE0）のコストより小さい状態情報を選択する。
【００８３】
図７の例では、未展開の状態それぞれのなかで最小のコストが９で、初期状態（STATE0）のコストが１０であるので、状態（STATEn）が選択される。なお、複数のコストに対応する状態を選択してもよい。
【００８４】
また、未展開の状態それぞれのコストが、初期状態におけるコスト以上である場合には、経路探索部４は初期状態を継続する。更に、未展開の状態のコストの最小が、初期状態におけるコストと同じ場合には、経路探索部４はいずれかのコストに対応する状態を選択する。
【００８５】
続いて、経路計画を終了する場合（ステップＡ８：Ｙｅｓ）、経路計画装置１はステップＡ２からＡ７の処理を終了する。また、経路計画を終了しない場合（ステップＡ８：Ｎｏ）、ステップＡ２に移行して、状態情報生成部２は、選択したコストに対応する状態情報（STATEn）を初期状態（STATE0）に設定し、最適化アルゴリズムを用いて、状態情報の生成をする。
【００８６】
なお、ステップＡ１の初期設定をする場合に、停止条件入力部５を用いて、状態情報の生成を停止させる条件が入力する。具体的には、停止条件入力部５は、条件があらかじめ設定した所定条件でない場合、再入力を促す。例えば、状態情報生成部２が生成する状態情報の数が閾値（所定条件）以下である場合、又は、状態情報を生成する時間が閾値（所定条件）以下である場合に、利用者に正しい停止させる条件を入力をするよう、不図示の出力装置に表示させる。
【００８７】
［本実施の形態の効果］
以上のように本実施の形態によれば、あらかじめ設定した条件に基づいて、状態情報の生成を停止し、再度、目標場所までの第二の経路を探索するので、探索の途中（経路計画の演算途中）で演算を停止しても経路を得ることができる。
【００８８】
また、本実施の形態においては、経路計画を任意に停止しても、その停止時において、ある程度の品質の解を出力できる。すなわち、経路計画の演算時間が短くても、最適ではない（移動時間の合計が最小ではない）が経路を得ることができる。
【００８９】
従って、どのタイミングでも経路を得ることができるので実用的である。なお、経路計画の演算時間を長くするほど、より最適な経路を得ることができる。
【００９０】
更に、経路（第二の経路）を設定した後、移動体を動かしながら、より良い経路を探索する運用も可能である。
【００９１】
［プログラム］
本発明の実施の形態におけるプログラムは、コンピュータに、図８に示すステップＡ１からＡ８を実行させるプログラムであればよい。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態における経路計画装置と経路計画方法とを実現することができる。
【００９２】
具体的には、（１）のシステムの場合、移動体制御装置１０側のコンピュータのプロセッサは、状態情報生成部２、停止部３、経路探索部４、停止条件入力部５として機能し、処理を行なう。また、（２）のシステムの場合、移動体２０側のコンピュータのプロセッサは、状態情報生成部２、停止部３、経路探索部４、停止条件入力部５として機能し、処理を行なう。
【００９３】
また、本実施の形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されてもよい。この場合は、例えば、各コンピュータが、それぞれ、状態情報生成部２、停止部３、経路探索部４、停止条件入力部５のいずれかとして機能してもよい。
【００９４】
［物理構成］
ここで、実施の形態におけるプログラムを実行することによって、経路計画装置を実現するコンピュータについて図９を用いて説明する。図９は、本発明の実施の形態における経路計画装置を実現するコンピュータの一例を示すブロック図である。
【００９５】
図９に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。なお、コンピュータ１１０は、ＣＰＵ１１１に加えて、又はＣＰＵ１１１に代えて、ＧＰＵ（Graphics Processing Unit）、又はＦＰＧＡ（Field-Programmable Gate Array）を備えていてもよい。
【００９６】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）などの揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであってもよい。
【００９７】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置があげられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【００９８】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【００９９】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）などの汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記録媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記録媒体があげられる。
【０１００】
なお、本実施の形態における経路計画装置１は、プログラムがインストールされたコンピュータではなく、各部に対応したハードウェアを用いることによっても実現可能である。更に、経路計画装置１は、一部がプログラムで実現され、残りの部分がハードウェアで実現されていてもよい。
【０１０１】
［付記］
以上の実施の形態に関し、更に以下の付記を開示する。上述した実施の形態の一部又は全部は、以下に記載する（付記１）から（付記１８）により表現することができるが、以下の記載に限定されるものではない。
【０１０２】
（付記１）
移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、状態情報生成部と、
前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、停止部と、
前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、経路探索部と、
を有することを特徴とする経路計画装置。
【０１０３】
（付記２）
付記１に記載の経路計画装置であって、
前記状態情報生成部は、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とする経路計画装置。
【０１０４】
（付記３）
付記１又は２に記載の経路計画装置であって、
前記経路探索部は、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とする経路計画装置。
【０１０５】
（付記４）
付記１から３のいずれか一つに記載の経路計画装置であって、
前記経路探索部は、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とする経路計画装置。
【０１０６】
（付記５）
付記１から４のいずれか一つに記載の経路計画装置であって、
前記状態情報の生成を停止させる前記条件を入力する、停止条件入力部を有する
ことを特徴とする経路計画装置。
【０１０７】
（付記６）
付記５に記載の経路計画装置であって、
前記停止条件入力部は、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とする経路計画装置。
【０１０８】
（付記７）
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を有することを特徴とする経路計画方法。
【０１０９】
（付記８）
付記７に記載の経路計画方法であって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とする経路計画方法。
【０１１０】
（付記９）
付記７又は８に記載の経路計画方法であって、
前記（ｂ）のステップにおいて、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とする経路計画方法。
【０１１１】
（付記１０）
付記７から９のいずれか一つに記載の経路計画方法であって、
前記（ｂ）のステップにおいて、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とする経路計画方法。
【０１１２】
（付記１１）
付記７から１０のいずれか一つに記載の経路計画方法であって、
（ｄ）前記状態情報の生成を停止させる前記条件を入力する、ステップを有する
ことを特徴とする経路計画方法。
【０１１３】
（付記１２）
付記１１に記載の経路計画方法であって、
前記（ｄ）のステップにおいて、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とする経路計画方法。
【０１１４】
（付記１３）
コンピュータに、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【０１１５】
（付記１４）
付記１３に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【０１１６】
（付記１５）
付記１３又は１４に記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【０１１７】
（付記１６）
付記１３から１５のいずれか一つに記載のコンピュータ読み取り可能な記録媒体であって、
前記（ｂ）のステップにおいて、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【０１１８】
（付記１７）
付記１３から１６のいずれか一つに記載のコンピュータ読み取り可能な記録媒体であって、
（ｄ）前記状態情報の生成を停止させる前記条件を入力する、ステップを有する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【０１１９】
（付記１８）
付記１７に記載のコンピュータ読み取り可能な記録媒体であって、
前記プログラムが、前記コンピュータに、
前記（ｄ）のステップにおいて、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【０１２０】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用可能性】
【０１２１】
以上のように本発明によれば、経路計画の演算途中において演算を停止しても経路を得ることができる。本発明は、経路計画に従い移動体を目標場所に移動させることが必要な分野において有用である。
【符号の説明】
【０１２２】
１  経路計画装置
２  状態情報生成部
３  停止部
４  経路探索部
５  停止条件入力部
１０  移動体制御装置
１１  通信部
１２  指示部
２０  移動体
２１  通信部
２２  センサ部
２３  位置推定部
２４  移動制御部
２５  移動部
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2020157990.tif 000003
【図２】
2020157990.tif 000004
【図３】
2020157990.tif 000005
【図４】
2020157990.tif 000006
【図５】
2020157990.tif 000007
【図６】
2020157990.tif 000008
【図７】
2020157990.tif 000009
【図８】
2020157990.tif 000010
【図９】
2020157990.tif 000011
【手続補正書】
【提出日】令和3年6月15日(2021.6.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、状態情報生成部と、
前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、停止部と、
前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、経路探索部と、
を有することを特徴とする経路計画装置。
【請求項２】
請求項１に記載の経路計画装置であって、
前記状態情報生成部は、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とする経路計画装置。
【請求項３】
請求項１又は２に記載の経路計画装置であって、
前記経路探索部は、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とする経路計画装置。
【請求項４】
請求項１から３のいずれか一つに記載の経路計画装置であって、
前記経路探索部は、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とする経路計画装置。
【請求項５】
請求項１から４のいずれか一つに記載の経路計画装置であって、
前記状態情報の生成を停止させる前記条件を入力する、停止条件入力部を有する
ことを特徴とする経路計画装置。
【請求項６】
請求項５に記載の経路計画装置であって、
前記停止条件入力部は、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とする経路計画装置。
【請求項７】
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を有することを特徴とする経路計画方法。
【請求項８】
請求項７に記載の経路計画方法であって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とする経路計画方法。
【請求項９】
コンピュータに、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索するステップと、
を実行させるプログラム。
【請求項１０】
請求項９に記載のプログラムであって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とするプログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、経路計画を行う経路計画装置、経路計画方法に関し、更には、これらを実現するためのプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
本発明の目的の一例は、経路計画の演算途中において演算を停止しても経路を得ることができる、経路計画装置、経路計画方法、及びプログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１０
【補正方法】変更
【補正の内容】
【００１０】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、
コンピュータに、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を実行させることを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
【図１】図１は、経路計画装置の一例を示す図である。
【図２】図２は、経路計画装置を有する（１）システムの一例を示す図である。
【図３】図３は、経路計画装置を有する（２）システムの一例を示す図である。
【図４】図４は、グリッドマップの一例を示す図である。
【図５】図５は、Ａ＊における状態情報の生成の一例を示す図である。
【図６】図６は、ＣＢＳにおける状態情報の生成の一例を示す図である。
【図７】図７は、状態情報の生成の停止の一例を示す図である。
【図８】図８は、経路計画装置の動作の一例を示す図である。
【図９】図９は、経路計画装置を実現するコンピュータの一例を示す図である。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００３８
【補正方法】変更
【補正の内容】
【００３８】
経路計画装置について説明をする。
図５、図６、図７を用いて、経路計画装置１について説明をする。図５は、Ａ＊における状態情報の生成の一例を示す図である。図６は、ＣＢＳにおける状態情報の生成の一例を示す図である。図７は、状態情報の生成の停止の一例を示す図である。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
ＣＢＳを適用した場合について説明をする。
ＣＢＳにおいては、状態情報生成部２は、移動体２０それぞれの進入禁止の位置と、進入禁止位置の追加とを用いて、移動体２０それぞれについて経路（第一の経路）を探索する。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００４７
【補正方法】変更
【補正の内容】
【００４７】
具体的には、図６に示すように、時刻ｔ２における状態（STATE0）を基点とした場合、時刻ｔ３における状態（STATE0）の遷移（ACTION1、ACTION2）先として状態（STATE1、STATE2）が生成される。なお、遷移（ACTION1）は時刻ｔ３における移動体２０（Ｍｂ）の進入禁止位置を表し、遷移（ACTION2）は時刻ｔ３における移動体２０（Ｍｃ）の進入禁止位置を表している。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
具体的には、図６に示すように、時刻ｔ２における状態（STATE0）を基点とした場合、時刻ｔ３における状態（STATE0）の遷移（ACTION1、ACTION2）先として状態（STATE1、STATE2）が生成される。なお、遷移（ACTION1）は時刻ｔ３における移動体２０（Ｍｂ）の進入禁止位置を表し、遷移（ACTION2）は時刻ｔ３における移動体２０（Ｍｃ）の進入禁止位置を表している。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１１４
【補正方法】変更
【補正の内容】
【０１１４】
（付記１３）
コンピュータに、
（ａ）移動体に対応する目標場所までの第一の経路の探索において、単位時間ごとに、前記移動体それぞれの状態を表す状態情報を生成する、ステップと、
（ｂ）前記状態情報の生成を停止させる条件になると、前記状態情報の生成を停止させる、ステップと、
（ｃ）前記状態情報の生成を停止した後、前記状態が遷移する前の状態情報に基づいて、前記目標場所までの第二の経路を探索する、ステップと、
を実行させるプログラム。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１１５
【補正方法】変更
【補正の内容】
【０１１５】
（付記１４）
付記１３に記載のプログラムであって、
前記（ａ）のステップにおいて、最適化アルゴリズムを用いて、前記移動体から前記目標場所までの第一の経路を探索する
ことを特徴とするプログラム。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１１６
【補正方法】変更
【補正の内容】
【０１１６】
（付記１５）
付記１３又は１４に記載のプログラムであって、
前記（ｂ）のステップにおいて、多項式アルゴリズムを用いて、前記状態情報の生成を停止後の前記移動体の位置を基点とし、前記目標場所までの第二の経路を探索する
ことを特徴とするプログラム。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
（付記１６）
付記１３から１５のいずれか一つに記載のプログラムであって、
前記（ｂ）のステップにおいて、前記第二の経路に基づいて、前記状態が遷移する前の状態情報ごとにコストを算出し、算出したコストを用いて、前記状態が遷移する前の状態情報から基点となる状態情報を選択する
ことを特徴とするプログラム。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１１８
【補正方法】変更
【補正の内容】
【０１１８】
（付記１７）
付記１３から１６のいずれか一つに記載のプログラムであって、
（ｄ）前記状態情報の生成を停止させる前記条件を入力する、ステップを有する
ことを特徴とするプログラム。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１１９
【補正方法】変更
【補正の内容】
【０１１９】
（付記１８）
付記１７に記載のプログラムであって、
前記プログラムが、前記コンピュータに、
前記（ｄ）のステップにおいて、前記条件があらかじめ設定した所定条件でない場合、再入力を促す
ことを特徴とするプログラム。
【国際調査報告】
2020157990.tif 000012
2020157990.tif 000013
2020157990.tif 000014
2020157990.tif 000015