JP2023072447A - 移動体制御装置 - Google Patents

Abstract

【課題】移動体のお互いの干渉を回避しつつ、全体の効率を最適化することができる移動体制御装置を提供する。【解決手段】移動制御システム１００では、経路は２つの移動体がすれ違えないので、移動経路が交錯する場合には、ＡＧＶ３０の衝突を避けるために、一方のＡＧＶ３０を待機させて、他方のＡＧＶ３０を移動させた後に、一方のＡＧＶ３０を移動させる必要がある。そこで混合整数計画問題の制約条件に衝突禁止条件を用いて、移動体の衝突を避けつつ、評価値を最小化する搬送スケジュールを計算する。また搬送工程は、特定経路に１つのＡＧＶ３０が存在すると、他のＡＧＶ３０が特定経路に進入することができない工程である。このような混合整数計画問題を解くことによって搬送スケジュールを決定するので、ＡＧＶ３０のお互いの干渉を回避しつつ、全体の効率を最適化することができる。【選択図】図１

Description

この明細書における開示は、移動体の移動を制御する移動体制御装置に関する。

複数の移動体、たとえば自動無人搬送車（ＡＧＶ：Automated Guided Vehicle）を制御する場合、各ＡＧＶの移動スケジュールを適切に設定しなければ、ＡＧＶ間で衝突するおそれがある。したがって、ＡＧＶ間の衝突を回避した移動スケジュールを設定する必要がある。従来、このような移動スケジュールを設定するためには、複数の目的地への巡回路の計画問題、すなわち最短路問題に代表される巡回経路長の最小化問題として取り扱われてきた。

また複数のＡＧＶを制御するシステムは、全てのＡＧＶの位置を一つのホストコンピュータを用いて管理し、全てのＡＧＶを同時に考慮して経路計画を実行する集中型の経路計画システムを基本としている。例えば、複数のＡＧＶに対して、現在地から目的地までの経路候補を木構造で表現し、ＡＧＶ間で衝突が生じないかどうかを逐次チェックしながら、探索木を登録、削除し、全てのＡＧＶの動作を一括して探索するという集中型経路計画法がある。

このような集中型経路計画法では、経路計画対象となるＡＧＶ台数が増加したとき、可能な経路の候補が膨大となるため、最適な経路を短時間で探索することが困難である。そこで特許文献１に記載の分散型経路計画装置では、ＡＧＶが互いに通信して、各ＡＧＶがそれぞれ経路計画を計算することで、計算負荷を分散している。

特開２００４－２８０２１３号公報

特許文献１に記載の装置では、ＡＧＶ同士の干渉を回避するために、経路における全ての干渉を発見して、各ＡＧＶにおいて回避計画計算を繰り返す必要がある。負荷は分散されているが、回避のための計算を繰り返す必要があり、合計の計算負荷が高いという問題がある。さらに最終的に得られる経路計画、すなわち移動スケジュールは、干渉を回避することを優先しているので、効率が良い最適な移動スケジュールでないおそれがある。

そこで、開示される目的は前述の問題点を鑑みてなされたものであり、移動体のお互いの干渉を回避しつつ、全体の効率を最適化することができる移動体制御装置を提供することを目的とする。

本開示は前述の目的を達成するために以下の技術的手段を採用する。

ここに開示された移動体制御装置は、経路上を移動する複数の移動体（３０）の移動を制御する移動体制御装置であって、経路は、２つの移動体がすれ違えない経路であり、複数の移動体の出発地点と終着地点とを結ぶ移動経路、および移動経路を移動する移動工程を設定する設定部（１４１）と、移動経路および移動工程を入力値して、制約条件を満たしつつ所定の評価値を最小化することを目的とする混合整数計画問題を解くことによって、移動体の移動スケジュールを計算する計算部（１４４）と、移動スケジュールによって各移動体の移動を制御する移動制御部（１４５）と、を含み、制約条件には、経路を少なくとも移動体よりも大きい長さで分割した分割経路において、移動体が次の分割経路への移動が完了するまで、移動が完了前の分割経路は他の移動体による利用を禁止する衝突禁止条件があり、設定部は、少なくとも２つの移動体の移動経路が重複して、移動体の移動方向が対向することによって、移動体が干渉する可能性がある特定経路では、特定経路に１つの移動体が存在する場合には、移動体が存在する特定経路では他の移動体の使用を禁止するように移動工程を設定する。

このような移動体制御装置に従えば、経路は２つの移動体がすれ違えないので、移動経路が交錯する場合には、移動体の衝突を避けるために、一方の移動体を待機させて、他方の移動体を移動させた後に、一方の移動体を移動させる必要がある。そこで混合整数計画問題の制約条件に衝突禁止条件を用いて、移動体の衝突を避けつつ、評価値を最小化する移動スケジュールを計算する。評価値は、たとえば全ての移動体の移動が完了するまでの時間、全ての移動体の移動時間の総和、移動体の待機時間の総和などである。また混合整数計画問題を解くことによって移動スケジュールを決定するので、複数回計算を繰り返すことを抑制することができる。

さらに設定部は、移動体が存在する特定経路では、他の移動体が特定経路を使用することを禁止するので、特定経路に１つの移動体が存在すると、他の移動体が特定経路に進入することができない。たとえば隣接する分割経路に移動体がそれぞれ配置され、互いに位置が入れ替わることを想定する。この場合、移動前も入れ替わり移動後も、１つの分割経路には、１つの移動体が配置され、１つの分割経路に２つの移動体は配置されていないので、字面上では衝突はおきていない。しかし、実際に分割経路を移動する移動体では、経路ではすれ違えないので、衝突せずに入れ替わることはできない。このように衝突禁止条件だけであると、隣接する分割経路に存在する移動体の位置が入れ替わることが許容されるが、設定部によって特定経路への進入が禁止されるので、このような入れ替わることを防止することができる。これによって移動体のお互いの干渉を回避しつつ、全体の効率をより高めることができる。

なお、前述の各手段の括弧内の符号は、後述する実施形態に記載の具体的手段との対応関係を示す一例である。

移動制御システム１００の構成を示すブロック図。 ＡＧＶ３０の処理を示すフローチャート。 ＡＧＶ３０の他の処理を示すフローチャート。 検出装置５０の処理を示すフローチャート。 検出装置５０の他の処理を示すフローチャート。 搬送指示装置６０の処理を示すフローチャート。 搬送スケジュールを説明する図。 数式を説明する図。 サーバ４０の処理を示すフローチャート。 サーバ４０の他の処理を示すフローチャート。 第１の計算事例を説明する図。 第１の計算事例の搬送工程を示す図。 第１の計算事例の搬送スケジュールを示す図。 第２の計算事例を説明する図。 第２の計算事例の搬送工程を示す図。 第２の計算事例の搬送スケジュールを示す図。 第３の計算事例を説明する図。 第３の計算事例の搬送工程を示す図。 第３の計算事例の搬送スケジュールを示す図。 第２実施形態のサーバ４０の処理を示すフローチャート。 第３実施形態のサーバ４０の処理を示すフローチャート。 第４実施形態のサーバ４０の処理を示すフローチャート。

以下、図面を参照しながら本開示を実施するための形態を、複数の形態を用いて説明する。各実施形態で先行する実施形態で説明している事項に対応している部分には同一の参照符を付すか、または先行の参照符号に一文字追加し、重複する説明を略する場合がある。また各実施形態にて構成の一部を説明している場合、構成の他の部分は、先行して説明している実施形態と同様とする。各実施形態で具体的に説明している部分の組合せばかりではなく、特に組合せに支障が生じなければ、実施形態同士を部分的に組合せることも可能である。

（第１実施形態）
本開示の第１実施形態に関して、図１～図１９を用いて説明する。本実施形態の移動制御システム１００は、経路上を移動する複数のＡＧＶ３０の移動を制御する。移動制御システム１００は、図１に示すように、ＡＧＶ３０、サーバ４０、検出装置５０および搬送指示装置６０を含んで構成される。

ＡＧＶ３０、サーバ４０、検出装置５０および搬送指示装置６０は、それぞれ記憶媒体に記憶されているプログラムを実行し、各部を制御する制御部を有する。制御部は、少なくとも１つの演算処理装置（ＣＰＵ）と、プログラムとデータとを記憶する記憶媒体とを有する。各装置の制御部は、たとえばコンピュータによって読み取り可能な記憶媒体を備えるマイクロコンピュータによって実現される。記憶媒体は、コンピュータによって読み取り可能なプログラムおよびデータを非一時的に格納する非遷移的実体的記憶媒体である。記憶媒体は、半導体メモリまたは磁気ディスクなどによって実現される。以下、それぞれの制御部を明示せず制御部に換えて、ＡＧＶ３０、サーバ４０、検出装置５０および搬送指示装置６０と表記する場合がある。

ＡＧＶ３０は、移動体であり、電動モータを駆動源として、無人で経路上を走行する。ＡＧＶ３０は、移動スケジュールに従って移動する。移動スケジュールは、ＡＧＶ３０が物を搬送するので、搬送スケジュールともいう。ＡＧＶ３０は、ＡＧＶ用受信部３１、ＡＧＶ用送信部３２、位置検出部３３およびＡＧＶ用制御部３４を含んで構成される。

ＡＧＶ用送信部３２は、サーバ４０と通信して、サーバ４０に所定の情報を送信する。ＡＧＶ用受信部３１は、サーバ４０と通信して、サーバ４０からの情報を受信する。位置検出部３３は、ＡＧＶ３０の現在の位置情報を取得する。位置情報は、ＡＧＶ３０の現在位置および進行方向を含む。位置検出部３３は、検出した位置情報をＡＧＶ用送信部３２からサーバ４０に定期的に送信する。

位置検出部３３は、複数のセンサ情報を組み合わせる複合測位により、位置情報を生成する。位置検出部３３は、たとえばＧＮＳＳ（Global Navigation Satellite System）受信機、慣性センサ、地図データベース、およびロケータＥＣＵを備えている。ＧＮＳＳ受信機は、複数の測位衛星からの測位信号を受信する。慣性センサは、ＡＧＶ３０に作用する慣性力を検出するセンサである。慣性センサは、例えばジャイロセンサおよび加速度センサを備える。地図データベースは、不揮発性メモリに記憶されており、経路のリンクデータおよびノードデータを含む。ロケータＥＣＵは、ＧＮＳＳ受信機で受信する測位信号、地図データベースの地図データ、および慣性センサの計測結果を組み合わせることにより、ＡＧＶ３０の現在位置を逐次測位する。現在位置は、例えば緯度経度の座標で表される。

ＡＧＶ用制御部３４は、ＡＧＶ用受信部３１が受信した搬送スケジュールに従って移動するように駆動部を制御する。搬送スケジュールには、移動経路と、各地点を出発する出発時刻、各地点に到着する到着時刻、および各地点に停止する停止時間などが含まれる。

次にＡＧＶ３０の処理について、図２および図３のフローチャートを用いて説明する。図２および図３に示すフローチャートは、ＡＧＶ３０が電源投入状態において、短時間に繰り返し実行する。

まず、図２のフローチャートに関して説明する。ステップＳ１では、ＡＧＶ用受信部３１が搬送スケジュールを受信すると、ステップＳ２に移る。ステップＳ２では、搬送スケジュールに従って移動するように駆動部を制御し、本フローを終了する。これによってＡＧＶ３０は、搬送スケジュールを受信すると、搬送スケジュールに従って移動する。

次に、図３のフローチャートに関して説明する。ステップＳ１では、位置検出部３３によって現在位置を検出し、ステップＳ２に移る。ステップＳ２では、検出した現在位置を示す位置情報をサーバ４０に送信するようにＡＧＶ用送信部３２を制御し、本フローを終了する。これによってＡＧＶ３０は、現在位置を定期的にサーバ４０に送信する。

次に、検出装置５０に関して説明する。検出装置５０は、経路に配置されて、経路の状態および経路上の物体を監視する。経路上の物体には、ＡＧＶ３０および経路上を移動する他の物体、たとえば人物などを含む。検出装置５０は、監視した監視情報をサーバ４０に送信する。また検出装置５０は、サーバ４０からの指示を出力する。指示は、たとえば人物の移動を許可または禁止を促す指示である。

検出装置５０は、図１に示すように、周辺監視部５１、検出装置用受信部５２、検出装置用送信部５３および指示部５４を含んで構成される。検出装置用送信部５３は、サーバ４０と通信して、サーバ４０に所定の情報を送信する。検出装置用受信部５２は、サーバ４０と通信して、サーバ４０からの情報を受信する。周辺監視部５１は、検出装置５０の周辺監視に用いられる。周辺監視部５１は、検出した監視情報を検出装置用送信部５３からサーバ４０に送信する。

周辺監視部５１は、監視情報として、経路を移動するＡＧＶ３０およびＡＧＶ３０以外の動作物体の移動情報を検出する。移動情報は、移動方向および移動速度である。動作物体は、たとえば人物である。周辺監視部５１は、また監視情報として、経路上の異常を検出する。経路上の異常は、経路上に移動を妨げる障害物の有無を検出する。周辺監視部５１は、経路上の異常を検出する異常情報をとして出力する。

周辺監視部５１は、周辺をセンシングする。周辺監視部５１は、たとえば画像センサおよび超音波ソナーによって実現される。画像センサは、周辺を撮像する撮像装置である。超音波ソナーは、探査波を送信して物体で反射される反射波を受信することで、検出装置５０から物体上の測距点までの距離を検出するセンサである。測距点は、物体の表面上で探査波を反射した部位である。超音波ソナーのセンシング範囲は、周辺の所定範囲、たとえば数メートルである。

指示部５４は、周辺に位置する動作物体、たとえば人物への移動を指示する。指示部５４は、たとえば音声を出力、および画像を表示することで指示を行う。指示部５４は、たとえば経路が交差する交点で、信号機と同様の役割をする。指示部５４は、サーバ４０から送信された指示を検出装置用受信部５２から与えられると、受信した指示を出力する。

次に検出装置５０の処理について、図４および図５のフローチャートを用いて説明する。図４および図５に示すフローチャートは、検出装置５０が電源投入状態において、短時間に繰り返し実行する。

まず、図４のフローチャートに関して説明する。ステップＳ１では、周辺監視部５１が移動物体、動作物体または経路異常を検出したか否かを判断し、検出した場合にはステップＳ２に移り、検出していない場合には、本フローを終了する。ステップＳ２では、検出した移動情報、または異常情報を監視情報としてサーバ４０に送信するように検出装置用送信部５３を制御し、本フローを終了する。これによって検出装置５０は、監視情報をサーバ４０に定期的に送信する。

次に、図５のフローチャートに関して説明する。ステップＳ１では、検出装置用受信部５２が指示を受信すると、ステップＳ２に移る。ステップＳ２では、受信した指示を出力するように指示部５４を制御し、本フローを終了する。これによって検出装置５０は、受信した指示部５４を出力することができる。

次に、搬送指示装置６０に関して説明する。搬送指示装置６０は、複数のＡＧＶ３０に対する搬送指示を受け付けて、サーバ４０に搬送指示を送信する。搬送指示装置６０は、たとえば管理者によって操作される情報端末である。搬送指示装置６０は、図１に示すように、指示監視部６１、搬送用受信部６２、搬送用送信部６３、および入力部６４を含んで構成される。搬送指示装置６０は、たとえば外部と通信可能なパーソナルコンピュータ（Personal Computer：略称ＰＣ）およびスマートフォンなどの携帯型情報端末によって実現される。

搬送用送信部６３は、サーバ４０と通信して、サーバ４０に所定の情報を送信する。搬送用受信部６２は、サーバ４０と通信して、サーバ４０からの情報を受信する。入力部６４は、管理者によって操作されて、搬送指示が入力される。入力部６４は、搬送指示が入力されると、搬送用送信部６３から搬送指示をサーバ４０に送信する。

指示監視部６１は、入力部６４から入力される搬送指示を監視する。指示監視部６１は、現在実行中の搬送指示とは異なる新たな搬送指示が入力されると、入力された搬送指示が新しい搬送指示であることを示す情報とともに、搬送用送信部６３からサーバ４０に送信する。換言すると、更新された搬送指示を搬送用送信部６３から送信するように制御する。

次に搬送指示装置６０の処理について、図６のフローチャートを用いて説明する。図６に示すフローチャートは、搬送指示装置６０が電源投入状態において、短時間に繰り返し実行する。ステップＳ１では、搬送指示の有無を監視し、ステップＳ２に移る。搬送指示の有無は、指示監視部６１によって行われる。ステップＳ３では、搬送指示があったか否かを判断し、搬送指示があった場合にはステップＳ３に移り、搬送指示がない場合は、ステップＳ１に戻る。ステップＳ３では、搬送指示があったので、搬送指示をサーバ４０に送信するように搬送用送信部６３を制御し、本フローを終了する。これによって搬送指示装置６０は、新しい搬送指示を受け付けると、新しい搬送指示がサーバ４０に送信される。

次に、サーバ４０に関して説明する。サーバ４０は、移動体制御装置であって、経路上を移動する複数のＡＧＶ３０の移動を制御する。サーバ４０は、具体的には、ＡＧＶ３０に移動スケジュールを送信して、ＡＧＶ３０の移動を制御する。サーバ４０は、図１に示すように、記憶部４１、サーバ用受信部４２、サーバ用送信部４３およびサーバ用制御部４５を含んで構成される。

サーバ用送信部４３は、ＡＧＶ３０、検出装置５０、および搬送指示装置６０と通信して、各装置に所定の情報を送信する。またサーバ用受信部４２は、ＡＧＶ３０、検出装置５０、および搬送指示装置６０と通信して、各装置からの情報を受信する。記憶部４１には、ＡＧＶ３０を管理するための情報が記憶されている。記憶部４１には、搬送指示装置６０から送信された搬送指示が記憶される。

サーバ用制御部４５は、制御部であって、記憶部４１からの必要な情報を読み込み、ＡＧＶ３０の移動を制御する。サーバ用制御部４５は、図１に示すように、機能ブロックとして、設定部１４１、予測部１４２、判定部１４３、計算部１４４、および移動制御部１４５を含んで構成される。またサーバ用制御部４５は、取得部としても機能し、サーバ用受信部４２を介して、位置情報および監視情報を取得する。したがってサーバ用制御部４５は、ＡＧＶ３０の現在位置、経路を移動するＡＧＶ３０以外の動作物体の移動情報、および経路における異常、すなわち経路の移動不可部分を取得する。

設定部１４１は、複数のＡＧＶ３０の出発地点と終着地点とを結ぶ移動経路、および移動経路を移動する移動工程を設定する。また経由地がある場合には、経由地を経由する移動経路を設定する。さらに経由地に順番がある場合には、経由地の順番を考慮した移動経路を設定する。さらにＡＧＶ３０の移動に優先順位がある場合には、優先順を考慮して移動工程を設定する。

移動工程は、本実施形態では搬送工程ともいう。設定部１４１は、出発地点と終着地点とを結ぶ最短経路を移動経路として設定する。また設定部１４１は、複数のＡＧＶ３０の移動経路の重複が少なくなるように移動経路を設定する。したがって、たとえば最短経路が複数ある場合には、重複が少ない移動経路を設定する。また最短経路を優先するか、重複をしないことを優先するかは、予め設定可能であってもよい。たとえば最短経路が１つしかなく、重複を回避できない場合には、重複回避を優先する場合には、最短経路よりも遠回りになる経路を設定してもよい。

計算部１４４は、移動経路および移動工程を入力値して、制約条件を満たしつつ所定の評価値を最小化することを目的とする混合整数計画問題を解くことによって、移動体の移動スケジュールを計算する。

具体的には、本実施形態では、blocking job shop型のスケジューリング問題を同時に複数の機械または設備を利用できるように定式化し、利用する経路に加え、先に利用する経路も工程に加えたスケジューリング問題にすることで、干渉を回避するzone controlを表現可能にしている。これによって干渉を回避しながら全体の効率を最適化する搬送スケジュールが計算可能になる。

たとえば他のＡＧＶ３０が進行方向に隣接する分割経路に存在する場合には、他のＡＧＶ３０が通り過ぎてから、隣接する分割経路への進入を許可する。これは一般に、blocking job shop schedulingといわれる。これによって衝突を回避する。さらに本実施形態では、ＡＧＶ３０が存在する場所と重複経路の出入口も同時に確保して他のＡＧＶ３０の重複経路への進入を禁止し、正面衝突回避のzone controlを表現する。このために、blocking job shop型のスケジューリング問題を、いわゆる複数機械同時利用へ定式化を拡張する。これによって干渉のない搬送スケジューリングを計算できるため、ＡＧＶ３０の動きを把握するための設備は不要となる。

移動制御部１４５は、搬送スケジュールによって各ＡＧＶ３０の移動を制御する。移動制御部１４５は、搬送スケジュールを各ＡＧＶ３０に送信するようにサーバ用送信部４３を制御する。予測部１４２は、検出装置５０が検出した監視情報に基づいて、ＡＧＶ３０以外の人などの動きを予測する。たとえば検出した人物が、経路のどちらの方向に進むのかを移動情報を用いて予測する。判定部１４３は、搬送スケジュールが更新されたとき、新たな搬送指示が発生したときに、搬送スケジュールを再計算すべきか否かを判断する。

次に、図７を用いて、搬送スケジュールに関して説明する。図７では、比較例では遅延や遠回りが起き、実施例では最適解が求まることを示す。経路は、複数の分割経路から構成される。たとえば図７に示す経路では、７つの分割経路から構成される。１つの分割経路には、１つのＡＧＶ３０しか位置することができない。また経路は、２つのＡＧＶ３０がすれ違えない。したがって分割経路でも、２つのＡＧＶ３０がすれ違うことができない。

移動工程は、ある時刻にあるＡＧＶ３０が位置する分割経路を示す。たとえば図７に示すように、現時点では、経路に７つの分割経路があり、第１分割経路Ｒ１に第１ＡＧＶ３０Ａが位置し、第６分割経路Ｒ６に第２ＡＧＶ３０Ｂが位置する。そしてその後、各ＡＧＶ３０が移動することで、位置する分割経路が変化する。図７に示す例では、第１ＡＧＶ３０Ａは、出発地点が第１分割経路Ｒ１であり、到着地点が第５分割経路Ｒ５である。また第２ＡＧＶ３０Ｂは、出発地点が第６分割経路Ｒ６であり、到着地点が第７分割経路Ｒ７である。この場合、２つの移動経路は、第２分割経路Ｒ２で交差するので、いずれか一方のＡＧＶ３０を先に通過させ、他方を後に通過させることになる。

第１比較例では、第２ＡＧＶ３０Ｂを先に第２分割経路Ｒ２を通過させ、その後に第１ＡＧＶ３０Ａを第２分割経路Ｒ２を通過している。これによって第２ＡＧＶ３０Ｂの移動は先に完了するが、第１ＡＧＶ３０Ａを待たせることで、全体の搬送時間が長くなる。

また第２比較例では、第２ＡＧＶ３０Ｂを最短経路ではなく、第２分割経路Ｒ２を迂回させ、第１ＡＧＶ３０Ａと第２ＡＧＶ３０Ｂを同時に移動させている。これによって第２ＡＧＶ３０Ｂを遠回りさせることになり、移動全体が非効率となる。

そして第１実施例では、第１ＡＧＶ３０Ａを先に第２分割経路Ｒ２を通過させ、その後に第２ＡＧＶ３０Ｂを第２分割経路Ｒ２を通過している。第２ＡＧＶ３０Ｂを待たせて、先に第１ＡＧＶ３０Ａを通過させることで、効率的な移動を実現しつつ、衝突を回避している。このように本実施形態では、衝突を回避し、全ての移動が完了するまでの時間を短くするように移動スケジュールを設定する。

次に、具体的な搬送スケジュールの計算方法に関して図８を用いて説明する。計算部１４４は、前述のように、移動経路および移動工程を入力値して、制約条件を満たしつつ所定の評価値を最小化することを目的とする混合整数計画問題を解くことによって、移動体の移動スケジュールを計算する。混合整数計画問題は、混合整数最適化問題ともいい、整数値を取る変数と実数値を取る変数が混在している整数計画問題のことである。整数計画問題は、整数変数を含む最適化問題のことである。スケジューリング問題とは、人や機械といったリソースに対してジョブのスケジュールを割当てる問題である。本実施形態では、リソースは経路に該当し、ジョブがＡＧＶ３０の移動に該当する。

最適化問題とは、条件を満たす候補の中から目的に対して最適なものを数学的に見つける問題である。最適化問題は、決定変数、目的関数および制約条件という３つの要素から構成される。決定変数は、意思決定や制御の対象で、値を決めたいものである。本実施形態では、決定変数は、搬送スケジュールが該当する。目的関数は、決定変数が目的に対して良いか悪いかを判断するための関数である。本実施形態では、メイクスパンを最小化、すなわち最後のジョブの終了時間が早くなることを目的とする関数である。

制約条件は、候補となる決定変数が満たす必要のある条件である。本実施形態では、制約条件には、衝突禁止条件が含まれる。衝突禁止条件は、経路を少なくともＡＧＶ３０よりも大きい長さで分割した分割経路において、１つの分割経路には、１つのＡＧＶ３０の存在を許可し、２つのＡＧＶ３０の存在を禁止する条件である。換言すると、衝突禁止条件は、分割経路において、ＡＧＶ３０が次の分割経路への移動が完了するまで、移動が完了前の分割経路は他のＡＧＶ３０による利用を禁止する条件である。

また最適化問題に入力される搬送工程は、少なくとも２つのＡＧＶ３０の移動経路が重複して、ＡＧＶ３０の移動方向が対向することによって、ＡＧＶ３０が干渉する可能性がある特定経路では、特定経路に１つのＡＧＶ３０が存在する場合には、ＡＧＶ３０が存在する特定経路に他のＡＧＶ３０の使用を禁止するように設定されている。

さらに設定部１４１は、特定経路に１つのＡＧＶ３０が存在する場合には、ＡＧＶ３０が存在する特定経路のうち移動体の移動方向の部分への他のＡＧＶ３０の使用を禁止し、移動方向とは反対方向の部分の使用を許可するように移動工程を設定する。

図８の右端の欄に示すように、本実施形態は、blocking job shop schedulingに示す式を用いる。図８の左の欄に示す一般的なjob shopスケジューリングの定式化に対して、図８の右の欄に示す式は、blocking job shop スケジューリングの定式化である。

次に図８の右の本実施形態の式に関して説明する。ジョブやプロセスに関する情報は、変数の添え字で示す。たとえば、S_α，ｉは、ジョブαのｉ番目のタスクであることを示す添え字である。ｓは、ジョブの開始時間を示し、pはジョブの処理時間を示し、Ｃ_ｍａｘは、スケジュールのメイクスパンを示す。Ｒは、リソースの集合を示し、Ｐは製品の集合を示し、Ｑ_αおよびＱ_βは、製品αと製品βのジョブの集合を示す。Ｍは、大きい正の数を示す。そしてｘ_{α，ｉ，β，ｊ}は、０－１の整数を示し、Ｊ_α，ｉとＪ_β，ｊの製造手順を示す。

式（１）の目的関数は、メイクスパンを最小化することを目的とする。そして、式（２）のＣ_ｍａｘは各製品の最後のジョブの最大終了時間を表している。式（３）は開始時刻に対する非負の制約を示し、式（４）は各ジョブが先行するジョブ動作の後に動作することを示している。したがって、次のジョブα，ｉ＋１の開始時刻は、処理終了時刻S_α，ｉ＋ｐ_α，ｉよりも製造資源の分だけ遅くなければならない。

式（５）、（６）は、移動体が次の分割経路へ移動が完了してからでないとその分割経路は他の移動体により利用を許さない衝突禁止条件である。ｘ_{α，ｉ，β，ｊ}は、ジョブαのｉ番目のタスクが製品βのｊ番目のジョブよりも先に操作された場合に０を取る決定変数を表す。

次に、サーバ４０の処理について、図９および図１０のフローチャートを用いて説明する。図９および図１０に示すフローチャートは、サーバ４０が電源投入状態において、短時間に繰り返し実行する。

まず、図９のフローチャートに関して説明する。ステップＳ１では、搬送工程を取得し、ステップＳ２に移る。ステップＳ２では、計算部１４４が搬送スケジュールを計算し、ステップＳ３に移る。ステップＳ３では、搬送スケジュールをＡＧＶ３０へ送信するようにサーバ用送信部４３を制御し、本フローを終了する。このようにサーバ用制御部４５は、搬送工程に基づいて、搬送スケジュールを計算し、計算した搬送スケジュールをＡＧＶ３０に送信する。

次に、図１０のフローチャートに関して説明する。ステップＳ１では、搬送指示をサーバ用受信部４２が受信し、ステップＳ２に移る。ステップＳ２では、判定部１４３が新しい搬送指示によって搬送スケジュールの再計算の有無が必要か否かを判断する。そして、ステップＳ２では、再計算が必要な場合には、ステップＳ３に移り、必要でない場合には、本フローを終了する。再計算が必要な場合とは、新たなＡＧＶ３０が追加された場合、新たな搬送先が追加された場合である。再計算が不要な場合とは、新しい搬送指示が搬送先および搬送経路は変わらないが、搬送量がかわった場合などである。

ステップＳ３では、新しい搬送指示における搬送工程を取得し、ステップＳ４に移る。ステップＳ４では、計算部１４４が搬送スケジュールを計算し、ステップＳ５に移る。ステップＳ５では、搬送スケジュールをＡＧＶ３０へ送信するようにサーバ用送信部４３を制御し、本フローを終了する。このようにサーバ用制御部４５は、搬送指示によって再計算が必要な場合には、新しい搬送工程に基づいて、搬送スケジュールを再計算し、再計算した搬送スケジュールをＡＧＶ３０に送信する。

次に、搬送スケジュールの３つの計算事例に関して、図１１～図１９を用いて説明する。まず第１の計算事例に関して説明する。第１の計算事例の経路には、図１１に示すように、７つの分割経路があり、スタート時点では、第１分割経路Ｒ１に第１ＡＧＶ３０Ａが位置し、第５分割経路Ｒ５に第２ＡＧＶ３０Ｂが位置する。そして、第１ＡＧＶ３０Ａは、出発地点が第１分割経路Ｒ１であり、到着地点が第６分割経路Ｒ６である。また第２ＡＧＶ３０Ｂは、出発地点が第５分割経路Ｒ５であり、到着地点が第７分割経路Ｒ７である。この場合、２つのＡＧＶ３０の移動経路のうち、第２分割経路Ｒ２、第３分割経路Ｒ３および第４分割経路Ｒ４が重複する特定経路となる。特定経路では、ＡＧＶ３０の移動方向が対向することによって、ＡＧＶ３０が干渉する可能性がある。この場合、特定経路では、いずれか一方のＡＧＶ３０を先に通過させ、他方を後に通過させることになる。

図１２には、搬送工程を示す。第１ＡＧＶ３０Ａの搬送工程では、第１分割経路Ｒ１を出発地点とし、次に第２分割経路Ｒ２に移動する。その場合、第２分割経路Ｒ２は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第２分割経路Ｒ２だけでなく、第４分割経路Ｒ４も使用中とする。実際は、第２分割経路Ｒ２しか使用していないが、仮想的に第４分割経路Ｒ４を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第１ＡＧＶ３０Ａが第２分割経路Ｒ２から第３分割経路Ｒ３に移動すると、同様に、第３分割経路Ｒ３は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第３分割経路Ｒ３だけでなく、第４分割経路Ｒ４も使用中とする。

その後、第１ＡＧＶ３０Ａが第３分割経路Ｒ３から第４分割経路Ｒ４に移動すると、第４分割経路Ｒ４は特定経路であるが、移動方向の前方には特定経路はないので、現在位置である第４分割経路Ｒ４だけを使用中とする。その後、第１ＡＧＶ３０Ａが第４分割経路Ｒ４から第６分割経路Ｒ６に移動して、第１ＡＧＶ３０Ａの移動は終了する。

同様に、第２ＡＧＶ３０Ｂの搬送工程では、第５分割経路Ｒ５を出発地点とし、次に第４分割経路Ｒ４に移動する。その場合、第４分割経路Ｒ４は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第４分割経路Ｒ４だけでなく、第２分割経路Ｒ２も使用中とする。実際は、第４分割経路Ｒ４しか使用していないが、仮想的に第２分割経路Ｒ２を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第２ＡＧＶ３０Ｂが第４分割経路Ｒ４から第３分割経路Ｒ３に移動すると、同様に、第３分割経路Ｒ３は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第３分割経路Ｒ３だけでなく、第２分割経路Ｒ２も使用中とする。

その後、第２ＡＧＶ３０Ｂが第３分割経路Ｒ３から第２分割経路Ｒ２に移動すると、第２分割経路Ｒ２は特定経路であるが、移動方向の前方には特定経路はないので、現在位置である第２分割経路Ｒ２だけを使用中とする。その後、第２ＡＧＶ３０Ｂが第２分割経路Ｒ２から第７分割経路Ｒ７に移動して、第２ＡＧＶ３０Ｂの移動は終了する。

図１３には、搬送スケジュールを示す。搬送スケジュールは、図１２の搬送工程を入力して、前述の数式（１）のメイクスパンが最小値となるように計算されたものである。図１３に示す搬送スケジュールは、ある時刻に、各ＡＧＶ３０が使用する分割経路を示す。

図１３に示すように、第１時刻ｔ１には、第１ＡＧＶ３０Ａが第１分割経路Ｒ１に位置し、第２ＡＧＶ３０Ｂが第５分割経路Ｒ５に位置する。その後、第２時刻ｔ２には、第１ＡＧＶ３０Ａが第２分割経路Ｒ２に移動し、仮想的に第４分割経路Ｒ４を使用する。第２時刻ｔ２では、第２ＡＧＶ３０Ｂは移動していない。その後、第３時刻ｔ３では、第１ＡＧＶ３０Ａが第３分割経路Ｒ３に移動し、仮想的に第４分割経路Ｒ４を使用する。第３時刻ｔ３でも、第２ＡＧＶ３０Ｂは移動していない。その後、第４時刻ｔ４では、第１ＡＧＶ３０Ａが第４分割経路Ｒ４に移動する。第４時刻ｔ４でも、第２ＡＧＶ３０Ｂは移動していない。

その後、第５時刻ｔ５には、第１ＡＧＶ３０Ａが第６分割経路Ｒ６に移動し、第１ＡＧＶ３０Ａの移動が終了する。第５時刻ｔ５では、第２ＡＧＶ３０Ｂも第５分割経路Ｒ５から第４分割経路Ｒ４に移動する。その後、第６時刻ｔ６～第８時刻ｔ８では、第２ＡＧＶ３０Ｂが、順次、第３分割経路Ｒ３、第２分割経路Ｒ２、および第７分割経路Ｒ７に移動して、第２ＡＧＶ３０Ｂの移動が終了する。

このように第１の計算事例では、２台のＡＧＶ３０の移動経路に特定経路があるが、干渉することなく、順番に特定経路を使用することで、無駄なＡＧＶ３０の移動もなく、移動を完了することができる。

次に、第２の計算事例に関して、図１４～図１６を用いて説明する。第２の計算事例の経路には、図１４に示すように、８つの分割経路があり、スタート時点では、第１分割経路Ｒ１に第１ＡＧＶ３０Ａが位置し、第８分割経路Ｒ８に第２ＡＧＶ３０Ｂが位置する。そして、第１ＡＧＶ３０Ａは、出発地点が第１分割経路Ｒ１であり、第８分割経路Ｒ８以外の分割経路を通過して、再び出発地点に戻る。したがって第１ＡＧＶ３０Ａの到着地点も、第１分割経路Ｒ１となる。

また第２ＡＧＶ３０Ｂは、出発地点が第８分割経路Ｒ８であり、第１分割経路Ｒ１以外の分割経路を通過して、再び出発地点に戻る。したがって第２ＡＧＶ３０Ｂの到着地点も、第８分割経路Ｒ８となる。この場合、２つのＡＧＶ３０の移動経路のうち、第２分割経路Ｒ２～第６分割経路Ｒ６が重複する特定経路となる。

図１５には、搬送工程を示す。第１ＡＧＶ３０Ａの搬送工程では、第１分割経路Ｒ１を出発地点とし、次に第２分割経路Ｒ２に移動する。その場合、第２分割経路Ｒ２は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第２分割経路Ｒ２だけでなく、特定経路への入口である第６分割経路Ｒ６も使用中とする。実際は、第２分割経路Ｒ２しか使用していないが、仮想的に第６分割経路Ｒ６を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第１ＡＧＶ３０Ａが第２分割経路Ｒ２から第３分割経路Ｒ３、第４分割経路Ｒ４、第５分割経路Ｒ５と順次、移動し、その間は第６分割経路Ｒ６も使用中とする。

その後、第１ＡＧＶ３０Ａが第６分割経路Ｒ６に移動すると、第６分割経路Ｒ６は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第６分割経路Ｒ６だけでなく、進行方向の前方に位置する特定経路の出入口である第２分割経路Ｒ２も使用中とする。その後、第１ＡＧＶ３０Ａが第７分割経路Ｒ７に移動し、同様に第２分割経路Ｒ２も使用中とする。その後、第１ＡＧＶ３０Ａが第２分割経路Ｒ２および第１分割経路Ｒ１の順に移動して、第１ＡＧＶ３０Ａの移動は終了する。

同様に、第２ＡＧＶ３０Ｂの搬送工程では、第８分割経路Ｒ８を出発地点とし、次に第６分割経路Ｒ６に移動する。その場合、第６分割経路Ｒ６は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第６分割経路Ｒ６だけでなく、第２分割経路Ｒ２も使用中とする。実際は、第６分割経路Ｒ６しか使用していないが、仮想的に第２分割経路Ｒ２を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第２ＡＧＶ３０Ｂが第６分割経路Ｒ６から第５分割経路Ｒ５、第４分割経路Ｒ４、第３分割経路Ｒ３と順次、移動し、その間は第２分割経路Ｒ２も使用中とする。

その後、第２ＡＧＶ３０Ｂが第２分割経路Ｒ２に移動すると、第２分割経路Ｒ２は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第２分割経路Ｒ２だけでなく、進行方向の前方に位置する直近の特定経路の出入口である第６分割経路Ｒ６も使用中とする。その後、第２ＡＧＶ３０Ｂが第７分割経路Ｒ７に移動し、同様に第６分割経路Ｒ６も使用中とする。その後、第２ＡＧＶ３０Ｂが第６分割経路Ｒ６および第８分割経路Ｒ８の順に移動して、第２ＡＧＶ３０Ｂの移動は終了する。

図１６には、搬送スケジュールを示す。搬送スケジュールは、図１５の搬送工程を入力して、前述の数式（１）のメイクスパンが最小値となるように計算されたものである。図１６に示す搬送スケジュールは、ある時刻に、各ＡＧＶ３０が使用する分割経路を示す。

図１６に示すように、第１時刻ｔ１には、第１ＡＧＶ３０Ａが第１分割経路Ｒ１に位置し、第２ＡＧＶ３０Ｂが第８分割経路Ｒ８に位置する。その後、第２時刻ｔ２には、第１ＡＧＶ３０Ａが第２分割経路Ｒ２に移動し、仮想的に第６分割経路Ｒ６を使用する。第２時刻ｔ２では、第２ＡＧＶ３０Ｂは移動していない。その後、第３時刻ｔ３～第６時刻ｔ６までは、第１ＡＧＶ３０Ａが、順次、第３分割経路Ｒ３、第４分割経路Ｒ４、第５分割経路Ｒ５、第６分割経路Ｒ６と移動する。そして第６時刻ｔ６では、第６分割経路Ｒ６だけでなく、第２分割経路Ｒ２を仮想的に使用する。その後、第７時刻ｔ７では、第７分割経路Ｒ７に移動し、仮想的に第２分割経路Ｒ２も使用する。その後、第８時刻ｔ８、第９時刻ｔ９では、順次、第２分割経路Ｒ２、第１分割経路Ｒ１と移動して、第１ＡＧＶ３０Ａの移動が終了する。

第９時刻ｔ９では、第２ＡＧＶ３０Ｂの移動が開始し、第６分割経路Ｒ６に移動し、仮想的に第２分割経路Ｒ２も使用する。その後、第１０時刻ｔ１０～第１３時刻ｔ１３までは、第２ＡＧＶ３０Ｂが、順次、第５分割経路Ｒ５、第４分割経路Ｒ４、第３分割、第２分割経路Ｒ２と移動する。そして第１３時刻ｔ１３では、第２分割経路Ｒ２だけでなく、第６分割経路Ｒ６を仮想的に使用する。その後、第１４時刻ｔ１４では、第７分割経路Ｒ７に移動し、仮想的に第６分割経路Ｒ６も使用する。その後、第１５時刻ｔ１５、第１６時刻ｔ１６では、順次、第６分割経路Ｒ６、第８分割経路Ｒ８と移動して、第２ＡＧＶ３０Ｂの移動が終了する。

このように第２の計算事例でも同様に、２台のＡＧＶ３０の移動経路に特定経路があるが、干渉することなく、順番に特定経路を使用することで、無駄なＡＧＶ３０の移動もなく、移動を完了することができる。

次に、第３の計算事例に関して、図１７～図１９を用いて説明する。第３の計算事例の経路には、図１７に示すように、１０つの分割経路があり、スタート時点では、第１分割経路Ｒ１に第１ＡＧＶ３０Ａが位置し、第８分割経路Ｒ８に第２ＡＧＶ３０Ｂが位置し、第５分割経路Ｒ５に第３ＡＧＶ３０Ｃが位置する。そして、第１ＡＧＶ３０Ａは、出発地点が第１分割経路Ｒ１であり、第２分割経路Ｒ２、第４分割経路Ｒ４、第６分割経路Ｒ６、第７分割経路Ｒ７、第９分割経路Ｒ９と順次、通過して、第１０分割経路Ｒ１０が到着点である。そして、第２ＡＧＶ３０Ｂは、出発地点が第８分割経路Ｒ８であり、第９分割経路Ｒ９、第７分割経路Ｒ７、第６分割経路Ｒ６、第４分割経路Ｒ４、第２分割経路Ｒ２と順次、通過して、第３分割経路Ｒ３が到着点である。また第３ＡＧＶ３０Ｃは、出発地点が第５分割経路Ｒ５であり、第６分割経路Ｒ６、第７分割経路Ｒ７、第９分割経路Ｒ９と順次、通過して、第１０分割経路Ｒ１０が到着点である。この場合、３つのＡＧＶ３０の移動経路のうち、第２分割経路Ｒ２、第４分割経路Ｒ４、第６分割経路Ｒ６、第７分割経路Ｒ７、第９分割経路Ｒ９が重複する特定経路となる。

図１８には、搬送工程を示す。第１ＡＧＶ３０Ａの搬送工程では、第１分割経路Ｒ１を出発地点とし、次に第２分割経路Ｒ２に移動する。その場合、第２分割経路Ｒ２は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第２分割経路Ｒ２だけでなく、第６分割経路Ｒ６および第９分割経路Ｒ９も使用中とする。実際は、第２分割経路Ｒ２しか使用していないが、仮想的に第６分割経路Ｒ６および第９分割経路Ｒ９を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第１ＡＧＶ３０Ａが第２分割経路Ｒ２から第４分割経路Ｒ４、第６分割経路Ｒ６、第７分割経路Ｒ７、第９分割経路Ｒ９と順次、移動し、その間は第９分割経路Ｒ９も使用中とする。また第１ＡＧＶ３０Ａが第７分割経路Ｒ７に移動するまで、第６分割経路Ｒ６も使用中とする。その後、第１ＡＧＶ３０Ａが第１０分割経路Ｒ１０に移動して、第１ＡＧＶ３０Ａの移動は終了する。

第２ＡＧＶ３０Ｂの搬送工程では、第８分割経路Ｒ８を出発地点とし、次に第９分割経路Ｒ９に移動する。その場合、第９分割経路Ｒ９は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第９分割経路Ｒ９だけでなく、第２分割経路Ｒ２および第６分割経路Ｒ６も使用中とする。実際は、第９分割経路Ｒ９しか使用していないが、仮想的に第２分割経路Ｒ２および第６分割経路Ｒ６を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第２ＡＧＶ３０Ｂが第９分割経路Ｒ９から第７分割経路Ｒ７、第６分割経路Ｒ６、第４分割経路Ｒ４、第２分割経路Ｒ２と順次、移動し、その間は第２分割経路Ｒ２も使用中とする。また第２ＡＧＶ３０Ｂが第４分割経路Ｒ４に移動するまで、第６分割経路Ｒ６も使用中とする。その後、第２ＡＧＶ３０Ｂが第３分割経路Ｒ３に移動して、第２ＡＧＶ３０Ｂの移動は終了する。

第３ＡＧＶ３０Ｃの搬送工程では、第５分割経路Ｒ５を出発地点とし、次に第６分割経路Ｒ６に移動する。その場合、第６分割経路Ｒ６は特定経路であるので、特定経路への他のＡＧＶ３０の進入を禁止するために、第６分割経路Ｒ６だけでなく、第９分割経路Ｒ９も使用中とする。実際は、第６分割経路Ｒ６しか使用していないが、仮想的に第９分割経路Ｒ９を使用しているとして、他のＡＧＶ３０が特定経路に進入すること防ぐ。その後、第３ＡＧＶ３０Ｃが第６分割経路Ｒ６から第７分割経路Ｒ７、第９分割経路Ｒ９と順次、移動し、その間は第９分割経路Ｒ９も使用中とする。その後、第３ＡＧＶ３０Ｃが第１０分割経路Ｒ１０に移動して、第３ＡＧＶ３０Ｃの移動は終了する。

図１９には、搬送スケジュールを示す。搬送スケジュールは、図１９の搬送工程を入力して、前述の数式（１）のメイクスパンが最小値となるように計算されたものである。図１９に示す搬送スケジュールは、ある時刻に、各ＡＧＶ３０が使用する分割経路を示す。

図１９に示すように、第１時刻ｔ１には、第１ＡＧＶ３０Ａが第１分割経路Ｒ１に位置し、第２ＡＧＶ３０Ｂが第８分割経路Ｒ８に位置し、第３ＡＧＶ３０Ｃが第５分割経路Ｒ５に位置する。その後、第２時刻ｔ２には、第２ＡＧＶ３０Ｂが第９分割経路Ｒ９に移動し、仮想的に第２分割経路Ｒ２および第６分割経路Ｒ６を使用する。第２時刻ｔ２では、第１ＡＧＶ３０Ａおよび第３ＡＧＶ３０Ｃは移動していない。その後、第３時刻ｔ３、第４時刻ｔ４、第５時刻ｔ５では、第２ＡＧＶ３０Ｂが、順次、第７分割経路Ｒ７、第６分割経路Ｒ６、第４分割経路Ｒ４と移動する。そして第５時刻ｔ５では、第６分割経路Ｒ６は使用されていないので、第３ＡＧＶ３０Ｃが移動を開始し、第６分割経路Ｒ６に移動し、第９分割経路Ｒ９も仮想的に使用する。

その後、第６時刻ｔ６では、第２ＡＧＶ３０Ｂは、第２分割経路Ｒ２に移動する。そして第６時刻ｔ６、第７時刻ｔ７では、第３ＡＧＶ３０Ｃは第７分割経路Ｒ７、第９分割経路Ｒ９と順次移動する。その後、第８時刻ｔ８では、第２ＡＧＶ３０Ｂが第３分割経路Ｒ３に移動して、第２ＡＧＶ３０Ｂの移動が終了する。また第３ＡＧＶ３０Ｃは、第１０分割経路Ｒ１０に移動して、第３ＡＧＶ３０Ｃの移動が終了する。

第１ＡＧＶ３０Ａは、第８時刻ｔ８から移動を開始して、第１３時刻ｔ１３まで、順次、第２分割経路Ｒ２、第４分割経路Ｒ４、第６分割経路Ｒ６、第７分割経路Ｒ７、第９分割経路Ｒ９、第１０分割経路Ｒ１０と移動するそして、第１ＡＧＶ３０Ａは、第１０分割経路Ｒ１０に移動して移動が終了する。

このように第３の計算事例でも同様に、３台のＡＧＶ３０の移動経路に特定経路があるが、干渉することなく、順番に特定経路を使用することで、無駄なＡＧＶ３０の移動もなく、移動を完了することができる。

以上説明したように本実施形態の移動制御システム１００では、経路は２つのＡＧＶ３０がすれ違えないので、移動経路が交錯する場合には、ＡＧＶ３０の衝突を避けるために、一方のＡＧＶ３０を待機させて、他方のＡＧＶ３０を移動させた後に、一方のＡＧＶ３０を移動させる必要がある。そこで混合整数計画問題の制約条件に衝突禁止条件を用いて、移動体の衝突を避けつつ、評価値を最小化する搬送スケジュールを計算する。評価値は、全てのＡＧＶ３０の移動が完了するまでの時間、全てのＡＧＶ３０の移動時間の総和、ＡＧＶ３０の待機時間の総和などであり、本実施形態ではメイクスパン、すなわち全ての移動体の移動が完了するまでの時間を評価値としている。また混合整数計画問題を解くことによって搬送スケジュールを決定するので、複数回計算を繰り返すことを抑制することができる。

さらに設定部１４１は、特定経路に１つのＡＧＶ３０が存在すると、他のＡＧＶ３０が特定経路に進入することができないように搬送工程を設定する。衝突禁止条件だけであると、隣接する分割経路に存在するＡＧＶ３０の位置が入れ替わることが許容されるが、設定部１４１によって特定経路への進入が禁止されるので、このような入れ替わることを防止することができる。これによってＡＧＶ３０のお互いの干渉を回避しつつ、全体の効率をより高めることができる。

また本実施形態では、設定部１４１は、特定経路に１つのＡＧＶ３０が存在する場合には、ＡＧＶ３０が存在する特定経路のうちＡＧＶ３０の移動方向の部分への他のＡＧＶ３０の使用を禁止し、移動方向とは反対方向の部分の使用を許可するように搬送工程を設定する。これによって特定経路の全体を進入禁止にするよりも、効率よく特定経路を使用することができる。したがって干渉を回避しつつ、有効に特定経路を活用して効率化することができる。

また本実施形態では、計算部１４４は、移動経路および搬送工程が設定部１４１によって変更された場合には、新しい移動経路および搬送工程を入力して、搬送スケジュールを計算する。これによって新しい情報を用いて搬送スケジュールを計算することができる。したがって搬送工程の変更に柔軟に対応することができる。

（第２実施形態）
次に、本開示の第２実施形態に関して、図２０を用いて説明する。本実施形態では、ＡＧＶ３０の位置情報を用いて、搬送スケジュールを再計算する点に特徴を有する。図２０は、本実施形態のサーバ４０の処理を示すフローチャートである。図２０に示すフローチャートは、サーバ４０が電源投入状態において、短時間に繰り返し実行する。

ステップＳ１では、各ＡＧＶ３０の位置情報を、サーバ用受信部４２を介して取得し、ステップＳ２に移る。ステップＳ２では、位置情報と搬送スケジュール上の予定位置とを比較して、乖離を計算し、ステップＳ３に移る。

ステップＳ３では、乖離が許容範囲内であるか否かを判断し、許容範囲内である場合には、再計算が不要として本フローを終了する。乖離が許容範囲外である場合には、再計算が必要として、ステップＳ４に移る。

ステップＳ４では、現在位置を考慮して、搬送スケジュールを再計算して、ステップＳ５に移る。ステップＳ５では、再計算した搬送スケジュールをサーバ用送信部４３から各ＡＧＶ３０に送信するように制御し、本フローを終了する。

このように計算部１４４は、ＡＧＶ３０の現在位置と、搬送スケジュールのおける予定位置との差が所定値より大きい場合には、搬送スケジュールを再計算する。これによってＡＧＶ３０の現在位置と予定位置との乖離に起因して、ＡＧＶ３０が干渉するなどを抑制することができる。

（第３実施形態）
次に、本開示の第３実施形態に関して、図２１を用いて説明する。本実施形態では、検出装置５０の監視情報を用いて、搬送スケジュールを再計算する点に特徴を有する。図２１は、本実施形態のサーバ４０の処理を示すフローチャートである。図２１に示すフローチャートは、サーバ４０が電源投入状態において、短時間に繰り返し実行する。

ステップＳ１では、検出装置５０から監視情報を、サーバ用受信部４２を介して取得し、ステップＳ２に移る。ステップＳ２では、監視情報を用いて、ＡＧＶ３０以外の動作物体、たとえば人物の移動方向および移動速度を予測し、ステップＳ３に移る。

ステップＳ３では、動作物体によって搬送スケジュールを再計算する必要があるか否かを判断し、再計算が必要な場合は、ステップＳ４に移り、再計算が不要な場合は本フローを終了する。再計算が必要な場合は、人物の移動によって、ＡＧＶ３０と人物が干渉するおそれがある場合である。

ステップＳ４では、人物の移動情報を考慮して、搬送スケジュールを再計算して、ステップＳ５に移る。ステップＳ５では、再計算した搬送スケジュールをサーバ用送信部４３から各ＡＧＶ３０に送信するように制御し、ステップＳ６に移る。ステップＳ６では、検出装置５０へ動作物体への指示を送信するようにサーバ用制御部４５を制御し、本フローを終了する。

このように設定部１４１は、移動情報から動作物体の動きを予測して、動作物体を含む移動経路および移動工程を設定する。そして計算部１４４は、新しい移動経路および移動工程を入力値して、搬送スケジュールを計算する。これによってＡＧＶ３０と動作物体が干渉するなどを抑制することができる。またサーバ用制御部４５は、動作物体への指示を出力するので、たとえば動作物体が止まるように検出装置５０の指示部５４によって指示することができる。これによって動作物体、たとえば人物は、指示に従って、ＡＧＶ３０の通過を待つ、またはＡＧＶ３０より先に移動を、安全に行うことができる。

また動作物体への指示を行う場合には、搬送スケジュールを計算する制約条件にＡＧＶ３０および動作物体の移動の優先順位が設定された優先条件を含む。たとえば動作物体を優先させるのか、ＡＧＶ３０の移動を優先させるのかの条件である。優先順位は、たとえば条件によって変わってもよく、事前に固定されていてもよい。たとえば時間帯によって、優先順位を変えてもよい。また優先度は、ＡＧＶ３０同士および人物との干渉を防ぎながら移動を実現させるために、人物を待たせても良い。またＡＧＶ３０と混在移動体である人物の優先順位を搬送量や混雑度に応じて決定してもよい。このような優先度、優先順位は、記憶部４１に記憶されている。そして優先度に従ったスケジュール計算を、たとえば人物の移動を優先する待ち時間を許さないというno-waitの制約条件を追加することで実現することができる。

（第４実施形態）
次に、本開示の第４実施形態に関して、図２２を用いて説明する。本実施形態では、検出装置５０の監視情報を用いて、搬送スケジュールを再計算する点に特徴を有する。図２２は、本実施形態のサーバ４０の処理を示すフローチャートである。図２２に示すフローチャートは、サーバ４０が電源投入状態において、短時間に繰り返し実行する。

ステップＳ１では、検出装置５０から監視情報を、サーバ用受信部４２を介して取得し、ステップＳ２に移る。ステップＳ２では、監視情報を用いて、経路に異常があるか否かを判断し、異常がある場合は、ステップＳ３に移り、異常がない場合は、本フローを終了する。

経路異常には、静的な異常と動的な異常を含む。静的な異常は、事前にわかっている工事などの異常である。動的な異常とは、ＡＧＶ３０の自動制御などに起因する一時停止、荷崩れなどの物理的な不具合による一時停止などが含まれる。

ステップＳ３では、経路に異常があるので、異常によって搬送スケジュールを再計算する必要があるか否かを判断し、再計算が必要な場合は、ステップＳ４に移り、再計算が不要な場合は本フローを終了する。再計算が必要な場合は、異常によって搬送スケジュールの経路で搬送できない場合である。

ステップＳ４では、経路異常を考慮して、搬送工程を設定し直し、ステップＳ５に移る。ステップＳ５では、経路異常を考慮して、搬送スケジュールを再計算して、ステップＳ６に移る。ステップＳ６では、再計算した搬送スケジュールをサーバ用送信部４３から各ＡＧＶ３０に送信するように制御し、本フローを終了する。

このように設定部１４１は、経路異常がある場合には、移動不可部分を回避する移動経路を設定する。これによって異常がある経路は、ＡＧＶ３０が移動することを抑制することができる。

（その他の実施形態）
以上、本開示の好ましい実施形態について説明したが、本開示は前述した実施形態に何ら制限されることなく、本開示の主旨を逸脱しない範囲において種々変形して実施することが可能である。

前述の実施形態の構造は、あくまで例示であって、本開示の範囲はこれらの記載の範囲に限定されるものではない。本開示の範囲は、特許請求の範囲の記載によって示され、さらに特許請求の範囲の記載と均等の意味及び範囲内での全ての変更を含むものである。

前述の第１実施形態では、移動体は、ＡＧＶ３０によって実現されているが、ＡＧＶ３０に限るものではない。移動体は、同時刻に同じ位置に存在すると衝突や、デッドロックが発生する移動体にはすべて利用可能である。

たとえば移動体は、閉空間における搬送ロボットであってもよい。閉空間とは、移動体のみが存在できるエリアを区切り、移動体が走行する空間である。移動体は、例えば、製造現場、病院、空港およびデパート内のパトロールロボット、監視ロボット、案内ロボットおよび搬送ロボットであってもよい。

また移動体は、道路を走行する車、タクシーおよびバスのようにドライバーが自律的に運転するモビリティであってもよい。その場合は、サーバ用制御部４５によって実現されていた機能、たとえば計算部１４４および設定部１４１などを車両側に備え、車両側からサーバ４０へ目的地と経路を送信してもよい。またサーバ用制御部４５とＡＧＶ３０とが処理が分担するように構成してもよく、たとえば計算部１４４の機能をサーバ４０が有し、設定部１４１の機能をＡＧＶ３０が有して、相互に通信することで経路を決定してもよい。さらに移動体は、自動運転車のように運転の仕方を管制制御されるようなモビリティであってもよい。また移動体は、電車および飛行機であってもよい。線路を共有しながら走行する電車、および滑走路を共有しながら利用する飛行機のスケジューリングにも利用することができる。さらに移動体は、ガントリークレーンおよび荷物搬送用のエレベーターなど経路や空間を占有しながら動くものであってもよい。

前述の第１実施形態では、経路は固定されていたが、固定でなくてもよい。経路は、たとえば事前に固定している必要はなく、途中で変更になってもよい。経路が都度変わっても、それを工程に反映し、再度スケジューリング計算をすれば良い。また経路を都度変える制御方法であってもよい。したがって移動体は、無軌道ＡＧＶのように監視装置を用いて経路を計算するような移動体であってもよい。

またスケジューリング対象は経路全体であってもよく、経路が交差する交差点、経路が重複する特定経路の出入口のみでも良い。経路の交差点ごとにフォーカスを当てて、都度計算してもよい。また、その結果を搬送システムや信号機のような制御に応用することもできる。また設定部１４１は、特定経路に１つのＡＧＶ３０がある場合は、特定経路の全体を他のＡＧＶ３０の使用を禁止するように搬送工程を設定してもよい。

前述の第１実施形態では、図８に示す数式によって搬送スケジュールを決定しているが、このような数式に限るものではない。図８に示した本実施形態の数式は、一例であって、他の式によって搬送スケジュールを計算してもよい。

前述の第１実施形態では、位置検出部３３は、ＧＮＳＳ受信器を用いて、ＡＧＶ３０の位置を検出しているが、このような構成に限るものではない。たとえば電波を送受信するＩｏＴルータおよびＩｏＴタグを用いて、ＩｏＴタグをＡＧＶ３０に設け、ＩｏＴルータを複数の固定位置に設け、ＩｏＴルータと通信する電波強度でＩｏＴタグの位置、すなわちＡＧＶ３０の位置を推定してもよい。

前述の第１実施形態において、サーバ用制御部４５によって実現されていた機能は、前述のものとは異なるハードウェアおよびソフトウェア、またはこれらの組み合わせによって実現してもよい。サーバ用制御部４５は、たとえば他の制御装置と通信し、他の制御装置が処理の一部または全部を実行してもよい。サーバ用制御部４５が電子回路によって実現される場合、それは多数の論理回路を含むデジタル回路、またはアナログ回路によって実現することができる。

３０…ＡＧＶ（移動体） ３１…ＡＧＶ用受信部 ３２…ＡＧＶ用送信部
３３…位置検出部 ３４…ＡＧＶ用制御部 ４０…サーバ ４１…記憶部
４２…サーバ用受信部 ４３…サーバ用送信部 ４５…サーバ用制御部（取得部）
５０…検出装置 ５１…周辺監視部 ５２…検出装置用受信部
５３…検出装置用送信部 ５４…指示部 ６０…搬送指示装置 ６１…指示監視部
６２…搬送用受信部 ６３…搬送用送信部 ６４…入力部
１００…移動制御システム １４１…設定部 １４２…予測部 １４３…判定部
１４４…計算部 １４５…移動制御部

Claims (7)

1. 経路上を移動する複数の移動体（３０）の移動を制御する移動体制御装置であって、
   前記経路は、２つの前記移動体がすれ違えない経路であり、
   複数の前記移動体の出発地点と終着地点とを結ぶ移動経路、および前記移動経路を移動する移動工程を設定する設定部（１４１）と、
   前記移動経路および前記移動工程を入力値して、制約条件を満たしつつ所定の評価値を最小化することを目的とする混合整数計画問題を解くことによって、前記移動体の移動スケジュールを計算する計算部（１４４）と、
   前記移動スケジュールによって各前記移動体の移動を制御する移動制御部（１４５）と、を含み、
   前記制約条件には、前記経路を少なくとも前記移動体よりも大きい長さで分割した分割経路において、前記移動体が次の前記分割経路への移動が完了するまで、移動が完了前の前記分割経路は他の前記移動体による利用を禁止する衝突禁止条件があり、
   前記設定部は、少なくとも２つの前記移動体の前記移動経路が重複して、前記移動体の移動方向が対向することによって、前記移動体が干渉する可能性がある特定経路では、前記特定経路に１つの前記移動体が存在する場合には、前記移動体が存在する前記特定経路では他の前記移動体の使用を禁止するように前記移動工程を設定する移動体制御装置。
2. 前記設定部は、前記特定経路に１つの前記移動体が存在する場合には、前記移動体が存在する前記特定経路のうち前記移動体の移動方向の部分への他の前記移動体の使用を禁止し、移動方向とは反対方向の部分の使用を許可するように前記移動工程を設定する請求項１に記載の移動体制御装置。
3. 前記計算部は、前記移動経路および前記移動工程が前記設定部によって変更された場合には、新しい前記移動経路および前記移動工程を入力値して、前記移動スケジュールを計算する請求項１または２に記載の移動体制御装置。
4. 前記移動体の現在位置を取得する取得部（４５）をさらに含み、
   前記計算部は、前記移動体の現在位置と、前記移動スケジュールのおける予定位置との差が所定値より大きい場合には、前記移動スケジュールを再計算する請求項１～３のいずれか１つに記載の移動体制御装置。
5. 前記経路を移動する前記移動体以外の動作物体の移動情報を取得する取得部（４５）と、
   前記動作物体に移動を指示する指示部（５４）と、をさらに含み、
   前記設定部は、前記移動情報から前記動作物体の動きを予測して、前記動作物体を含む前記移動経路および前記移動工程を設定し、
   前記計算部は、新しい前記移動経路および前記移動工程を入力値して、前記移動スケジュールを計算し、
   前記移動制御部は、前記指示部に前記動作物体への指示を出力するように制御する請求項１～４のいずれか１つに記載の移動体制御装置。
6. 前記制約条件には、前記移動体および前記動作物体の移動の優先順位が設定された優先条件を含む請求項５に記載の移動体制御装置。
7. 前記経路における移動不可部分を取得する取得部（４５）をさらに含み、
   前記設定部は、前記移動不可部分を回避する前記移動経路を設定する請求項１～６のいずれか１つに記載の移動体制御装置。

Images