JP7228420B2 - 情報処理装置、情報処理方法、情報処理システム及びコンピュータプログラム - Google Patents

Description

本発明の実施形態は、運行計画システム、運行計画方法及びコンピュータプログラムに関する。

近年、多品種少量生産の一般化に伴い、生産工程における柔軟性を生み出すことが必要となってきている。例えば、生産ラインの各工程をモジュール化し、自由に組み替えて、工程間をＡＧＶ（無人搬送車）で搬送させることや、作業用のアーム付の移動ロボットを複数の作業場所を移動させながら作業させることが行われている。

また、物流現場の深刻な人手不足を背景として、ネット通販などの物流センターでは、省人化する取り組みが加速している。例えば、ＡＧＶや自動走行フォークリフトと、ピッキングロボットとを組み合わせることなどで、これに対応する方法などがある。

さらに、自動車の自動走行技術の進歩に伴い、無人の状態で自動車群を駐車場で自動走行させ駐車させる自動バレーパーキングや、工事現場や採掘場等で遠隔操縦された無人の建機移動体を走行させるなどの試みも、実用段階に達している。

狭いエリア内で多数の自動走行移動体の移動を効率的に制御するため、衝突やデッドロックといった移動体同士の競合を回避することが必要である。これまで、双方向に同時走行可能な複線走行路、複数の一方向ループ、及び格子状などの専用の走行路や、走行スペースを予め設置することで、これに対処しているのが一般であった。

このような専用の走行路等を用いることを前提に、ある関連技術では、全ての移動体の経路で同一走行路の逆方向の移動が発生しないように計画を策定している。しかしながら、作業者も使用する既存通路を流用して段階的な導入を進める場合には、同一走行路で双方向の移動が発生せざるを得ない形状の走行路を利用する場合、又は安全等の理由等で予め双方向の移動が発生する経路を指定する場合でも、汎用的に運行計画を立案することが可能なシステムが必要となる。上述の関連技術では、この条件での適用は困難である。

また、別の関連技術として、一台ずつ移動体の走行計画を決定（移動体を予約）し、先に予約した移動体と逆方向走行が生じないように、次の移動体の走行計画を決定するものがある。この関連技術では、移動体の予約順序に走行効率が大きく左右されて、全体の効率が悪化するという問題があった。

また、専用の走行路等を用いることは、工事コストがかかり、利用開始後の走行路レイアウトの段階的な変更も容易ではないという問題がある。

特許登録２９５３２８２号公報 特許登録３３６４０２１号公報 特許登録１９９４９４０号公報 米国特許７８７３４６９号明細書 米国特許７９２０９６２号明細書 米国特許８０６８９７８号明細書

本発明の実施形態は、移動体同士の競合を回避して、複数の移動体を効率的に運行させる運行計画システム、運行計画方法及びコンピュータプログラムを提供する。

本発明の実施形態としての運行計画システムは、複数の走行路を含む走行路ネットワークを走行する複数の移動体に対する運行計画システムであって、前記複数の移動体の位置情報と、前記走行路ネットワークの構造を表す走行路構造情報と、前記走行路ネットワークにおける複数の指定領域について、前記複数の移動体に対してそれぞれ通過する１つ以上の指定領域の順序を指定した複数の経路計画と、に基づき、前記走行路で移動体同士の競合が発生しないように、前記複数の移動体が前記走行路を走行するタイミングを指定した複数の走行タイミング計画を生成する走行タイミング計画部と、前記複数の走行タイミング計画に基づき、前記複数の移動体に対する移動指令データを送信する指令部と、を備える。

第１の実施形態に係る運用計画システムを含む全体システム構成の一例を示す図。 複数の移動体が走行路ネットワークを走行している状態の一例を示す図。 移動体同士の競合の例を示す図。 走行路構造情報の例を示す図。 走行路構造情報の他の例を示す図。 経路計画の例を示す図。 複数の移動体の各々の走行タイミング計画の例を示す図。 運行計画の一部の例を示す。 運行計画システムの処理のフローチャートを示す図。 走行タイミング計画部の詳細な処理のフローチャートを示す図。 競合チェックと回避処理の一例を示す図。 競合チェックと回避処理の他の例を示す図。 走行タイミング計画部の探索処理のイメージ図。 運用計画装置のハードウェアブロック図。 第２の実施形態に係る運用計画システムを含む全体システム構成の一例を示す図。 第３の実施形態に係る運用計画システムを含む全体システム構成の一例を示す図。

以下、図面を参照しながら、本発明の実施形態について説明する。

図１は、第１の実施形態に係る運行計画システムを備えた全体システム構成の一例を示す。全体システム構成は、運行計画システム１、複数の移動体３０１＿１～３０１＿Ｎ、複数のセンサ４０１＿１～４０１＿Ｍ、複数の通信装置５０１＿１～５０１Ｋを備える。運行計画システム１は、運行計画装置１００、運行管理装置２００を備える。任意の移動体を移動体３０１と記載する。任意のセンサをセンサ４０１と記載する。任意の通信装置を通信装置５０１と記載する。

運行計画装置１００と運行管理装置２００とは、同じ計算機システム上に存在していてもよい。あるいは、運行計画装置１００と運行管理装置２００とが、異なる計算機システム上に存在し、互いにネットワークを介して接続されていてもよい。

運行計画システム１は、例えば狭いエリアに複数の走行路により構成した走行路ネットワークを配置して、多数の移動体が走行路ネットワークを低速で自動走行する場合に、デッドロック又は衝突等の競合を起こさないように、全体として効率良く運行を制御する。

移動体３０１＿１～３０１＿Ｎは、ＡＧＶ（無人搬送車：Automatic Guided Vehicle）、自律型の移動ロボット、自動走行の車両（例えば自動走行車）などの、自動で移動可能な移動体である。移動体３０１＿１～３０１＿Ｎは、例えば、工場内、倉庫内、施設敷地内などのエリアに配置された走行路ネットワークを走行する。移動体３０１＿１～３０１＿Ｎは一例として蓄電池（バッテリー）を搭載し、バッテリーに蓄積された電力を用いて動作する。

図２は、走行路ネットワークにおいて複数の移動体の運行を制御する様子を模式的に示した上面図である。ある施設のフロアにガイドテープ１０による走行路ネットワークが配置されている。直線のガイドテープ１０を走行路として組み合わせることで、走行路ネットワークが構成されている。この例では、個々の走行路は直線の形状であるが、これは一例に過ぎない。走行路は曲線の形状でもよいし、直線と曲線の組み合わせた形状でもよい。なお、ガイドテープ以外に、走行路上の要所にマーカーを配置する方法や、移動体自身が自己位置を検知して仮想的な走行路ネットワーク上を走行する方法など、複数の方法がある。走行路ネットワークの実現方法はここでは限定しない。

移動体１２Ａ、１２Ｂ、１２Ｃ、１２Ｄ、１２Ｅ、１２Ｆ、１２Ｇ、１２Ｈ、１２Ｉ、１２Ｊ、１２Ｋ、１２Ｌは図１の移動体３０１に対応し、ガイドテープ１０に沿って前方向、後方向又は前後両方向に移動できる。移動体は前後を反転するように回転可能であってもよい。また、走行路の形状に依存して、移動体は、斜め方向など、前後以外の方向に移動できてもよい。

走行路の端部、走行路同士の交差部（例えば分岐合流部）の近傍、走行路の端部、走行路の途中（走行路の両端の間）、その他の任意の箇所には搬入口１３Ａ、１３Ｂ、１３Ｃ、１３Ｄ、１３Ｅ、１３Ｆ及び棚１４Ａ、１４Ｂ、１４Ｃ、１４Ｄ、１４Ｅが設けられている。走行路の端部、走行路同士の交差部の近傍、走行路の途中（走行路の両端の間）、その他の任意の箇所に棚１４Ａ～１４Ｅ、搬入口１３Ａ～１３Ｆの全部又は一部には、図１のセンサ４０１及び通信装置５０１（図２において図示せず）が配置されている。

移動体１２Ａ～１２Ｌは、図１の運行計画システム１の管理の元、各走行路を移動し、予め指示された作業を行う。例えば、搬入口から荷物を受け取り、受け取った荷物を棚に運び、積み上げる。また、棚から荷物を積み降ろし、荷物を搬入口まで運ぶ。図における二重丸は荷物を模式的に表している。このような移動及び作業を各移動体は、運行計画システム１から与えられた移動指令データに基づき自動で行う。なお、作業は荷物の搬送に限定せず、また、作業を行わずにただ移動する場合もあり得る。

本実施形態に係る運行計画装置１００は、各移動体が行うべき作業の内容及び作業の順序に基づき各移動体が走行すべき経路を表した経路計画を生成し（各移動体の経路計画が予め与えられている場合もある）、経路計画に基づき、各移動体に衝突又はデッドロックを生じさせないように、各移動体が各走行路を走行するタイミングを定めた走行タイミング計画を生成する。運行管理装置２００は、各移動体の走行タイミング計画に基づく移動指令データを各移動体に送信することで、各移動体の運行を制御する。また、運行管理装置２００は、各移動体の走行状態を検知して、各移動体の運行を管理する。

ここでデッドロックとは、任意の移動体が走行ネットワークにおける任意の交差部（例えば分岐合流部）又は走行路の端部に移動できない状態になることである。衝突は、移動体が別の移動体に接触することである。

図３（Ａ）はデッドロックの例、図３（Ｂ）は衝突の例を示す。図３（Ａ）では同一の走行路を２つの移動体が互いに逆方向に走行している。２つの移動体は前進のみ可能であるとする。この場合、２つの移動体は任意の交差部又は端部に移動できなくなり、デッドロックが発生する。図３（Ｂ）では、同一の走行路を２つの移動体が同じ方向に走行しているが、後ろの移動体が前の移動体よりも速度が速いため、後ろの移動体が前の移動体に衝突する。

このようにデッドロック又は衝突が起こることを、移動体が競合する（又は干渉する）と表現する。但し、競合はこの例に限定されない。例えば交差部（分岐合流部）に２つの移動体が同時に到着することでもよい。走行路につながる交差部に１台以上の移動体が待機している状態で他の移動体が当該走行路を走行することでもよい。

図１の運行計画システム１は、各移動体に競合（衝突又はデッドロック等）を生じさずに、各移動体の運行を効率的に行うことを実現するものである。

図１の運行計画装置１００は、走行路構造記憶部１０１、経路計画記憶部１０２、運行計画記憶部１０３、状態記憶部１０４、走行タイミング計画部１０５、更新位置決定部１０６、指令部１０７、再計画判定部１０８、経路計画部１０９及び通信部１１０を備える。本装置１００のユーザから各種の指示又はデータの入力を行う入力装置（例えばマウス、キーボード、タッチパネル）が設けられていてもよい。また、各記憶部内のデータ又は各部で生成されるデータを表示する表示装置（例えば液晶ディスプレイ、有機エレクトロルミネッセンスディスプレイ）が本装置１００に設けられてもよい。

運行計画装置１００の通信部１１０は、運行管理装置２００の通信部２０１と通信する。通信部１１０及び通信部２０１間の通信は、無線による通信でも有線による通信でもよい。運行管理装置２００の通信部２０１は、運行計画装置１００の通信部１１０及び移動体３０１と通信する。通信部２０１と移動体３０１との通信は無線通信である。但し、有線通信を排除しない。一部又は全ての移動体３０１が通信部２０１と通信できなくてもよい。但し、この場合でも、移動体３０１は路側に設置された通信装置５０１（後述）と通信できる。移動体３０１は、通信装置５０１の通信可能な範囲内で、通信装置５０１と通信できる。運行計画装置１００と運行管理装置２００が同一の装置である場合、通信部１１０を省略してもよい。

走行路構造記憶部１０１は、走行路ネットワークの構造を表す情報（走行路構造情報）を内部に記憶している。走行路構造情報は、例えば、複数のノードと、ノード間を接続する複数のアーク（走行路）とを含むグラフ構造として表現できる。

図４は走行路構造情報の例を示す。ノード間を結合する直線によって個々の走行路は表されている。図４（Ａ）の各円がノードを表し、円間をつなぐ線分がアーク（走行路）を表す。ノードは、走行路の端部、及び走行路同士の交差部を表す。走行路ネットワークにおいて予め指定した箇所を指定領域と称する。ユーザが任意に定めた箇所を指定領域とすることも許容される。荷物の積み上げ・積み降ろし場所、待機場所等の任意の箇所を指定領域として指定できる。一例として、交差部につながる走行路端部、交差部につながらない走行路端部（走行路の行き止まり）がこのような場所である。その他、走行路の任意の箇所（例えば走行路の両端間の任意の領域）を指定領域としてもよい。交差部そのものを指定領域としてもよい。移動体は、指定領域を通過したり、一時的に滞在したりする。移動体が一時的に滞在する例としては、作業のために一時的に停止、他の移動体が走行路を通過するのを待つため一時的に停止、行うべき作業が存在せず次の作業が発生するまで停止すること、移動体に搭載されたバッテリーの充電のための待機、移動体が自動運転車の場合の駐車などがある。

図４（Ｂ）は、ノードの詳細情報として、ノードＩＤ、Ｘ座標、Ｙ座標を表す。例えば、ノードＡの座標は（Ｘ，Ｙ）＝（２０，２０）である。

図４（Ｃ）は、走行路の詳細情報として、走行路ＩＤ、走行路の両端のノードのＩＤを示す。例えばノードＡ、Ｂ間の走行路のＩＤは１、走行路の両端のノードはＡ及びＢである。ノード間の距離（アークの距離）が走行路ＩＤに対応づけて走行路構造情報に含めてもよい。あるいは、アークの距離をその両側のノードの位置に基づき計算してもよい。

図５は、走行路構造情報の他の例を示す。図５（Ａ）は、図４の走行路構造情報から一部のノードを省略して、特定のノードのみを残したものである。特定のノードは、荷物の積み上げ・積み降ろし場所や待機場所などの指定領域又はその近傍のノードである。

図５（Ｂ）は、各走行路の走行路ＩＤ、走行路の両端のノードのＩＤ、各走行路を走行するのに要する標準時間を示す。例えば、ノードＢ及びＣ間の走行路の走行路ＩＤは１であり、走行路の両端のノードはＢ及びＣであり、走行路を走行するのに要する標準時間は１８０である。時間の単位は何でもよい。

経路計画部１０９は、予め決められた各移動体の行うべき作業の内容と作業の順序に関する情報に基づき、各移動体が通過する複数の指定領域の通過順序を指定した経路計画を生成し、生成した経路計画のデータを経路計画記憶部１０２に格納する。経路計画の生成方法は任意でよいが、一例として、複数の移動体が同一走行路を逆方向に進行する走行距離が少なくなることを評価基準又はその一部として、各移動体の経路計画を生成してもよい。経路計画は、外部の装置が生成したもの又はユーザが生成したものでもよい。この場合、経路計画部１０９は、当該経路計画を取得して、経路計画記憶部１０２に格納する。経路計画部１０９は、通信部１１０を介して外部の装置から経路計画のデータを受信してもよい。経路計画部１０９は、ユーザが操作する入力装置を介して経路計画のデータを取得してもよい。

経路計画記憶部１０２は、各移動体の経路計画のデータを内部に記憶する。

図６（Ａ）に、ある移動体の経路計画の一例を示す。この例では、移動体が図４（Ａ）の指定領域Ｌから出発し、Ｋ，Ｉ，Ｇ，Ｅ，Ｃ，Ａを経由して、指定領域Ｂに行き、次にＡ，Ｃ，Ｄ，Ｆ，Ｅ，Ｇ，Ｈ，Ｊ，Ｉ，Ｋを経由して指定領域Ｍに行き、再びＫ，Ｉ，Ｇ，Ｅ，Ｃ，Ａを経由して、指定領域Ｂに行き、またＡ，Ｃ，Ｄ，Ｆ，Ｅ，Ｇ，Ｈ，Ｊ，Ｉ，Ｋを経由して、指定領域Ｌに戻る。ここでは便宜上、ノードのＩＤを用いて指定領域を表現している。ノードが交差部に対応する場合、当該ノードのＩＤを用いた指定領域は、当該ノードが表す交差部につながる走行路端部（交差部に入る手前）を表すとして内部的に解釈する。例えば、指定領域Ｌの次の指定領域Ｋは、ノードＫが表す交差部に入る直前の走行路ＬＫの端部を指すと解釈する。ここで走行路ＬＫとはノードＬとノードＫ間の走行路である。以下の説明でもノードＩＤを用いて指定領域を示すが、この場合もここで行った説明と同様の意味であるとする。

上記の例の経路は、指定領域を往復するループ状の経路を含んでいる。この経路計画は１つの移動体についてのものであり、他の各移動体についても経路計画が用意されている。なお経路はループ状である必要はない。各移動体が長時間に渡って異なる走行路を走行してもよい。

荷物の搬送を目的とした移動体や、移動しながら各種作業を行う移動ロボットなどの場合は、経路計画において作業を行う指定領域に対して、当該作業の情報が追加されてもよい。

図６（Ｂ）は、この場合の経路計画の例を示す。この例では、指定領域ＬとＭで棚からの荷物の積み込み作業を行うことを指示する情報（Ｌｏａｄ）、指定領域Ｂで荷物を降ろす作業を行うことを指示する情報（Ｕｎｌｏａｄ）が挿入されている。ここで、Ｌｏａｄは荷物積み作業、ＵｎＬｏａｄは荷物降し作業を示す。なお、積み上げ等の作業を行う際の作業対象の棚等は移動体から見て左方向、右方向、前方向、斜め方向などどの方向にあるかは予め定められていてもよいし、移動体がセンサ等で自動検出してもよい。

状態記憶部１０４は、各移動体の走行状態を表す情報、及び移動体の固有の情報を内部に記憶している。

移動体の走行状態を表す情報として、各移動体の位置情報、移動体が搭載するバッテリーの残存電力、移動体が荷物を保有しているか否か（移動体が荷物を搬送する場合）、搬送中の荷物の種類や数等がある。位置情報は、移動体の現在位置（最も直近に検知された位置）、及び、各移動体がこれまで通過した位置の履歴情報を含む。当該走行状態を表す情報は、後述するように運行管理装置２００の状態検知部２０２（後述）により取得される。

移動体の固有の情報として、例えば、標準速度、最大速度、最低速度、移動体のサイズ、移動可能な方向など、移動体の仕様情報がある。また、バッテリーの残存電力に応じた標準速度の変化率がある（例えば、残存電力が少ないほど、標準速度が低くされる）。また、荷物の搬送を目的とした移動体であれば、荷物の積み降しに要する作業時間の情報（例えば所定個数の荷物を積み上げ又は積み下ろすのに要する時間）がある。ここに挙げた情報は一例に過ぎず、他の情報でもよい。

走行タイミング計画部１０５は、各移動体の経路計画を変更しない前提条件の下で、計画対象となる各移動体について、競合（衝突又はデッドロック）を発生させないように走行タイミング計画を生成する。走行タイミング計画は、一例として、各指定領域に対する到着時刻又は出発時刻を特定可能な情報を含む。例えば、指定領域への到着時刻、指定領域の出発時刻、指定領域における滞在時間、指定領域間の移動時間などある。

走行タイミング計画の計画対象となる移動体は、一例として運行管理装置２００により運行管理される全ての移動体である。走行タイミング計画部１０５は、各移動体の走行タイミング計画の生成のために、各移動体の経路計画、及び、各移動体の情報（走行状態を表す情報及び固有情報）を用いる。

走行タイミング計画部１０５は、後述する再計画判定部１０８により再計画を行うことが決定された場合に、各移動体の走行タイミング計画を再生成する。再生成した走行タイミング計画で、前回生成した走行タイミング計画を更新する。走行タイミング計画の再生成は、移動体の経路計画で示される経路のうち、まだ当該移動体がまだ移動していない経路部分（後述するように移動体の経路のうち、当該移動体に対して決定される更新位置以降の経路部分）に対して行う。

図７は、走行タイミング計画部１０５により生成された走行タイミング計画の一例を示す。３つの移動体（ＡＧＶ０、ＡＧＶ１、ＡＧＶ２）の走行タイミング計画の例が示される。

“ＭＯＶＥ”は、移動を指示するコマンド（移動コマンド）であり、移動時間を引数として有する。例えば、ＡＧＶ０の走行タイミング計画において、ＭＯＶＥ－Ｋ－Ｉ－３７．０は、指定領域Ｋ（ノードＫが表す交差部につながる走行路ＬＫの端部）から指定領域Ｉ（ノードＩが表す交差部につながる走行路ＫＩの端部）に３７単位時間で移動することを示す。３７単位時間が、引数として指定される移動時間である。

“ＷＡＩＴ”は移動先の指定領域（ノードの手前）で待機することを指示するコマンド（待機コマンド）である。例えばＭＯＶＥ－Ｉ－Ｇ－１０．０，ＷＡＩＴ－５２．０，とコマンドが続いた場合は、指定領域Ｉから指定領域Ｇに移動した際に、指定領域Ｇ（ノードＧの手前）で５２単位時間待機することを示す。したがって、この場合、ＭＯＶＥ－Ｉ－Ｇ－１０．０は、指定領域Ｇまで１０単位時間で移動し、その場で５２単位時間待機したら、次のコマンドに従って移動する（ノードＧが表す交差部に入り、さらに次の走行路へ入る）。待機場所は、指定領域でなくてもよい。待機場所は、交差部から離れた位置であればよい。

本例では、移動体ＡＧＶ０の経路計画は、図４（Ａ）の指定領域Ｌから出発して、他の指定領域を経由して指定領域Ｂに行き、次に他の指定領域を経由してＭに行き、再び他の指定領域を経由してＢに行き、また他の指定領域を経由してＬに戻る経路を指定する。

移動体ＡＧＶ１の経路計画は、図４（Ａ）の指定領域Ｂから出発して他の指定領域を経由して指定領域Ｍに行き、再度他の指定領域を経由して指定領域Ｂに戻ることを２回反復数する経路を指定する。

移動体ＡＧＶ２の経路計画は、図４（Ａ）の指定領域Ｋから出発して他の指定領域を経由して指定領域Ｂに行き、指定領域Ｌを含む他の指定領域を経由して再度Ｂに行き、他の指定領域を経由して指定領域Ｋに戻る経路を指定する。

走行タイミング計画部１０５は、これらのＡＧＶ０、ＡＧＶ１、ＡＧＶ２の経路計画（図６参照）が与えられた条件の下で、後述する探索アルゴリズムを実行することにより、図７に示したようなＡＧＶ０、ＡＧＶ１、ＡＧＶ２の走行タイミング計画を生成する。これらの走行タイミング計画では、例えば他の移動体が通過するまで交差部の手前で移動体を待機させるなどの時間調整を行うことで、競合（衝突又はデッドロック等）を発生させずに、ＡＧＶ０、ＡＧＶ１及びＡＧＶ２の各指定場所の到着時刻又は出発時刻等を調整する。

走行タイミング計画部１０５は、ＭＯＶＥコマンドで引数として指定する移動時間を算出するに当たっては、図４の走行路構造情報における走行路毎の距離を、移動体がその標準速度で移動すると仮定してもよい。走行路の曲率又は傾斜などに応じて、移動体の速度が標準速度から変化する場合を考慮して、図５の走行路構造情報のように走行路に対して標準時間を予め与えてもよい。この場合、標準時間で移動できるように移動体は移動速度を最大速度と最低速度の間で自律的に制御してもよい。また、バッテリーの残存電力に応じた標準速度の変化率等を与えて標準速度を補正することもあり得る。また、荷物の搬送を目的とした移動体であれば、荷物搬送中は標準速度を速い値又は遅い値に補正してもよい。また、走行実績データを元に、各走行路を走行する標準時間を補正しても良い。このように走行タイミング計画部１０５は、速度に関する条件を満たすように移動時間を算出する。

走行タイミング計画部１０５は、荷物の搬送を目的する移動体や、荷物の積み降し等を含む各種作業を行う移動ロボットに対しては、荷物の積み降し等に要する作業時間の情報等も反映させて、走行タイミング計画を生成する。前述した経路計画（図６（Ｂ）参照）のように、当該指定領域で行う作業内容が指定されていてもよい。また、指定領域と移動体の種類との組に応じて、予め移動体が指定領域で行う作業内容が決まっていてもよい。

図７に示した走行タイミング計画の例は、指定領域ＭとＬで荷物の積み込みに４０単位時間、指定領域Ｂで荷物を降しに１３０単位時間を要することを仮定している。荷物の積み込み及び積み降しの作業時間は、荷物の種類・個数、又は移動体の種類に応じた値が予め与えられている。この値は、状態記憶部１０４に格納されていてもよいし、経路計画に付与されていてもよい。また、走行実績データを元に作業時間を補正しても良い。移動体に対して当該作業の実施を指示するコマンドを、走行タイミング計画において当該作業を行う場所の指定領域に対して付与してもよい。あるいは、そのような指示のコマンドは予め移動体の内部にプログラムコードとして埋め込まれていてもよい。

図７に示した走行タイミング計画のフォーマットは、移動体のコマンドを並べた形式で表現されていたが、これは一例に過ぎない。走行タイミング計画のフォーマットは特に限定はしない。各移動体の経路計画の一部の指定領域、もしくは全ての指定領域に対して、移動体が到着すべき時刻及び出発すべき時刻を特定可能な情報が含まれていればよい。

走行タイミング計画部１０５は、各移動体の走行タイミング計画と、各移動体の経路計画とに基づき、各移動体の運行計画を生成する。具体的には、移動体の経路計画の一部もしくは全ての指定領域に、当該移動体が到着すべき時刻及び出発すべき時刻を特定可能な情報を設定することにより、各移動体の運行計画を生成する。

運行計画記憶部１０３は、走行タイミング計画部１０５により生成された各移動体の運行計画を内部に記憶する。

図８に、図７の移動体（ＡＧＶ０）の運行計画の一部を示す。図６の経路計画に対して図７のＡＧＶ０の走行タイミング計画の時刻情報が付与されている。ＡＧＶ０は指定領域Ｌを時刻０に出発し、指定領域Ｋに時刻７０に到着してそのまま停止することなく出発し（すなわち指定領域Ｋを時刻７０で通過）、指定領域Ｉを時刻１０７で通過し、指定領域Ｇに時刻１１７に到着し、その場で５２単位時間待機し、時刻１６９に出発する。図８に示した運行計画のフォーマットは一例に過ぎず、フォーマットは特に限定されない。例えば、運行計画は、走行タイミング計画と経路計画とを単に対応づけたものでもよい。

指令部１０７は、走行タイミング計画部１０５により決定された各移動体走行タイミング計画に基づく移動指令データを、通信部１１０を介して、運行管理装置２００に送信する。運行管理装置２００は、通信部２０１を介して、運行計画装置１００の通信部１１０から各移動体の移動指令データを受信し、各移動体に移動指令データを各移動体に送信する。

各移動体に送信される移動指令データの形態の第１の例として、各移動体の経路計画上の一部もしくは全ての指定領域に対する到着時刻及び出発時刻を特定可能な情報を指示する形態がある。例えば、図７の走行タイミング計画の場合、計画そのものがコマンドの列であるため、これをそのまま移動指令データとして用いてもよい。あるいは、図７とは別のフォーマットを有する走行タイミング計画を生成する場合、走行タイミング計画から移動体が解釈可能なコマンド列を生成し、このコマンド列を移動指令データとしてもよい。

移動指令データの形態の第２の例として、各走行路の移動時間と待機時間（指定領域での待機）に相当する情報を指示する形態がある。

上述した２つの例のいずれの場合でも、各移動体は移動指令データに従って、自身で走行を制御する。運行管理装置２００が、各移動指令データに基づき、各移動体に待機中の指定領域を出発することを指示するコマンド、及び、次に待機のため停止すべき指定領域を指定するコマンドを、各移動体に送信することを逐次的に反復してもよい。この場合、各移動体は移動指令データとして運行管理装置２００からコマンドを逐次的に受信及び実行することを繰り返す。

移動指令データの形態の第３の例として、走行タイミング計画から、経路計画上で移動体が複数通過する交差部を特定し、当該交差部を各移動体が通過する順番を、各移動体に指示してもよい。この場合、当該交差部を指定領域として設定し、指定領域を通過する順番を指定してもよい。各移動体に通過順序を厳守させることで、走行タイミング計画における各指定領域への到着時刻と現実の到着時刻が前後にずれたとしても、衝突又はデッドロック等の競合が発生しないことを保証できる。なお、指定領域に対する各移動体の通過順序は、各移動体の走行タイミング計画を比較することで算出できる。

図７における各移動体（ＡＧＶ０、ＡＧＶ１、ＡＧＶ２）の走行タイミング計画に基づき、ノードＫが表す交差部に設定した指定領域（指定領域Ｋａと記載する）を通過（到着）する順番と、時刻（経過時間）とを指示するコマンドの例を下記に示す。
ＡＧＶ２ ０
ＡＧＶ０ ７０
ＡＧＶ１ ２０５
ＡＧＶ１ ４５３
ＡＧＶ２ ５９３
ＡＧＶ２ ７７３
ＡＧＶ０ ９２０
ＡＧＶ０ １１６８
ＡＧＶ１ １２１８
ＡＧＶ１ １４６６
ＡＧＶ２ １６０６
ＡＧＶ０ １９２５

上記の例では、最初に（時刻０の時点で）ＡＧＶ２が指定領域Ｋａを通過し、次に時刻７０の時点でＡＧＶ０が通過し、その次に、時刻２０５の時点でＡＧＶ１が通過する。以降同様にして、解釈される。

指定領域の通過順序の制御方法としては、一例として、運行管理装置２００が移動コマンドの実行を管理する方法がある。運行管理装置２００は移動指令データの実行（コマンドのの実行）を管理する制御部を備える。例えば、運行管理装置２００は、ＡＧＶ２が先に通過する必要のある指定領域にＡＧＶ０が先に到着することが見込まれた場合は、ＡＧＶ２が通過するまで、当該指定領域の手前もしくは指定領域から離れた位置でＡＧＶ０を待機させる。または、ＡＧＶ０の速度調整をして、当該指定領域におけるＡＧＶ０の到着時刻（通過時刻）を遅らせる。このような制御を待機コマンドや速度調整コマンド（例えば減速コマンド）を移動体に送信することで行う。

制御方法の他の例として、運行管理装置２００は当該指定領域を最後に通過した移動体の識別情報（ＩＤ）を、状態検知部２０２を介して検知及び記憶し、当該ＩＤを他の各移動体に送信する。各移動体は、運行管理装置２００から受信されるＩＤに基づき、自移動体に先行して通過すべき移動体が指定領域を通過したかチェックする。例えば、上記のコマンド例における
ＡＧＶ０ ７０
ＡＧＶ１ ２０５
ＡＧＶ１ ４５３
の場合、ＡＧＶ１は、最初に指定領域Ｋａを通過する前にＡＧＶ０が先に通過しているか否かを運行管理装置２００から受信されるＩＤに基づき確認し、ＡＧＶ０が先に通過していることを確認した後に、指定領域Ｋを通過する。また、その後は、直前に（最後）に指定領域Ｋａを通過したのが自移動体であることを確認した後に、再度、ＡＧＶ０は指定領域Ｋａを通過する。

再計画判定部１０８は、運行計画記憶部１０３に記憶されている運行計画と、状態検知部２０２により検知された移動体の走行状態とを比較して、再計画を行うべきか否かを判定する。再計画とは、運行計画の更新、すなわち経路計画及び走行タイミング計画の少なくとも後者の更新を意味する。再計画判定部１０８は、少なくとも１台の移動体について、運行計画を守ることができないと判断した場合は、再計画トリガーを発生させる。また、新規に行うべき作業や新規に運ぶべき荷物が発生するなどの外部要因により再計画が必要になった場合も再計画トリガーを発生させる。再計画は、計画対象となる全ての移動体が対象となる。以下、運行計画が守れない例を、第１の例及び第２の例として示す。

（第１の例）各移動体の走行タイミング計画における指定領域に到着する時刻（到着予定時刻）もしくは出発する時刻（出発予定時刻）と、各移動体の走行状態（移動体の現在位置、移動体が最後に通過または出発した指定領域など）とを比較する。そして、移動体が到着予定時刻までに到着できない、または移動体が到着予定時刻に対して閾値時間以上の到着の遅れが発生することが確定した時点で、再計画トリガーを発生させる。この判断を行うに際して、移動体が走行路を最大可能速度で移動する又は標準速度で移動するなど、種々の仮定をおいてもよい。

（第２の例）として、各移動体の走行タイミング計画における指定領域を各移動体が通過する順番と、各移動体の現在位置、もしくは最後に通過又は出発した指定領域とを比較する。そして、走行タイミング計画における指定領域の通過順番において先行すべき移動体が到着する時刻（到着予定時刻）に閾値時間以上遅れることが確定した時点で、再計画トリガーを発生させる。例えば、先行すべき移動体が走行路で走行可能な最大速度で移動しても到着予定時刻に間に合わない場合は、閾値時間以上遅れることが確定したと判断できる。なお、第２の例は、先行すべき移動体に着目すれば、先行すべき移動体が指定領域への到着が遅れることにより再計画トリガーを発生させることになり、第１の例と同じである。

更新位置決定部１０６は、再計画判定部１０８により再計画を行うことが決定された場合に、各移動体に対して当該運行計画を更新すべき位置（更新位置）を決定する。つまり、移動体は更新位置に達するまで更新前の運行計画（更新前の走行タイミング計画）で運行し、更新位置に達した後は、更新後の運行計画（更新後の走行タイミング計画）に従って動作する。

更新位置の例として、各移動体が運行管理装置２００と通信部２０１を介してリアルタイムに通信できる場合は、任意の位置（例えば移動体の現在位置、あるいは、演算に要する時間を考慮して、一定のマージンを加えた後の時刻における位置など）でよい。

移動体が指定領域又はその近傍に配置されている通信装置５０１を介してのみ運行管理装置２００と通信できる場合は、当該指定領域又はその近傍の位置を、更新位置とする。通信装置５０１は指定領域又はその近傍でなく通信装置５０１が走行路の途中に配置されていてもよい。通信装置５０１と通信可能な範囲であれば、更新位置は、指定領域又はその近傍の位置でなくてもよい。移動体が走行路の途中で停止すると他の移動体の走行を妨害する可能性（例えば後ろからくる移動体と衝突する可能性）などがある場合は、移動体が現在向かっている交差部の手前（指定領域）を更新位置とするのがよい。

経路計画部１０９は、再計画判定部１０８により再計画を行うことが決定された場合に、各移動体について各移動体の更新位置を起点とした経路計画を生成する。

一例として、現在の経路計画において更新位置以降の経路部分に対する計画をそのまま更新後の経路計画とする。すなわち、移動体の経路計画に示される経路のうち、まだ移動していない経路の計画部分を特定し、特定した部分を更新後の経路計画とする。つまり、現在の経路計画において更新位置以降の部分に対する計画をそのまま切り出して、更新後の経路計画とする。例えば、現在の経路計画が図６（Ａ）の経路計画の場合において、移動体の現在位置が指定領域Ｅ（ノードＥが表す交差部の手前）であり、次の移動先がノードＣ（ノードＣが表す交差部の手前）だとする。この場合、移動していない経路の計画部分（更新後の経路計画）は、図６（Ａ）の最初の４つのノードＬ、Ｋ、Ｉ、Ｇを除去して以下のようになる。

（更新後の経路計画）
Ｅ，Ｃ，Ａ，Ｂ，Ａ，Ｃ，Ｄ，Ｆ，Ｅ，Ｇ，Ｈ，Ｊ，Ｉ，Ｋ，Ｍ，Ｋ，Ｉ，Ｇ，Ｅ，Ｃ，Ａ，Ｂ，Ａ，Ｃ，Ｄ，Ｆ，Ｅ，Ｇ，Ｈ，Ｊ，Ｉ，Ｋ，Ｌ，Ｋ，Ｉ，Ｇ，Ｅ，

あるいは、他の例として、経路計画部１０９は、再計画判定部１０８により再計画を行うことが決定された場合に、各移動体の現在位置、もしくは各移動体の更新位置の情報を元に、複数の移動体が同時に逆方向に進行する走行路（走行区間）の合計距離が少なくなることを評価基準又はその一部として、各移動体の経路計画を生成してもよい。

あるいは、さらに他の例としては、移動体の現在位置と移動体が行うべき作業内容とに応じて予め利用可能な経路計画の選択肢が複数与えられている場合、移動体の更新位置と残りの作業内容とに基づき、いずれかの選択肢を選択してもよい。その他、予め与えられたアルゴリズムにより新たな経路計画を生成する方法もある。経路計画の更新の方法はここでは特に限定せず、既存の経路計画手法を用いてもよい。

走行タイミング計画部１０５は、更新後の経路計画に基づき、走行タイミング計画を再生成（更新）する。走行タイミング計画部１０５は、更新後の走行タイミング計画における各指定領域に対する時刻情報を更新後の経路計画に付与することにより、運行計画を再生成する。走行タイミング計画部１０５は、再生成した運行計画によって運行計画記憶部１０３の運行計画を更新する。

指令部１０７は、更新された走行タイミング計画に基づく移動指令データを運行管理装置２００に送信する。運行管理装置２００は、各移動体が当該更新位置に存在するときに、各移動体に移動指令データを送信する。

運行管理装置２００は、運行計画装置１００から受信した各移動体の移動指令データに従って、各移動体を走行させるための実行管理と、各移動体の走行状態の管理とを行う。

運行管理装置２００の通信部２０１は、移動体３０１＿１～３０１＿Ｎ及び運行計画装置１００と通信する。通信は無線でも有線でもよい。

運行管理装置２００の状態検知部２０２は、通信装置５０１又はセンサ４０１を用いて、移動体の走行状態を表す情報を取得する。状態検知部２０２は、通信部２０１を用いて、移動体の走行状態を表す情報を取得してもよい。状態検知部２０２は、通信部２０１を介して各移動体の走行状態を表す情報を運行計画装置１００に送信する。各移動体の走行状態を表す情報は、各移動体の走行状態が検知された時刻を含んでもよい。

センサ４０１は、移動体の状態を検知するためのセンサである。通信装置５０１は通信部２０１と比べて近距離で移動体と無線通信する装置である。センサ４０１及び通信装置５０１は、例えば、走行路の一時停止の発生する可能性のある特定の場所に配置される。当該特定の場所は一例として指定領域又はその近傍である。

センサ４０１は、一例として近接センサ、圧力センサ、又は光電センサ等の路側センサである。センサ４０１は、当該特定の場所における移動体の到着、通過、方向、荷物の搭載有無等を検知する。センサ４０１は、施設の天井に設けられたカメラでもよい。この場合、カメラで天井から俯瞰するように施設内を撮影する。また、通信装置５０１は、例えば、近接無線通信、赤外線通信など比較的近距離で通信を行う装置である。通信装置５０１は、通信範囲内に存在する移動体と無線通信できる。

センサ４０１は、移動体から検知した情報を表す信号を状態検知部２０２に送信する。通信装置５０１は、移動体から受信した情報を状態検知部２０２に送信する。

状態検知部２０２は、センサ４０１又は通信装置５０１から受信した情報に基づき、移動体の走行状態を特定する。センサ４０１がカメラの場合、状態検知部２０２は、撮影した画像に基づき、各移動体の位置を特定する。センサ４０１又は通信装置５０１を用いることで、移動体が通信部２０１と通信できない場所に存在するときでも、移動体の走行状態を検知できる。

移動体の走行状態の例として、各移動体の位置（現在位置）、各移動体が指定領域を通過した時刻、各移動体の進行方向、各移動体が荷物を保有しているか否か（各移動体が荷物を搬送する場合）などがある。

移動体が自装置で自己位置推定を行う機能を有する場合に、状態検知部２０２は、当該移動体が推定した位置情報を、通信部２０１又は通信装置５０１を介して、取得してもよい。自己位置推定の例としては、デッドレコニング、ＳＬＡＭ、ＧＰＳ等の手段を用いるものがある。

また、移動体が通過する可能性のある特定の場所に、無線タグ又はバーコードなどの位置検知用のマーカーを設置してもよい。当該特定の場所は一例として指定領域又はその近傍である。この場合、移動体が、当該マーカーを検知することで、当該場所への到着もしくは通過を、移動体自体が検知できる。移動体は、当該検知した情報を、通信部２０１又は通信装置５０１を介して、運行管理装置２００に送信する。

各移動体３０１は、運行管理装置２００から移動指令データを受信し、移動指令データに従って、走行路上を自動走行する。自動走行の手段としては、例えば、前述した図２に示したように、予めフロアにガイドテープを貼っておき、移動体がガイドテープに沿って走行することがある。他の手段として、マーカーで位置を補正しながらデッドレコニング（Dead Reckoning）で一定距離を走行することを反復したり、指定領域間をＳＬＡＭ（Simultaneous Localization And Mapping）等を用いて移動体が自律走行することがある。ここで述べた以外の手段でもよい。

図９は、運行計画システム１の全体の動作のフローチャートである。予め各移動体の経路計画が与えられており、走行タイミング計画部１０５によって走行タイミング計画が生成され、経路計画に当該走行タイミング計画の時刻情報を付与した運行計画が生成されているとする。各移動体は走行タイミング計画に基づく移動指令データに基づき運行しているとする。なお、運行計画システム１の動作開始時（走行タイミング計画がまだ作成されておらず、各移動体が初期位置で停止している）の動作については適宜補足説明を追加することで補う。

運行管理装置２００の状態検知部２０２が、各移動体の位置と進行方向を検知する（ステップ１１）。なお、運行計画システム１の動作開始時の場合、各移動体の初期位置と向きを検知すればよい。なお、その場回転や全方向移動が可能な移動体の場合、進行方向の検出を行わない場合もあり得る。

更新位置決定部１０６が、各移動体の現在の運行計画に基づき、各移動体の運行計画を更新する位置（更新位置）を移動体ごとに決定する（ステップ１２）。なお、運行計画システム１の動作開始時の場合は、各移動体の運行計画はまだ生成されていないため、更新位置は各移動体の初期位置とすればよい。

経路計画部１０９は、各移動体について更新位置を起点とした経路計画を生成、もしくは予め用意された経路計画の一部を選択・抽出する。生成もしくは選択・抽出した経路計画によって、前回の経路計画を更新する（ステップ１３）。なお、運行計画システム１の動作開始時の場合は、各移動体の初期位置を起点とした経路計画を生成するか、もしくは外部から経路計画を取得すればよい。

全ての移動体について経路計画が生成されなかった場合（ステップ１４のＹＥＳ）、本フローチャートの処理を終了する。例えば、輸送すべき荷物がない又は行うべき作業がなくなった等の場合は、その移動体について経路計画を生成しない。走行タイミング計画の更新が間に合わない（例えば走行路タイミング計画の更新前に、現在の全ての移動体の運行が完了する見込みがある）、もしくは、経路計画が生成できないと判断した場合も、本処理を終了してよい。

少なくとも１台の移動体について経路計画が更新（再生成）された場合（ステップ１４のＮＯ）、走行タイミング計画部１０５は、当該移動体の更新後の経路計画に基づき、各移動体の走行タイミング計画を生成する（ステップ１５）。走行タイミング計画部１０５は、走行タイミング計画に示される時刻情報を経路計画に付与して運行計画を生成する。なお、経路計画が生成されなかった移動体（例えば運行が完了した移動体）については、走行タイミング計画は生成しない。なお、運行計画システム１の動作開始時の場合は、全ての移動体の経路計画が存在するため、これら全ての移動体の走行タイミング計画が生成される。

指令部１０７が、各移動体の走行タイミング計画に基づき、各移動体に対する移動指令データを生成し（ステップ１６）、各移動体の移動指令データを運行管理装置２００に送信する。

運行管理装置２００が、通信部２０１を用いて、各移動体に移動指令データを送信する（ステップ１７）。

運行管理装置２００の状態検知部２０２は、通信部２０１、センサ４０１及び通信装置５０１の少なくとも１つを介して、各移動体の走行状態をリアルタイムに監視する（ステップ１８）。状態検知部２０２は、各移動体の走行状態を表す情報を、通信部２０１を介して、再計画判定部１０８に送信する（同ステップ１８）。

再計画判定部１０８は、各移動体の運行計画と、各移動体の走行状態とに基づき、運行計画（あるいは走行タイミング計画）を守ることができない移動体が少なくとも１つ存在するかを判断、もしくは、新規の作業発生などで外部要因により再計画が必要になったか否かを判断する（ステップ１９）。再計画判定部１０８は、再計画を行うと決定した場合は、再計画トリガーを発生させる（ステップ１９のＹＥＳ）。

再計画トリガーが発生した場合（ステップ１９のＹＥＳ）、ステップ１１に戻る。そして、全移動体（既に計画の実行が終了している移動体は除く）の経路計画と走行タイミング計画とを更新する（ステップ１１～ステップ１５）。そして、各移動体に、更新された走行タイミング計画に基づく移動指令データを再度送信する。なお、各移動体は、受信した移動指令データによって、前回受信した移動指令データを更新する。

再計画トリガーが発生していない場合（ステップ１９のＮＯ）、運行計画（又は走行タイミング計画）が終了した移動体が存在するかを判断する。少なくとも１台の移動体について、運行計画が終了した場合は（ステップ２０のＹＥＳ）、ステップ１１に戻る。そして、全移動体の経路計画と走行タイミング計画とを更新し（ステップ１１～ステップ１５）、各移動体に、更新された走行タイミング計画に基づく移動指令データを再送信する。運行計画が終了した移動体が存在しない場合は、ステップ１８に戻る。再計画トリガーが発生するまで、又は運行計画の終了した移動体が発生するまで、ステップ１８～ステップ２０を繰り返す。

図１０、図１１及び図１２を用いて、図９のステップ１５の詳細を説明する。本ステップでは、各経路計画で同一の走行路を逆方向に走行したり、速度の異なる移動体が複数台存在する場合でも、移動体同士の衝突又はデッドロックを発生させないことを保障する走行タイミング計画を生成する。走行タイミング計画の生成では、各移動体の経路計画を変更しないことを前提条件とする。

図１０は走行タイミング計画部１０５による処理の一例のフローチャートである。

走行タイミング計画部１０５は、走行路構造記憶部１０１から走行路構造情報（図４又は図５参照）を取得し、経路計画記憶部１０２から経路計画のデータを取得する（ステップ２１）。

走行タイミング計画部１０５は、走行路構造情報と、各移動体の経路計画とに基づき、一例として、各移動体が指定領域に到着する時刻又は指定領域を出発する時刻の少なくとも一方を特定したタイミング計画（初期状態のタイミング計画）を生成する（ステップ２２）。これらの移動体の初期状態のタイミング計画をまとめて、初期状態のタイミング計画セットと呼ぶ。初期状態のタイミング計画の生成方法として、各移動体に対して、任意の方法で経路計画における指定領域の到着時刻又は出発時刻の少なくとも一方に関する情報を設定する。例えば、移動体の標準速度と、作業の所要時間とに基づき、各指定領域に対する到着又は出発の時刻を算出し、算出した時刻の情報を設定する。移動体の各走行路で走行する速度に関する条件（例えば速度パタン）がある場合は、当該速度に関する条件を満たすようにする。あるいは、前回生成された走行タイミング計画の一部（更新位置以降の部分）をそのまま流用することも可能である。

走行タイミング計画部１０５は、初期状態のタイミング計画セットに基づき、時間方向に最初に競合（デッドロック又は衝突など）が発生する２つの移動体のペアと、競合の発生するアーク（走行路）とを検出する（検出処理）（ステップ２３）。一例として、初期状態のタイミング計画セットにおいて、２つのタイミング計画の全ての組み合わせのそれぞれについて、最初に競合が発生する時刻を特定する。特定した時刻の中で最も時間的に速い時刻を選択し、選択した時刻で競合が発生する２つの移動体のペアと、当該競合が発生するアーク（走行路）とを検出する。

図１１（Ａ）は、２台の移動体（移動体１、移動体２とする）が簡単な構造の走行路ネットワークを走行する場合に競合が発生する例を説明するための図である。ここで、移動体１はノードＣとノードＥとの間を往復し、移動体２はノードＦとノードＤとの間を往復することが、移動体１の経路計画及び移動体２の経路計画で定められているとする。

ここでノードＡＢ間の走行路（区間ＡＢ）においては、移動体１及び移動体２で互いに逆方向の走行が発生する。このまま走行すると、移動体１及び移動体２が走行路上でバック走行を出来ない場合は、デッドロックが発生する。移動体１及び移動体２の少なくとも一方がバック走行を行うことが可能であっても、衝突回避のための停止と、バック走行とによる大幅な効率低下が発生する。

図１１（Ｂ）は、移動体１及び移動体２の初期状態のタイミング計画に基づき、移動体１及び移動体２の移動軌跡を時間に沿って示したグラフを表す。破線のグラフは移動体１のグラフ、実線のグラフは移動体２のグラフである。走行路（区間）ごとに移動軌跡の交差をチェックすることにより、競合の発生の有無を検出できる。この例では、区間ＡＢ間において、移動体１及び移動体２の移動軌跡が点８０１で交差する。このため、区間ＡＢにおける移動体１及び移動体２の競合の発生を検出できる。

図１２（Ａ）は、２台の移動体（移動体１、移動体２とする）が走行する場合に競合（衝突）が発生する他の例を説明するための図である。ここで、移動体１はノードＥとノードＣとの間を往復し、移動体２はノードＦとノードＤとの間を往復する予定であることが、移動体１の経路計画及び移動体２の経路計画で定められているとする。

移動体１及び移動体２は区間ＡＢを同じ方向に走行する。区間ＡＢ間で追い越しが出来ない走行路構造のため、移動体１及び移動体２の移動速度が異なる場合、区間ＡＢにおいて追突又は一時停止が発生し得る。追突防止による一時停止と再走行を反復し、走行効率が悪くなる。

図１２（Ｂ）は、移動体１及び移動体２の走行タイミング計画（初期状態）に基づき、移動体１及び移動体２の移動軌跡を時間に沿って示したグラフを表す。破線のグラフは移動体１のグラフ、実線のグラフは移動体２のグラフである。移動体２は移動体１より後から出発するが、移動体２は移動体１に比べ高速であり、移動体２が移動体１に後ろから衝突する。移動体１及び移動体２の移動軌跡が点８０２で交差し、点８０２に対応する位置で衝突する。このようにして、区間ＡＢにおける移動体１及び移動体２の競合の発生を検出できる。

ステップ２３で競合が発生する移動体ペアを検出できた場合（ステップ２４のＮＯ）、競合の発生するアーク（競合アーク）に対して、競合を回避する複数の対策又は少なくとも１つの対策を決定する。例えば、移動体ペアのいずれかの移動体に対して、該当競合アークの上流側のアーク（走行路）または指定領域で、待機させる操作を行うことにより、該当する競合を回避することができる。この場合、２つの対策があるといえる。よって、各対策について、少なくとも競合が発生している２つの移動体のタイミング計画の少なくとも一方を変更するようにタイミング計画セットを更新する（更新処理）（ステップ２５）。

例えば複数の移動体１～Ｈ（Ｈは２以上の整数）が存在するとする。移動体１と移動体２が競合する場合、移動体１を待機させる対策、移動体２を待機させる対策の２つの対策がある。この場合、移動体１～Ｈのタイミング計画のセットのうち、少なくとも移動体１又は２の少なくとも一方のタイミング計画を変更することにより、当該セットを更新することを各対策について行う。この場合、１つのセットから、２つの更新されたセットが得られる。

更新されたタイミング計画のセットを、変更状態のタイミング計画セットと呼ぶ。更新前のタイミング計画セットは保存しておく。

図１１（Ｃ）に、ステップ２５における競合回避の操作例を示す。図１１（Ｃ）は、図１１（Ｂ）で検出された点８０１での競合を回避するため、移動体１がアーク（走行路）ＡＢの上流であるアークＣＡで待機もしくは速度調整する（遅くする）ことで競合を回避する例を示す。図１１（Ｂ）で検出された競合を回避する別の方法として、移動体２が走行路ＢＡの上流である走行路ＦＢで待機する、もしくは速度調整する（遅くする）ことも可能である。このように競合回避の操作を行うことで、走行路ＡＢでは移動体１及び移動体２の移動軌跡は交差しない。よって、競合は回避される。

図１２（Ｃ）及び図１２（Ｄ）に、ステップ２５における競合回避の他の操作例を示す。図１２（Ｃ）は、図１２（Ｂ）で検出された点８０２での競合を回避するため、移動体１が走行路ＢＡの上流である走行路ＥＢで待機することで競合を回避する例を示す。移動体１は、例えば移動体２が指定領域Ａに到着又はノードＡに対応する交差部を通過した後に、走行路ＢＡを通過させる。同様に、図１２（Ｄ）は、移動体２がＢＡの上流である走行路ＦＢで待機することで競合を回避する例を示す。移動体２は、例えば移動体１が指定領域Ａに到着又はノードＡに対応する交差部を通過した後に、走行路ＢＡを通過させる。

走行タイミング計画部１０５は、生成した各変更状態のタイミング計画セットに対して、評価値を計算する（演算処理）。走行タイミング計画部１０５は、生成した各変更状態のタイミング計画セットと各評価値とを互いに対応づけて、探索リストに追加する（ステップ２６）。探索リストは、処理中の複数のタイミング計画セットを一時的に保持するリストである。

ここで、タイミング計画の評価値の算出例として、それぞれの移動体が各経路を競合による時間調整無しで走行した場合の走行時間（例えば初期状態のタイミング計画で走行した場合の時間）を基準値として計算することがある。この基準値に対して、時間調整による遅れ時間の総和又はべき乗和を算出して、算出した値を移動体間で合計し、合計した値を評価値（ペナルティ評価値）とする。この例では評価値の値が小さいほど、評価が高くなる。但し、評価値の値が大きいほど、評価が高くなるように、評価値を定義してもよい。この場合、上記合計した値の逆数を評価値と定義すればよい。評価値の算出方法の詳細な説明は後述する。評価値の算出方法は、特定の方法に限定されない。

走行タイミング計画部１０５は、探索リスト内の各変更状態のタイミング計画セットを評価値の降順に整列する（ステップ２７）。走行タイミング計画部１０５は、次の探索すべき対象として、探索リスト先頭の変更状態のタイミング計画セットを抽出する（同ステップ２７）。すなわち、探索リスト内の変更状態のタイミング計画セットの中から１つの変更状態のタイミング計画セットを選択する（選択処理）。

走行タイミング計画部１０５は、演算時間が所定の制限時間内に収まっているか、もしくは反復回数が規程の回数以内に収まっているか否かを判断する（ステップ２８）。反復回数は、フローチャートの任意の箇所を対象にできる。例えばステップ２３～２８の反復回数である。演算時間が制限時間内または反復回数が規程の回数以内であれば（ステップ２８のＹＥＳ）、ステップ２３に戻る。戻ったステップ２３では、ステップ２７で抽出した変更状態のタイミング計画を新たに初期状態のタイミング計画とみなして、引き続き検出処理（最初に競合が発生するアークと競合する移動体ペアの検出。前回又はそれ以前に検出された競合は解消済みである）を行う。

ステップ２３で処理対象としてタイミング計画セットにおいて競合が発生していない場合（ステップ２４のＹＥＳ）、これを、出力すべき走行タイミング計画セットの候補とする。このため、該当する変更状態のタイミング計画セットを、走行タイミング計画セット候補として、その評価値とともに、探索リストから解リストに移動させる（ステップ３１）。解リストは、出力対象となる走行タイミング計画セットの候補を一時的に保持するリストである。

走行タイミング計画部１０５は、解リストを評価値順に整列する（ステップ３２）。

走行タイミング計画部１０５は、探索リストの先頭におけるタイミング計画セットを次の処理対象として抽出し（ステップ３３）、これを初期状態のタイミング計画セットとみなして、ステップ２３に戻る。

演算時間が制限時間を超えた、もしくは反復回数が規程の回数を超えた場合は（ステップ２８のＮＯ）、走行タイミング計画部１０５は、解リストに走行タイミング計画セットの候補が少なくとも１つ入っているかをチェックする（ステップ２９）。解リストが空でない場合は（ステップ２９のＮＯ）、解リストの先頭の走行タイミング計画セットの候補を解として出力する。すなわち、当該候補に含まれる各移動体のタイミング計画を各移動体の走行タイミング計画として出力する（ステップ３０）。解リストは評価値の昇順（ここでは評価値の値が小さいほど評価が高いとする）に整列されているため、解リストの先頭の候補は、最も評価が高い走行タイミング計画のセットである。

一方、解リストが空の場合（ステップ２９のＹＥＳ）、走行タイミング計画部１０５は、探索リスト先頭における変更状態のタイミング計画セットを解として抽出する（ステップ３４）。当該抽出した解における各移動体のタイミング計画において、競合が解消されている時間の範囲（途中まで完成している計画部分）を特定し、特定した範囲の計画部分を各移動体の走行タイミング計画として出力する（ステップ３５）。

図１３に、図１０のフローチャートにおける走行タイミング計画部の探索処理のイメージ例を示す。図１３の一番上は、図１１（Ｂ）に示した走行タイミング計画に対応する（但し縮尺は変更されている）。

逆方向の走行が発生する走行路（競合アーク）に対して、移動体１を待機させる場合と移動体２を待機させる場合のそれぞれ２パタンの競合回避の対策がある。競合を回避するためにどちらの移動体を待機させるかに応じて、次に競合が発生する時刻及び発生する走行路も変化する。図１０のステップ２５において、移動体２を優先する操作（移動体１を待機させる操作）を行うと変更状態１のタイミング計画セット、移動体１を優先する操作（移動体２を待機させる操作）を行うと変更状態２のタイミング計画セットが得られる。なお、図中の白抜きの矢印はグラフの変更した箇所を示している。

変更状態１のタイミング計画セット及び変更状態２のタイミング計画セットについてそれぞれ評価値を計算し、変更状態１のタイミング計画セット及び変更状態２のタイミング計画セットをそれぞれの評価値とともに探索リストに格納する（図１０のステップ２６）。探索リストが評価値の昇順に整列され、変更状態１の走行タイミング計画セットの評価値の方が小さい（評価が高い）ため、変更状態１のタイミング計画セットが選択される（図１０のステップ２７）。

変更状態１のタイミング計画セットを初期状態のタイミング計画セットとみなして探索を再帰的に続行し（図１０のステップ２３）、移動体２及び移動体１のいずれを優先するかに応じて、変更状態３のタイミング計画セット及び変更状態４のタイミング計画セットが得られる。変更状態３のタイミング計画セット及び変更状態４のタイミング計画セットについてそれぞれ評価値を計算する。変更状態３のタイミング計画セット及び変更状態４のタイミング計画セットをそれぞれの評価値とともに探索リストに格納する（図１０のステップ２６）。

探索リストには、この時点で変更状態２のタイミング計画セット、変更状態３のタイミング計画セット、変更状態４のタイミング計画セットがそれぞれの評価値とともに格納される。この中で最も評価値が小さい（評価が高い）タイミング計画セットが選択され、これを初期状態のタイミング計画セットとみなして再帰的に処理を継続する（ステップ２３）。

このように、図１０の探索アルゴリズムでは、競合回避策の組合せを順次探索していく。移動体の台数が多かったり、競合アークの回数が多くなったりすると、競合回避策の組合せの数は膨大となり、一般にはリアルタイムでの計画生成が困難となるが図１０の探索アルゴリズムでは、次に調べる変更状態のタイミング計画セットの評価値を計算し、評価値が小さい（評価が高い）ものから優先的に探索を行うようにしている。よって、効率のよい探索が可能となる。

この際、発見的最適解探索アルゴリズム（Ａ探索）と呼ばれる探索手法を適用することで、短時間で評価の高い走行タイミング計画を得ることが可能となる。Ａ探索では、例えば、対象となるタイミング計画セットにおいて競合が解消されている経路（探索済みの回路）に対応する遅れ時間と、それより後の残りの経路（未探索の経路）に対して予想される遅れ時間の予測値との合計に基づき、評価値を計算する。

具体的には、タイミング計画セットにおいて最後に回避された競合の発生時刻以降について、各移動体の経路計画における残りの走行距離の総和を演算する。残りの走行距離に応じて一定の比率で遅れが発生するなどの仮定により、残りの走行における遅れ時間の予測値を求める。例えば、残りの走行距離を標準速度で走行する場合の走行時間を計算し、走行時間に一定の係数を乗じた値を遅れ時間として算出する。算出した遅れ時間の合計と、上記の競合の発生時刻より前の各移動体の遅れ時間の合計とを総和し、総和値を評価値とする（評価値の値が小さいほど評価が高い場合）。評価値の値が大きいほど評価を高くする場合は、総和値の逆数を評価値と定義すればよい。

以上、本実施形態によれば、デッドロック又は衝突等の競合を回避して、複数の移動体の運行計画を効率的に立案できる。また、木構造状に分岐した走行路を走行する場合や、安全等の理由等の場合などで、同一の走行路で双方向の移動が発生せざるを得ない場合でも、衝突又はデッドロックを発生させないことを保障した走行タイミング計画を生成できる。

（ハードウェア構成）
図１４に、図１の運行計画装置１００のハードウェア構成を示す。図１の運行計画装置１００は、コンピュータ装置６００により構成される。コンピュータ装置６００は、ＣＰＵ６０１と、入力インタフェース６０２と、表示装置６０３と、通信装置６０４と、主記憶装置６０５と、外部記憶装置６０６とを備え、これらはバス６０７により相互に接続されている。図１の運行管理装置２００も図１４と同様のハードウェア構成で実現される。

ＣＰＵ（中央演算装置）６０１は、主記憶装置６０５上で、コンピュータプログラムである運行計画プログラムを実行する。運行計画プログラムは、運行計画装置１００の上述の各機能構成を実現するプログラムのことである。運行計画プログラムは、１つのプログラムではなく、複数のプログラムやスクリプトの組み合わせにより実現されていてもよい。ＣＰＵ６０１が、運行計画プログラムを実行することにより、各機能構成は実現される。

入力インタフェース６０２は、キーボード、マウス、およびタッチパネルなどの入力装置からの操作信号を、運行計画装置１００に入力するための回路である。

表示装置６０３は、運行計画装置１００から出力されるデータを表示する。表示装置６０３は、例えば、ＬＣＤ（液晶ディスプレイ）、有機エレクトロルミネッセンスディスプレイ、ＣＲＴ（ブラウン管）、またはＰＤＰ（プラズマディスプレイ）であるが、これに限られない。コンピュータ装置６００から出力されたデータは、この表示装置６０３に表示することができる。

通信装置６０４は、運行計画装置１００が外部装置と無線または有線で通信するための回路である。データは、通信装置６０４を介して外部装置から入力することができる。外部装置から入力したデータを、主記憶装置６０５や外部記憶装置６０６に格納することができる。

主記憶装置６０５は、運行計画プログラム、運行計画プログラムの実行に必要なデータ、および運行計画プログラムの実行により生成されたデータなどを記憶する。運行計画プログラムは、主記憶装置６０５上で展開され、実行される。主記憶装置６０５は、例えば、ＲＡＭ、ＤＲＡＭ、ＳＲＡＭであるが、これに限られない。図１の各記憶部は、主記憶装置６０５上に構築されてもよい。

外部記憶装置６０６は、運行計画プログラム、運行計画プログラムの実行に必要なデータ、および運行計画プログラムの実行により生成されたデータなどを記憶する。これらの運行計画プログラムやデータは、運行計画プログラムの実行の際に、主記憶装置６０５に読み出される。外部記憶装置６０６は、例えば、ハードディスク、光ディスク、フラッシュメモリ、及び磁気テープであるが、これに限られない。図１の各記憶部又はデータベースは、外部記憶装置６０６上に構築されてもよい。

なお、運行計画プログラムは、コンピュータ装置６００に予めインストールされていてもよいし、ＣＤ－ＲＯＭなどの記憶媒体に記憶されていてもよい。また、運行計画プログラムは、インターネット上にアップロードされていてもよい。

また、運行計画装置１００は、単一のコンピュータ装置６００により構成されてもよいし、相互に接続された複数のコンピュータ装置６００からなるシステムとして構成されてもよい。

（第２の実施形態）
図１５に、第２の実施形態に係る運行計画システムを備えた全体システム構成の一例を示す。各移動体が経路計画部３０９と経路計画記憶部３０２を備えており、運行計画装置１００は経路計画部を備えていない。経路計画部３０９は、図１の経路計画部１０９と同様の機能を有する。

各移動体の経路計画部３０９は自律的に経路計画を決定し、経路計画記憶部３０２に経路計画を格納する。また、各移動体は、運行管理装置２００の通信部２１１又は通信装置５０１を介して、経路計画のデータを運行計画装置１００に送信する。運行計画装置１００は、各移動体の経路計画を経路計画記憶部１０２に格納する。各移動体に経路計画部３０９がなく、各移動体の経路計画記憶部３０２に予め各移動体の経路が記憶されていてもよい。

第２の実施形態では、各移動体が、ＳＬＡＭを備えた自律型の移動ロボット、自動走行の自動車、建機等であり、運行計画装置１００と運行管理装置２００との管理下にある走行路上を走行する場合等を想定している。各移動体の経路計画が予め決められている、もしくは、各移動体が自律的に経路計画を決定するため、運行計画装置１００及び運行管理装置２００側で自由に各移動体の経路計画を変更できない場合を想定している。このような場合においても、運行計画装置１００で走行タイミング計画を適切に生成し、各移動体に移動指令データを指示することで、衝突又はデッドロック等を発生させない走行を保障できる。もし衝突又はデッドロックを発生させない走行タイミング計画を生成できない場合、運行計画装置１００は、運行管理装置２００を介して、各移動体に、経路計画の変更要請を送信してもよい。

（第３の実施形態）
図１６は、第３の実施形態に係る運行計画システムを備えた全体システム構成の一例を示す。本実施形態では、基本的な各機能部は第１又は第２の実施形態と同じであるが、運行計画装置（又は運行計画システム）に相当する機能を少なくとも１台の移動体が備えている。それ以外の移動体は、経路計画部３０９と経路計画記憶部３０２と通信部３１０を備えている。通信部３１０は、他の移動体と無線通信する。

運行計画装置に相当する機能を有する移動体の内、１台の移動体がマスターとなる。図では移動体３０１＿Ｘがマスターとなった例が示されている。マスターは、例えば運行計画装置に相当する機能を有する移動体間で互いに交渉することで決定してもよい。または、予め定めた優先順位でマスターを決めてもよい。例えば、一番性能が高い移動体、もしくは、電池残量が一番大きい移動体がマスターとなってもよい。他の方法でマスターを決定してもよい。

移動体３０１＿Ｘ以外の移動体の経路計画部３０９は、自律的に経路計画を決定した後、マスターとなった移動体３０１＿Ｘに経路計画を送信する。または、予め経路計画記憶部３０２に経路計画が予め記憶されていてもよい。この場合、経路計画部３０９は、自分で経路計画の生成を行わず、経路計画記憶部３０２内の経路計画のデータを読み出して、マスターに送信する。

マスターとなった移動体３０１＿Ｘが、自移動体を含む複数の移動体の走行タイミング計画を一括して生成する。マスターは、各移動体の経路計画を変更しないように、各移動体の走行タイミング計画を生成する。移動体３０１＿Ｘは、各移動体の走行タイミング計画に基づく移動指令データを各移動体に送信する。各移動体は移動指令データに基づき走行を制御する。これにより、衝突又はデッドロック等を発生させることのない、全体として効率のよい走行を実現できる。

移動体３０１＿Ｘ以外の移動体が、経路計画部３０９と経路計画記憶部３０２を備えていなくてもよい。この場合、移動体３０１＿Ｘ以外の移動体は、第１の実施形態の移動体のうち、運行管理装置２００の通信部２０１と通信可能な移動体と同様の動作を行う。

第１又は第２の実施形態で状態検知部２０２が検知していた情報は、第３の実施形態では各移動体が自ら検知し、通信部３１０を介して運行計画装置１００に送信する。

第３の実施形態では、各移動体が、ＳＬＡＭを備えた自律型の移動ロボット、自動走行の自動車、建機等であり、単線の走行路において逆方向走行や追い抜きが発生する構造の走行路ネットワークを走行する場合等を想定している。各移動体の経路計画が予め決められている、もしくは、各移動体が自律的に経路計画を決定するため、他者が自由に経路計画を変更できない場合を想定している。このような場合においても、マスターとなった移動体が走行タイミング計画を適切に生成し、各移動体に指示することで、衝突又はデッドロックを発生させない走行を保障できる。もし衝突又はデッドロックを発生させない走行タイミング計画が生成できない場合は、マスターとなった移動体は、他の移動体に経路計画の変更要請を送信してもよい。

なお、本発明は上記各実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記各実施形態に開示されている複数の構成要素を適宜組み合わせることによって種々の発明を形成できる。また例えば、各実施形態に示される全構成要素からいくつかの構成要素を削除した構成も考えられる。さらに、異なる実施形態に記載した構成要素を適宜組み合わせてもよい。

１：運行計画システム
１００：運行計画装置
１０１：走行路構造記憶部
１０２：経路計画記憶部
１０３：運行計画記憶部
１０４：状態記憶部
１０５：走行タイミング計画部
１０６：更新位置決定部
１０７：指令部
１０８：再計画判定部
１０９：経路計画部
１１０：通信部
２００：運行管理装置
２０１：通信部
２０２：状態検知部
３０１＿１～３０１＿Ｎ：移動体
４０１＿１～４０１＿Ｍ：センサ
５０１＿１～５０１Ｋ：通信装置

Claims (23)

1. 複数の移動路を含む移動路ネットワークを移動する複数の移動体に対する情報処理装置であって、
   前記移動路ネットワークにおける複数の指定領域のうち、前記複数の移動体が通過する１つ以上の指定領域の順序を含む複数の経路計画に基づき、前記複数の経路計画を変更しない前提条件の下、前記移動路で移動体同士の競合が発生しないように、前記複数の移動体が前記移動路を移動するタイミングを指定した複数の移動タイミング計画を生成する移動タイミング計画部と、
   前記複数の移動タイミング計画に基づき、前記複数の移動体に対する移動指令データを送信する指令部と、を備え、
   前記競合は、第１の移動路の端部にある第１の交差部に１台以上の前記移動体が待機している状態で他の移動体が前記第１の移動路を通過することを含む、
   情報処理装置。
2. 前記移動タイミング計画部は、前記移動体が前記指定領域に到着する時刻及び前記指定領域を出発する時刻の少なくとも一方を決定することにより、前記複数の移動タイミング計画を生成する
   請求項１に記載の情報処理装置。
3. 前記経路計画は、前記移動体が前記移動路を移動する速度に関する条件を定めており、前記移動タイミング計画部は、前記速度に関する条件を満たすように、前記移動タイミング計画を生成する
   請求項１～２のいずれか一項に記載の情報処理装置。
4. 前記移動タイミング計画部は、第１の前記移動体を前記第１の移動路の一方の端部から離れた位置、もしくは、前記端部の手前の指定領域で待機させ、その間に第２の前記移動体を前記第１の移動路の他方の端部から前記一方の端部へ移動させるよう計画する
   請求項１～３のいずれか一項に記載の情報処理装置。
5. 前記移動タイミング計画部は、第２の前記移動体が前記第１の移動路の一方の端部から他方の端部への移動を完了する前に、前記第１の移動路を前記他方の端部から前記一方の端部へ移動する予定の第１の前記移動体が前記他方の端部に到着しないように、第１の前記移動体の速度を調整するよう計画する
   請求項１～３のいずれか一項に記載の情報処理装置。
6. 前記移動路における第１の前記移動体の速度が、第２の前記移動体よりも遅いことが定められており、
   前記移動タイミング計画部は、前記第１の移動路の一方の端部から第１の前記移動体が入る前に前記一方の端部から離れた位置、もしくは、前記端部の手前の指定領域で第１の前記移動体を待機させ、その間に第２の前記移動体を前記第１の移動路の一方の端部から他方の端部へ移動させるよう計画する
   請求項１～３のいずれか一項に記載の情報処理装置。
7. 前記移動路における第１の前記移動体の速度が、第２の前記移動体よりも遅いことが定められており、
   前記移動タイミング計画部は、前記第１の移動路を一方の端部から他方の端部へ移動する予定の第１の前記移動体が前記第１の移動路の一方の端部に到着した後に、第２の前記移動体を前記第１の移動路の一方の端部から他方の端部へ移動させるよう、第２の前記移動体の速度を調整するよう計画する
   請求項１～３のいずれか一項に記載の情報処理装置。
8. 前記移動タイミング計画部は、前記移動体ごとに前記移動体の前記経路計画に基づき、前記移動体が前記指定領域に到着する時刻及び前記指定領域を出発する時刻の少なくとも一方を特定したタイミング計画を生成し、
   前記タイミング計画のセットを対象として、時間方向に最初に移動体同士の競合が発生する移動路を検出する検出処理を行い、
   前記競合を回避する複数の対策を決定し、前記決定した対策ごとに、前記セットのうち前記競合が発生した前記移動体の少なくとも一方のタイミング計画を変更するように前記セットを更新する更新処理を行い、
   前記更新されたセットの評価値を計算する演算処理を行い、
   前記評価値に基づいて１つの前記更新されたセットを選択する選択処理を行い、
   選択した前記セットを対象として前記検出処理と、前記更新処理と、前記演算処理と、前記選択処理とを行うことを反復する探索を行い、
   前記探索で得られた前記更新されたセットの中から前記評価値に基づき１つの前記更新されたセットを選択し、
   選択した前記更新されたセットに含まれる前記タイミング計画を、前記移動タイミング計画とする
   請求項１～７のいずれか一項に記載の情報処理装置。
9. 前記移動タイミング計画部は、前記競合の発生時刻までの前記複数の移動体の遅れ時間と、前記競合の発生時刻より後の前記複数の移動体の残りの移動距離に応じた予測遅れ時間との総和に基づき、前記評価値を算出する
   請求項８に記載の情報処理装置。
10. 前記指令部は、前記移動指令データとして、前記移動体に対して待機のために停止すべき位置を指示するコマンドを送信し、前記待機している位置を出発するコマンドを送信することを逐次行う
    請求項１～７のいずれか一項に記載の情報処理装置。
11. 前記指令部は、前記移動タイミング計画に基づき、前記指定領域の複数の前記移動体の通過順序を特定し、
    前記移動指令データは、特定した前記通過順序に従って前記指定領域を通過することを指示し、
    前記指定領域を通過した移動体の識別情報を、少なくとも前記指定領域を通過していない前記移動体に送信する通信部を備えた
    請求項１～１０のいずれか一項に記載の情報処理装置。
12. 前記移動タイミング計画と、前記複数の移動体の位置情報とに基づき、前記複数の移動体の前記移動タイミング計画の再計画を行うか否かを判定する再計画判定部と、
    前記再計画判定部により前記再計画を行うことが決定された場合に、前記移動タイミング計画を更新する更新位置を前記複数の移動体に対して決定する更新位置決定部と、
    前記移動タイミング計画部は、前記経路計画において前記更新する位置以降の計画部分を更新する
    請求項１～１１のいずれか一項に記載の情報処理装置。
13. 前記移動路ネットワークにおいて前記移動路に沿って配置された通信装置を介して、前記移動体と通信する通信部を備え、
    前記更新位置は、前記通信装置と通信可能な範囲内の位置であり、
    前記指令部は、前記更新位置に存在する前記移動体に対して、更新後の前記移動タイミング計画に基づく前記移動指令データを送信する
    請求項１２に記載の情報処理装置。
14. 前記再計画判定部は、前記指定領域への前記移動体の到着が閾値時間以上遅れるかを判定し、遅れると判断した場合は、前記複数の移動体の前記移動タイミング計画の再計画を行うことを決定する
    請求項１２又は１３に記載の情報処理装置。
15. 前記第１の移動路を２以上の前記移動体が同時に逆方向で移動する移動路の距離の総和を少なくすることを評価基準として前記複数の移動体の複数の前記経路計画を生成する経路計画部
    を備えた請求項１～１４のいずれか一項に記載の情報処理装置。
16. 前記複数の移動体から前記経路計画を受信する通信部を備え、
    前記移動タイミング計画部は、前記複数の移動体から受信した前記経路計画を用いて、前記移動タイミング計画を生成する
    請求項１～１５のいずれか一項に記載の情報処理装置。
17. 前記競合は、前記第１の移動路の端部にある第１の交差部に、前記第１の移動路を移動予定の２台以上の前記移動体が同時に到着することを含む
    請求項１～１６のいずれか一項に記載の情報処理装置。
18. 前記第１の移動路の端部として第１の交差部及び第２の交差部があり、
    前記競合は、前記第１の移動路に前記第１の交差部から進入した第１の前記移動体が移動中もしくは停止中に、第２の前記移動体が第２の交差部から進入することを含む
    請求項１～１７のいずれか一項に記載の情報処理装置。
19. 請求項１～１８のいずれか一項に記載の情報処理装置と、
    前記複数の移動体と
    を備えた情報処理システム。
20. 複数の移動路を含む移動路ネットワークを移動する複数の移動体に対する情報処理方法であって、
    前記移動路ネットワークにおける複数の指定領域のうち、前記複数の移動体が通過する１つ以上の指定領域の順序を含む複数の経路計画に基づき、前記複数の経路計画を変更しない前提条件の下、前記移動路で移動体同士の競合が発生しないように、前記複数の移動体が前記移動路を移動するタイミングを指定した複数の移動タイミング計画を生成するステップと、
    前記複数の移動タイミング計画に基づき、前記複数の移動体に対する移動指令データを送信するステップと、
    をコンピュータが実行し、
    前記競合は、第１の移動路の端部にある第１の交差部に１台以上の前記移動体が待機している状態で他の移動体が前記第１の移動路を通過することを含む、情報処理方法。
21. 複数の移動路を含む移動路ネットワークを移動する複数の移動体に対する情報処理を行うためのコンピュータプログラムであって、
    前記移動路ネットワークにおける複数の指定領域のうち、前記複数の移動体が通過する１つ以上の指定領域の順序を含む複数の経路計画に基づき、前記複数の経路計画を変更しない前提条件の下、前記移動路で移動体同士の競合が発生しないように、前記複数の移動体が前記移動路を移動するタイミングを指定した複数の移動タイミング計画を生成するステップと、
    前記複数の移動タイミング計画に基づき、前記複数の移動体に対する移動指令データを送信するステップと
    をコンピュータに実行させ、
    前記競合は、第１の移動路の端部にある第１の交差部に１台以上の前記移動体が待機している状態で他の移動体が前記第１の移動路を通過することを含む、コンピュータプログラム。
22. 複数の移動路を含む移動路ネットワークを移動する複数の移動体に対する情報処理装置であって、
    前記複数の移動体がそれぞれ移動する経路を表す複数の経路計画を変更しない前提条件の下、前記移動路で移動体同士の競合が発生しないように、前記複数の移動体が前記移動路を移動するタイミングを指定した複数の移動タイミング計画を生成する移動タイミング計画部と、
    前記複数の移動タイミング計画に基づき、前記複数の移動体に対する移動指令データを送信する指令部と、
    を備え、
    前記競合は、第１の移動路の端部にある第１の交差部に１台以上の前記移動体が待機している状態で他の移動体が前記第１の移動路を通過することを含む、情報処理装置。
23. 複数の移動路を含む移動路ネットワークにおける複数の指定領域のうち、複数の移動体が通過する１つ以上の指定領域の順序を含む複数の経路計画に基づき、前記複数の経路計画を変更しない前提条件の下、前記複数の移動体が前記移動路を移動するタイミングを指定した複数の移動タイミング計画を生成する移動タイミング計画部と、
    前記複数の移動タイミング計画に基づき、前記複数の移動体に対する移動指令データを送信する指令部と、を備え、
    前記移動タイミング計画部は、前記移動体ごとに前記移動体の前記経路計画に基づき、前記移動体が前記指定領域に到着する時刻及び前記指定領域を出発する時刻の少なくとも一方を特定したタイミング計画を生成し、
    前記タイミング計画のセットを対象として、時間方向に最初に移動体同士の競合が発生する移動路を検出する検出処理を行い、
    前記競合を回避する複数の対策を決定し、前記決定した対策ごとに、前記セットのうち前記競合が発生した前記移動体の少なくとも一方のタイミング計画を変更することにより前記セットを更新する更新処理を行い、
    前記更新されたセットの評価値を計算する演算処理を行い、
    前記評価値に基づいて１つの前記更新されたセットを選択する選択処理を行い、
    選択した前記セットを対象として前記検出処理と、前記更新処理と、前記演算処理と、前記選択処理とを行うことを反復する探索を行い、
    前記探索で得られた前記更新されたセットの中から前記評価値に基づき１つの前記更新されたセットを選択し、
    選択した前記更新されたセットに含まれる前記タイミング計画を、前記移動タイミング計画とし、
    前記競合は、第１の移動路の端部にある第１の交差部に１台以上の前記移動体が待機している状態で他の移動体が前記第１の移動路を通過することを含む、情報処理装置。

Images