航跡割当装置
【課題】組合せ最適化問題を解くメタヒューリスティックス手法を用いて航跡割当問題の一つであるＭＦＡ問題の解を高速に求める航跡割当装置を提供する。
【解決手段】測定して蓄積された移動体の航跡に関する観測データに基づき、予め定められた制約条件に違反しない複数の航跡候補を割当パターン群として生成し、この生成された割当パターン群を構成する各割当パターンに対し、航跡の始点に基づくグループに分類し、各グループの各割当パターンに対して一意の番号を付与する航跡候補群生成手段３，４と、各割当パターンに付与された番号に基づき、組合せ最適化を図るメタヒューリスティックス手法によって観測値を航跡に割り当てる航跡割当処理を行う航跡割当処理手段５〜１０とを有することを特徴とする航跡割当装置にある。
【解決手段】測定して蓄積された移動体の航跡に関する観測データに基づき、予め定められた制約条件に違反しない複数の航跡候補を割当パターン群として生成し、この生成された割当パターン群を構成する各割当パターンに対し、航跡の始点に基づくグループに分類し、各グループの各割当パターンに対して一意の番号を付与する航跡候補群生成手段３，４と、各割当パターンに付与された番号に基づき、組合せ最適化を図るメタヒューリスティックス手法によって観測値を航跡に割り当てる航跡割当処理を行う航跡割当処理手段５〜１０とを有することを特徴とする航跡割当装置にある。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、組合せ最適化問題を解くメタヒューリスティックス手法を用いて航跡割当問題の一つであるＭＦＡ問題の解を高速に求める航跡割当装置に関する。
【背景技術】
【０００２】
レーダの観測値から、飛行中の複数の航空機の航跡を推測する航跡追尾処理を構成する一つの処理として航跡割当処理がある。一回のレーダ観測で得られた観測値の集合を観測フレームと呼び、航跡割当は、観測フレーム内の観測値を複数ある航跡のいずれか一つに割り当てる処理である(新規航跡の始点とする場合もある)。例えば、下記特許文献１では、最新の一つの観測フレーム内の観測値を航跡に割り当てるＭＨＴ法を適用した目標追尾装置が提案されている。
【０００３】
ＭＨＴ法のように一つの観測フレームを用いた航跡割当では十分な航跡追尾精度が得られないため、より高い精度の航跡追尾処理が望まれている。このためには連続した複数の観測フレームを用いた航跡割当処理が必要であり、これは、連続した複数の観測フレームに対して航跡割当を行うＭＦＡ(Multiple Frame Assignment)問題を解くことで実現できる。しかし、ＭＦＡ問題は、ＭＨＴ法のような一つの観測フレームの割当処理に比べて考慮する航跡候補数が爆発的に増加するため、厳密に最適な解を求めようとすると処理に長時間を要し、実用面で問題を生じる。
【０００４】
そこで、運用上問題ない解が求まれば必ずしも最適解でなくても良いという考えに立ち、組合せ最適化問題を高速に解くアルゴリズムの適用が提案されている。例えば非特許文献１では、ラグランジュ緩和法を適用することで解の探索空間の絞込みを行い処理の高速化を図っている。
【０００５】
【特許文献１】特許第３１４５８９３号明細書
【非特許文献１】Aubrey B. Poore、”A New Multidimensional Data Association Algorithm for Multisensor-Multitarget Tracking”、Proc. of SPIE Vol. 2561、1995
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、ラグランジュ緩和法は対象問題の次元数(ＭＦＡ問題の場合はフレーム数)が大きくなると処理が煩雑になり、実装が難しくなるという問題がある。また、探索範囲を絞り込むための制約条件の緩和の仕方によっては効果的な絞込みが行えないという問題もある。
【０００７】
ラグランジュ緩和法よりもアルゴリズムが単純で実装が容易であり、且つ、ＭＦＡ問題を高速に解くことが期待できるアルゴリズムに組合せ最適化のメタヒューリスティクス手法がある。主要なアルゴリズムとしては、遺伝的アルゴリズム、タブーサーチ、シミュレーテッド・アニーリングなどが挙げられる。組合せ最適化のメタヒューリスティックス手法を適用することでより効率良くＭＦＡ問題を解くことが期待できるが、ＭＦＡ問題の制約条件の一つであるゲート条件の存在により、効率的な探索が行えない可能性がある。
【０００８】
図１２は航跡割当例を示したものである。時刻ｔ〜時刻ｔ＋３の４つの観測フレーム内の各観測点がＸ−Ｙ平面上に分布している。これら４つの観測フレームの各観測値を重複が無いように結ぶことで４本の航跡への各観測値の割当が行われる。
【０００９】
メタヒューリスティックス手法を用いて最適な航跡割当の探索を行う場合、一般的には現時点で得られている最良解の一部を変更した解(新規解と呼ぶ)を複数生成し、最良解よりも評価値の良い新規解が得られれば、その新規解を最良解とするという処理を繰り返し実行することで最適な割当を求める。例えば、図１２に示した割当結果を現時点の最良解とし、最良解のフレームｔの２番の観測値からフレームｔ＋１の２番の観測値へのリンクと、フレームｔの４番の観測値からフレームｔ＋１の３番の観測値へのリンクを変更し、フレームｔの２番の観測値からフレームｔ＋１の３番の観測値へのリンクと、フレームｔの４番の観測値からフレームｔ＋１の２番の観測値へのリンクとすることで、図１３に示す新規解を生成する。このような部分的な変更による新規解を複数生成し、現時点での最良解よりも良い解の探索を行う。
【００１０】
しかし、ＭＦＡ問題にはゲート条件と呼ばれる制約条件が存在し、上記のようなリンクの変更を行った際、ゲート条件違反が発生し、得られた解が実行不可能な解となってしまう場合がある。
【００１１】
ここで、図１４および図１５を用いてゲート条件を説明する。ゲート条件とは、ある観測フレーム内の観測値から次の観測フレーム内の観測値に航跡を伸長する際に伸長可能な観測値をゲートと呼ばれる範囲内に含まれるものに限定するものであり、例えば、図１４のフレームｔ＋２の１番の観測点から伸長できる、フレームｔ＋３内の観測値は、ゲート範囲内に含まれる１番と２番となる。なお、ゲート範囲はそれまでに得られている航跡によってその範囲が異なり、図１５に示した航跡が得られている場合には、図１４と同じフレームｔ＋２の１番の観測点からのゲート範囲は図１４のものとは異なり、伸長可能なフレームｔ＋３の観測点は１番のみとなる。
【００１２】
すなわち、最良解のリンクを一部張り替えることで航跡の構成が変更され、ゲート条件が変わってしまう。ゲート条件が変わるとゲート条件違反が発生してしまう可能性もある。ゲート条件が発生した場合はゲート条件違反を解消しなければならないが、現在の違反箇所を修正するようリンクの変更を行うと、また別の箇所でゲート条件違反が発生し、それを解消するとまた別の箇所で違反が発生するというように、ゲート条件違反の解消処理を何度も繰り返し行わなければならなくなる。
【００１３】
メタヒューリスティクス手法による最適解探索は、最良解の部分的な変更を繰り返すことに特徴があり、上記のようにゲート条件違反の解消処理が繰り返されることは最良解の部分的な変更とはならず、効率的な探索が行えないという問題がある。
【００１４】
この発明は上記のような問題点を解決するためになされたもので、ＭＦＡ問題を高速に解き、且つ、ラグランジュ緩和法に比べてアルゴリズムが単純で実装が容易である、組合せ最適化のメタヒューリスティックス手法を適用した航跡割当装置を提案することを目的としている。
【課題を解決するための手段】
【００１５】
この発明は、測定して蓄積された移動体の航跡に関する観測データに基づき、予め定められた制約条件に違反しない複数の航跡候補を割当パターン群として生成し、この生成された割当パターン群を構成する各割当パターンに対し、航跡の始点に基づくグループに分類し、各グループの各割当パターンに対して一意の番号を付与する航跡候補群生成手段と、各割当パターンに付与された番号に基づき、組合せ最適化を図るメタヒューリスティックス手法によって観測値を航跡に割り当てる航跡割当処理を行う航跡割当処理手段とを有することを特徴とする航跡割当装置にある。
【発明の効果】
【００１６】
この発明では、組合せ最適化問題を解くメタヒューリスティックス手法を用いて航跡割当問題の一つであるＭＦＡ問題の解を高速に求める航跡割当装置を提供することができる。
【発明を実施するための最良の形態】
【００１７】
実施の形態１．
図１は、この発明の実施の形態１における航跡割当装置の構成を示すブロック図であり、例えばコンピュータとメモリにより構成される。図１において、観測データ収集部１は、レーダ等により観測された飛行物体等の移動体の観測値のデータを収集する装置である。観測データ蓄積部２は、観測データ収集部１により収集された観測値を観測データとして蓄積する装置である。航跡候補群生成部３は、観測データ蓄積部２に蓄積された観測値データ、および航跡平滑値格納部１０に格納される平滑値情報より、ゲート条件と呼ばれる制約条件に違反しない航跡候補を全て生成し(航跡候補を割当パターンと呼ぶ場合もある)、航跡候補群を構成する航跡候補を、始点が同じものでグループ化する装置である。航跡候補群格納部４は、航跡候補群生成部３において生成された航跡候補群を格納する装置である。
【００１８】
初期解生成部５は、航跡候補群格納部４に格納された航跡候補群の中から航跡グループ毎に一つずつ航跡候補を選択し、最適な航跡候補の組合せ(以降、航跡候補の組合せ「解」と呼ぶ)を探索するための初期解を生成する装置である。初期解格納部６は、初期解生成部５で生成された初期解を格納する装置である。
【００１９】
最適解探索部７は、初期解格納部６に格納された初期解を最初の最良解とし、最良解の一部分を変更した複数の解を新たに生成する「新規解生成」と、現時点の最良解よりも評価値が良い新規解が存在する場合、評価値が最も良い新規解を新たな最良解とする「解更新」の２つの処理を、解の更新がされなくなるまで交互に繰り返すことで最適解の探索を行う装置である。最良解格納部８は、最適解探索部７における処理で最終的に得られた解を格納する装置である。航跡平滑化処理部９は、最良解格納部８に格納された解に示される航跡割当結果を用いて航跡平滑値を更新する装置である。航跡平滑値格納部１０は、航跡平滑化処理部９の処理結果を格納する装置である。
【００２０】
なお、観測データ収集部１と観測データ蓄積部２が観測データ収集手段を構成する。また、航跡候補群生成部３と航跡候補群格納部４が航跡候補群生成手段を構成する。一方、初期解生成部５と初期解格納部６が初期解生成手段を構成し、最適解探索部７と最良解格納部８が最適解探索手段を構成し、航跡平滑化処理部９と航跡平滑値格納部１０が航跡平滑化処理手段を構成する。そして上記初期解生成手段、最適解探索手段及び航跡平滑化処理手段が航跡割当処理手段を構成する。
【００２１】
次に図１の構成を有する航跡割当装置の一連の動作について説明する。まず、航跡割当装置は、例えばレーダ(図示省略)により観測された飛翔体、例えば航空機の航跡に関する観測値を観測データとして観測データ収集部１により収集し、観測データ蓄積部２に蓄積する。観測データは、観測時刻毎にまとめられ、一時刻分の観測データの集合を観測フレームと呼ぶ(以降、単にフレームと記述する場合もある)。図２は、観測フレームの例を示した図で、時刻ｔ〜時刻ｔ＋３の間に観測された観測値を二次元平面上に表示したものである。フレームｔの破線枠で囲まれているものは時刻ｔの観測フレームに含まれる観測値であり、フレームｔ＋１〜ｔ＋３も同様である。なお、各フレーム内の観測値には１〜４の番号が振られているが、これは単に識別のために付けた番号であり、各フレームの同じ番号の観測値が同じ航跡に含まれるという意味ではない。観測データ収集部１では、図２に示したような観測データをフレーム単位に観測データ蓄積部２に蓄積する。なお、各観測値には、例えば、飛行物体の飛行速度、進行方向、位置などの情報が含まれる。
【００２２】
次に、航跡候補群生成部３が、以下に示す手順に従って航跡候補群を生成し、航跡候補群格納部４に格納する。なお、航跡候補群とは、観測データを基に生成した、ゲート条件を満たす航跡候補(割当パターンとも呼ぶ)の集合である。
【００２３】
以下に、航跡候補群生成の手順を示す。
＜航跡候補群生成手順＞
Ｓｔｅｐ１． 航跡候補群生成部３は、観測データ蓄積部２から最新のＮフレーム分(Ｎは正の整数で、Ｎの値は問題設定により変わる)のデータを取得し、さらに航跡平滑値格納部１０より、前回の航跡割当処理後の航跡平滑値を取得する。航跡平滑値は、航跡毎に、割当が確定された部分(以降の処理で割当変更を行わない部分)を構成する複数の観測値の情報を平滑化し一つの観測値としてまとめたものである(以降、航跡平滑値は単に平滑値と呼ぶ)。図３は、時刻ｔ〜ｔ＋３の４つの観測フレームに対して航跡割当を行う場合の取得データ例を示したものであり、最初に平滑値データ、以降に観測時刻順にフレームが並んでいる。
Ｓｔｅｐ２． 航跡候補群生成部３は、Ｓｔｅｐ１において取得した観測データより、各平滑値を始点とする、ゲート条件に違反しない、割当パターンを全て生成する。生成された割当パターンの集合を航跡候補群と呼ぶ。図４に割当パターンの例を示す。図３に示した取得データにおいて、図４の航跡１１がゲート条件に違反しない航跡候補の一つであるとすると、この航跡候補１１に対して、割当パターン１２を生成する。割当パターン１２における数字は各フレームにおける航跡候補１１を構成する観測値の番号であり、先頭は平滑値、２番目以降は観測時刻の早いフレーム順の並びとなっている。
Ｓｔｅｐ３． Ｓｔｅｐ２において抽出した航跡候補群を、始点を同じとする割当パターン同士をグルーピングする。図５に、図３に示した取得データに対する航跡候補群のグルーピング例を示す。先頭の数字が同じ割当パターンを同じグループとしている。
Ｓｔｅｐ４． Ｓｔｅｐ３においてグルーピングした航跡候補群に対して、グループ内の割当パターンが一意に識別できるように各割当パターンに番号を付与する。この番号を割当パターン番号と呼ぶ。図６に割当パターン番号付与の例を示す。図６では、各航跡グループ内の割当パターンに対して、１から順に番号を付与している。
Ｓｔｅｐ５． Ｓｔｅｐ４で割当パターン番号を付与した航跡候補群を、航跡候補群格納部４に格納する。
【００２４】
次に、初期解生成部５が、メタヒューリスティックス手法による航跡割当処理のための初期解を生成し、初期解格納部６に生成した初期解を格納する。ＭＦＡ問題の解は、航跡候補群の中から、航跡グループ毎に一つずつ割当パターンを選択することで構成されるが、この発明における航跡割当装置では、さらに前述の割当パターン番号を利用してＭＦＡ問題の解を間接的に表現することを特徴とする。図７に、航跡候補群からのＭＦＡ問題の解の構成と、メタヒューリスティックス手法を適用するための解表現の例を示す。図７の航跡候補群１３は、航跡候補群生成部３により生成された航跡候補群である。ＭＦＡ問題の解は、航跡候補群１３から、航跡グループ毎に一つずつ割当パターンを選択した物となり、図７のＭＦＡの解１４が一つの解の例を示している。このＭＦＡの解１４は、横一列が一つの航跡を構成する各観測フレームの観測値を表している。なお、ＭＦＡの解１４の右端にある丸で囲まれた数字は、割当パターン番号である。
【００２５】
ＭＦＡの解１４は直接的な表現であり、２次元の配列となっている。これを、よりメタヒューリスティックス手法が適用しやすい形の間接的な表現にしたものが、メタヒューリスティックスにおける解表現１５である。メタヒューリスティックスにおける解表現１５では、ＭＦＡの解１４を構成する割当パターンの割当パターン番号の並びでＭＦＡ問題の解を表現する。
【００２６】
初期解の生成方法には複数の方式が考えられるが、以下にＧＲＡＳＰ(Greedy Randoized Adaptive Search Procedure)手法の初期解生成を応用した手順を示す。
＜初期解生成手順＞
Ｓｔｅｐ１． 航跡候補群に含まれる割当パターンの最大コストＣｍａｘと最小コストＣｍｉｎを求める。
Ｓｔｅｐ２． 航跡候補群に含まれるｉ番目の割当パターンのコストをＣｉとし、式(１)を満たす割当パターンを全て選択候補リストに加える。
Ｃｍｉｎ≦Ｃｉ≦Ｃｍｉｎ＋α(Ｃｍａｘ−Ｃｍｉｎ) (１)
Ｓｔｅｐ３． 選択候補リストの中からランダムに一つ割当パターンを選択し、解の構成要素とする。解が完成したら終了し、そうでなければＳｔｅｐ４に進む。
Ｓｔｅｐ４． 選択候補リストを空にし、解の構成要素となっている割当パターンおよびそれらと同じ航跡グループに属する割当パターン、更に解の構成要素となっている割当パターンと航跡を構成する観測値が重複する割当パターンを航跡候補群から除外し(航跡候補群の更新)、Ｓｔｅｐ１に戻る。
【００２７】
以上の手順のＳｔｅｐ２〜Ｓｔｅｐ４の概要を図８に示す。まず、初期解生成手順を実行する前に航跡候補群生成部３において生成された航跡候補群が航跡候補群１３である。この航跡候補群１３の中から、Ｓｔｅｐ２の処理により求めたコストが式(１)を満たす割当パターンの集合が選択候補リスト１６である。なお、選択候補リスト１６の右端のＧ１やＧ２などの表記は、その割当パターンが属する航跡グループを示している。
【００２８】
Ｓｔｅｐ３では、この選択候補リスト１６の中からランダムに一つ割当パターンを選択する。図８では、選択候補リスト１６の上から３番目の航跡グループ２の割当パターン番号１の割当パターンが選択された場合を示している。従って、同じＳｔｅｐ３の処理において、メタヒューリスティックスにおける解表現１７には、航跡グループ２に対応する左から２番目の位置に割当パターン番号１が追加される。
【００２９】
Ｓｔｅｐ４では、Ｓｔｅｐ３で選択された航跡グループ２の割当パターン番号１の割当パターンが選択されているので、航跡グループ２の全ての割当パターンを航跡候補群から除外する。さらに、初期解を構成する割当パターンと、同じ観測フレームの観測値が重複する割当パターンを航跡候補群から除外し、航跡候補群１８を生成する。
【００３０】
初期解生成の手順では、このような、選択候補リストの生成、割当パターンの選択・解の要素追加、航跡候補群の更新を、全ての解の要素が追加されるまで繰り返し行う。
【００３１】
次に、最適解探索部７の動作について説明する。最適解探索部７は、初期解格納部６に格納された初期解を探索の開始点として、新規解の生成(最良解の一部を変更して新規解を複数生成すること)と、解の更新(現時点で得られている最良解を含めて最も評価値の良い解を新たな最良解とすること)を繰り返し実行することで最適解探索を実行する。探索終了後、最適解探索部７は、得られた最良解を最良解格納部８に格納する。
【００３２】
図９および図１０を用いて、最適解探索部７の動作例を説明する。図９は、タブーサーチや遺伝的アルゴリズムの突然変異処理等に代表される局所探索の例を示している。以下にｎ回目の探索処理後の最良解１９が得られた状態における処理手順を示す。
＜最適解探索部７の動作手順１＞
Ｓｔｅｐ１． ｎ回目の探索処理後に得られた最良解１９の変更点２０を選択する。変更点２０の選択方法は、例えば、ランダムでも良いし、対応する割当パターンのコストに比例した(コストが悪いものほど選択されやすくなる)選択確率を与えても良い。
Ｓｔｅｐ２． 変更点を選択したら、その変更点を、取り得る値全てに置き換えた場合の解を新規解として生成し、新規解集合２１を構成する。図９では、解の、左から５番目の要素が変更点として選択されている。
Ｓｔｅｐ３． 新規解集合２１およびｎ回目の探索処理に得られた最良解１９を併せた中から最も評価値の良い解をｎ＋１回目の探索処理後の最良解２２とする。図９では、新規解集合２１の下から２番目の解がｎ＋１回目の探索処理後の最良解となっている。
最適解探索部７の動作手順１のＳｔｅｐ１〜Ｓｔｅｐ３の処理は、最良解が一定回数連続して変化しなくなるまで繰り返される。
【００３３】
探索アルゴリズムとして遺伝的アルゴリズムを適用した場合、交叉という処理による探索が行われる。図１０を用いて、遺伝的アルゴリズムの交叉処理の手順を示す。なお、遺伝的アルゴリズムでは最良解を含む複数の解を保持している。
＜最適解探索部７の動作手順２＞
Ｓｔｅｐ１． ｎ回目の探索処理後に得られた最良解を含む解の集合であるｎ回目の探索後の最良解集合２３の中から２つの解を選択する。図１０では、ｎ回目の探索後の最良解集合２３の中の、上から２番目と下から２番目の解が選択されている。
Ｓｔｅｐ２． Ｓｔｅｐ１で選択された２つの解に対して交叉処理２４を行う。この交叉処理では、選択された２つの解をそれぞれ同じ位置で２つに分割して繋ぎかえることで新規解を２つ生成する。図１０では、新規解集合２５が交叉により生成された新規解である。
Ｓｔｅｐ３． ｎ回目の探索後の最良解集合２３および新規解集合２５を併せた中から、解の評価値の良い順に一定個数選択し、ｎ＋１回目の探索後の最良解集合２６を生成する。図１０では、ｎ回目の探索後の最良解集合２３の上から１番目〜４番目までの４つの解と、新規解集合２５の上の解をｎ＋１回目の探索後の最良解集合２６としている。
最適解探索部７の動作手順２のＳｔｅｐ１〜Ｓｔｅｐ３の処理は、最良解が一定回数連続して変化しなくなるまで繰り返される。
【００３４】
最適解探索部７の動作手順１と最適解探索部７の動作手順２は、常に両方が実行されるわけではなく、適用するアルゴリズムによって、どちらか一方、あるいは、両方が実行される。
【００３５】
次に、図１１を用いて航跡平滑化処理部９の動作について説明する。図１１は、観測フレームｔ〜ｔ＋３に対する航跡割当処理が確定した後の航跡平滑化処理について示している。航跡平滑化処理部９は、観測フレームｔ〜ｔ＋３の航跡割当確定後に、航跡平滑値と最も古い時刻の観測フレームであるフレームｔの間の航跡割当結果と、航跡平滑値と、フレームｔの観測値から新規の航跡平滑値を求め、航跡平滑値格納部１０に格納する。
【００３６】
フレームｔ〜フレームｔ＋３の航跡割当処理を終え、新規航跡平滑値が求まると、航跡割当処理は、新規航跡平滑値とフレームｔ＋１〜フレームｔ＋４の各観測値を用いて、フレームｔ＋１〜ｔ＋４の航跡割当処理を実行する。
また、航跡平滑化処理部９は航跡割当処理結果等を外部に出力する、又は例えば表示部(図示省略)に表示することができる。
【００３７】
以上のように、この発明では、航跡割当問題の一つであるＭＦＡ問題の解の表現方法を、図７のメタヒューリスティックスにおける解表現１５のような形で定義することにより、ＭＦＡ問題に対して、最適解探索部７の動作説明に示したような、組合せ最適化問題を解く様々なメタヒューリスティックス手法による最適解探索手順を容易に実現でき、これによりＭＦＡ問題の解を高速に求める航跡割当装置を実現できるという効果がある。
【図面の簡単な説明】
【００３８】
【図１】この発明の実施の形態１における航跡割当装置の構成を示すブロック図である。
【図２】この発明における観測フレームの例を示した図である。
【図３】この発明における航跡候補群生成部の動作を説明するための図である。
【図４】この発明における航跡候補群生成部の動作を説明するための図である。
【図５】この発明における航跡候補群生成部の動作を説明するための図である。
【図６】この発明における航跡候補群生成部の動作を説明するための図である。
【図７】この発明における初期解生成部の動作を説明するための図である。
【図８】この発明における初期解生成部の動作を説明するための図である。
【図９】この発明における最適解探索部の動作を説明するための図である。
【図１０】この発明における最適解探索部の動作を説明するための図である。
【図１１】この発明における航跡平滑化処理部の動作を説明するための図である。
【図１２】一般的な航跡割当を説明するための図である。
【図１３】一般的な航跡割当を説明するための図である。
【図１４】一般的な航跡割当を説明するための図である。
【図１５】一般的な航跡割当を説明するための図である。
【符号の説明】
【００３９】
１ 観測データ収集部、２ 観測データ蓄積部、３ 航跡候補群生成部、４ 航跡候補群格納部、５ 初期解生成部、６ 初期解格納部、７ 最適解探索部、８ 最良解格納部、９ 航跡平滑化処理部、１０ 航跡平滑値格納部、１１ 航跡(候補)、１２ 割当パターン、１３ 航跡候補群、１４ 解、１５ 解表現、１６ 選択候補リスト、１７ 解表現、１８ 航跡候補群、１９ 最良解、２０ 変更点、２１ 新規解集合、２２ 最良解、２３ 最良解集合、２４ 交叉処理、２５ 新規解集合、２６ 最良解集合。
【技術分野】
【０００１】
この発明は、組合せ最適化問題を解くメタヒューリスティックス手法を用いて航跡割当問題の一つであるＭＦＡ問題の解を高速に求める航跡割当装置に関する。
【背景技術】
【０００２】
レーダの観測値から、飛行中の複数の航空機の航跡を推測する航跡追尾処理を構成する一つの処理として航跡割当処理がある。一回のレーダ観測で得られた観測値の集合を観測フレームと呼び、航跡割当は、観測フレーム内の観測値を複数ある航跡のいずれか一つに割り当てる処理である(新規航跡の始点とする場合もある)。例えば、下記特許文献１では、最新の一つの観測フレーム内の観測値を航跡に割り当てるＭＨＴ法を適用した目標追尾装置が提案されている。
【０００３】
ＭＨＴ法のように一つの観測フレームを用いた航跡割当では十分な航跡追尾精度が得られないため、より高い精度の航跡追尾処理が望まれている。このためには連続した複数の観測フレームを用いた航跡割当処理が必要であり、これは、連続した複数の観測フレームに対して航跡割当を行うＭＦＡ(Multiple Frame Assignment)問題を解くことで実現できる。しかし、ＭＦＡ問題は、ＭＨＴ法のような一つの観測フレームの割当処理に比べて考慮する航跡候補数が爆発的に増加するため、厳密に最適な解を求めようとすると処理に長時間を要し、実用面で問題を生じる。
【０００４】
そこで、運用上問題ない解が求まれば必ずしも最適解でなくても良いという考えに立ち、組合せ最適化問題を高速に解くアルゴリズムの適用が提案されている。例えば非特許文献１では、ラグランジュ緩和法を適用することで解の探索空間の絞込みを行い処理の高速化を図っている。
【０００５】
【特許文献１】特許第３１４５８９３号明細書
【非特許文献１】Aubrey B. Poore、”A New Multidimensional Data Association Algorithm for Multisensor-Multitarget Tracking”、Proc. of SPIE Vol. 2561、1995
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかし、ラグランジュ緩和法は対象問題の次元数(ＭＦＡ問題の場合はフレーム数)が大きくなると処理が煩雑になり、実装が難しくなるという問題がある。また、探索範囲を絞り込むための制約条件の緩和の仕方によっては効果的な絞込みが行えないという問題もある。
【０００７】
ラグランジュ緩和法よりもアルゴリズムが単純で実装が容易であり、且つ、ＭＦＡ問題を高速に解くことが期待できるアルゴリズムに組合せ最適化のメタヒューリスティクス手法がある。主要なアルゴリズムとしては、遺伝的アルゴリズム、タブーサーチ、シミュレーテッド・アニーリングなどが挙げられる。組合せ最適化のメタヒューリスティックス手法を適用することでより効率良くＭＦＡ問題を解くことが期待できるが、ＭＦＡ問題の制約条件の一つであるゲート条件の存在により、効率的な探索が行えない可能性がある。
【０００８】
図１２は航跡割当例を示したものである。時刻ｔ〜時刻ｔ＋３の４つの観測フレーム内の各観測点がＸ−Ｙ平面上に分布している。これら４つの観測フレームの各観測値を重複が無いように結ぶことで４本の航跡への各観測値の割当が行われる。
【０００９】
メタヒューリスティックス手法を用いて最適な航跡割当の探索を行う場合、一般的には現時点で得られている最良解の一部を変更した解(新規解と呼ぶ)を複数生成し、最良解よりも評価値の良い新規解が得られれば、その新規解を最良解とするという処理を繰り返し実行することで最適な割当を求める。例えば、図１２に示した割当結果を現時点の最良解とし、最良解のフレームｔの２番の観測値からフレームｔ＋１の２番の観測値へのリンクと、フレームｔの４番の観測値からフレームｔ＋１の３番の観測値へのリンクを変更し、フレームｔの２番の観測値からフレームｔ＋１の３番の観測値へのリンクと、フレームｔの４番の観測値からフレームｔ＋１の２番の観測値へのリンクとすることで、図１３に示す新規解を生成する。このような部分的な変更による新規解を複数生成し、現時点での最良解よりも良い解の探索を行う。
【００１０】
しかし、ＭＦＡ問題にはゲート条件と呼ばれる制約条件が存在し、上記のようなリンクの変更を行った際、ゲート条件違反が発生し、得られた解が実行不可能な解となってしまう場合がある。
【００１１】
ここで、図１４および図１５を用いてゲート条件を説明する。ゲート条件とは、ある観測フレーム内の観測値から次の観測フレーム内の観測値に航跡を伸長する際に伸長可能な観測値をゲートと呼ばれる範囲内に含まれるものに限定するものであり、例えば、図１４のフレームｔ＋２の１番の観測点から伸長できる、フレームｔ＋３内の観測値は、ゲート範囲内に含まれる１番と２番となる。なお、ゲート範囲はそれまでに得られている航跡によってその範囲が異なり、図１５に示した航跡が得られている場合には、図１４と同じフレームｔ＋２の１番の観測点からのゲート範囲は図１４のものとは異なり、伸長可能なフレームｔ＋３の観測点は１番のみとなる。
【００１２】
すなわち、最良解のリンクを一部張り替えることで航跡の構成が変更され、ゲート条件が変わってしまう。ゲート条件が変わるとゲート条件違反が発生してしまう可能性もある。ゲート条件が発生した場合はゲート条件違反を解消しなければならないが、現在の違反箇所を修正するようリンクの変更を行うと、また別の箇所でゲート条件違反が発生し、それを解消するとまた別の箇所で違反が発生するというように、ゲート条件違反の解消処理を何度も繰り返し行わなければならなくなる。
【００１３】
メタヒューリスティクス手法による最適解探索は、最良解の部分的な変更を繰り返すことに特徴があり、上記のようにゲート条件違反の解消処理が繰り返されることは最良解の部分的な変更とはならず、効率的な探索が行えないという問題がある。
【００１４】
この発明は上記のような問題点を解決するためになされたもので、ＭＦＡ問題を高速に解き、且つ、ラグランジュ緩和法に比べてアルゴリズムが単純で実装が容易である、組合せ最適化のメタヒューリスティックス手法を適用した航跡割当装置を提案することを目的としている。
【課題を解決するための手段】
【００１５】
この発明は、測定して蓄積された移動体の航跡に関する観測データに基づき、予め定められた制約条件に違反しない複数の航跡候補を割当パターン群として生成し、この生成された割当パターン群を構成する各割当パターンに対し、航跡の始点に基づくグループに分類し、各グループの各割当パターンに対して一意の番号を付与する航跡候補群生成手段と、各割当パターンに付与された番号に基づき、組合せ最適化を図るメタヒューリスティックス手法によって観測値を航跡に割り当てる航跡割当処理を行う航跡割当処理手段とを有することを特徴とする航跡割当装置にある。
【発明の効果】
【００１６】
この発明では、組合せ最適化問題を解くメタヒューリスティックス手法を用いて航跡割当問題の一つであるＭＦＡ問題の解を高速に求める航跡割当装置を提供することができる。
【発明を実施するための最良の形態】
【００１７】
実施の形態１．
図１は、この発明の実施の形態１における航跡割当装置の構成を示すブロック図であり、例えばコンピュータとメモリにより構成される。図１において、観測データ収集部１は、レーダ等により観測された飛行物体等の移動体の観測値のデータを収集する装置である。観測データ蓄積部２は、観測データ収集部１により収集された観測値を観測データとして蓄積する装置である。航跡候補群生成部３は、観測データ蓄積部２に蓄積された観測値データ、および航跡平滑値格納部１０に格納される平滑値情報より、ゲート条件と呼ばれる制約条件に違反しない航跡候補を全て生成し(航跡候補を割当パターンと呼ぶ場合もある)、航跡候補群を構成する航跡候補を、始点が同じものでグループ化する装置である。航跡候補群格納部４は、航跡候補群生成部３において生成された航跡候補群を格納する装置である。
【００１８】
初期解生成部５は、航跡候補群格納部４に格納された航跡候補群の中から航跡グループ毎に一つずつ航跡候補を選択し、最適な航跡候補の組合せ(以降、航跡候補の組合せ「解」と呼ぶ)を探索するための初期解を生成する装置である。初期解格納部６は、初期解生成部５で生成された初期解を格納する装置である。
【００１９】
最適解探索部７は、初期解格納部６に格納された初期解を最初の最良解とし、最良解の一部分を変更した複数の解を新たに生成する「新規解生成」と、現時点の最良解よりも評価値が良い新規解が存在する場合、評価値が最も良い新規解を新たな最良解とする「解更新」の２つの処理を、解の更新がされなくなるまで交互に繰り返すことで最適解の探索を行う装置である。最良解格納部８は、最適解探索部７における処理で最終的に得られた解を格納する装置である。航跡平滑化処理部９は、最良解格納部８に格納された解に示される航跡割当結果を用いて航跡平滑値を更新する装置である。航跡平滑値格納部１０は、航跡平滑化処理部９の処理結果を格納する装置である。
【００２０】
なお、観測データ収集部１と観測データ蓄積部２が観測データ収集手段を構成する。また、航跡候補群生成部３と航跡候補群格納部４が航跡候補群生成手段を構成する。一方、初期解生成部５と初期解格納部６が初期解生成手段を構成し、最適解探索部７と最良解格納部８が最適解探索手段を構成し、航跡平滑化処理部９と航跡平滑値格納部１０が航跡平滑化処理手段を構成する。そして上記初期解生成手段、最適解探索手段及び航跡平滑化処理手段が航跡割当処理手段を構成する。
【００２１】
次に図１の構成を有する航跡割当装置の一連の動作について説明する。まず、航跡割当装置は、例えばレーダ(図示省略)により観測された飛翔体、例えば航空機の航跡に関する観測値を観測データとして観測データ収集部１により収集し、観測データ蓄積部２に蓄積する。観測データは、観測時刻毎にまとめられ、一時刻分の観測データの集合を観測フレームと呼ぶ(以降、単にフレームと記述する場合もある)。図２は、観測フレームの例を示した図で、時刻ｔ〜時刻ｔ＋３の間に観測された観測値を二次元平面上に表示したものである。フレームｔの破線枠で囲まれているものは時刻ｔの観測フレームに含まれる観測値であり、フレームｔ＋１〜ｔ＋３も同様である。なお、各フレーム内の観測値には１〜４の番号が振られているが、これは単に識別のために付けた番号であり、各フレームの同じ番号の観測値が同じ航跡に含まれるという意味ではない。観測データ収集部１では、図２に示したような観測データをフレーム単位に観測データ蓄積部２に蓄積する。なお、各観測値には、例えば、飛行物体の飛行速度、進行方向、位置などの情報が含まれる。
【００２２】
次に、航跡候補群生成部３が、以下に示す手順に従って航跡候補群を生成し、航跡候補群格納部４に格納する。なお、航跡候補群とは、観測データを基に生成した、ゲート条件を満たす航跡候補(割当パターンとも呼ぶ)の集合である。
【００２３】
以下に、航跡候補群生成の手順を示す。
＜航跡候補群生成手順＞
Ｓｔｅｐ１． 航跡候補群生成部３は、観測データ蓄積部２から最新のＮフレーム分(Ｎは正の整数で、Ｎの値は問題設定により変わる)のデータを取得し、さらに航跡平滑値格納部１０より、前回の航跡割当処理後の航跡平滑値を取得する。航跡平滑値は、航跡毎に、割当が確定された部分(以降の処理で割当変更を行わない部分)を構成する複数の観測値の情報を平滑化し一つの観測値としてまとめたものである(以降、航跡平滑値は単に平滑値と呼ぶ)。図３は、時刻ｔ〜ｔ＋３の４つの観測フレームに対して航跡割当を行う場合の取得データ例を示したものであり、最初に平滑値データ、以降に観測時刻順にフレームが並んでいる。
Ｓｔｅｐ２． 航跡候補群生成部３は、Ｓｔｅｐ１において取得した観測データより、各平滑値を始点とする、ゲート条件に違反しない、割当パターンを全て生成する。生成された割当パターンの集合を航跡候補群と呼ぶ。図４に割当パターンの例を示す。図３に示した取得データにおいて、図４の航跡１１がゲート条件に違反しない航跡候補の一つであるとすると、この航跡候補１１に対して、割当パターン１２を生成する。割当パターン１２における数字は各フレームにおける航跡候補１１を構成する観測値の番号であり、先頭は平滑値、２番目以降は観測時刻の早いフレーム順の並びとなっている。
Ｓｔｅｐ３． Ｓｔｅｐ２において抽出した航跡候補群を、始点を同じとする割当パターン同士をグルーピングする。図５に、図３に示した取得データに対する航跡候補群のグルーピング例を示す。先頭の数字が同じ割当パターンを同じグループとしている。
Ｓｔｅｐ４． Ｓｔｅｐ３においてグルーピングした航跡候補群に対して、グループ内の割当パターンが一意に識別できるように各割当パターンに番号を付与する。この番号を割当パターン番号と呼ぶ。図６に割当パターン番号付与の例を示す。図６では、各航跡グループ内の割当パターンに対して、１から順に番号を付与している。
Ｓｔｅｐ５． Ｓｔｅｐ４で割当パターン番号を付与した航跡候補群を、航跡候補群格納部４に格納する。
【００２４】
次に、初期解生成部５が、メタヒューリスティックス手法による航跡割当処理のための初期解を生成し、初期解格納部６に生成した初期解を格納する。ＭＦＡ問題の解は、航跡候補群の中から、航跡グループ毎に一つずつ割当パターンを選択することで構成されるが、この発明における航跡割当装置では、さらに前述の割当パターン番号を利用してＭＦＡ問題の解を間接的に表現することを特徴とする。図７に、航跡候補群からのＭＦＡ問題の解の構成と、メタヒューリスティックス手法を適用するための解表現の例を示す。図７の航跡候補群１３は、航跡候補群生成部３により生成された航跡候補群である。ＭＦＡ問題の解は、航跡候補群１３から、航跡グループ毎に一つずつ割当パターンを選択した物となり、図７のＭＦＡの解１４が一つの解の例を示している。このＭＦＡの解１４は、横一列が一つの航跡を構成する各観測フレームの観測値を表している。なお、ＭＦＡの解１４の右端にある丸で囲まれた数字は、割当パターン番号である。
【００２５】
ＭＦＡの解１４は直接的な表現であり、２次元の配列となっている。これを、よりメタヒューリスティックス手法が適用しやすい形の間接的な表現にしたものが、メタヒューリスティックスにおける解表現１５である。メタヒューリスティックスにおける解表現１５では、ＭＦＡの解１４を構成する割当パターンの割当パターン番号の並びでＭＦＡ問題の解を表現する。
【００２６】
初期解の生成方法には複数の方式が考えられるが、以下にＧＲＡＳＰ(Greedy Randoized Adaptive Search Procedure)手法の初期解生成を応用した手順を示す。
＜初期解生成手順＞
Ｓｔｅｐ１． 航跡候補群に含まれる割当パターンの最大コストＣｍａｘと最小コストＣｍｉｎを求める。
Ｓｔｅｐ２． 航跡候補群に含まれるｉ番目の割当パターンのコストをＣｉとし、式(１)を満たす割当パターンを全て選択候補リストに加える。
Ｃｍｉｎ≦Ｃｉ≦Ｃｍｉｎ＋α(Ｃｍａｘ−Ｃｍｉｎ) (１)
Ｓｔｅｐ３． 選択候補リストの中からランダムに一つ割当パターンを選択し、解の構成要素とする。解が完成したら終了し、そうでなければＳｔｅｐ４に進む。
Ｓｔｅｐ４． 選択候補リストを空にし、解の構成要素となっている割当パターンおよびそれらと同じ航跡グループに属する割当パターン、更に解の構成要素となっている割当パターンと航跡を構成する観測値が重複する割当パターンを航跡候補群から除外し(航跡候補群の更新)、Ｓｔｅｐ１に戻る。
【００２７】
以上の手順のＳｔｅｐ２〜Ｓｔｅｐ４の概要を図８に示す。まず、初期解生成手順を実行する前に航跡候補群生成部３において生成された航跡候補群が航跡候補群１３である。この航跡候補群１３の中から、Ｓｔｅｐ２の処理により求めたコストが式(１)を満たす割当パターンの集合が選択候補リスト１６である。なお、選択候補リスト１６の右端のＧ１やＧ２などの表記は、その割当パターンが属する航跡グループを示している。
【００２８】
Ｓｔｅｐ３では、この選択候補リスト１６の中からランダムに一つ割当パターンを選択する。図８では、選択候補リスト１６の上から３番目の航跡グループ２の割当パターン番号１の割当パターンが選択された場合を示している。従って、同じＳｔｅｐ３の処理において、メタヒューリスティックスにおける解表現１７には、航跡グループ２に対応する左から２番目の位置に割当パターン番号１が追加される。
【００２９】
Ｓｔｅｐ４では、Ｓｔｅｐ３で選択された航跡グループ２の割当パターン番号１の割当パターンが選択されているので、航跡グループ２の全ての割当パターンを航跡候補群から除外する。さらに、初期解を構成する割当パターンと、同じ観測フレームの観測値が重複する割当パターンを航跡候補群から除外し、航跡候補群１８を生成する。
【００３０】
初期解生成の手順では、このような、選択候補リストの生成、割当パターンの選択・解の要素追加、航跡候補群の更新を、全ての解の要素が追加されるまで繰り返し行う。
【００３１】
次に、最適解探索部７の動作について説明する。最適解探索部７は、初期解格納部６に格納された初期解を探索の開始点として、新規解の生成(最良解の一部を変更して新規解を複数生成すること)と、解の更新(現時点で得られている最良解を含めて最も評価値の良い解を新たな最良解とすること)を繰り返し実行することで最適解探索を実行する。探索終了後、最適解探索部７は、得られた最良解を最良解格納部８に格納する。
【００３２】
図９および図１０を用いて、最適解探索部７の動作例を説明する。図９は、タブーサーチや遺伝的アルゴリズムの突然変異処理等に代表される局所探索の例を示している。以下にｎ回目の探索処理後の最良解１９が得られた状態における処理手順を示す。
＜最適解探索部７の動作手順１＞
Ｓｔｅｐ１． ｎ回目の探索処理後に得られた最良解１９の変更点２０を選択する。変更点２０の選択方法は、例えば、ランダムでも良いし、対応する割当パターンのコストに比例した(コストが悪いものほど選択されやすくなる)選択確率を与えても良い。
Ｓｔｅｐ２． 変更点を選択したら、その変更点を、取り得る値全てに置き換えた場合の解を新規解として生成し、新規解集合２１を構成する。図９では、解の、左から５番目の要素が変更点として選択されている。
Ｓｔｅｐ３． 新規解集合２１およびｎ回目の探索処理に得られた最良解１９を併せた中から最も評価値の良い解をｎ＋１回目の探索処理後の最良解２２とする。図９では、新規解集合２１の下から２番目の解がｎ＋１回目の探索処理後の最良解となっている。
最適解探索部７の動作手順１のＳｔｅｐ１〜Ｓｔｅｐ３の処理は、最良解が一定回数連続して変化しなくなるまで繰り返される。
【００３３】
探索アルゴリズムとして遺伝的アルゴリズムを適用した場合、交叉という処理による探索が行われる。図１０を用いて、遺伝的アルゴリズムの交叉処理の手順を示す。なお、遺伝的アルゴリズムでは最良解を含む複数の解を保持している。
＜最適解探索部７の動作手順２＞
Ｓｔｅｐ１． ｎ回目の探索処理後に得られた最良解を含む解の集合であるｎ回目の探索後の最良解集合２３の中から２つの解を選択する。図１０では、ｎ回目の探索後の最良解集合２３の中の、上から２番目と下から２番目の解が選択されている。
Ｓｔｅｐ２． Ｓｔｅｐ１で選択された２つの解に対して交叉処理２４を行う。この交叉処理では、選択された２つの解をそれぞれ同じ位置で２つに分割して繋ぎかえることで新規解を２つ生成する。図１０では、新規解集合２５が交叉により生成された新規解である。
Ｓｔｅｐ３． ｎ回目の探索後の最良解集合２３および新規解集合２５を併せた中から、解の評価値の良い順に一定個数選択し、ｎ＋１回目の探索後の最良解集合２６を生成する。図１０では、ｎ回目の探索後の最良解集合２３の上から１番目〜４番目までの４つの解と、新規解集合２５の上の解をｎ＋１回目の探索後の最良解集合２６としている。
最適解探索部７の動作手順２のＳｔｅｐ１〜Ｓｔｅｐ３の処理は、最良解が一定回数連続して変化しなくなるまで繰り返される。
【００３４】
最適解探索部７の動作手順１と最適解探索部７の動作手順２は、常に両方が実行されるわけではなく、適用するアルゴリズムによって、どちらか一方、あるいは、両方が実行される。
【００３５】
次に、図１１を用いて航跡平滑化処理部９の動作について説明する。図１１は、観測フレームｔ〜ｔ＋３に対する航跡割当処理が確定した後の航跡平滑化処理について示している。航跡平滑化処理部９は、観測フレームｔ〜ｔ＋３の航跡割当確定後に、航跡平滑値と最も古い時刻の観測フレームであるフレームｔの間の航跡割当結果と、航跡平滑値と、フレームｔの観測値から新規の航跡平滑値を求め、航跡平滑値格納部１０に格納する。
【００３６】
フレームｔ〜フレームｔ＋３の航跡割当処理を終え、新規航跡平滑値が求まると、航跡割当処理は、新規航跡平滑値とフレームｔ＋１〜フレームｔ＋４の各観測値を用いて、フレームｔ＋１〜ｔ＋４の航跡割当処理を実行する。
また、航跡平滑化処理部９は航跡割当処理結果等を外部に出力する、又は例えば表示部(図示省略)に表示することができる。
【００３７】
以上のように、この発明では、航跡割当問題の一つであるＭＦＡ問題の解の表現方法を、図７のメタヒューリスティックスにおける解表現１５のような形で定義することにより、ＭＦＡ問題に対して、最適解探索部７の動作説明に示したような、組合せ最適化問題を解く様々なメタヒューリスティックス手法による最適解探索手順を容易に実現でき、これによりＭＦＡ問題の解を高速に求める航跡割当装置を実現できるという効果がある。
【図面の簡単な説明】
【００３８】
【図１】この発明の実施の形態１における航跡割当装置の構成を示すブロック図である。
【図２】この発明における観測フレームの例を示した図である。
【図３】この発明における航跡候補群生成部の動作を説明するための図である。
【図４】この発明における航跡候補群生成部の動作を説明するための図である。
【図５】この発明における航跡候補群生成部の動作を説明するための図である。
【図６】この発明における航跡候補群生成部の動作を説明するための図である。
【図７】この発明における初期解生成部の動作を説明するための図である。
【図８】この発明における初期解生成部の動作を説明するための図である。
【図９】この発明における最適解探索部の動作を説明するための図である。
【図１０】この発明における最適解探索部の動作を説明するための図である。
【図１１】この発明における航跡平滑化処理部の動作を説明するための図である。
【図１２】一般的な航跡割当を説明するための図である。
【図１３】一般的な航跡割当を説明するための図である。
【図１４】一般的な航跡割当を説明するための図である。
【図１５】一般的な航跡割当を説明するための図である。
【符号の説明】
【００３９】
１ 観測データ収集部、２ 観測データ蓄積部、３ 航跡候補群生成部、４ 航跡候補群格納部、５ 初期解生成部、６ 初期解格納部、７ 最適解探索部、８ 最良解格納部、９ 航跡平滑化処理部、１０ 航跡平滑値格納部、１１ 航跡(候補)、１２ 割当パターン、１３ 航跡候補群、１４ 解、１５ 解表現、１６ 選択候補リスト、１７ 解表現、１８ 航跡候補群、１９ 最良解、２０ 変更点、２１ 新規解集合、２２ 最良解、２３ 最良解集合、２４ 交叉処理、２５ 新規解集合、２６ 最良解集合。
【特許請求の範囲】
【請求項１】
測定して蓄積された移動体の航跡に関する観測データに基づき、予め定められた制約条件に違反しない複数の航跡候補を割当パターン群として生成し、この生成された割当パターン群を構成する各割当パターンに対し、航跡の始点に基づくグループに分類し、各グループの各割当パターンに対して一意の番号を付与する航跡候補群生成手段と、各割当パターンに付与された番号に基づき、組合せ最適化を図るメタヒューリスティックス手法によって観測値を航跡に割り当てる航跡割当処理を行う航跡割当処理手段とを有することを特徴とする航跡割当装置。
【請求項２】
航跡割当処理手段が、初期解生成手段、最適解探索手段、航跡平滑化処理手段を含み、
前記航跡候補群生成手段が、蓄積された観測データと前記航跡平滑化処理手段で求められ格納されている航跡平滑値より、制約条件に違反しない航跡候補を割当パターン群として全て生成し、さらに生成された割当パターン群を構成する割当パターンを同じ始点のグループに分類し、グループ毎に各割当パターンに対して一意の番号を付与して格納し、
前記初期解生成手段が、前記航跡候補群生成手段に格納された割当パターン群の中から航跡割当結果を各割当パターンに付与した番号で表現して、割当パターン群の中からグループ毎に一つずつ割当パターンを選択し、最適な航跡候補の組合解を探索するための初期解を生成して格納し、
前記最適解探索手段が、前記初期解生成手段に格納された初期解を最初の最良解とし、最良解の一部分を変更した複数の解を新たに生成する新規解生成と、現時点の最良解よりも評価値が良い新規解が存在する場合、評価値が最も良い新規解を新たな最良解とする解更新の２つの処理を、解の更新がされなくなるまで交互に繰り返して最適解の探索を行い、最終的に得られた最適解を格納し、
前記航跡平滑化処理手段が、前記最適解探索手段に格納された最適解に示される航跡割当結果に基づき航跡平滑値を更新して格納する、
ことを特徴とする請求項１に記載の航跡割当装置。
【請求項１】
測定して蓄積された移動体の航跡に関する観測データに基づき、予め定められた制約条件に違反しない複数の航跡候補を割当パターン群として生成し、この生成された割当パターン群を構成する各割当パターンに対し、航跡の始点に基づくグループに分類し、各グループの各割当パターンに対して一意の番号を付与する航跡候補群生成手段と、各割当パターンに付与された番号に基づき、組合せ最適化を図るメタヒューリスティックス手法によって観測値を航跡に割り当てる航跡割当処理を行う航跡割当処理手段とを有することを特徴とする航跡割当装置。
【請求項２】
航跡割当処理手段が、初期解生成手段、最適解探索手段、航跡平滑化処理手段を含み、
前記航跡候補群生成手段が、蓄積された観測データと前記航跡平滑化処理手段で求められ格納されている航跡平滑値より、制約条件に違反しない航跡候補を割当パターン群として全て生成し、さらに生成された割当パターン群を構成する割当パターンを同じ始点のグループに分類し、グループ毎に各割当パターンに対して一意の番号を付与して格納し、
前記初期解生成手段が、前記航跡候補群生成手段に格納された割当パターン群の中から航跡割当結果を各割当パターンに付与した番号で表現して、割当パターン群の中からグループ毎に一つずつ割当パターンを選択し、最適な航跡候補の組合解を探索するための初期解を生成して格納し、
前記最適解探索手段が、前記初期解生成手段に格納された初期解を最初の最良解とし、最良解の一部分を変更した複数の解を新たに生成する新規解生成と、現時点の最良解よりも評価値が良い新規解が存在する場合、評価値が最も良い新規解を新たな最良解とする解更新の２つの処理を、解の更新がされなくなるまで交互に繰り返して最適解の探索を行い、最終的に得られた最適解を格納し、
前記航跡平滑化処理手段が、前記最適解探索手段に格納された最適解に示される航跡割当結果に基づき航跡平滑値を更新して格納する、
ことを特徴とする請求項１に記載の航跡割当装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２００９−１６２６１５（Ｐ２００９−１６２６１５Ａ）
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願番号】特願２００８−５２４（Ｐ２００８−５２４）
【出願日】平成２０年１月７日（２００８．１．７）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
【公開日】平成２１年７月２３日（２００９．７．２３）
【国際特許分類】
【出願日】平成２０年１月７日（２００８．１．７）
【出願人】（０００００６０１３）三菱電機株式会社 (33,312)
【Ｆターム（参考）】
[ Back to top ]