(57)【要約】【課題】少ない計算量で、監視対象領域を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価可能なセンサ配置評価装置を得る。【解決手段】目標状態ツリーを保持する目標状態探索状況保持手段１０９と、目標状態選択手段１１０と、目標状態生成手段１１５と、見逃し確率算出手段１０７と、累積見逃し確率算出手段１０８と、終了判定手段１２１とを備えている。目標状態ツリーは、目標の位置または向きに関する情報を含む目標状態と、目標の累積見逃し確率との対をノードとするツリー構造からなり、ツリー構造のルートノードは、初期目標状態に対応する。目標状態選択手段１１０は、目標状態ツリーにおいて、累積見逃し確率があらかじめ定めた閾値以上であるノードから、１つの目標状態を選択する。目標状態生成手段１１５は、選択した目標状態に基づき、その一定時間後の目標状態を新たに生成する。【選択図】図１
2010281784.tif 000002
【特許請求の範囲】
【請求項１】
目標状態探索状況保持手段と、目標状態選択手段と、目標状態生成手段と、見逃し確率算出手段と、累積見逃し確率算出手段と、終了判定手段とを備え、複数のセンサの配置を評価するセンサ配置評価装置であって、
前記目標状態探索状況保持手段は、目標状態ツリーを保持し、
前記目標状態ツリーは、目標の位置または向きに関する情報を含む目標状態と、前記目標の累積見逃し確率との対をノードとするツリー構造からなり、
前記ツリー構造のルートノードは、初期目標状態に対応するノードであり、
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーにおいて、前記累積見逃し確率があらかじめ定めた閾値以上であるノードから、１つの目標状態を選択し、
前記目標状態生成手段は、前記目標状態選択手段が選択した前記目標状態に基づき、その一定時間後の目標状態を新たに生成し、
前記見逃し確率算出手段は、前記初期目標状態、または前記目標状態生成手段が生成した前記目標状態について、前記目標状態と、前記複数のセンサに関するセンサ情報およびセンサ配置情報とを利用して、前記目標状態の見逃し確率を算出し、
前記累積見逃し確率算出手段は、前記目標状態生成手段が生成した前記目標状態について、前記目標状態の生成元の目標状態の累積見逃し確率と、前記見逃し確率算出手段が算出した前記目標状態の前記見逃し確率との積を取ることにより、前記目標状態の累積見逃し確率を算出するとともに、前記目標状態ごとに、前記目標状態探索状況保持手段が保持する前記目標状態ツリーに対し、前記目標状態の生成元の目標状態に対応するノードの子ノードとして追加し、
前記終了判定手段は、前記目標状態生成手段が生成した前記目標状態が、前記目標の目的地であるゴール領域に到達している場合には、前記複数のセンサの配置が性能不十分と評価して、評価処理を終了し、また、前記目標状態探索状況保持手段が保持する前記目標状態ツリーを構成するノード数が所定値以上である場合には、前記複数のセンサの配置が性能十分と評価して、評価処理を終了することを特徴とするセンサ配置評価装置。
【請求項２】
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーからの目標状態選択において、前記目標状態と前記ゴール領域との間のゴール距離が小さいほど、高確率で選択することを特徴とする請求項１に記載のセンサ配置評価装置。
【請求項３】
前記目標状態生成手段は、前記目標状態選択手段が選択した前記目標状態に基づく目標状態生成において、前記ゴール領域との間のゴール距離が小さい目標状態を、高確率で新たに生成することを特徴とする請求項１または請求項２に記載のセンサ配置評価装置。
【請求項４】
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーからの目標状態選択において、前記複数のセンサの各位置を母点とするボロノイ図に関し、前記目標状態と、前記目標状態に最も近いボロノイ辺との間のボロノイ辺距離が小さいほど、高確率で選択することを特徴とする請求項１に記載のセンサ配置評価装置。
【請求項５】
前記目標状態生成手段は、前記目標状態選択手段が選択した前記目標状態に基づく目標状態生成において、前記複数のセンサの各位置を母点とするボロノイ図に関し、ボロノイ辺との間のボロノイ辺距離が小さい目標状態を、高確率で新たに生成することを特徴とする請求項１または請求項４に記載のセンサ配置評価装置。
【請求項６】
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーからの目標状態選択において、前記累積見逃し確率が高いほど高確率で選択することを特徴とする請求項１から請求項５までのいずれか１項に記載のセンサ配置評価装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数のセンサ（センサ群）をそれぞれ異なる場所に配置した際に、センサ群で監視すべき領域（以下、「監視対象領域」という）を目標が移動する過程で、センサ群によって高確率で探知可能か否かを評価するセンサ配置評価装置に関するものである。
【背景技術】
【０００２】
従来から、複数のセンサをそれぞれ異なる場所に配置した際に、このセンサ群によって目標を高確率で探知可能か否かを評価するセンサ配置評価装置は、種々提案されている（たとえば、非特許文献１参照）。
【０００３】
ここで、任意の目標（航空機、船舶、車両などの推進体）が、監視対象領域内を移動して、目標の目的地とする領域（以下、「ゴール領域」という）を目指して横切る状況を想定する。
【０００４】
この場合、非特許文献１に記載の従来のセンサ配置評価装置においては、目標が監視対象領域を移動している途中に、センサ群によって探知可能か否かを評価するために、監視対象領域をグリッドで分割し、目標がグリッドに沿って移動することを仮定して、以下の手順により、センサ群の配置を評価していた。
【０００５】
すなわち、まず、グリッドの各隣接点の間を目標が移動する際に、センサ群によって探知されない確率（以下、「見逃し確率」という）を求め、求められた見逃し確率に応じた数値を、各隣接点間を結ぶ線分の重みとして付与する。
【０００６】
続いて、目標のスタート地点とゴール地点とを結ぶグリッド上の経路のうち、「その経路を移動中に探知されない確率」が最大のものを求める。
ここで、「経路を移動中に探知されない確率」は、その経路を構成する線分の見逃し確率の積として評価可能である。また、「経路を移動中に探知されない確率」が最大である経路を効率良く求めるためには、ダイクストラ法などの最短経路探索アルゴリズムを利用する。
【０００７】
上記の評価方法を利用することにより、グリッド上の経路のうち、見逃し確率が最大である経路が求められる。逆に言うと、目標がグリッド上のどの経路を通過してスタート地点からゴール地点に至っても、求められた見逃し確率以下の見逃し確率で探知可能である、とセンサ配置を評価することができる。
【０００８】
しかしながら、上記非特許文献１に記載の従来のセンサ配置評価装置においては、以下の条件（１）〜（５）の下で、グリッドの隣接点間の全線分に関する見逃し確率の算出に要する処理時間が膨大となり、処理時間の増大を無視することができなくなる。
【０００９】
（１）監視対象領域が広い場合。
（２）グリッドの刻みが細かい場合。
（３）３次元空間を考慮する必要がある場合。
（４）センサのバイスタティック運用をするなどの理由により、目標の位置に加えて目標形状や向きも考慮する必要がある場合。
（５）種々のセンサ配置の評価を行う場合。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Ｖ．  Ｐｈｉｐａｔａｎａｓｕｐｈｒｏｎ，  Ｐ．  Ｒａａｍａｎａｔｈａｎ，  “Ｖｕｌｎｅｒａｂｉｌｉｔｙ  ｏｆ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ  ｔｏ  Ｕｎａｕｔｈｏｒｉｚｅｄ  Ｔｒａｖｅｒｓａｌ  ａｎｄ  Ｍｏｎｉｔｏｒｉｎｇ，”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，  ｖｏｌ．  ５３，  ｎｏ．  ３，  ｐｐ．  ３６４−３６９，  Ｍａｒｃｈ  ２００４
【発明の概要】
【発明が解決しようとする課題】
【００１１】
従来のセンサ配置評価装置は、あらかじめ、グリッドの隣接点間に関するすべての見逃し確率を求めておく必要があるので、１つの見逃し確率の算出に要する処理時間が無視できず、さらに計算すべき見逃し確率の数が多い場合には、計算量が増大するという課題があった。
また、従来のセンサ配置評価装置は、目標がグリッドに沿って移動することを前提としており、目標の運動性能などの制約に基づく自然な動き方が考慮されていないという課題があった。
【００１２】
この発明は、上記のような課題を解決するためになされたものであり、少ない計算量で、監視対象領域を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価することができ、さらに、評価の過程で目標の自然な動き方を考慮可能なセンサ配置評価装置を得ることを目的とする。
【課題を解決するための手段】
【００１３】
この発明に係るセンサ配置評価装置は、目標状態探索状況保持手段と、目標状態選択手段と、目標状態生成手段と、見逃し確率算出手段と、累積見逃し確率算出手段と、終了判定手段とを備え、複数のセンサの配置を評価するセンサ配置評価装置であって、目標状態探索状況保持手段は、目標状態ツリーを保持し、目標状態ツリーは、目標の位置または向きに関する情報を含む目標状態と、目標の累積見逃し確率との対をノードとするツリー構造からなり、ツリー構造のルートノードは、初期目標状態に対応するノードであり、目標状態選択手段は、目標状態探索状況保持手段が保持する目標状態ツリーにおいて、累積見逃し確率があらかじめ定めた閾値以上であるノードから、１つの目標状態を選択し、目標状態生成手段は、目標状態選択手段が選択した目標状態に基づき、その一定時間後の目標状態を新たに生成し、見逃し確率算出手段は、初期目標状態、または目標状態生成手段が生成した目標状態について、目標状態と、複数のセンサに関するセンサ情報およびセンサ配置情報とを利用して、目標状態の見逃し確率を算出し、累積見逃し確率算出手段は、目標状態生成手段が生成した目標状態について、目標状態の生成元の目標状態の累積見逃し確率と、見逃し確率算出手段が算出した目標状態の見逃し確率との積を取ることにより、目標状態の累積見逃し確率を算出するとともに、目標状態ごとに、目標状態探索状況保持手段が保持する目標状態ツリーに対し、目標状態の生成元の目標状態に対応するノードの子ノードとして追加し、終了判定手段は、目標状態生成手段が生成した目標状態が、目標の目的地であるゴール領域に到達している場合には、複数のセンサの配置が性能不十分と評価して、評価処理を終了し、また、目標状態探索状況保持手段が保持する目標状態ツリーを構成するノード数が所定値以上である場合には、複数のセンサの配置が性能十分と評価して、評価処理を終了するものである。
【発明の効果】
【００１４】
この発明によれば、少ない計算量で、監視対象領域を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価することができ、さらに、評価の過程で目標の自然な動き方を考慮可能にすることができる。
【図面の簡単な説明】
【００１５】
【図１】この発明の実施の形態１に係るセンサ配置評価装置の構成を示すブロック図である。
【図２】この発明の実施の形態１において探知対象となる目標の経路の例を示す説明図である。
【図３】この発明の実施の形態１に係るセンサ配置評価装置の処理動作を示すフローチャートである。
【図４】この発明の実施の形態１において探知対象となるスタート地点での目標状態の例を示す説明図である。
【図５】図４の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図６】図５の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図７】図６の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図８】図７の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図９】図８の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図１０】図４〜図９の選択処理の繰り返しにより最終的な目標状態を生成した例を示す説明図である。
【図１１】この発明の実施の形態１のセンサ配置評価処理過程における或る時点での目標状態ツリーの構成例を示す説明図である。
【図１２】この発明の実施の形態１における代表的な目標状態の変化例を示す説明図である。
【図１３】この発明の実施の形態１により選択された目標状態から図１２参照にしたがって得られる目標状態候補の例を示す説明図である。
【図１４】この発明の実施の形態２に係るセンサ配置評価装置の構成を示すブロック図である。
【図１５】この発明の実施の形態２におけるボロノイ図の例を示す説明図である。
【図１６】この発明の実施の形態２のセンサ配置評価処理過程における或る時点での目標状態ツリーの例をボロノイ図とともに示す説明図である。
【図１７】この発明の実施の形態２に係るセンサ配置評価装置の動作をボロノイ図とともに示す説明図である。
【図１８】この発明の実施の形態３に係るセンサ配置評価装置の構成を示すブロック図である。
【発明を実施するための形態】
【００１６】
実施の形態１．
以下、図１〜図１３を参照しながら、この発明の実施の形態１に係るセンサ配置評価装置について説明する。
図１はこの発明の実施の形態１に係るセンサ配置評価装置の構成を示すブロック図である。
【００１７】
図１において、センサ配置評価装置は、地形情報保持手段１０１と、目標情報保持手段１０２と、センサ情報保持手段１０３と、センサ配置保持手段１０４と、監視対象領域保持手段１０５と、初期目標状態指定手段１０６と、見逃し確率算出手段１０７と、累積見逃し確率算出手段１０８と、目標状態探索状況保持手段１０９と、目標状態選択手段１１０と、目標状態生成手段１１５と、終了判定手段１２１とを備えている。
【００１８】
目標状態選択手段１１０は、目標状態確率分布設定手段１１１と、目標状態確率的選択手段１１４とを備えている。
目標状態確率分布設定手段１１１は、目標状態確率分布保持手段１１２と、ゴール距離対応目標状態確率分布加工手段１１３とを備えている。
【００１９】
目標状態生成手段１１５は、目標状態候補生成手段１１６と、目標状態候補確率分布設定手段１１７と、目標状態候補確率的選択手段１２０とを備えている。
目標状態候補確率分布設定手段１１７は、目標状態候補確率分布保持手段１１８と、ゴール距離対応目標状態候補確率分布加工手段１１９とを備えている。
【００２０】
ここで、図１に示したセンサ配置評価装置の動作について説明する前に、図２を参照しながら、技術背景について説明する。
図２においては、複数のセンサ（ユニット）を、それぞれ異なる場所に配置した状況を想定し、ユーザが定めた監視対象領域２０１を、航空機、船舶、車両などの目標Ａが横切って、所定のゴール領域２０２に至る状況を想定している。
【００２１】
センサ配置評価装置の目的は、上記想定条件の下で、目標Ａが監視対象領域２０１を移動途中に（つまり、ゴール領域２０２に到達する前に）、配置されたセンサ群によって高確率で探知可能か否かを評価することである。もし、「高確率で探知可能でない場合がある」と判定された場合には、センサ配置が適切ではなかったものと判定し、センサ群の再配置や、新たなセンサの追加などのアクションに結び付けることができる。
【００２２】
図２は探知対象となる目標Ａの経路（破線矢印参照）の例を示す説明図であり、監視対象領域２０１、目標Ａのゴール領域２０２およびセンサ群と関連付けて各経路を示している。
図２において、複数のセンサ（レーダ装置）からなるセンサ群の配置は、送受信ユニット（△印参照）と、送信ユニット（○印参照）と、受信ユニット（□印参照）とにより、示されている。
【００２３】
以下の説明においては、簡単のため、目標Ａの経路および監視対象領域２０１やゴール領域２０２などが２次元平面に限定されることを前提とするが、この発明の実施の形態１の考え方は、これらが３次元空間の場合にも全く同様に適用可能である。
【００２４】
図２に示すように、目標Ａは、あらかじめ設定したスタート地点から移動を開始し、監視対象領域２０１を横断して、ゴール領域２０２（ハッチング部分）に向かうことを想定する。
ただし、この際、目標Ａは直線などの単純な経路上を移動するとは限らず、その取りうる経路（破線矢印）は、目標Ａの運動性能が許す範囲内で無限に考えられるものとする。
【００２５】
図２においては、目標Ａが監視対象領域２０１を移動中に、目標Ａを探知することを目的として、複数のセンサから構成されるセンサ群を配置することを考える。
ここで、各センサは、送信ユニット（○印）、受信ユニット（□印）、送受信ユニット（△印）のいずれかである。
【００２６】
なお、送信ユニット（○印）とは、空間中に電波を送信するユニットであり、受信ユニット（□印）とは、目標Ａが出力した電波や目標Ａから反射した電波を受信して、目標Ａを探知するユニットである。また、送受信ユニット（△印）は、送信ユニットおよび受信ユニットの両方の機能を有するユニットであり、通常のモノスタティックレーダに相当する。
【００２７】
或る時刻における目標Ａが、特定の送受信ユニット（△印）の捜索によって、どの程度探知可能であるかは、目標Ａの構造や材質などの諸元、さらに、その時刻における目標Ａの位置や向きによって評価可能である。
【００２８】
具体的には、まず、レーダ方程式を利用して、送受信ユニット（△印）において、目標Ａからの反射波を受信する際のＳ／Ｎ比を求める。さらに、Ｓ／Ｎ比と、あらかじめ設定した許容可能な誤警報確率とにより、探知確率を求めることができる。
ここで、目標Ａを探知できない確率、すなわち「１−探知確率」を、「見逃し確率」という。
【００２９】
上記手順において、目標Ａの構造、材質、向きなどの諸元は、レーダ方程式を構成する要素であるレーダ反射断面積を評価するために利用される。
具体的には、あらかじめ、送受信ユニット（△印）を基準とした目標Ａが取りうる向きを離散化し、離散化したそれぞれの目標Ａの向きについて、実験またはコンピュータシミュレーションにより、レーダ反射断面積を求めてデータベース化しておく。
【００３０】
以下、見逃し確率評価時には、送受信ユニット（△印）を基準とした目標Ａの向きに基づき、上記データベースを検索して、必要に応じて補間処理を行うことにより、レーダ反射断面積を得る。
【００３１】
上記説明では、単一の送受信ユニット（△印）による捜索について述べたが、送信ユニット（○印）と受信ユニット（□印）との対によって捜索を行うことも可能であり、この形態の運用を「バイスタティック運用」という。
【００３２】
また、或る時刻における目標Ａが、バイスタティック運用を行う特定の送信ユニット／受信ユニットの対の捜索によってどの程度探知可能であるかも、上記と同様に、目標の向きなどからレーダ反射断面積を評価し、さらにレーダ方程式などを利用することによって、評価可能である。
【００３３】
上記説明では、或る時刻における、単一の送受信ユニット（△印）、または単一の送信ユニット／受信ユニット対による捜索について述べたが、センサ群においては、一般に、このような送受信ユニットや、送信ユニット／受信ユニット対が複数存在する。
【００３４】
このような場合、センサ群の全体としての探知可能性は、以下のように評価することができる。
まず、各送受信ユニット（△印）、または送信ユニット／受信ユニット対における目標Ａの見逃し確率を求め、続いて、各確率の積を計算すれば、センサ群の全体としての、目標Ａの見逃し確率を評価することができる。
【００３５】
なお、どの送信ユニット／受信ユニット対についてバイスタティック運用を行うかが定まらない場合は、すべての送信ユニット／受信ユニットの対でバイスタティック運用を行うと仮定するなどして、上記処理を行えばよい。
また、その時刻に捜索を行わないと想定される送受信ユニット（△印）、または送信ユニット／受信ユニット対については、見逃し確率を「１」として上記処理を行えばよい。
【００３６】
上記説明では、或る時刻におけるセンサ群の全体としての、目標Ａの見逃し確率の評価方法について述べたが、一方、一般にセンサの運用においては、一定の捜索周期間隔で、捜索が繰り返し行われる。
そこで、一定時間間隔で刻んだ連続する複数時刻を通じての、センサ群全体としての探知可能性を評価することが要求される。
【００３７】
この評価要求を実現するためには、まず、各時刻におけるセンサ群全体としての見逃し確率を算出し、続いて、各時刻における見逃し確率の積を取れば、上記連続する複数時刻を通じての、センサ群全体としての、目標の見逃し確率を算出することができる。
以下、連続する複数時刻を通じての目標の見逃し確率を「累積見逃し確率」という。
【００３８】
なお、上記累積見逃し確率の評価において、各時刻における見逃し確率を評価する際には、一般に、目標Ａの位置や向きが動的に変化することに留意する必要がある。
この、見逃し確率算出に影響を与えるような、目標Ａの位置や向きなど、動的に変化する諸元を、以下「目標状態」という。
【００３９】
前述のように、この発明の実施の形態１に係るセンサ配置評価装置は、目標Ａが監視対象領域２０１を移動途中に、配置されたセンサ群によって高確率で探知可能か否かを評価することが目的である。
【００４０】
具体的には、目標Ａの取りうる、スタート地点からゴール領域２０２に至る経路（破線矢印）について、その間のセンサ群による「累積見逃し確率」が、あらかじめ定めた閾値を下回った場合に、「高確率で探知可能」と判定する。
【００４１】
次に、図２の説明図を参照しながら、図１に示したこの発明の実施の形態１に係るセンサ配置評価装置の動作について説明する。
図１において、まず、地形情報保持手段１０１は、電波遮蔽条件を判定する場合に必要な地形情報を保持する。
【００４２】
一般に、センサと目標Ａとの間が地形によって遮蔽されると、センサに電波が届かないので目標Ａの探知が不可能となるが、地形情報保持手段１０１内の地形情報は、電波遮蔽条件を判定する場合に必要となる。
【００４３】
目標情報保持手段１０２は、目標Ａの見逃し確率を算出する際に必要な目標情報（目標Ａの、動的に変化しない情報）を保持する。
具体的には、目標情報保持手段１０２は、たとえば、目標Ａに各方向から電波が到来する場合の、各方向に対するレーダ反射断面積に関するデータを保持する。
【００４４】
センサ情報保持手段１０３は、目標Ａの見逃し確率を算出する際に必要な、各センサの情報を保持し、センサ配置保持手段１０４は、各センサの配置情報を保持し、監視対象領域保持手段１０５は、ユーザが設定する監視対象領域２０１およびゴール領域２０２を保持する。
【００４５】
目標状態探索状況保持手段１０９は、目標状態と累積見逃し確率との対をノードとするツリー構造（以下、「目標状態ツリー」という）を保持する。
ここで、目標状態ツリーについて説明する。
目標状態ツリーは、スタート地点における目標状態に関するノードをルートノードとして、センサ配置評価処理の過程で、子ノードの生成の反復により、拡張されていく。
【００４６】
ルートノード以外の各ノードの目標状態は、その親ノードの目標状態から、あらかじめ定めた時間間隔（以下、「時刻進行間隔」という）後の目標状態を表す。
ここで、目標Ａの動き方には自由度があるので、一般に、各ノードの下には、複数の子ノードが生成される可能性がある。つまり、目標状態ツリーを、ルートノードから子ノードに順次たどっていくと、時刻進行間隔ごとの目標状態の時系列が得られることになる。
【００４７】
また、各ノードの累積見逃し確率は、ルートノード（つまり、スタート地点）における目標状態から、当該ノードの目標状態に至るまでの累積見逃し確率を表す。
目標状態ツリーの拡張の過程において、以下の性質（Ａ１）、（Ａ２）の両方を有する目標状態が生成されれば、「目標が監視対象領域２０１を移動途中に、高確率で探知不可能な場合がある」と判定することができる。
【００４８】
（Ａ１）当該目標状態がゴール領域２０２に到達している。
（Ａ２）当該目標状態の累積見逃し確率があらかじめ定めた閾値以上である。
なお、時刻進行間隔は、センサ群を構成する各センサの捜索周期に基づいて決めておけばよい。
【００４９】
図１に戻り、初期目標状態指定手段１０６は、センサ配置評価処理開始時に、スタート地点における目標状態を設定する。
見逃し確率算出手段１０７は、初期目標状態指定手段１０６により指定された目標状態、または目標状態生成手段１１５（後述する）により生成された目標状態について、その見逃し確率を算出する。
このとき、見逃し確率は、目標状態の他、地形情報、目標の動的に変化しない情報、センサ情報、センサ配置情報を利用して算出される。
【００５０】
累積見逃し確率算出手段１０８は、見逃し確率算出手段１０７が出力した見逃し確率に基づき、累積見逃し確率を算出する。
このとき、対象とする目標状態が、初期目標状態指定手段１０６が指定したものであれば、累積見逃し確率算出手段１０８により算出される累積見逃し確率は、見逃し確率算出手段１０７から出力された見逃し確率の値に等しい。
【００５１】
一方、対象とする目標状態が、目標状態生成手段１１５が生成したものである場合には、累積見逃し確率算出手段１０８は、以下のように、累積見逃し確率を算出する。
なお、後述するが、目標状態生成手段１１５が生成した目標状態に関しては、生成元の目標状態が存在する。
【００５２】
対象とする目標状態が、目標状態生成手段１１５が生成したものである場合、まず、累積見逃し確率算出手段１０８は、生成元の目標状態の累積見逃し確率を目標状態探索状況保持手段１０９から取得し、生成元の目標状態の累積見逃し確率と、見逃し確率算出手段１０７から出力された見逃し確率との積を取ることにより、対象とする目標状態の累積見逃し確率を算出する。
【００５３】
累積見逃し確率算出手段１０８は、累積見逃し確率を算出すると、対応する目標状態とともに、目標状態探索状況保持手段１０９内の目標状態ツリーに、新たなノードとして追加する。
【００５４】
すなわち、累積見逃し確率算出手段１０８は、対象とする目標状態が、初期目標状態指定手段１０６が指定したものであれば、目標状態探索状況保持手段１０９内の目標状態ツリーのルートノードとして設定する。
一方、対象とする目標状態が、目標状態生成手段１１５が生成したものであれば、生成元の目標状態に対応するノードの子ノードとして追加する。
【００５５】
目標状態選択手段１１０は、目標状態探索状況保持手段１０９が保持する目標状態ツリーにおいて、累積見逃し確率が閾値以上であるノードから、１つの目標状態を選択する。この選択は、累積見逃し確率が十分低い目標状態については、センサ群によって高い確率で探知可能であることから、それ以上の探索を実行しても意味がないので、探索の対象としないという考え方に基づいている。
【００５６】
目標状態生成手段１１５は、目標状態選択手段１１０が選択した目標状態に基づき、その時刻進行間隔後の目標状態を新たに生成する。
終了判定手段１２１は、目標状態生成手段１１５が生成した目標状態が、ゴール領域２０２に到達しているか否かを判定し、ゴール領域２０２に到達していると判定された場合には、「目標が監視対象領域２０１を高い累積見逃し確率で横断可能な場合がある」として、センサ配置の評価処理を終了する。
【００５７】
終了判定手段１２１は、上記判定において、センサ配置評価処理を終了しなかった場合には、さらに、目標状態探索状況保持手段１０９が保持する目標状態ツリーを構成するノード数が、所定値以上であるか否かを判定する。
【００５８】
上記判定結果が、「ノード数≧所定値」であった場合には、「目標が監視対象領域２０１を高い累積見逃し確率で横断することは困難」と見なして、センサ配置評価処理を終了する。
【００５９】
この判定結果は、十分に目標状態の探索を実行したのにもかかわらず、所定の閾値以上の累積見逃し確率を保ってゴール領域２０２に到達する目標状態が見つからないのであれば、追加探索処理を実行しても、そのような目標状態は見つからない可能性が高いであろう、という考え方に基づいている。
【００６０】
以下、目標状態探索状況保持手段１０９と関連した目標状態選択手段１１０の動作について、さらに詳細に説明する。
まず、目標状態選択手段１１０内の目標状態確率分布設定手段１１１は、目標状態探索状況保持手段１０９が保持する目標状態ツリーにおいて、累積見逃し確率が閾値以上であるノードを抽出し、それぞれの目標状態の選択のされやすさを表す確率分布を設定する。
また、目標状態選択手段１１０内の目標状態確率的選択手段１１４は、目標状態確率分布設定手段１１１が設定した確率分布に基づき、１つの目標状態を確率的に選択する。
【００６１】
次に、目標状態確率分布設定手段１１１の動作について、さらに詳細に説明する。
まず、目標状態確率分布設定手段１１１内の目標状態確率分布保持手段１１２は、目標状態探索状況保持手段１０９が保持する目標状態ツリーにおいて、累積見逃し確率が閾値以上であるノードを抽出し、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。この初期化時においては、たとえば、各目標状態に対して一様な確率分布を設定すればよい。
【００６２】
また、目標状態確率分布設定手段１１１内のゴール距離対応目標状態確率分布加工手段１１３は、各目標状態とゴール領域２０２との間の距離（以下「ゴール距離」と呼ぶ）が近いほど、選択される確率が高くなるように、目標状態確率分布保持手段１１２が保持する確率分布を加工する。
【００６３】
以下、目標状態選択手段１１０と関連した目標状態生成手段１１５の動作について、さらに詳細に説明する。
まず、目標状態生成手段１１５内の目標状態候補生成手段１１６は、目標状態選択手段１１０が選択した目標状態に基づき、その時刻進行間隔後の目標状態として想定される候補（以下、「目標状態候補」という）を複数生成する。
【００６４】
また、目標状態生成手段１１５内の目標状態候補確率分布設定手段１１７は、目標状態候補生成手段１１６が生成した複数の目標状態候補について、それぞれの選択のされやすさを表す確率分布を設定する。
さらに、目標状態生成手段１１５内の目標状態候補確率的選択手段１２０は、目標状態候補確率分布設定手段１１７が設定した確率分布に基づき、複数の目標状態候補から、１つの目標状態を確率的に選択する。
【００６５】
次に、目標状態候補確率分布設定手段１１７の動作について、さらに詳細に説明する。
まず、目標状態候補確率分布設定手段１１７内の目標状態候補確率分布保持手段１１８は、目標状態候補生成手段１１６が生成した複数の目標状態候補について、それぞれの目標状態候補の選択のされやすさを表す確率分布を初期化して保持する。
【００６６】
この初期化時においては、たとえば、各目標状態に対して一様な確率分布を設定すればよい。または、進行方向の変化が小さいほど、確率が高くなるよう確率分布を設定してもよい。これは、現実の目標の動きとして、進行方向を大きく変えるような移動が行われることは少ないであろう、との考え方に基づく方法である。
【００６７】
続いて、目標状態候補確率分布設定手段１１７内のゴール距離対応目標状態候補確率分布加工手段１１９は、各目標状態候補とゴール領域２０２との間のゴール距離が近いほど、選択される確率が高くなるように、目標状態候補確率分布保持手段１１８が保持する確率分布を加工する。
【００６８】
次に、図３のフローチャートを参照しながら、図１に示したこの発明の実施の形態１に係るセンサ配置評価装置の処理動作について、さらに具体的に説明する。
図３において、まず初めに、目標状態探索状況保持手段１０９は、自身が保持する目標状態ツリーを空に初期化する（ステップ３０１）。
【００６９】
続いて、見逃し確率算出手段１０７は、初期目標状態指定手段１０６で指定された、スタート地点における目標状態に関する見逃し確率を算出して、目標状態とともに、累積見逃し確率算出手段１０８に出力する（ステップ３０２）。
【００７０】
また、このとき、累積見逃し確率算出手段１０８は、見逃し確率算出手段１０７から取得した目標状態および見逃し確率を、目標状態探索状況保持手段１０９が保持する目標状態ツリーのルートノードとして設定する（ステップ３０２）。
ここで、ルートノードの累積見逃し確率は、スタート地点における目標状態の見逃し確率とする。
【００７１】
次に、目標状態選択手段１１０は、目標状態探索状況保持手段１０９が保持する目標状態ツリーから、１つの目標状態を選択する（ステップ３０３）。
この際、累積見逃し確率が閾値未満である目標状態は、選択対象から外す。
【００７２】
続いて、目標状態生成手段１１５は、目標状態選択手段１１０が選択した目標状態に基づき、その時刻進行間隔後の目標状態を新たに生成する（ステップ３０４）。
次に、終了判定手段１２１は、目標状態生成手段１１５が生成した目標状態が、ゴール領域２０２に到達しているか否かを判定する（ステップ３０５）。
【００７３】
ステップ３０５において、ゴール領域２０２に到達している（すなわち、ＹＥＳ）と判定された場合は、「目標が監視対象領域２０１を高い累積見逃し確率で横断可能な場合がある」と見なして（ステップ３０６）、図３のセンサ配置評価処理を終了する。
【００７４】
一方、ステップ３０５において、ゴール領域２０２に到達していない（すなわち、ＮＯ）と判定されれば、続いて、終了判定手段１２１は、目標状態探索状況保持手段１０９が保持する目標状態ツリーを構成するノード数が、所定値以上であるか否かを判定する（ステップ３０７）。
【００７５】
ステップ３０７において、ノード数が所定値以上である（すなわち、ＹＥＳ）と判定された場合は、「目標が監視対象領域２０１を高い累積見逃し確率で横断することは困難」と見なして（ステップ３０８）、図３のセンサ配置評価処理を終了する。
【００７６】
一方、ステップ３０７において、ノード数が所定値未満である（すなわち、ＮＯ）と判定されれば、見逃し確率算出手段１０７は、目標状態生成手段１１５が生成した目標状態の見逃し確率を算出する（ステップ３０９）。
【００７７】
また、このとき、累積見逃し確率算出手段１０８は、生成元の目標状態の累積見逃し確率と、見逃し確率算出手段１０７が出力した見逃し確率とから、累積見逃し確率を算出する（ステップ３０９）。
【００７８】
さらに、累積見逃し確率算出手段１０８は、目標状態および累積見逃し確率を、目標状態探索状況保持手段１０９が保持する目標状態ツリーに、生成元の目標状態に対応するノードの子ノードとして追加して（ステップ３０９）、ステップ３０３の処理に復帰する。
【００７９】
次に、図１とともに、図４〜図１０の説明図を参照しながら、センサ配置評価処理の具体的な手順について説明する。
図４はスタート地点における目標状態（２等辺３角形Ａで示す）の例を示している。
図４において、目標状態（２等辺３角形Ａ）は、具体的には目標の位置および向きにより構成されており、２等辺３角形Ａの位置は、目標の位置を示し、２等辺３角形Ａの頂角方向は、目標の向きを示している。
【００８０】
また、目標状態Ａの横に示す数値は、累積見逃し確率を表し、ここでは、スタート地点における目標状態Ａの見逃し確率が「１．００」であったものとしている。
また、図４においては、スタート地点における目標状態に関するノードのみ（破線枠内参照）から構成される目標状態ツリーＴ１も示されている。
【００８１】
一方、図５は新たな目標状態Ｂを示しており、図４の目標状態ツリーＴ１から目標状態Ａを選択し、選択された目標状態Ａから新たな目標状態Ｂを生成した例を示している。
【００８２】
以下、目標状態選択手段１１０において、選択対象とする目標状態の条件を、「累積見逃し確率が所定の閾値０．５以上」とした場合について説明する。
この場合、累積見逃し確率が閾値「０．５」未満ならば、センサ群によって高い確率で探知可能と見なしていることになる。
【００８３】
図４においては、選択可能な目標状態はＡのみであることから、必然的に目標状態Ａが選択されており、図５においては、目標状態Ａの時刻進行間隔後の目標状態として、目標状態Ｂが生成されている。
【００８４】
図５において、目標状態Ｂの累積見逃し確率は、目標状態Ｂの生成元の目標状態Ａの累積見逃し確率と、目標状態Ｂの見逃し確率との積として計算され、ここでは、目標状態Ｂの累積見逃し確率が「０．９８」と算出されたものとしている。
また、図５においては、目標状態Ａと目標状態Ｂとに関するノードから構成される目標状態ツリーＴ２も示されている。図５の目標状態ツリーＴ２に示すように、目標状態Ｂのノードは、その生成元である目標状態Ａの子ノードとなっている。
【００８５】
次に、図６は新たな目標状態Ｃを示しており、図５の目標状態ツリーＴ２から目標状態Ｂを選択し、選択された目標状態Ｂから新たな目標状態Ｃを生成した例を示している。
図５においては、選択可能な目標状態はＡおよびＢであり、これらの中から目標状態Ｂが選択されており、図６においては、さらに、目標状態Ｂの時刻進行間隔後の目標状態として、目標状態Ｃが生成されている。
【００８６】
図６において、目標状態Ｃの累積見逃し確率は、目標状態Ｃの生成元の目標状態Ｂの累積見逃し確率と、目標状態Ｃの見逃し確率との積として計算され、ここでは、目標状態Ｃの累積見逃し確率が「０．３５」と算出されたものとしている。
【００８７】
このとき、目標状態Ｃの累積見逃し確率「０．３５」が所定の閾値「０．５」未満であることから、以降の探索において、目標状態Ｃ（黒塗りの２等辺３角形参照）は選択されないことになる。
図６を含め、以降の説明図において、次回の探索で選択されない目標状態は、黒塗りの２等辺３角形で示すものとする。
【００８８】
また、図６においては、目標状態Ａ、Ｂ、Ｃに関するノードから構成される目標状態ツリーＴ３も示されている。図６の目標状態ツリーＴ３に示すように、目標状態Ｃのノードは、その生成元である目標状態Ｂの子ノードとなっている。
【００８９】
次に、図７は新たな目標状態Ｄを示しており、図６の目標状態ツリーＴ３から目標状態Ｂを選択し、選択された目標状態Ｂから新たな目標状態Ｄを生成した例を示している。
図６においては、選択可能な目標状態はＡおよびＢであり、これらの中から目標状態Ｂが選択されており、図７においては、さらに、目標状態Ｂの時刻進行間隔後の目標状態として、目標状態Ｄが生成されている。
【００９０】
図７において、目標状態Ｄの累積見逃し確率は、目標状態Ｄの生成元の目標状態Ｂの累積見逃し確率と、目標状態Ｄの見逃し確率との積として計算され、ここでは、目標状態Ｄの累積見逃し確率が「０．８６」と算出されたものとしている。
また、図７においては、目標状態Ａ、Ｂ、Ｃ、Ｄに関するノードから構成される目標状態ツリーＴ４も示されている。図７の目標状態ツリーＴ４に示すように、目標状態Ｄのノードは、その生成元である目標状態Ｂの子ノードとなっている。
【００９１】
次に、図８は新たな目標状態Ｅを示しており、図７の目標状態ツリーＴ４から目標状態Ｄを選択し、選択された目標状態Ｄから新たな目標状態Ｅを生成した例を示している。
図７においては、選択可能な目標状態はＡ、Ｂ、Ｄであり、これらの中から目標状態Ｄが選択されており、図８においては、さらに、目標状態Ｄの時刻進行間隔後の目標状態として、目標状態Ｅが生成されている。
【００９２】
図８において、目標状態Ｅの累積見逃し確率は、目標状態Ｅの生成元の目標状態Ｄの累積見逃し確率と、目標状態Ｅの見逃し確率との積として計算され、ここでは、目標状態Ｅの累積見逃し確率が「０．８４」と算出されたものとしている。
また、図８においては、目標状態Ａ、Ｂ、Ｃ、Ｄ、Ｅに関するノードから構成される目標状態ツリーＴ５も示されている。図８の目標状態ツリーＴ５に示すように、目標状態Ｅのノードは、その生成元である目標状態Ｄの子ノードとなっている。
【００９３】
次に、図９は新たな目標状態Ｆを示しており、図８の目標状態ツリーＴ５から目標状態Ｂを選択し、選択された目標状態Ｂから新たな目標状態Ｆを生成した例を示している。
図８においては、選択可能な目標状態はＡ、Ｂ、Ｄ、Ｅであり、これらの中からＢが選択されたものとしており、図９においては、さらに、目標状態Ｂの時刻進行間隔後の目標状態として、目標状態Ｆが生成されている。
【００９４】
図９において、目標状態Ｆの累積見逃し確率は、目標状態Ｆの生成元の目標状態Ｂの累積見逃し確率と、目標状態Ｆの見逃し確率との積として計算され、ここでは、目標状態Ｆの累積見逃し確率が「０．４０」と算出されたものとしている。
このとき、目標状態Ｆの累積見逃し確率「０．４０」が閾値「０．５」未満であることから、以降の探索において、目標状態Ｆ（黒塗りの２等辺３角形参照）は選択されないことになる。
【００９５】
また、図９においては、目標状態Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆに関するノードから構成される目標状態ツリーＴ６も示されている。図９の目標状態ツリーＴ６に示すように、目標状態Ｆのノードは、その生成元である目標状態Ｂの子ノードとなっている。
【００９６】
以上の図４〜図９に示すように、センサ配置評価処理においては、目標状態ツリーの拡張処理（Ｔ１→Ｔ２→、・・・→Ｔ６）が繰り返し実行される。
この結果、図１０に示すように、最終的に、目標状態ツリーＴｘが得られた場合を考える。
【００９７】
図１０においては、新たな目標状態Ｘを生成した例が示されている。
この場合、目標状態Ｘがゴール領域２０２に達しているので、終了判定手段１２１は、「目標が監視対象領域２０１を高い累積見逃し確率で横断可能な場合がある」と判定して、センサ配置評価処理を終了させることになる。
【００９８】
一方、目標状態ツリーを構成するノード数が所定値を超えても、図１０に示すように、ゴール領域２０２に到達する目標状態Ｘが出現しなければ、終了判定手段１２１は、「目標が監視対象領域２０１を高い累積見逃し確率で横断することは困難」と判定して、センサ配置評価処理を終了させることになる。
【００９９】
次に、図１とともに、図１１の説明図を参照しながら、目標状態選択手段１１０による目標状態の選択方法について、具体的に説明する。
図１１においては、センサ配置評価処理過程における、或る時点での目標状態ツリーの構成例が示されている。
【０１００】
目標状態選択手段１１０において、まず、目標状態確率分布設定手段１１１内の目標状態確率分布保持手段１１２は、目標状態ツリー上の、選択可能な（つまり、累積見逃し確率が閾値以上の）ノードにおいて、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。
図１１の場合、選択可能な目標状態（白抜き２等辺３角形）はＡ、Ｂ、Ｃ、Ｄであり、初期化時点においては、これらが選択される確率はすべて同じ値に設定される。
【０１０１】
続いて、目標状態確率分布設定手段１１１内のゴール距離対応目標状態確率分布加工手段１１３は、各目標状態Ａ〜Ｄとゴール領域２０２との間のゴール距離ＬＡ、ＬＢ、ＬＣ、ＬＤを算出する。
図１１においては、各目標状態Ａ〜Ｄのゴール距離ＬＡ〜ＬＤが示されている。
【０１０２】
また、ゴール距離対応目標状態確率分布加工手段１１３は、小さいゴール距離を有する目標状態の選択確率が高くなるように、目標状態確率分布保持手段１１２が保持する確率分布を加工する。
【０１０３】
なお、ゴール距離対応目標状態確率分布加工手段１１３による具体的な加工方法としては、たとえば、まず、目標状態確率分布保持手段１１２が保持する各目標状態Ａ〜Ｄの確率を、それぞれゴール距離ＬＡ〜ＬＤで除算し、その後、確率の和が「１」となるように、各確率を規格化すればよい。
最後に、目標状態確率的選択手段１１４は、目標状態確率分布保持手段１１２が保持する加工後の確率分布に基づき、１つの目標状態を確率的に選択する。
【０１０４】
次に、図１とともに、図１２および図１３の説明図を参照しながら、目標状態生成手段１１５による目標状態の生成方法について、具体的に説明する。
まず、目標状態生成手段１１５内の目標状態候補生成手段１１６は、目標状態が、時刻進行間隔後にどのように変化するかについて、その代表的な変化の仕方を複数個保持する。この変化の仕方は、目標状態の運動性能などの制約を反映したものとする。
【０１０５】
図１２は代表的な目標状態の変化例を示しており、目標ｎが右に曲がる場合（ａ）と、目標ｎが真っ直ぐに移動する場合（ｂ）と、目標ｎが左に曲がる場合（ｃ）と、の３通りの変化の仕方を保持する例を示している。
【０１０６】
目標状態候補生成手段１１６は、目標状態選択手段１１０が選択した目標状態に基づき、図１２に示した代表的な目標状態変化（ａ）〜（ｃ）にしたがって、図１３のように、時刻進行間隔後の目標状態候補ａ〜ｃを生成する。
図１３においては、選択された目標状態から、代表的な目標状態変化（図１２参照）にしたがって得られる目標状態候補ａ〜ｃの例を示している。
【０１０７】
続いて、目標状態候補確率分布設定手段１１７内の目標状態候補確率分布保持手段１１８は、目標状態候補生成手段１１６が生成した複数の目標状態候補について、それぞれの目標状態候補の選択のされやすさを表す確率分布を初期化して保持する。
【０１０８】
図１３の場合、目標状態候補はａ、ｂ、ｃであり、初期化時点において、これらの目標状態候補ａ、ｂ、ｃが選択される確率は、すべて同じ値に設定されている。
または、一般に目標ｎは、図１２内の（ｂ）のよう、真っ直ぐに移動する可能性の方が高いことを想定し、目標状態候補ｂの確率を、目標状態候補ａ、ｃの確率よりも高い値に初期設定してもよい。
【０１０９】
続いて、目標状態候補確率分布設定手段１１７内のゴール距離対応目標状態候補確率分布加工手段１１９は、各目標状態候補ａ〜ｃとゴール領域２０２との間のゴール距離Ｌａ〜Ｌｃを算出する。
図１３においては、各目標状態候補ａ、ｂ、ｃのゴール距離Ｌａ〜Ｌｃが示されている。
【０１１０】
また、ゴール距離対応目標状態候補確率分布加工手段１１９は、小さいゴール距離を有する目標状態候補の選択確率が高くなるように、目標状態候補確率分布保持手段１１８が保持する確率分布を加工する。
【０１１１】
具体的な加工方法としては、たとえば、まず、目標状態候補確率分布保持手段１１８が保持する各目標状態ａ〜ｃの確率を、それぞれゴール距離Ｌａ〜Ｌｃで除算し、その後、確率の和が「１」となるように、各確率を規格化すればよい。
【０１１２】
最後に、目標状態生成手段１１５内の目標状態候補確率的選択手段１２０は、目標状態候補確率分布保持手段１１８が保持する加工後の確率分布に基づき、１つの目標状態候補を確率的に選択し、新たな目標状態として出力する。
【０１１３】
以上のように、この発明の実施の形態１（図１）に係るセンサ配置評価装置は、複数のセンサの配置を評価するために、目標状態探索状況保持手段１０９と、目標状態選択手段１１０と、目標状態生成手段１１５と、見逃し確率算出手段１０７と、累積見逃し確率算出手段１０８と、終了判定手段１２１とを備えている。
【０１１４】
目標状態探索状況保持手段１０９は、目標の位置または向きに関する情報を含む目標状態と、目標の累積見逃し確率との対をノードとするツリー構造からなる目標状態ツリーを保持し、ツリー構造のルートノードは、初期目標状態に対応する。
目標状態選択手段１１０は、目標状態探索状況保持手段１０９が保持する目標状態ツリーにおいて、累積見逃し確率があらかじめ定めた閾値以上であるノードから、１つの目標状態を選択する。
【０１１５】
目標状態生成手段１１５は、目標状態選択手段１１０が選択した目標状態に基づき、その一定時間後の目標状態を新たに生成する。
見逃し確率算出手段１０７は、初期目標状態、または目標状態生成手段が生成した目標状態について、目標状態と、複数のセンサに関するセンサ情報およびセンサ配置情報とを利用して、目標状態の見逃し確率を算出する。
【０１１６】
累積見逃し確率算出手段１０８は、目標状態生成手段１１５が生成した目標状態について、目標状態の生成元の目標状態の累積見逃し確率と、見逃し確率算出手段１０７が算出した目標状態の見逃し確率との積を取ることにより、目標状態の累積見逃し確率を算出する。
また、累積見逃し確率算出手段１０８は、目標状態ごとに、目標状態探索状況保持手段１０９が保持する目標状態ツリーに対し、目標状態の生成元の目標状態に対応するノードの子ノードとして追加する。
【０１１７】
終了判定手段１２１は、目標状態生成手段１１５が生成した目標状態が、目標の目的地であるゴール領域に到達している場合には、複数のセンサの配置が性能不十分と評価して、評価処理を終了する。
また、終了判定手段１２１は、目標状態探索状況保持手段１０９が保持する目標状態ツリーを構成するノード数が所定値以上である場合には、複数のセンサの配置が性能十分と評価して、評価処理を終了する。
【０１１８】
さらに具体的には、目標状態選択手段１１０は、目標状態探索状況保持手段１０９が保持する目標状態ツリーからの目標状態選択において、目標状態とゴール領域２０２との間のゴール距離が小さいほど、高確率で選択する。
また、目標状態生成手段１１５は、目標状態選択手段１１０が選択した目標状態に基づく目標状態生成において、ゴール領域２０２との間のゴール距離が小さい目標状態を、高確率で新たに生成する。
【０１１９】
このように、確率的に目標状態ツリーを拡張して、かつ、累積見逃し確率が十分低い目標状態は「センサ群によって高い確率で探知可能」と評価して、それ以上の探索を行わないように構成したので、見逃し確率算出の対象となる目標状態数が、従来手法と比較して大幅に削減される。
【０１２０】
したがって、少ない計算量で、監視対象領域２０１を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価することができ、さらに、評価の過程で目標の自然な動き方を考慮可能にすることができ、処理時間を大幅に短縮するという効果を奏する。
【０１２１】
すなわち、目標状態の生成において、目標の運動性能などの制約を反映可能であることから、目標の自然な動き方のみを累積見逃し確率の算出対象とでき、無駄な処理を回避することができる。
【０１２２】
また、目標状態ツリーからの目標状態選択において、ゴール距離が小さいほど選択確率が高くなるように、各目標状態の確率分布を設定することにより、ゴール領域２０２に近い目標状態の方が、他の目標状態よりも選択されやすくなるので、センサ配置評価処理において、目標状態ツリーがゴール状態に向かって早期に拡張される。
したがって、「目標が監視対象領域２０１を高い累積見逃し確率で横断可能な場合がある」という状況下では、短い処理時間で判定が可能になるという効果を奏する。
【０１２３】
さらに、この発明の実施の形態１によれば、選択された目標状態からの新たな目標状態生成において、ゴール距離が小さいほど選択確率が高くなるように、各目標状態候補の確率分布を設定するので、新たな目標状態として、ゴール領域２０２に近い目標状態候補の方が、他の目標状態候補よりも選択されやすくなる。
【０１２４】
したがって、センサ配置評価処理において、目標状態ツリーが、ゴール状態に向かって早期に拡張されるので、「目標が監視対象領域２０１を高い累積見逃し確率で横断可能な場合がある」という状況下では、短い処理時間で判定が可能になるという効果を奏する。
【０１２５】
実施の形態２．
なお、上記実施の形態１（図１）では、目標状態選択手段１１０（目標状態生成手段１１５）において、ゴール距離対応目標状態確率分布加工手段１１３（ゴール距離対応目標状態候補確率分布加工手段１１９）を用いたが、図１４のように、ボロノイ（Ｖｏｒｏｎｏｉ）辺対応目標状態確率分布加工手段１１３Ａ（ボロノイ辺対応目標状態候補確率分布加工手段１１９Ａ）を用いてもよい。
【０１２６】
以下、図１４〜図１７を参照しながら、この発明の実施の形態２について説明する。
図１４はこの発明の実施の形態２に係るセンサ配置評価装置の構成を示すブロック図であり、前述（図１参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
【０１２７】
また、図１４において、目標状態選択手段１１０Ａ、目標状態生成手段１１５Ａ、目標状態確率分布設定手段１１１Ａおよび目標状態候補確率分布設定手段１１７Ａは、ぞれぞれ、前述（図１）の目標状態選択手段１１０、目標状態生成手段１１５、目標状態確率分布設定手段１１１および目標状態候補確率分布設定手段１１７に対応する。
【０１２８】
この場合、目標状態選択手段１１０Ａおよび目標状態生成手段１１５Ａ内において、目標状態確率分布設定手段１１１Ａおよび目標状態候補確率分布設定手段１１７Ａの構成のみが前述（図１）と異なり、他の構成は前述と同様である。
【０１２９】
目標状態確率分布設定手段１１１Ａは、目標状態確率分布保持手段１１２と、ボロノイ辺対応目標状態確率分布加工手段１１３Ａとにより構成されている。
目標状態候補確率分布設定手段１１７Ａは、目標状態候補確率分布保持手段１１８と、ボロノイ辺対応目標状態候補確率分布加工手段１１９Ａとにより構成されている。
【０１３０】
次に、図１５〜図１７の説明図を参照しながら、図１４に示したこの発明の実施の形態２に係るセンサ配置評価装置の動作について説明する。
まず、目標状態選択手段１１０Ａ内の目標状態確率分布設定手段１１１Ａについて説明する。ここで、目標状態確率分布設定手段１１１Ａ内の目標状態確率分布保持手段１１２の動作は、実施の形態１と同じなので省略する。
【０１３１】
目標状態確率分布設定手段１１１Ａ内のボロノイ辺対応目標状態確率分布加工手段１１３Ａは、あらかじめ、各センサの位置を母点とするボロノイ図を生成して保持しておく。
図１５は複数のセンサの各位置を母点としたボロノイ図の例を示している。ボロノイ図とは、空間を、「どの母点に最も近いか」によって、母点数分の小領域に分割してできる図である。
【０１３２】
ボロノイ辺対応目標状態確率分布加工手段１１３Ａは、センサ配置評価処理過程において、目標状態ツリーから１つの目標状態を選択する際に、各目標状態と、当該目標状態に最も近いボロノイ辺との間の距離（以下「ボロノイ辺距離」と呼ぶ）が近いほど、選択される確率が高くなるように、目標状態確率分布保持手段１１２が保持する確率分布を加工する。
【０１３３】
次に、目標状態生成手段１１５Ａ内の目標状態候補確率分布設定手段１１７Ａについて説明する。ここで、目標状態候補確率分布設定手段１１７Ａ内の目標状態候補確率分布保持手段１１８の動作は、前述と同じなので省略する。
【０１３４】
目標状態候補確率分布設定手段１１７Ａ内のボロノイ辺対応目標状態候補確率分布加工手段１１９Ａは、あらかじめ、各センサの位置を母点とするボロノイ図を保持しておく。
また、ボロノイ辺対応目標状態候補確率分布加工手段１１９Ａは、センサ配置評価処理過程において、複数の目標状態候補から１つの目標状態候補を選択する際に、各目標状態候補と、当該目標状態候補に最も近いボロノイ辺との間の距離が近いほど、選択される確率が高くなるように、目標状態候補確率分布保持手段１１８が保持する確率分布を加工する。
【０１３５】
次に、図１４とともに、図１６の説明図を参照しながら、目標状態選択手段１１０Ａによる目標状態の選択方法について、具体的に説明する。
図１６においては、センサ配置評価処理過程における、或る時点での目標状態ツリーの例を、各センサの位置を母点とするボロノイ図とともに示している。
【０１３６】
目標状態選択手段１１０Ａにおいて、まず、目標状態確率分布設定手段１１１Ａ内の目標状態確率分布保持手段１１２は、目標状態ツリー上の、選択可能な（つまり、累積見逃し確率が閾値以上の）ノードにおいて、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。
図１６の場合、選択可能な目標状態（白抜き２等辺３角形）はＡ、Ｂ、Ｃ、Ｄ、Ｅであり、初期化時点において、これらが選択される確率は、すべて同じ値に設定されている。
【０１３７】
続いて、目標状態確率分布設定手段１１１Ａ内のボロノイ辺対応目標状態確率分布加工手段１１３Ａは、各目標状態Ａ、Ｂ、Ｃ、Ｄ、Ｅと、当該目標状態に最も近いボロノイ辺との間のボロノイ辺距離ＶＡ、ＶＢ、ＶＣ、ＶＤ、ＶＥを算出する。
図１６においては、各目標状態Ａ〜Ｅのボロノイ辺距離ＶＡ〜ＶＥが示されている。
【０１３８】
また、ボロノイ辺対応目標状態確率分布加工手段１１３Ａは、小さいボロノイ辺距離を有する目標状態の選択確率が高くなるように、目標状態確率分布保持手段１１２が保持する確率分布を加工する。
【０１３９】
具体的な加工方法としては、たとえば、まず、目標状態確率分布保持手段１１２が保持する各目標状態Ａ〜Ｅの確率を、それぞれボロノイ辺距離ＶＡ〜ＶＥで除算し、その後、確率の和が「１」となるように、各確率を規格化すればよい。
最後に、目標状態確率的選択手段１１４は、目標状態確率分布保持手段１１２が保持する加工後の確率分布に基づき、１つの目標状態を確率的に選択する。
【０１４０】
次に、図１４とともに、図１７の説明図を参照しながら、目標状態生成手段１１５Ａによる目標状態の生成方法について、具体的に説明する。
まず、目標状態生成手段１１５Ａ内の目標状態候補生成手段１１６は、目標状態選択手段１１０Ａが選択した目標状態ｎ（図１７参照）に基づき、時刻進行間隔後の目標状態候補ａ〜ｃを生成する。
図１７においては、選択された目標状態ｎから得られる目標状態候補ａ〜ｃの例が示されている。
【０１４１】
続いて、目標状態候補確率分布設定手段１１７Ａ内の目標状態候補確率分布保持手段１１８は、目標状態候補生成手段１１６が生成した複数の目標状態候補ａ〜ｃについて、それぞれの目標状態候補の選択のされやすさを表す確率分布を初期化して保持する。
図１７の場合、目標状態候補はａ、ｂ、ｃであり、初期化時点において、これらが選択される確率は、たとえば、すべて同じ値に設定されるものとする。
【０１４２】
その後、目標状態候補確率分布設定手段１１７Ａ内のボロノイ辺対応目標状態候補確率分布加工手段１１９Ａは、各目標状態候補ａ〜ｃと、当該目標状態候補に最も近いボロノイ辺との間のボロノイ辺距離Ｖａ〜Ｖｃを算出する。
図１７においては、各目標状態候補ａ、ｂ、ｃのボロノイ辺距離Ｖａ〜Ｖｃが示されている。
【０１４３】
また、ボロノイ辺対応目標状態候補確率分布加工手段１１９Ａは、小さいボロノイ辺距離を有する目標状態候補の選択確率が高くなるように、目標状態候補確率分布保持手段１１８が保持する確率分布を加工する。
【０１４４】
具体的には、たとえば、まず、目標状態候補確率分布保持手段１１８が保持する各目標状態候補ａ〜ｃの確率を、それぞれボロノイ辺距離Ｖａ〜Ｖｃで除算し、その後、確率の和が「１」となるように、各確率を規格化すればよい。
最後に、目標状態候補確率的選択手段１２０は、目標状態候補確率分布保持手段１１８が保持する加工後の確率分布に基づき、１つの目標状態候補を確率的に選択し、新たな目標状態として出力する。
【０１４５】
以上のように、この発明の実施の形態２（図１４）による目標状態選択手段１１０Ａは、目標状態探索状況保持手段１０９が保持する目標状態ツリーからの目標状態選択において、複数のセンサの各位置を母点とするボロノイ図（図１５〜図１７）に関し、目標状態と、目標状態に最も近いボロノイ辺との間のボロノイ辺距離が小さいほど、高確率で選択する。
【０１４６】
また、この発明の実施の形態２（図１４）による目標状態生成手段１１５Ａは、目標状態選択手段１１０Ａが選択した目標状態に基づく目標状態生成において、複数のセンサの各位置を母点とするボロノイ図（図１５〜図１７）に関し、ボロノイ辺との間のボロノイ辺距離が小さい目標状態を、高確率で新たに生成する。
【０１４７】
このように、目標状態ツリーからの目標状態選択において、ボロノイ辺距離が小さいほど選択確率が高くなるように、各目標状態の確率分布を設定することにより、ボロノイ辺に近い目標状態が、より選択されやすくなる。
したがって、センサ配置評価処理において、目標状態ツリーがボロノイ辺に沿うような形で拡張されやすくなる。
【０１４８】
一方、一般に、目標は、センサからの距離が大きいほど探知されにくい傾向があり、目標が監視対象領域２０１を高い累積見逃し確率で横断可能な場合に、その経路は、複数のセンサの各位置を母点とするボロノイ辺の近傍を通過するものになることが多いと考えられるので、上記処理により、「目標が監視対象領域を高い累積見逃し確率で横断可能な場合がある」という状況下において、短い処理時間で判定が可能になるという効果を奏する。
【０１４９】
また、この発明の実施の形態２によれば、選択された目標状態からの新たな目標状態生成において、ボロノイ辺距離が小さいほど選択確率が高くなるように、各目標状態候補の確率分布を設定するので、新たな目標状態として、ボロノイ辺に近い目標状態候補の方が、他の目標状態候補よりも選択されやすくなる。
【０１５０】
これにより、センサ配置評価処理において、目標状態ツリーがボロノイ辺に沿うような形で拡張されやすくなるので、上記と同様に、「目標が監視対象領域を高い累積見逃し確率で横断可能な場合がある」という状況下において、短い処理時間で判定が可能になるという効果を奏する。
【０１５１】
さらに、ここでは、簡単のため、監視対象領域２０１およびゴール領域２０２が２次元の場合について説明したが、３次元の場合にも適用可能なことは言うまでもない。ただし、この場合、上記の「ボロノイ辺」を「ボロノイ面」に読み替える必要がある。
【０１５２】
実施の形態３．
なお、上記実施の形態１（図１）では、目標状態選択手段１１０において、ゴール距離対応目標状態確率分布加工手段１１３を用いたが、図１８のように、ゴール距離対応目標状態確率分布加工手段１１３に加えて（または、ゴール距離対応目標状態確率分布加工手段１１３に代えて）、累積見逃し確率対応目標状態確率分布加工手段１１３Ｂを用いてもよい。
【０１５３】
図１８はこの発明の実施の形態３に係るセンサ配置評価装置の構成を示すブロック図であり、前述（図１参照）と同様のものについては、前述と同一符号を付して詳述を省略する。
図１８において、前述（図１）との相違点は、目標状態選択手段１１０Ｂ内の目標状態確率分布設定手段１１１Ｂの構成のみであり、他の構成は前述と同様である。
【０１５４】
この場合、目標状態確率分布設定手段１１１Ｂは、前述と同様の目標状態確率分布保持手段１１２およびゴール距離対応目標状態確率分布加工手段１１３に加えて、累積見逃し確率対応目標状態確率分布加工手段１１３Ｂを備えている。
【０１５５】
以下、図１８に示したこの発明の実施の形態３による目標状態選択手段１１０Ｂの動作について、順を追って説明する。
まず、目標状態確率分布保持手段１１２は、目標状態ツリー上の、選択可能な（つまり、累積見逃し確率が閾値以上の）ノードにおいて、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。具体的には、たとえば、選択可能な目標状態に関して、その選択確率をすべて同じ値に設定する。
【０１５６】
続いて、ゴール距離対応目標状態確率分布加工手段１１３は、各目標状態とゴール領域２０２との間のゴール距離を算出し、小さいゴール距離を有する目標状態の選択確率が高くなるように、目標状態確率分布保持手段１１２が保持する確率分布を加工する。
【０１５７】
具体的には、前述のように、たとえば、まず、目標状態確率分布保持手段１１２が保持する各目標状態の確率を、それぞれゴール距離で除算し、その後、確率の和が「１」となるように、各確率を規格化すればよい。
【０１５８】
次に、累積見逃し確率対応目標状態確率分布加工手段１１３Ｂは、累積見逃し確率が高い目標状態ほど、選択される確率が高くなるように、目標状態確率分布保持手段１１２が保持する、ゴール距離対応目標状態確率分布加工手段１１３による加工済みの確率分布をさらに加工する。
【０１５９】
具体的には、たとえば、まず、目標状態確率分布保持手段１１２が保持する各目標状態の確率に対し、当該目標状態の累積見逃し確率を乗算し、その後、確率の和が「１」となるように、各確率を規格化すればよい。
最後に、目標状態確率的選択手段１１４は、目標状態確率分布保持手段１１２が保持する加工後の確率分布に基づき、１つの目標状態を確率的に選択する。
【０１６０】
以上のように、この発明の実施の形態３（図１８）による目標状態選択手段１１０Ｂは、累積見逃し確率対応目標状態確率分布加工手段１１３Ｂを備えており、目標状態探索状況保持手段１０９が保持する目標状態ツリーからの目標状態選択において、累積見逃し確率が高いほど高確率で選択する。
【０１６１】
このように、目標状態ツリーからの目標状態選択において、累積見逃し確率が高い目標状態ほど選択される確率が高くなるように、各目標状態の確率分布を設定することにより、累積見逃し確率が低い（その先の探索の望みが少ない）目標状態は、選択されにくくなるので、有望な領域を優先的に探索できるようになるという効果を奏する。
【０１６２】
なお、図１８においては、実施の形態１（図１）の構成に対して、累積見逃し確率対応目標状態確率分布加工手段１１３Ｂを追加した場合を示したが、目標状態確率分布設定手段１１１Ｂ内に累積見逃し確率対応目標状態確率分布加工手段１１３Ｂのみを設けてもよい。
また、前述の実施の形態２（図１４）の構成に対して、累積見逃し確率対応目標状態確率分布加工手段１１３Ｂを追加してもよく、上述と同等の作用効果を奏することは言うまでもない。
【符号の説明】
【０１６３】
１０１  地形情報保持手段、１０２  目標情報保持手段、１０３  センサ情報保持手段、１０４  センサ配置保持手段、１０５  監視対象領域保持手段、１０６  初期目標状態指定手段、１０７  見逃し確率算出手段、１０８  累積見逃し確率算出手段、１０９  目標状態探索状況保持手段、１１０、１１０Ａ、１１０Ｂ  目標状態選択手段、１１１、１１１Ａ、１１１Ｂ  目標状態確率分布設定手段、１１２  目標状態確率分布保持手段、１１３  ゴール距離対応目標状態確率分布加工手段、１１３Ａ  ボロノイ辺対応目標状態確率分布加工手段、１１３Ｂ  累積見逃し確率対応目標状態確率分布加工手段、１１４  目標状態確率的選択手段、１１５、１１５Ａ、１１５Ｂ  目標状態生成手段、１１６  目標状態候補生成手段、１１７、１１７Ａ、１１７Ｂ  目標状態候補確率分布設定手段、１１８  目標状態候補確率分布保持手段、１１９  ゴール距離対応目標状態候補確率分布加工手段、１１９Ａ  ボロノイ辺対応目標状態候補確率分布加工手段、１２０  目標状態候補確率的選択手段、１２１  終了判定手段、２０１  監視対象領域、２０２  ゴール領域、ＬＡ〜ＬＤ、Ｌａ〜Ｌｃ  ゴール距離、Ｔ１〜Ｔ６、Ｔｘ  目標状態ツリー、Ｖａ〜Ｖｃ  ボロノイ辺距離。
【図１】
2010281784.tif 000003
【図２】
2010281784.tif 000004
【図３】
2010281784.tif 000005
【図４】
2010281784.tif 000006
【図５】
2010281784.tif 000007
【図６】
2010281784.tif 000008
【図７】
2010281784.tif 000009
【図８】
2010281784.tif 000010
【図９】
2010281784.tif 000011
【図１０】
2010281784.tif 000012
【図１１】
2010281784.tif 000013
【図１２】
2010281784.tif 000014
【図１３】
2010281784.tif 000015
【図１４】
2010281784.tif 000016
【図１５】
2010281784.tif 000017
【図１６】
2010281784.tif 000018
【図１７】
2010281784.tif 000019
【図１８】
2010281784.tif 000020