(57)【要約】  【課題】  複数の移動体の経路について、迂回経路も含む最適な経路を推定する。  【解決手段】  複数の移動体２の最適経路を推定する経路推定システム１は、複数の移動体２の各々について、最短経路及び迂回経路の時系列経路候補を生成する最短経路生成部３４及び迂回経路生成部３５と、複数の移動体２の各々について、最短経路及び迂回経路の時系列経路候補の経路割当評価値を計算する経路割当評価値計算部３６と、複数の移動体２の各々について、最短経路及び迂回経路の時系列経路候補の移動距離評価値を計算する移動距離評価値計算部３７と、複数の移動体２の各々の時系列経路候補の組み合わせの経路衝突評価値を計算する経路衝突評価値計算部３８と、複数の移動体の時系列経路候補の組み合わせについて、経路割当評価値、移動距離評価値、及び経路衝突評価値の合計値を比較することで、複数の移動体２の時系列経路の組み合わせを最適候補として推定する評価値比較部３９とを備えている。【選択図】  図１
2020046384.tif 000002
【特許請求の範囲】
【請求項１】
複数の移動体の最適経路を推定する経路推定システム（１）であって、
前記複数の移動体の各々について、最短経路の時系列経路候補を生成する最短経路生成部（３４）と、
前記複数の移動体の各々について、迂回経路の時系列経路候補を生成する迂回経路生成部（３５）と、
前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の経路割当評価値を計算する経路割当評価値計算部（３６）と、
前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の移動距離評価値を計算する移動距離評価値計算部（３７）と、
前記複数の移動体の各々の前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の組み合わせの経路衝突評価値を計算する経路衝突評価値計算部（３８）と、
複数の移動体の時系列経路候補の組み合わせについて、前記経路割当評価値、前記移動距離評価値、及び前記経路衝突評価値の合計値を比較することで、複数の移動体の時系列経路の組み合わせを最適候補として推定する評価値比較部（３９）と、
を備えた経路推定システム。
【請求項２】
前記移動距離評価値計算部は、前記迂回経路の移動距離評価値を計算する際に、前記迂回経路と前記最短経路との距離の差分に応じた補正を加える、請求項１に記載の経路推定システム。
【請求項３】
前記経路割当評価値計算部は、各移動体について複数の前記時系列経路候補が選択される場合に前記経路割当評価値が十分に大きくなるように係数を設定する、請求項１又は２に記載の経路推定システム。
【請求項４】
前記移動距離評価値計算部は、優先順位の高い移動体の前記移動距離評価値が小さくなるように、各移動体について優先順位に応じて異なる係数を設定して前記移動距離評価値を算出する、請求項１〜３のいずれかに記載の経路推定システム。
【請求項５】
前記経路衝突評価値計算部は、前記複数の移動体が衝突する場合に前記経路衝突評価値が十分に大きくなるように係数を設定する、請求項１〜４のいずれかに記載の経路推定システム。
【請求項６】
前記複数の移動体の各々の前記最短経路が互いに重複しないときは、当該最短経路を前記最適候補として推定する、請求項１〜５のいずれかに記載の経路推定システム。
【請求項７】
前記合計値が同じ前記複数の移動体の時系列経路の組み合わせが複数あるときに、優先順位の高い前記移動体の移動距離評価値が低い前記複数の移動体の時系列経路の組み合わせを前記最適経路として推定する、請求項１〜６のいずれかに記載の経路推定システム。
【請求項８】
複数の移動体の最適経路を推定する経路推定プログラムであって、
コンピュータを、
前記複数の移動体の各々について、最短経路の時系列経路候補を生成する最短経路生成部、
前記複数の移動体の各々について、迂回経路の時系列経路候補を生成する迂回経路生成部、
前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の経路割当評価値を計算する経路割当評価値計算部、
前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の移動距離評価値を計算する移動距離評価値計算部、
前記複数の移動体の各々の前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の組み合わせの経路衝突評価値を計算する経路衝突評価値計算部、及び
複数の移動体の時系列経路候補の組み合わせについて、前記経路割当評価値、前記移動距離評価値、及び前記経路衝突評価値の合計値を比較することで、複数の移動体の時系列経路の組み合わせを最適候補として推定する評価値比較部、
として機能させる経路推定プログラム。
【請求項９】
複数の移動体の最適経路を推定する経路推定方法であって、
前記複数の移動体の各々について、最短経路の時系列経路候補を生成する最短経路生成ステップと、
前記複数の移動体の各々について、迂回経路の時系列経路候補を生成する迂回経路生成ステップと、
前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の経路割当評価値を計算する経路割当評価値計算ステップと、
前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の移動距離評価値を計算する移動距離評価値計算ステップと、
前記複数の移動体の各々の前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の組み合わせの経路衝突評価値を計算する経路衝突評価値計算ステップと、
複数の移動体の時系列経路候補の組み合わせについて、前記経路割当評価値、前記移動距離評価値、及び前記経路衝突評価値の合計値を比較することで、複数の移動体の時系列経路の組み合わせを最適候補として推定する評価値比較ステップと、
を含む経路推定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の移動体が同時に移動する場合の経路を推定する経路推定システム、経路推定方法、及び経路推定プログラムに関する。
【背景技術】
【０００２】
複数の移動体が同時に移動する場合の各移動体の最適経路を推定する経路推定システムが知られている。この経路推定システムは、例えば、工場内で自律走行する複数のロボットについて、互いに衝突することなくより早く各々の目的地に到達できるように各ロボットの移動経路を求めるシステムといて応用される。
【０００３】
特許文献１には、複数ロボットに全体として最小コストでタスクを実行させることにより、複数のロボットの行動を最適化できるロボット制御装置が開示されている。このロボット制御装置では、複数のロボットが移動中に出会う（衝突する）可能性を判定して出会起因コストを求め、出会起因コストと移動計画実行コストとの和が小さいプランを実行する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−３２６７０３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、距離の最小化を考慮し、最短経路のみを選ぶ方法には問題がある。即ち、最短経路がある移動体によって専有されている場合、当該経路を通る他の移動体は一時停止する必要があるが、この一時停止する時間が長い場合には、最短経路を選択しても必ずしも所要時間が最小にならないことがある。
【０００６】
図１４は、最短経路が最小コストとならない場合の例を示す図である。いま、複数のロボットＡ〜Ｄをいずれも開始点１から目的地７に移動させることを考える。ロボットＡ〜Ｄにとって、最短経路は、いずれも［１  ２  ３  ６  ７］であり、この経路の距離コストは４である。開始点１から目的地７までは、迂回経路［４  ８  ９  １０  １１  ７］を通ることもできるが、この経路の距離コストは６である。
【０００７】
図１５は、図１４の例において距離コストを最小化する移動を示す図である。距離コストの最小化を考慮すると、図１５に示すように、ロボットＡ〜Ｄはいずれも最短経路［１  ２  ３  ６  ７］を選択することになる。この場合には、以下の手順でロボットＡ〜Ｄの移動制御が行われる。
（１）１台目のロボットＡは最短経路を選択し、２〜４台目のロボットＢ〜Ｄは一時停止を選択する。
（２）１台目のロボットＡ及び２台目のロボットＢは最短経路を選択し、３台目のロボットＣ及び４台目のロボットＤは一時停止を選択する。
（３）１〜３台目のロボットＡ〜Ｃは最短経路を選択し、４台目のロボットＤは一時停止を選択する。
（４）ロボットＡ〜Ｄがいずれも最短経路を選択する。
【０００８】
上記の手順によって分かるとおり、２台目以降のロボットＢ〜Ｄには一時停止が発生する。一時停止によるコストを停止コストとして、距離コストと時間コストの合計を移動コストとすると、ロボットＡ〜Ｄの移動コストは以下のとおりとなる。
ロボットＡ：距離コスト４＋停止コスト０＝移動コスト４
ロボットＢ：距離コスト４＋停止コスト１＝移動コスト５
ロボットＣ：距離コスト４＋停止コスト２＝移動コスト６
ロボットＤ：距離コスト４＋停止コスト３＝移動コスト７
よって、ロボットＡ〜Ｄの全体の移動コストは、４＋５＋６＋７＝２２となる。
【０００９】
図１６は、図１４の例において迂回経路を利用する場合の移動を示す図である。この例では、ロボットＤが迂回経路を選択する。具体的には、以下の手順でロボットＡ〜Ｄの移動制御が行われる。
（１）１台目のロボットＡは最短経路を選択し、２台目のロボットＢ及び３台目のロボットＣは一時停止を選択し、４台目のロボットＤは迂回経路を選択する。
（２）１台目のロボットＡ及び２台目のロボットＢは最短経路を選択し、３台目のロボットＣは一時停止を選択し、４台目のロボットＤは迂回経路を選択する。
（３）１〜３台目のロボットＡ〜Ｃは最短経路を選択し、４台目のロボットＤは迂回経路を選択する。
【００１０】
この手順によれば、ロボットＡ〜Ｄの移動コストは以下のとおりとなる。
ロボットＡ：距離コスト４＋停止コスト０＝移動コスト４
ロボットＢ：距離コスト４＋停止コスト１＝移動コスト５
ロボットＣ：距離コスト４＋停止コスト２＝移動コスト６
ロボットＤ：距離コスト６＋停止コスト０＝移動コスト６
よって、ロボットＡ〜Ｄの全体の移動コストは、４＋５＋６＋６＝２１となり、最短経路のみを通る図１５の例よりも全体の移動コストは小さくなる。
【００１１】
そこで、本発明は、複数の移動体の経路について、迂回経路も含む最適な経路を推定することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の一態様の経路推定システムは、複数の移動体の最適経路を推定する経路推定システム（１）であって、前記複数の移動体の各々について、最短経路の時系列経路候補を生成する最短経路生成部（３４）と、前記複数の移動体の各々について、迂回経路の時系列経路候補を生成する迂回経路生成部（３５）と、前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の経路割当評価値を計算する経路割当評価値計算部（３６）と、前記複数の移動体の各々について、前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の移動距離評価値を計算する移動距離評価値計算部（３７）と、前記複数の移動体の各々の前記最短経路の時系列経路候補及び前記迂回経路の時系列経路候補の組み合わせの経路衝突評価値を計算する経路衝突評価値計算部（３８）と、複数の移動体の時系列経路候補の組み合わせについて、前記経路割当評価値、前記移動距離評価値、及び前記経路衝突評価値の合計値を比較することで、複数の移動体の時系列経路の組み合わせを最適候補として推定する評価値比較部（３９）とを備えた構成を有している。
【００１３】
この構成により、経路割当評価値計算部、移動距離評価値計算部、及び経路衝突評価値計算部は、最短経路だけでなく迂回経路も含めて、各評価値を計算して、評価値比較部が迂回経路の評価値も含めて評価値の合計値を比較して最適候補を推定するので、迂回経路も含む最適な経路を推定できる。
【発明の効果】
【００１４】
本発明によれば、最短経路だけでなく迂回経路も含めて各評価値を計算して、最短経路の評価値だけでなく迂回経路の評価値も含めて評価値の合計値を比較して最適候補を推定するので、迂回経路も含む最適な経路を推定できる。
【図面の簡単な説明】
【００１５】
【図１】図１は、本発明の実施の形態の経路推定システムを含むロボット制御システムの利用状況を示す図である。
【図２】図２は、本発明の実施の形態の地図データと最短経路の例を示す図である。
【図３】図３は、図２の例における時系列候補列を示す図である。
【図４】図４は、本発明の実施の形態の第１移動体の経路の例を示す図である。
【図５】図５は、本発明の実施の形態の経路割当評価値の例を示す図である。
【図６】図６は、本発明の実施の形態の移動距離評価値の例を示す図である。
【図７】図７は、本発明の実施の形態の第１移動体及び第２移動体の経路の例を示す図である。
【図８】図８は、本発明の実施の形態の経路衝突評価値の例を示す図である。
【図９】図９は、本発明の実施の形態の合計評価値の例を示す図である。
【図１０】図１０は、本発明の実施の形態の経路推定方法のフローチャートである。
【図１１】図１１は、本発明の実施の形態の変形例１における重複がない複数の経路を示している。
【図１２】図１２は、本発明の実施の形態の変形例１における重複がある複数の経路を示している。
【図１３】図１３は、本発明の実施の形態の変形例２における移動体に優先順位に応じた係数を設定した場合の距離コストの計算結果の例を示している。
【図１４】図１４は、最短経路が最小コストとならない場合の例を示す図である。
【図１５】図１５は、図１４の例において距離コストを最小化する移動を示す図である。
【図１６】図１６は、図１４の例において迂回経路を利用する場合の移動を示す図である。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下に説明する実施の形態は、本発明を実施する場合の一例を示すものであって、本発明を以下に説明する具体的構成に限定するものではない。本発明の実施にあたっては、実施の形態に応じた具体的構成が適宜採用されてよい。
【００１７】
図１は、本発明の実施の形態のロボット制御システムの構成を示すブロック図である。ロボット制御システム１は、複数の移動体２と経路推定システム３とからなる。移動体２及び経路推定システム３は、図示は省略するがそれぞれ無線通信機能を有し、各移動体２と経路推定システム３とは、互いに無線通信が可能である。
【００１８】
移動体２は、経路推定システム３によって経路を推定する対象である。移動体２は、図示は省略するが、移動をするための機構を備えている。移動体２が作業車両である場合には、移動をするための機構として、車輪及び車両駆動機構等を備えている。図１の例では、複数の移動体２として、第１移動体２Ａ及び第２移動体２Ｂが示されており、以下の説明でも、説明を簡略化するために２つの移動体がある場合について、その最適経路の推定を説明するが、移動体２は３つ以上であってもよい。
【００１９】
経路推定システム３は、複数の移動体２を同時に移動させる場合の各移動体２の最適経路を推定する。移動体２は、経路推定システム３が推定した経路に従って移動する。このロボット制御システム１は、例えば、倉庫内において複数の移動体２が経路推定システム３によって推定した最適経路に従って移動することで荷物をピックアップするシステムとして応用が可能である。
【００２０】
経路推定システム３は、地図データメモリ３１、目的地データメモリ３２、及び位置データメモリ３３を備えている。地図データメモリ３１は、経路推定システム３が経路を推定する領域の地図データを記憶している。地図データは、ノード、及びノードを結ぶリンクの情報を含み、各リンクには方向が定義されている。方向は、ノードからノードへの両方向であっても、一方のノードから他方のノードへの片方向であってもよい。
【００２１】
目的地データメモリ３２は、各移動体２について目的地として設定されたノードを記憶している。目的地は各移動体２にて設定されて、経路推定システム３は、移動体２にて設定された目的地の情報を受けて、移動体２ごとに目的地データメモリ３２に目的地を設定する。なお、各移動体２の目的地は、移動体２の移動を計画する他のシステムによって設定されて経路推定システム３に伝えられてもよい。例えば、移動体２が倉庫内において荷物を搬送するシステムである場合には、荷物の搬送を計画するシステムにて各移動体の目的地が決定されて、経路推定システム３に伝達されてよく、あるいは、経路推定システム３字体が移動体の移動を計画する機能を備えていてよい。
【００２２】
位置データメモリ３３は、各移動体２の現在位置を記憶している。現在位置は各移動体２にて測定されて、経路推定システム３は、移動体２にて測定された現在位置の情報を受けて、移動体２ごとに位置データメモリ３３に現在位置を記憶する。なお、移動体２の現在位置の情報は、外部のセンサ（例えば、カメラ）によって取得されて経路推定システム３に送信されてもよい。
【００２３】
経路推定システム３は、更に、最短経路生成部３４と、迂回経路生成部３５とを備えている。最短経路生成部３４は、各移動体２について、目的地データメモリ３２から目的地を読み出し、位置データメモリ３３から現在位置を開始点として読み出し、地図データメモリ３１に記憶された地図上に目的地と開始点を設定して、開始点から目的地までの最短経路を求める。この際に、最短経路生成部３４は、地図データにあるリンクの方向も考慮して、進行可能な方向のみを選択する。最短経路は、距離が最も短い経路、即ち距離コストが最も小さい経路である。
【００２４】
最短経路生成部３４は、最短経路について、時系列位置を含んだ時系列経路候補を生成する。具体的には、最短経路生成部３４は、所定数の時間スロットについて、次のノードに進むか、そこで停止するかを選択することで、最短経路上の進み方のすべてのパターンを生成する。ここで、時間スロットとは、移動体が１つのリンクを進むのに要するものとして設定された時間である。各時間スロットについて、進む／停止するのいずれかを選択することで、時間スロットをｎとすると、２のｎ乗とおりの時系列経路の候補が得られる。時系列経路とは、所定の時間スロット数において、進む／停止を選択することで、各時間スロットの位置を示したノード列である。
【００２５】
図２は、地図データと最短経路の例を示す図である。また、図３は、図２の例における時系列候補列を示す図である。図２及び図３の例では、地図データはノード１〜９を含み、第１移動体２Ａの開始点はノード１であり、第１移動体２Ａの目的地はノード９であり、第２移動体２Ｂの開始点はノード３である。第１移動体２Ａの最短経路は、ノード１、２、５、８、９をこの順に経由する経路である。また、第２移動体２Ｂの最短経路は、ノード３、２、５、８、９をこの順に経由する経路である。
【００２６】
時間スロットを４としたとき、第１移動体２Ａ及び第２移動体２Ｂの最短経路の時系列経路候補は、それぞれ図３に示すとおりである。最短経路生成部３４は、第１移動体２Ａの最短経路について、時間スロット４の時系列経路候補として、経路１Ａ〜経路１６Ａを生成し、第２移動体２Ｂの最短経路について、時間スロット４の時系列経路候補として、経路１Ｂ〜経路１６Ｂを生成する。
【００２７】
迂回経路生成部３５は、開始点から目的地までの最短経路以外の経路（迂回経路）を求める。迂回経路の数が多くなりすぎることもあり得るので、迂回経路生成部３５は、距離コストが小さい順に所定の数の迂回経路を求める。
【００２８】
迂回経路生成部３５は、求めた複数の迂回経路のそれぞれについて、最短経路生成部３４と同様にして、時系列経路候補を生成する。その結果、各迂回経路について、図３と同様にして第１移動体２Ａ及び第２移動体２Ｂの時系列候補が得られる。
【００２９】
経路推定システム３は、更に、経路割当評価値計算部３６、移動距離評価値計算部３７、及び経路衝突評価値計算部３８を備えている。これらの計算部は、量子コンピュータ等のイジング最適化計算機が所定のプログラムを実行することで実現される。
【００３０】
経路割当評価値計算部３６は、各移動体２について、時系列経路候補（以下単に「経路」ともいう。）を読み出して、選択した経路割当についての評価値を出力する。経路割当評価値計算部３６は、最短経路生成部３４から読み出した最短経路の時系列経路候補について経路割当評価値を計算し、迂回経路生成部３５から読み出した各迂回経路について経路割当評価値を計算する。ここで、経路割当評価値は、経路最適化のための評価値の１つであり、各移動体２に１つの経路のみを割り当てるために、１つの経路のみを選択した場合に最小となる評価値である。
【００３１】
図４は、第１移動体２Ａの経路の例を示す図である。図５は、経路割当の評価値（以下、「割当コスト」、あるいは単に「コスト」ともいう。）の例を示す図である。図５の例では、時系列経路候補として、経路１Ａ［１１１１１］、経路２Ａ［１２２２２］、経路３［１２５５５］、経路４［１２５８８］、経路５［１２５８９］の５つの経路が得られている場合の例を示している。図５において、各径路について「１」は当該経路を選択することを意味し、「０」は当該経路を選択しないことを意味する。図５（ａ）は、割当コストが最小になる場合の例を示しており、図５（ｂ）は、割当コストが最小にならない場合の例を示している。
【００３２】
経路割当評価値計算部３６は、式（１）に示すように、イジングモデルのコスト関数を用いて経路割当評価値を計算する。具体的には、経路割当評価値計算部３６は、各移動体ｉに対して、経路のセット（ｘ，ｓ）から１つの経路のみを選択するとコスト０（最小）となるコスト関数を用いる。ここで、ｘは移動体の座標であり、ｓは移動体のタスク、即ち開始点から目的地までの移動である。
【数１】
2020046384.tif 000003
【００３３】
図５（ａ）の例では、経路５Ａのみが選択されているのでコストは最小の０となり、図５（ｂ）の例では、経路１Ａ、３Ａ、及び５Ａが選択されているのでコストは０より大きい４となる。なお、式（１）に十分に大きな係数をかけることで、複数の経路を選択した場合のコストをより大きくしてもよい。また、図５の例では、５つの時系列経路候補が得られている場合の例を示しているが、図２及び図３の例では１６の時系列候補が得られているので、経路割当評価値計算部３６は、これらの１６の経路について、選択する「１」及び選択しない「０」のすべての組み合わせについて、式（１）を用いて経路割当評価値を計算する。
【００３４】
移動距離評価値計算部３７は、各移動体２について、時系列経路候補を読み出して、選択した経路距離についての評価値を出力する。移動距離評価値計算部３７は、最短経路生成部３４から読み出した最短経路の時系列経路候補について移動距離評価値を計算し、迂回経路生成部３５から読み出した各迂回経路について移動距離評価値を計算する。ここで、移動距離評価値は、経路最適化のための評価値の１つであり、各移動体２の移動距離が遠い経路を選ぶために、移動距離が最長のものを０として、移動距離が最長より短い場合にはマイナスになる評価値である。
【００３５】
図６は、移動距離の評価値（以下、「距離コスト」、あるいは単に「コスト」ともいう。）の例を示す図である。図６の例でも、図５と同様に、第１移動体２Ａの時系列経路候補として、経路１Ａ［１１１１１］、経路２Ａ［１２２２２］、経路３Ａ［１２５５５］、経路４Ａ［１２５８８］、経路５Ａ［１２５８９］の５つが得られている場合の例を示している。図５において、各径路について「１」は当該経路を選択することを意味し、「０」は当該経路を選択しないことを意味する。図６（ａ）は、距離コストが最小になる場合の例を示しており、図６（ｂ）は、距離コストが最小にならない場合の例を示している。
【００３６】
移動距離評価値計算部３７は、イジングモデルのコスト関数を用いて移動距離評価値を計算する。具体的には、移動距離評価値計算部３７は、最短経路については、各移動体ｉに対して、経路のセット（ｘ，ｓ）から距離ｄの経路を選択すると、距離コスト−ｄとなるコスト関数を用いる。ｄが大きいほど距離コストは低下することになる。
【００３７】
移動距離評価値計算部３７は、迂回経路については、最短経路との差分距離コストΔｄをコスト−ｄに加える。これにより、コスト−ｄは正の値に近くなり、距離コストは増加する。
【００３８】
移動距離評価値計算部３７は、最短経路については、式（２）のコスト関数を用いて距離コストを計算する。ここで、式（１）と同様に、ｘは移動体の座標であり、ｓは移動体のタスク、即ち開始点から目的地までの移動である。
【数２】
2020046384.tif 000004
【００３９】
移動距離評価値計算部３７は、迂回経路については、式（３）のコスト関数を用いて距離コストを計算する。即ち、移動距離評価値計算部３７は、迂回経路については、距離コストを計算する場合に、距離評価値補正を加える。
【数３】
2020046384.tif 000005
【００４０】
図６（ａ）の例では、経路５Ａのみが選択されているのでコストは最小の−４となり、図６（ｂ）の例では、経路１Ａのみが選択されているのでコストは−４より大きい０となる。なお、図６では、５つの時系列経路候補が得られている場合の例を示しているが、図２及び図３の例では１６の時系列候補が得られているので、経路割当評価値計算部３６は、これらの１６の経路の選択する「１」及び選択しない「０」のすべての組み合わせについて、式（２）及び式（３）を用いて移動距離評価値を計算する。
【００４１】
経路衝突評価値計算部３８は、各移動体について、時系列経路候補を読み出して、選択した経路衝突についての評価値を出力する。経路衝突評価値計算部３８は、最短経路生成部３４から読み出した最短経路の時系列経路候補について経路衝突評価値を計算し、迂回経路生成部３５から読み出した各迂回経路について経路衝突評価値を計算する。ここで、経路衝突評価値は、経路最適化のための評価値の１つであり、各移動体２が同時に同じ経路を通らないようにするために、衝突がない場合を０として、衝突がある場合には１以上になる評価値である。
【００４２】
図７は、第１移動体２Ａ及び第２移動体２Ｂの経路の例を示す図である。図８は、経路衝突の評価値（以下、「衝突コスト」、あるいは単に「コスト」ともいう。）の例を示す図である。図８の例では、第１移動体２Ａの時系列経路候補として、経路１Ａ［１１１１１］、経路２Ａ［１２２２２］、経路３Ａ［１２５５５］、経路４Ａ［１２５８８］、経路５Ａ［１２５８９］の５つの経路が得られており、第２移動体２Ｂの時系列経路候補として、経路１Ｂ［３３３３３］、経路２Ｂ［３２２２２］、経路３Ｂ［３２５５５］、経路４Ｂ［３２５８８］、経路５Ｂ［３２５８９］が得られている場合の例を示している。図８において、各径路について「１」は当該経路を選択することを意味しており、「０」は当該経路を選択しないことを意味する。図８（ａ）は、衝突コストが最小になる場合（即ち、衝突しない場合）の例を示しており、図８（ｂ）は、衝突コストが最小にならない場合（即ち、衝突が生じる場合）の例を示している。
【００４３】
経路衝突評価値計算部３８は、式（４）に示すように、イジングモデルのコスト関数を用いて経路衝突評価値を計算する。具体的には、経路衝突評価値県産部３８は、各移動体ｉに対して、経路のセット（ｘ，ｓ）から経路を選んだ場合の重なりコストを計算する。ここで、ｘは移動体の座標であり、ｓは移動体のタスク、即ち開始点から目的地までの移動である。
【数４】
2020046384.tif 000006
【００４４】
図８（ａ）の例では、第１移動体２Ａについて経路５Ａのみが選択され、第２移動体２Ｂについて経路１Ａのみが選択されているので、衝突コストは最小の０となり、図８（ｂ）の例では、第１移動体２Ａについて経路５Ａが選択され、第２移動体２Ｂについて経路５Ｂ経路１Ｂが選択されているので、衝突コストは第１移動体２Ａ及び第２移動体２Ｂのそれぞれについて０より大きい１となる。なお、式（４）に十分に大きな係数をかけることで、衝突が生じる場合のコストをより大きくしてもよい。また、図８の例では、４つの時系列経路候補が得られている場合の例を示しているが、図２及び図３の例では１６の時系列候補が得られているので、経路衝突評価値計算部３８は、これらの１６の経路について、選択する「１」及び選択しない「０」のすべての組み合わせについて、式（４）を用いて経路衝突評価値を計算する。
【００４５】
経路推定システム３は、更に、評価値比較部３９、及び最適経路出力部４０を備えている。評価値比較部３９は、経路選択の組み合わせに対する、経路割当評価値（即ち、割当コスト）、経路距離評価値（即ち、距離コスト）、経路衝突評価値（即ち、衝突コスト）の合計値である合計評価値（以下、「合計コスト」ともいう。）が最小となる各移動体の時系列経路を出力する。
【００４６】
図９は、合計評価値の例を示す図である。図９には、第１移動体２Ａが経路５のみを選択し、第２移動体２Ｂが経路１のみを選択したときの合計評価値を示しており、合計評価値は−４となっている。移動体２の台数がｎ台、時系列経路の候補数がｋ個の場合には、２ｎ×ｋ個の合計評価値が得られることになる。したがって、移動体の台数や時系列経路の候補数等の変数が増えたときに、爆発的に組み合わせが増えるため、量子コンピュータ等のイジング最適化計算機を用いてもよい。
【００４７】
評価値比較部３９は、得られた複数の合計評価値を互いに比較して、最小の合計評価値となる時系列経路の組み合わせを選択する。
【００４８】
最適経路出力部４０は、評価値比較部３９で選択された、合計評価値が最小の時系列経路の組み合わせを、推定された最適経路として各移動体２に出力する。
【００４９】
図１に示すように、各移動体２は、目的地設定部２１、位置測定部２２、及び運動制御部２３を備えている。目的地設定部２１は、目的地即ち、移動体２の移動先を設定し、設定された目的地を経路推定システム３に送信する。経路推定システム３は、各移動体２から送信されてきた各移動体２の目的地を受信して、目的地データメモリ３２に記憶する。なお、上述のとおり、目的地は移動体２以外のシステムが決定してもよい。
【００５０】
位置測定部２２は、移動体２の現在位置を測定して、位置情報を生成する。位置測定部２２は、ＧＰＳを用いて位置を測定する。位置測定部２２は、移動体２の現在位置を測定して、測定した現在位置の情報を経路推定システム３に送信する。経路推定システム３は、各移動体２から送信されてきた各移動体２の現在位置の位情報を受信して、位置データメモリ３３に記憶する。なお、上述のとおり、各移動体２の現在位置は外部のセンサによって測定されてもよい。
【００５１】
運動制御部２３は、移動体２の移動機構を駆動することで移動体２を移動させる。運動制御部２３は、経路推定システム３で推定され、最適経路出力部４０から送信された最適経路を受信して、この最適経路に含まれる当該移動体２の時系列経路にしたがって、移動機構を駆動する。移動体２は、運動制御部２３によって移動機構を制御することで、所定の時間スロット数における最適経路に従って移動する。
【００５２】
図１０は、本発明の実施の形態の経路推定方法のフローチャートである。まず、経路推定システム３は、すべての移動体２の目的地を目的地データメモリ３２に設定し、すべての移動体２の現在位置を位置データメモリ３３に設定する（ステップＳ１０１）。次に、最短経路生成部３４が各移動体２の最短経路の時系列経路候補を生成し、迂回経路生成部３５が各移動体の各迂回経路の時系列経路候補を生成する（ステップＳ１０２）。
【００５３】
次に、経路割当評価部３６は各時系列経路候補の経路割当評価値を計算し、移動距離評価値計算部３７は各時系列経路候補の移動距離評価値を計算し、経路衝突評価値計算部３８は複数の移動体２の各時系列経路候補の組み合わせの経路衝突評価値を計算する（ステップＳ１０３）。そして、評価比較部３９は、経路割当評価値、移動距離評価値、及び経路衝突評価値を合計することで、複数の移動体２の各時系列経路候補の組み合わせの合計評価値を計算して、互いに比較し、合計評価値が最小の時系列経路候補の組み合わせを最適経路として推定する（ステップＳ１０４）。
【００５４】
最適経路出力部４０は、評価比較部３９にて最適経路として決定された経路を各移動体２に対して送信する（ステップＳ１０５）。各移動体２は、この最適経路を経路推定システム３から受信して、それに従って運動制御部２３が移動体２の移動機構を駆動して、移動体２を最適経路に従って移動させる。
【００５５】
以上のように、本発明の実施の形態の経路推定システム３及びそれを含むロボット制御システム１は、最短経路が必ずしも最適経路にならないことを前提として、最短経路生成部３４にて最短経路についての時系列経路候補列を生成するだけでなく、迂回経路生成部３５にて最短ではない迂回経路についての時系列経路候補列も生成する。そして、最短経路だけでなく迂回経路についてもコストを計算して互いに比較をするので、迂回経路の方がコストが小さくなる場合には、迂回経路が選択される。これによって、迂回経路も含めた最適経路を求めることができ、最短経路のみで最適経路を求めるよりもよりコストの小さい経路を最適経路として求めることができる。
【００５６】
また、最短経路生成部３４及び迂回経路生成部３５は、所定の時間スロット数の移動体２の進む／止まるの組み合わせからなる時系列経路候補列を生成し、経路割当評価値計算部３６、移動距離評価値計算部３７、経路衝突評価値計算部３８は、すべての時系列経路候補、又は複数の移動体２の時系列経路候補のすべての組み合わせについて、各コストを計算する。移動体２の台数が大きくなり、時間スロット数が大きくなると、これらのコストを計算するための計算量が膨大になるが、これらの経路割当評価値計算部３６、移動距離評価値計算部３７、及び経路衝突評価値計算部３８を量子コンピュータ等のイジング最適化計算機で行うことで、高速に計算を行うことができる。
【００５７】
また、評価比較部３９もすべての移動体２の時系列経路の組み合わせの合計評価値を計算するため、移動体２の台数や時間スロット数が大きくなると、指数関数的に計算量が多くなる。そこで、この評価比較部３９にも量子コンピュータ等のイジング最適化計算機を採用することで、高速に計算を行うことができる。
【００５８】
（変形例１）
経路推定システム３は、最短経路生成部３４が、複数の移動体２の最短経路を求めた際に、当該最短経路に重複がない場合には、それらの最短経路をそのまま採用して最適経路としてもよい。また、最短経路に重複がある場合において、迂回経路生成部３５は、迂回経路において複数の移動体２の迂回経路に重複がない場合には、経路推定システム３は、当該迂回経路をそのまま採用して最適経路としてもよい。
【００５９】
図１１は、重複がない複数の経路を示しており、図１２は、重複がある複数の経路を示している。最短経路生成部３４及び迂回経路生成部３５は、経路が重複した場合にのみ最短経路及び迂回経路の時系列経路候補列を生成し、経路割当評価値計算部３６、移動距離評価値計算部３７、及び経路衝突評価値計算部３８は、複数の移動体２の経路が重複する場合にのみ当該経路の時系列経路候補の各評価値を計算する。
【００６０】
図１１の例では、図１１（ａ）のように、第１移動体２Ａの開始点はノード１であり、目的地はノード７である。また、図１１（ｂ）のように、第２移動体２Ｂの開始点はノード３であり、目的地はノード９である。この場合には、第１移動体２Ａの最短経路は［１２５８７］であり、第２移動体２Ｂの最短経路は［３６９−−］であり、これらの経路は重複しない。よって、これらの最短経路がそのまま最適経路として決定される。
【００６１】
図１２の例では、図１２（ａ）のように、第１移動体２Ａの開始点はノード１であり、目的地はノード９である。また、図１２（ｂ）のように、第２移動体２Ｂの開始点はノード３であり、目的地はノード９である。この場合には、第１移動体の２Ａの最短経路は［１２５８９］であり、第２移動体２Ｂの最短経路は［３６５８９］であり、これらの経路は、［−−５８９］で重複している。よって、最短経路生成部３４は、これらの経路について時系列経路候補列を作成し、経路割当評価値計算部３６、移動距離評価値計算部３７、及び経路衝突評価値計算部３８は、上述したように各評価値を計算する。
【００６２】
このように、最短経路生成部３４及び迂回経路生成部３５において生成した複数の移動体２の経路が互いに重複しない場合には、それらの経路を直ちに最適経路として決定することで、最適経路を推定するための計算負荷を軽減でき、高速に最適経路を推定できる。
【００６３】
（変形例２）
移動距離評価計算部３７は、各移動体２について、優先順位を設定して、優先順位の高い移動体２の移動距離評価値が小さくなるように、式（２）及び式（３）において、移動体２ごと優先順位に応じて異なる係数を設定する。
【００６４】
図１３は、各移動体２に優先順位に応じた係数を設定した場合の距離コストの計算結果の例を示している。この例では、第１移動体２Ａの優先順位は第２移動体２Ｂの優先順位より高く、よって、係数は、第１移動体２Ａには０．９と設定されており、第２移動体２Ｂにはそれより小さい０．５と設定されている。
【００６５】
その結果、図１３（ａ）の場合には、もともと第１移動体２Ａの距離コストが−３であり、第２移動体２Ｂの距離コストが−２であって、第１移動体２Ａの方が距離コストが小さく、それぞれ係数０．９及び係数０．５をかけても距離コストの大小関係は変わらないが、図１３（ｂ）の場合には、もともと第１移動体２Ａの距離コストが−２であり、第２移動体２Ｂの距離コストが−３であって、第２移動体２Ｂの方が距離コストが小さいが、それぞれ係数０．９及び係数０．５をかけることで、第１移動体２Ａの距離コストは−１．８となり、第２移動体２Ｂの距離コストは−１．５となり、第１位移動体２Ａの距離コストの方が小さくなる。
【００６６】
これにより、優先順位が高い移動体２が優先順位の低い移動体に阻害されにくくなり、優先的にタスクを実行できるようになる。
【００６７】
（変形例３）
評価比較部３９は、合計評価値を比較した結果、最もコストの低い複数の移動体の時系列経路の組み合わせが複数ある場合には、優先順位が高い移動体の距離コストが最も小さい時系列経路の組み合わせを最適経路として推定してよい。優先順位は複数の移動体２についてあらかじめ決められており、評価比較部３９に記憶されていてよい。
【００６８】
この結果、合計評価値が同じ複数の時系列経路の組み合わせがある場合には、優先順位が高い移動体２がより目的地に近づく経路が最適経路として推定される。よって、優先順位の高い移動体２のタスクが優先されることになる。
【産業上の利用可能性】
【００６９】
以上のように、本発明は、複数の移動体の経路について、迂回経路も含む最適な経路を推定できるという効果を有し、経路推定システム等として有用である。
【符号の説明】
【００７０】
１：ロボット制御システム、２：移動体、２Ａ：第１移動体、２Ｂ：第２移動体、３：経路推定システム、２１：目的地設定部、２２：位置測定部、２３：運動制御部、３１：地図データメモリ、３２：目的地データメモリ、３３：位置データメモリ、３４：最短経路生成部、３５：迂回経路生成部、３６：経路割当評価値計算部、３７：移動距離評価値計算部、３８：経路衝突評価値計算部、３９：評価値比較部、４０：最適経路出力部
【図１】
2020046384.tif 000007
【図２】
2020046384.tif 000008
【図３】
2020046384.tif 000009
【図４】
2020046384.tif 000010
【図５】
2020046384.tif 000011
【図６】
2020046384.tif 000012
【図７】
2020046384.tif 000013
【図８】
2020046384.tif 000014
【図９】
2020046384.tif 000015
【図１０】
2020046384.tif 000016
【図１１】
2020046384.tif 000017
【図１２】
2020046384.tif 000018
【図１３】
2020046384.tif 000019
【図１４】
2020046384.tif 000020
【図１５】
2020046384.tif 000021
【図１６】
2020046384.tif 000022