航跡割当装置
【課題】多スタート局所探索においてＭＦＡ問題の最適解探索を精度良く効率的に行うことのできる航跡割当装置を得る。
【解決手段】観測値情報取得部１と、観測値情報格納部２と、航跡候補生成部３と、航跡候補格納部４と、初期解生成部５と、最良解格納部６と、新規解生成部７と、新規解格納部８と、最良解更新部９と、ビルディングブロック候補情報格納部１０と、ビルディングブロック判定部１１と、ビルディングブロック情報格納部１２と、終了判定部１３と、探索結果出力部１４とを備えている。新規解生成部７は、ビルディングブロックと判定された構成要素が必ず含まれるように新規解を生成する。最良解更新部９は、多スタート局所探索時にＫ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定して登録する。
【解決手段】観測値情報取得部１と、観測値情報格納部２と、航跡候補生成部３と、航跡候補格納部４と、初期解生成部５と、最良解格納部６と、新規解生成部７と、新規解格納部８と、最良解更新部９と、ビルディングブロック候補情報格納部１０と、ビルディングブロック判定部１１と、ビルディングブロック情報格納部１２と、終了判定部１３と、探索結果出力部１４とを備えている。新規解生成部７は、ビルディングブロックと判定された構成要素が必ず含まれるように新規解を生成する。最良解更新部９は、多スタート局所探索時にＫ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定して登録する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、レーダなどの観測センサにより得られる時間的に連続した複数フレームの観測値を用いて、観測された複数の移動体の航跡を求める航跡割当装置に関するものである。
【背景技術】
【０００２】
従来から、レーダなどの観測センサにより得られた観測値（位置座標や信号強度などの情報が含まれる）を用いて複数の移動体の航跡を推定する航跡追尾処理はよく知られており、航跡追尾処理を構成する処理の１つとして航跡割当処理がある。一般に、観測センサの観測単位をフレームと呼び、１フレーム内には複数の観測値が含まれる。
【０００３】
航跡割当処理においては、航跡の尤度（航跡の尤もらしさを表す指標）が最も高くなるように、それまでに得られている航跡に対して、新たに観測されたフレーム内の観測値を割り当てる処理が行われる。
従来の航跡割当装置としては、最新の１個のフレーム内の観測値の割当処理を行うＭＨＴ（Ｍｕｌｔｉｐｌｅ Ｈｙｐｏｔｈｅｓｉｓ Ｔｒａｃｋｉｎｇ）法を適用した目標追尾装置が提案されている（たとえば、特許文献１参照）。
【０００４】
また、ＭＨＴ法のように１個のフレームの割当処理から求められる航跡では、十分な航跡追尾の精度が得られないことから、さらに高い精度を得るために、連続する複数フレームの航跡割当処理を行うＭＦＡ（Ｍｕｌｔｉｐｌｅ Ｆｒａｍｅ Ａｓｓｉｇｎｍｅｎｔ）問題を解くアルゴリズムも提案されている。
【０００５】
ＭＦＡ問題は、組合せ最適化問題の１つであり、フレーム数やフレーム内の観測値数が増加すると、組合せ数が爆発的に増加してしまうので、厳密解法による最適解の導出においては、長時間を要し実用面で問題が生じる。
そこで、運用に支障をきたさなければ、最適解でなくても差し支えないという観点に立ち、ＭＦＡ問題を高速に解くアルゴリズムとして、ラグランジュ緩和法を適用した手法が提案されている（たとえば、非特許文献１参照）。
【０００６】
ＭＦＡ問題にラグランジュ緩和法を適用する場合には、Ｎ次元（次元数＝フレーム数）の問題を２次元に変換することで探索範囲の絞込みが行われるが、次元数が増えるほど、処理が煩雑になるうえ実装も難しくなり、効果的な絞込みを実現することができない可能性がある。
【０００７】
一方、ラグランジュ緩和法よりも処理が単純で実装が容易であり、且つ、ＭＦＡ問題を高速に解くことが期待できるアルゴリズムとして、組合せ最適化メタヒューリスティックス手法が存在する。
組合せ最適化メタヒューリスティックス手法の代表的なアルゴリズムとしては、遺伝的アルゴリズム、タブーサーチ、シミュレーテッドアニーリング、多スタート局所探索などが挙げられる。
【０００８】
多スタート局所探索は、異なる初期解を複数用意して、複数の近傍探索を同時に実行する探索処理であり、単純な処理ながら探索効率を上げることが可能である。
この種のメタヒューリスティックス手法の特徴は、それまでの探索で得られた最良解の一部を変更して新規解を生成し、新規解の元となった最良解よりも評価値の良い新規解が存在した場合には、その新規解を最良解と置き換えることを繰り返し実行し、最適解を探索することにある。
【０００９】
しかしながら、最良解から新規解を生成する処理において、最良解中に、最適解を構成する要素（以下、「ビルディングブロック」という）が含まれていた場合に、そのビルディングブロックが変更されてしまうことから、新規解の中にビルディングブロックが残らず、最適解または準最適解が求まるまでの探索回数の増加を招く場合や、最適解または準最適解が求まらない場合が生じるという問題がある。
【００１０】
なお、「最良解」とは、現時点までの探索で得られている最も良い解を意味し、「最適解」とは、全ての組合せの中で最も適した解を意味し、「準最適解」とは、最適解に近い運用に支障を及ぼさない解を意味している。
【００１１】
以下、図１４の説明図を参照しながら、従来の航跡割当処理における具体例を挙げて、上記問題点について説明する。
図１４においては、第ｎ世代の最良解と、最良解の組み合わせを変更した新規解と、更新後（第ｎ＋１世代）の最適解との関係が示されている。
【００１２】
図１４において、ｎ回目の更新後に得られた「最良解（第ｎ世代）」は、４個の航跡を表しており、横一行｛１、１、１、２｝、｛２、２、２、３｝、｛３、４、４、４｝、｛４、３、３、１｝は、それぞれ１個の航跡であり、各航跡内の「１」〜「４」の数字は、観測値に振られた番号である。
【００１３】
また、「最良解（第ｎ世代）」の縦一列｛１、２、３、４｝、｛１、２、４、３｝｛１、２、４、３｝｛２、３、４、１｝は、同一フレーム内の観測値である。
したがって、「最良解（第ｎ世代）」は、各フレームの観測値｛１、１、１、２｝を結んだ航跡と、観測値｛２、２、２、３｝を結んだ航跡と、観測値｛３、４、４、４｝を結んだ航跡と、観測値｛４、３、３、１｝を結んだ航跡から構成されている。
【００１４】
このとき、航跡｛２、２、２、３｝が「ビルディングブロック」であったと仮定し、新規解の生成処理において、航跡｛２、２、２、３｝と航跡｛４、３、３、１｝とが変更対処として選ばれ、それぞれの同じ位置の観測値（灰色ブロック参照）を入れ替えた４個の新規解を生成したと仮定する。
こうして得られた４個の新規解（図１４の破線枠内の４個の解）においては、「ビルディングブロック」が壊されていることが分かる。
【００１５】
これら４個の新規解のうち、たとえば左から２番目の解が「最良解（第ｎ世代）」よりも良い評価値であった場合には、最良解更新時に、「最良解（第ｎ＋１世代）」の解として、左から２番目の新規解が選ばれ（破線矢印参照）、最良解（第ｎ＋１世代）からビルディングブロックである航跡｛２、２、２、３｝が消えてしまう。
ビルディングブロックは最適解の構成要素であり、探索途中の最良解の構成要素がビルディングブロックであるか否かは判定することができないことから、このような問題が発生する。
【００１６】
【特許文献１】特許第３１４５８９３号公報
【非特許文献１】Ａｕｂｒｅｙ Ｂ．Ｐｏｏｒｅ、「Ａ Ｎｅｗ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ｄａｔａ Ａｓｓｏｃｉａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｍｕｌｔｉｓｅｎｓｏｒ−Ｍｕｌｔｉｔａｒｇｅｔ Ｔｒａｃｋｉｎｇ」、Ｐｒｏｃ． ｏｆ ＳＰＩＥ Ｖｏｌ．２５６１、１９９５
【発明の開示】
【発明が解決しようとする課題】
【００１７】
従来の航跡割当装置では、ＭＦＡ問題を高速に解くためのメタヒューリスティックス手法として多スタート局所探索を適用した場合に、最良解から新規解を生成する処理において、最適解を構成する「ビルディングブロック」が変更されてしまうので、新規解の中にビルディングブロックが残らず、最適解または準最適解が求まるまでの探索回数の増加を招く場合や、最適解または準最適解が求められない場合が生じるという課題があった。
【００１８】
この発明は、上記のような課題を解決するためになされたものであり、多スタート局所探索において各探索を連携させ、各探索における最良解を構成する要素の中でビルディングブロックである可能性が高いと判定したものを次の世代の最良解に必ず残すことにより、ＭＦＡ問題の最適解探索を精度良く効率的に行うことのできる航跡割当装置を得ることを目的とする。
【課題を解決するための手段】
【００１９】
この発明による航跡割当装置は、観測センサにより観測される時間的に連続した観測値情報を用いて複数の移動体の航跡を追尾するために、観測値情報の各々を複数の移動体の各航跡に割り当てる航跡割当装置であって、観測センサを用いて観測値情報を取得する観測値情報取得部と、観測値情報取得部が取得した観測値情報を格納する観測値情報格納部と、観測値情報格納部に格納された各時刻の観測値情報を組合せて、複数の移動体の各々が取り得る航跡の候補を航跡候補として生成する航跡候補生成部と、航跡候補を格納する航跡候補格納部と、航跡候補格納部に格納された航跡候補の集合から最も評価値の良い航跡候補の組合せを最適解として探索する際に、最適解探索の開始時の航跡候補の組合せを初期解として生成する初期解生成部と、初期解を格納するとともに、最適解探索の途中で得られた解の中で最も良い解を最良解として格納する最良解格納部と、最良解格納部に格納された最良解の一部分を変更し、新たな解を新規解として生成する新規解生成部と、新規解を格納する新規解格納部と、新規解格納部に格納された新規解と最良解格納部に格納された最良解とを比較して、最良解よりも評価値が良い新規解が存在する場合に、当該新規解を新たな最良解として最良解格納部に格納する最良解更新部と、最良解の構成要素となる航跡候補が最適解の構成要素となり得るか否かを判定し、最適解の構成要素となり得ると判定された最良解の構成要素をビルディングブロックと判定するビルディングブロック判定部と、ビルディングブロックの候補となる構成要素に関するビルディングブロック候補情報を格納するビルディングブロック候補情報格納部と、ビルディングブロックと判定された構成要素に関するビルディングブロック情報を格納するビルディングブロック情報格納部と、最適解探索を終了するかまたは継続するかを判定する終了判定部と、最適解探索を終了すると判定された場合に、最終的に得られた最良解を出力する探索結果出力部とを備え、新規解生成部は、ビルディングブロック情報に基づいて、ビルディングブロックと判定された構成要素が必ず含まれるように新規解を生成し、最良解更新部は、スタート数がＫ個の初期解を用いた（すなわち、最適解探索の実行中にＫ個の最良解が存在する）多スタート局所探索時に、Ｋ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定し、当該ビルディングブロック候補情報をビルディングブロック候補情報格納部に登録し、ビルディングブロック判定部は、最良解更新部による１回の最良解更新で世代が１つ進む条件下で、同一構成要素がＮ世代にわたって連続してビルディングブロック候補と判定された場合に、当該構成要素をビルディングブロックと判定し、当該ビルディングブロック情報をビルディングブロック情報格納部に登録するものである。
【発明の効果】
【００２０】
この発明によれば、多スタート局所探索における最良解を構成する要素の中で、ビルディングブロックである可能性が高いと判定したものを次の世代の最良解に必ず残すことができるので、ＭＦＡ問題の最適解探索を精度良く効率的に行うことができる。
【発明を実施するための最良の形態】
【００２１】
実施の形態１．
以下、図面を参照しながら、この発明を実施するための最良の形態について説明する。
図１はこの発明の実施の形態１に係る航跡割当装置の機能構成を示すブロック図であり、各ブロックを結ぶ実線矢印は、処理の流れを示し、破線矢印は、データの流れを示している。
【００２２】
図１において、航跡割当装置は、観測値情報取得部１と、観測値情報格納部２と、航跡候補生成部３と、航跡候補格納部４と、初期解生成部５と、最良解格納部６と、新規解生成部７と、新規解格納部８と、最良解更新部９と、ビルディングブロック候補情報格納部１０と、ビルディングブロック判定部１１と、ビルディングブロック情報格納部１２と、終了判定部１３と、探索結果出力部１４とを備えている。
【００２３】
観測値情報取得部１は、レーダなど（図示せず）の観測センサにより観測された移動体の観測値データ（観測値情報）を取得し、観測値情報格納部２は、観測値情報取得部１で取得された移動体の観測値情報を格納する。
【００２４】
航跡候補生成部３は、観測値情報格納部２に格納されている観測値情報に基づいて、観測値を組合せた航跡候補を生成するとともに、各航跡候補の評価値を計算する。航跡候補格納部４は、航跡候補生成部３により生成された航跡候補およびその評価値を格納する。
【００２５】
初期解生成部５は、航跡候補格納部４に格納されている航跡候補およびその評価値を用いて、ＭＦＡ問題の最適解探索を行うための初期解を生成する。
最良解格納部６は、繰り返し実行される最適解探索において、最新の最も評価値の良い解を最良解として格納する。なお、初期解生成部５で生成された初期解は、最初に得られた最良解として最良解格納部６に格納される。
【００２６】
新規解生成部７は、ビルディングブロック情報格納部１２に格納されているビルディングブロック情報に基づき、ビルディングブロックが残るように、最良解格納部６に格納されている最良解の一部を変更して新規解を生成する。新規解格納部８は、新規解生成部７で生成された新規解を格納する。
【００２７】
最良解更新部９は、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解とを比較して、最良解よりも評価値の良い新規解が存在する場合には、当該新規解を新たな最良解として最良解格納部６に格納する。また、最良解更新部９は、最良解の更新後に、新たな最良解を構成する要素がビルディングブロックの候補となるか否かを判定する。
【００２８】
ビルディングブロック候補情報格納部１０は、最良解更新部９がビルディングブロック候補と判定した最良解の構成要素に関するビルディングブロック候補情報を格納する。
ビルディングブロック判定部１１は、ビルディングブロック候補情報格納部１０に格納された情報に基づいて、最良解を構成する要素がビルディングブロックとなり得るか否か判定する。
【００２９】
ビルディングブロック情報格納部１２は、ビルディングブロック判定部１１がビルディングブロックと判定した、最良解を構成する要素に関するビルディングブロック情報を格納する。
終了判定部１３は、最適解探索の処理終了判定を行い、探索処理終了と判定された場合には探索結果出力部１４に処理を移し、終了しないと判定された場合には新規解生成部７に処理を戻す。
探索結果出力部１４は、最適解探索に応じて得られた最良解を探索結果として出力する。
【００３０】
次に、図２〜図８の説明図を参照しながら、図１に示した航跡割当装置による一連の動作について説明する。
まず、観測値情報取得部１は、たとえばレーダにより観測された移動体の最新の１フレーム分の観測値情報を取得し、観測値情報格納部２は、取得した観測値を、時間的に連続した複数フレーム分にわたって格納する。
【００３１】
図２は観測値情報取得部１により取得される観測値を図式的に示しており、時系列的な観測値をＸ−Ｙ平面上に配置した例を示している。
ここでは、時刻ｔ、時刻ｔ＋１、時刻ｔ＋２、時刻ｔ＋３（４個のフレームｔ〜フレームｔ＋３に対応）における４個の観測値が示されている。
【００３２】
図２において、同一フレーム内の観測値は、それぞれ破線枠で囲まれており、各フレーム内の丸で囲まれた数字は、それぞれ観測値を表している。なお、観測値の数値「１」〜「４」は、単にフレーム内で割り当てた連番であり、数値そのものに特に意味はない。
【００３３】
たとえば、図２に示した状況において、観測値情報収集部１は、最新のフレームｔ＋３の観測値を取得して観測値情報格納部２に格納し、このとき、観測値情報格納部２は、最新のＦフレーム分（Ｆ＝４）の観測値情報を格納することになる。
【００３４】
図３は観測値情報格納部２における観測値情報の格納状態を図式的に示しており、Ｆフレーム分（Ｆ＝４）の場合を示している。
図３において、観測値情報格納部２には、４フレーム分（フレームｔ〜フレームｔ＋３）の観測値情報が格納されており、最新のフレームがｔ＋３である。また、丸で囲まれた数字は、前述（図２）と同様の観測値を表している。
【００３５】
観測値情報格納部２への観測値情報の格納処理に続いて、次に、航跡候補生成部３は、観測値情報格納部２に格納されている観測値情報に基づいて航跡候補を生成し、航跡候補格納部４は、生成された航跡候補を格納する。
【００３６】
図４は航跡候補生成部３による処理動作を示している。
図４において、観測値情報格納部２には、４フレーム分の観測値情報（１点鎖線枠内）が格納されており、縦一列が１フレーム分の観測値である。
各観測値は、図３と同様に、左から観測時刻（ｔ、ｔ＋１、ｔ＋２、ｔ＋３）順に並んでいる。
【００３７】
航跡候補生成部３は、観測値情報格納部２内の観測値情報から航跡候補を生成する。
航跡候補とは、ＭＦＡの解を構成する航跡となり得るものであり、各フレームから１個ずつ観測値を選択して観測順に並べることにより、図４内の航跡候補集合（１点鎖線枠内）のように生成される。
【００３８】
たとえば、航跡候補集合中の最上段の航跡候補｛１、１、１、１｝は、フレームｔの観測値「１」、フレームｔ＋１の観測値「１」、フレームｔ＋２の観測値「１」、フレームｔ＋３の観測値「１」を繋いだ航跡候補である。
【００３９】
図４の例では、航跡候補｛１、１、１、１｝〜｛４、４、４、４｝は、４４（＝２５６通り）だけ生成される。また、航跡候補生成部３は、生成した各航跡候補に対する評価値として、航跡コスト（−１５．４、−２．２、・・・、−１０．７）も併せて求める。
以下、航跡候補格納部４は、航跡候補生成部３で生成された航跡候補およびその評価値（図４）のデータを格納する。
【００４０】
続いて、初期解生成部５は、航跡候補格納部４に格納されている航跡候補の集合の中から、同一フレーム内での観測値の重複がないように、且つ、全ての観測値が含まれるように、最適解探索の初期解を生成する。このとき生成される初期解の数は、適用される最適解探索のアルゴリズムに依存し、たとえば、多スタート局所探索を適用する場合には、スタート数が「Ｋ」であれば、Ｋ個の異なる初期解を生成する。
【００４１】
図５は初期解生成部５における初期解生成動作を示しており、３個の初期解を生成する例を示している。
図５において、初期解生成部５は、以下の手順（１）〜（３）を３回繰り返すことにより、３個の初期解を生成する。
【００４２】
（１）まず、航跡候補格納部４に格納されている航跡候補の集合から１個の航跡候補を選択する。このときの選択の基準としては、ランダムに基づくもの、評価値が最も良いもの、評価値に比例した選択確率に基づくもの、などが挙げられる。
ここでは、たとえば、図５の最上段に示す航跡候補｛１、２、３、４｝を選択する。
【００４３】
（２）次に、選択済みの航跡候補との間で、同一フレーム内で観測値が重複しないように、航跡候補の集合から新たに航跡候補を選択する。このときの選択の基準は上記（１）と同じである。
ここでは、（１）において、航跡候補｛１、２、３、４｝が選択されているので、図５の２段目に示すように、（１）の航跡候補との間で同一フレーム内の観測値が重複しない航跡候補｛２、３、４、１｝を選択する。
【００４４】
（３）同様にして、選択済みの全ての航跡候補と観測値の重複が起きないように、且つ、全ての観測値が初期解に含まれるように、航跡候補の集合から順次に航跡候補｛３、４、１、２｝、｛４、１、２、３｝を選択する。
これにより、図５に示すように、上記４通りの航跡候補からなる１個の「初期解−１」が生成される。
【００４５】
以下、上記（１）〜（３）と同様の処理により、「初期解−２」を生成する。ただし、「初期解−２」は、「初期解−１」とは異なっていなければならない。
同様にして、「初期解−１」および「初期解−２」とは異なる「初期解−３」を生成する。
初期解生成部５で生成された３個の初期解「初期解−１」〜「初期解−３」は、最初に得られた最良解と見なせるので、最良解格納部６に格納される。
【００４６】
効率的な最適解探索を行うためには、初期解が重要であり、この発明では、ＧＲＡＳＰ（Ｇｒｅｅｄｙ Ｒａｎｄｏｍｉｚｅｄ Ａｄａｐｔｉｖｅ Ｓｅａｒｃｈ Ｐｒｏｃｅｄｕｒｅ）という手法の初期解生成法を利用することとする。
なお、ＧＲＡＳＰ法による初期解生成の手順は、公知なので、ここでは割愛する。
【００４７】
次に、新規解生成部７は、最良解格納部６に格納されている最良解の一部を変更した新規解を生成し、新規解格納部８は、生成された新規解を格納する。
新規解生成部７は、新規解生成時において、ビルディングブロック情報格納部１２に格納されている情報に基づいて、最良解中に含まれるビルディングブロックと判定された構成要素を新規解に残すように解を生成する。
【００４８】
ビルディングブロックの判定処理に関しては、ビルディングブロック判定部１１の動作説明（後述する）で具体例を述べる。
新規解格納部８に新規解が格納されると、最良解更新部９は、最良解格納部６に格納されている最良解と新規解格納部８に格納されている新規解とを比較し、最良解よりも評価値の良い新規解が存在する場合には、最も評価値の良い新規解を「新たな最良解」とし、最良解格納部６に新たな最良解を格納する。
【００４９】
もし、第ｎ世代の最良解よりも評価値が良い新規解が生成されなかった場合には、最良解更新部９は、新規解生成部７に処理を戻す。これにより、新規解生成部７は、新規解の生成処理を再度実行する。
この発明の実施の形態１に係る航跡割当装置においては、新規解生成部７による新規解生成処理と、最良解更新部９による最良解更新処理と、を繰り返し実行することにより、最適解探索が行われる。
【００５０】
図６は新規解生成部７および最良解更新部９の動作を示しており、第ｎ世代から第ｎ＋１世代への新規解生成および最良解更新の例を示している。
ここでは、新規解生成処理と最良解更新処理との１サイクル分を「世代」と呼ぶことにする。
【００５１】
図６において、新規解生成部７は、最良解格納部６に格納されている第ｎ世代の最良解を取得し、新規解を生成するために観測値の入れ替えを行うための２個の構成要素を選択する（以下、この選択を「ペア選択」という）。
【００５２】
このとき、ビルディングブロック情報格納部１２に格納されているビルディングブロック情報に第ｎ世代の最良解の構成要素｛２、２、２、３｝が含まれていたとすると、新規解生成部７は、構成要素｛２、２、２、３｝をペア選択対象から除外し、図６に示すように、たとえば構成要素｛１、１、１、２｝および｛４、３、３、１｝をペア選択する。
【００５３】
なお、ペア選択の基準は、ここでは特に定めないが、たとえば、各構成要素の評価値の悪い順に２個選択するか、または、各構成要素の評価値に比例した選択確率を与えて選択する方法が考えられる。
【００５４】
新規解生成部７は、選択した構成要素｛１、１、１、２｝と｛４、３、３、１｝の同じ位置の観測値（すなわち、同一フレーム内の観測値）を入れ替えて新規解を生成する。
図６においては、４個の新規解（２点鎖線枠内）が生成される。すなわち、右端の観測値「２」、「１」を入れ替えた「新規解−１」と、右から２番目の観測値「１」、「３」を入れ替えた「新規解−２」と、左から２番目の観測値「１」、「３」を入れ替えた「新規解−３」と、左端の観測値「１」、「４」を入れ替えた「新規解−４」とが生成される。
【００５５】
また、新規解生成部７は、各新規解の評価値を計算し、新規解格納部８は、生成された新規解およびその評価値を格納する。
新規解生成部７における新規解生成処理が完了すると、最良解更新部９は、最良解格納部６に格納されている第ｎ世代の最良解の評価値と、新規解格納部８に格納されている「新規解−１」〜「新規解−４」の評価値とを比較し、最良解よりも評価値の良い新規解が存在する場合には、最も評価値の良い新規解を第ｎ＋１世代の最良解として決定する。
【００５６】
図６においては、第ｎ世代の最良解と４個の新規解とを合わせた中で、「新規解−２」が最も評価値が良かったことから、最良解更新部９は、「新規解−２」を第ｎ＋１世代の最良解として決定した場合を示している。
【００５７】
次に、最良解更新部９は、スタート数がＫ個の多スタート局所探索において、各探索の第ｎ＋１世代のＫ個の最良解の中に、同じ構成要素がＬ（≦Ｋ）個以上含まれれば、その構成要素をビルディングブロック候補と判定する。
【００５８】
図７は最良解更新部９によるビルディングブロック候補の判定処理例を示しており、Ｋ＝３、Ｌ＝２とした場合の例を示している。
この場合、スタート数が「３」の多スタート局所探索が行われているので、異なる３通りの探索処理が実行されており、最良解格納部６には、それぞれの探索における最良解が格納されている。
【００５９】
図７において、第ｎ＋１世代の３個の最良解のそれぞれには、構成要素｛２、２、２、３｝が含まれており、構成要素｛２、２、２、３｝は、「Ｋ（＝３）個のスタート数のうち、Ｌ（＝２）個以上の最良解に含まれている」という条件を満たしているので、最良解更新部９は、構成要素｛２、２、２、３｝を「ビルディングブロック候補」と判定する。
ビルディングブロック候補と判定された構成要素｛２、２、２、３｝に関する情報は、ビルディングブロック候補情報格納部１０に格納される。
【００６０】
最良解更新部９による更新処理が完了すると、ビルディングブロック判定部１１は、ビルディングブロック候補情報格納部１０に格納された情報から、「連続Ｎ世代、Ｋスタート中のＬ個以上の最良解に含まれるビルディングブロック候補」を、「ビルディングブロック」と判定する。
【００６１】
図８はビルディングブロック判定部１１の判定処理を示しており、上記条件数Ｎ、Ｋ、Ｌが、Ｎ＝４、Ｋ＝３、Ｌ＝２の場合を示している。
図８において、構成要素｛２、２、２、３｝は、第ｎ−２世代から第ｎ＋１世代までのＮ（＝４）世代にわたって連続して、「Ｋ（＝３）スタート中Ｌ（＝２）個以上の最良解に含まれている」という条件を満たしているので、ビルディングブロック判定部１１は、構成要素｛２、２、２、３｝を「ビルディングブロック」と判定する。
ビルディングブロックと判定された構成要素に関する情報は、ビルディングブロック情報格納部１２に格納される。
【００６２】
最後に、終了判定部１３は、最適解探索の処理を継続するか否（終了する）かを判定し、継続する場合には新規解生成部７に処理を戻し、終了する場合には探索結果出力部１４に処理を進める。
【００６３】
終了判定部１３による終了判定基準は、以下の通りである。
すなわち、「探索終了」の判定条件は、世代数が上限値に達するか、新規解生成部７が生成する全ての新規解に対して最良解更新部９が最良解の更新処理を実行できなかった場合であり、「探索継続」の条件は、上記「探索終了」の条件を満たさない場合である。
【００６４】
最適解探索を終了する場合には、探索結果出力部１４は、探索終了時点において最良解格納部６に格納されている最良解の中で最も評価値の良いものを、探索結果として出力する。
【００６５】
以上のように、この発明の実施の形態１に係る航跡割当装置（図１〜図８）は、観測センサにより観測される時間的に連続した観測値情報を用いて複数の移動体の航跡を追尾するために、観測値情報の各々を複数の移動体の各航跡に割り当てる航跡割当装置であって、観測センサを用いて観測値情報を取得する観測値情報取得部１と、観測値情報取得部１が取得した観測値情報を格納する観測値情報格納部２と、航跡候補を生成する航跡候補生成部３と、航跡候補を格納する航跡候補格納部４と、最適解探索の開始時の初期解を生成する初期解生成部５と、初期解および最適解探索の途中で得られた解の中で最も良い解を最良解として格納する最良解格納部６と、最良解格納部６に格納された最良解の一部分を変更して新規解を生成する新規解生成部７と、新規解を格納する新規解格納部８と、新たな最良解を最良解格納部６に格納する最良解更新部９とを備えている。
【００６６】
また、航跡割当装置は、最良解の構成要素をビルディングブロックと判定するビルディングブロック判定部１１と、ビルディングブロックの候補となる構成要素に関するビルディングブロック候補情報を格納するビルディングブロック候補情報格納部１０と、ビルディングブロックと判定された構成要素に関するビルディングブロック情報を格納するビルディングブロック情報格納部１２と、最適解探索を終了するかまたは継続するかを判定する終了判定部１３と、最適解探索を終了すると判定された場合に最終的に得られた最良解を出力する探索結果出力部１４とを備えている。
【００６７】
航跡候補生成部３は、観測値情報格納部２に格納された各時刻の観測値情報を組合せて、複数の移動体の各々が取り得る航跡の候補を航跡候補として生成する。
初期解生成部５は、航跡候補格納部４に格納された航跡候補の集合から最も評価値の良い航跡候補の組合せを最適解として探索する際に、最適解探索の開始時の航跡候補の組合せを初期解として生成する。
【００６８】
新規解生成部７は、ビルディングブロック情報に基づいて、ビルディングブロックと判定された構成要素が必ず含まれるように新規解を生成する。
最良解更新部９は、新規解格納部８に格納された新規解と最良解格納部６に格納された最良解とを比較して、最良解よりも評価値が良い新規解が存在する場合に、当該新規解を新たな最良解として最良解格納部６に格納する。
【００６９】
また、最良解更新部９は、スタート数がＫ個の初期解を用いた（すなわち、最適解探索の実行中にＫ個の最良解が存在する）多スタート局所探索時に、Ｋ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定し、当該ビルディングブロック候補情報をビルディングブロック候補情報格納部１０に登録する。
【００７０】
ビルディングブロック判定部１１は、最良解の構成要素となる航跡候補が最適解の構成要素となり得るか否かを判定し、最適解の構成要素となり得ると判定された最良解の構成要素をビルディングブロックと判定する。
また、ビルディングブロック判定部１１は、最良解更新部による１回の最良解更新で世代が１つ進む条件下で、同一構成要素がＮ世代にわたって連続してビルディングブロック候補と判定された場合に、当該構成要素をビルディングブロックと判定し、当該ビルディングブロック情報をビルディングブロック情報格納部１０に登録する。
【００７１】
この発明の実施の形態１に係る航跡割当装置においては、多スタート局所探索における個々の探索を連携させ、一定世代数にわたって連続して、それぞれの探索で得られる最良解に共通して含まれる構成要素が存在する場合には、その構成要素を、最良解に含まれる構成要素であるビルディングブロックと判定し、以降の新規解生成時にビルディングブロックを必ず解の中に残すようにしている。
すなわち、多スタート局所探索における最良解を構成する要素の中で、ビルディングブロックである可能性が高いと判定したものを次の世代の最良解に必ず残すことができる。
【００７２】
これにより、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されることを回避することができるので、最良解が最適解から遠ざかること、最適解を求めるまでの更新世代数の増加、局所解に陥ること、といった不具合の発生を抑制することができる。
【００７３】
したがって、最終的に得られる解の評価値の良さを表す探索精度を向上させるとともに、探索終了までの更新世代数の少なさに対応する探索速度を向上させることができ、ＭＦＡ問題の最適解探索を精度良く効率的に行うことができる。
【００７４】
実施の形態２．
なお、上記実施の形態１（図１）では、ビルディングブロック判定部１１が多スタート局所探索の各探索で得られた最良解を連携させ「連続Ｎ世代、Ｋスタート中Ｌ個以上の最良解に含まれるビルディングブロック候補」をビルディングブロックと判定したが、ビルディングブロック判定部が各探索の連携を行わずに、各探索に関して独立にビルディングブロック判定を行うように構成してもよい。
【００７５】
図９は独立にビルディングブロックを判定するように構成したこの発明の実施の形態２に係る航跡割当装置の機能構成を示すブロック図であり、前述（図１参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
ここでは、図１とは一部機能が異なる新規解生成部７Ａ、最良解更新部９Ａ、ビルディングブロック候補情報格納部１０Ａおよびビルディングブロック判定部１１Ａのみの動作について説明する。
【００７６】
図９において、新規解生成部７Ａは、最良解格納部６に格納されている最良解の構成要素から新規解生成のためのペア選択を行う。
このペア選択において、新規解生成部７Ａは、まず、ビルディングブロック情報格納部１２に格納されているビルディングブロック情報を参照し、ビルディングブロックである構成要素をペア選択対象外とする。
【００７７】
次に、新規解生成部７Ａは、１個の構成要素を主構成要素として選択し、続いて、別の１個の構成要素を副構成要素として選択する。
このとき、新規解生成部７Ａは、ビルディングブロック候補情報格納部１０Ａに格納されているビルディングブロック候補に関する情報を参照し、最良解の構成要素の中にビルディングブロック候補が存在する場合には、ビルディングブロック候補である構成要素を優先的に主構成要素として選択する。
【００７８】
ここで、ビルディングブロック候補情報には、ビルディングブロック候補に選ばれた回数を示すビルディングブロック候補カウンタ（以下、「ＢＢ候補カウンタ」と略称する）の値が含まれているものとする。
【００７９】
したがって、主構成要素を選択する際に、ビルディングブロック候補が複数存在する場合には、新規解生成部７Ａは、ＢＢ候補カウンタ値の大きな構成要素から順に選択する。
一方、最良解の構成要素にビルディングブロック候補が含まれていなければ、新規解生成部７Ａは、たとえば、ランダムに（または、構成要素の評価値に比例した選択確率にしたがい）主構成要素および副構成要素を選択する。
【００８０】
次に、新規解生成部７Ａは、ペア選択した主構成要素と副構成要素との同じ位置の観測値を入れ替えて新規解を生成し、生成した新規解を新規解格納部８に格納する。この新規解生成処理および新規解格納処理は、前述と同様である。
【００８１】
次に、最良解更新部９Ａは、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解を比較し、以下の処理（ａ）、（ｂ）を行う。
（ａ）まず、最良解よりも評価値が高い新規解が存在する場合には、最良解更新部９Ａは、最も評価値が高い新規解を、次の世代の最良解として最良解格納部６に格納する。
このとき、新規解の生成に用いた主構成要素または副構成要素が、ビルディングブロック候補であれば、当該ビルディングブロック候補のＢＢ候補カウンタの値をリセットし、ビルディングブロック候補情報格納部１０Ａに格納されたビルディングブロック候補情報から、当該ビルディングブロック候補の情報を削除する。
【００８２】
（ｂ）一方、最良解よりも評価値が高い新規解が存在しなかった場合には、最良解更新部９Ａは、新規解生成部７Ａに処理を戻す。
また、同一の主構成要素とペア選択が可能な全ての副構成要素とから生成された全ての新規解から、最良解よりも高い評価値が得られなかった場合には、当該主構成要素をビルディングブロック候補と判定し、当該種構成要素のＢＢ候補カウンタの値を「１」だけ増加させ、当該構成要素およびそのＢＢ候補カウンタ値を、ビルディングブロック候補情報格納部１０Ａに格納する。
【００８３】
以下、図１０および図１１の説明図を参照しながら、図９内の新規解生成部７Ａおよび最良解更新部９Ａの動作について説明する。
図１０は新規解生成部７Ａおよび最良解更新部９Ａの動作を示しており、最良解に含まれるビルディングブロック候補を主構成要素として生成した新規解が、最良解よりも高い評価値を有する場合の例を示している。
【００８４】
新規解生成部７Ａは、最良解格納部６に格納されている最良解を取得し、ビルディングブロック候補情報格納部１０Ａに格納されているビルディングブロック情報を参照して、主構成要素と副構成要素とのペア選択を行う。
【００８５】
図１０において、新規解生成部７Ａは、まず、最良解の構成要素｛２、２、２、３｝がビルディングブロック候補であることから、｛２、２、２、３｝を主構成要素とする。
続いて、新規解生成部７Ａは、他に最良解の構成要素がビルディングブロック候補に含まれないことから、残りの構成要素から何らかの選択確率にしたがって副構成要素を選択する。
【００８６】
このとき、副構成要素の選択に用いられる選択確率は、たとえばランダムに決定されてもよく、構成要素の評価値に比例した選択確率として決定されてもよい。
図１０においては、｛１、１、１、２｝が副構成要素として選択された場合を示している。
続いて、新規解生成部７Ａは、｛２、２、２、３｝と｛１、１、１、２｝とのペアにより新規解を生成し、生成した新規解を新規解格納部８に格納する。
【００８７】
次に、最良解更新部９Ａは、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解とを比較して、最良解よりも評価値が高い新規解が存在した場合には、最も評価値の高い新規解を、新たな最良解として最良解格納部６に格納する。
【００８８】
また、最良解更新部９Ａは、最良解の構成要素であって、且つ、ビルディングブロック候補である構成要素｛２、２、２、３｝を変更して、最良解よりも評価値が高い新規解が得られたことから、構成要素｛２、２、２、３｝は、ビルディングブロックではないと判定する。さらに、構成要素｛２、２、２、３｝をビルディングブロック候補から除外するために、｛２、２、２、３｝のＢＢ候補カウンタの値を「０」にリセットし、｛２、２、２、３｝に関するビルディングブロック候補情報を、ビルディングブロック候補情報格納部１０Ａから削除する。
【００８９】
図１１は新規解生成部７Ａおよび最良解更新部９Ａの他の動作を示しており、最良解に含まれるビルディングブロック候補を主構成要素として生成した新規解の全てが、最良解よりも悪い評価値となった場合の例を示している。
【００９０】
図１１において、新規解生成部７Ａは、前述（図１０）と同様に、まず、最良解の構成要素｛２、２、２、３｝がビルディングブロック候補であることから、｛２、２、２、３｝を主構成要素とする。
続いて、最良解の他の構成要素はビルディングブロック候補に含まれないことから、残りの構成要素から、何らかの選択確率にしたがって副構成要素が選択される。
【００９１】
このときの選択確率は、たとえばランダムでもあってもよく、構成要素の評価値に比例した選択確率としてもよい。
図１１においては、前述（図１０）と同様に、まず、｛１、１、１、２｝が副構成要素として選択された場合を示している。
続いて、新規解生成部７Ａは、｛２、２、２、３｝と｛１、１、１、２｝とのペアにより新規解を生成し、生成した新規解を新規解格納部８に格納する。
【００９２】
次に、最良解更新部９Ａは、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解とを比較する。
この場合、比較の結果、最良解よりも評価値の高い新規解が存在しなかったことから、最良解更新部９Ａは、第１回目に生成した新規解（図１１内の最上段×印）を破棄して、新規解生成部７Ａに処理を戻す。
【００９３】
これにより、新規解生成部７Ａは、主構成要素を｛２、２、２、３｝のままとしつつ、副構成要素を｛３、４、４、４｝に変更して２回目の新規解を生成し、生成した新規解を新規解格納部８に格納する。
最良解更新部９Ａは、前回と同様に２回目の新規解と最良解との比較を行い、最良解よりも評価値の高い新規解が存在しなかったことから、第２回目に生成した新規解（図１１内の２段目×印）を破棄して、再び新規解生成部７Ａに処理を戻す。
【００９４】
これにより、新規解生成部７Ａは、主構成要素は｛２、２、２、３｝のままとしつつ、副構成要素を｛４、３、３、１｝に変更して３回目の新規解を生成し、新規解格納部８に生成した新規解を格納する。
最良解更新部９Ａは、第２回目と同様に新規解と最良解との比較を行い、比較の結果、最良解よりも評価値の高い新規解が存在しなかったことから、第３回目に生成した新規解（図１１内の３段目×印）を破棄する。
【００９５】
以上の処理により、主構成要素を｛２、２、２、３｝として生成される新規解は、全て最良解よりも評価値が悪い結果となったので、最良解更新部９Ａは、｛２、２、２、３｝をビルディングブロック候補と判定し、｛２、２、２、３｝のＢＢ候補カウンタの値を「１」だけ増やして「２」とする。
【００９６】
また、最良解更新部９Ａは、ビルディングブロック候補情報格納部１０Ａに格納されている構成要素｛２、２、２、３｝のＢＢ候補カウンタの値を「２」に更新する。
この時点で、最良解よりも評価値が高い新規解はまだ得られていないので、最良解更新部９Ａは、再び処理を新規解生成部７Ａに戻す。
【００９７】
このとき、新規解生成部７Ａにおいては、｛２、２、２、３｝を主構成要素とした新規解は全て生成済みなので、主構成要素を他の構成要素から選択する。
以下、新規解生成部７Ａおよび最良解更新部９Ａは、前述と同様の処理を繰り返し実行する。
【００９８】
なお、図１０、図１１の例では、ビルディングブロック候補に含まれる最良解の構成要素を主構成要素とした場合を示したが、ビルディングブロック候補に含まれる最良解の構成要素が存在しない場合には、上記例で示した副構成要素の選択と同様にして、主構成要素を選択すればよい。
【００９９】
最後に、ビルディングブロック判定部１１Ａは、ビルディングブロック候補情報格納部１０Ａに格納されているビルディングブロック候補情報を参照して、ＢＢ候補カウンタの値が予め定めた閾値を超えたビルディングブロック候補を「ビルディングブロック」と判定し、判定したビルディングブロックに関する情報を、ビルディングブロック情報格納部１２に格納する。
【０１００】
このとき、前述の実施の形態１（図１、図８）によるビルディングブロック判定部１１は、多スタート局所探索の各探索で得られた最良解を連携させ「連続Ｎ世代、Ｋスタート中のＬ個以上の最良解に含まれるビルディングブロック候補」をビルディングブロックと判定したが、この発明の実施の形態２（図９）によるビルディングブロック判定部１１Ａは、各探索の連携を行わずに、各探索において独立にビルディングブロック判定を行う。
【０１０１】
以上のように、この発明の実施の形態２に係る航跡割当装置（図９〜図１１）の最良解更新部９Ａは、新規解生成部７Ａによる新規解生成処理において、最良解の構成要素の一部分を変更して生成された全ての新規解の評価値が最良解の評価値よりも悪ければ、新規解の生成の元となった構成要素をビルディングブロック候補としてビルディングブロック候補情報格納部１０Ａに登録する。
すなわち、最良解の１個の構成要素を用いて生成される全ての新規解が最良解よりも高い評価値を得られなかった場合には、元となった構成要素をビルディングブロック候補と判定する。
【０１０２】
また、ビルディングブロック判定部１１Ａは、Ｒ回にわたって連続してビルディングブロック候補となった構成要素が存在する場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報をビルディングブロック情報格納部１２に登録する。
すなわち、同一構成要素が一定回数にわたって連続してビルディングブロック候補と判定された場合には、その構成要素をビルディングブロックと判定して、以降の新規解生成処理において、必ずビルディングブロックを新規解に残す。
【０１０３】
これにより、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されて最良解が最適解から遠ざかる現象、最適解を求めるまでの更新世代数が増加する現象および局所解に陥る現象を全て回避して、探索精度および探索速度を向上させることができるという効果がある。
【０１０４】
実施の形態３．
なお、上記実施の形態２では、多スタート局所探索時における処理を具体的に言及しなかったが、多スタート局所探索時において同様の処理を適用してもよい。
以下、多スタート局所探索時に同様の処理を適用したこの発明の実施の形態３について説明する。
【０１０５】
なお、この発明の実施の形態３に係る航跡割当装置は、前述（図９）と同様の構成からなり、ビルディングブロック判定部１１Ａの一部動作のみが異なるのみである。
したがって、ここでは、図９を参照しながら、主にビルディングブロック判定部１１Ａの動作について説明する。
【０１０６】
この発明の実施の形態３において、ビルディングブロック判定部１１Ａは、スタート数Ｋの多スタート局所探索における各探索の第ｎ世代の最良解において、「Ｋ個の最良解のうち、ＢＢ候補カウンタが閾値Ｒを超える共通した構成要素（共通構成要素）を有する最良解がＬ個以上存在する」場合に、当該共通構成要素を「ビルディングブロック」と判定する。
【０１０７】
すなわち、ビルディングブロック判定部１１Ａは、多スタート探索時に、同一構成要素がＲ回にわたって連続して、Ｋ個中のＬ個以上の探索においてビルディングブロック候補となった場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報をビルディングブロック情報格納部１２に登録する。
【０１０８】
この場合、最良解更新部９Ａは、多スタート局所探索時に、個々の最適解探索の処理に応じた新規解生成部による新規解生成処理において、同じ構成要素の一部分を変更して生成された全ての新規解の評価値が最良解の評価値よりも悪ければ、新規解の生成の元となった構成要素に関するビルディングブロック候補情報をビルディングブロック候補情報格納部１０Ａに登録する。
【０１０９】
以上のように、この発明の実施の形態に係る航跡割当装置（図９）は、最良解の１個の構成要素を用いて生成される全ての新規解が最良解よりも高い評価値を得られなかった場合には、元となった構成要素をビルディングブロック候補と判定する。
また、多スタート局所探索における個々の探索を連携させ、同一世代の一定個数以上の最良解に共通するビルディングブロック候補が存在し、且つ、そのビルディングブロック候補のＢＢ候補カウンタが一定値を超えている場合には、そのビルディングブロック候補をビルディングブロックと判定し、以降の新規解生成時にビルディングブロックを必ず解の中に残す。
【０１１０】
これにより、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されることによって最良解が最適解から遠ざかる現象、最適解を求めるまでの更新世代数が増加する現象および局所解に陥る現象を回避して、探索精度（得られる解の評価値の良さ）および探索速度（探索終了までの更新世代数の少なさ）を向上させることができるという効果がある。
【０１１１】
実施の形態４．
なお、上記実施の形態３では、特に言及しなかったが、図１２のように、優先変更対象判定部１５および優先変更対象格納部１６を追加し、多スタート局所探索において、ビルディングブロックでない同一の構成要素が一定数以上の最良解に含まれる場合に、いくつかの探索で優先的に当該構成要素を変更対象としてペア選択するように構成してもよい。
図１２はこの発明の実施の形態３に係る航跡割当装置の機能構成を示すブロック図であり、前述（図９参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
【０１１２】
図１２において、優先変更対象判定部１５は、初期解生成部５と新規解生成部７Ｂとの間に挿入されており、終了判定部の判定結果に応答する。
優先変更対象格納部１６は、優先変更対象判定部１５で判定された優先変更対象情報を格納し、格納データを新規解生成部７Ｂに提供する。
【０１１３】
この場合、前述（図９）との相違点は、優先変更対象判定部１５および優先変更対象格納部１６を新たに追加したことに加えて、新規解生成部７Ｂの一部機能が異なることである。
したがって、以下、図１２を参照しながら、主に優先変更対象判定部１５、優先変更対象格納部１６および新規解生成部７Ｂの動作について説明する。
【０１１４】
まず、優先変更対象判定部１５は、スタート数がＫ個の多スタート局所探索の実行時において、最良解格納部６に格納されているＫ個の最良解に共通して含まれる構成要素（共通構成要素）を探索し、Ｋ個中にＳ個以上の最良解に共通構成要素が存在する場合であって、且つ、共通構成要素がビルディングブロックでない場合には、当該最良解の数をＭ個とすると、Ｍ個の当該最良解からＭ−（Ｓ−１）個を選択する。
【０１１５】
続いて、優先変更対象判定部１５は、選択した最良解の共通構成要素を優先変更対象と判定し、優先変更対象を含む最良解のスタート番号（スタート数が「３」であれば、スタート番号は「１」、「２」、「３」となる）と、優先変更対象となった共通構成要素を優先変更対象情報として優先変更対象格納部１６に格納する。
【０１１６】
次に、新規解生成部７Ｂは、優先変更対象格納部１６に格納されている優先変更対象情報を参照し、自分のスタート番号が優先変更対象情報に含まれている場合には、ペア選択において、優先変更対象の構成要素を主構成要素として選択する。
以降の新規解生成部７Ｂの処理については、前述の実施の形態２で述べた内容と同じなので、ここでは省略する。
【０１１７】
なお、新規解生成部７Ｂは、優先変更対象が存在しない場合か、または、ペア選択処理の未実行の優先変更対象が残っていない場合であれば、前述の実施の形態２で述べたように、ビルディングブロック候補を優先的に主構成要素として選択する。
すなわち、ペア選択における主構成要素の選択優先順位は、（１）「優先変更対象の構成要素」、（２）「ビルディングブロック候補」、（３）「それ以外の構成要素」の順となる。ただし、「ビルディングブロック」は、選択対象から除外される。
【０１１８】
次に、図１３の説明図を参照しながら、優先変更対象判定部１５の動作について説明する。
図１３はスタート数が「５」の場合を示しており、５個の最良解のうちの４個にビルディングブロックでない構成要素｛１、１、１、２｝が含まれている場合の動作例を示している。
【０１１９】
図１３において、優先選択対象の判定条件を、「Ｋ（＝５）個中のＳ（＝２）個以上の最良解にビルディングブロックでない構成要素が含まれている場合」とすると、構成要素｛１、１、１、２｝は、Ｓ（＝２）個を超えるＭ（＝４）個の最良解に含まれている。
したがって、優先変更対象判定部１５は、構成要素｛１、１、１、２｝を含む最良解の中から、Ｍ−（Ｓ−１）（＝３）個の最良解を選択する。
図１３においては、破線矢印で示すように、スタート１、スタート２およびスタート５の３個の最良解が選択されている。
【０１２０】
次に、優先変更対象判定部１５は、｛１、１、１、２｝のパターンと、選択したスタート番号「１」、「２」、「５」をまとめて、優先変更対象情報として優先変更対象格納部１６に格納する。
【０１２１】
以上のように、この発明の実施の形態４に係る航跡割当装置（図１２、図１３）は、最良解格納部６に格納された最良解の構成要素の中から、新規解を生成する際の優先変更対象を選択する優先変更対象判定部１５と、優先変更対象判定部１５が優先変更対象と判定した構成要素に関する情報を優先変更対象情報として格納する優先対象格納部１６とを備えている。
【０１２２】
優先変更対象判定部１５は、多スタート探索時に、Ｋ個の最良解のうちのＭ個以上の最良解に同一構成要素が存在する場合に、Ｍ個の当該最良解からＳ個を選択し、選択したＳ個の最良解に含まれる同一構成要素に関する情報を優先変更対象情報として優先変更対象格納部１６に登録する。
【０１２３】
また、新規解生成部７Ｂは、優先変更対象格納部１６に格納された優先変更対象情報を参照し、優先変更対象とした構成要素の一部を変更して新規解を生成する。
すなわち、新規解生成部７Ｂは、多スタート局所探索において、ビルディングブロックでない同一の構成要素が一定数以上の最良解に含まれる場合に、新規解生成の処理実行時において、いくつかの探索で優先的に当該構成要素を変更対象としてペア選択する。
【０１２４】
これにより、各探索が解空間中の同じ範囲を探索することを防ぐことができ、各探索が異なる範囲を探索することにより、広い範囲の解空間の探索を可能とすることができる。
また、ビルディングブロックの判定を行い、新規解生成時にビルディングブロックを必ず解の中に残すことにより、前述と同様に、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されることによって最良解が最適解から遠ざかる現象、最適解を求めるまでの更新世代数が増加する現象および局所解に陥る現象を回避して、探索精度（得られる解の評価値の良さ）および探索速度（探索終了までの更新世代数の少なさ）を向上させることができる。
【０１２５】
なお、上記実施の形態４では、実施の形態３の構成に適用した場合を例にとって説明したが、前述の実施の形態１、２にも適用可能なことは言うまでもない。
【図面の簡単な説明】
【０１２６】
【図１】この発明の実施の形態１に係る航跡割当装置の機能構成を示すブロック図である。
【図２】図１内の観測値情報取得部により取得される観測値を図式的に示す説明図である。
【図３】図１内の観測値情報格納部による観測値情報の格納状態を図式的に示す説明図である。
【図４】図１内の航跡候補生成部による処理動作を図式的に示す説明図である。を示している。
【図５】図１内の初期解生成部による初期解生成動作を図式的に示す説明図である。
【図６】図１内の新規解生成部および最良解更新部による処理動作を図式的に示す説明図である。
【図７】図１内の最良解更新部によるビルディングブロック候補による判定処理動作を図式的に示す説明図である。
【図８】図１内のビルディングブロック判定部による判定処理を図式的に示す説明図である。
【図９】この発明の実施の形態２に係る航跡割当装置の機能構成を示すブロック図である。
【図１０】図９内の新規解生成部および最良解更新部による処理動作を図式的に示す説明図である。
【図１１】図９内の新規解生成部および最良解更新部による他の処理動作を図式的に示す説明図である。
【図１２】この発明の実施の形態４に係る航跡割当装置の機能構成を示すブロック図である。
【図１３】図１２内の優先変更対象判定部による判定処理動作を図式的に示す説明図である。
【図１４】従来の航跡割当装置による処理動作を図式的に示す説明図であり、第ｎ世代の最良解と更新後（第ｎ＋１世代）の最適解との関係を示している。
【符号の説明】
【０１２７】
１ 観測値情報取得部、２ 観測値情報格納部、３ 航跡候補生成部、４ 航跡候補格納部、５ 初期解生成部、６ 最良解格納部、７、７Ａ、７Ｂ 新規解生成部、８ 新規解格納部、９、９Ａ 最良解更新部、１０、１０Ａ ビルディングブロック候補情報格納部、１１、１１Ａ ビルディングブロック判定部、１２ ビルディングブロック情報格納部、１３ 終了判定部、１４ 探索結果出力部。
【技術分野】
【０００１】
この発明は、レーダなどの観測センサにより得られる時間的に連続した複数フレームの観測値を用いて、観測された複数の移動体の航跡を求める航跡割当装置に関するものである。
【背景技術】
【０００２】
従来から、レーダなどの観測センサにより得られた観測値（位置座標や信号強度などの情報が含まれる）を用いて複数の移動体の航跡を推定する航跡追尾処理はよく知られており、航跡追尾処理を構成する処理の１つとして航跡割当処理がある。一般に、観測センサの観測単位をフレームと呼び、１フレーム内には複数の観測値が含まれる。
【０００３】
航跡割当処理においては、航跡の尤度（航跡の尤もらしさを表す指標）が最も高くなるように、それまでに得られている航跡に対して、新たに観測されたフレーム内の観測値を割り当てる処理が行われる。
従来の航跡割当装置としては、最新の１個のフレーム内の観測値の割当処理を行うＭＨＴ（Ｍｕｌｔｉｐｌｅ Ｈｙｐｏｔｈｅｓｉｓ Ｔｒａｃｋｉｎｇ）法を適用した目標追尾装置が提案されている（たとえば、特許文献１参照）。
【０００４】
また、ＭＨＴ法のように１個のフレームの割当処理から求められる航跡では、十分な航跡追尾の精度が得られないことから、さらに高い精度を得るために、連続する複数フレームの航跡割当処理を行うＭＦＡ（Ｍｕｌｔｉｐｌｅ Ｆｒａｍｅ Ａｓｓｉｇｎｍｅｎｔ）問題を解くアルゴリズムも提案されている。
【０００５】
ＭＦＡ問題は、組合せ最適化問題の１つであり、フレーム数やフレーム内の観測値数が増加すると、組合せ数が爆発的に増加してしまうので、厳密解法による最適解の導出においては、長時間を要し実用面で問題が生じる。
そこで、運用に支障をきたさなければ、最適解でなくても差し支えないという観点に立ち、ＭＦＡ問題を高速に解くアルゴリズムとして、ラグランジュ緩和法を適用した手法が提案されている（たとえば、非特許文献１参照）。
【０００６】
ＭＦＡ問題にラグランジュ緩和法を適用する場合には、Ｎ次元（次元数＝フレーム数）の問題を２次元に変換することで探索範囲の絞込みが行われるが、次元数が増えるほど、処理が煩雑になるうえ実装も難しくなり、効果的な絞込みを実現することができない可能性がある。
【０００７】
一方、ラグランジュ緩和法よりも処理が単純で実装が容易であり、且つ、ＭＦＡ問題を高速に解くことが期待できるアルゴリズムとして、組合せ最適化メタヒューリスティックス手法が存在する。
組合せ最適化メタヒューリスティックス手法の代表的なアルゴリズムとしては、遺伝的アルゴリズム、タブーサーチ、シミュレーテッドアニーリング、多スタート局所探索などが挙げられる。
【０００８】
多スタート局所探索は、異なる初期解を複数用意して、複数の近傍探索を同時に実行する探索処理であり、単純な処理ながら探索効率を上げることが可能である。
この種のメタヒューリスティックス手法の特徴は、それまでの探索で得られた最良解の一部を変更して新規解を生成し、新規解の元となった最良解よりも評価値の良い新規解が存在した場合には、その新規解を最良解と置き換えることを繰り返し実行し、最適解を探索することにある。
【０００９】
しかしながら、最良解から新規解を生成する処理において、最良解中に、最適解を構成する要素（以下、「ビルディングブロック」という）が含まれていた場合に、そのビルディングブロックが変更されてしまうことから、新規解の中にビルディングブロックが残らず、最適解または準最適解が求まるまでの探索回数の増加を招く場合や、最適解または準最適解が求まらない場合が生じるという問題がある。
【００１０】
なお、「最良解」とは、現時点までの探索で得られている最も良い解を意味し、「最適解」とは、全ての組合せの中で最も適した解を意味し、「準最適解」とは、最適解に近い運用に支障を及ぼさない解を意味している。
【００１１】
以下、図１４の説明図を参照しながら、従来の航跡割当処理における具体例を挙げて、上記問題点について説明する。
図１４においては、第ｎ世代の最良解と、最良解の組み合わせを変更した新規解と、更新後（第ｎ＋１世代）の最適解との関係が示されている。
【００１２】
図１４において、ｎ回目の更新後に得られた「最良解（第ｎ世代）」は、４個の航跡を表しており、横一行｛１、１、１、２｝、｛２、２、２、３｝、｛３、４、４、４｝、｛４、３、３、１｝は、それぞれ１個の航跡であり、各航跡内の「１」〜「４」の数字は、観測値に振られた番号である。
【００１３】
また、「最良解（第ｎ世代）」の縦一列｛１、２、３、４｝、｛１、２、４、３｝｛１、２、４、３｝｛２、３、４、１｝は、同一フレーム内の観測値である。
したがって、「最良解（第ｎ世代）」は、各フレームの観測値｛１、１、１、２｝を結んだ航跡と、観測値｛２、２、２、３｝を結んだ航跡と、観測値｛３、４、４、４｝を結んだ航跡と、観測値｛４、３、３、１｝を結んだ航跡から構成されている。
【００１４】
このとき、航跡｛２、２、２、３｝が「ビルディングブロック」であったと仮定し、新規解の生成処理において、航跡｛２、２、２、３｝と航跡｛４、３、３、１｝とが変更対処として選ばれ、それぞれの同じ位置の観測値（灰色ブロック参照）を入れ替えた４個の新規解を生成したと仮定する。
こうして得られた４個の新規解（図１４の破線枠内の４個の解）においては、「ビルディングブロック」が壊されていることが分かる。
【００１５】
これら４個の新規解のうち、たとえば左から２番目の解が「最良解（第ｎ世代）」よりも良い評価値であった場合には、最良解更新時に、「最良解（第ｎ＋１世代）」の解として、左から２番目の新規解が選ばれ（破線矢印参照）、最良解（第ｎ＋１世代）からビルディングブロックである航跡｛２、２、２、３｝が消えてしまう。
ビルディングブロックは最適解の構成要素であり、探索途中の最良解の構成要素がビルディングブロックであるか否かは判定することができないことから、このような問題が発生する。
【００１６】
【特許文献１】特許第３１４５８９３号公報
【非特許文献１】Ａｕｂｒｅｙ Ｂ．Ｐｏｏｒｅ、「Ａ Ｎｅｗ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ｄａｔａ Ａｓｓｏｃｉａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｍｕｌｔｉｓｅｎｓｏｒ−Ｍｕｌｔｉｔａｒｇｅｔ Ｔｒａｃｋｉｎｇ」、Ｐｒｏｃ． ｏｆ ＳＰＩＥ Ｖｏｌ．２５６１、１９９５
【発明の開示】
【発明が解決しようとする課題】
【００１７】
従来の航跡割当装置では、ＭＦＡ問題を高速に解くためのメタヒューリスティックス手法として多スタート局所探索を適用した場合に、最良解から新規解を生成する処理において、最適解を構成する「ビルディングブロック」が変更されてしまうので、新規解の中にビルディングブロックが残らず、最適解または準最適解が求まるまでの探索回数の増加を招く場合や、最適解または準最適解が求められない場合が生じるという課題があった。
【００１８】
この発明は、上記のような課題を解決するためになされたものであり、多スタート局所探索において各探索を連携させ、各探索における最良解を構成する要素の中でビルディングブロックである可能性が高いと判定したものを次の世代の最良解に必ず残すことにより、ＭＦＡ問題の最適解探索を精度良く効率的に行うことのできる航跡割当装置を得ることを目的とする。
【課題を解決するための手段】
【００１９】
この発明による航跡割当装置は、観測センサにより観測される時間的に連続した観測値情報を用いて複数の移動体の航跡を追尾するために、観測値情報の各々を複数の移動体の各航跡に割り当てる航跡割当装置であって、観測センサを用いて観測値情報を取得する観測値情報取得部と、観測値情報取得部が取得した観測値情報を格納する観測値情報格納部と、観測値情報格納部に格納された各時刻の観測値情報を組合せて、複数の移動体の各々が取り得る航跡の候補を航跡候補として生成する航跡候補生成部と、航跡候補を格納する航跡候補格納部と、航跡候補格納部に格納された航跡候補の集合から最も評価値の良い航跡候補の組合せを最適解として探索する際に、最適解探索の開始時の航跡候補の組合せを初期解として生成する初期解生成部と、初期解を格納するとともに、最適解探索の途中で得られた解の中で最も良い解を最良解として格納する最良解格納部と、最良解格納部に格納された最良解の一部分を変更し、新たな解を新規解として生成する新規解生成部と、新規解を格納する新規解格納部と、新規解格納部に格納された新規解と最良解格納部に格納された最良解とを比較して、最良解よりも評価値が良い新規解が存在する場合に、当該新規解を新たな最良解として最良解格納部に格納する最良解更新部と、最良解の構成要素となる航跡候補が最適解の構成要素となり得るか否かを判定し、最適解の構成要素となり得ると判定された最良解の構成要素をビルディングブロックと判定するビルディングブロック判定部と、ビルディングブロックの候補となる構成要素に関するビルディングブロック候補情報を格納するビルディングブロック候補情報格納部と、ビルディングブロックと判定された構成要素に関するビルディングブロック情報を格納するビルディングブロック情報格納部と、最適解探索を終了するかまたは継続するかを判定する終了判定部と、最適解探索を終了すると判定された場合に、最終的に得られた最良解を出力する探索結果出力部とを備え、新規解生成部は、ビルディングブロック情報に基づいて、ビルディングブロックと判定された構成要素が必ず含まれるように新規解を生成し、最良解更新部は、スタート数がＫ個の初期解を用いた（すなわち、最適解探索の実行中にＫ個の最良解が存在する）多スタート局所探索時に、Ｋ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定し、当該ビルディングブロック候補情報をビルディングブロック候補情報格納部に登録し、ビルディングブロック判定部は、最良解更新部による１回の最良解更新で世代が１つ進む条件下で、同一構成要素がＮ世代にわたって連続してビルディングブロック候補と判定された場合に、当該構成要素をビルディングブロックと判定し、当該ビルディングブロック情報をビルディングブロック情報格納部に登録するものである。
【発明の効果】
【００２０】
この発明によれば、多スタート局所探索における最良解を構成する要素の中で、ビルディングブロックである可能性が高いと判定したものを次の世代の最良解に必ず残すことができるので、ＭＦＡ問題の最適解探索を精度良く効率的に行うことができる。
【発明を実施するための最良の形態】
【００２１】
実施の形態１．
以下、図面を参照しながら、この発明を実施するための最良の形態について説明する。
図１はこの発明の実施の形態１に係る航跡割当装置の機能構成を示すブロック図であり、各ブロックを結ぶ実線矢印は、処理の流れを示し、破線矢印は、データの流れを示している。
【００２２】
図１において、航跡割当装置は、観測値情報取得部１と、観測値情報格納部２と、航跡候補生成部３と、航跡候補格納部４と、初期解生成部５と、最良解格納部６と、新規解生成部７と、新規解格納部８と、最良解更新部９と、ビルディングブロック候補情報格納部１０と、ビルディングブロック判定部１１と、ビルディングブロック情報格納部１２と、終了判定部１３と、探索結果出力部１４とを備えている。
【００２３】
観測値情報取得部１は、レーダなど（図示せず）の観測センサにより観測された移動体の観測値データ（観測値情報）を取得し、観測値情報格納部２は、観測値情報取得部１で取得された移動体の観測値情報を格納する。
【００２４】
航跡候補生成部３は、観測値情報格納部２に格納されている観測値情報に基づいて、観測値を組合せた航跡候補を生成するとともに、各航跡候補の評価値を計算する。航跡候補格納部４は、航跡候補生成部３により生成された航跡候補およびその評価値を格納する。
【００２５】
初期解生成部５は、航跡候補格納部４に格納されている航跡候補およびその評価値を用いて、ＭＦＡ問題の最適解探索を行うための初期解を生成する。
最良解格納部６は、繰り返し実行される最適解探索において、最新の最も評価値の良い解を最良解として格納する。なお、初期解生成部５で生成された初期解は、最初に得られた最良解として最良解格納部６に格納される。
【００２６】
新規解生成部７は、ビルディングブロック情報格納部１２に格納されているビルディングブロック情報に基づき、ビルディングブロックが残るように、最良解格納部６に格納されている最良解の一部を変更して新規解を生成する。新規解格納部８は、新規解生成部７で生成された新規解を格納する。
【００２７】
最良解更新部９は、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解とを比較して、最良解よりも評価値の良い新規解が存在する場合には、当該新規解を新たな最良解として最良解格納部６に格納する。また、最良解更新部９は、最良解の更新後に、新たな最良解を構成する要素がビルディングブロックの候補となるか否かを判定する。
【００２８】
ビルディングブロック候補情報格納部１０は、最良解更新部９がビルディングブロック候補と判定した最良解の構成要素に関するビルディングブロック候補情報を格納する。
ビルディングブロック判定部１１は、ビルディングブロック候補情報格納部１０に格納された情報に基づいて、最良解を構成する要素がビルディングブロックとなり得るか否か判定する。
【００２９】
ビルディングブロック情報格納部１２は、ビルディングブロック判定部１１がビルディングブロックと判定した、最良解を構成する要素に関するビルディングブロック情報を格納する。
終了判定部１３は、最適解探索の処理終了判定を行い、探索処理終了と判定された場合には探索結果出力部１４に処理を移し、終了しないと判定された場合には新規解生成部７に処理を戻す。
探索結果出力部１４は、最適解探索に応じて得られた最良解を探索結果として出力する。
【００３０】
次に、図２〜図８の説明図を参照しながら、図１に示した航跡割当装置による一連の動作について説明する。
まず、観測値情報取得部１は、たとえばレーダにより観測された移動体の最新の１フレーム分の観測値情報を取得し、観測値情報格納部２は、取得した観測値を、時間的に連続した複数フレーム分にわたって格納する。
【００３１】
図２は観測値情報取得部１により取得される観測値を図式的に示しており、時系列的な観測値をＸ−Ｙ平面上に配置した例を示している。
ここでは、時刻ｔ、時刻ｔ＋１、時刻ｔ＋２、時刻ｔ＋３（４個のフレームｔ〜フレームｔ＋３に対応）における４個の観測値が示されている。
【００３２】
図２において、同一フレーム内の観測値は、それぞれ破線枠で囲まれており、各フレーム内の丸で囲まれた数字は、それぞれ観測値を表している。なお、観測値の数値「１」〜「４」は、単にフレーム内で割り当てた連番であり、数値そのものに特に意味はない。
【００３３】
たとえば、図２に示した状況において、観測値情報収集部１は、最新のフレームｔ＋３の観測値を取得して観測値情報格納部２に格納し、このとき、観測値情報格納部２は、最新のＦフレーム分（Ｆ＝４）の観測値情報を格納することになる。
【００３４】
図３は観測値情報格納部２における観測値情報の格納状態を図式的に示しており、Ｆフレーム分（Ｆ＝４）の場合を示している。
図３において、観測値情報格納部２には、４フレーム分（フレームｔ〜フレームｔ＋３）の観測値情報が格納されており、最新のフレームがｔ＋３である。また、丸で囲まれた数字は、前述（図２）と同様の観測値を表している。
【００３５】
観測値情報格納部２への観測値情報の格納処理に続いて、次に、航跡候補生成部３は、観測値情報格納部２に格納されている観測値情報に基づいて航跡候補を生成し、航跡候補格納部４は、生成された航跡候補を格納する。
【００３６】
図４は航跡候補生成部３による処理動作を示している。
図４において、観測値情報格納部２には、４フレーム分の観測値情報（１点鎖線枠内）が格納されており、縦一列が１フレーム分の観測値である。
各観測値は、図３と同様に、左から観測時刻（ｔ、ｔ＋１、ｔ＋２、ｔ＋３）順に並んでいる。
【００３７】
航跡候補生成部３は、観測値情報格納部２内の観測値情報から航跡候補を生成する。
航跡候補とは、ＭＦＡの解を構成する航跡となり得るものであり、各フレームから１個ずつ観測値を選択して観測順に並べることにより、図４内の航跡候補集合（１点鎖線枠内）のように生成される。
【００３８】
たとえば、航跡候補集合中の最上段の航跡候補｛１、１、１、１｝は、フレームｔの観測値「１」、フレームｔ＋１の観測値「１」、フレームｔ＋２の観測値「１」、フレームｔ＋３の観測値「１」を繋いだ航跡候補である。
【００３９】
図４の例では、航跡候補｛１、１、１、１｝〜｛４、４、４、４｝は、４４（＝２５６通り）だけ生成される。また、航跡候補生成部３は、生成した各航跡候補に対する評価値として、航跡コスト（−１５．４、−２．２、・・・、−１０．７）も併せて求める。
以下、航跡候補格納部４は、航跡候補生成部３で生成された航跡候補およびその評価値（図４）のデータを格納する。
【００４０】
続いて、初期解生成部５は、航跡候補格納部４に格納されている航跡候補の集合の中から、同一フレーム内での観測値の重複がないように、且つ、全ての観測値が含まれるように、最適解探索の初期解を生成する。このとき生成される初期解の数は、適用される最適解探索のアルゴリズムに依存し、たとえば、多スタート局所探索を適用する場合には、スタート数が「Ｋ」であれば、Ｋ個の異なる初期解を生成する。
【００４１】
図５は初期解生成部５における初期解生成動作を示しており、３個の初期解を生成する例を示している。
図５において、初期解生成部５は、以下の手順（１）〜（３）を３回繰り返すことにより、３個の初期解を生成する。
【００４２】
（１）まず、航跡候補格納部４に格納されている航跡候補の集合から１個の航跡候補を選択する。このときの選択の基準としては、ランダムに基づくもの、評価値が最も良いもの、評価値に比例した選択確率に基づくもの、などが挙げられる。
ここでは、たとえば、図５の最上段に示す航跡候補｛１、２、３、４｝を選択する。
【００４３】
（２）次に、選択済みの航跡候補との間で、同一フレーム内で観測値が重複しないように、航跡候補の集合から新たに航跡候補を選択する。このときの選択の基準は上記（１）と同じである。
ここでは、（１）において、航跡候補｛１、２、３、４｝が選択されているので、図５の２段目に示すように、（１）の航跡候補との間で同一フレーム内の観測値が重複しない航跡候補｛２、３、４、１｝を選択する。
【００４４】
（３）同様にして、選択済みの全ての航跡候補と観測値の重複が起きないように、且つ、全ての観測値が初期解に含まれるように、航跡候補の集合から順次に航跡候補｛３、４、１、２｝、｛４、１、２、３｝を選択する。
これにより、図５に示すように、上記４通りの航跡候補からなる１個の「初期解−１」が生成される。
【００４５】
以下、上記（１）〜（３）と同様の処理により、「初期解−２」を生成する。ただし、「初期解−２」は、「初期解−１」とは異なっていなければならない。
同様にして、「初期解−１」および「初期解−２」とは異なる「初期解−３」を生成する。
初期解生成部５で生成された３個の初期解「初期解−１」〜「初期解−３」は、最初に得られた最良解と見なせるので、最良解格納部６に格納される。
【００４６】
効率的な最適解探索を行うためには、初期解が重要であり、この発明では、ＧＲＡＳＰ（Ｇｒｅｅｄｙ Ｒａｎｄｏｍｉｚｅｄ Ａｄａｐｔｉｖｅ Ｓｅａｒｃｈ Ｐｒｏｃｅｄｕｒｅ）という手法の初期解生成法を利用することとする。
なお、ＧＲＡＳＰ法による初期解生成の手順は、公知なので、ここでは割愛する。
【００４７】
次に、新規解生成部７は、最良解格納部６に格納されている最良解の一部を変更した新規解を生成し、新規解格納部８は、生成された新規解を格納する。
新規解生成部７は、新規解生成時において、ビルディングブロック情報格納部１２に格納されている情報に基づいて、最良解中に含まれるビルディングブロックと判定された構成要素を新規解に残すように解を生成する。
【００４８】
ビルディングブロックの判定処理に関しては、ビルディングブロック判定部１１の動作説明（後述する）で具体例を述べる。
新規解格納部８に新規解が格納されると、最良解更新部９は、最良解格納部６に格納されている最良解と新規解格納部８に格納されている新規解とを比較し、最良解よりも評価値の良い新規解が存在する場合には、最も評価値の良い新規解を「新たな最良解」とし、最良解格納部６に新たな最良解を格納する。
【００４９】
もし、第ｎ世代の最良解よりも評価値が良い新規解が生成されなかった場合には、最良解更新部９は、新規解生成部７に処理を戻す。これにより、新規解生成部７は、新規解の生成処理を再度実行する。
この発明の実施の形態１に係る航跡割当装置においては、新規解生成部７による新規解生成処理と、最良解更新部９による最良解更新処理と、を繰り返し実行することにより、最適解探索が行われる。
【００５０】
図６は新規解生成部７および最良解更新部９の動作を示しており、第ｎ世代から第ｎ＋１世代への新規解生成および最良解更新の例を示している。
ここでは、新規解生成処理と最良解更新処理との１サイクル分を「世代」と呼ぶことにする。
【００５１】
図６において、新規解生成部７は、最良解格納部６に格納されている第ｎ世代の最良解を取得し、新規解を生成するために観測値の入れ替えを行うための２個の構成要素を選択する（以下、この選択を「ペア選択」という）。
【００５２】
このとき、ビルディングブロック情報格納部１２に格納されているビルディングブロック情報に第ｎ世代の最良解の構成要素｛２、２、２、３｝が含まれていたとすると、新規解生成部７は、構成要素｛２、２、２、３｝をペア選択対象から除外し、図６に示すように、たとえば構成要素｛１、１、１、２｝および｛４、３、３、１｝をペア選択する。
【００５３】
なお、ペア選択の基準は、ここでは特に定めないが、たとえば、各構成要素の評価値の悪い順に２個選択するか、または、各構成要素の評価値に比例した選択確率を与えて選択する方法が考えられる。
【００５４】
新規解生成部７は、選択した構成要素｛１、１、１、２｝と｛４、３、３、１｝の同じ位置の観測値（すなわち、同一フレーム内の観測値）を入れ替えて新規解を生成する。
図６においては、４個の新規解（２点鎖線枠内）が生成される。すなわち、右端の観測値「２」、「１」を入れ替えた「新規解−１」と、右から２番目の観測値「１」、「３」を入れ替えた「新規解−２」と、左から２番目の観測値「１」、「３」を入れ替えた「新規解−３」と、左端の観測値「１」、「４」を入れ替えた「新規解−４」とが生成される。
【００５５】
また、新規解生成部７は、各新規解の評価値を計算し、新規解格納部８は、生成された新規解およびその評価値を格納する。
新規解生成部７における新規解生成処理が完了すると、最良解更新部９は、最良解格納部６に格納されている第ｎ世代の最良解の評価値と、新規解格納部８に格納されている「新規解−１」〜「新規解−４」の評価値とを比較し、最良解よりも評価値の良い新規解が存在する場合には、最も評価値の良い新規解を第ｎ＋１世代の最良解として決定する。
【００５６】
図６においては、第ｎ世代の最良解と４個の新規解とを合わせた中で、「新規解−２」が最も評価値が良かったことから、最良解更新部９は、「新規解−２」を第ｎ＋１世代の最良解として決定した場合を示している。
【００５７】
次に、最良解更新部９は、スタート数がＫ個の多スタート局所探索において、各探索の第ｎ＋１世代のＫ個の最良解の中に、同じ構成要素がＬ（≦Ｋ）個以上含まれれば、その構成要素をビルディングブロック候補と判定する。
【００５８】
図７は最良解更新部９によるビルディングブロック候補の判定処理例を示しており、Ｋ＝３、Ｌ＝２とした場合の例を示している。
この場合、スタート数が「３」の多スタート局所探索が行われているので、異なる３通りの探索処理が実行されており、最良解格納部６には、それぞれの探索における最良解が格納されている。
【００５９】
図７において、第ｎ＋１世代の３個の最良解のそれぞれには、構成要素｛２、２、２、３｝が含まれており、構成要素｛２、２、２、３｝は、「Ｋ（＝３）個のスタート数のうち、Ｌ（＝２）個以上の最良解に含まれている」という条件を満たしているので、最良解更新部９は、構成要素｛２、２、２、３｝を「ビルディングブロック候補」と判定する。
ビルディングブロック候補と判定された構成要素｛２、２、２、３｝に関する情報は、ビルディングブロック候補情報格納部１０に格納される。
【００６０】
最良解更新部９による更新処理が完了すると、ビルディングブロック判定部１１は、ビルディングブロック候補情報格納部１０に格納された情報から、「連続Ｎ世代、Ｋスタート中のＬ個以上の最良解に含まれるビルディングブロック候補」を、「ビルディングブロック」と判定する。
【００６１】
図８はビルディングブロック判定部１１の判定処理を示しており、上記条件数Ｎ、Ｋ、Ｌが、Ｎ＝４、Ｋ＝３、Ｌ＝２の場合を示している。
図８において、構成要素｛２、２、２、３｝は、第ｎ−２世代から第ｎ＋１世代までのＮ（＝４）世代にわたって連続して、「Ｋ（＝３）スタート中Ｌ（＝２）個以上の最良解に含まれている」という条件を満たしているので、ビルディングブロック判定部１１は、構成要素｛２、２、２、３｝を「ビルディングブロック」と判定する。
ビルディングブロックと判定された構成要素に関する情報は、ビルディングブロック情報格納部１２に格納される。
【００６２】
最後に、終了判定部１３は、最適解探索の処理を継続するか否（終了する）かを判定し、継続する場合には新規解生成部７に処理を戻し、終了する場合には探索結果出力部１４に処理を進める。
【００６３】
終了判定部１３による終了判定基準は、以下の通りである。
すなわち、「探索終了」の判定条件は、世代数が上限値に達するか、新規解生成部７が生成する全ての新規解に対して最良解更新部９が最良解の更新処理を実行できなかった場合であり、「探索継続」の条件は、上記「探索終了」の条件を満たさない場合である。
【００６４】
最適解探索を終了する場合には、探索結果出力部１４は、探索終了時点において最良解格納部６に格納されている最良解の中で最も評価値の良いものを、探索結果として出力する。
【００６５】
以上のように、この発明の実施の形態１に係る航跡割当装置（図１〜図８）は、観測センサにより観測される時間的に連続した観測値情報を用いて複数の移動体の航跡を追尾するために、観測値情報の各々を複数の移動体の各航跡に割り当てる航跡割当装置であって、観測センサを用いて観測値情報を取得する観測値情報取得部１と、観測値情報取得部１が取得した観測値情報を格納する観測値情報格納部２と、航跡候補を生成する航跡候補生成部３と、航跡候補を格納する航跡候補格納部４と、最適解探索の開始時の初期解を生成する初期解生成部５と、初期解および最適解探索の途中で得られた解の中で最も良い解を最良解として格納する最良解格納部６と、最良解格納部６に格納された最良解の一部分を変更して新規解を生成する新規解生成部７と、新規解を格納する新規解格納部８と、新たな最良解を最良解格納部６に格納する最良解更新部９とを備えている。
【００６６】
また、航跡割当装置は、最良解の構成要素をビルディングブロックと判定するビルディングブロック判定部１１と、ビルディングブロックの候補となる構成要素に関するビルディングブロック候補情報を格納するビルディングブロック候補情報格納部１０と、ビルディングブロックと判定された構成要素に関するビルディングブロック情報を格納するビルディングブロック情報格納部１２と、最適解探索を終了するかまたは継続するかを判定する終了判定部１３と、最適解探索を終了すると判定された場合に最終的に得られた最良解を出力する探索結果出力部１４とを備えている。
【００６７】
航跡候補生成部３は、観測値情報格納部２に格納された各時刻の観測値情報を組合せて、複数の移動体の各々が取り得る航跡の候補を航跡候補として生成する。
初期解生成部５は、航跡候補格納部４に格納された航跡候補の集合から最も評価値の良い航跡候補の組合せを最適解として探索する際に、最適解探索の開始時の航跡候補の組合せを初期解として生成する。
【００６８】
新規解生成部７は、ビルディングブロック情報に基づいて、ビルディングブロックと判定された構成要素が必ず含まれるように新規解を生成する。
最良解更新部９は、新規解格納部８に格納された新規解と最良解格納部６に格納された最良解とを比較して、最良解よりも評価値が良い新規解が存在する場合に、当該新規解を新たな最良解として最良解格納部６に格納する。
【００６９】
また、最良解更新部９は、スタート数がＫ個の初期解を用いた（すなわち、最適解探索の実行中にＫ個の最良解が存在する）多スタート局所探索時に、Ｋ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定し、当該ビルディングブロック候補情報をビルディングブロック候補情報格納部１０に登録する。
【００７０】
ビルディングブロック判定部１１は、最良解の構成要素となる航跡候補が最適解の構成要素となり得るか否かを判定し、最適解の構成要素となり得ると判定された最良解の構成要素をビルディングブロックと判定する。
また、ビルディングブロック判定部１１は、最良解更新部による１回の最良解更新で世代が１つ進む条件下で、同一構成要素がＮ世代にわたって連続してビルディングブロック候補と判定された場合に、当該構成要素をビルディングブロックと判定し、当該ビルディングブロック情報をビルディングブロック情報格納部１０に登録する。
【００７１】
この発明の実施の形態１に係る航跡割当装置においては、多スタート局所探索における個々の探索を連携させ、一定世代数にわたって連続して、それぞれの探索で得られる最良解に共通して含まれる構成要素が存在する場合には、その構成要素を、最良解に含まれる構成要素であるビルディングブロックと判定し、以降の新規解生成時にビルディングブロックを必ず解の中に残すようにしている。
すなわち、多スタート局所探索における最良解を構成する要素の中で、ビルディングブロックである可能性が高いと判定したものを次の世代の最良解に必ず残すことができる。
【００７２】
これにより、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されることを回避することができるので、最良解が最適解から遠ざかること、最適解を求めるまでの更新世代数の増加、局所解に陥ること、といった不具合の発生を抑制することができる。
【００７３】
したがって、最終的に得られる解の評価値の良さを表す探索精度を向上させるとともに、探索終了までの更新世代数の少なさに対応する探索速度を向上させることができ、ＭＦＡ問題の最適解探索を精度良く効率的に行うことができる。
【００７４】
実施の形態２．
なお、上記実施の形態１（図１）では、ビルディングブロック判定部１１が多スタート局所探索の各探索で得られた最良解を連携させ「連続Ｎ世代、Ｋスタート中Ｌ個以上の最良解に含まれるビルディングブロック候補」をビルディングブロックと判定したが、ビルディングブロック判定部が各探索の連携を行わずに、各探索に関して独立にビルディングブロック判定を行うように構成してもよい。
【００７５】
図９は独立にビルディングブロックを判定するように構成したこの発明の実施の形態２に係る航跡割当装置の機能構成を示すブロック図であり、前述（図１参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
ここでは、図１とは一部機能が異なる新規解生成部７Ａ、最良解更新部９Ａ、ビルディングブロック候補情報格納部１０Ａおよびビルディングブロック判定部１１Ａのみの動作について説明する。
【００７６】
図９において、新規解生成部７Ａは、最良解格納部６に格納されている最良解の構成要素から新規解生成のためのペア選択を行う。
このペア選択において、新規解生成部７Ａは、まず、ビルディングブロック情報格納部１２に格納されているビルディングブロック情報を参照し、ビルディングブロックである構成要素をペア選択対象外とする。
【００７７】
次に、新規解生成部７Ａは、１個の構成要素を主構成要素として選択し、続いて、別の１個の構成要素を副構成要素として選択する。
このとき、新規解生成部７Ａは、ビルディングブロック候補情報格納部１０Ａに格納されているビルディングブロック候補に関する情報を参照し、最良解の構成要素の中にビルディングブロック候補が存在する場合には、ビルディングブロック候補である構成要素を優先的に主構成要素として選択する。
【００７８】
ここで、ビルディングブロック候補情報には、ビルディングブロック候補に選ばれた回数を示すビルディングブロック候補カウンタ（以下、「ＢＢ候補カウンタ」と略称する）の値が含まれているものとする。
【００７９】
したがって、主構成要素を選択する際に、ビルディングブロック候補が複数存在する場合には、新規解生成部７Ａは、ＢＢ候補カウンタ値の大きな構成要素から順に選択する。
一方、最良解の構成要素にビルディングブロック候補が含まれていなければ、新規解生成部７Ａは、たとえば、ランダムに（または、構成要素の評価値に比例した選択確率にしたがい）主構成要素および副構成要素を選択する。
【００８０】
次に、新規解生成部７Ａは、ペア選択した主構成要素と副構成要素との同じ位置の観測値を入れ替えて新規解を生成し、生成した新規解を新規解格納部８に格納する。この新規解生成処理および新規解格納処理は、前述と同様である。
【００８１】
次に、最良解更新部９Ａは、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解を比較し、以下の処理（ａ）、（ｂ）を行う。
（ａ）まず、最良解よりも評価値が高い新規解が存在する場合には、最良解更新部９Ａは、最も評価値が高い新規解を、次の世代の最良解として最良解格納部６に格納する。
このとき、新規解の生成に用いた主構成要素または副構成要素が、ビルディングブロック候補であれば、当該ビルディングブロック候補のＢＢ候補カウンタの値をリセットし、ビルディングブロック候補情報格納部１０Ａに格納されたビルディングブロック候補情報から、当該ビルディングブロック候補の情報を削除する。
【００８２】
（ｂ）一方、最良解よりも評価値が高い新規解が存在しなかった場合には、最良解更新部９Ａは、新規解生成部７Ａに処理を戻す。
また、同一の主構成要素とペア選択が可能な全ての副構成要素とから生成された全ての新規解から、最良解よりも高い評価値が得られなかった場合には、当該主構成要素をビルディングブロック候補と判定し、当該種構成要素のＢＢ候補カウンタの値を「１」だけ増加させ、当該構成要素およびそのＢＢ候補カウンタ値を、ビルディングブロック候補情報格納部１０Ａに格納する。
【００８３】
以下、図１０および図１１の説明図を参照しながら、図９内の新規解生成部７Ａおよび最良解更新部９Ａの動作について説明する。
図１０は新規解生成部７Ａおよび最良解更新部９Ａの動作を示しており、最良解に含まれるビルディングブロック候補を主構成要素として生成した新規解が、最良解よりも高い評価値を有する場合の例を示している。
【００８４】
新規解生成部７Ａは、最良解格納部６に格納されている最良解を取得し、ビルディングブロック候補情報格納部１０Ａに格納されているビルディングブロック情報を参照して、主構成要素と副構成要素とのペア選択を行う。
【００８５】
図１０において、新規解生成部７Ａは、まず、最良解の構成要素｛２、２、２、３｝がビルディングブロック候補であることから、｛２、２、２、３｝を主構成要素とする。
続いて、新規解生成部７Ａは、他に最良解の構成要素がビルディングブロック候補に含まれないことから、残りの構成要素から何らかの選択確率にしたがって副構成要素を選択する。
【００８６】
このとき、副構成要素の選択に用いられる選択確率は、たとえばランダムに決定されてもよく、構成要素の評価値に比例した選択確率として決定されてもよい。
図１０においては、｛１、１、１、２｝が副構成要素として選択された場合を示している。
続いて、新規解生成部７Ａは、｛２、２、２、３｝と｛１、１、１、２｝とのペアにより新規解を生成し、生成した新規解を新規解格納部８に格納する。
【００８７】
次に、最良解更新部９Ａは、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解とを比較して、最良解よりも評価値が高い新規解が存在した場合には、最も評価値の高い新規解を、新たな最良解として最良解格納部６に格納する。
【００８８】
また、最良解更新部９Ａは、最良解の構成要素であって、且つ、ビルディングブロック候補である構成要素｛２、２、２、３｝を変更して、最良解よりも評価値が高い新規解が得られたことから、構成要素｛２、２、２、３｝は、ビルディングブロックではないと判定する。さらに、構成要素｛２、２、２、３｝をビルディングブロック候補から除外するために、｛２、２、２、３｝のＢＢ候補カウンタの値を「０」にリセットし、｛２、２、２、３｝に関するビルディングブロック候補情報を、ビルディングブロック候補情報格納部１０Ａから削除する。
【００８９】
図１１は新規解生成部７Ａおよび最良解更新部９Ａの他の動作を示しており、最良解に含まれるビルディングブロック候補を主構成要素として生成した新規解の全てが、最良解よりも悪い評価値となった場合の例を示している。
【００９０】
図１１において、新規解生成部７Ａは、前述（図１０）と同様に、まず、最良解の構成要素｛２、２、２、３｝がビルディングブロック候補であることから、｛２、２、２、３｝を主構成要素とする。
続いて、最良解の他の構成要素はビルディングブロック候補に含まれないことから、残りの構成要素から、何らかの選択確率にしたがって副構成要素が選択される。
【００９１】
このときの選択確率は、たとえばランダムでもあってもよく、構成要素の評価値に比例した選択確率としてもよい。
図１１においては、前述（図１０）と同様に、まず、｛１、１、１、２｝が副構成要素として選択された場合を示している。
続いて、新規解生成部７Ａは、｛２、２、２、３｝と｛１、１、１、２｝とのペアにより新規解を生成し、生成した新規解を新規解格納部８に格納する。
【００９２】
次に、最良解更新部９Ａは、最良解格納部６に格納されている最良解と、新規解格納部８に格納されている新規解とを比較する。
この場合、比較の結果、最良解よりも評価値の高い新規解が存在しなかったことから、最良解更新部９Ａは、第１回目に生成した新規解（図１１内の最上段×印）を破棄して、新規解生成部７Ａに処理を戻す。
【００９３】
これにより、新規解生成部７Ａは、主構成要素を｛２、２、２、３｝のままとしつつ、副構成要素を｛３、４、４、４｝に変更して２回目の新規解を生成し、生成した新規解を新規解格納部８に格納する。
最良解更新部９Ａは、前回と同様に２回目の新規解と最良解との比較を行い、最良解よりも評価値の高い新規解が存在しなかったことから、第２回目に生成した新規解（図１１内の２段目×印）を破棄して、再び新規解生成部７Ａに処理を戻す。
【００９４】
これにより、新規解生成部７Ａは、主構成要素は｛２、２、２、３｝のままとしつつ、副構成要素を｛４、３、３、１｝に変更して３回目の新規解を生成し、新規解格納部８に生成した新規解を格納する。
最良解更新部９Ａは、第２回目と同様に新規解と最良解との比較を行い、比較の結果、最良解よりも評価値の高い新規解が存在しなかったことから、第３回目に生成した新規解（図１１内の３段目×印）を破棄する。
【００９５】
以上の処理により、主構成要素を｛２、２、２、３｝として生成される新規解は、全て最良解よりも評価値が悪い結果となったので、最良解更新部９Ａは、｛２、２、２、３｝をビルディングブロック候補と判定し、｛２、２、２、３｝のＢＢ候補カウンタの値を「１」だけ増やして「２」とする。
【００９６】
また、最良解更新部９Ａは、ビルディングブロック候補情報格納部１０Ａに格納されている構成要素｛２、２、２、３｝のＢＢ候補カウンタの値を「２」に更新する。
この時点で、最良解よりも評価値が高い新規解はまだ得られていないので、最良解更新部９Ａは、再び処理を新規解生成部７Ａに戻す。
【００９７】
このとき、新規解生成部７Ａにおいては、｛２、２、２、３｝を主構成要素とした新規解は全て生成済みなので、主構成要素を他の構成要素から選択する。
以下、新規解生成部７Ａおよび最良解更新部９Ａは、前述と同様の処理を繰り返し実行する。
【００９８】
なお、図１０、図１１の例では、ビルディングブロック候補に含まれる最良解の構成要素を主構成要素とした場合を示したが、ビルディングブロック候補に含まれる最良解の構成要素が存在しない場合には、上記例で示した副構成要素の選択と同様にして、主構成要素を選択すればよい。
【００９９】
最後に、ビルディングブロック判定部１１Ａは、ビルディングブロック候補情報格納部１０Ａに格納されているビルディングブロック候補情報を参照して、ＢＢ候補カウンタの値が予め定めた閾値を超えたビルディングブロック候補を「ビルディングブロック」と判定し、判定したビルディングブロックに関する情報を、ビルディングブロック情報格納部１２に格納する。
【０１００】
このとき、前述の実施の形態１（図１、図８）によるビルディングブロック判定部１１は、多スタート局所探索の各探索で得られた最良解を連携させ「連続Ｎ世代、Ｋスタート中のＬ個以上の最良解に含まれるビルディングブロック候補」をビルディングブロックと判定したが、この発明の実施の形態２（図９）によるビルディングブロック判定部１１Ａは、各探索の連携を行わずに、各探索において独立にビルディングブロック判定を行う。
【０１０１】
以上のように、この発明の実施の形態２に係る航跡割当装置（図９〜図１１）の最良解更新部９Ａは、新規解生成部７Ａによる新規解生成処理において、最良解の構成要素の一部分を変更して生成された全ての新規解の評価値が最良解の評価値よりも悪ければ、新規解の生成の元となった構成要素をビルディングブロック候補としてビルディングブロック候補情報格納部１０Ａに登録する。
すなわち、最良解の１個の構成要素を用いて生成される全ての新規解が最良解よりも高い評価値を得られなかった場合には、元となった構成要素をビルディングブロック候補と判定する。
【０１０２】
また、ビルディングブロック判定部１１Ａは、Ｒ回にわたって連続してビルディングブロック候補となった構成要素が存在する場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報をビルディングブロック情報格納部１２に登録する。
すなわち、同一構成要素が一定回数にわたって連続してビルディングブロック候補と判定された場合には、その構成要素をビルディングブロックと判定して、以降の新規解生成処理において、必ずビルディングブロックを新規解に残す。
【０１０３】
これにより、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されて最良解が最適解から遠ざかる現象、最適解を求めるまでの更新世代数が増加する現象および局所解に陥る現象を全て回避して、探索精度および探索速度を向上させることができるという効果がある。
【０１０４】
実施の形態３．
なお、上記実施の形態２では、多スタート局所探索時における処理を具体的に言及しなかったが、多スタート局所探索時において同様の処理を適用してもよい。
以下、多スタート局所探索時に同様の処理を適用したこの発明の実施の形態３について説明する。
【０１０５】
なお、この発明の実施の形態３に係る航跡割当装置は、前述（図９）と同様の構成からなり、ビルディングブロック判定部１１Ａの一部動作のみが異なるのみである。
したがって、ここでは、図９を参照しながら、主にビルディングブロック判定部１１Ａの動作について説明する。
【０１０６】
この発明の実施の形態３において、ビルディングブロック判定部１１Ａは、スタート数Ｋの多スタート局所探索における各探索の第ｎ世代の最良解において、「Ｋ個の最良解のうち、ＢＢ候補カウンタが閾値Ｒを超える共通した構成要素（共通構成要素）を有する最良解がＬ個以上存在する」場合に、当該共通構成要素を「ビルディングブロック」と判定する。
【０１０７】
すなわち、ビルディングブロック判定部１１Ａは、多スタート探索時に、同一構成要素がＲ回にわたって連続して、Ｋ個中のＬ個以上の探索においてビルディングブロック候補となった場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報をビルディングブロック情報格納部１２に登録する。
【０１０８】
この場合、最良解更新部９Ａは、多スタート局所探索時に、個々の最適解探索の処理に応じた新規解生成部による新規解生成処理において、同じ構成要素の一部分を変更して生成された全ての新規解の評価値が最良解の評価値よりも悪ければ、新規解の生成の元となった構成要素に関するビルディングブロック候補情報をビルディングブロック候補情報格納部１０Ａに登録する。
【０１０９】
以上のように、この発明の実施の形態に係る航跡割当装置（図９）は、最良解の１個の構成要素を用いて生成される全ての新規解が最良解よりも高い評価値を得られなかった場合には、元となった構成要素をビルディングブロック候補と判定する。
また、多スタート局所探索における個々の探索を連携させ、同一世代の一定個数以上の最良解に共通するビルディングブロック候補が存在し、且つ、そのビルディングブロック候補のＢＢ候補カウンタが一定値を超えている場合には、そのビルディングブロック候補をビルディングブロックと判定し、以降の新規解生成時にビルディングブロックを必ず解の中に残す。
【０１１０】
これにより、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されることによって最良解が最適解から遠ざかる現象、最適解を求めるまでの更新世代数が増加する現象および局所解に陥る現象を回避して、探索精度（得られる解の評価値の良さ）および探索速度（探索終了までの更新世代数の少なさ）を向上させることができるという効果がある。
【０１１１】
実施の形態４．
なお、上記実施の形態３では、特に言及しなかったが、図１２のように、優先変更対象判定部１５および優先変更対象格納部１６を追加し、多スタート局所探索において、ビルディングブロックでない同一の構成要素が一定数以上の最良解に含まれる場合に、いくつかの探索で優先的に当該構成要素を変更対象としてペア選択するように構成してもよい。
図１２はこの発明の実施の形態３に係る航跡割当装置の機能構成を示すブロック図であり、前述（図９参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
【０１１２】
図１２において、優先変更対象判定部１５は、初期解生成部５と新規解生成部７Ｂとの間に挿入されており、終了判定部の判定結果に応答する。
優先変更対象格納部１６は、優先変更対象判定部１５で判定された優先変更対象情報を格納し、格納データを新規解生成部７Ｂに提供する。
【０１１３】
この場合、前述（図９）との相違点は、優先変更対象判定部１５および優先変更対象格納部１６を新たに追加したことに加えて、新規解生成部７Ｂの一部機能が異なることである。
したがって、以下、図１２を参照しながら、主に優先変更対象判定部１５、優先変更対象格納部１６および新規解生成部７Ｂの動作について説明する。
【０１１４】
まず、優先変更対象判定部１５は、スタート数がＫ個の多スタート局所探索の実行時において、最良解格納部６に格納されているＫ個の最良解に共通して含まれる構成要素（共通構成要素）を探索し、Ｋ個中にＳ個以上の最良解に共通構成要素が存在する場合であって、且つ、共通構成要素がビルディングブロックでない場合には、当該最良解の数をＭ個とすると、Ｍ個の当該最良解からＭ−（Ｓ−１）個を選択する。
【０１１５】
続いて、優先変更対象判定部１５は、選択した最良解の共通構成要素を優先変更対象と判定し、優先変更対象を含む最良解のスタート番号（スタート数が「３」であれば、スタート番号は「１」、「２」、「３」となる）と、優先変更対象となった共通構成要素を優先変更対象情報として優先変更対象格納部１６に格納する。
【０１１６】
次に、新規解生成部７Ｂは、優先変更対象格納部１６に格納されている優先変更対象情報を参照し、自分のスタート番号が優先変更対象情報に含まれている場合には、ペア選択において、優先変更対象の構成要素を主構成要素として選択する。
以降の新規解生成部７Ｂの処理については、前述の実施の形態２で述べた内容と同じなので、ここでは省略する。
【０１１７】
なお、新規解生成部７Ｂは、優先変更対象が存在しない場合か、または、ペア選択処理の未実行の優先変更対象が残っていない場合であれば、前述の実施の形態２で述べたように、ビルディングブロック候補を優先的に主構成要素として選択する。
すなわち、ペア選択における主構成要素の選択優先順位は、（１）「優先変更対象の構成要素」、（２）「ビルディングブロック候補」、（３）「それ以外の構成要素」の順となる。ただし、「ビルディングブロック」は、選択対象から除外される。
【０１１８】
次に、図１３の説明図を参照しながら、優先変更対象判定部１５の動作について説明する。
図１３はスタート数が「５」の場合を示しており、５個の最良解のうちの４個にビルディングブロックでない構成要素｛１、１、１、２｝が含まれている場合の動作例を示している。
【０１１９】
図１３において、優先選択対象の判定条件を、「Ｋ（＝５）個中のＳ（＝２）個以上の最良解にビルディングブロックでない構成要素が含まれている場合」とすると、構成要素｛１、１、１、２｝は、Ｓ（＝２）個を超えるＭ（＝４）個の最良解に含まれている。
したがって、優先変更対象判定部１５は、構成要素｛１、１、１、２｝を含む最良解の中から、Ｍ−（Ｓ−１）（＝３）個の最良解を選択する。
図１３においては、破線矢印で示すように、スタート１、スタート２およびスタート５の３個の最良解が選択されている。
【０１２０】
次に、優先変更対象判定部１５は、｛１、１、１、２｝のパターンと、選択したスタート番号「１」、「２」、「５」をまとめて、優先変更対象情報として優先変更対象格納部１６に格納する。
【０１２１】
以上のように、この発明の実施の形態４に係る航跡割当装置（図１２、図１３）は、最良解格納部６に格納された最良解の構成要素の中から、新規解を生成する際の優先変更対象を選択する優先変更対象判定部１５と、優先変更対象判定部１５が優先変更対象と判定した構成要素に関する情報を優先変更対象情報として格納する優先対象格納部１６とを備えている。
【０１２２】
優先変更対象判定部１５は、多スタート探索時に、Ｋ個の最良解のうちのＭ個以上の最良解に同一構成要素が存在する場合に、Ｍ個の当該最良解からＳ個を選択し、選択したＳ個の最良解に含まれる同一構成要素に関する情報を優先変更対象情報として優先変更対象格納部１６に登録する。
【０１２３】
また、新規解生成部７Ｂは、優先変更対象格納部１６に格納された優先変更対象情報を参照し、優先変更対象とした構成要素の一部を変更して新規解を生成する。
すなわち、新規解生成部７Ｂは、多スタート局所探索において、ビルディングブロックでない同一の構成要素が一定数以上の最良解に含まれる場合に、新規解生成の処理実行時において、いくつかの探索で優先的に当該構成要素を変更対象としてペア選択する。
【０１２４】
これにより、各探索が解空間中の同じ範囲を探索することを防ぐことができ、各探索が異なる範囲を探索することにより、広い範囲の解空間の探索を可能とすることができる。
また、ビルディングブロックの判定を行い、新規解生成時にビルディングブロックを必ず解の中に残すことにより、前述と同様に、最適解探索の途中において、新規解生成時にビルディングブロックが破壊されることによって最良解が最適解から遠ざかる現象、最適解を求めるまでの更新世代数が増加する現象および局所解に陥る現象を回避して、探索精度（得られる解の評価値の良さ）および探索速度（探索終了までの更新世代数の少なさ）を向上させることができる。
【０１２５】
なお、上記実施の形態４では、実施の形態３の構成に適用した場合を例にとって説明したが、前述の実施の形態１、２にも適用可能なことは言うまでもない。
【図面の簡単な説明】
【０１２６】
【図１】この発明の実施の形態１に係る航跡割当装置の機能構成を示すブロック図である。
【図２】図１内の観測値情報取得部により取得される観測値を図式的に示す説明図である。
【図３】図１内の観測値情報格納部による観測値情報の格納状態を図式的に示す説明図である。
【図４】図１内の航跡候補生成部による処理動作を図式的に示す説明図である。を示している。
【図５】図１内の初期解生成部による初期解生成動作を図式的に示す説明図である。
【図６】図１内の新規解生成部および最良解更新部による処理動作を図式的に示す説明図である。
【図７】図１内の最良解更新部によるビルディングブロック候補による判定処理動作を図式的に示す説明図である。
【図８】図１内のビルディングブロック判定部による判定処理を図式的に示す説明図である。
【図９】この発明の実施の形態２に係る航跡割当装置の機能構成を示すブロック図である。
【図１０】図９内の新規解生成部および最良解更新部による処理動作を図式的に示す説明図である。
【図１１】図９内の新規解生成部および最良解更新部による他の処理動作を図式的に示す説明図である。
【図１２】この発明の実施の形態４に係る航跡割当装置の機能構成を示すブロック図である。
【図１３】図１２内の優先変更対象判定部による判定処理動作を図式的に示す説明図である。
【図１４】従来の航跡割当装置による処理動作を図式的に示す説明図であり、第ｎ世代の最良解と更新後（第ｎ＋１世代）の最適解との関係を示している。
【符号の説明】
【０１２７】
１ 観測値情報取得部、２ 観測値情報格納部、３ 航跡候補生成部、４ 航跡候補格納部、５ 初期解生成部、６ 最良解格納部、７、７Ａ、７Ｂ 新規解生成部、８ 新規解格納部、９、９Ａ 最良解更新部、１０、１０Ａ ビルディングブロック候補情報格納部、１１、１１Ａ ビルディングブロック判定部、１２ ビルディングブロック情報格納部、１３ 終了判定部、１４ 探索結果出力部。
【特許請求の範囲】
【請求項１】
観測センサにより観測される時間的に連続した観測値情報を用いて複数の移動体の航跡を追尾するために、前記観測値情報の各々を前記複数の移動体の各航跡に割り当てる航跡割当装置であって、
前記観測センサを用いて前記観測値情報を取得する観測値情報取得部と、
前記観測値情報取得部が取得した前記観測値情報を格納する観測値情報格納部と、
前記観測値情報格納部に格納された各時刻の観測値情報を組合せて、前記複数の移動体の各々が取り得る航跡の候補を航跡候補として生成する航跡候補生成部と、
前記航跡候補を格納する航跡候補格納部と、
前記航跡候補格納部に格納された航跡候補の集合から最も評価値の良い航跡候補の組合せを最適解として探索する際に、最適解探索の開始時の航跡候補の組合せを初期解として生成する初期解生成部と、
前記初期解を格納するとともに、前記最適解探索の途中で得られた解の中で最も良い解を最良解として格納する最良解格納部と、
前記最良解格納部に格納された最良解の一部分を変更し、新たな解を新規解として生成する新規解生成部と、
前記新規解を格納する新規解格納部と、
前記新規解格納部に格納された新規解と前記最良解格納部に格納された最良解とを比較して、最良解よりも評価値が良い新規解が存在する場合に、当該新規解を新たな最良解として前記最良解格納部に格納する最良解更新部と、
前記最良解の構成要素となる航跡候補が前記最適解の構成要素となり得るか否かを判定し、前記最適解の構成要素となり得ると判定された最良解の構成要素をビルディングブロックと判定するビルディングブロック判定部と、
前記ビルディングブロックの候補となる構成要素に関するビルディングブロック候補情報を格納するビルディングブロック候補情報格納部と、
前記ビルディングブロックと判定された構成要素に関するビルディングブロック情報を格納するビルディングブロック情報格納部と、
前記最適解探索を終了するかまたは継続するかを判定する終了判定部と、
前記最適解探索を終了すると判定された場合に、最終的に得られた最良解を出力する探索結果出力部と
を備え、
前記新規解生成部は、前記ビルディングブロック情報に基づいて、前記ビルディングブロックと判定された構成要素が必ず含まれるように前記新規解を生成し、
前記最良解更新部は、スタート数がＫ個の初期解を用いた（すなわち、最適解探索の実行中にＫ個の最良解が存在する）多スタート局所探索時に、Ｋ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定し、当該ビルディングブロック候補情報をビルディングブロック候補情報格納部に登録し、
前記ビルディングブロック判定部は、前記最良解更新部による１回の最良解更新で世代が１つ進む条件下で、同一構成要素がＮ世代にわたって連続してビルディングブロック候補と判定された場合に、当該構成要素をビルディングブロックと判定し、当該ビルディングブロック情報を前記ビルディングブロック情報格納部に登録する
ことを特徴とする航跡割当装置。
【請求項２】
前記最良解更新部は、前記新規解生成部による新規解生成処理において、前記最良解の構成要素の一部分を変更して生成された全ての新規解の評価値が前記最良解の評価値よりも悪ければ、前記新規解の生成の元となった構成要素をビルディングブロック候補として前記ビルディングブロック候補情報格納部に登録し、
前記ビルディングブロック判定部は、Ｒ回にわたって連続してビルディングブロック候補となった構成要素が存在する場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報を前記ビルディングブロック情報格納部に登録する
ことを特徴とする請求項１に記載の航跡割当装置。
【請求項３】
前記最良解更新部は、前記多スタート局所探索時に、個々の最適解探索の処理に応じた前記新規解生成部による新規解生成処理において、同じ構成要素の一部分を変更して生成された全ての新規解の評価値が前記最良解の評価値よりも悪ければ、前記新規解の生成の元となった構成要素に関するビルディングブロック候補情報を前記ビルディングブロック候補情報格納部に登録し、
前記ビルディングブロック判定部は、前記多スタート探索時に、同一構成要素がＲ回にわたって連続して、Ｋ個中のＬ個以上の探索においてビルディングブロック候補となった場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報を前記ビルディングブロック情報格納部に登録する
ことを特徴とする請求項１に記載の航跡割当装置。
【請求項４】
前記最良解格納部に格納された最良解の構成要素の中から、前記新規解を生成する際の優先変更対象を選択する優先変更対象判定部と、
前記優先変更対象判定部が優先変更対象と判定した構成要素に関する情報を優先変更対象情報として格納する優先対象格納部と
を備え、
前記優先変更対象判定部は、前記多スタート探索時に、Ｋ個の最良解のうちのＭ個以上の最良解に同一構成要素が存在する場合に、Ｍ個の当該最良解からＳ個を選択し、選択したＳ個の最良解に含まれる同一構成要素に関する情報を前記優先変更対象情報として前記優先変更対象格納部に登録し、
前記新規解生成部は、前記優先変更対象格納部に格納された優先変更対象情報を参照し、前記優先変更対象とした構成要素の一部を変更して前記新規解を生成する
ことを特徴とする請求項１から請求項３までのいずれか１項に記載の航跡割当装置。
【請求項１】
観測センサにより観測される時間的に連続した観測値情報を用いて複数の移動体の航跡を追尾するために、前記観測値情報の各々を前記複数の移動体の各航跡に割り当てる航跡割当装置であって、
前記観測センサを用いて前記観測値情報を取得する観測値情報取得部と、
前記観測値情報取得部が取得した前記観測値情報を格納する観測値情報格納部と、
前記観測値情報格納部に格納された各時刻の観測値情報を組合せて、前記複数の移動体の各々が取り得る航跡の候補を航跡候補として生成する航跡候補生成部と、
前記航跡候補を格納する航跡候補格納部と、
前記航跡候補格納部に格納された航跡候補の集合から最も評価値の良い航跡候補の組合せを最適解として探索する際に、最適解探索の開始時の航跡候補の組合せを初期解として生成する初期解生成部と、
前記初期解を格納するとともに、前記最適解探索の途中で得られた解の中で最も良い解を最良解として格納する最良解格納部と、
前記最良解格納部に格納された最良解の一部分を変更し、新たな解を新規解として生成する新規解生成部と、
前記新規解を格納する新規解格納部と、
前記新規解格納部に格納された新規解と前記最良解格納部に格納された最良解とを比較して、最良解よりも評価値が良い新規解が存在する場合に、当該新規解を新たな最良解として前記最良解格納部に格納する最良解更新部と、
前記最良解の構成要素となる航跡候補が前記最適解の構成要素となり得るか否かを判定し、前記最適解の構成要素となり得ると判定された最良解の構成要素をビルディングブロックと判定するビルディングブロック判定部と、
前記ビルディングブロックの候補となる構成要素に関するビルディングブロック候補情報を格納するビルディングブロック候補情報格納部と、
前記ビルディングブロックと判定された構成要素に関するビルディングブロック情報を格納するビルディングブロック情報格納部と、
前記最適解探索を終了するかまたは継続するかを判定する終了判定部と、
前記最適解探索を終了すると判定された場合に、最終的に得られた最良解を出力する探索結果出力部と
を備え、
前記新規解生成部は、前記ビルディングブロック情報に基づいて、前記ビルディングブロックと判定された構成要素が必ず含まれるように前記新規解を生成し、
前記最良解更新部は、スタート数がＫ個の初期解を用いた（すなわち、最適解探索の実行中にＫ個の最良解が存在する）多スタート局所探索時に、Ｋ個の最良解のうちのＬ個以上の最良解に同じ構成要素が含まれる場合に、当該構成要素をビルディングブロック候補と判定し、当該ビルディングブロック候補情報をビルディングブロック候補情報格納部に登録し、
前記ビルディングブロック判定部は、前記最良解更新部による１回の最良解更新で世代が１つ進む条件下で、同一構成要素がＮ世代にわたって連続してビルディングブロック候補と判定された場合に、当該構成要素をビルディングブロックと判定し、当該ビルディングブロック情報を前記ビルディングブロック情報格納部に登録する
ことを特徴とする航跡割当装置。
【請求項２】
前記最良解更新部は、前記新規解生成部による新規解生成処理において、前記最良解の構成要素の一部分を変更して生成された全ての新規解の評価値が前記最良解の評価値よりも悪ければ、前記新規解の生成の元となった構成要素をビルディングブロック候補として前記ビルディングブロック候補情報格納部に登録し、
前記ビルディングブロック判定部は、Ｒ回にわたって連続してビルディングブロック候補となった構成要素が存在する場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報を前記ビルディングブロック情報格納部に登録する
ことを特徴とする請求項１に記載の航跡割当装置。
【請求項３】
前記最良解更新部は、前記多スタート局所探索時に、個々の最適解探索の処理に応じた前記新規解生成部による新規解生成処理において、同じ構成要素の一部分を変更して生成された全ての新規解の評価値が前記最良解の評価値よりも悪ければ、前記新規解の生成の元となった構成要素に関するビルディングブロック候補情報を前記ビルディングブロック候補情報格納部に登録し、
前記ビルディングブロック判定部は、前記多スタート探索時に、同一構成要素がＲ回にわたって連続して、Ｋ個中のＬ個以上の探索においてビルディングブロック候補となった場合に、当該構成要素をビルディングブロックと判定し、当該構成要素に関するビルディングブロック情報を前記ビルディングブロック情報格納部に登録する
ことを特徴とする請求項１に記載の航跡割当装置。
【請求項４】
前記最良解格納部に格納された最良解の構成要素の中から、前記新規解を生成する際の優先変更対象を選択する優先変更対象判定部と、
前記優先変更対象判定部が優先変更対象と判定した構成要素に関する情報を優先変更対象情報として格納する優先対象格納部と
を備え、
前記優先変更対象判定部は、前記多スタート探索時に、Ｋ個の最良解のうちのＭ個以上の最良解に同一構成要素が存在する場合に、Ｍ個の当該最良解からＳ個を選択し、選択したＳ個の最良解に含まれる同一構成要素に関する情報を前記優先変更対象情報として前記優先変更対象格納部に登録し、
前記新規解生成部は、前記優先変更対象格納部に格納された優先変更対象情報を参照し、前記優先変更対象とした構成要素の一部を変更して前記新規解を生成する
ことを特徴とする請求項１から請求項３までのいずれか１項に記載の航跡割当装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１０−６６２２３（Ｐ２０１０−６６２２３Ａ）
【公開日】平成２２年３月２５日（２０１０．３．２５）
【国際特許分類】
【出願番号】特願２００８−２３５２０８（Ｐ２００８−２３５２０８）
【出願日】平成２０年９月１２日（２００８．９．１２）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２２年３月２５日（２０１０．３．２５）
【国際特許分類】
【出願日】平成２０年９月１２日（２００８．９．１２）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]