(57)【特許請求の範囲】
【請求項１】
目標の位置の時間的な変化を示す航跡を含む複数の仮説のうち、互いに異なる仮説を更新する複数の演算器を備え、
前記複数の演算器のそれぞれは、
１つの仮説に含まれている航跡と、１つ以上の目標の観測位置とから、前記１つ以上の目標の観測位置に対する当該航跡のコスト行列に含まれる複数のコスト要素を並列処理で算出する複数のコスト算出部と、
前記複数のコスト算出部により算出された複数のコスト要素に基づいて、前記１つ以上の目標の中で、航跡におけるそれぞれの時刻に割り当てる目標の複数の組み合わせを並列処理で決定する複数の目標割当部と、
前記複数の目標割当部により決定された複数の組み合わせのそれぞれについて、１つの組み合わせに含まれているそれぞれの時刻での目標の観測位置から航跡を生成し、生成した航跡を含む仮説を更新後の仮説として出力する仮説出力部とを備えていることを特徴とする追尾処理装置。
【請求項２】
前記複数のコスト算出部は、前記コスト行列に含まれる複数のコスト要素として、前記１つ以上の目標の観測位置と、前記１つの仮説に含まれている航跡におけるそれぞれの時刻での目標の位置との距離を並列処理で算出することを特徴とする請求項１記載の追尾処理装置。
【請求項３】
前記仮説出力部は、前記１つの組み合わせに含まれているそれぞれの時刻での目標の観測位置から航跡を生成する複数の航跡生成部を備えており、
前記複数の航跡生成部は、並列処理で航跡を生成することを特徴とする請求項１記載の追尾処理装置。
【請求項４】
前記複数の目標割当部は、前記複数のコスト算出部により算出された複数のコスト要素に基づいて、前記複数の組み合わせにおけるそれぞれの総コストを算出し、
前記複数の目標割当部により算出された複数の組み合わせの総コストのうち、前記更新後の仮説の算出元の組み合わせの総コストを互いに比較し、前記総コストの比較結果に基づいて、前記更新後の仮説の中で、一部の仮説を破棄する仮説選択部を備えたことを特徴とする請求項１記載の追尾処理装置。
【請求項５】
複数の演算器が、目標の位置の時間的な変化を示す航跡を含む複数の仮説のうち、互いに異なる仮説を更新するに際して、
前記複数の演算器のそれぞれに含まれている複数のコスト算出部が、１つの仮説に含まれている航跡と、１つ以上の目標の観測位置とから、前記１つ以上の目標の観測位置に対する当該航跡のコスト行列に含まれる複数のコスト要素を並列処理で算出し、
前記複数の演算器のそれぞれに含まれている複数の目標割当部が、前記複数のコスト算出部により算出された複数のコスト要素に基づいて、前記１つ以上の目標の中で、航跡におけるそれぞれの時刻に割り当てる目標の複数の組み合わせを並列処理で決定し、
前記複数の演算器のそれぞれに含まれている仮説出力部が、前記複数の目標割当部により決定された複数の組み合わせのそれぞれについて、１つの組み合わせに含まれているそれぞれの時刻での目標の観測位置から航跡を生成し、生成した航跡を含む仮説を更新後の仮説として出力する
追尾処理方法。
【請求項６】
目標の位置の時間的な変化を示す航跡を含む複数の仮説を更新する追尾処理装置として、請求項１から請求項４のうちのいずれか１項記載の追尾処理装置を備えたことを特徴とする目標観測装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、目標の位置の時間的な変化を示す航跡を含む仮説を更新する追尾処理装置、追尾処理方法及び目標観測装置に関するものである。
【背景技術】
【０００２】
以下の特許文献１には、移動体を追尾するための観測情報を処理する追尾処理用ＣＰＵを複数備えている並列多目標追尾システムが開示されている。
複数の追尾処理用ＣＰＵは、並列に観測情報の処理を行っている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００５−２５７３８６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
特許文献１に開示されている並列多目標追尾システムでは、複数の追尾処理用ＣＰＵが、並列に観測情報の処理を行っている。しかし、１つの追尾処理用ＣＰＵにおける観測情報の処理自体は、並列に処理されていない。
したがって、移動体を追尾するための観測情報の処理に多くの時間を要してしまうことがあるという課題があった。【０００５】
この発明は上記のような課題を解決するためになされたもので、航跡を含む複数の仮説の更新処理を並列に処理する際に、それぞれの仮説の更新処理自体を並列に処理することができる追尾処理装置、追尾処理方法及び目標観測装置を得ることを目的とする。
【課題を解決するための手段】
【０００６】
この発明に係る追尾処理装置は、目標の位置の時間的な変化を示す航跡を含む複数の仮説のうち、互いに異なる仮説を更新する複数の演算器を備え、複数の演算器のそれぞれが、１つの仮説に含まれている航跡と、１つ以上の目標の観測位置とから、１つ以上の目標の観測位置に対する当該航跡のコスト行列に含まれる複数のコスト要素を並列処理で算出する複数のコスト算出部と、複数のコスト算出部により算出された複数のコスト要素に基づいて、１つ以上の目標の中で、航跡におけるそれぞれの時刻に割り当てる目標の複数の組み合わせを並列処理で決定する複数の目標割当部と、複数の目標割当部により決定された複数の組み合わせのそれぞれについて、１つの組み合わせに含まれているそれぞれの時刻での目標の観測位置から航跡を生成し、生成した航跡を含む仮説を更新後の仮説として出力する仮説出力部とを備えているものである。
【発明の効果】
【０００７】
この発明によれば、航跡を含む複数の仮説の更新処理を並列に処理する際に、それぞれの仮説の更新処理自体を並列に処理することができる。
【図面の簡単な説明】
【０００８】
【図１】実施の形態１に係る追尾処理装置１を備える目標観測装置示す構成図である。
【図２】実施の形態１に係る追尾処理装置１を示す構成図である。
【図３】実施の形態１に係る追尾処理装置１の演算器１２−ｍ−ｎを示す構成図である。
【図４】演算器１２−ｍ−ｎのハードウェアを示すハードウェア構成図である。
【図５】演算器１２−ｍ−ｎに含まれている（Ｐ＋Ｑ）個の仮説観測位置読込部２１を示す構成図である。
【図６】演算器１２−ｍ−ｎに含まれている（Ｐ×Ｑ）個のコスト算出部２２を示す構成図である。
【図７】演算器１２−ｍ−ｎに含まれている（Ｐ×Ｑ）個の目標割当部２３を示す構成図である。
【図８】演算器１２−ｍ−ｎに含まれている（Ｐ×Ｋ）個の航跡生成部２５を示す構成図である。
【図９】演算器１２−ｍ−ｎに含まれている（Ｐ×Ｋ）個の更新仮説出力部２６を示す構成図である。
【図１０】演算器１２−ｍ−ｎがソフトウェア又はファームウェア等によって実現される場合のコンピュータのハードウェア構成図である。
【図１１】演算器１２−ｍ−ｎの処理手順である追尾処理方法を示すフローチャートである。
【図１２】主記憶装置１１の記憶内容の一例を示す説明図である。
【図１３】演算器１２−ｍ−ｎによる仮説（ｈ）の更新処理を示す説明図である。
【図１４】（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑによる組み合わせ（１）〜（Ｋ）の決定処理を示す説明図である。
【図１５】実施の形態２に係る追尾処理装置１を示す構成図である。
【図１６】目標割当部２３による最小のコスト要素ｃｐ，ｑの探索処理を示す説明図である。
【図１７】目標割当部２３による解候補の総コストｃｔｏｔａｌ（ｋ）の算出処理を示す説明図である。
【図１８】目標割当部２３による解候補の選択処理を示す説明図である。
【発明を実施するための形態】
【０００９】
以下、この発明をより詳細に説明するために、この発明を実施するための形態について、添付の図面に従って説明する。
【００１０】
実施の形態１．
図１は、実施の形態１に係る追尾処理装置１を備える目標観測装置を示す構成図である。
目標観測装置は、例えば、目標を追尾するに際して、目標の位置の時間的な変化を示す航跡Ｗｐを含む複数の仮説（ｈ）を更新する追尾処理装置１を備えている。ｐ＝１，・・・，Ｐであり、Ｐは、２以上の整数である。ｈ＝１，・・・，Ｈであり、Ｈは、２以上の整数である。
【００１１】
図２は、実施の形態１に係る追尾処理装置１を示す構成図である。
図２において、追尾処理装置１は、主記憶装置１１及びＭ×Ｎ個の演算器１２−ｍ−ｎを備えている。ｍ＝１，・・・，Ｍであり、Ｍは、１以上の整数である。ｎ＝１，・・・，Ｎであり、Ｎは、１以上の整数である。
主記憶装置１１は、目標の位置の時間的な変化を示す航跡Ｗｐを含むＨ個の仮説（ｈ）を記憶している。航跡Ｗｐは、時刻ｔにおける目標の位置（ｒｘ，ｒｙ）のほか、時刻ｔにおける目標の速度（ｖｘ，ｖｙ）を含んでいる。以下、時刻ｔを航跡番号ｐで表し、時刻ｔにおける目標の位置（ｒｘ，ｒｙ）を、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）として説明し、時刻ｔにおける目標の速度（ｖｘ，ｖｙ）を、航跡番号ｐにおける目標の速度（ｖｘ，ｖｙ）として説明する。
また、主記憶装置１１は、Ｑ個の目標の観測位置（ｏｐｘ，ｏｐｙ）を記憶している。Ｑは、１つ以上の整数である。
Ｑ個の目標のそれぞれは、目標番号ｑ（ｑ＝１，・・・，Ｑ）の目標であり、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）は、例えば、図示せぬ目標検出装置により検出された目標の位置を示す観測データである。
【００１２】
演算器１２−ｍ−ｎは、主記憶装置１１により記憶されているＨ個の仮説（１）〜（Ｈ）の中から、１つの仮説（ｈ）を取得し、主記憶装置１１により記憶されているＱ個の目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する。Ｍ×Ｎ個の演算器１２−ｍ−ｎのそれぞれは、互いに異なる仮説（ｈ）を取得する。
演算器１２−ｍ−ｎは、Ｑ個の目標の観測位置（ｏｐｘ，ｏｐｙ）に基づいて、取得した１つの仮説（ｈ）を更新し、更新後の仮説を主記憶装置１１に記憶させる。
【００１３】
図３は、実施の形態１に係る追尾処理装置１の演算器１２−ｍ−ｎを示す構成図であり、図４は、演算器１２−ｍ−ｎのハードウェアを示すハードウェア構成図である。
図３において、演算器１２−ｍ−ｎは、制御部２０、（Ｐ＋Ｑ）個の仮説観測位置読込部２１、（Ｐ×Ｑ）個のコスト算出部２２、（Ｐ×Ｑ）個の目標割当部２３、（Ｐ×Ｋ）個の仮説出力部２４及びデータ記憶部２７を備えている。Ｋは、後述する目標の組み合わせの数であり、２以上の整数である。
【００１４】
図５は、演算器１２−ｍ−ｎに含まれている（Ｐ＋Ｑ）個の仮説観測位置読込部２１を示す構成図である。
図６は、演算器１２−ｍ−ｎに含まれている（Ｐ×Ｑ）個のコスト算出部２２を示す構成図である。
図７は、演算器１２−ｍ−ｎに含まれている（Ｐ×Ｑ）個の目標割当部２３を示す構成図である。
図８は、演算器１２−ｍ−ｎに含まれている（Ｐ×Ｋ）個の航跡生成部２５を示す構成図である。
図９は、演算器１２−ｍ−ｎに含まれている（Ｐ×Ｋ）個の更新仮説出力部２６を示す構成図である。
【００１５】
制御部２０は、例えば、図４に示す制御回路３０によって実現される。
制御部２０は、仮説の更新時に、仮説観測位置読込部２１、コスト算出部２２、目標割当部２３及び仮説出力部２４におけるそれぞれの動作を制御する。
【００１６】
（Ｐ＋Ｑ）個の仮説観測位置読込部２１は、例えば、図４に示す仮説観測位置読込回路３１によって実現される。
（Ｐ＋Ｑ）個の仮説観測位置読込部２１のうち、Ｐ個の仮説観測位置読込部２１−ｐ（ｐ＝１，・・・，Ｐ）は、主記憶装置１１から、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを取得する。
Ｐ個の仮説観測位置読込部２１−ｐは、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを、（Ｐ×Ｑ）個のコスト算出部２２の中のコスト算出部２２−ｐ−１〜２２−ｐ−Ｑのそれぞれに出力する。
また、仮説観測位置読込部２１−ｐは、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを航跡生成部２５−ｐ−ｋに出力する。
（Ｐ＋Ｑ）個の仮説観測位置読込部２１のうち、Ｑ個の仮説観測位置読込部２１−（Ｐ＋ｑ）は、主記憶装置１１から、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する。
Ｑ個の仮説観測位置読込部２１−（Ｐ＋ｑ）は、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を、（Ｐ×Ｑ）個のコスト算出部２２の中のコスト算出部２２−１−ｑ〜２２−Ｐ−ｑのそれぞれに出力する。
また、仮説観測位置読込部２１−（Ｐ＋ｑ）は、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を航跡生成部２５−ｐ−ｋに出力する。
【００１７】
（Ｐ×Ｑ）個のコスト算出部２２は、例えば、図４に示すコスト算出回路３２によって実現される。
以下、（Ｐ×Ｑ）個のコスト算出部２２のそれぞれを、コスト算出部２２−ｐ−ｑのように表記する。
コスト算出部２２−ｐ−ｑは、仮説観測位置読込部２１−ｐから出力された航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを取得する。
コスト算出部２２−ｐ−ｑは、仮説観測位置読込部２１−（Ｐ＋ｑ）から出力された目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する。
コスト算出部２２−ｐ−ｑは、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれと、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）とから、目標の観測位置（ｏｐｘ，ｏｐｙ）に対する航跡Ｗｐのコスト行列に含まれるコスト要素ｃｐ，ｑを算出する。
コスト要素ｃｐ，ｑは、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）と、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）との距離である。
（Ｐ×Ｑ）個のコスト算出部２２−ｐ−ｑは、コスト要素ｃｐ，ｑを並列に算出する。
【００１８】
（Ｐ×Ｑ）個の目標割当部２３は、例えば、図４に示す目標割当回路３３によって実現される。
以下、（Ｐ×Ｑ）個の目標割当部２３のそれぞれを、目標割当部２３−ｐ−ｑのように表記する。
（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑは、（Ｐ×Ｑ）個のコスト算出部２２−ｐ−ｑにより算出された（Ｐ×Ｑ）個のコスト要素ｃｐ，ｑに基づいて、Ｑ個の目標の中で、それぞれの航跡番号ｐ（ｐ＝１，・・・，Ｐ）に割り当てる目標のＫ個の組み合わせ（１）〜（Ｋ）を並列処理で決定する。
以下、組み合わせ（ｋ）（ｋ＝１，・・・，Ｋ）を、経路（ｋ）と称する。
【００１９】
（Ｐ×Ｋ）個の仮説出力部２４は、航跡生成部２５及び更新仮説出力部２６を備えている。
（Ｐ×Ｋ）個の航跡生成部２５は、例えば、図４に示す航跡生成回路３４によって実現される。
以下、（Ｐ×Ｋ）個の航跡生成部２５のそれぞれを、航跡生成部２５−ｐ−ｋのように表記する。
（Ｐ×Ｋ）個の航跡生成部２５−ｐ−ｋは、経路（ｋ）に含まれているそれぞれの航跡番号ｐでの目標の観測位置（ｏｐｘ，ｏｐｙ）から航跡Ｗｐ，ｋを並列処理で生成する。
【００２０】
（Ｐ×Ｋ）個の更新仮説出力部２６は、例えば、図４に示す更新仮説出力回路３５によって実現される。
以下、（Ｐ×Ｋ）個の更新仮説出力部２６のそれぞれを、更新仮説出力部２６−ｐ−ｋのように表記する。
（Ｐ×Ｋ）個の更新仮説出力部２６−ｐ−ｋは、航跡生成部２５−ｐ−ｋにより生成された航跡Ｗｐ，ｋを含む仮説（ｈｐ，ｋ）を更新後の仮説として、主記憶装置１１に記憶させる。
データ記憶部２７は、例えば、図４に示すデータ記憶回路３６によって実現される。
データ記憶部２７は、演算器１２−ｍ−ｎにおける途中の計算結果等を記憶する。
【００２１】
図３では、演算器１２−ｍ−ｎの構成要素である制御部２０、仮説観測位置読込部２１、コスト算出部２２、目標割当部２３、航跡生成部２５、更新仮説出力部２６及びデータ記憶部２７のそれぞれが、図４に示すような専用のハードウェアによって実現されるものを想定している。即ち、演算器１２−ｍ−ｎが、制御回路３０、仮説観測位置読込回路３１、コスト算出回路３２、目標割当回路３３、航跡生成回路３４、更新仮説出力回路３５及びデータ記憶回路３６によって実現されるものを想定している。
【００２２】
ここで、データ記憶回路３６は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＥＰＲＯＭ（Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＥＥＰＲＯＭ（Ｅｌｅｃｔｒｉｃａｌｌｙ  Ｅｒａｓａｂｌｅ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒy）等の不揮発性又は揮発性の半導体メモリ、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、あるいは、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）が該当する。
制御回路３０、仮説観測位置読込回路３１、コスト算出回路３２、目標割当回路３３、航跡生成回路３４及び更新仮説出力回路３５のそれぞれは、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）、又は、これらを組み合わせたものが該当する。
【００２３】
演算器１２−ｍ−ｎの構成要素は、専用のハードウェアによって実現されるものに限るものではなく、演算器１２−ｍ−ｎがソフトウェア、ファームウェア、又は、ソフトウェアとファームウェアとの組み合わせによって実現されるものであってもよい。
ソフトウェア又はファームウェアは、プログラムとして、コンピュータのメモリに格納される。コンピュータは、プログラムを実行するハードウェアを意味し、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサ、あるいは、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）が該当する。
図１０は、演算器１２−ｍ−ｎがソフトウェア又はファームウェア等によって実現される場合のコンピュータのハードウェア構成図である。
【００２４】
演算器１２−ｍ−ｎがソフトウェア又はファームウェア等によって実現される場合、データ記憶部２７がコンピュータのメモリ４１上に構成される。
制御部２０、仮説観測位置読込部２１、コスト算出部２２、目標割当部２３、航跡生成部２５及び更新仮説出力部２６の処理手順をコンピュータに実行させるためのプログラムがメモリ４１に格納される。そして、コンピュータのプロセッサ４２がメモリ４１に格納されているプログラムを実行する。
図１１は、演算器１２−ｍ−ｎの処理手順である追尾処理方法を示すフローチャートである。
【００２５】
次に、図２に示す追尾処理装置１の動作について説明する。
主記憶装置１１は、図１２に示すように、Ｈ個の仮説（ｈ）を記憶している。
仮説（ｈ）に含まれている航跡Ｗｐは、目標の位置及び速度におけるそれぞれの時間的な変化を示すものであり、航跡Ｗｐは、それぞれの時刻ｔに対応する航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを含んでいる。例えば、航跡番号ｐは、時刻ｔに対応し、航跡番号ｐ−１は、時刻ｔ−１に対応している。
また、主記憶装置１１は、図１２に示すように、Ｑ個の目標の観測位置（ｏｐｘ，ｏｐｙ）を記憶している。
図１２は、主記憶装置１１の記憶内容の一例を示す説明図である。
【００２６】
演算器１２−ｍ−ｎは、主記憶装置１１により記憶されているＨ個の仮説（１）〜（Ｈ）の中から、１つの仮説（ｈ）を取得する。Ｍ×Ｎ個の演算器１２−ｍ−ｎのそれぞれは、互いに異なる仮説（ｈ）を取得する。
また、演算器１２−ｍ−ｎは、主記憶装置１１により記憶されているＱ個の目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する。
演算器１２−ｍ−ｎは、Ｑ個の目標の観測位置（ｏｐｘ，ｏｐｙ）に基づいて、取得した１つの仮説（ｈ）を更新し、更新後の仮説（ｈｐ，ｋ）を主記憶装置１１に記憶させる。
Ｈ個の仮説（１）〜（Ｈ）の更新は、複数の演算器１２−ｍ−ｎによって、並列に処理される。
以下、演算器１２−ｍ−ｎによる仮説（ｈ）の更新処理を具体的に説明する。
図１３は、演算器１２−ｍ−ｎによる仮説（ｈ）の更新処理を示す説明図である。
【００２７】
まず、制御部２０は、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）の取得と、目標の速度（ｖｘ，ｖｙ）の取得とを指示する制御信号を、Ｐ個の仮説観測位置読込部２１−ｐのそれぞれに出力する。
また、制御部２０は、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）の取得を指示する制御信号を、Ｑ個の仮説観測位置読込部２１−（Ｐ＋ｑ）のそれぞれに出力する。
【００２８】
Ｐ個の仮説観測位置読込部２１−ｐは、制御部２０から制御信号を受けると、主記憶装置１１から、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを取得する（図１１のステップＳＴ１）。
仮説観測位置読込部２１−ｐは、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを、コスト算出部２２−ｐ−１〜２２−ｐ−Ｑのそれぞれに出力する。
また、仮説観測位置読込部２１−ｐは、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを航跡生成部２５−ｐ−ｋに出力する。
Ｑ個の仮説観測位置読込部２１−（Ｐ＋ｑ）は、制御部２０から制御信号を受けると、主記憶装置１１から、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する（図１１のステップＳＴ２）。
仮説観測位置読込部２１−（Ｐ＋ｑ）は、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を、コスト算出部２２−１−ｑ〜２２−Ｐ−ｑのそれぞれに出力する。
また、仮説観測位置読込部２１−（Ｐ＋ｑ）は、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を航跡生成部２５−ｐ−ｋに出力する。
【００２９】
制御部２０は、コスト要素ｃｐ，ｑの算出指令を（Ｐ×Ｑ）個のコスト算出部２２−ｐ−ｑのそれぞれに出力する。
コスト算出部２２−ｐ−ｑは、制御部２０からコスト要素ｃｐ，ｑの算出指令を受けると、仮説観測位置読込部２１−ｐから出力された航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを取得する。
コスト算出部２２−ｐ−ｑは、仮説観測位置読込部２１−（Ｐ＋ｑ）から出力された目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する。
コスト算出部２２−ｐ−ｑは、目標の位置（ｒｘ，ｒｙ）、目標の速度（ｖｘ，ｖｙ）及び目標の観測位置（ｏｐｘ，ｏｐｙ）から、以下の式（１）に示すように、目標の観測位置（ｏｐｘ，ｏｐｙ）に対する航跡Ｗｐのコスト行列に含まれるコスト要素ｃｐ，ｑを算出する（図１１のステップＳＴ３）。
0006942287.tif 000002
式（１）において、δｔは、時刻ｔと、時刻ｔ−１との間の時間差である。
（Ｐ×Ｑ）個のコスト算出部２２−ｐ−ｑが、コスト要素ｃｐ，ｑを並列に算出することで、図１３に示すようなコスト行列が得られる。
コスト算出部２２−ｐ−ｑは、算出したコスト要素ｃｐ，ｑを（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑに出力する。
【００３０】
制御部２０は、経路（ｋ）の決定指令を（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑのそれぞれに出力する。
（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑは、制御部２０から経路（ｋ）の決定指令を受けると、（Ｐ×Ｑ）個のコスト算出部２２−ｐ−ｑにより算出された（Ｐ×Ｑ）個のコスト要素ｃｐ，ｑに基づいて、経路（１）〜（Ｋ）を並列処理で決定する（図１１のステップＳＴ４）。
（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑは、例えば、Ｋ最短経路ソルバというアルゴリズムを実行することで、Ｋ個の経路（１）〜（Ｋ）を並列処理で決定する。
以下、（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑによる経路（１）〜（Ｋ）の決定処理を具体的に説明する。
【００３１】
図１４は、（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑによる経路（１）〜（Ｋ）の決定処理を示す説明図である。
図１４では、説明の便宜上、航跡Ｗｐに含まれている目標の位置の航跡番号ｐがｐ＝１，２，３，４であるものとする。また、図１４では、Ｑ＝５個の目標の観測位置（ｏｐｘ，ｏｐｙ）が得られており、目標番号ｑがｑ＝１，２，３，４，５であるものとする。
図１４では、航跡Ｗｐのコスト行列に含まれるコスト要素ｃｐ，ｑのうち、例えば、コスト要素ｃ１，１が“１”の値を有し、コスト要素ｃ１，３が“１２”の値を有し、コスト要素ｃ２，４が“１６”の値を有している。
図１４では、（Ｐ×Ｑ）個の目標割当部２３−ｐ−ｑが、Ｓｔｅｐ１．〜Ｓｔｅｐ６．を実行することで、Ｋ＝８個の経路（１）〜（８）を決定している。
【００３２】
［Ｓｔｅｐ１．］
目標割当部２３−１−ｑ（ｑ＝１，２，３，４，５）は、コスト算出部２２−１−１〜２２−１−５から出力されたコスト要素ｃ１，１〜ｃ１，５を取得し、コスト要素ｃ１，１〜ｃ１，５を比較することで、最小のコスト要素ｃ１，ｑを探索する。
図１４の例では、コスト要素ｃ１，１〜ｃ１，５の中で、“１”の値を有するコスト要素ｃ１，１が最小のコスト要素である。
目標割当部２３−１−ｑ（ｑ＝１，２，３，４，５）は、コスト要素ｃ１，ｑが有する値から、最小のコスト要素ｃ１，１が有する“１”の値を減算することで、コスト要素ｃ１，ｑが有する値を更新する。
【００３３】
目標割当部２３−２−ｑ（ｑ＝１，２，３，４，５）は、コスト算出部２２−２−１〜２２−２−５から出力されたコスト要素ｃ２，１〜ｃ２，５を取得し、コスト要素ｃ２，１〜ｃ２，５を比較することで、最小のコスト要素ｃ２，ｑを探索する。
図１４の例では、コスト要素ｃ２，１〜ｃ２，５の中で、“２”の値を有するコスト要素ｃ２，２が最小のコスト要素である。
目標割当部２３−２−ｑ（ｑ＝１，２，３，４，５）は、コスト要素ｃ２，ｑが有する値から、最小のコスト要素ｃ２，２が有する“２”の値を減算することで、コスト要素ｃ２，ｑが有する値を更新する。
目標割当部２３−３−ｑ及び目標割当部２３−４−ｑについても、目標割当部２３−１−ｑと同様に、コスト要素ｃ３，ｑが有する値及びコスト要素ｃ４，ｑが有する値のそれぞれを更新する。
【００３４】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、１つの解候補をデータ記憶部２７に記憶させる。
解候補は、航跡番号ｐにおけるコスト値と、航跡番号ｐにおける最小のコスト要素に対応する目標番号ｑとの組で表される。
航跡番号ｐ＝１では、コスト要素ｃ１，１が有する“０”の値から、最小のコスト要素ｃ１，１が有する“１”の値を減算した値である“０”がコスト値である。
航跡番号ｐ＝２では、コスト要素ｃ２，２が有する“０”の値から、最小のコスト要素ｃ２，２が有する“２”の値を減算した値である“０”がコスト値である。
航跡番号ｐ＝３では、コスト要素ｃ３，３が有する“０”の値から、最小のコスト要素ｃ３，３が有する“１”の値を減算した値である“０”がコスト値である。
航跡番号ｐ＝４では、コスト要素ｃ４，４が有する“０”の値から、最小のコスト要素ｃ４，４が有する“４”の値を減算した値である“０”がコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，２に対応する目標番号ｑがｑ＝２ある。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，３に対応する目標番号ｑがｑ＝３である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
当該解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“０”の値である。
なお、図１４では、航跡番号ｐのコスト値と、航跡番号ｐの最小のコスト要素に対応する目標番号ｑとの組で表される解候補が、以下のように表記されている。
例えば、航跡番号ｐのコスト値＝“０”と、航跡番号ｐの最小のコスト要素に対応する目標番号ｑ＝１とについては、“０１”のように表記されている。
例えば、航跡番号ｐのコスト値＝“０”と、航跡番号ｐの最小のコスト要素に対応する目標番号ｑ＝３とについては、“０３”のように表記されている。
【００３５】
［Ｓｔｅｐ２．］
目標割当部２３−１−ｑ（ｑ＝２，３，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ１，２〜ｃ１，５を比較することで、最小のコスト要素ｃ１，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ１，２〜ｃ１，５の中で、“６”の値を有するコスト要素ｃ１，５が最小のコスト要素である。
目標割当部２３−２−ｑ（ｑ＝１，３，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ２，１，ｃ２，３，ｃ２，４，ｃ２，５を比較することで、最小のコスト要素ｃ２，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ２，１，ｃ２，３，ｃ２，４，ｃ２，５の中で、“３”の値を有するコスト要素ｃ２，１が最小のコスト要素である。
【００３６】
目標割当部２３−３−ｑ（ｑ＝１，２，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ３，１，ｃ３，２，ｃ３，４，ｃ３，５を比較することで、最小のコスト要素ｃ３，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ３，１，ｃ３，２，ｃ３，４，ｃ３，５の中で、“４”の値を有するコスト要素ｃ３，５が最小のコスト要素である。
目標割当部２３−４−ｑ（ｑ＝１，２，３，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ４，１，ｃ４，２，ｃ４，３，ｃ４，５を比較することで、最小のコスト要素ｃ４，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ４，１，ｃ４，２，ｃ４，３，ｃ４，５の中で、“１０”の値を有するコスト要素ｃ４，１が最小のコスト要素である。
【００３７】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、目標割当部２３−１−ｑ〜２３−４−ｑにより探索された最小のコスト要素ｃ１，ｑ，ｃ２，ｑ，ｃ３，ｑ，ｃ４，ｑの中で、最小のコスト要素を探索する。
図１４の例では、目標割当部２３−１−ｑ〜２３−４−ｑにより探索された最小のコスト要素ｃ１，ｑ，ｃ２，ｑ，ｃ３，ｑ，ｃ４，ｑの中で、“３”の値を有するコスト要素ｃ２，１が最小のコスト要素である。
【００３８】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、１つの解候補をデータ記憶部２７に記憶させる。
航跡番号ｐ＝１では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ２．］で探索された最小のコスト要素ｃ２，１が有する“３”の値が、コスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，１に対応する目標番号ｑがｑ＝１ある。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，３に対応する目標番号ｑがｑ＝３である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
当該解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“３”の値である。
【００３９】
［Ｓｔｅｐ３．］
目標割当部２３−１−ｑ（ｑ＝２，３，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ１，２〜ｃ１，５を比較することで、最小のコスト要素ｃ１，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ１，２〜ｃ１，５の中で、“６”の値を有するコスト要素ｃ１，５が最小のコスト要素である。
目標割当部２３−２−ｑ（ｑ＝３，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ２，３，ｃ２，４，ｃ２，５を比較することで、最小のコスト要素ｃ２，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ２，３，ｃ２，４，ｃ２，５の中で、“１０”の値を有するコスト要素ｃ２，５が最小のコスト要素である。
【００４０】
目標割当部２３−３−ｑ（ｑ＝１，２，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ３，１，ｃ３，２，ｃ３，４，ｃ３，５を比較することで、最小のコスト要素ｃ３，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ３，１，ｃ３，２，ｃ３，４，ｃ３，５の中で、“４”の値を有するコスト要素ｃ３，５が最小のコスト要素である。
目標割当部２３−４−ｑ（ｑ＝１，２，３，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ４，１，ｃ４，２，ｃ４，３，ｃ４，５を比較することで、最小のコスト要素ｃ４，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ４，１，ｃ４，２，ｃ４，３，ｃ４，５の中で、“１０”の値を有するコスト要素ｃ４，１が最小のコスト要素である。
【００４１】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、目標割当部２３−１−ｑ〜２３−４−ｑにより探索された最小のコスト要素ｃ１，ｑ，ｃ２，ｑ，ｃ３，ｑ，ｃ４，ｑの中で、最小のコスト要素を探索する。
図１４の例では、目標割当部２３−１−ｑ〜２３−４−ｑにより探索された最小のコスト要素ｃ１，ｑ，ｃ２，ｑ，ｃ３，ｑ，ｃ４，ｑの中で、“４”の値を有するコスト要素ｃ３，５が最小のコスト要素である。
【００４２】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、２つの解候補をデータ記憶部２７に記憶させる。
［１つ目の解候補］
航跡番号ｐ＝１では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ３．］で探索された最小のコスト要素ｃ３，５が有する“４”の値が、コスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，１に対応する目標番号ｑがｑ＝２である。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
１つ目の解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“４”の値である。
［２つ目の解候補］
航跡番号ｐ＝１では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ２．］で算出された“３”のコスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ３．］で探索された最小のコスト要素ｃ３，５が有する“４”の値が、コスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
２つ目の解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“７”の値である。
【００４３】
［Ｓｔｅｐ４．］
目標割当部２３−１−ｑ（ｑ＝２，３，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ１，２〜ｃ１，５を比較することで、最小のコスト要素ｃ１，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ１，２〜ｃ１，５の中で、“６”の値を有するコスト要素ｃ１，５が最小のコスト要素である。
目標割当部２３−２−ｑ（ｑ＝３，４，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ２，３，ｃ２，４，ｃ２，５を比較することで、最小のコスト要素ｃ２，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ２，３，ｃ２，４，ｃ２，５の中で、“１０”の値を有するコスト要素ｃ２，５が最小のコスト要素である。
【００４４】
目標割当部２３−３−ｑ（ｑ＝１，２，４）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ３，１，ｃ３，２，ｃ３，４を比較することで、最小のコスト要素ｃ３，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ３，１，ｃ３，２，ｃ３，４の中で、“９”の値を有するコスト要素ｃ３，２が最小のコスト要素である。
目標割当部２３−４−ｑ（ｑ＝１，２，３，５）は、［Ｓｔｅｐ１．］での更新後のコスト要素ｃ４，１，ｃ４，２，ｃ４，３，ｃ４，５を比較することで、最小のコスト要素ｃ４，ｑを探索する。
図１４の例では、更新後のコスト要素ｃ４，１，ｃ４，２，ｃ４，３，ｃ４，５の中で、“１０”の値を有するコスト要素ｃ４，１が最小のコスト要素である。
【００４５】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、目標割当部２３−１−ｑ〜２３−４−ｑにより探索された最小のコスト要素ｃ１，ｑ，ｃ２，ｑ，ｃ３，ｑ，ｃ４，ｑの中で、最小のコスト要素を探索する。
図１４の例では、目標割当部２３−１−ｑ〜２３−４−ｑにより探索された最小のコスト要素ｃ１，ｑ，ｃ２，ｑ，ｃ３，ｑ，ｃ４，ｑの中で、“６”の値を有するコスト要素ｃ１，５が最小のコスト要素である。
【００４６】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、４つの解候補をデータ記憶部２７に記憶させる。
［１つ目の解候補］
航跡番号ｐ＝１では、［Ｓｔｅｐ４．］で探索された最小のコスト要素ｃ１，５が有する“６”の値が、コスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，２に対応する目標番号ｑがｑ＝２である。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，３に対応する目標番号ｑがｑ＝３である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
１つ目の解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“６”の値である。
［２つ目の解候補］
航跡番号ｐ＝１では、［Ｓｔｅｐ４．］で探索された最小のコスト要素ｃ１，５が有する“６”の値が、コスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ２．］で算出された“３”のコスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，３に対応する目標番号ｑがｑ＝３である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
２つ目の解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“９”の値である。
【００４７】
［３つ目の解候補］
航跡番号ｐ＝１では、［Ｓｔｅｐ４．］で探索された最小のコスト要素ｃ１，５が有する“６”の値が、コスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ３．］で算出された“４”のコスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，２に対応する目標番号ｑがｑ＝２である。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
３つ目の解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“１０”の値である。
［４つ目の解候補］
航跡番号ｐ＝１では、［Ｓｔｅｐ４．］で探索された最小のコスト要素ｃ１，５が有する“６”の値が、コスト値である。
航跡番号ｐ＝２では、［Ｓｔｅｐ２．］で算出された“３”のコスト値である。
航跡番号ｐ＝３では、［Ｓｔｅｐ３．］で算出された“４”のコスト値である。
航跡番号ｐ＝４では、［Ｓｔｅｐ１．］で算出された“０”のコスト値である。
航跡番号ｐ＝１では、最小のコスト要素ｃ１，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝２では、最小のコスト要素ｃ２，１に対応する目標番号ｑがｑ＝１である。
航跡番号ｐ＝３では、最小のコスト要素ｃ３，５に対応する目標番号ｑがｑ＝５である。
航跡番号ｐ＝４では、最小のコスト要素ｃ４，４に対応する目標番号ｑがｑ＝４である。
４つ目の解候補の総コストは、航跡番号ｐ＝１におけるコスト値と、航跡番号ｐ＝２におけるコスト値と、航跡番号ｐ＝３におけるコスト値と、航跡番号ｐ＝４におけるコスト値との総和である“１３”の値である。
【００４８】
［Ｓｔｅｐ５．］〜［Ｓｔｅｐ６．］
［Ｓｔｅｐ５．］〜［Ｓｔｅｐ６．］の処理は、［Ｓｔｅｐ４．］と同様の方法で行われるため、詳細な説明を省略する。
図１４では、［Ｓｔｅｐ６．］の処理が完了することで、１８個の解候補がデータ記憶部２７に記憶される。
【００４９】
目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３は、データ記憶部２７に記憶させている１８個の解候補の中から、総コストが小さい上位Ｋ個の解候補を選択する。
いずれか１つの目標割当部２３は、選択したＫ個の解候補のそれぞれを経路（１）〜（Ｋ）とし、経路（ｋ）（ｋ＝１，・・・，Ｋ）を航跡生成部２５−１−ｋ〜２５−Ｐ−ｋのそれぞれに出力する。
【００５０】
制御部２０は、仮説の生成指令を（Ｐ×Ｋ）個の航跡生成部２５−ｐ−ｋのそれぞれに出力する。
航跡生成部２５−ｐ−ｋは、制御部２０から仮説の生成指令を受けると、仮説観測位置読込部２１−ｐから出力された航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）及び目標の速度（ｖｘ，ｖｙ）のそれぞれを取得する。
また、航跡生成部２５−ｐ−ｋは、仮説観測位置読込部２１−ｐから出力された目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を取得する。
また、航跡生成部２５−ｐ−ｋは、いずれか１つの目標割当部２３から出力された経路（ｋ）（ｋ＝１，・・・，Ｋ）を取得する。
航跡生成部２５−ｐ−ｋは、経路（ｋ）に含まれている航跡番号ｐに対応する目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）を、以下の式（２）に示すように、新たな航跡Ｗｐ，ｋに含まれる航跡番号ｐにおける目標の位置（ｒｘ’，ｒｙ’）に決定する（図１１のステップＳＴ５）。
ｒｘ’＝ｏｐｘ
ｒｙ’＝ｏｐｙ                              （２）
【００５１】
航跡生成部２５−ｐ−ｋは、航跡番号ｐにおける目標の位置（ｒｘ，ｒｙ）と、航跡番号ｐにおける目標の速度（ｖｘ，ｖｙ）と、目標番号ｑにおける目標の観測位置（ｏｐｘ，ｏｐｙ）とから、以下の式（３）に示すように、新たな航跡Ｗｐ，ｋに含まれる航跡番号ｐにおける目標の速度（ｖｘ’，ｖｙ’）を算出する（図１１のステップＳＴ６）。
0006942287.tif 000003
航跡生成部２５−ｐ−ｋは、新たな航跡Ｗｐ，ｋを更新仮説出力部２６−ｐ−ｋに出力する。
【００５２】
制御部２０は、更新仮説の出力指令を（Ｐ×Ｋ）個の更新仮説出力部２６−ｐ−ｋのそれぞれに出力する。
更新仮説出力部２６−ｐ−ｋは、制御部２０から更新仮説の出力指令を受けると、航跡生成部２５−ｐ−ｋから出力された新たな航跡Ｗｐ，ｋを含む仮説（ｈｐ，ｋ）を更新後の仮説として、主記憶装置１１に記憶させる（図１１のステップＳＴ７）。
【００５３】
以上の実施の形態１では、追尾処理装置１が、目標の位置の時間的な変化を示す航跡を含む複数の仮説のうち、互いに異なる仮説を更新する複数の演算器１２−ｍ−ｎを備えている。複数の演算器１２−ｍ−ｎのそれぞれは、１つの仮説に含まれている航跡と、１つ以上の目標の観測位置とから、１つ以上の目標の観測位置に対する当該航跡のコスト行列に含まれる複数のコスト要素を並列処理で算出する複数のコスト算出部２２と、複数のコスト算出部２２により算出された複数のコスト要素に基づいて、１つ以上の目標の中で、航跡におけるそれぞれの時刻に割り当てる目標の複数の組み合わせを並列処理で決定する複数の目標割当部２３と、複数の目標割当部２３により決定された複数の組み合わせのそれぞれについて、１つの組み合わせに含まれているそれぞれの時刻での目標の観測位置から航跡を生成し、生成した航跡を含む仮説を更新後の仮説として出力する仮説出力部２４とを備えている。したがって、追尾処理装置１は、航跡を含む複数の仮説の更新処理を並列に処理する際に、それぞれの仮説の更新処理自体を並列に処理することができる。
【００５４】
実施の形態２．
実施の形態２では、複数の演算器１２−ｍ−ｎの仮説出力部２４から出力された複数の更新後の仮説の中で、一部の仮説を破棄する仮説選択部５０を備えた追尾処理装置１について説明する。
【００５５】
図１５は、実施の形態２に係る追尾処理装置１を示す構成図である。図１５において、図２と同一符号は同一又は相当部分を示すので説明を省略する。
仮説選択部５０は、例えば、演算器によって実現される。
仮説選択部５０は、主記憶装置１１から、複数の演算器１２−ｍ−ｎによるそれぞれの更新後の仮説（ｈｐ，ｋ）の算出元の経路（ｋ）における解候補の総コストを取得する。
仮説選択部５０は、複数の解候補の総コストを互いに比較し、複数の総コストの比較結果に基づいて、複数の更新後の仮説（ｈｐ，ｋ）の中で、一部の仮説（ｈｐ，ｋ）を破棄する。
【００５６】
図１５に示す追尾処理装置１では、仮説選択部５０が、例えば、演算器によって実現されるものとしている。しかし、これは一例に過ぎず、複数の演算器１２−ｍ−ｎのうちのいずれかの演算器１２が、仮説選択部５０を備えていてもよい。
【００５７】
次に、図１５に示す追尾処理装置１の動作について説明する。
複数の演算器１２−ｍ−ｎに含まれている更新仮説出力部２６−ｐ−ｋは、更新後の仮説（ｈｐ，ｋ）の算出元の経路（ｋ）における解候補の総コストｃｔｏｔａｌ（ｋ）を主記憶装置１１に記憶させる。
【００５８】
仮説選択部５０は、主記憶装置１１から、複数の演算器１２−ｍ−ｎによるそれぞれの更新後の仮説（ｈｐ，ｋ）の算出元の経路（ｋ）における解候補の総コストｃｔｏｔａｌ（ｋ）を取得する。
仮説選択部５０は、例えば、以下の式（４）に示すように、それぞれの総コストｃｔｏｔａｌ（ｋ）の逆数に比例する値を、更新後の仮説（ｈｐ，ｋ）の評価値Ｒｅｐ，ｋとして算出する。
0006942287.tif 000004
式（４）において、αは、正の定数である。
【００５９】
仮説選択部５０は、全ての評価値Ｒｅ１，１〜ＲｅＰ，Ｋを比較し、主記憶装置１１により記憶されている更新後の仮説（ｈｐ，ｋ）の中で、例えば、評価値が高い上位Ｈ個の仮説（ｈｐ，ｋ）を残し、上位Ｈ個以外の仮説（ｈｐ，ｋ）を破棄仮説として選択する。
仮説選択部５０は、主記憶装置１１により記憶されている更新後の仮説（ｈｐ，ｋ）のうち、選択した破棄仮説を削除する。
【００６０】
以上の実施の形態２では、目標割当部２３−ｐ−ｑにより算出された複数の組み合わせの総コストのうち、更新後の仮説の算出元の組み合わせの総コストを互いに比較し、総コストの比較結果に基づいて、更新後の仮説の中で、一部の仮説を破棄する仮説選択部５０を備えるように、図１５に示す追尾処理装置１を構成した。したがって、図１５に示す追尾処理装置１は、図１に示す追尾処理装置１と同様に、航跡を含む複数の仮説の更新処理を並列に処理する際に、それぞれの仮説の更新処理自体を並列に処理することができるほか、仮説の爆発的な増加を抑えることができる。
【００６１】
図１及び図１５に示す追尾処理装置１では、目標割当部２３−ｐ−ｑ（ｑ＝１，２，３，４，５）が、コスト算出部２２−ｐ−１〜２２−ｐ−５から出力されたコスト要素ｃｐ，１〜ｃｐ，５を比較することで、最小のコスト要素ｃｐ，ｑを探索している。
目標の個数であるＱが例えば８であれば、目標割当部２３−ｐ−１〜２３−ｐ−Ｑのうちのいずれかの目標割当部２３が、以下の図１６に示す探索処理によって、最小のコスト要素ｃｐ，ｑを探索することが可能である。
【００６２】
図１６は、目標割当部２３による最小のコスト要素ｃｐ，ｑの探索処理を示す説明図である。
図１６では、Ｑ＝８であり、航跡番号ｐにおけるコスト要素ｃｐ，ｑが有する値が以下の通りである。
ｃｐ，１＝４、ｃｐ，２＝５、ｃｐ，３＝３、ｃｐ，４＝８
ｃｐ，５＝７、ｃｐ，６＝２、ｃｐ，７＝４、ｃｐ，８＝６
最小値選択器（以下、「ｍｉｎ」と称する）６１−１〜６１−８、６２−１〜６２−８、６３−１〜６３−８は、２つの値を比較して、小さい方の値を選択する。
【００６３】
ｍｉｎ６１−１は、コスト要素ｃｐ，１が有する値“４”と、コスト要素ｃｐ，５が有する値“７”とを比較し、小さい方の値として“４”を選択する。
ｍｉｎ６１−２は、コスト要素ｃｐ，２が有する値“５”と、コスト要素ｃｐ，６が有する値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６１−３は、コスト要素ｃｐ，３が有する値“３”と、コスト要素ｃｐ，７が有する値“４”とを比較し、小さい方の値として“３”を選択する。
ｍｉｎ６１−４は、コスト要素ｃｐ，４が有する値“８”と、コスト要素ｃｐ，８が有する値“６”とを比較し、小さい方の値として“６”を選択する。
ｍｉｎ６１−５は、コスト要素ｃｐ，１が有する値“４”と、コスト要素ｃｐ，５が有する値“７”とを比較し、小さい方の値として“４”を選択する。
ｍｉｎ６１−６は、コスト要素ｃｐ，２が有する値“５”と、コスト要素ｃｐ，６が有する値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６１−７は、コスト要素ｃｐ，３が有する値“３”と、コスト要素ｃｐ，７が有する値“４”とを比較し、小さい方の値として“３”を選択する。
ｍｉｎ６１−８は、コスト要素ｃｐ，４が有する値“８”と、コスト要素ｃｐ，８が有する値“６”とを比較し、小さい方の値として“６”を選択する。
【００６４】
ｍｉｎ６２−１は、ｍｉｎ６１−１により選択された値“４”と、ｍｉｎ６１−３により選択された値“３”とを比較し、小さい方の値として“３”を選択する。
ｍｉｎ６２−２は、ｍｉｎ６１−２により選択された値“２”と、ｍｉｎ６１−４により選択された値“６”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６２−３は、ｍｉｎ６１−１により選択された値“４”と、ｍｉｎ６１−３により選択された値“３”とを比較し、小さい方の値として“３”を選択する。
ｍｉｎ６２−４は、ｍｉｎ６１−２により選択された値“２”と、ｍｉｎ６１−４により選択された値“６”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６２−５は、ｍｉｎ６１−５により選択された値“４”と、ｍｉｎ６１−７により選択された値“３”とを比較し、小さい方の値として“３”を選択する。
ｍｉｎ６２−６は、ｍｉｎ６１−６により選択された値“２”と、ｍｉｎ６１−８により選択された値“６”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６２−７は、ｍｉｎ６１−５により選択された値“４”と、ｍｉｎ６１−７により選択された値“３”とを比較し、小さい方の値として“３”を選択する。
ｍｉｎ６２−８は、ｍｉｎ６１−６により選択された値“２”と、ｍｉｎ６１−８により選択された値“６”とを比較し、小さい方の値として“２”を選択する。
【００６５】
ｍｉｎ６３−１は、ｍｉｎ６２−１により選択された値“３”と、ｍｉｎ６２−２により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−２は、ｍｉｎ６２−１により選択された値“３”と、ｍｉｎ６２−２により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−３は、ｍｉｎ６２−３により選択された値“３”と、ｍｉｎ６２−４により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−４は、ｍｉｎ６２−３により選択された値“３”と、ｍｉｎ６２−４により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−５は、ｍｉｎ６２−５により選択された値“３”と、ｍｉｎ６２−６により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−６は、ｍｉｎ６２−５により選択された値“３”と、ｍｉｎ６２−６により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−７は、ｍｉｎ６２−７により選択された値“３”と、ｍｉｎ６２−８により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
ｍｉｎ６３−８は、ｍｉｎ６２−７により選択された値“３”と、ｍｉｎ６２−８により選択された値“２”とを比較し、小さい方の値として“２”を選択する。
【００６６】
ｍｉｎ６３−１〜６３−８におけるいずれの選択結果も“２”となり、最小のコスト要素ｃｐ，ｑが有する値が“２”となる。
また、“２”の値を有するコスト要素ｃｐ，ｑがコスト要素ｃｐ，６であるため、最小のコスト要素ｃｐ，ｑがコスト要素ｃｐ，６である。
【００６７】
図１及び図１５に示す追尾処理装置１では、目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３が、解候補の総コストを算出している。
例えば、航跡番号の個数であるＰが例えば８であれば、いずれか１つの目標割当部２３が、以下の図１７に示す算出処理によって、解候補の総コストを算出することが可能である。
【００６８】
図１７は、目標割当部２３による解候補の総コストの算出処理を示す説明図である。
図１７では、Ｐ＝８であり、目標番号ｑにおけるコスト要素ｃｐ，ｑが有する値が以下の通りである。
ｃ１，ｑ＝４、ｃ２，ｑ＝５、ｃ３，ｑ＝３、ｃ４，ｑ＝８
ｃ５，ｑ＝７、ｃ６，ｑ＝２、ｃ７，ｑ＝４、ｃ８，ｑ＝６
加算器（図１７では、「＋」と表記している）７１−１〜７１−８、７２−１〜７２−８、７３−１〜７３−８は、２つの値を加算する。
【００６９】
加算器７１−１は、コスト要素ｃ１，ｑが有する値“４”と、コスト要素ｃ５，ｑが有する値“７”とを加算し、加算結果として“１１”を得ている。
加算器７１−２は、コスト要素ｃ２，ｑが有する値“５”と、コスト要素ｃ６，ｑが有する値“２”とを加算し、加算結果として“７”を得ている。
加算器７１−３は、コスト要素ｃ３，ｑが有する値“３”と、コスト要素ｃ７，ｑが有する値“４”とを加算し、加算結果として“７”を得ている。
加算器７１−４は、コスト要素ｃ４，ｑが有する値“８”と、コスト要素ｃ８，ｑが有する値“６”とを加算し、加算結果として“１４”を得ている。
加算器７１−５は、コスト要素ｃ１，ｑが有する値“４”と、コスト要素ｃ５，ｑが有する値“７”とを加算し、加算結果として“１１”を得ている。
加算器７１−６は、コスト要素ｃ２，ｑが有する値“５”と、コスト要素ｃ６，ｑが有する値“２”とを加算し、加算結果として“７”を得ている。
加算器７１−７は、コスト要素ｃ３，ｑが有する値“３”と、コスト要素ｃ７，ｑが有する値“４”とを加算し、加算結果として“７”を得ている。
加算器７１−８は、コスト要素ｃ４，ｑが有する値“８”と、コスト要素ｃ８，ｑが有する値“６”とを加算し、加算結果として“１４”を得ている。
【００７０】
加算器７２−１は、加算器７１−１の加算結果“１１”と、加算器７１−３の加算結果“７”とを加算し、加算結果として“１８”を得ている。
加算器７２−２は、加算器７１−２の加算結果“７”と、加算器７１−４の加算結果“１４”とを加算し、加算結果として“２１”を得ている。
加算器７２−３は、加算器７１−１の加算結果“１１”と、加算器７１−３の加算結果“７”とを加算し、加算結果として“１８”を得ている。
加算器７２−４は、加算器７１−２の加算結果“７”と、加算器７１−４の加算結果“１４”とを加算し、加算結果として“２１”を得ている。
加算器７２−５は、加算器７１−５の加算結果“１１”と、加算器７１−７の加算結果“７”とを加算し、加算結果として“１８”を得ている。
加算器７２−６は、加算器７１−６の加算結果“７”と、加算器７１−８の加算結果“１４”とを加算し、加算結果として“２１”を得ている。
加算器７２−７は、加算器７１−５の加算結果“１１”と、加算器７１−７の加算結果“７”とを加算し、加算結果として“１８”を得ている。
加算器７２−８は、加算器７１−６の加算結果“７”と、加算器７１−８の加算結果“１４”とを加算し、加算結果として“２１”を得ている。
【００７１】
加算器７３−１は、加算器７２−１の加算結果“１８”と、加算器７２−２の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−２は、加算器７２−１の加算結果“１８”と、加算器７２−２の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−３は、加算器７２−３の加算結果“１８”と、加算器７２−４の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−４は、加算器７２−３の加算結果“１８”と、加算器７２−４の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−５は、加算器７２−５の加算結果“１８”と、加算器７２−６の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−６は、加算器７２−５の加算結果“１８”と、加算器７２−６の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−７は、加算器７２−７の加算結果“１８”と、加算器７２−８の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
加算器７３−８は、加算器７２−７の加算結果“１８”と、加算器７２−８の加算結果“２１”とを加算し、加算結果として“３９”を得ている。
【００７２】
加算器７３−１〜７３−８におけるいずれの加算結果も“３９”となり、解候補の総コストが“３７”となる。
【００７３】
図１及び図１５に示す追尾処理装置１では、目標割当部２３−１−ｑ〜２３−４−ｑのうち、いずれか１つの目標割当部２３が、複数の解候補の中から、総コストが小さい上位Ｋ個の解候補を選択している。
例えば、複数の解候補の数が例えば８であれば、いずれか１つの目標割当部２３が、以下の図１８に示す選択処理によって、複数の解候補の中から、総コストが小さい上位Ｋ個の解候補を選択することが可能である。
【００７４】
図１８は、目標割当部２３による解候補の選択処理を示す説明図である。
図１８では、解候補の数が８、Ｋ＝４であり、８個の解候補の総コストｃｔｏｔａｌ（ｋ）が以下の通りである。
ｃｔｏｔａｌ（１）＝４、ｃｔｏｔａｌ（２）＝５、ｃｔｏｔａｌ（３）＝３、ｃｔｏｔａｌ（４）＝８
ｃｔｏｔａｌ（５）＝７、ｃｔｏｔａｌ（６）＝２、ｃｔｏｔａｌ（７）＝４、ｃｔｏｔａｌ（８）＝６
比較器（図１８では、「≧」と表記している）８１−１〜８１−８は、Ｋ（＝４）と総コストｃｔｏｔａｌ（ｋ）とを比較する。
比較器８１−１〜８１−８は、Ｋが総コストｃｔｏｔａｌ（ｋ）以上であれば、“１”を出力し、Ｋが総コストｃｔｏｔａｌ（ｋ）未満であれば、“０”を出力する。
【００７５】
比較器８１−１は、Ｋと総コストｃｔｏｔａｌ（１）（＝４）とを比較し、Ｋが総コストｃｔｏｔａｌ（１）以上であるため、“１”を出力する。
比較器８１−２は、Ｋと総コストｃｔｏｔａｌ（２）（＝５）とを比較し、Ｋが総コストｃｔｏｔａｌ（２）未満であるため、“０”を出力する。
比較器８１−３は、Ｋと総コストｃｔｏｔａｌ（３）（＝３）とを比較し、Ｋが総コストｃｔｏｔａｌ（３）以上であるため、“１”を出力する。
比較器８１−４は、Ｋと総コストｃｔｏｔａｌ（４）（＝８）とを比較し、Ｋが総コストｃｔｏｔａｌ（４）未満であるため、“０”を出力する。
比較器８１−５は、Ｋと総コストｃｔｏｔａｌ（５）（＝７）とを比較し、Ｋが総コストｃｔｏｔａｌ（５）未満であるため、“０”を出力する。
比較器８１−６は、Ｋと総コストｃｔｏｔａｌ（６）（＝２）とを比較し、Ｋが総コストｃｔｏｔａｌ（６）以上であるため、“１”を出力する。
比較器８１−７は、Ｋと総コストｃｔｏｔａｌ（７）（＝４）とを比較し、Ｋが総コストｃｔｏｔａｌ（７）以上であるため、“１”を出力する。
比較器８１−８は、Ｋと総コストｃｔｏｔａｌ（８）（＝６）とを比較し、Ｋが総コストｃｔｏｔａｌ（８）未満であるため、“０”を出力する。
【００７６】
加算器８２−１は、比較器８１−１から出力された“１”と、比較器８１−５から出力された“０”とを加算し、加算結果として“１”を得ている。
加算器８２−２は、比較器８１−２から出力された“０”と、比較器８１−６から出力された“１”とを加算し、加算結果として“１”を得ている。
加算器８２−３は、比較器８１−３から出力された“１”と、比較器８１−７から出力された“１”とを加算し、加算結果として“２”を得ている。
加算器８２−４は、比較器８１−４から出力された“０”と、比較器８１−８から出力された“０”とを加算し、加算結果として“０”を得ている。
加算器８２−５は、比較器８１−１から出力された“１”と、比較器８１−５から出力された“０”とを加算し、加算結果として“１”を得ている。
加算器８２−６は、比較器８１−２から出力された“０”と、比較器８１−６から出力された“１”とを加算し、加算結果として“１”を得ている。
加算器８２−７は、比較器８１−３から出力された“１”と、比較器８１−７から出力された“１”とを加算し、加算結果として“２”を得ている。
加算器８２−８は、比較器８１−４から出力された“０”と、比較器８１−８から出力された“０”とを加算し、加算結果として“０”を得ている。
【００７７】
加算器８３−１は、加算器８２−１の加算結果“１”と、加算器８２−３の加算結果“２”とを加算し、加算結果として“３”を得ている。
加算器８３−２は、加算器８２−２の加算結果“１”と、加算器８２−４の加算結果“０”とを加算し、加算結果として“１”を得ている。
加算器８３−３は、加算器８２−１の加算結果“１”と、加算器８２−３の加算結果“２”とを加算し、加算結果として“３”を得ている。
加算器８３−４は、加算器８２−２の加算結果“１”と、加算器８２−４の加算結果“０”とを加算し、加算結果として“１”を得ている。
加算器８３−５は、加算器８２−５の加算結果“１”と、加算器８２−７の加算結果“２”とを加算し、加算結果として“３”を得ている。
加算器８３−６は、加算器８２−６の加算結果“１”と、加算器８２−８の加算結果“０”とを加算し、加算結果として“１”を得ている。
加算器８３−７は、加算器８２−５の加算結果“１”と、加算器８２−７の加算結果“２”とを加算し、加算結果として“３”を得ている。
加算器８３−８は、加算器８２−６の加算結果“１”と、加算器８２−８の加算結果“０”とを加算し、加算結果として“１”を得ている。
【００７８】
加算器８４−１は、加算器８３−１の加算結果“３”と、加算器８３−２の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−２は、加算器８３−１の加算結果“３”と、加算器８３−２の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−３は、加算器８３−３の加算結果“３”と、加算器８３−４の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−４は、加算器８３−３の加算結果“３”と、加算器８３−４の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−５は、加算器８３−５の加算結果“３”と、加算器８３−６の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−６は、加算器８３−５の加算結果“３”と、加算器８３−６の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−７は、加算器８３−７の加算結果“３”と、加算器８３−８の加算結果“１”とを加算し、加算結果として“４”を得ている。
加算器８４−８は、加算器８３−７の加算結果“３”と、加算器８３−８の加算結果“１”とを加算し、加算結果として“４”を得ている。
【００７９】
加算器８４−１〜８４−８におけるいずれの加算結果も“４”となり、総コストが小さい上位４個の解候補を選択できている。
総コストが小さい上位４個の解候補として、“１”を出力している比較器８１−１，８１−３，８１−６，８１−７におけるＫとの比較対象である総コストｃｔｏｔａｌ（１），ｃｔｏｔａｌ（３），ｃｔｏｔａｌ（６），ｃｔｏｔａｌ（７）に係る解候補が、いずれか１つの目標割当部２３によって選択される。
【００８０】
なお、本願発明はその発明の範囲内において、各実施の形態の自由な組み合わせ、あるいは各実施の形態の任意の構成要素の変形、もしくは各実施の形態において任意の構成要素の省略が可能である。
【産業上の利用可能性】
【００８１】
この発明は、目標の位置の時間的な変化を示す航跡を含む仮説を更新する追尾処理装置、追尾処理方法及び目標観測装置に適している。
【符号の説明】
【００８２】
１  追尾処理装置、１１  主記憶装置、１２−ｍ−ｎ  演算器、２０  制御部、２１，２１−ｐ，２１−（Ｐ＋ｑ）  仮説観測位置読込部、２２，２２−ｐ−ｑ  コスト算出部、２３，２３−ｐ−ｑ  目標割当部、２４  仮説出力部、２５，２５−ｐ−ｋ  航跡生成部、２６，２６−ｐ−ｋ  更新仮説出力部、２７  データ記憶部、３０  制御回路、３１  仮説観測位置読込回路、３２  コスト算出回路、３３  目標割当回路、３４  航跡生成回路、３５  更新仮説出力回路、３６  データ記憶回路、４１  メモリ、４２  プロセッサ、５０  仮説選択部、６１−１〜６１−８、６２−１〜６２−８、６３−１〜６３−８  ｍｉｎ、７１−１〜７１−８、７２−１〜７２−８、７３−１〜７３−８  加算器、８１−１〜８１−８  比較器、８２−１〜８２−８、８３−１〜８３−８、８４−１〜８４−８  加算器。
【図１】
0006942287.tif 000005
【図２】
0006942287.tif 000006
【図３】
0006942287.tif 000007
【図４】
0006942287.tif 000008
【図５】
0006942287.tif 000009
【図６】
0006942287.tif 000010
【図７】
0006942287.tif 000011
【図８】
0006942287.tif 000012
【図９】
0006942287.tif 000013
【図１０】
0006942287.tif 000014
【図１１】
0006942287.tif 000015
【図１２】
0006942287.tif 000016
【図１３】
0006942287.tif 000017
【図１４】
0006942287.tif 000018
【図１５】
0006942287.tif 000019
【図１６】
0006942287.tif 000020
【図１７】
0006942287.tif 000021
【図１８】
0006942287.tif 000022