(57)【要約】【課題】仮想移動体同士の衝突判定を行う場合であっても、ベクトル演算器によって高速に移動シミュレーションを実行することができる移動体シミュレーションシステムを提供する。【解決手段】移動空間分割部３２は、移動空間を分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定する。仮想移動体登録部３３は、分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録する。移動計算部３４は、各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いて計算する。【選択図】図１９
2019028877.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションを行う移動体シミュレーションシステムであって、
コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定する移動空間分割部と、
分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録する仮想移動体登録部と、
前記リストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算する移動計算部とを備え、
前記仮想移動体登録部は、
前記ベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択する
ことを特徴とする移動体シミュレーションシステム。
【請求項２】
仮想移動体登録部は、
単位時間経過後の位置が計算された仮想移動体について、単位時間経過後の位置の計算前に当該仮想移動体が存在していた分割空間に当該仮想移動体が存在しなくなったとみなし、単位時間経過後に当該仮想移動体が存在する分割空間を記憶し、
全ての仮想移動体の単位時間経過後の位置が計算された場合に、単位時間経過後に各仮想移動体が存在する分割空間を、各仮想移動体が現在存在する分割空間として記憶し直す
請求項１に記載の移動体シミュレーションシステム。
【請求項３】
仮想移動体登録部は、
分割空間群から仮想移動体が存在している分割空間を最大でＮ個選択する際に、前記分割空間群に含まれている各分割空間に対して、存在している仮想移動体の数が多い順に優先順序を決定し、前記優先順序に従って、仮想移動体が存在している分割空間を最大でＮ個選択する
請求項２に記載の移動体シミュレーションシステム。
【請求項４】
移動空間分割部は、
仮想移動体が単位時間当たりに移動可能な最大距離をＬとしたときに、移動空間を、Ｘ軸方向およびＹ軸方向に２Ｌ毎に分割することによって複数の分割空間を生成し、
Ｘ軸方向の並びの順序が偶数番目であり、Ｙ軸方向の並びの順序が偶数番目である分割空間の集合である分割空間群と、
Ｘ軸方向の並びの順序が偶数番目であり、Ｙ軸方向の並びの順序が奇数番目である分割空間の集合である分割空間群と、
Ｘ軸方向の並びの順序が奇数番目であり、Ｙ軸方向の並びの順序が偶数番目である分割空間の集合である分割空間群と、
Ｘ軸方向の並びの順序が奇数番目であり、Ｙ軸方向の並びの順序が奇数番目である分割空間の集合である分割空間群とを決定する
請求項１から請求項３のうちのいずれか１項に記載の移動体シミュレーションシステム。
【請求項５】
コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションを行う移動体シミュレーション方法であって、
コンピュータが、
前記コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定し、
分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録し、
前記リストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算し、
分割空間を選択する際、前記ベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択する
ことを特徴とする移動体シミュレーション方法。
【請求項６】
コンピュータが、
単位時間経過後の位置が計算された仮想移動体について、単位時間経過後の位置の計算前に当該仮想移動体が存在していた分割空間に当該仮想移動体が存在しなくなったとみなし、単位時間経過後に当該仮想移動体が存在する分割空間を記憶し、
全ての仮想移動体の単位時間経過後の位置が計算された場合に、単位時間経過後に各仮想移動体が存在する分割空間を、各仮想移動体が現在存在する分割空間として記憶し直す
請求項５に記載の移動体シミュレーション方法。
【請求項７】
コンピュータが、
分割空間群から仮想移動体が存在している分割空間を最大でＮ個選択する際に、前記分割空間群に含まれている各分割空間に対して、存在している仮想移動体の数が多い順に優先順序を決定し、前記優先順序に従って、仮想移動体が存在している分割空間を最大でＮ個選択する
請求項６に記載の移動体シミュレーション方法。
【請求項８】
コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションをコンピュータに実行させる移動体シミュレーションプログラムであって、
前記コンピュータに、
コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定する移動空間分割処理、
分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録する仮想移動体登録処理、および、
前記リストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算する移動計算処理を実行させ、
前記仮想移動体登録処理で、
前記ベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択させる
ための移動体シミュレーションプログラム。
【請求項９】
コンピュータに、
単位時間経過後の位置が計算された仮想移動体について、単位時間経過後の位置の計算前に当該仮想移動体が存在していた分割空間に当該仮想移動体が存在しなくなったとみなし、単位時間経過後に当該仮想移動体が存在する分割空間を記憶する処理、および、
全ての仮想移動体の単位時間経過後の位置が計算された場合に、単位時間経過後に各仮想移動体が存在する分割空間を、各仮想移動体が現在存在する分割空間として記憶し直す処理を実行させる
請求項８に記載の移動体シミュレーションプログラム。
【請求項１０】
コンピュータに、
仮想移動体登録処理で、
分割空間群から仮想移動体が存在している分割空間を最大でＮ個選択する際に、前記分割空間群に含まれている各分割空間に対して、存在している仮想移動体の数が多い順に優先順序を決定させ、前記優先順序に従って、仮想移動体が存在している分割空間を最大でＮ個選択させる
請求項９に記載の移動体シミュレーションプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の移動体の移動のシミュレーションを実行する移動体シミュレーションシステム、移動体シミュレーション方法および移動体シミュレーションプログラムに関する。
【背景技術】
【０００２】
多数の人の流れや、多数の車両の流れ等をコンピュータ内で表現し、人の流れや車両の流れ等の将来の状態を予測するマルチエージェントシミュレーションが知られている。マルチエージェントシミュレーションにおけるエージェントとは、コンピュータ内に表現される個々の移動体である。例えば、人の移動のシミュレーションを実行する場合には、エージェントはコンピュータ内に表現された個々の人であり、自動車の移動のシミュレーションを実行する場合には、エージェントはコンピュータ内に表現された個々の自動車である。
【０００３】
コンピュータ内におけるデータ処理を高速化する技術の１つとして、ＳＩＭＤ（Single Instruction Multiple Data）等のベクトル処理が知られている。ベクトル処理とは、複数の異なるデータに対して単一の演算命令を与え、同期的に処理する並列処理方法である。ベクトル処理は、例えば、並列処理されるデータを格納する複数のベクトルレジスタと、パイプライン化された演算ユニットとを備える専用のベクトル演算器によって実現される。また、ベクトル処理は、例えば、ＳＩＭＤ拡張命令セットが搭載されたＣＰＵ（Central Processing Unit ）や、マルチスレッドによるＳＩＭＤ命令処理を行うＧＰＵ（Graphics Processing Unit）等によっても実現可能である。
【０００４】
特許文献１には、プロセス移動に伴う計算プロセッサ間の通信負荷の増減の影響を含めた処理負荷量を適切に分散する方法が記載されている。特許文献１に記載の技術では、処理負荷間の通信量の情報を取得し、取得した情報に基づいて、複数の処理ノードの内で配置の変更の対象となる処理ノードの対を選択する。そして、選択した対の処理ノード間で処理負荷の移動を行った場合の該対の処理ノード間の通信負荷量の変化を予測し、予測結果に基づいて、複数の処理の再配置を行う。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１４／０１６９５０号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以下、コンピュータ内に表現された移動体を、仮想移動体と記す。
【０００７】
街中の人や車両等の移動体の動きをマルチエージェントシミュレーションによってシミュレーションする場合、シミュレーションの対象となる移動体の数が、数万から数百万等のように膨大になり、シミュレーションの実行時間が増大する場合がある。
【０００８】
また、リアルタイムに複数の移動体の移動のシミュレーションを行う場合に、状況の変化に応じて、仮想移動体の行動パターンを変化させて、再度、シミュレーションを行うことが必要になる場合もある。
【０００９】
これらの点を鑑み、複数の移動体の移動のシミュレーション（以下、単に移動シミュレーションと記す。）の高速化が必要とされている。
【００１０】
特許文献１に記載の技術は、処理ノード内で処理されるプロセスが他の処理ノード内で処理されるプロセスとの情報交換を必要とし、そのためのノード間通信に時間を要することに着目し、プロセスのノード配置方法を提供している。特許文献１に記載の技術と、一般的な移動シミュレーションとを対比すると、例えば、各仮想移動体の位置の更新処理がプロセスに相当する。プロセス間の情報交換は、仮想移動体同士の衝突判定時の位置情報の交換に相当する。
【００１１】
並列ノード処理の場合、各ノードは非同期に実行されるため、プロセス間の情報交換に伴うプロセスの待機が可能であり、処理ノード内でのプロセスの実行順序までは考慮しない。
【００１２】
一方、ベクトル演算器を用いたベクトル処理の場合、データを同期的に処理するため、プロセスの待機が不可能である。すなわち、衝突判定に伴う情報交換を必要とするプロセスが同時に処理されないように、同時にベクトル処理を行うプロセスを選択することが必要になる。従って、特許文献１に記載の方法を、ベクトル演算器を用いたベクトル処理に適用することはできない。
【００１３】
そこで、本発明は、仮想移動体同士の衝突判定を行う場合であっても、ベクトル演算器によって高速に移動シミュレーションを実行することができる移動体シミュレーションシステム、移動体シミュレーション方法および移動体シミュレーションプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明による移動体シミュレーションシステムは、コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションを行う移動体シミュレーションシステムであって、コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定する移動空間分割部と、分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録する仮想移動体登録部と、リストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算する移動計算部とを備え、仮想移動体登録部は、ベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択することを特徴とする。
【００１５】
また、本発明による移動体シミュレーション方法は、コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションを行う移動体シミュレーション方法であって、コンピュータが、コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定し、分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録し、リストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算し、分割空間を選択する際、ベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択することを特徴とする。
【００１６】
また、本発明による移動体シミュレーションプログラムは、コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションをコンピュータに実行させる移動体シミュレーションプログラムであって、コンピュータに、コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を複数決定する移動空間分割処理、分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリストに、選択した各仮想移動体を登録する仮想移動体登録処理、および、リストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算する移動計算処理を実行させ、仮想移動体登録処理で、ベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択させることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、仮想移動体同士の衝突判定を行う場合であっても、ベクトル演算器によって高速に移動シミュレーションを実行することができる。
【図面の簡単な説明】
【００１８】
【図１】移動空間の例を示す模式図である。
【図２】移動空間をセルで分割した状態を示す模式図である。
【図３】本発明の第１の実施形態の移動体シミュレーションシステムの例を示すブロック図である。
【図４】移動空間分割部の構成例を示すブロック図である。
【図５】移動空間を分割することで生成された分割空間を示す模式図である。
【図６】各分割空間が非隣接分割空間群Z1〜Z4に分類された状態の例を示す模式図である。
【図７】配置情報リストの例を示す模式図である。
【図８】仮想移動体登録部の構成例を示すブロック図である。
【図９】移動計算部の構成例を示すブロック図である。
【図１０】第１の実施形態の移動体シミュレーションシステムの処理経過の例を示すフローチャートである。
【図１１】ステップＳ１０２の処理経過の例を示すフローチャートである。
【図１２】ステップＳ１０３の処理経過の例を示すフローチャートである。
【図１３】ステップＳ１０４の処理経過の例を示すフローチャートである。
【図１４】ステップＳ１０５の処理経過の例を示すフローチャートである。
【図１５】第２の実施形態における仮想移動体登録部の構成例を示すブロック図である。
【図１６】第２の実施形態におけるステップＳ１０３の処理経過の例を示すフローチャートである。
【図１７】図７に示す要素を識別ＩＤの記録数の多い順に並び替えた配置情報リストを示す模式図である。
【図１８】本発明の各実施形態に係るコンピュータの構成例を示す概略ブロック図である。
【図１９】本発明の移動体シミュレーションシステムの概要を示すブロック図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態を図面を参照して説明する。
【００２０】
本発明の移動体シミュレーションシステムは、例えば、経路誘導時における複数の歩行者を、複数の仮想移動体として表現する。また、本発明の移動体シミュレーションシステムは、誘導範囲となる街中の歩道およびその周辺の状況（例えば、進入できない領域）を示す地図情報を、座標を用いて表現した移動空間としてコンピュータ内で表す。そして、移動体シミュレーションシステムは、複数の仮想移動体が移動空間内を移動する様子のシミュレーションを実行する。避難誘導の例として、例えば、イベントが行われた大規模会場から周辺の駅への退場誘導や、緊急時の避難誘導が挙げられる。なお、経路誘導は、これらの例に限定されない。
【００２１】
前述のように、仮想移動体は、コンピュータ内に表現された移動体である。仮想移動体は、例えば、人を表現したものであっても、自動車等の車両を表現したものであってもよい。以下の説明では、仮想移動体が人を表現したものである場合を例にして説明する。
【００２２】
本発明の移動体シミュレーションシステムは、コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動シミュレーションを行う。また、連続する単位時間の境界を「時間ステップ」と称する。従って、ある時間ステップｔから次の時間ステップｔ＋１までの時間が単位時間となる。
【００２３】
次に、本発明の移動体シミュレーションシステムにおいて、コンピュータ内で表現される移動空間について説明する。移動空間は、移動体が移動する通路およびその周辺の状況（例えば、進入できない領域）を示す地図情報（例えば、道路網および種々の施設等を示す街中の地図情報や、イベント施設内のフロアを示すフロアマップ）を、２次元座標を用いてコンピュータ内に表現した情報である。
【００２４】
移動空間は、移動シミュレーションの対象領域を表す地図情報を、２次元座標平面上にプロットし、通行可能領域を座標値（Ｘ、Ｙ）で表現すること得られる。図１は、移動空間の例を示す模式図である。図１に示すように、移動空間は、２次元座標平面の原点（０，０）を基準とし、Ｘ軸およびＹ軸の０以上の範囲内で表される。また、移動空間のＸ座標の最大値をＸｍａｘとし、Ｙ座標の最大値をＹｍａｘとする。なお、座標値は、実数で与えられる。
【００２５】
図１に示す例では、白色の領域は、仮想移動体が移動可能な通路を表し、斜線で示した領域は、仮想移動体が進入できない領域を表している。
【００２６】
移動体シミュレーションでは、仮想移動体同士の衝突を考慮しなければならない。衝突判定方法の１つとして、仮想移動体の形状を定義し、仮想移動体同士の重なりの発生の有無を判定する方法がある。しかし、この方法は複雑な計算を要する。
【００２７】
そこで、本実施形態では、より簡易な衝突判定方法を採用する。具体的には、衝突判定方法として、仮想移動体を質点として捉え、座標空間（移動空間）を大きさおよび形状が一定の複数のセルに分割し、２つ以上の仮想移動体が同一セル内に存在した場合に、衝突が発生したと判定する方法を採用する。
【００２８】
図２は、移動空間をセル７０で分割した状態を示す模式図である。セル７０の形状は、例えば、正方形である。個々のセル７０のＸ軸方向およびＹ軸方向の辺の長さをＣとすると、現実の歩行者が一人存在しうる幅に、Ｃの長さを合わせればよい。例えば、Ｃの長さが、現実の５０ｃｍ〜１ｍ程度の範囲内の１つの値に対応するものとして、Ｃの長さを設定すればよい。ただし、以下では、説明を簡単にするため、Ｃを、座標軸の単位長さとして表す。すなわち、Ｃ＝１と表すものとして、説明する。
【００２９】
上記のような、移動空間のサイズ（移動空間の範囲）、通行可能領域を表す座標値、および、セルの分割幅の情報を、移動空間情報と記す。なお、通行可能領域の表現方法は特に限定されない。例えば、進入できない領域毎に、進入できない領域の各頂点の情報を定めることによって、進入できない領域を規定し、移動空間の範囲内で、進入できない領域以外の領域を、通行可能領域として表現してもよい。通行可能領域を表す情報は変化しない。移動空間情報は、シミュレーション前の時点で予め作成される。
【００３０】
次に、仮想移動体を表す移動体情報について説明する。移動体情報は、仮想移動体毎に定められる。１つの移動体情報は、１つの仮想移動体を表し、移動体情報と仮想移動体とは一対一に対応している。各移動体情報も、シミュレーション前の時点で予め作成される。
【００３１】
１つの移動体情報には、対応する仮想移動体の識別ＩＤ（Identification）と、その仮想移動体の移動速度と、その仮想移動体の現在位置座標と、その仮想移動体の目的位置座標と、その仮想移動体の移動方向と、その仮想移動体の移動モデルとを含む。移動体情報において、現在位置座標および移動方向は、シミュレーションの進行に伴って更新される。
【００３２】
目的位置座標は、最終的な目的位置座標だけではなく、仮想移動体の現在位置座標に応じた目的位置座標（換言すれば、シミュレーション実行中の仮想移動体の位置に応じた目的位置座標）として、複数定められている。例えば、現在位置座標から見て前方に存在する交差点で仮想移動体が右折（または左折）すると定められているとする。この場合、その交差点上に目的位置座標が予め定められている。そして、現在位置座標がその交差点に到達する経路（通行可能領域）内に存在する場合、その交差点上の目的位置座標が現在位置座標に応じた目的位置座標に該当することになる。このような目的位置座標が、仮想移動体に定められた経路上に複数定められ、順序付けられている。最後の目的位置座標が、仮想移動体が最終的に到達すべき場所を表す。ある目的位置座標（Ｍとする。）は、その１つ前の目的位置座標からその目的位置座標Ｍまでの通行可能領域内の任意の現在位置座標と、目的位置座標Ｍとを結ぶ線分が、仮想移動体が進入できない領域を通過しないように定められる。
【００３３】
仮想移動体の識別ＩＤとして、例えば、仮想移動体毎に、個別の整数値が定められる。
【００３４】
仮想移動体の移動方向は、Ｘ軸を基準とし、現在位置座標から、その現在位置座標に応じた目的位置座標への方向ベクトルの角度として表される。すなわち、移動方向は、Ｘ軸方向のベクトル（例えば、Ｘ軸方向の単位ベクトル）を、上記のベクトルまで回転させたときの回転角度である。現在位置座標は、時間ステップ毎に変わるので、移動方向も時間ステップ毎に変わる。
【００３５】
移動モデルは、ある時間ステップｔにおいて、次の時間ステップｔ＋１までの単位時間内に、仮想移動体がどの位置に移動するかを決定するための計算式やルールである。各実施形態では、全ての移動体情報で、共通の移動モデルが定められているものとする。
【００３６】
以下に示す各実施形態では、全ての移動体情報で共通の移動モデルとして、以下の（１）〜（３）に示す事項が定められている場合を例にする。以下の説明における左、右はそれぞれ、現在位置座標に応じた目的位置座標に向かって移動する仮想移動体から見た左、右を意味する。
【００３７】
（１）
仮想移動体が移動方向に向かって直進移動した場合における、単位時間経過後の仮想移動体の位置の座標値を計算する。その座標値は、単位時間当たりのＸ軸方向・Ｙ軸方向の移動距離をそれぞれ、現在位置座標に加算することで計算される。単位時間当たりのＸ軸方向の移動距離は、現在の時間ステップｔにおける移動方向を用い、「仮想移動体の移動速度」×「単位時間」×「移動方向の余弦値」を計算することによって求められる。単位時間当たりのＹ軸方向の移動距離は、現在の時間ステップｔにおける移動方向を用い、「仮想移動体の移動速度」×「単位時間」×「移動方向の正弦値」を計算することによって求められる。そして、Ｘ軸方向の移動距離およびＹ軸方向の移動距離を、現在位置座標のＸ座標、Ｙ座標に加算することによって得られた座標値を、単位時間経過後の仮想移動体の位置の候補として定める。
【００３８】
（２）
上記の（１）で単位時間経過後の仮想移動体の位置の候補の座標値を計算した後、以下の２つの条件をいずれも満たしているか否かを判定する。第１の条件は、その計算した座標値に対応するセル上に他の仮想移動体が存在していないことである。第２の条件は、現在位置座標と、その計算した座標値とを結ぶ線分が通行可能領域のみを通過していることである。上記の２つの条件が全て満たされている場合、（１）で計算した単位時間経過後の仮想移動体の位置の候補の座標値を、単位時間経過後の仮想移動体の位置の座標値として定める。第１の条件および第２の条件のいずれか一方でも満たされない場合、仮想移動体の移動方向を左あるいは右に一定の角度だけ変更し、変更後の移動方向を用いて再度上記の（１）の処理を実行し、単位時間経過後の仮想移動体の位置の候補を定める。このとき、移動方向を変更するだけでなく、現在の時間ステップにおける移動速度を、全ての仮想移動体の移動速度の中の最大値以下の範囲内で変更してもよい。そして、上記の２つの条件が全て満たされている場合に、その候補の座標値を、単位時間経過後の仮想移動体の位置の座標値として定める。第１の条件および第２の条件のいずれか一方でも満たされない場合は、再度、上記のように仮想移動体の移動方向を変更し、同様の処理を繰り返す。
【００３９】
なお、第２の条件が満たされないということは、仮想移動体が、通過できない領域を通過しようとしていることを意味する。既に説明したように、ある目的位置座標（Ｍとする。）は、その１つ前の目的位置座標からその目的位置座標Ｍまでの通行可能領域内の任意の現在位置座標と、目的位置座標Ｍとを結ぶ線分が、仮想移動体が進入できない領域を通過しないように定められる。従って、仮想移動体の移動方向が左あるいは右に一定の角度だけ変更されない場合には、第２の条件は満たされている。第１の条件が満たされないことによって、仮想移動体の移動方向が変更された場合、第２の条件が満たされない場合が生じ得る。
【００４０】
（３）
上記の２つの条件を全て満たす単位時間経過後の仮想移動体の位置の候補の座標値が得られなかった場合には、現在位置座標を、単位時間経過後の仮想移動体の位置の座標値として定める。このことは、仮想移動体がいずれの位置にも移動することができずに、現在の時間ステップｔにおける位置に停滞していることを意味する。
【００４１】
なお、上記の移動モデルは例示であり、移動モデルは、上記の例に限定されない。
【００４２】
本発明の移動体シミュレーションシステムは、時間ステップ毎に、各仮想移動体の単位時間経過後の位置を計算する。そして、移動体シミュレーションシステムは、その位置に応じて、各移動体情報内の現在位置座標および移動方向を更新する。このように、仮想移動体の単位時間経過後の位置を計算することを移動計算と称する。
【００４３】
移動計算において、上記の第１の条件および第２の条件がいずれも満たされることを確認することで、衝突を回避することおよび通行可能領域を通過することを模擬して、位置を更新する。従って、次の時間ステップにおける位置を決定する際に、他の仮想移動体の位置を参照しなければならない。このように、衝突回避行動を含む移動計算において、移動先の候補となるセルの位置が重複する可能性があり、互いに位置情報の参照を必要とする２つの仮想移動体は依存関係にある。
【００４４】
２つの仮想移動体が依存関係にある場合、適切に衝突回避行動をとるためには２つの仮想移動体の移動計算は逐次的に行わなければならない。この場合、２つの仮想移動体の移動計算を行う順序によってシミュレーション結果は変化するが、大規模な群衆行動シミュレーションにおいては個々の計算順序を定義せず、ランダムに決定することが一般的である。よって、本実施形態においても仮想移動体の移動計算順序に関する規則や制約条件は事前に設定されていないものとする。
【００４５】
一方、２つの仮想移動体が依存関係にない場合、互いの移動の結果が干渉しないため、これらの仮想移動体の移動計算をベクトル演算器によって並列計算することが可能となる。
【００４６】
仮想移動体の単位時間経過後の位置は単位時間と移動速度と移動方向に応じて決定される。移動方向は現在位置座標と目的位置座標との位置関係によって決定される。そのため、単位時間経過後の位置は、いずれの仮想移動体に関しても３６０度全ての方向に決定される可能性がある。一方、移動速度は最大値が決まっていることが多い。つまり、仮想移動体の最大移動速度をＶ、単位時間をＴとしたとき、仮想移動体が単位時間内に移動する可能性のある領域は、仮想移動体の現在位置座標を中心とし、距離Ｌ＝Ｖ×Ｔを半径とした円領域となる。
【００４７】
つまり、２つの仮想移動体が直線距離で２Ｌ以上離れている場合、それらは単位時間経過後に衝突する可能性がないと言える。言い換えると、移動空間を距離２Ｌ毎に分割し、隣接しない分割空間上に存在する仮想移動体同士は単位時間経過後に衝突する可能性がない。このような仮想移動体同士は衝突判定において依存関係がなく、移動計算をベクトル処理によって並列計算することが可能となる。
【００４８】
以下、依存関係のない仮想移動体を選択し、ベクトル処理を適用することで高速に移動シミュレーションを実行する本発明の移動体シミュレーションシステム実施形態を示す。
【００４９】
実施形態１．
図３は、本発明の第１の実施形態の移動体シミュレーションシステムの例を示すブロック図である。本発明の第１の実施形態の移動体シミュレーションシステム３０は、シナリオ取得部３１と、移動空間分割部３２と、仮想移動体登録部３３と、移動計算部３４と、終了判定部３５とを備える。
【００５０】
シナリオ取得部３１は、移動シミュレーションに用いるシナリオを取得する。シナリオとは、予め作成されている移動空間情報と、各仮想移動体に対応する移動体情報とを合わせた情報群である。シナリオを変更することで、シミュレーション内容を変更することができる。例えば、移動体シミュレーションシステム３０の管理者は、予め、外部の情報処理装置または情報記録媒体にシナリオを記憶させておけばよい。シナリオ取得部３１は、その情報処理装置または情報記録媒体にアクセスして、その情報処理装置に記憶されているシナリオを取得すればよい。
【００５１】
また、シナリオ取得部３１は、移動体シミュレーションシステム３０が備えるメモリ（図３において図示略）に、取得したシナリオを記憶させる。メモリに記憶されたシナリオは、適宜、移動空間分割部３２、仮想移動体登録部３３、移動計算部３４および終了判定部３５によって参照される。また、各移動体情報内の現在位置座標や移動方向は、シミュレーションの進行に伴い、適宜、更新される。
【００５２】
移動空間分割部３２は、シナリオ取得部３１が取得したシナリオから移動空間情報および各移動体情報を取得し、仮想移動体の単位時間当たりの移動可能距離Ｌを計算する。Ｌは、仮想移動体が単位時間当たりに移動可能な距離の最大値である。そして、移動空間分割部３２は、移動空間をＸ軸方向およびＹ軸方向に幅２Ｌ毎に分割することによって、正方形の分割空間を複数個、生成する。
【００５３】
さらに、移動空間分割部３２は、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群を４つ決定する。以下、この分割空間群を、「非隣接分割空間群」と称する。
【００５４】
また、移動空間分割部３２は、分割空間毎に、分割空間内に存在している仮想移動体の識別ＩＤを記録するための配列を、現在時間ステップ用と次時間ステップ用の２種類作成する。この配列の個々の要素は、個々の分割空間に対応する。また、この配列の要素は、リスト形式で複数の識別ＩＤを記録可能である。以下、この配列を、「配置情報リスト」と記す。移動空間分割部３２は、シナリオから得られる全ての仮想移動体のシミュレーション開始時の現在位置座標に従って、現在位置座標が属する分割空間に対応する要素（配列の要素）に、仮想移動体の識別ＩＤを記録する。
【００５５】
また、移動空間分割部３２は、非隣接分割空間群毎に、現在時間ステップ用の配置情報リストと、次時間ステップ用の配置情報リストを作成する。非隣接分割空間群は４つ決定されるので、配置情報リストは８個作成されることになる。また、各時間ステップの初期状態において、次時間ステップ用の配置情報リストの各要素は、何も格納されていない状態になっている。
【００５６】
また、本発明の移動体シミュレーションシステム３０が仮想移動体の移動計算をする際に用いるベクトル演算器のベクトルレジスタの本数をＮ本とする。仮想移動体登録部３３は、長さが最大でＮとなる配列（換言すれば、要素数が最大でＮとなる配列）を作成する。以下、この配列を「ベクトルリスト」と記す。仮想移動体登録部３３は、非隣接分割空間群毎に、仮想移動体が存在している分割空間を最大でＮ個選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択する。仮想移動体登録部３３は、選択した各仮想移動体（より具体的には、選択各仮想移動体の識別ＩＤ）をベクトルリストに登録する。仮想移動体登録部３３は、分割空間を最大でＮ個選択し、その分割空間から１つずつ選択した各仮想移動体の識別ＩＤをベクトルリストに登録する。従って、ベクトルリストの長さは、最大でＮとなる。
【００５７】
ベクトルリストは、並列計算による単位時間経過後の位置の計算対象となる仮想移動体（より具体的には、仮想移動体の識別ＩＤ）のリストである。
【００５８】
移動計算部３４は、仮想移動体登録部３３によってベクトルリストに登録された各識別ＩＤに対応する仮想移動体を参照し、各仮想移動体の単位時間経過後の位置の計算をベクトル処理によって実行する。すなわち、移動計算部３４は、各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算する。
【００５９】
また、仮想移動体登録部３３は、単位時間経過後の位置が計算された仮想移動体の識別ＩＤを、現在時間ステップ用の配置情報リストから削除する。さらに、移動計算部３４は、次時間ステップ用の配置情報リストにおける、計算された位置に該当する分割空間に対応する要素に、その識別ＩＤを追加する。
【００６０】
移動体シミュレーションシステム３０において、仮想移動体登録部３３の処理、および、その処理に続く移動計算部３４の処理が繰り返されることによって、時間ステップ毎の移動計算が実行され、移動シミュレーションが進行する。終了判定部３５は、その繰り返し処理の終了条件が満たされた否かを判定する。仮想移動体登録部３３および移動計算部３４は、終了判定部３５によって終了条件が満たされたと判定されるまで、処理を繰り返す。
【００６１】
例えば、全ての仮想移動体が目的地点に到達したこと、および、処理の繰り返し数が予め定められた値に達したことのいずれかが満たされたことを、上記の終了条件としてもよい。この場合、終了判定部３５は、全ての仮想移動体が目的地点に到達した場合、または、処理の繰り返し数が予め定められた値に達した場合に、終了条件が満たされたと判定する。ただし、終了条件として、他の条件が用いられてもよい。
【００６２】
図４は、移動空間分割部３２の構成例を示すブロック図である。移動空間分割部３２は、分割幅決定部４１と、分割空間決定部４２と、非隣接分割空間群決定部４３と、移動体配置情報作成部４４とを備える。
【００６３】
分割幅決定部４１は、シナリオに含まる個々の移動体情報を参照し、全ての仮想移動体の移動速度の中の最大値（最大移動速度と記し、その値をＶで表す。）を特定する。そして、分割幅決定部４１は、最大移動速度Ｖと単位時間Ｔに基づき、単位時間当たりの移動可能距離Ｌ（仮想移動体が単位時間当たりに移動可能な距離の最大値）を算出する。最大移動速度をＶ、単位時間をＴとしたときに、分割幅決定部４１は、Ｌ＝Ｖ×Ｔの計算によって、単位時間当たりの移動可能距離Ｌを算出する。さらに、分割幅決定部４１は、移動空間の分割幅Ｄを、Ｄ＝２Ｌの計算によって算出する。
【００６４】
分割空間決定部４２は、移動空間をＸ軸方向およびＹ軸方向に幅Ｄ毎に分割し、分割空間Aij を以下に示すように決定する。Aij は、より具体的には、各分割空間の座標領域である。
【００６５】
【数１】
2019028877.tif 000003
【００６６】
なお、
【数２】
2019028877.tif 000004
は、自然数の集合（つまり、０，１，２，・・・）を表す。
【００６７】
Ｌ＝２となる場合を例にすると、図５に示すように、Ｘ軸方向およびＹ軸方向に距離４毎に分割される。すなわち、Ｘ軸方向およびＹ軸方向にそれぞれ２個並ぶように配置された４つセルが１つの分割空間に相当するように、複数の分割空間が生成される。図５に示す例では、実線で示した個々の正方形の領域が分割空間に該当する。また、図５に示す例では、移動空間は、Ｘ軸方向に７分割され、Ｙ軸方向に５分割されているので、分割空間Aij は、全部で３５個存在する。なお、図５に示す例において、各分割空間Aij を識別するための添え字ｊ，ｊに関して、ｉは、０〜６の値をとり、ｊは、０〜４の値をとる。従って、各分割空間は、A00からA64まで存在する。
【００６８】
非隣接分割空間群決定部４３は、非隣接分割空間群（Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合）を４つ決定する。非隣接分割空間群決定部４３は、分割空間Aij の添え字となっているｉ，ｊが奇数か偶数かであるかに応じて、分割空間を４種類に分類し、分類された分割空間の集合を、それぞれ非隣接分割空間群として決定する。
【００６９】
具体的には、非隣接分割空間群決定部４３は、非隣接分割空間群Z1〜Z4を、以下に示すように決定する。
【００７０】
【数３】
2019028877.tif 000005
【００７１】
換言すれば、非隣接分割空間群決定部４３は、Ｘ軸方向の並びの順序が偶数番目であり、Ｙ軸方向の並びの順序が偶数番目である分割空間の集合である非隣接分割空間群Z1を決定する。また、非隣接分割空間群決定部４３は、Ｘ軸方向の並びの順序が偶数番目であり、Ｙ軸方向の並びの順序が奇数番目である分割空間の集合である非隣接分割空間群Z2を決定する。また、非隣接分割空間群決定部４３は、Ｘ軸方向の並びの順序が奇数番目であり、Ｙ軸方向の並びの順序が偶数番目である分割空間の集合である非隣接分割空間群Z3を決定する。また、非隣接分割空間群決定部４３は、Ｘ軸方向の並びの順序が奇数番目であり、Ｙ軸方向の並びの順序が奇数番目である分割空間の集合である非隣接分割空間群Z4を決定する。ここでは、Ｘ軸方向の並びの順序、および、Ｙ軸方向の並びの順序が、いずれも０番目から始まっているものとしている。
【００７２】
図６は、各分割空間が非隣接分割空間群Z1〜Z4に分類された状態の例を示す模式図である。移動空間は、Ｘ軸方向には０番目から６番目まで（ｉ＝０〜６に相当）、７分割されている。また、移動空間は、Ｙ軸方向には０番目から４番目まで（ｊ＝０〜４に相当）、５分割されている。図６において、同じ模様で示す分割空間は、Ｘ軸方向、Ｙ軸方向および斜め方向に１つ飛ばしで配置されていて、同じ模様で示す分割空間が、同一の非隣接分割空間群に属していることを表している。図６に示す例では、A00、A20、A40、A60、A02、A22、A42、A62、A04、A24、A44、A64は非隣接分割空間群Z1に属する。また、分割空間A01、A21、A41、A61、A03、A23、A43、A63は非隣接分割空間群Z2に属する。また、分割空間A10、A30、A50、A12、A32、A52、A14、A34、A54は非隣接分割空間群Z3に属する。また、分割空間A11、A31、A51、A13、A33、A53は非隣接分割空間群Z4に属する。
【００７３】
移動体配置情報作成部４４は、非隣接分割空間群Z1〜Z4毎に、現在時間ステップ用の配置情報リストと、次時間ステップ用の配置情報リストを作成する。従って、前述のように、配置情報リストは８個作成されることになる。また、既に述べたように、配置情報リストは、分割空間内に存在している仮想移動体の識別ＩＤを記録するための配列である。
【００７４】
図７は、上記の非隣接分割空間群Z1に関して作成された配置情報リストの例を示す模式図である。非隣接分割空間群Z1には、１２個の分割空間（A00、A20、A40、A60、A02、A22、A42、A62、A04、A24、A44、A64）が属する。従って、移動体配置情報作成部４４は、非隣接分割空間群Z1に関しては、１２個の要素を有する配列を、配置情報リストとする。また、配列に含まれる１２個の要素は、非隣接分割空間群Z1に属する１２個の分割空間と一対一に対応する。移動体配置情報作成部４４は、非隣接分割空間群Z1に属する分割空間毎に、分割空間内に存在する仮想移動体の識別ＩＤを、その分割空間に対応する配列内の要素にリスト形式で記録する。リスト形式で識別ＩＤを記録するので、１つの要素に複数の識別ＩＤを記録することができる（図７参照）。このような、配置情報リストを参照することによって、分割空間内に存在する仮想移動体の識別ＩＤを確認することができる。
【００７５】
移動シミュレーション開始時に、移動体配置情報作成部４４は、全ての仮想移動体のシミュレーション開始時の現在位置座標を参照し、非隣接分割空間群Z1に属する分割空間内に存在する仮想移動体を全て特定し、非隣接分割空間群Z1の現在時間ステップ用の配置情報リストにおいて、仮想移動体が存在している分割空間に対応する要素に、その仮想移動体の識別ＩＤを記録する。この結果、移動シミュレーション開始時における非隣接分割空間群Z1の現在時間ステップ用の配置情報リストが得られる。また、移動体配置情報作成部４４は、非隣接分割空間群Z1の次ステップ用の配置情報リストとして、現在時間ステップ用の配置情報リストと同数の要素（配列の要素）を有し、各要素に何も記録されていない状態の配置情報リストを作成する。ここでは、非隣接分割空間群Z1を例にして説明したが、移動体配置情報作成部４４は、他の非隣接分割空間群Z2、Z3、Z4に関しても、移動シミュレーション開始時における現在時間ステップ用の配置情報リストおよび次ステップ用の配置情報リストを作成する。
【００７６】
図８は、仮想移動体登録部３３の構成例を示すブロック図である。仮想移動体登録部３３は、非隣接分割空間群選択部８１と、分割空間選択部８２と、仮想移動体選択部８３と、ベクトルリスト登録部８４と、移動体配置情報更新部８５と、登録終了判定部８６とを備える。
【００７７】
非隣接分割空間群選択部８１は、非隣接分割空間群Z1〜Z4の中から未選択の非隣接分割空間群Znを１つ選択する。
【００７８】
分割空間選択部８２は、非隣接分割空間群選択部８１によって選択された非隣接分割空間群Zn内の分割空間Aij∈Znのうち、単位時間経過後の位置の座標が未だ計算されていない仮想移動体（以下、単位時間経過後の位置が未計算の仮想移動体と記す。）が存在する分割空間を、最大でＮ個選択する。なお、Ｎは、ベクトル演算器のベクトルレジスタの本数である。単位時間経過後の位置が未計算の仮想移動体が存在するか否かは、選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストの各分割空間に対応する要素を参照し、１つ以上の仮想移動体の識別ＩＤが記録されているか否かによって、判定することができる。
【００７９】
仮想移動体選択部８３は、分割空間選択部８２によって選択された分割空間毎に、分割空間内に存在していて、単位時間経過後の位置が未計算の仮想移動体を最大１つずつ選択する。すなわち、仮想移動体選択部８３は、選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストにおいて、選択された各分割空間Aijに対応する要素それぞれから、記録されている仮想移動体の識別ＩＤを最大１つ取得する。
【００８０】
ベクトルリスト登録部８４は、仮想移動体選択部８３によって選択された各仮想移動体の識別ＩＤをベクトルリストに登録する。
【００８１】
移動体配置情報更新部８５は、移動計算部３４によって単位時間経過後の位置が計算された仮想移動体の識別ＩＤを現在時間ステップ用の配置情報リストから削除する。そして、移動体配置情報更新部８５は、次時間ステップ用の配置情報リストにおいて、計算された単位時間経過後の位置を含む分割空間に対応する要素に、その仮想移動体の識別ＩＤを記録する。この処理は、単位時間経過後の位置が計算された仮想移動体について、単位時間の計算前にその仮想移動体が存在していた分割空間にその仮想移動体が存在しなくなったとみなし、単位時間経過後にその仮想移動体が存在する分割空間を記憶する処理であると言える。
【００８２】
また、移動体配置情報更新部８５は、全ての仮想移動体に対して、現在の時間ステップから単位時間経過後の位置の計算が完了ならば、非隣接分割空間群毎に、次時間ステップ用の配置情報リストに記録されている情報を、現在時間ステップ用の配置情報リストに上書きし、次時間ステップ用の配置情報リストの全要素に記録されている情報を削除する。この処理は、全ての仮想移動体の単位時間経過後の位置が計算された場合に、単位時間経過後に各仮想移動体が存在する分割空間を、各仮想移動体が現在存在する分割空間として記憶し直す処理であると言える。
【００８３】
登録終了判定部８６は、非隣接分割空間群選択部８１、分割空間選択部８２、仮想移動体選択部８３およびベクトルリスト登録部８４によって、移動空間内の全ての仮想移動体が選択され、ベクトルリストに登録され、単位時間経過後の位置の計算が終了したか否かを判定する。
【００８４】
図９は、移動計算部３４の構成例を示すブロック図である。移動計算部３４は、ベクトルリスト参照部９１と、移動体情報取得部９２と、ベクトル処理部９３とを備える。
【００８５】
ベクトルリスト参照部９１は、仮想移動体登録部３３によって仮想移動体の識別ＩＤが登録されたベクトルリストを参照し、ベクトル処理によって単位時間経過後の位置を計算する対象となる仮想移動体の識別ＩＤを取得する。
【００８６】
移動体情報取得部９２は、ベクトルリスト参照部９１によって取得された識別ＩＤに対応する各仮想移動体の移動体情報から、移動速度、移動方向、移動モデルを取得する。
【００８７】
ベクトル処理部９３は、移動体情報取得部９２によって取得された移動速度、移動方向および移動モデルを用い、単位時間経過後の位置をベクトル演算器によって計算する。移動モデルは、例えば、前述の（１）〜（３）に示す事項が定められた移動モデルであるが、移動モデルの例は、前述の例に限定されない。
【００８８】
シナリオ取得部３１、移動空間分割部３２、仮想移動体登録部３３、移動計算部３４および終了判定部３５は、例えば、移動体シミュレーションプログラムに従って動作するコンピュータのＣＰＵであって、ベクトル演算器を備えたＣＰＵによって実現される。この場合、ＣＰＵは、例えば、コンピュータのプログラム記憶装置（図３において図示略）等のプログラム記録媒体から移動体シミュレーションプログラムを読み込み、そのプログラムに従って、シナリオ取得部３１、移動空間分割部３２、仮想移動体登録部３３、移動計算部３４および終了判定部３５として動作すればよい。また、シナリオ取得部３１、移動空間分割部３２、仮想移動体登録部３３、移動計算部３４および終了判定部３５がそれぞれ別々のハードウェアによって実現されてもよい。
【００８９】
また、移動体シミュレーションシステム３０は、２つ以上の物理的に分離した装置が有線または無線で接続されている構成であってもよい。
【００９０】
次に、本実施形態の処理経過について説明する。図１０は、第１の実施形態の移動体シミュレーションシステムの処理経過の例を示すフローチャートである。
【００９１】
シナリオ取得部３１は、シナリオ（移動空間情報と、各仮想移動体に対応する移動体情報とを合わせた情報群）を取得する（ステップＳ１０１）。例えば、シナリオ取得部３１は、予め作成されたシナリオを記憶している外部の情報処理装置にアクセスして、シナリオを取得すればよい。シナリオ取得部３１は、移動体シミュレーションシステム３０が備えるメモリ（図３において図示略）に、取得したシナリオを記憶させる。
【００９２】
移動空間分割部３２は、ステップＳ１０１で取得されたシナリオを参照し、仮想移動体の単位時間当たりの移動可能距離Ｌを計算する。そして、移動空間分割部３２は、移動空間を、Ｘ軸方向およびＹ軸方向に幅２Ｌ毎に分割し、４つの非隣接分割空間群を決定する。さらに、移動空間分割部３２は、非隣接分割空間群毎に、シミュレーション開始時における現在時間ステップ用の配置情報リストおよび次ステップ用の配置情報リストを作成する（ステップＳ１０２）。１つの非隣接分割空間群に属する分割空間同士は、少なくとも２Ｌ以上離れている。従って、１つの非隣接分割空間群において、異なる分割空間に存在している仮想移動体同士も２Ｌ以上離れている。よって、その仮想移動体同士は、単位時間経過後に衝突する可能性がなく、仮想移動体同士には、衝突判定における依存関係がない。
【００９３】
次に、仮想移動体登録部３３は、ステップＳ１０２で決定された４つの非隣接分割空間群の中から、非隣接分割空間群を１つ選択する。そして、仮想移動体登録部３３は、現在時間ステップ用の配置情報リストを基に、その非隣接分割空間群から、最大でＮ個の分割空間を選択する。さらに、仮想移動体登録部３３は、選択した各分割空間から単位時間経過後の位置が未計算の仮想移動体を１つずつ選択し、その仮想移動体の識別ＩＤをベクトルリストに登録する（ステップＳ１０３）。上記のように、１つの非隣接分割空間群から選択された各分割空間から１つずつ選択された仮想移動体は、必ず２Ｌ以上離れている。従って、その仮想移動体同士には、衝突判定に伴う依存関係がなく、移動計算をベクトル処理によって並列計算することが可能となる。
【００９４】
次に、移動計算部３４は、ベクトルリストに登録された識別ＩＤに対応する仮想移動体の移動体情報を参照し、その各仮想移動体の単位時間経過後の位置の計算をベクトル処理によって行う（ステップＳ１０４）。
【００９５】
次に、仮想移動体登録部３３は、移動空間内の全ての仮想移動体について、単位時間経過後の位置の計算が終了したか判定する（ステップＳ１０５）。また、仮想移動体登録部３３は、ステップＳ１０５において、仮想移動体の移動計算結果に基づき、配置情報リストを更新する。全ての仮想移動体について単位時間経過後の位置の計算が終了している場合（ステップＳ１０５におけるＹＥＳ）、終了判定部３５は、シミュレーション終了条件が満たされたか否かを判定する（ステップＳ１０６）。全ての仮想移動体について単位時間経過後の位置の計算が終了していない場合（ステップＳ１０５におけるＮＯ）、ステップＳ１０３に移行し、ステップＳ１０３〜Ｓ１０５の処理を再度実行する。
【００９６】
また、後述するように、ステップＳ１０３やステップＳ１０５は、複数の処理を含む。ステップＳ１０５における判定に基づいて、ステップＳ１０３内のどの処理に移行するかについては、後述する。
【００９７】
シミュレーション終了条件は、ステップＳ１０３〜Ｓ１０６の繰り返し処理の終了条件であると言うこともできる。例えば、終了判定部３５は、ステップＳ１０６において、全ての仮想移動体が目的地点に到達した場合、または、処理の繰り返し数が予め定められた値に達した場合に、終了条件が満たされたと判定する。
【００９８】
終了条件が満たされていなければ（ステップＳ１０６におけるＮＯ）、仮想移動体登録部３３、移動計算部３４および終了判定部３５は、ステップＳ１０３〜Ｓ１０６の処理を再度実行する。この際、移動体シミュレーションシステム３０は時間ステップを、次の時間ステップに進める。そして、ステップＳ１０３の冒頭（後述のステップＳ１２１、図１２を参照。）から処理を実行する。また、終了条件が満たされていれば（ステップＳ１０６におけるＹＥＳ）、移動体シミュレーションシステム３０は、移動シミュレーションを終了する。
【００９９】
図１１は、ステップＳ１０２（図１０参照）の処理経過の例を示すフローチャートである。ステップＳ１０２において、まず、分割幅決定部４１は、最大移動速度Ｖ（全ての仮想移動体の移動速度の中の最大値）と、単位時間Ｔを用い、仮想移動体の単位時間当たりの移動可能距離ＬをＬ＝Ｖ×Ｔによって算出する（ステップＳ１１１）。
【０１００】
次に、分割幅決定部４１は、移動空間の分割幅ＤをＤ＝２Ｌの計算によって算出する（ステップＳ１１２）。なお、分割幅Ｄを２Ｌ以上の値に設定することも可能である。しかし、移動空間の分割数を最大化し、並列性を向上させるために、Ｄを、最小の分割幅である２Ｌに設定することが好ましい。
【０１０１】
次に、分割空間決定部４２は、移動空間を、原点からＸ軸方向およびＹ軸方向に距離Ｄ毎に分割し、分割空間Aij を決定する（ステップＳ１１３）。Aij は、より具体的には、各分割空間の座標領域であり、以下のように定義される。
【０１０２】
【数４】
2019028877.tif 000006
【０１０３】
次に、非隣接分割空間群決定部４３は、４つの非隣接分割空間群を決定する（ステップＳ１１４）。非隣接分割空間群決定部４３は、分割空間Aij の添え字となっているｉ，ｊが奇数か偶数かであるかに応じて、分割空間を４種類に分類し、分類された分割空間の集合を、それぞれ非隣接分割空間群として決定する。ｉは、Ｘ軸方向の並びの順序を表し、ｊは、Ｙ軸方向の並びの順序を表している。また、この並びの順序はいずれも０番目から始まっているものとする。（ｉ，ｊ）は、（偶数番目、偶数番目）、（偶数番目、奇数番目）、（奇数番目、偶数番目）、（奇数番目、奇数番目）の４種類に分類されるので、４つの非隣接分割空間群が決定される。
【０１０４】
具体的には、非隣接分割空間群決定部４３は、以下に示すように定義される４つの非隣接分割空間群Z1〜Z4を決定する。
【０１０５】
【数５】
2019028877.tif 000007
【０１０６】
非隣接分割空間群は、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である。従って、１つの非隣接分割空間群に属する分割空間同士は、距離Ｄ以上離れている。
【０１０７】
上記のように決定された４つの非隣接分割空間群を図６に模式的に示している。図６については、既に説明したので、ここでは説明を省略する。
【０１０８】
次に、移動体配置情報作成部４４は、非隣接分割空間群毎に、非隣接分割空間群に属する分割空間内に存在する仮想移動体を全て特定し、現在時間ステップ用の配置情報リストにおいて、仮想移動体が存在している分割空間に対応する要素に、その仮想移動体の識別ＩＤを記録する（ステップＳ１１５）。また、移動体配置情報作成部４４は、ステップＳ１１５において、非隣接分割空間群毎に、次ステップ用の配置情報リストとして、現在時間ステップ用の配置情報リストと同数の要素（配列の要素）を有し、各要素に何も記録されていない状態の配置情報リストを作成する。
【０１０９】
ステップＳ１１５が終了することで、ステップＳ１０２が終了する。
【０１１０】
図１２は、ステップＳ１０３（図１０参照）の処理経過の例を示すフローチャートである。なお、ステップＳ１０３〜ステップＳ１０６のループ処理１回は、１つの時間ステップの処理である。ステップＳ１０３〜ステップＳ１０６のループ処理が繰り返されることで時間ステップが進行する。
【０１１１】
ステップＳ１０３において、まず、非隣接分割空間群選択部８１は、非隣接分割空間群Z1〜Z4から未だ選択されていない非隣接分割空間群Znを１つ選択する（ステップＳ１２１）。
【０１１２】
次に、分割空間選択部８２は、選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストを参照し、分割空間Aij∈Znのうち、単位時間経過後の位置が未計算の仮想移動体が１つ以上存在する分割空間を、最大でＮ個選択する（ステップＳ１２２）。
【０１１３】
例えば、図６に示すように、４種類の非隣接分割空間群が決定されたとする。そして、非隣接分割空間群選択部８１が非隣接分割空間群Z1を選択したとする。また、非隣接分割空間群Z1の現在時間ステップ用の配置情報リストが、図７に示す配置情報リストであるとする。さらに、分割空間選択部８２が図７に示す配置情報リストを参照して分割空間を選択し、移動計算部３４がＮ＝４のベクトル演算器でベクトル処理を行うものとする。図７に示すように、非隣接分割空間群Z1内にはA00〜A64の１２個の分割空間が属している。この１２個の分割空間のうち、単位時間経過後の位置が未計算の仮想移動体が１つ以上存在する分割空間（換言すれば、対応する要素に１つ以上の識別ＩＤが記録されている分割空間）は、A20、A02、A22、A42、A62、A24、A44、A64の８個である。よって、分割空間選択部８２は、これら８つの分割空間から４つの分割空間を選択する。
【０１１４】
一方で、上記のような分割空間の数が４つ未満の場合は、分割空間選択部８２は、単位時間経過後の位置が未計算の仮想移動体が１つ以上存在する分割空間を、選択中の非隣接分割空間群Z1内に残っている分だけ選択する。従って、分割空間選択部８２によって選択される分割空間の数が４未満となることもあり得る。
【０１１５】
なお、分割空間選択部８２は、選択されていない非隣接分割空間群Z2〜Z4に属する分割空間は選択しない。
【０１１６】
次に、仮想移動体選択部８３は、分割空間選択部８２により選択された分割空間毎に、分割空間内に存在する、単位時間経過後の位置が未計算の仮想移動体を最大１つずつ選択する（ステップＳ１２３）。同一分割空間内の仮想移動体は衝突の可能性があり、ベクトル処理により同時に移動計算を行うことができない。そのため、ステップＳ１２３において、仮想移動体選択部８３は、各分割空間から１つずつ仮想移動体を選択する。なお、仮想移動体選択部８３が分割空間から仮想移動体を選択する順序は任意であり、リストの先頭から仮想移動体を選択してもよく、ランダムに仮想移動体を選択してもよい。
【０１１７】
次に、ベクトルリスト登録部８４は、仮想移動体選択部８３によって選択された仮想移動体の識別ＩＤをベクトルリストに登録する（ステップＳ１２４）。
【０１１８】
ステップＳ１２４が終了することで、ステップＳ１０３が終了する。
【０１１９】
図１３は、ステップＳ１０４（図１０参照）の処理経過の例を示すフローチャートである。
【０１２０】
ステップＳ１０４において、ベクトルリスト参照部９１は、ベクトルリストを参照し、単位時間経過後の位置を計算する対象となる各仮想移動体の識別ＩＤを取得する（ステップＳ１４１）。
【０１２１】
次に、移動体情報取得部９２は、ステップＳ１４１において取得された各識別ＩＤに対応する各仮想移動体の移動体情報を取得する（ステップＳ１４２）。各仮想移動体の移動体情報は、ステップＳ１０１（図１０参照）で取得され、移動体シミュレーションシステム３０が備えるメモリ（図３において図示略）に記憶されている。移動体情報には、対応する仮想移動体の識別ＩＤが含まれているので、移動体情報取得部９２は、ステップＳ１４１で取得された識別ＩＤに対応する移動体情報をメモリから取得すればよい。
【０１２２】
次に、ベクトル処理部９３は、ステップＳ１４２において取得された各移動体情報を用い、各想移動体の単位時間経過後の位置をベクトル演算器によって計算する（ステップＳ１４３）。つまり、ベクトル処理部９３は、各移動体情報に含まれている現在位置座標、目標位置座標、移動速度、移動方向を用い、移動体情報に含まれている移動モデルが示す位置（単位時間経過後の位置）を計算するための計算式やルールに従った演算を、ベクトル演算器によって実行し、各想移動体の単位時間経過後の位置を求める。本実施形態では、移動モデルとして、全ての仮想移動体に対して前述の（１）〜（３）の事項が定められている。従って、ベクトル処理部９３は、前述の（１）〜（３）の事項に従って、ベクトル演算器によって、各想移動体の単位時間経過後の位置を計算する。
【０１２３】
以下、ベクトル処理による移動計算の高速化の例を示す。単位時間経過後の移動先となる位置のＸ座標（以下、移動先の位置のＸ座標と記す。）は、以下に示す式（１）で表される。
【０１２４】
「移動先の位置のＸ座標」＝「現在位置座標のＸ座標」＋「仮想移動体の移動速度」×「単位時間」×「移動方向の余弦値」        ・・・式（１）
【０１２５】
この場合、ベクトル処理部９３は、以下の（ａ），（ｂ），（ｃ）の３つの演算を、ベクトルリストに登録されている全ての仮想移動体に対して行う。
（ａ）  「仮想移動体の移動速度」と「単位時間」との乗算
（ｂ）  （ａ）の乗算結果と「移動方向の余弦値」との乗算
（ｃ）  （ｂ）の乗算結果と、「現在位置座標のＸ座標」との加算
【０１２６】
この際、ベクトル処理部９３は、（ａ）に関して、各仮想移動体の移動速度および単位時間を各々のベクトルレジスタにロードし、１回の乗算命令によって並列に計算する。また、ベクトル処理部９３は、（ｂ）に関して、各仮想移動体の（ａ）の乗算結果および移動方向の余弦値を各々のベクトルレジスタにロードし、１回の乗算命令によって並列に計算する。また、ベクトル処理部９３は、（ｃ）に関しても同様に、各仮想移動体の（ｂ）の乗算結果および現在位置座標のＸ座標を各々のベクトルレジスタにロードし、１回の加算命令によって並列に計算する。
【０１２７】
また、Ｎ個の仮想移動体に対して、式（１）の計算をスカラ処理で行う場合、（ａ），（ｂ）の乗算はＮ回ずつ行うので、２Ｎ回の乗算命令が必要となる。また、（ｃ）の加算はＮ回行うので、Ｎ回の加算命令が必要になる。一方、ベクトル処理を実行する場合、上記のように、ベクトル処理部９３は、２回の乗算命令と１回の加算命令を実行すればよく、１回の命令でＮ個の演算を並列に実行する。従って、ベクトル処理を実行する場合、スカラ処理を実行する場合に比べて、実行時間は１／Ｎに短縮される。
【０１２８】
ステップＳ１４３が終了することで、ステップＳ１０４が終了し、ステップＳ１０５に移行する。
【０１２９】
図１４は、ステップＳ１０５（図１０参照）の処理経過の例を示すフローチャートである。ステップＳ１０５において、移動体配置情報更新部８５（図８参照）は、現在時間ステップ用の配置情報リストから、単位時間経過後の位置の計算が行われた仮想移動体の識別ＩＤを削除する。そして、移動体配置情報更新部８５は、計算された単位時間経過後の位置に対応する次時間ステップ用の配置情報リスト内の要素（配列の要素）に、単位時間経過後の位置の計算が行われたその仮想移動体の識別ＩＤを記録する（ステップＳ１２５）。現在時間ステップ用の配置情報リストから識別ＩＤが削除され、次時間ステップ用の配置情報リストに識別ＩＤが登録された仮想移動体に関しては、現在の時間ステップにおける単位時間経過後の位置の計算が終了したことになる。
【０１３０】
次に、登録終了判定部８６（図８参照）は、選択中の非隣接分割空間群Zn内の全ての仮想移動体がステップＳ１２３（図１２参照）において選択され、移動計算部３４によって単位時間経過後の位置の計算が行われたか否かを判定する（ステップＳ１２６）。すなわち、登録終了判定部８６は、選択中の非隣接分割空間群Zn内の全ての仮想移動体の移動計算が終了したか否かを判定する。登録終了判定部８６は、選択中の非隣接分割空間群Znの現在時間ステップ用の配置情報リストの全ての要素に仮想移動体の識別ＩＤが記録されていなければ、選択中の非隣接分割空間群Zn内の全ての仮想移動体の移動計算が終了したと判定すればよい（ステップＳ１２６におけるＹＥＳ）。また、登録終了判定部８６は、現在時間ステップ用の配置情報リストのいずれかの要素に仮想移動体の識別ＩＤが記録されているならば、移動計算が行われてない仮想移動体が残っていると判定すればよい（ステップＳ１２６におけるＮＯ）。
【０１３１】
選択中の非隣接分割空間群Zn内の仮想移動体のうち、移動計算が行われてない仮想移動体が残っている場合（ステップＳ１２６におけるＮＯ）、ステップＳ１２２（図１２参照）に移行し、ステップＳ１２２以降の処理を繰り返す。また、選択中の非隣接分割空間群Zn内の全ての仮想移動体の移動計算が終了した場合（ステップＳ１２６におけるＹＥＳ）、ステップＳ１２７に移行する。
【０１３２】
ステップＳ１２７において、登録終了判定部８６は、全ての非隣接分割空間群がステップ１２１（図１２参照）において選択されたか否かを判定する。未選択の非隣接分割空間群が残っている場合（ステップＳ１２７におけるＮＯ）、ステップＳ１２１（図１２参照）に移行し、ステップＳ１２１以降の処理を繰り返す。全ての非隣接分割空間群が選択済みである場合（ステップＳ１２７におけるＹＥＳ）、ステップＳ１２８に移行する。
【０１３３】
ステップＳ１２８において、移動体配置情報更新部８５は、非隣接分割空間群毎に、次時間ステップ用の配置情報リストに記録されている情報を現在時間ステップ用の配置情報リストに上書きし、次時間ステップ用の配置情報リストの全要素から、記録されている情報を削除する。この結果、現在時間ステップ用の配置情報リストは、次の時間ステップの処理において、その時間ステップにおける現在の時間ステップの情報として使用することができる。
【０１３４】
また、移動体配置情報更新部８５は、例えば、ステップＳ１２８において、全ての仮想移動体について計算された単位時間経過後の位置の座標によって、それぞれの仮想移動体の移動体情報に含まれる現在位置座標を更新する。また、移動体配置情報更新部８５は、全ての仮想移動体について、その現在位置座標に基づいて移動方向を計算し、その移動方向で、それぞれの仮想移動体の移動体情報に含まれる移動方向を更新する。なお、移動体情報に含まれる現在位置座標および移動方向の更新は、別のタイミングで実行してもよい。
【０１３５】
ステップＳ１２８が終了すると、ステップＳ１０６（図１０参照）に移行する。ステップＳ１０６において、終了判定部３５は、シミュレーション終了条件が満たされたか否かを判定する。終了条件が満たされていれば（ステップＳ１０６におけるＹＥＳ）、移動体シミュレーションシステム３０は、移動シミュレーションを終了する。また、終了条件が満たされていなければ（ステップＳ１０６におけるＮＯ）、終了判定部３５は、時間ステップを次の時間ステップに進め、ステップＳ１０３（より具体的にはステップＳ１２１、図１２参照。）に移行し、ステップＳ１２１以降の処理を繰り返す。
【０１３６】
本実施形態によれば、移動空間分割部３２が、移動可能距離Ｌに基づく空間分割を行い、仮想移動体登録部３３が、隣接しない分割空間から仮想移動体を選択する。その結果、単位時間経過後に衝突の発生する可能性がなく、依存関係のない仮想移動体が選択される。従って、移動速度、移動方向の異なる複数の仮想移動体の移動シミュレーションにおいて、移動モデルにおいて移動体同士の衝突判定を含む場合でも、ベクトル演算器によって高速に移動シミュレーションを実行することができる
【０１３７】
また、高速に移動シミュレーションを実行できるので、例えば、道路等の状況の変化に合わせて誘導方針を変更する場合であっても、再シミュレーションをリアルタイムに実行することができる。
【０１３８】
実施形態２．
第２の実施形態における移動体シミュレーションシステムの構成は、第１の実施形態と同様に、図３に示すブロック図で表すことができる。また、移動体シミュレーションシステム３０が備える移動空間分割部３２、移動計算部３４の構成もそれぞれ、第１の実施形態と同様に、図４、図９に示すブロック図で表すことができる。以下、適宜、これらの図面を参照して、本発明の第２の実施形態について説明する。
【０１３９】
なお、シナリオ取得部３１、移動空間分割部３２、移動計算部３４および終了判定部３５は、第１の実施形態におけるシナリオ取得部３１、移動空間分割部３２、移動計算部３４および終了判定部３５と同様であり、説明を省略する。
【０１４０】
また、第２の実施形態の処理経過は、第１の実施形態と同様に、図１０に示すフローチャートで表すことができる。ただし、第２の実施形態では、仮想移動体登録部３３の動作が、第１の実施形態とは一部異なる。そのため、ステップＳ１０３（図１０参照）の処理が、第１の実施形態とは一部異なる。ステップＳ１０１，Ｓ１０２，Ｓ１０４、Ｓ１０５、Ｓ１０６は、第１の実施形態におけるステップＳ１０１，Ｓ１０２，Ｓ１０４、Ｓ１０５、Ｓ１０６と同様である。
【０１４１】
次に、第２の実施形態における仮想移動体登録部３３の構成について説明する。図１５は、第２の実施形態における仮想移動体登録部３３の構成例を示すブロック図である。第２の実施形態における仮想移動体登録部３３は、非隣接分割空間群選択部８１、分割空間選択部８２、仮想移動体選択部８３、ベクトルリスト登録部８４、移動体配置情報更新部８５および登録終了判定部８６に加え、選択順序決定部１５１を備える。
【０１４２】
選択順序決定部１５１は、非隣接分割空間群選択部８１によって選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストの要素を、仮想移動体の識別ＩＤの記録数の多い順に並び替える。そして、選択順序決定部１５１は、識別ＩＤの記録数がより多い要素に対応する分割空間に対して、より高い選択優先順位を与える。従って、記録されている識別ＩＤがより多い要素に対応する分割空間ほど、選択優先順位がより高くなり、記録されている識別ＩＤがより少ない要素に対応する分割空間ほど、選択優先順位が低くなる。
【０１４３】
選択優先順位は、分割空間選択部８２が分割空間を選択する際の優先順位である。すなわち、分割空間選択部８２は、選択優先順位が高い分割空間から選択していく。
【０１４４】
第２の実施形態において、仮想移動体登録部３３は、非隣接分割空間群から分割空間を最大でＮ個選択する際に、その非隣接分割空間群に含まれている各分割空間に対して、存在している仮想移動体の数が多い順に優先順序を決定し、その優先順序に従って、仮想移動体が存在している分割空間を最大でＮ個選択する処理を行っているということができる。
【０１４５】
次に、第２の実施形態の処理経過について説明する。前述のように、第２の実施形態の処理経過は、第１の実施形態と同様に、図１０に示すフローチャートで表すことができる。さらに、ステップＳ１０１，Ｓ１０２，Ｓ１０４、Ｓ１０５、Ｓ１０６（図１０参照）は、第１の実施形態におけるステップＳ１０１，Ｓ１０２，Ｓ１０４、Ｓ１０５、Ｓ１０６と同様であり、説明を省略する。
【０１４６】
図１６は、第２の実施形態におけるステップＳ１０３の処理経過の例を示すフローチャートである。
【０１４７】
第２の実施形態におけるステップＳ１０３が開始されると、ステップＳ１２１を開始する。第２の実施形態におけるステップＳ１２１は、第１の実施形態におけるステップＳ１２１（図１２参照）と同様の処理である。
【０１４８】
次に、選択順序決定部１５１は、非隣接分割空間群選択部８１によって選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストの各要素を、識別ＩＤの記録数の多い順に並び替え、識別ＩＤの記録数がより多い要素に対応する分割空間に対して、より高い選択優先順位を与える（ステップＳ１６１）。
【０１４９】
現在時間ステップ用の配置情報リストの要素の並び替えの例を示す。要素が並び替えられる前の配置情報リストが、図７に示す配置情報リストであるとする。この場合、識別ＩＤの記録数の多い順に要素を並び替えると、配置情報リストは、図１７に示すようになる。分割空間選択部８２は、A42、A64、A24、A44、A02、A62、A20、A22、A00、A40、A60、A04の順に、選択優先順位を与える（図１７参照）。従って、分割空間A42 の選択優先順位が最も高く定められる。
【０１５０】
次に、分割空間選択部８２は、選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストを参照し、選択順序決定部１５１によって決定された選択優先順位に従って、単位時間経過後の位置が未計算の仮想移動体が存在する分割空間を、最大でＮ個選択する（ステップＳ１６２）。
【０１５１】
ステップＳ１６２が終了後、ステップＳ１２３およびステップＳ１２４に移行する。なお、ステップＳ１２３、Ｓ１２４は第１の実施形態におけるステップＳ１２３、Ｓ１２４と同様の処理である。
【０１５２】
ステップ１２４が終了することで、ステップＳ１０３が終了し、ステップＳ１０４（図１３参照）に移行する。さらに、ステップＳ１０４の終了後、ステップＳ１０５（図１４参照）に移行する。ステップ１０５内で実行されるステップＳ１２６において、移動計算が行われてない仮想移動体が残っていると判定された場合（ステップＳ１２６におけるＮＯ）、ステップＳ１６１（図１６参照）に移行し、ステップＳ１６１以降の処理を繰り返す。また、ステップ１０５内で実行されるステップＳ１２７において、未選択の非隣接分割空間群が残っていると判定された場合（ステップＳ１２７におけるＮＯ）、図１６に示すステップＳ１２１に移行し、ステップＳ１２１以降の処理を繰り返す。
【０１５３】
その他の点は、第１の実施形態と同様である。
【０１５４】
第２の実施形態では、選択順序決定部１５１が、配置情報リストの各要素を、識別ＩＤの記録数の多い順に並び替え、識別ＩＤの記録数がより多い要素に対応する分割空間に対して、より高い選択優先順位を与える。そのため、ステップＳ１０３〜Ｓ１０５のループ処理の繰り返し数を、最小化することができる。
【０１５５】
以下、図７に示す現在時間ステップ用の配置情報リストの上位の要素側から（すなわち、A00 側から）順に、識別ＩＤが登録されている要素を特定し、その要素に対応する分割空間を選択する場合（第１の選択方法と記す。）と、図７に示す要素を識別ＩＤの記録数の多い順に並び替えた配置情報リスト（図１７参照）における選択優先順位が上位の方から分割空間を選択する場合（第２の選択方法と記す。）とを比較する。また、ここでは、ベクトル演算器のベクトルレジスタの本数が４であるものとする。すなわち、Ｎ＝４であり、分割空間選択部８２は、分割空間を最大で４個選択する場合を例にして説明する。なお、以下に示す例では、選択されている非隣接分割空間群はZ1である。
【０１５６】
まず、図７を参照して、第１の選択方法の場合について説明する。分割空間選択部８２が１回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A20、A02、A22、A42を選択し、仮想移動体選択部８３は、その４つの分割空間から識別ＩＤとして、“１”，“２”，“４”，“５”を選択する（図７参照）。そして、その４つの識別ＩＤがベクトルリストに登録され、その４つの識別ＩＤに対応する仮想移動体の単位時間経過後の位置の計算が終了すると、ステップＳ１２５（図１４参照）において、移動体配置情報更新部８５が、図７に示す現在時間ステップ用の配置情報リストから、上記の４つの識別ＩＤを削除し、次時間ステップ用の配置情報リストにその４つの識別ＩＤを記録する。この結果、分割空間A20およびA22には、単位時間経過後の位置が未計算の仮想移動体が存在しなくなるので、分割空間A20およびA22は選択対象から除外される。分割空間選択部８２が２回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A02、A42、A62、A24を選択し、同様の処理が実行される。分割空間選択部８２が３回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A42、A62、A24、A44を選択し、同様の処理が実行される。分割空間選択部８２が４回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A42、A24、A44、A64を選択し、同様の処理が実行される。分割空間選択部８２が５回目に分割空間を選択する場合、単位時間経過後の位置が未計算の仮想移動体が存在している分割空間は、A44、A64のみであり、分割空間A44には１つの仮想移動体が存在し、分割空間A46には３つの仮想移動体が存在する。従って、分割空間選択部８２が５回目に分割空間を選択する場合、分割空間選択部８２は、２つの分割空間A44、A64を選択し、ベクトルリストには２つの仮想移動体の識別ＩＤが登録される。分割空間選択部８２が６回目に分割空間を選択する場合、分割空間選択部８２は、１つの分割空間A64 を選択し、１つの仮想移動体の移動計算が行われる。分割空間選択部８２が７回目に分割空間を選択する場合も、分割空間選択部８２は、１つの分割空間A64 を選択し、１つの仮想移動体の移動計算が行われる。この結果、非隣接分割空間Z1における全ての仮想移動体の移動計算が終了する。上記のように、図７に例示する配置情報リストに対して、第１の選択方法を適用した場合、７回の繰り返し処理が行われる。
【０１５７】
次に、図１７を参照して、第２の選択方法の場合について説明する。図１７は、図７に示す要素を識別ＩＤの記録数の多い順に並び替えた配置情報リストを示している。そして、A42、A64、A24、A44、A02、A62、A20、A22、A00、A40、A60、A04の順に、選択優先順位が与えられている。分割空間選択部８２が１回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A42、A64、A24、A44を選択し、仮想移動体選択部８３は、その４つの分割空間から識別ＩＤとして、“５”，“１７”，“１１”，“１４”を選択する（図１７参照）。そして、その４つの識別ＩＤがベクトルリストに登録され、その４つの識別ＩＤに対応する仮想移動体の単位時間経過後の位置の計算が終了すると、ステップＳ１２５（図１４参照）において、移動体配置情報更新部８５が、図１７に示す現在時間ステップ用の配置情報リストから、上記の４つの識別ＩＤを削除し、次時間ステップ用の配置情報リストにその４つの識別ＩＤを記録する。分割空間選択部８２が２回目に分割空間を選択する場合、分割空間選択部８２は、１回目と同様に、４つの分割空間A42、A64、A24、A44を選択し、同様の処理が実行される。その結果、分割空間A24およびA44に対応する要素に記録されている識別ＩＤの数が１となる。また、分割空間A02およびA62に対応する要素に記録されている識別ＩＤの数は２である。従って、選択順序決定部１５１は、ステップＳ１６１において、A02およびA62の選択優先順位が、A24およびA44よりも高くなるように、選択優先順位を変更する。
【０１５８】
そして、ステップＳ１６１に続いて、分割空間選択部８２が３回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A42、A64、A02、A62を選択し、同様の処理が実行される。この結果、A42、A64、A02、A62、A24、A44、A20、A22に対応する要素に記録されている識別ＩＤの数は、いずれも１となる。この場合、選択順序決定部１５１は、ステップＳ１６１において選択優先順位を変更しなくてよい。そして、ステップＳ１６１に続いて、分割空間選択部８２が４回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A42、A64、A02、A62を選択し、同様の処理が実行される。次のステップＳ１６１では、選択順序決定部１５１は、A24、A44、A20、A22の選択優先順位がA42、A64、A02、A62よりも高くなるように、選択優先順位を変更する。そして、ステップＳ１６１に続いて、分割空間選択部８２が５回目に分割空間を選択する場合、分割空間選択部８２は、４つの分割空間A24、A44、A20、A22を選択し、同様の処理が実行される。この結果、非隣接分割空間Z1における全ての仮想移動体の移動計算が終了する。上記のように、図７に示す要素を識別ＩＤの記録数の多い順に並び替えた配置情報リスト（図１７参照）に対して、第２の方法を適用した場合、５回の繰り返し処理が実現される。
【０１５９】
従って、第２の選択方法では、第１の選択方法よりも、繰り返し処理を削減できることが分かる。上記の例では、第１の選択方法における繰り返し処理の回数は７回であり、第２の選択方法における繰り返し処理の回数は５回であり、繰り返し処理の回数が２回削減されている。
【０１６０】
なお、上記の第２の選択方法の例では、分割空間選択部８２は、毎回、４つの分割空間を選択し、４つの識別ＩＤがベクトルリストに登録され、ベクトル処理が実行される。従って、最大で４つまで識別ＩＤを登録可能なベクトルリストに空きができることがなく、常に最大の並列度でベクトル処理が行われる。このように、第２の選択方法の例では、ベクトルリストの空きが最小化されるので、繰り返し処理（ステップＳ１０３〜Ｓ１０５のループ処理）の回数も最小化される。
【０１６１】
第２の実施形態においても、第１の実施形態と同様の効果が得られる。さらに、第２の実施形態では、選択順序決定部１５１が、非隣接分割空間群選択部８１によって選択された非隣接分割空間群Znの現在時間ステップ用の配置情報リストの要素を、仮想移動体の識別ＩＤの記録数の多い順に並び替える。そして、選択順序決定部１５１が、識別ＩＤの記録数がより多い要素に対応する分割空間に対して、より高い選択優先順位を与える。また、分割空間選択部８２は、選択優先順位が高い分割空間から選択していく。従って、上記のように、ベクトルリストの空きが最小化することができ、ステップＳ１０３〜Ｓ１０５のループ処理の繰り返し数を最小化することができる。従って、第２の実施形態では、移動シミュレーションをさらに高速化することができる。
【０１６２】
図１８は、本発明の各実施形態に係るコンピュータの構成例を示す概略ブロック図である。コンピュータ１０００は、ＣＰＵ１００１と、主記憶装置１００２と、補助記憶装置１００３と、インタフェース１００４とを備える。
【０１６３】
各実施形態の移動体シミュレーションシステム３０は、コンピュータ１０００に実装される。移動体シミュレーションシステム３０の動作はプログラム（移動体シミュレーションプログラム）の形式で補助記憶装置１００３に記憶されている。ＣＰＵ１００１は、プログラムを補助記憶装置１００３から読み出して主記憶装置１００２に展開し、そのプログラムに従って上記の処理を実行する。なお、ＣＰＵ１００１は、ベクトル演算器を備える。
【０１６４】
補助記憶装置１００３は、一時的でない有形の媒体の例である。一時的でない有形の媒体の他の例として、インタフェース１００４を介して接続される磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory ）、ＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory ）、半導体メモリ等が挙げられる。また、このプログラムが通信回線によってコンピュータ１０００に配信される場合、配信を受けたコンピュータ１０００がそのプログラムを主記憶装置１００２に展開し、上記の処理を実行してもよい。
【０１６５】
また、プログラムは、前述の処理の一部を実現するためのものであってもよい。さらに、プログラムは、補助記憶装置１００３に既に記憶されている他のプログラムとの組み合わせで前述の処理を実現する差分プログラムであってもよい。
【０１６６】
また、各構成要素の一部または全部は、汎用または専用の回路（circuitry ）、プロセッサ等やこれらの組み合わせによって実現されてもよい。これらは、単一のチップによって構成されてもよいし、バスを介して接続される複数のチップによって構成されてもよい。各構成要素の一部または全部は、上述した回路等とプログラムとの組み合わせによって実現されてもよい。
【０１６７】
各構成要素の一部または全部が複数の情報処理装置や回路等により実現される場合には、複数の情報処理装置や回路等は集中配置されてもよいし、分散配置されてもよい。例えば、情報処理装置や回路等は、クライアントアンドサーバシステム、クラウドコンピューティングシステム等、各々が通信ネットワークを介して接続される形態として実現されてもよい。
【０１６８】
次に、本発明の概要について説明する。図１９は、本発明の移動体シミュレーションシステムの概要を示すブロック図である。本発明の移動体シミュレーションシステムは、コンピュータ内に表現された複数の仮想移動体の単位時間経過後の位置の計算を繰り返すことによって、現実の移動体の移動のシミュレーションを行う。そして、本発明の移動体シミュレーションシステムは、移動空間分割部３２と、仮想移動体登録部３３と、移動計算部３４とを備える。
【０１６９】
移動空間分割部３２は、コンピュータ内に座標を用いて表現された移動空間を、仮想移動体が単位時間当たりに移動可能な距離の最大値（例えば、移動可能距離Ｌ）に基づいて分割することによって複数の分割空間を生成し、Ｘ軸方向、Ｙ軸方向および斜め方向にそれぞれ１つ飛ばしで配置されている分割空間の集合である分割空間群（例えば、非隣接分割空間群）を複数決定する。
【０１７０】
仮想移動体登録部３３は、分割空間群を順次選択し、選択している分割空間群において、仮想移動体が存在している分割空間を最大で所定数選択し、選択した各分割空間からそれぞれ仮想移動体を１つずつ選択し、並列計算による単位時間経過後の位置の計算対象となる仮想移動体のリスト（例えば、ベクトルリスト）に、選択した各仮想移動体を登録する。
【０１７１】
移動計算部３４は、そのリストに登録された各仮想移動体の単位時間経過後の位置を、ベクトル演算器を用いた並列計算によって計算する。
【０１７２】
また、仮想移動体登録部３３は、そのベクトル演算器のベクトルレジスタの本数をＮとしたときに、仮想移動体が存在している分割空間を最大でＮ個選択する。
【０１７３】
そのような構成によって、仮想移動体同士の衝突判定を行う場合であっても、ベクトル演算器によって高速に移動シミュレーションを実行することができる。
【０１７４】
また、仮想移動体登録部３３が、単位時間経過後の位置が計算された仮想移動体について、単位時間経過後の位置の計算前に当該仮想移動体が存在していた分割空間に当該仮想移動体が存在しなくなったとみなし、単位時間経過後に当該仮想移動体が存在する分割空間を記憶し（例えば、ステップＳ１２５の処理を実行し）、全ての仮想移動体の単位時間経過後の位置が計算された場合に、単位時間経過後に各仮想移動体が存在する分割空間を、各仮想移動体が現在存在する分割空間として記憶し直す（例えば、ステップＳ１２８の処理を実行する）構成であってもよい。
【０１７５】
また、仮想移動体登録部３３が、分割空間群から仮想移動体が存在している分割空間を最大でＮ個選択する際に、その分割空間群に含まれている各分割空間に対して、存在している仮想移動体の数が多い順に優先順序を決定し、その優先順序に従って、仮想移動体が存在している分割空間を最大でＮ個選択する構成であってもよい。
【０１７６】
そのような構成によれば、移動シミュレーションをさらに高速化することができる。
【０１７７】
また、移動空間分割部３２が、仮想移動体が単位時間当たりに移動可能な最大距離をＬとしたときに、移動空間を、Ｘ軸方向およびＹ軸方向に２Ｌ毎に分割することによって複数の分割空間を生成し、Ｘ軸方向の並びの順序が偶数番目であり、Ｙ軸方向の並びの順序が偶数番目である分割空間の集合である分割空間群（例えば、非隣接分割空間群Z1）と、Ｘ軸方向の並びの順序が偶数番目であり、Ｙ軸方向の並びの順序が奇数番目である分割空間の集合である分割空間群（例えば、非隣接分割空間群Z2）と、Ｘ軸方向の並びの順序が奇数番目であり、Ｙ軸方向の並びの順序が偶数番目である分割空間の集合である分割空間群（例えば、非隣接分割空間群Z3）と、Ｘ軸方向の並びの順序が奇数番目であり、Ｙ軸方向の並びの順序が奇数番目である分割空間の集合である分割空間群（例えば、非隣接分割空間群Z4）とを決定する構成であってもよい。
【産業上の利用可能性】
【０１７８】
本発明は、複数の移動体の移動のシミュレーションを実行する移動体シミュレーションシステムに好適に適用可能である。
【符号の説明】
【０１７９】
３０  移動体シミュレーションシステム
３１  シナリオ取得部
３２  移動空間分割部
３３  仮想移動体登録部
３４  移動計算部
３５  終了判定部
４１  分割幅決定部
４２  分割空間決定部
４３  非隣接分割空間群決定部
４４  移動体配置情報作成部
８１  非隣接分割空間群選択部
８２  分割空間選択部
８３  仮想移動体選択部
８４  ベクトルリスト登録部
８５  移動体配置情報更新部
８６  登録終了判定部
９１  ベクトルリスト参照部
９２  移動体情報取得部
９３  ベクトル処理部
１５１  選択順序決定部
【図１】
2019028877.tif 000008
【図２】
2019028877.tif 000009
【図３】
2019028877.tif 000010
【図４】
2019028877.tif 000011
【図５】
2019028877.tif 000012
【図６】
2019028877.tif 000013
【図７】
2019028877.tif 000014
【図８】
2019028877.tif 000015
【図９】
2019028877.tif 000016
【図１０】
2019028877.tif 000017
【図１１】
2019028877.tif 000018
【図１２】
2019028877.tif 000019
【図１３】
2019028877.tif 000020
【図１４】
2019028877.tif 000021
【図１５】
2019028877.tif 000022
【図１６】
2019028877.tif 000023
【図１７】
2019028877.tif 000024
【図１８】
2019028877.tif 000025
【図１９】
2019028877.tif 000026