(57)【要約】【課題】計算機資源を有効に活用し、高速な探索処理を可能とする並列多目標追尾装置を得る。【解決手段】クラスタ内の目標物予測領域と観測点の組み合わせから、所定の個数の信頼度の高い組み合わせを探索して出力する組み合わせ探索手段と、目標物予測領域と観測点の組み合わせの一部である部分的な組み合わせについて探索処理を行い、信頼度の高い部分的な組み合わせを選択して出力する複数のタスク処理手段と、複数の前記部分的な組み合わせを前記複数のタスク処理手段に割り付ける負荷分散手段とを備えた。【選択図】              図１
2004219299.tif 000002
【特許請求の範囲】
【請求項１】
レーダが捉えた複数の目標物の移動を予測し、その予測結果に応じて予測領域を生成する予測領域生成手段と、
レーダから入力された観測点情報と、前記予測領域生成手段が生成した目標物予測領域からクラスタを生成するクラスタ生成手段と、
前記クラスタ生成手段が生成したクラスタ内の目標物予測領域と観測点の組み合わせから、所定個数の信頼度の高い組み合わせを探索して出力する組み合わせ探索手段と、
前記組み合わせ探索手段が出力した組み合わせに基づいて前記目標物の情報を更新し、それを追尾結果として出力すると共に、前記目標物の移動予測のために前記予測領域生成手段に入力する目標物航跡更新手段と、を備える並列多目標追尾装置において、
前記目標物予測領域と前記観測点の複数の組み合わせの一部である部分的な組み合わせについて探索処理を行い、信頼度の高い部分的な組み合わせを選択して出力する複数のタスク処理手段と、
複数の前記部分的な組み合わせを前記複数のタスク処理手段に割り付ける負荷分散手段と、をさらに備え、
前記組み合わせ探索手段は、前記クラスタ生成手段が生成したクラスタ内の目標物予測領域と観測点の組み合わせから複数の前記部分的な組み合わせを生成して前記負荷分散手段に出力し、前記複数のタスク処理手段が出力する部分的な組み合わせのうち、所定個数の信頼度の高い組み合わせを探索して出力することを特徴とする並列多目標追尾装置。
【請求項２】
前記負荷分散手段は、前記部分的な組み合わせを順に前記複数のタスク処理手段に割り付けることを特徴とする請求項１に記載した並列多目標追尾装置。
【請求項３】
前記負荷分散手段は、複数の前記部分的な組み合わせのうち、個々の部分的な組み合わせについての探索処理の予測負荷を算出し、その予測負荷に基づいて、前記複数のタスク処理手段の個々の処理負荷が均等になるように前記部分的な組み合わせを割り付けることを特徴とする請求項１に記載した並列多目標追尾装置。
【請求項４】
前記負荷分散手段は、前記個々の部分的な組み合わせが有する観測点の個数に基づいて、前記予測負荷を算出することを特徴とする請求項３に記載した並列多目標追尾装置。
【請求項５】
前記負荷分散手段は、前記個々の部分的な組み合わせが有する観測点の個数と目標物の個数に基づいて、前記予測負荷を算出することを特徴とする請求項３に記載した並列多目標追尾装置。
【請求項６】
前記負荷分散手段は、前記複数のタスク処理手段の負荷状況を収集して、この負荷状況の平均値を算出し、負荷状況が前記平均値を超える前記タスク処理手段に、前記探索処理の移動指示を行い、
前記タスク処理手段は、前記移動指示を受けて、前記負荷状況が前記平均値未満である他の前記タスク処理手段に、前記平均値を超過した分の前記探索処理の移動を行うことを特徴とする請求項１乃至請求項５のいずれか一に記載した並列多目標追尾装置。
【請求項７】
前記負荷分散手段は、前記部分的な組み合わせについての探索処理を１つずつ前記各タスク処理手段に分配し、
前記各タスク処理手段は、前記部分的な組み合わせについての探索処理を終了すると、前記負荷分散手段に対し、次の部分的な組み合わせについての探索処理の分配を要求することを特徴とする請求項１に記載した並列多目標追尾装置。
【請求項８】
前記負荷分散手段は、２以上の前記部分的な組み合わせについての探索処理を前記各タスク処理手段に分配し、
前記各タスク処理手段は、前記部分的な組み合わせについての探索処理を進めた結果、分配された前記探索処理であって、未処理の探索処理の個数が所定の数まで減少した場合に、前記負荷分散手段に対し、次の部分的な組み合わせについての探索処理の分配を要求することを特徴とする請求項１に記載した並列多目標追尾装置。
【請求項９】
前記負荷分散手段は、前記部分的な組み合わせのうち、処理量の大きな組み合わせについての探索処理を優先的に前記複数のタスク処理手段に分配することを特徴とする請求項１及び請求項７又は請求項８のいずれか一に記載した並列多目標追尾装置。
【請求項１０】
前記負荷分散手段は、前記複数のタスク処理手段の一と同一の中央演算装置により処理されることを特徴とする請求項１乃至請求項９のいずれか一に記載された並列多目標追尾装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、レーダにおける複数目標物の追尾手法として、ＪＰＤＡ（Ｊｏｉｎｔ  Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｄａｔａ  Ａｓｓｏｃｉａｔｉｏｎ）やＭＨＴ（Ｍｕｌｔｉｐｌｅ  Ｈｙｐｏｔｈｅｓｉｓ  Ｔｒａｃｋｉｎｇ）のような複数の目標物の組み合わせを想定した追尾方法を採用する並列多目標追尾装置において、処理を分散する装置に関するものである。
【０００２】
【従来の技術】
多目標追尾を行う従来の追尾方法としては、ＪＰＤＡやＭＨＴのように目標物の予測領域を生成し、入力された観測点と上記目標物の予測領域の全ての組み合わせを求め、これらの組み合わせのそれぞれについて目標物の持つ情報（航跡）の更新を行う処理を行う方法がある。このような方法では、複数存在する目標物に対して観測点も複数存在するので、それぞれの観測点と複数の目標物との対応関係（組み合わせ）も複数通り存在する。そこで、このような複数の組み合わせのそれぞれについて航跡の更新を高速に行うために、並列処理技術が用いられることがある。
【０００３】
ここで、そのような処理を並列処理するための技術として、目標物と観測点の組み合わせを探索木として表し、その節を並列処理単位としてタスク処理部に並列処理させる方法がある（例えば、特許文献１や特許文献２）。
【０００４】
【特許文献１】
特開２００１−９９９２１「並列多目標追尾装置」（第４−９頁、第１図）
【０００５】
【特許文献２】
特開２００１−９９９２５「並列多目標追尾装置」（第４−９頁、第１図）
【０００６】
【発明が解決しようとする課題】
従来の「並列多目標追尾装置」では、観測点と目標物の予測領域の全ての組み合わせを探索木として表し、節を単位として各タスク処理部に分配する構成としているが、それらの組み合わせの最大数は（Ｔ＋１）のＹ乗（ただし、Ｔは目標物の数でＹは観測点の数）となって、膨大となるため、それぞれの節の処理を並列処理しても、一定時間内に処理できるとは限らない。
【０００７】
また、これらの方法では、並列処理の単位を探索木の節としているので、全ての組み合わせの数に対して採用すべき組み合わせの数が少ない場合、処理した組み合わせのほとんどが採用されない組み合わせのための処理となるために、無駄な処理に計算機資源を費やす結果となり、並列処理しても高速化できないという問題点があった。
【０００８】
本発明は上記のような問題点を解決するためになされたもので、並列処理の単位を探索木の節ではなく、組み合わせの探索処理とすることで、Ｎベスト探索においても並列処理の効果を上げ、高速化することを目的とするものである。
【０００９】
【課題を解決するための手段】
本発明に係る並列他目標追尾装置は、
複数の目標物の移動を予測し、その予測結果に応じて予測領域を生成する予測領域生成手段と、
レーダから入力された観測点情報と、前記予測領域生成手段が生成し目標物予測領域からクラスタを生成するクラスタ生成手段と、
前記クラスタ生成手段が生成したクラスタ内の目標物予測領域と観測点の組み合わせから、所定の個数の信頼度の高い組み合わせを探索して出力する組み合わせ探索手段と、
前記組み合わせ探索手段が出力した組み合わせに基づいて前記目標物の情報を更新し、それを追尾結果として出力すると共に、前記目標物の移動予測のために前記予測領域生成手段に入力する目標物航跡更新手段と、を備える並列多目標追尾装置であって、
前記目標物予測領域と前記観測点の組み合わせの一部である部分的な組み合わせについて探索処理を行い、信頼度の高い部分的な組み合わせを選択して出力する複数のタスク処理手段と、
複数の前記部分的な組み合わせを前記複数のタスク処理手段に割り付ける負荷分散手段と、をさらに備え、
前記組み合わせ探索手段は、前記クラスタ生成手段が生成したクラスタ内の目標物予測領域と観測点の組み合わせから複数の前記部分的な組み合わせを生成して前記負荷分散手段に出力し、前記複数のタスク処理手段が出力する部分的な組み合わせのうち、所定の個数の信頼度の高い組み合わせを探索して出力するものである。
【００１０】
【発明の実施の形態】
以下、本発明の実施の形態について述べる。
実施の形態１．
図１は、本発明の実施の形態１における並列多目標追尾装置の構成を示したものである。図において、入力線１−１は、観測点を入力する。予測領域生成手段１−２は、目標物の移動を予測し、その予測に応じて、予測範囲を生成する。クラスタ生成手段１−３は、観測点と予測領域からクラスタを生成する。組み合わせ探索手段１−４は、生成されたクラスタ内の目標物予測領域と観測点の組み合わせの中である決められた個数の信頼度の高い組み合わせのみを探索する。タスク処理手段１−５ａ〜１−５ｄは、個々の探索処理を行なう部位であって、それぞれがＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ：中央演算装置）またはＣＰＵを搭載したコンピュータによって構成される。目標物航跡更新手段１−６は、組み合わせ探索手段の処理結果に基づいて、目標物の持つ情報（航跡）の更新を行なう。出力線１−７は、本装置の追尾結果である目標物航跡更新手段１−６の出力を表している。転送線１−８ａ〜１−８ｅは、各手段の処理結果の転送を行う。負荷分散手段１−９は、個々の探索処理をタスク処理手段１−５ａ〜１−５ｄに分配する。
【００１１】
次に本追尾装置の処理について、ＪＰＤＡを用いる場合を例として説明する。図２は、ＪＰＤＡにおける目標物と観測点の関係の例を示したものである。図において、
・  ｔ（１）とｔ（２）は目標物の予測座標、この予測座標を中心とする楕円は、予測範囲
・  ｙ（１）〜ｙ（４）は観測点の座標
を示している。
【００１２】
まずレーダから、これらの観測点についての観測点情報が、入力線１−１を介してクラスタ生成手段１−３に入力される。また、予測領域生成手段１−２は、内部で保持している目標物の情報（座標や速度など）から、観測点が観測された時間に対応する目標物の予測座標ｔ（１），ｔ（２）と、存在確率が一定の値以上となる予測領域（図２の楕円）とを算出し、これらを転送線１−８ａを介して、同じくクラスタ生成手段１−３に出力する。
【００１３】
次に、クラスタ生成手段１−３は、複数の目標物の予測領域と観測点の含有関係を調べ、複数の予測領域に含まれる観測点が存在する場合に、その観測点を含有する予測領域同士を結合して、１つのクラスタを生成し、このクラスタの情報（観測点と目標物の予測領域）を、転送線１−８ｂを介して組み合わせ探索手段１−４に出力する。図２では、観測点ｙ（２）が２つの予測領域に含まれるため、この２つを１つのクラスタとして結合する。
【００１４】
続いて、組み合わせ探索手段１−４は、負荷分散手段１−９とタスク処理手段１−５ａ〜１−５ｄを用いて、観測点と目標物の予測領域の組み合わせの中から、信頼度の高い順に所定の個数の組み合わせを生成する。図４は、観測点と目標物の予測領域の組み合わせの中から、信頼度の高い順に所定の個数の組み合わせを生成する処理のフローチャートである。図のステップＳ４０１において、組み合わせ探索手段１−４は観測点と目標物の予測領域の組み合わせを生成する。
【００１５】
ここで、観測点と目標物の予測領域の組み合わせは、次のように求められる。
図３は、図２に示した目標物の予測座標と観測点の座標の関係を示す行列Ωを示すものである。行列Ωの行方向の成分１〜４はそれぞれｙ（１）〜ｙ（４）に対応するものである。一方、列方向の成分０，１，２は次のような意味を有している。すなわち成分０は、観測点ｙ（ｋ）（ｋ＝１，２，３，４）がどの目標物にも対応していないことを意味する。そして成分１と成分２は、それぞれ目標物ｔ（１）およびｔ（２）である。各行列の成分の値は可能性の有無を示すもので、成分の値が０である組合せは可能性なし、そして成分の値が１である組合せは可能性ありであることを意味する。したがって列成分０はすべての行にわたって１となっているが、これはどの観測点も目標物に対応していない可能性があることを示している。また例えば行成分２（ｙ（２）に対応する）は目標物ｔ（１）およびｔ（２）のいずれにも対応しうる可能性があることを示している。
【００１６】
以上を総合すると、次のようになる。すなわち、
・  観測点ｙ（１）は、目標物ｔ（２）、もしくは、対応する目標無しである。
・  観測点ｙ（２）は、目標物ｔ（１）、もしくは、目標物ｔ（２）、もしくは、対応する目標無しである。
・  観測点ｙ（３）は、目標物ｔ（１）、もしくは、対応する目標無しである。
・  観測点ｙ（４）は、目標物ｔ（１）、もしくは、対応する目標無しである。
【００１７】
以上のようなクラスタの情報に基づき、組み合わせ探索手段１−４は、組み合わせの探索処理を生成する。すなわち上記を満たす次のような目標物と観測点の組み合わせについて、探索処理を生成する。
・  ｔ（１）がｙ（２）で、ｔ（２）がｙ（１）のケース
・  ｔ（１）がｙ（２）で、ｔ（２）が対応なしのケース
・  ｔ（１）がｙ（３）で、ｔ（２）がｙ（１）のケース
・  ｔ（１）がｙ（３）で、ｔ（２）がｙ（２）のケース
・  ｔ（１）がｙ（３）で、ｔ（２）が対応なしのケース
・  ｔ（１）がｙ（４）で、ｔ（２）がｙ（１）のケース
・  ｔ（１）がｙ（４）で、ｔ（２）がｙ（２）のケース
・  ｔ（１）がｙ（４）で、ｔ（２）が対応なしのケース
・  ｔ（１）が対応なしで、ｔ（２）がｙ（１）のケース
・  ｔ（１）が対応なしで、ｔ（２）がｙ（２）のケース
・  ｔ（１）が対応なしで、ｔ（２）が対応なしのケース
【００１８】
次にステップＳ４０２において、負荷分散手段１−９は、組み合わせ探索手段１−４が生成した組み合わせを、転送線１−８ｆを介して取り込み、各タスク処理手段１−５ａ〜１−５ｄに分配する。ここでのタスク分配の方法については、後述する。
【００１９】
次にステップＳ４０３において、タスク処理手段１−５ａ〜１−５ｄは、組み合わせ探索手段１−４によって生成され組み合わせであって、負荷分散手段１−９がタスク処理手段１−５ａ〜１−５ｄに分配した処理を並列実行する。この処理は、組み合わせ探索手段１−４が生成した組み合わせに対して信頼度を算出する処理である。そこで、本処理の内容を、以下に説明する。
【００２０】
まず、最も信頼度の高い組み合わせを探索する。最も信頼性の高い組み合わせを探索する最も単純な方法は、次のようなものである。すなわち、初めに目標物と観測点の組み合わせの中から、任意の組み合わせを１つ生成し（以下、組み合わせＡとする）、その信頼度を仮の最適解として記憶しておく。次に、組み合わせＡにおける個々の観測点の信頼度の逆数の合計値を、組み合わせＡについて求める。そして、その他の組み合わせ（以下、組み合わせＢとする）を生成し、組み合わせＢの各観測点の信頼度の逆数を組み合わせＢについて加算していき、組み合わせＢの信頼度の逆数の和（途中経過）が仮の最適解の信頼度の逆数の合計値より大きくなった場合に、その探索を打ち切る。また組み合わせＢの観測点すべてについて、信頼度の逆数を合計してもなお、組み合わせＡの信頼度の逆数の合計よりも小さい場合には、組み合わせＢを新たな仮の最適解として、その他の組み合わせとの比較処理を続行する。信頼度は負数となることがないので、仮の最適解の信頼度の逆数の合計値と他の組み合わせの信頼度の和算の途中経過を比較することで、全ての組み合わせを探索する必要がなくなる。
【００２１】
上記において、組み合わせ探索手段１−４が仮の最適解を求めておき、タスク処理手段１−５ａ〜１−５ｄは、この仮の最適解を参照して不必要な演算を省略するようにしてもよい。
【００２２】
または、”Ａｎ  Ｅｘｔｅｎｓｉｏｎ  ｏｆ  ｔｈｅ  Ｍｕｎｋｒｅｓ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｔｈｅ  Ａｓｓｉｇｎｍｅｎｔ  Ｐｒｏｂｌｅｍ  ｔｏ  Ｒｅｃｔａｎｇｕｌａｒ  Ｍａｔｒｉｃｅｓ”，  Ｆ．Ｂｏｕｒｇｅｏｉｓ  ａｎｄ  Ｊ−Ｃ  Ｌａｓｓａｌｌｅ，  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｏｆ  ｔｈｅ  ＡＣＭ  ，  Ｄｅｃ．  １９７１  Ｖｏｌ．１４，  Ｎｏ．１２“に記載されたアルゴリズム（本探索問題を競合が起きている部分から解きほぐしていくという方法）を用いてもよい。
【００２３】
次にステップＳ４０４において、組み合わせ探索手段１−４はタスク処理手段１−５ａ〜１−５ｄの算出した信頼度を、転送線１−８ｃ及び１−８ｆを介して受け取り、信頼度の高い順に組み合わせを所定の個数選択する。この処理を、図５に示すような目的物と観測点の組み合わせを表す樹形図を用いて、具体的に説明する。図５は、図２で示した観測点ｙ（１）〜ｙ（４）が対応しうる目標物を樹形図として表したものである。図において、楕円に囲まれた符号のうち、Ｃは対応する目標物がない状態を表している。またｔ（１）とｔ（２）はそれぞれ２つの目標物を表している。ｒｏｏｔは樹形図のルートを表すものである。図は、例えば観測点ｙ（１）が目標物に対応しない場合（Ｃ）、あるいは目標物ｔ（２）に対応する場合のいずれかの２つの可能性があることを示している。また観測点ｙ（１）が目標物ｔ（２）に対応する場合には、観測点ｙ（２）が、目標物に対応しない場合（Ｃ）、あるいは目標物ｔ（１）に対応する場合の、さらに２つの可能性があることを示している。
【００２４】
図では、タスク処理手段１−５ａ〜１−５ｄに算出させた信頼度を評価した結果として、太線５−１によって結合された組み合わせが、最も信頼度の高い組み合わせであるものとする。次に、組み合わせ探索手段１−４は、この太線５−１を除いた組み合わせの中から、それぞれの部分木（部分的な組み合わせ）での最も信頼度の高い組み合わせを探索し、その中で最も信頼度の高い組み合わせを、全体の中で２番目に信頼度の高い組み合わせとする。図６は、図５の樹形図から太線５−１と太線５−１によって特定される最後の要素ｙ（４）に対応する観測点を取り除いた樹形図である。この樹形図は、５−２、５−３、５−４、５−５の部分木から構成される。また図６においても、最も信頼度の高い組み合わせは太線で示されており、太線５−６で示す組み合わせが最も高い組み合わせであるものとする。太線５−６は、タスク処理手段１−５ａ〜１−５ｄに算出させた信頼度に基づいて求めたものである。
【００２５】
組み合わせ探索手段１−４は、さらにこの太線５−６を除いた組み合わせの中から、それぞれの部分木での最も信頼度の高い組み合わせを探索する。図７は、図６の太線５−６で表される組み合わせを除いた部分木による樹形図である。そして、５−７、５−８及び５−９で最も信頼度の高い組み合わせを探索し、既に求められている５−２、５−３、５−４の中の最も信頼度の高い組み合わせと合わせて、その中で最も信頼度の高い組み合わせを、全体の中で３番目に最も信頼度の高い組み合わせとする。これを予め決められた個数の組み合わせを求めるまで繰り返す。以上が、組み合わせ探索手段１−４によって、信頼度の高い順に所定の個数の組み合わせを生成する方法である。なお、この例では目標物と観測点が少ないので、説明のために樹形図上では全ての組み合わせを木として展開している。しかし現実には、より多くの目標物と観測点を有しており、組み合わせが多数となるため、処理上はこのような樹形図の展開はなされない。
【００２６】
以上のように負荷分散手段１−９は、並列処理の分配単位として樹形図の探索木の節を用いずに、部分的な組み合わせを用いているので、最終的に採用される解に対応する処理が分散されて実行されることとなる結果、無駄な処理が少なくなり、効率的に実行できる。
【００２７】
次に、負荷分散手段１−９における負荷の分散方法について説明する。組み合わせ探索手段１−４は、最も信頼度の高い組み合わせを取得した後、組み合わせ全体の中から、その組み合わせを除いた部分木に分割し、負荷分散手段１−９にその分割した部分木を渡す。その場合において、負荷分散手段１−９は、組み合わせ探索手段１−４から渡された部分木をタスク処理手段１−５ａ〜５ｄに１つずつ順番に分配する。例えば、部分木が１０個あれば、１つ目の部分木をタスク処理手段１−５ａへ、２つ目の部分木をタスク処理手段１−５ｂへと順に分配し、５つ目の部分木を再びタスク処理手段１−５ａへ割り付けていく。これにより、各タスク処理手段は、それぞれ２つの部分木の探索処理を行うことになる。以上が図４のフローチャートの説明である。
【００２８】
組み合わせ探索手段１−４は、タスク処理手段１−５ａ〜１−５ｄから送られてきた処理結果（「目標物と各観測点の対応関係についての重み付け」）を集計して、転送線１−８ｄを介して目標物航跡更新手段１−６に送る。続いて、目標物航跡更新手段１−６は、送られた個々の組合せ可能性を基に、目標物の情報を更新する。ここで更新された目標物の情報は、出力線１−７を介して出力され、転送線１−８ｅを介して予測領域生成手段１−２へも送られる。予測領域生成手段１−２は、更新された目標物の情報に基づいて、再び各目標物について移動予測を行ない、その予測領域を生成する。本追尾装置は、以上の動作を繰り返すことによって、追尾装置として動作する。
【００２９】
以上より明らかなように、実施の形態１による並列多目標追尾装置によれば、観測点と目標物との組み合わせを並列処理の単位として負荷分散することとし、負荷分散手段１−９がタスク処理手段１−５ａ〜１−５ｄに均等な個数になるように部分木の探索処理を分配することとしたので、各タスク処理での処理時間が確率的に均等となり、効率的に探索ができる、という効果を奏する。また、分配方法が非常に単純なので、負荷分配のオーバヘッドが少ない、という効果を奏する。
【００３０】
なお本追尾装置では、タスク処理手段１−５ａ〜１−５ｄのように４つのタスク処理手段が存在する場合について処理方法を示したが、タスク処理手段の個数は４つに限定されるわけではないことは、いうまでもない。
【００３１】
実施の形態２．
実施の形態１では、部分木の個数が均等になるように、タスク処理部１−５ａ〜１−５ｄに処理を分配したが、処理の負荷を均等にするような分配方法を採用してもよい。すなわち、負荷分散手段１−９は、組み合わせ探索手段１−４から渡された各部分木について、それぞれの探索に必要とされる予測負荷量を算出する。次に、その予測負荷量の合計値をタスク処理手段の個数で割ることにより、各タスク処理手段が担当する負荷量を算出する。そして、タスク処理手段１−５ａに部分木の先頭から１つのタスク処理手段が担当する処理能力量まで部分木を分配する。これをタスク処理手段１−５ｂ〜１−５ｄについても繰り返す。
【００３２】
このように負荷分散手段１−９が、各部分木の処理負荷を予測し、各タスク処理手段の負荷量を算出して、さらに各タスク処理手段の処理負荷が均等になるように部分木の探索処理をタスク処理手段１−５ａ〜１−５ｄに分配するので、各タスク処理の処理時間が均等となり、効率的に探索ができる、という効果がある。
【００３３】
次に、各部分木の処理負荷の予測方法について説明する。各部分木において、最も信頼度の高い組み合わせを見つけるまでの処理の負荷を厳密に見積もることは困難である。処理量は、処理するデータの量だけでなく、データの内容によっても異なってくるからである。例えば、個々の観測点と目標物の予測領域との最適な組み合わせで競合が起きなければ直ぐに探索できるし、競合が多ければその競合を解くのに時間がかかる。
【００３４】
そこで、ここでは部分木の高さ、すなわちその部分木が扱う観測点の数に基づいて、探索負荷を予測することとする。探索処理は、観測点の組み合わせについての信頼度を算出する処理を含むので、個々の観測点の信頼度を算出することになる。したがって観測点の数が多いほど、部分木の探索負荷が高くなることが予測できる。
【００３５】
以上のように各部分木の処理負荷を部分木の高さで予測し、負荷分散手段１−９が、予測負荷を基に各タスク処理手段の処理負荷が均等になるように、部分木の探索処理をタスク処理手段１−５ａ〜１−５ｄに分配するので、負荷の予測に要するオーバヘッドが少なくすることができ、かつ各タスク処理での処理時間が均等となって、効率的に探索ができる、という効果を奏する。
【００３６】
実施の形態３．
実施の形態２では、部分木の探索処理負荷を部分木の高さに基づいて予測することとしたが、部分木のノードの数を予測し、この数に基づいて負荷を予測してもよい。部分木の探索は、部分木のノードを辿ることであると考えると、部分木のノードの数が増えるにつれて、処理負荷も増大するからである。
【００３７】
しかし、部分木を全て辿ることによってノードの数を算出すると、結果的に全ての組み合わせを探索することになり、処理負荷の軽減につなげることができない。そこで、樹形図の各段、すなわち各観測点毎に子ノードの総数が幾つになるかを予測することにする。部分木における各節の子ノードの数は、子供に対応する観測点を含む目標物の予測領域の数＋１が最大値となる。＋１は観測点がクラッタである場合を考慮したものである。そこで、部分木の探索負荷をその部分木の先頭の観測点を除いた各観測点を含む目標物の予測領域の数＋１を乗じた数とする。先頭の観測点を除く理由は、先頭の観測点がその部分木のルートに相当するためである。例えば、図７の５−２の部分木では、ｙ（２）を含む目標物の予測領域の数は２つであり、ｙ（３）を含む目標物の予測領域の数は１つであって、ｙ（４）を含む目標物の予測領域の数は１つなので、予測ノード数は（２＋１）×（１＋１）×（１＋１）＝１２となる。
【００３８】
なお、５−２を見れば分かるように、実際にはノードの数は９個である。このように予測と実測で結果が相違するのは、図７は信頼度の高い所定の個数の組み合わせを除いた部分木を示すものであり、その過程で取り除かれたノードを考慮しないからである。しかしノード数の予測において、そこまで考慮してノードの数を算出しようすると、結果的に部分木のノードを探索することとなってしまい、予測に要するオーバヘッドが高くなりすぎる。したがって、そのような相違を無視することにし、単純な乗算のみで負荷を予測することとする。
【００３９】
以上のように各部分木の処理負荷を部分木の最上位を除いた各節に対応する観測点を含む目標物の予測領域の数＋１を乗じた数で見積もりこととしたので、少ないオーバヘッドでより正確に予測できる、という効果がある。
【００４０】
実施の形態４．
実施の形態１乃至実施の形態３では、タスク処理手段１−５ａ〜１−５ｄが探索処理を行う前に、負荷分散手段１−９が探索処理を行う前に部分木の負荷予測を行い、タスク処理手段１−５ａ〜５ｄに分配することとしたが、タスク処理手段１−５ａ〜１−５ｄが探索処理を行いながら、その負荷状況に応じて負荷分散手段１−９が部分木の探索処理を分配するようにしてもよい。
【００４１】
負荷分散手段１−９は、組み合わせ探索手段１−４から処理すべき部分木を取得すると、タスク処理手段１−５ａ〜１−５ｄに部分木を負荷量が均等になるように分配する。ここで、この負荷量は、実施の形態２及び実施の形態３で述べたように、部分木の数、各部分木の高さの合計値、各部分木の節に対応する観測点を含む目標物の予測領域の数＋１を乗じた値、に基づいて算出する方法が考えられる。負荷分散手段１−９が処理を分配すると、タスク処理手段１−５ａ〜１−５ｄは、分配された部分木の探索処理を１つずつ行う。
【００４２】
一方、負荷分散手段１−９は、転送線１−８ｃを介してタスク処理手段１−５ａ〜１−５ｄに負荷の報告要求を出す。これに対して、タスク処理手段１−５ａ〜１−５ｄはその要求に応えて負荷状況を負荷分散手段１−９に報告する。ここで、負荷状況は、各タスク処理手段がまだ処理していない部分木の負荷量の合計値とする。ここでの負荷量は、前述した負荷量と同じ意味であって、部分木の数、各部分木の高さの合計値、各部分木の節に対応する観測点を含む目標物の予測領域の数＋１を乗じた値などである。
【００４３】
次に、負荷分散手段１−９は、タスク処理手段１−５ａ〜１−５ｄからの負荷状況の報告を受け取ると、その情報を基に、タスク処理手段１−５ａ〜１−５ｄの負荷が均等になるように、タスク処理手段１−５ａ〜１−５ｄに対して、他のタスク処理手段に部分木の探索処理を移動するよう要求する。例えば、各タスク処理手段１−５ａ〜１−５ｄからの負荷状況の報告がそれぞれ３０，５０，４０，４０であったとする。これにより、全ての未処理の探索処理量は３０＋５０＋４０＋４０＝１６０なので、４つのタスク処理手段へ均等化した場合、各タスク処理手段の担当すべき負荷量は４０ずつとなる。そこで、負荷分散手段１−９は、転送線１−８ｃを介して、タスク処理手段１−５ｂに負荷量１０の探索処理をタスク処理手段１−５ａに移動するよう指示する。なお、タスク処理手段１−５ｂに負荷量が１０に等しい探索処理がない場合は、１０に最も近い探索処理をタスク処理手段１−５ａに移動する。これにより、タスク処理手段１−５ａ〜１−５ｄの未処理の探索処理量がおよそ４０ずつとなる。このように、負荷分散手段１−９とタスク処理手段１−５ａ〜１−５ｄは、負荷状況の収集とそれによる各タスク処理手段間の探索処理の移動を定期的に行なう。
【００４４】
上記より明らかなように、実施の形態４における並列多目標追尾装置によれば、各タスク処理手段の未処理の探索処理量が定期的に均等化されるので、部分木の探索処理以外の処理が各タスク処理手段と同一マシン上で行われていても、各タスク処理手段の全ての探索処理がほぼ同じ時間で終了し、最適な負荷分散となる、という効果を奏する。
【００４５】
実施の形態５．
実施の形態４では、負荷分散手段１−９が負荷分散のタイミングの主導権を取り、定期的に各タスク処理手段の負荷を均等化して、各タスク処理手段での探索処理をほぼ同じ時間で終了させるというものであるが、タスク処理手段が負荷分散のタイミングの主導権を取り、負荷分散手段へ処理の転送要求を行なうようにしてもよい。
【００４６】
すなわち、負荷分散手段１−９は、組み合わせ探索手段１−４から処理すべき部分木が渡されたら、タスク処理手段１−５ａ〜１−５ｄに部分木を最初に１つだけ順に分配し（その結果、４つの部分木が分配される）、分配できなかった残った５つ目以降の部分木を保持しておく。タスク処理手段１−５ａ〜１−５ｄは、それぞれの部分木の探索処理を終了すると処理結果を負荷分散手段１−９を介して組み合わせ探索手段１−４へ返すと共に、負荷分散手段１−９に次の処理、すなわち、別の部分木の探索処理の転送を要求する。負荷分散手段１−９は、その部分木の探索処理の転送要求を受け取ると、要求を出したタスク処理手段へ保持しておいた１つの部分木の探索処理を与える。以上を全ての部分木の探索処理がなくなるまで繰り返す。
【００４７】
上記より明らかなように、実施の形態５における並列多目標追尾装置によれば、各タスク処理手段が処理すべき処理がなくなり次第、次の処理の転送要求を負荷分散手段１−９へ出すので、部分木の探索処理以外の処理が各タスク処理手段と同一マシン上で行われていても、各タスク処理手段の全ての探索処理がほぼ同じ時間で終了し、最適な負荷分散となる、という効果を奏する。
【００４８】
また、負荷分散手段１−９による定期的な負荷状況の収集処理が必要ないので、負荷分散のオーバヘッドが抑制できるため、１つの部分木の探索処理に対応する処理量が小さい場合にも適用できる、という効果を奏する。
【００４９】
実施の形態６．
実施の形態５では、各タスク処理手段１−５ａ〜１−５ｄは１つの部分木の探索処理が完了してから次の部分木の探索処理の転送要求を負荷分散手段１−９に出す方法について述べたが、タスク処理手段に仕事をある程度確保しておき処理するようにしてもよい。
【００５０】
まず、負荷分散手段１−９は、組み合わせ探索手段１−４が生成した部分木の探索処理のうち、２以上の探索処理であって、所定の数の探索処理をタスク処理手段１−５ａ〜１−５ｄに分配する。また、負荷分散手段１−９は、ここで分配しきれなかった探索処理を保持しておく。タスク処理手段１−５ａ〜１−５ｄは、複数の部分木の探索処理を受け取ると、各部分木の探索処理を行なう。そして、探索処理を進めることによって、未処理の部分木の数が減少し、一定数に達した場合に、負荷分散手段１−９に次の部分木の探索処理の転送を要求する。
【００５１】
負荷分散手段１−９は、部分木の探索処理の転送要求を受け取ると、保持しておいた残りの部分木から、要求を出したタスク処理手段へ複数の部分木の探索処理を分配する。また、要求を出したタスク処理手段は、負荷分散手段１−９からの部分木の探索処理を受け取ると、それを保持する。以上を全ての部分木がなくなるまで繰り返す。
【００５２】
上記より明らかなように、実施の形態６における並列多目標追尾装置によれば、タスク処理手段１−５ａ〜１−５ｄは、処理が少なくなると新たな処理の転送要求を負荷分散手段１−９へ出すと共に、新たな処理が到着するまでの間も残っている部分木の探索処理を続行するので、計算機資源を有効に活用でき、最適な負荷分散となる、という効果がある。
【００５３】
実施の形態７．
実施の形態１乃至実施の形態６では、負荷分散の単位を一定としているが、負荷分散の単位を時間と共に小さくするようにしてもよい。一般に、負荷分散の単位のサイズが小さいほど、負荷を分散する回数が増えるため、負荷分散のためのオーバヘッドが大きくなる。一方、負荷分散の単位のサイズが小さいほど、負荷調整が小さな単位で行うようになるので、各タスク処理手段で処理負荷を均一化するという観点からは好ましい。
【００５４】
そこで、これら２つの要求を満たすために、最初は負荷分散の単位のサイズを大きくとり、処理が進むにつれて、そのサイズを小さくすることとする。ここで、実施の形態７における負荷分散の単位は複数の部分木であるが、その処理量は、これまでにも述べたように、部分木の数や各部分木の高さで測ることができる。そこで負荷分散手段１−９は、処理量の大きい部分木からタスク処理手段１−５ａ〜１−５ｄに分配するようにする。こうすることで、処理が進むにつれて次第に処理量の小さい部分木に処理が移行していくようになる。
【００５５】
上記より明らかなように、実施の形態７における並列多目標追尾装置によれば、負荷分散オーバヘッドを抑えた上で、各タスク処理手段の部分木の探索処理の終了に要する時間を均一化することができるという効果を奏する。
【００５６】
実施の形態８．
実施の形態１乃至実施の形態７では、各タスク処理手段１−５ａ〜１−５ｄと負荷分散手段１−９とでは異なるプロセッサにより構成されるが、複数のタスク処理手段の内の１つを負荷分散手段１−９と同一のプロセッサで動作させるようにしてもよい。タスク処理手段１−５ａ〜１−５ｄにおける部分木の探索処理の負荷と、負荷分散手段１−９における組み合わせ分配処理の負荷を比較すると、タスク処理手段１−５ａ〜１−５ｄの負荷の方が圧倒的に高い。したがって、負荷分散手段１−９を独立したプロセッサで構成したとすると、このプロセッサは負荷という観点から余裕があることになる。したがって、負荷分散手段１−９をタスク処理手段の１つと同一プロセッサで動作させることにより、全てのプロセッサの資源を有効に活用して、無駄のない並列処理が可能となる。
【００５７】
【発明の効果】
本発明に係る並列他目標追尾装置は、観測点と目標物の組み合わせを並列処理の単位として負荷分散することとしたので、計算機資源の有効活用を行うとともに、並列処理による高速化を達成できるという効果を奏する。
【図面の簡単な説明】
【図１】実施の形態１乃至実施の形態８における並列他目標追尾装置の構成図である。
【図２】実施の形態１乃至実施の形態８における目標物と観測点の関係を示す関係図である。
【図３】実施の形態１における目標物と観測点の組み合わせを関連を示す関連図である。
【図４】実施の形態１における組み合わせ探索処理を示すフローチャートである。
【図５】実施の形態１における目標物と観測点の組み合わせの樹形図である。
【図６】実施の形態１における目標物と観測点の部分的な組み合わせを含む樹形図である。
【図７】実施の形態１における目標物と観測点の部分的な組み合わせを含む樹形図である。
【符号の説明】
１−１：入力線
１−２：予測領域生成手段
１−３：クラスタ生成手段
１−４：組み合わせ探索手段
１−５ａ〜１−５ｄ：タスク処理手段
１−６：目標物航跡更新手段
１−７：出力線
１−８ａ〜１−８ｅ：転送線
１−９：負荷分散手段
【図１】
2004219299.tif 000003
【図２】
2004219299.tif 000004
【図３】
2004219299.tif 000005
【図４】
2004219299.tif 000006
【図５】
2004219299.tif 000007
【図６】
2004219299.tif 000008
【図７】
2004219299.tif 000009