説明

センサ配置評価装置

【課題】少ない計算量で、監視対象領域を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価可能なセンサ配置評価装置を得る。
【解決手段】目標状態ツリーを保持する目標状態探索状況保持手段109と、目標状態選択手段110と、目標状態生成手段115と、見逃し確率算出手段107と、累積見逃し確率算出手段108と、終了判定手段121とを備えている。目標状態ツリーは、目標の位置または向きに関する情報を含む目標状態と、目標の累積見逃し確率との対をノードとするツリー構造からなり、ツリー構造のルートノードは、初期目標状態に対応する。目標状態選択手段110は、目標状態ツリーにおいて、累積見逃し確率があらかじめ定めた閾値以上であるノードから、1つの目標状態を選択する。目標状態生成手段115は、選択した目標状態に基づき、その一定時間後の目標状態を新たに生成する。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、複数のセンサ(センサ群)をそれぞれ異なる場所に配置した際に、センサ群で監視すべき領域(以下、「監視対象領域」という)を目標が移動する過程で、センサ群によって高確率で探知可能か否かを評価するセンサ配置評価装置に関するものである。
【背景技術】
【0002】
従来から、複数のセンサをそれぞれ異なる場所に配置した際に、このセンサ群によって目標を高確率で探知可能か否かを評価するセンサ配置評価装置は、種々提案されている(たとえば、非特許文献1参照)。
【0003】
ここで、任意の目標(航空機、船舶、車両などの推進体)が、監視対象領域内を移動して、目標の目的地とする領域(以下、「ゴール領域」という)を目指して横切る状況を想定する。
【0004】
この場合、非特許文献1に記載の従来のセンサ配置評価装置においては、目標が監視対象領域を移動している途中に、センサ群によって探知可能か否かを評価するために、監視対象領域をグリッドで分割し、目標がグリッドに沿って移動することを仮定して、以下の手順により、センサ群の配置を評価していた。
【0005】
すなわち、まず、グリッドの各隣接点の間を目標が移動する際に、センサ群によって探知されない確率(以下、「見逃し確率」という)を求め、求められた見逃し確率に応じた数値を、各隣接点間を結ぶ線分の重みとして付与する。
【0006】
続いて、目標のスタート地点とゴール地点とを結ぶグリッド上の経路のうち、「その経路を移動中に探知されない確率」が最大のものを求める。
ここで、「経路を移動中に探知されない確率」は、その経路を構成する線分の見逃し確率の積として評価可能である。また、「経路を移動中に探知されない確率」が最大である経路を効率良く求めるためには、ダイクストラ法などの最短経路探索アルゴリズムを利用する。
【0007】
上記の評価方法を利用することにより、グリッド上の経路のうち、見逃し確率が最大である経路が求められる。逆に言うと、目標がグリッド上のどの経路を通過してスタート地点からゴール地点に至っても、求められた見逃し確率以下の見逃し確率で探知可能である、とセンサ配置を評価することができる。
【0008】
しかしながら、上記非特許文献1に記載の従来のセンサ配置評価装置においては、以下の条件(1)〜(5)の下で、グリッドの隣接点間の全線分に関する見逃し確率の算出に要する処理時間が膨大となり、処理時間の増大を無視することができなくなる。
【0009】
(1)監視対象領域が広い場合。
(2)グリッドの刻みが細かい場合。
(3)3次元空間を考慮する必要がある場合。
(4)センサのバイスタティック運用をするなどの理由により、目標の位置に加えて目標形状や向きも考慮する必要がある場合。
(5)種々のセンサ配置の評価を行う場合。
【先行技術文献】
【非特許文献】
【0010】
【非特許文献1】V. Phipatanasuphron, P. Raamanathan, “Vulnerability of Sensor Networks to Unauthorized Traversal and Monitoring,” IEEE Transactions on Computers, vol. 53, no. 3, pp. 364−369, March 2004
【発明の概要】
【発明が解決しようとする課題】
【0011】
従来のセンサ配置評価装置は、あらかじめ、グリッドの隣接点間に関するすべての見逃し確率を求めておく必要があるので、1つの見逃し確率の算出に要する処理時間が無視できず、さらに計算すべき見逃し確率の数が多い場合には、計算量が増大するという課題があった。
また、従来のセンサ配置評価装置は、目標がグリッドに沿って移動することを前提としており、目標の運動性能などの制約に基づく自然な動き方が考慮されていないという課題があった。
【0012】
この発明は、上記のような課題を解決するためになされたものであり、少ない計算量で、監視対象領域を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価することができ、さらに、評価の過程で目標の自然な動き方を考慮可能なセンサ配置評価装置を得ることを目的とする。
【課題を解決するための手段】
【0013】
この発明に係るセンサ配置評価装置は、目標状態探索状況保持手段と、目標状態選択手段と、目標状態生成手段と、見逃し確率算出手段と、累積見逃し確率算出手段と、終了判定手段とを備え、複数のセンサの配置を評価するセンサ配置評価装置であって、目標状態探索状況保持手段は、目標状態ツリーを保持し、目標状態ツリーは、目標の位置または向きに関する情報を含む目標状態と、目標の累積見逃し確率との対をノードとするツリー構造からなり、ツリー構造のルートノードは、初期目標状態に対応するノードであり、目標状態選択手段は、目標状態探索状況保持手段が保持する目標状態ツリーにおいて、累積見逃し確率があらかじめ定めた閾値以上であるノードから、1つの目標状態を選択し、目標状態生成手段は、目標状態選択手段が選択した目標状態に基づき、その一定時間後の目標状態を新たに生成し、見逃し確率算出手段は、初期目標状態、または目標状態生成手段が生成した目標状態について、目標状態と、複数のセンサに関するセンサ情報およびセンサ配置情報とを利用して、目標状態の見逃し確率を算出し、累積見逃し確率算出手段は、目標状態生成手段が生成した目標状態について、目標状態の生成元の目標状態の累積見逃し確率と、見逃し確率算出手段が算出した目標状態の見逃し確率との積を取ることにより、目標状態の累積見逃し確率を算出するとともに、目標状態ごとに、目標状態探索状況保持手段が保持する目標状態ツリーに対し、目標状態の生成元の目標状態に対応するノードの子ノードとして追加し、終了判定手段は、目標状態生成手段が生成した目標状態が、目標の目的地であるゴール領域に到達している場合には、複数のセンサの配置が性能不十分と評価して、評価処理を終了し、また、目標状態探索状況保持手段が保持する目標状態ツリーを構成するノード数が所定値以上である場合には、複数のセンサの配置が性能十分と評価して、評価処理を終了するものである。
【発明の効果】
【0014】
この発明によれば、少ない計算量で、監視対象領域を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価することができ、さらに、評価の過程で目標の自然な動き方を考慮可能にすることができる。
【図面の簡単な説明】
【0015】
【図1】この発明の実施の形態1に係るセンサ配置評価装置の構成を示すブロック図である。
【図2】この発明の実施の形態1において探知対象となる目標の経路の例を示す説明図である。
【図3】この発明の実施の形態1に係るセンサ配置評価装置の処理動作を示すフローチャートである。
【図4】この発明の実施の形態1において探知対象となるスタート地点での目標状態の例を示す説明図である。
【図5】図4の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図6】図5の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図7】図6の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図8】図7の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図9】図8の目標状態ツリーに基づいて選択された目標状態から新たな目標状態を生成した例を示す説明図である。
【図10】図4〜図9の選択処理の繰り返しにより最終的な目標状態を生成した例を示す説明図である。
【図11】この発明の実施の形態1のセンサ配置評価処理過程における或る時点での目標状態ツリーの構成例を示す説明図である。
【図12】この発明の実施の形態1における代表的な目標状態の変化例を示す説明図である。
【図13】この発明の実施の形態1により選択された目標状態から図12参照にしたがって得られる目標状態候補の例を示す説明図である。
【図14】この発明の実施の形態2に係るセンサ配置評価装置の構成を示すブロック図である。
【図15】この発明の実施の形態2におけるボロノイ図の例を示す説明図である。
【図16】この発明の実施の形態2のセンサ配置評価処理過程における或る時点での目標状態ツリーの例をボロノイ図とともに示す説明図である。
【図17】この発明の実施の形態2に係るセンサ配置評価装置の動作をボロノイ図とともに示す説明図である。
【図18】この発明の実施の形態3に係るセンサ配置評価装置の構成を示すブロック図である。
【発明を実施するための形態】
【0016】
実施の形態1.
以下、図1〜図13を参照しながら、この発明の実施の形態1に係るセンサ配置評価装置について説明する。
図1はこの発明の実施の形態1に係るセンサ配置評価装置の構成を示すブロック図である。
【0017】
図1において、センサ配置評価装置は、地形情報保持手段101と、目標情報保持手段102と、センサ情報保持手段103と、センサ配置保持手段104と、監視対象領域保持手段105と、初期目標状態指定手段106と、見逃し確率算出手段107と、累積見逃し確率算出手段108と、目標状態探索状況保持手段109と、目標状態選択手段110と、目標状態生成手段115と、終了判定手段121とを備えている。
【0018】
目標状態選択手段110は、目標状態確率分布設定手段111と、目標状態確率的選択手段114とを備えている。
目標状態確率分布設定手段111は、目標状態確率分布保持手段112と、ゴール距離対応目標状態確率分布加工手段113とを備えている。
【0019】
目標状態生成手段115は、目標状態候補生成手段116と、目標状態候補確率分布設定手段117と、目標状態候補確率的選択手段120とを備えている。
目標状態候補確率分布設定手段117は、目標状態候補確率分布保持手段118と、ゴール距離対応目標状態候補確率分布加工手段119とを備えている。
【0020】
ここで、図1に示したセンサ配置評価装置の動作について説明する前に、図2を参照しながら、技術背景について説明する。
図2においては、複数のセンサ(ユニット)を、それぞれ異なる場所に配置した状況を想定し、ユーザが定めた監視対象領域201を、航空機、船舶、車両などの目標Aが横切って、所定のゴール領域202に至る状況を想定している。
【0021】
センサ配置評価装置の目的は、上記想定条件の下で、目標Aが監視対象領域201を移動途中に(つまり、ゴール領域202に到達する前に)、配置されたセンサ群によって高確率で探知可能か否かを評価することである。もし、「高確率で探知可能でない場合がある」と判定された場合には、センサ配置が適切ではなかったものと判定し、センサ群の再配置や、新たなセンサの追加などのアクションに結び付けることができる。
【0022】
図2は探知対象となる目標Aの経路(破線矢印参照)の例を示す説明図であり、監視対象領域201、目標Aのゴール領域202およびセンサ群と関連付けて各経路を示している。
図2において、複数のセンサ(レーダ装置)からなるセンサ群の配置は、送受信ユニット(△印参照)と、送信ユニット(○印参照)と、受信ユニット(□印参照)とにより、示されている。
【0023】
以下の説明においては、簡単のため、目標Aの経路および監視対象領域201やゴール領域202などが2次元平面に限定されることを前提とするが、この発明の実施の形態1の考え方は、これらが3次元空間の場合にも全く同様に適用可能である。
【0024】
図2に示すように、目標Aは、あらかじめ設定したスタート地点から移動を開始し、監視対象領域201を横断して、ゴール領域202(ハッチング部分)に向かうことを想定する。
ただし、この際、目標Aは直線などの単純な経路上を移動するとは限らず、その取りうる経路(破線矢印)は、目標Aの運動性能が許す範囲内で無限に考えられるものとする。
【0025】
図2においては、目標Aが監視対象領域201を移動中に、目標Aを探知することを目的として、複数のセンサから構成されるセンサ群を配置することを考える。
ここで、各センサは、送信ユニット(○印)、受信ユニット(□印)、送受信ユニット(△印)のいずれかである。
【0026】
なお、送信ユニット(○印)とは、空間中に電波を送信するユニットであり、受信ユニット(□印)とは、目標Aが出力した電波や目標Aから反射した電波を受信して、目標Aを探知するユニットである。また、送受信ユニット(△印)は、送信ユニットおよび受信ユニットの両方の機能を有するユニットであり、通常のモノスタティックレーダに相当する。
【0027】
或る時刻における目標Aが、特定の送受信ユニット(△印)の捜索によって、どの程度探知可能であるかは、目標Aの構造や材質などの諸元、さらに、その時刻における目標Aの位置や向きによって評価可能である。
【0028】
具体的には、まず、レーダ方程式を利用して、送受信ユニット(△印)において、目標Aからの反射波を受信する際のS/N比を求める。さらに、S/N比と、あらかじめ設定した許容可能な誤警報確率とにより、探知確率を求めることができる。
ここで、目標Aを探知できない確率、すなわち「1−探知確率」を、「見逃し確率」という。
【0029】
上記手順において、目標Aの構造、材質、向きなどの諸元は、レーダ方程式を構成する要素であるレーダ反射断面積を評価するために利用される。
具体的には、あらかじめ、送受信ユニット(△印)を基準とした目標Aが取りうる向きを離散化し、離散化したそれぞれの目標Aの向きについて、実験またはコンピュータシミュレーションにより、レーダ反射断面積を求めてデータベース化しておく。
【0030】
以下、見逃し確率評価時には、送受信ユニット(△印)を基準とした目標Aの向きに基づき、上記データベースを検索して、必要に応じて補間処理を行うことにより、レーダ反射断面積を得る。
【0031】
上記説明では、単一の送受信ユニット(△印)による捜索について述べたが、送信ユニット(○印)と受信ユニット(□印)との対によって捜索を行うことも可能であり、この形態の運用を「バイスタティック運用」という。
【0032】
また、或る時刻における目標Aが、バイスタティック運用を行う特定の送信ユニット/受信ユニットの対の捜索によってどの程度探知可能であるかも、上記と同様に、目標の向きなどからレーダ反射断面積を評価し、さらにレーダ方程式などを利用することによって、評価可能である。
【0033】
上記説明では、或る時刻における、単一の送受信ユニット(△印)、または単一の送信ユニット/受信ユニット対による捜索について述べたが、センサ群においては、一般に、このような送受信ユニットや、送信ユニット/受信ユニット対が複数存在する。
【0034】
このような場合、センサ群の全体としての探知可能性は、以下のように評価することができる。
まず、各送受信ユニット(△印)、または送信ユニット/受信ユニット対における目標Aの見逃し確率を求め、続いて、各確率の積を計算すれば、センサ群の全体としての、目標Aの見逃し確率を評価することができる。
【0035】
なお、どの送信ユニット/受信ユニット対についてバイスタティック運用を行うかが定まらない場合は、すべての送信ユニット/受信ユニットの対でバイスタティック運用を行うと仮定するなどして、上記処理を行えばよい。
また、その時刻に捜索を行わないと想定される送受信ユニット(△印)、または送信ユニット/受信ユニット対については、見逃し確率を「1」として上記処理を行えばよい。
【0036】
上記説明では、或る時刻におけるセンサ群の全体としての、目標Aの見逃し確率の評価方法について述べたが、一方、一般にセンサの運用においては、一定の捜索周期間隔で、捜索が繰り返し行われる。
そこで、一定時間間隔で刻んだ連続する複数時刻を通じての、センサ群全体としての探知可能性を評価することが要求される。
【0037】
この評価要求を実現するためには、まず、各時刻におけるセンサ群全体としての見逃し確率を算出し、続いて、各時刻における見逃し確率の積を取れば、上記連続する複数時刻を通じての、センサ群全体としての、目標の見逃し確率を算出することができる。
以下、連続する複数時刻を通じての目標の見逃し確率を「累積見逃し確率」という。
【0038】
なお、上記累積見逃し確率の評価において、各時刻における見逃し確率を評価する際には、一般に、目標Aの位置や向きが動的に変化することに留意する必要がある。
この、見逃し確率算出に影響を与えるような、目標Aの位置や向きなど、動的に変化する諸元を、以下「目標状態」という。
【0039】
前述のように、この発明の実施の形態1に係るセンサ配置評価装置は、目標Aが監視対象領域201を移動途中に、配置されたセンサ群によって高確率で探知可能か否かを評価することが目的である。
【0040】
具体的には、目標Aの取りうる、スタート地点からゴール領域202に至る経路(破線矢印)について、その間のセンサ群による「累積見逃し確率」が、あらかじめ定めた閾値を下回った場合に、「高確率で探知可能」と判定する。
【0041】
次に、図2の説明図を参照しながら、図1に示したこの発明の実施の形態1に係るセンサ配置評価装置の動作について説明する。
図1において、まず、地形情報保持手段101は、電波遮蔽条件を判定する場合に必要な地形情報を保持する。
【0042】
一般に、センサと目標Aとの間が地形によって遮蔽されると、センサに電波が届かないので目標Aの探知が不可能となるが、地形情報保持手段101内の地形情報は、電波遮蔽条件を判定する場合に必要となる。
【0043】
目標情報保持手段102は、目標Aの見逃し確率を算出する際に必要な目標情報(目標Aの、動的に変化しない情報)を保持する。
具体的には、目標情報保持手段102は、たとえば、目標Aに各方向から電波が到来する場合の、各方向に対するレーダ反射断面積に関するデータを保持する。
【0044】
センサ情報保持手段103は、目標Aの見逃し確率を算出する際に必要な、各センサの情報を保持し、センサ配置保持手段104は、各センサの配置情報を保持し、監視対象領域保持手段105は、ユーザが設定する監視対象領域201およびゴール領域202を保持する。
【0045】
目標状態探索状況保持手段109は、目標状態と累積見逃し確率との対をノードとするツリー構造(以下、「目標状態ツリー」という)を保持する。
ここで、目標状態ツリーについて説明する。
目標状態ツリーは、スタート地点における目標状態に関するノードをルートノードとして、センサ配置評価処理の過程で、子ノードの生成の反復により、拡張されていく。
【0046】
ルートノード以外の各ノードの目標状態は、その親ノードの目標状態から、あらかじめ定めた時間間隔(以下、「時刻進行間隔」という)後の目標状態を表す。
ここで、目標Aの動き方には自由度があるので、一般に、各ノードの下には、複数の子ノードが生成される可能性がある。つまり、目標状態ツリーを、ルートノードから子ノードに順次たどっていくと、時刻進行間隔ごとの目標状態の時系列が得られることになる。
【0047】
また、各ノードの累積見逃し確率は、ルートノード(つまり、スタート地点)における目標状態から、当該ノードの目標状態に至るまでの累積見逃し確率を表す。
目標状態ツリーの拡張の過程において、以下の性質(A1)、(A2)の両方を有する目標状態が生成されれば、「目標が監視対象領域201を移動途中に、高確率で探知不可能な場合がある」と判定することができる。
【0048】
(A1)当該目標状態がゴール領域202に到達している。
(A2)当該目標状態の累積見逃し確率があらかじめ定めた閾値以上である。
なお、時刻進行間隔は、センサ群を構成する各センサの捜索周期に基づいて決めておけばよい。
【0049】
図1に戻り、初期目標状態指定手段106は、センサ配置評価処理開始時に、スタート地点における目標状態を設定する。
見逃し確率算出手段107は、初期目標状態指定手段106により指定された目標状態、または目標状態生成手段115(後述する)により生成された目標状態について、その見逃し確率を算出する。
このとき、見逃し確率は、目標状態の他、地形情報、目標の動的に変化しない情報、センサ情報、センサ配置情報を利用して算出される。
【0050】
累積見逃し確率算出手段108は、見逃し確率算出手段107が出力した見逃し確率に基づき、累積見逃し確率を算出する。
このとき、対象とする目標状態が、初期目標状態指定手段106が指定したものであれば、累積見逃し確率算出手段108により算出される累積見逃し確率は、見逃し確率算出手段107から出力された見逃し確率の値に等しい。
【0051】
一方、対象とする目標状態が、目標状態生成手段115が生成したものである場合には、累積見逃し確率算出手段108は、以下のように、累積見逃し確率を算出する。
なお、後述するが、目標状態生成手段115が生成した目標状態に関しては、生成元の目標状態が存在する。
【0052】
対象とする目標状態が、目標状態生成手段115が生成したものである場合、まず、累積見逃し確率算出手段108は、生成元の目標状態の累積見逃し確率を目標状態探索状況保持手段109から取得し、生成元の目標状態の累積見逃し確率と、見逃し確率算出手段107から出力された見逃し確率との積を取ることにより、対象とする目標状態の累積見逃し確率を算出する。
【0053】
累積見逃し確率算出手段108は、累積見逃し確率を算出すると、対応する目標状態とともに、目標状態探索状況保持手段109内の目標状態ツリーに、新たなノードとして追加する。
【0054】
すなわち、累積見逃し確率算出手段108は、対象とする目標状態が、初期目標状態指定手段106が指定したものであれば、目標状態探索状況保持手段109内の目標状態ツリーのルートノードとして設定する。
一方、対象とする目標状態が、目標状態生成手段115が生成したものであれば、生成元の目標状態に対応するノードの子ノードとして追加する。
【0055】
目標状態選択手段110は、目標状態探索状況保持手段109が保持する目標状態ツリーにおいて、累積見逃し確率が閾値以上であるノードから、1つの目標状態を選択する。この選択は、累積見逃し確率が十分低い目標状態については、センサ群によって高い確率で探知可能であることから、それ以上の探索を実行しても意味がないので、探索の対象としないという考え方に基づいている。
【0056】
目標状態生成手段115は、目標状態選択手段110が選択した目標状態に基づき、その時刻進行間隔後の目標状態を新たに生成する。
終了判定手段121は、目標状態生成手段115が生成した目標状態が、ゴール領域202に到達しているか否かを判定し、ゴール領域202に到達していると判定された場合には、「目標が監視対象領域201を高い累積見逃し確率で横断可能な場合がある」として、センサ配置の評価処理を終了する。
【0057】
終了判定手段121は、上記判定において、センサ配置評価処理を終了しなかった場合には、さらに、目標状態探索状況保持手段109が保持する目標状態ツリーを構成するノード数が、所定値以上であるか否かを判定する。
【0058】
上記判定結果が、「ノード数≧所定値」であった場合には、「目標が監視対象領域201を高い累積見逃し確率で横断することは困難」と見なして、センサ配置評価処理を終了する。
【0059】
この判定結果は、十分に目標状態の探索を実行したのにもかかわらず、所定の閾値以上の累積見逃し確率を保ってゴール領域202に到達する目標状態が見つからないのであれば、追加探索処理を実行しても、そのような目標状態は見つからない可能性が高いであろう、という考え方に基づいている。
【0060】
以下、目標状態探索状況保持手段109と関連した目標状態選択手段110の動作について、さらに詳細に説明する。
まず、目標状態選択手段110内の目標状態確率分布設定手段111は、目標状態探索状況保持手段109が保持する目標状態ツリーにおいて、累積見逃し確率が閾値以上であるノードを抽出し、それぞれの目標状態の選択のされやすさを表す確率分布を設定する。
また、目標状態選択手段110内の目標状態確率的選択手段114は、目標状態確率分布設定手段111が設定した確率分布に基づき、1つの目標状態を確率的に選択する。
【0061】
次に、目標状態確率分布設定手段111の動作について、さらに詳細に説明する。
まず、目標状態確率分布設定手段111内の目標状態確率分布保持手段112は、目標状態探索状況保持手段109が保持する目標状態ツリーにおいて、累積見逃し確率が閾値以上であるノードを抽出し、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。この初期化時においては、たとえば、各目標状態に対して一様な確率分布を設定すればよい。
【0062】
また、目標状態確率分布設定手段111内のゴール距離対応目標状態確率分布加工手段113は、各目標状態とゴール領域202との間の距離(以下「ゴール距離」と呼ぶ)が近いほど、選択される確率が高くなるように、目標状態確率分布保持手段112が保持する確率分布を加工する。
【0063】
以下、目標状態選択手段110と関連した目標状態生成手段115の動作について、さらに詳細に説明する。
まず、目標状態生成手段115内の目標状態候補生成手段116は、目標状態選択手段110が選択した目標状態に基づき、その時刻進行間隔後の目標状態として想定される候補(以下、「目標状態候補」という)を複数生成する。
【0064】
また、目標状態生成手段115内の目標状態候補確率分布設定手段117は、目標状態候補生成手段116が生成した複数の目標状態候補について、それぞれの選択のされやすさを表す確率分布を設定する。
さらに、目標状態生成手段115内の目標状態候補確率的選択手段120は、目標状態候補確率分布設定手段117が設定した確率分布に基づき、複数の目標状態候補から、1つの目標状態を確率的に選択する。
【0065】
次に、目標状態候補確率分布設定手段117の動作について、さらに詳細に説明する。
まず、目標状態候補確率分布設定手段117内の目標状態候補確率分布保持手段118は、目標状態候補生成手段116が生成した複数の目標状態候補について、それぞれの目標状態候補の選択のされやすさを表す確率分布を初期化して保持する。
【0066】
この初期化時においては、たとえば、各目標状態に対して一様な確率分布を設定すればよい。または、進行方向の変化が小さいほど、確率が高くなるよう確率分布を設定してもよい。これは、現実の目標の動きとして、進行方向を大きく変えるような移動が行われることは少ないであろう、との考え方に基づく方法である。
【0067】
続いて、目標状態候補確率分布設定手段117内のゴール距離対応目標状態候補確率分布加工手段119は、各目標状態候補とゴール領域202との間のゴール距離が近いほど、選択される確率が高くなるように、目標状態候補確率分布保持手段118が保持する確率分布を加工する。
【0068】
次に、図3のフローチャートを参照しながら、図1に示したこの発明の実施の形態1に係るセンサ配置評価装置の処理動作について、さらに具体的に説明する。
図3において、まず初めに、目標状態探索状況保持手段109は、自身が保持する目標状態ツリーを空に初期化する(ステップ301)。
【0069】
続いて、見逃し確率算出手段107は、初期目標状態指定手段106で指定された、スタート地点における目標状態に関する見逃し確率を算出して、目標状態とともに、累積見逃し確率算出手段108に出力する(ステップ302)。
【0070】
また、このとき、累積見逃し確率算出手段108は、見逃し確率算出手段107から取得した目標状態および見逃し確率を、目標状態探索状況保持手段109が保持する目標状態ツリーのルートノードとして設定する(ステップ302)。
ここで、ルートノードの累積見逃し確率は、スタート地点における目標状態の見逃し確率とする。
【0071】
次に、目標状態選択手段110は、目標状態探索状況保持手段109が保持する目標状態ツリーから、1つの目標状態を選択する(ステップ303)。
この際、累積見逃し確率が閾値未満である目標状態は、選択対象から外す。
【0072】
続いて、目標状態生成手段115は、目標状態選択手段110が選択した目標状態に基づき、その時刻進行間隔後の目標状態を新たに生成する(ステップ304)。
次に、終了判定手段121は、目標状態生成手段115が生成した目標状態が、ゴール領域202に到達しているか否かを判定する(ステップ305)。
【0073】
ステップ305において、ゴール領域202に到達している(すなわち、YES)と判定された場合は、「目標が監視対象領域201を高い累積見逃し確率で横断可能な場合がある」と見なして(ステップ306)、図3のセンサ配置評価処理を終了する。
【0074】
一方、ステップ305において、ゴール領域202に到達していない(すなわち、NO)と判定されれば、続いて、終了判定手段121は、目標状態探索状況保持手段109が保持する目標状態ツリーを構成するノード数が、所定値以上であるか否かを判定する(ステップ307)。
【0075】
ステップ307において、ノード数が所定値以上である(すなわち、YES)と判定された場合は、「目標が監視対象領域201を高い累積見逃し確率で横断することは困難」と見なして(ステップ308)、図3のセンサ配置評価処理を終了する。
【0076】
一方、ステップ307において、ノード数が所定値未満である(すなわち、NO)と判定されれば、見逃し確率算出手段107は、目標状態生成手段115が生成した目標状態の見逃し確率を算出する(ステップ309)。
【0077】
また、このとき、累積見逃し確率算出手段108は、生成元の目標状態の累積見逃し確率と、見逃し確率算出手段107が出力した見逃し確率とから、累積見逃し確率を算出する(ステップ309)。
【0078】
さらに、累積見逃し確率算出手段108は、目標状態および累積見逃し確率を、目標状態探索状況保持手段109が保持する目標状態ツリーに、生成元の目標状態に対応するノードの子ノードとして追加して(ステップ309)、ステップ303の処理に復帰する。
【0079】
次に、図1とともに、図4〜図10の説明図を参照しながら、センサ配置評価処理の具体的な手順について説明する。
図4はスタート地点における目標状態(2等辺3角形Aで示す)の例を示している。
図4において、目標状態(2等辺3角形A)は、具体的には目標の位置および向きにより構成されており、2等辺3角形Aの位置は、目標の位置を示し、2等辺3角形Aの頂角方向は、目標の向きを示している。
【0080】
また、目標状態Aの横に示す数値は、累積見逃し確率を表し、ここでは、スタート地点における目標状態Aの見逃し確率が「1.00」であったものとしている。
また、図4においては、スタート地点における目標状態に関するノードのみ(破線枠内参照)から構成される目標状態ツリーT1も示されている。
【0081】
一方、図5は新たな目標状態Bを示しており、図4の目標状態ツリーT1から目標状態Aを選択し、選択された目標状態Aから新たな目標状態Bを生成した例を示している。
【0082】
以下、目標状態選択手段110において、選択対象とする目標状態の条件を、「累積見逃し確率が所定の閾値0.5以上」とした場合について説明する。
この場合、累積見逃し確率が閾値「0.5」未満ならば、センサ群によって高い確率で探知可能と見なしていることになる。
【0083】
図4においては、選択可能な目標状態はAのみであることから、必然的に目標状態Aが選択されており、図5においては、目標状態Aの時刻進行間隔後の目標状態として、目標状態Bが生成されている。
【0084】
図5において、目標状態Bの累積見逃し確率は、目標状態Bの生成元の目標状態Aの累積見逃し確率と、目標状態Bの見逃し確率との積として計算され、ここでは、目標状態Bの累積見逃し確率が「0.98」と算出されたものとしている。
また、図5においては、目標状態Aと目標状態Bとに関するノードから構成される目標状態ツリーT2も示されている。図5の目標状態ツリーT2に示すように、目標状態Bのノードは、その生成元である目標状態Aの子ノードとなっている。
【0085】
次に、図6は新たな目標状態Cを示しており、図5の目標状態ツリーT2から目標状態Bを選択し、選択された目標状態Bから新たな目標状態Cを生成した例を示している。
図5においては、選択可能な目標状態はAおよびBであり、これらの中から目標状態Bが選択されており、図6においては、さらに、目標状態Bの時刻進行間隔後の目標状態として、目標状態Cが生成されている。
【0086】
図6において、目標状態Cの累積見逃し確率は、目標状態Cの生成元の目標状態Bの累積見逃し確率と、目標状態Cの見逃し確率との積として計算され、ここでは、目標状態Cの累積見逃し確率が「0.35」と算出されたものとしている。
【0087】
このとき、目標状態Cの累積見逃し確率「0.35」が所定の閾値「0.5」未満であることから、以降の探索において、目標状態C(黒塗りの2等辺3角形参照)は選択されないことになる。
図6を含め、以降の説明図において、次回の探索で選択されない目標状態は、黒塗りの2等辺3角形で示すものとする。
【0088】
また、図6においては、目標状態A、B、Cに関するノードから構成される目標状態ツリーT3も示されている。図6の目標状態ツリーT3に示すように、目標状態Cのノードは、その生成元である目標状態Bの子ノードとなっている。
【0089】
次に、図7は新たな目標状態Dを示しており、図6の目標状態ツリーT3から目標状態Bを選択し、選択された目標状態Bから新たな目標状態Dを生成した例を示している。
図6においては、選択可能な目標状態はAおよびBであり、これらの中から目標状態Bが選択されており、図7においては、さらに、目標状態Bの時刻進行間隔後の目標状態として、目標状態Dが生成されている。
【0090】
図7において、目標状態Dの累積見逃し確率は、目標状態Dの生成元の目標状態Bの累積見逃し確率と、目標状態Dの見逃し確率との積として計算され、ここでは、目標状態Dの累積見逃し確率が「0.86」と算出されたものとしている。
また、図7においては、目標状態A、B、C、Dに関するノードから構成される目標状態ツリーT4も示されている。図7の目標状態ツリーT4に示すように、目標状態Dのノードは、その生成元である目標状態Bの子ノードとなっている。
【0091】
次に、図8は新たな目標状態Eを示しており、図7の目標状態ツリーT4から目標状態Dを選択し、選択された目標状態Dから新たな目標状態Eを生成した例を示している。
図7においては、選択可能な目標状態はA、B、Dであり、これらの中から目標状態Dが選択されており、図8においては、さらに、目標状態Dの時刻進行間隔後の目標状態として、目標状態Eが生成されている。
【0092】
図8において、目標状態Eの累積見逃し確率は、目標状態Eの生成元の目標状態Dの累積見逃し確率と、目標状態Eの見逃し確率との積として計算され、ここでは、目標状態Eの累積見逃し確率が「0.84」と算出されたものとしている。
また、図8においては、目標状態A、B、C、D、Eに関するノードから構成される目標状態ツリーT5も示されている。図8の目標状態ツリーT5に示すように、目標状態Eのノードは、その生成元である目標状態Dの子ノードとなっている。
【0093】
次に、図9は新たな目標状態Fを示しており、図8の目標状態ツリーT5から目標状態Bを選択し、選択された目標状態Bから新たな目標状態Fを生成した例を示している。
図8においては、選択可能な目標状態はA、B、D、Eであり、これらの中からBが選択されたものとしており、図9においては、さらに、目標状態Bの時刻進行間隔後の目標状態として、目標状態Fが生成されている。
【0094】
図9において、目標状態Fの累積見逃し確率は、目標状態Fの生成元の目標状態Bの累積見逃し確率と、目標状態Fの見逃し確率との積として計算され、ここでは、目標状態Fの累積見逃し確率が「0.40」と算出されたものとしている。
このとき、目標状態Fの累積見逃し確率「0.40」が閾値「0.5」未満であることから、以降の探索において、目標状態F(黒塗りの2等辺3角形参照)は選択されないことになる。
【0095】
また、図9においては、目標状態A、B、C、D、E、Fに関するノードから構成される目標状態ツリーT6も示されている。図9の目標状態ツリーT6に示すように、目標状態Fのノードは、その生成元である目標状態Bの子ノードとなっている。
【0096】
以上の図4〜図9に示すように、センサ配置評価処理においては、目標状態ツリーの拡張処理(T1→T2→、・・・→T6)が繰り返し実行される。
この結果、図10に示すように、最終的に、目標状態ツリーTxが得られた場合を考える。
【0097】
図10においては、新たな目標状態Xを生成した例が示されている。
この場合、目標状態Xがゴール領域202に達しているので、終了判定手段121は、「目標が監視対象領域201を高い累積見逃し確率で横断可能な場合がある」と判定して、センサ配置評価処理を終了させることになる。
【0098】
一方、目標状態ツリーを構成するノード数が所定値を超えても、図10に示すように、ゴール領域202に到達する目標状態Xが出現しなければ、終了判定手段121は、「目標が監視対象領域201を高い累積見逃し確率で横断することは困難」と判定して、センサ配置評価処理を終了させることになる。
【0099】
次に、図1とともに、図11の説明図を参照しながら、目標状態選択手段110による目標状態の選択方法について、具体的に説明する。
図11においては、センサ配置評価処理過程における、或る時点での目標状態ツリーの構成例が示されている。
【0100】
目標状態選択手段110において、まず、目標状態確率分布設定手段111内の目標状態確率分布保持手段112は、目標状態ツリー上の、選択可能な(つまり、累積見逃し確率が閾値以上の)ノードにおいて、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。
図11の場合、選択可能な目標状態(白抜き2等辺3角形)はA、B、C、Dであり、初期化時点においては、これらが選択される確率はすべて同じ値に設定される。
【0101】
続いて、目標状態確率分布設定手段111内のゴール距離対応目標状態確率分布加工手段113は、各目標状態A〜Dとゴール領域202との間のゴール距離LA、LB、LC、LDを算出する。
図11においては、各目標状態A〜Dのゴール距離LA〜LDが示されている。
【0102】
また、ゴール距離対応目標状態確率分布加工手段113は、小さいゴール距離を有する目標状態の選択確率が高くなるように、目標状態確率分布保持手段112が保持する確率分布を加工する。
【0103】
なお、ゴール距離対応目標状態確率分布加工手段113による具体的な加工方法としては、たとえば、まず、目標状態確率分布保持手段112が保持する各目標状態A〜Dの確率を、それぞれゴール距離LA〜LDで除算し、その後、確率の和が「1」となるように、各確率を規格化すればよい。
最後に、目標状態確率的選択手段114は、目標状態確率分布保持手段112が保持する加工後の確率分布に基づき、1つの目標状態を確率的に選択する。
【0104】
次に、図1とともに、図12および図13の説明図を参照しながら、目標状態生成手段115による目標状態の生成方法について、具体的に説明する。
まず、目標状態生成手段115内の目標状態候補生成手段116は、目標状態が、時刻進行間隔後にどのように変化するかについて、その代表的な変化の仕方を複数個保持する。この変化の仕方は、目標状態の運動性能などの制約を反映したものとする。
【0105】
図12は代表的な目標状態の変化例を示しており、目標nが右に曲がる場合(a)と、目標nが真っ直ぐに移動する場合(b)と、目標nが左に曲がる場合(c)と、の3通りの変化の仕方を保持する例を示している。
【0106】
目標状態候補生成手段116は、目標状態選択手段110が選択した目標状態に基づき、図12に示した代表的な目標状態変化(a)〜(c)にしたがって、図13のように、時刻進行間隔後の目標状態候補a〜cを生成する。
図13においては、選択された目標状態から、代表的な目標状態変化(図12参照)にしたがって得られる目標状態候補a〜cの例を示している。
【0107】
続いて、目標状態候補確率分布設定手段117内の目標状態候補確率分布保持手段118は、目標状態候補生成手段116が生成した複数の目標状態候補について、それぞれの目標状態候補の選択のされやすさを表す確率分布を初期化して保持する。
【0108】
図13の場合、目標状態候補はa、b、cであり、初期化時点において、これらの目標状態候補a、b、cが選択される確率は、すべて同じ値に設定されている。
または、一般に目標nは、図12内の(b)のよう、真っ直ぐに移動する可能性の方が高いことを想定し、目標状態候補bの確率を、目標状態候補a、cの確率よりも高い値に初期設定してもよい。
【0109】
続いて、目標状態候補確率分布設定手段117内のゴール距離対応目標状態候補確率分布加工手段119は、各目標状態候補a〜cとゴール領域202との間のゴール距離La〜Lcを算出する。
図13においては、各目標状態候補a、b、cのゴール距離La〜Lcが示されている。
【0110】
また、ゴール距離対応目標状態候補確率分布加工手段119は、小さいゴール距離を有する目標状態候補の選択確率が高くなるように、目標状態候補確率分布保持手段118が保持する確率分布を加工する。
【0111】
具体的な加工方法としては、たとえば、まず、目標状態候補確率分布保持手段118が保持する各目標状態a〜cの確率を、それぞれゴール距離La〜Lcで除算し、その後、確率の和が「1」となるように、各確率を規格化すればよい。
【0112】
最後に、目標状態生成手段115内の目標状態候補確率的選択手段120は、目標状態候補確率分布保持手段118が保持する加工後の確率分布に基づき、1つの目標状態候補を確率的に選択し、新たな目標状態として出力する。
【0113】
以上のように、この発明の実施の形態1(図1)に係るセンサ配置評価装置は、複数のセンサの配置を評価するために、目標状態探索状況保持手段109と、目標状態選択手段110と、目標状態生成手段115と、見逃し確率算出手段107と、累積見逃し確率算出手段108と、終了判定手段121とを備えている。
【0114】
目標状態探索状況保持手段109は、目標の位置または向きに関する情報を含む目標状態と、目標の累積見逃し確率との対をノードとするツリー構造からなる目標状態ツリーを保持し、ツリー構造のルートノードは、初期目標状態に対応する。
目標状態選択手段110は、目標状態探索状況保持手段109が保持する目標状態ツリーにおいて、累積見逃し確率があらかじめ定めた閾値以上であるノードから、1つの目標状態を選択する。
【0115】
目標状態生成手段115は、目標状態選択手段110が選択した目標状態に基づき、その一定時間後の目標状態を新たに生成する。
見逃し確率算出手段107は、初期目標状態、または目標状態生成手段が生成した目標状態について、目標状態と、複数のセンサに関するセンサ情報およびセンサ配置情報とを利用して、目標状態の見逃し確率を算出する。
【0116】
累積見逃し確率算出手段108は、目標状態生成手段115が生成した目標状態について、目標状態の生成元の目標状態の累積見逃し確率と、見逃し確率算出手段107が算出した目標状態の見逃し確率との積を取ることにより、目標状態の累積見逃し確率を算出する。
また、累積見逃し確率算出手段108は、目標状態ごとに、目標状態探索状況保持手段109が保持する目標状態ツリーに対し、目標状態の生成元の目標状態に対応するノードの子ノードとして追加する。
【0117】
終了判定手段121は、目標状態生成手段115が生成した目標状態が、目標の目的地であるゴール領域に到達している場合には、複数のセンサの配置が性能不十分と評価して、評価処理を終了する。
また、終了判定手段121は、目標状態探索状況保持手段109が保持する目標状態ツリーを構成するノード数が所定値以上である場合には、複数のセンサの配置が性能十分と評価して、評価処理を終了する。
【0118】
さらに具体的には、目標状態選択手段110は、目標状態探索状況保持手段109が保持する目標状態ツリーからの目標状態選択において、目標状態とゴール領域202との間のゴール距離が小さいほど、高確率で選択する。
また、目標状態生成手段115は、目標状態選択手段110が選択した目標状態に基づく目標状態生成において、ゴール領域202との間のゴール距離が小さい目標状態を、高確率で新たに生成する。
【0119】
このように、確率的に目標状態ツリーを拡張して、かつ、累積見逃し確率が十分低い目標状態は「センサ群によって高い確率で探知可能」と評価して、それ以上の探索を行わないように構成したので、見逃し確率算出の対象となる目標状態数が、従来手法と比較して大幅に削減される。
【0120】
したがって、少ない計算量で、監視対象領域201を目標が移動する過程でセンサ群によって高確率で探知可能か否かを評価することができ、さらに、評価の過程で目標の自然な動き方を考慮可能にすることができ、処理時間を大幅に短縮するという効果を奏する。
【0121】
すなわち、目標状態の生成において、目標の運動性能などの制約を反映可能であることから、目標の自然な動き方のみを累積見逃し確率の算出対象とでき、無駄な処理を回避することができる。
【0122】
また、目標状態ツリーからの目標状態選択において、ゴール距離が小さいほど選択確率が高くなるように、各目標状態の確率分布を設定することにより、ゴール領域202に近い目標状態の方が、他の目標状態よりも選択されやすくなるので、センサ配置評価処理において、目標状態ツリーがゴール状態に向かって早期に拡張される。
したがって、「目標が監視対象領域201を高い累積見逃し確率で横断可能な場合がある」という状況下では、短い処理時間で判定が可能になるという効果を奏する。
【0123】
さらに、この発明の実施の形態1によれば、選択された目標状態からの新たな目標状態生成において、ゴール距離が小さいほど選択確率が高くなるように、各目標状態候補の確率分布を設定するので、新たな目標状態として、ゴール領域202に近い目標状態候補の方が、他の目標状態候補よりも選択されやすくなる。
【0124】
したがって、センサ配置評価処理において、目標状態ツリーが、ゴール状態に向かって早期に拡張されるので、「目標が監視対象領域201を高い累積見逃し確率で横断可能な場合がある」という状況下では、短い処理時間で判定が可能になるという効果を奏する。
【0125】
実施の形態2.
なお、上記実施の形態1(図1)では、目標状態選択手段110(目標状態生成手段115)において、ゴール距離対応目標状態確率分布加工手段113(ゴール距離対応目標状態候補確率分布加工手段119)を用いたが、図14のように、ボロノイ(Voronoi)辺対応目標状態確率分布加工手段113A(ボロノイ辺対応目標状態候補確率分布加工手段119A)を用いてもよい。
【0126】
以下、図14〜図17を参照しながら、この発明の実施の形態2について説明する。
図14はこの発明の実施の形態2に係るセンサ配置評価装置の構成を示すブロック図であり、前述(図1参照)と同様のものについては、前述と同一符号を付して詳述を省略する。
【0127】
また、図14において、目標状態選択手段110A、目標状態生成手段115A、目標状態確率分布設定手段111Aおよび目標状態候補確率分布設定手段117Aは、ぞれぞれ、前述(図1)の目標状態選択手段110、目標状態生成手段115、目標状態確率分布設定手段111および目標状態候補確率分布設定手段117に対応する。
【0128】
この場合、目標状態選択手段110Aおよび目標状態生成手段115A内において、目標状態確率分布設定手段111Aおよび目標状態候補確率分布設定手段117Aの構成のみが前述(図1)と異なり、他の構成は前述と同様である。
【0129】
目標状態確率分布設定手段111Aは、目標状態確率分布保持手段112と、ボロノイ辺対応目標状態確率分布加工手段113Aとにより構成されている。
目標状態候補確率分布設定手段117Aは、目標状態候補確率分布保持手段118と、ボロノイ辺対応目標状態候補確率分布加工手段119Aとにより構成されている。
【0130】
次に、図15〜図17の説明図を参照しながら、図14に示したこの発明の実施の形態2に係るセンサ配置評価装置の動作について説明する。
まず、目標状態選択手段110A内の目標状態確率分布設定手段111Aについて説明する。ここで、目標状態確率分布設定手段111A内の目標状態確率分布保持手段112の動作は、実施の形態1と同じなので省略する。
【0131】
目標状態確率分布設定手段111A内のボロノイ辺対応目標状態確率分布加工手段113Aは、あらかじめ、各センサの位置を母点とするボロノイ図を生成して保持しておく。
図15は複数のセンサの各位置を母点としたボロノイ図の例を示している。ボロノイ図とは、空間を、「どの母点に最も近いか」によって、母点数分の小領域に分割してできる図である。
【0132】
ボロノイ辺対応目標状態確率分布加工手段113Aは、センサ配置評価処理過程において、目標状態ツリーから1つの目標状態を選択する際に、各目標状態と、当該目標状態に最も近いボロノイ辺との間の距離(以下「ボロノイ辺距離」と呼ぶ)が近いほど、選択される確率が高くなるように、目標状態確率分布保持手段112が保持する確率分布を加工する。
【0133】
次に、目標状態生成手段115A内の目標状態候補確率分布設定手段117Aについて説明する。ここで、目標状態候補確率分布設定手段117A内の目標状態候補確率分布保持手段118の動作は、前述と同じなので省略する。
【0134】
目標状態候補確率分布設定手段117A内のボロノイ辺対応目標状態候補確率分布加工手段119Aは、あらかじめ、各センサの位置を母点とするボロノイ図を保持しておく。
また、ボロノイ辺対応目標状態候補確率分布加工手段119Aは、センサ配置評価処理過程において、複数の目標状態候補から1つの目標状態候補を選択する際に、各目標状態候補と、当該目標状態候補に最も近いボロノイ辺との間の距離が近いほど、選択される確率が高くなるように、目標状態候補確率分布保持手段118が保持する確率分布を加工する。
【0135】
次に、図14とともに、図16の説明図を参照しながら、目標状態選択手段110Aによる目標状態の選択方法について、具体的に説明する。
図16においては、センサ配置評価処理過程における、或る時点での目標状態ツリーの例を、各センサの位置を母点とするボロノイ図とともに示している。
【0136】
目標状態選択手段110Aにおいて、まず、目標状態確率分布設定手段111A内の目標状態確率分布保持手段112は、目標状態ツリー上の、選択可能な(つまり、累積見逃し確率が閾値以上の)ノードにおいて、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。
図16の場合、選択可能な目標状態(白抜き2等辺3角形)はA、B、C、D、Eであり、初期化時点において、これらが選択される確率は、すべて同じ値に設定されている。
【0137】
続いて、目標状態確率分布設定手段111A内のボロノイ辺対応目標状態確率分布加工手段113Aは、各目標状態A、B、C、D、Eと、当該目標状態に最も近いボロノイ辺との間のボロノイ辺距離VA、VB、VC、VD、VEを算出する。
図16においては、各目標状態A〜Eのボロノイ辺距離VA〜VEが示されている。
【0138】
また、ボロノイ辺対応目標状態確率分布加工手段113Aは、小さいボロノイ辺距離を有する目標状態の選択確率が高くなるように、目標状態確率分布保持手段112が保持する確率分布を加工する。
【0139】
具体的な加工方法としては、たとえば、まず、目標状態確率分布保持手段112が保持する各目標状態A〜Eの確率を、それぞれボロノイ辺距離VA〜VEで除算し、その後、確率の和が「1」となるように、各確率を規格化すればよい。
最後に、目標状態確率的選択手段114は、目標状態確率分布保持手段112が保持する加工後の確率分布に基づき、1つの目標状態を確率的に選択する。
【0140】
次に、図14とともに、図17の説明図を参照しながら、目標状態生成手段115Aによる目標状態の生成方法について、具体的に説明する。
まず、目標状態生成手段115A内の目標状態候補生成手段116は、目標状態選択手段110Aが選択した目標状態n(図17参照)に基づき、時刻進行間隔後の目標状態候補a〜cを生成する。
図17においては、選択された目標状態nから得られる目標状態候補a〜cの例が示されている。
【0141】
続いて、目標状態候補確率分布設定手段117A内の目標状態候補確率分布保持手段118は、目標状態候補生成手段116が生成した複数の目標状態候補a〜cについて、それぞれの目標状態候補の選択のされやすさを表す確率分布を初期化して保持する。
図17の場合、目標状態候補はa、b、cであり、初期化時点において、これらが選択される確率は、たとえば、すべて同じ値に設定されるものとする。
【0142】
その後、目標状態候補確率分布設定手段117A内のボロノイ辺対応目標状態候補確率分布加工手段119Aは、各目標状態候補a〜cと、当該目標状態候補に最も近いボロノイ辺との間のボロノイ辺距離Va〜Vcを算出する。
図17においては、各目標状態候補a、b、cのボロノイ辺距離Va〜Vcが示されている。
【0143】
また、ボロノイ辺対応目標状態候補確率分布加工手段119Aは、小さいボロノイ辺距離を有する目標状態候補の選択確率が高くなるように、目標状態候補確率分布保持手段118が保持する確率分布を加工する。
【0144】
具体的には、たとえば、まず、目標状態候補確率分布保持手段118が保持する各目標状態候補a〜cの確率を、それぞれボロノイ辺距離Va〜Vcで除算し、その後、確率の和が「1」となるように、各確率を規格化すればよい。
最後に、目標状態候補確率的選択手段120は、目標状態候補確率分布保持手段118が保持する加工後の確率分布に基づき、1つの目標状態候補を確率的に選択し、新たな目標状態として出力する。
【0145】
以上のように、この発明の実施の形態2(図14)による目標状態選択手段110Aは、目標状態探索状況保持手段109が保持する目標状態ツリーからの目標状態選択において、複数のセンサの各位置を母点とするボロノイ図(図15〜図17)に関し、目標状態と、目標状態に最も近いボロノイ辺との間のボロノイ辺距離が小さいほど、高確率で選択する。
【0146】
また、この発明の実施の形態2(図14)による目標状態生成手段115Aは、目標状態選択手段110Aが選択した目標状態に基づく目標状態生成において、複数のセンサの各位置を母点とするボロノイ図(図15〜図17)に関し、ボロノイ辺との間のボロノイ辺距離が小さい目標状態を、高確率で新たに生成する。
【0147】
このように、目標状態ツリーからの目標状態選択において、ボロノイ辺距離が小さいほど選択確率が高くなるように、各目標状態の確率分布を設定することにより、ボロノイ辺に近い目標状態が、より選択されやすくなる。
したがって、センサ配置評価処理において、目標状態ツリーがボロノイ辺に沿うような形で拡張されやすくなる。
【0148】
一方、一般に、目標は、センサからの距離が大きいほど探知されにくい傾向があり、目標が監視対象領域201を高い累積見逃し確率で横断可能な場合に、その経路は、複数のセンサの各位置を母点とするボロノイ辺の近傍を通過するものになることが多いと考えられるので、上記処理により、「目標が監視対象領域を高い累積見逃し確率で横断可能な場合がある」という状況下において、短い処理時間で判定が可能になるという効果を奏する。
【0149】
また、この発明の実施の形態2によれば、選択された目標状態からの新たな目標状態生成において、ボロノイ辺距離が小さいほど選択確率が高くなるように、各目標状態候補の確率分布を設定するので、新たな目標状態として、ボロノイ辺に近い目標状態候補の方が、他の目標状態候補よりも選択されやすくなる。
【0150】
これにより、センサ配置評価処理において、目標状態ツリーがボロノイ辺に沿うような形で拡張されやすくなるので、上記と同様に、「目標が監視対象領域を高い累積見逃し確率で横断可能な場合がある」という状況下において、短い処理時間で判定が可能になるという効果を奏する。
【0151】
さらに、ここでは、簡単のため、監視対象領域201およびゴール領域202が2次元の場合について説明したが、3次元の場合にも適用可能なことは言うまでもない。ただし、この場合、上記の「ボロノイ辺」を「ボロノイ面」に読み替える必要がある。
【0152】
実施の形態3.
なお、上記実施の形態1(図1)では、目標状態選択手段110において、ゴール距離対応目標状態確率分布加工手段113を用いたが、図18のように、ゴール距離対応目標状態確率分布加工手段113に加えて(または、ゴール距離対応目標状態確率分布加工手段113に代えて)、累積見逃し確率対応目標状態確率分布加工手段113Bを用いてもよい。
【0153】
図18はこの発明の実施の形態3に係るセンサ配置評価装置の構成を示すブロック図であり、前述(図1参照)と同様のものについては、前述と同一符号を付して詳述を省略する。
図18において、前述(図1)との相違点は、目標状態選択手段110B内の目標状態確率分布設定手段111Bの構成のみであり、他の構成は前述と同様である。
【0154】
この場合、目標状態確率分布設定手段111Bは、前述と同様の目標状態確率分布保持手段112およびゴール距離対応目標状態確率分布加工手段113に加えて、累積見逃し確率対応目標状態確率分布加工手段113Bを備えている。
【0155】
以下、図18に示したこの発明の実施の形態3による目標状態選択手段110Bの動作について、順を追って説明する。
まず、目標状態確率分布保持手段112は、目標状態ツリー上の、選択可能な(つまり、累積見逃し確率が閾値以上の)ノードにおいて、それぞれの目標状態の選択のされやすさを表す確率分布を初期化して保持する。具体的には、たとえば、選択可能な目標状態に関して、その選択確率をすべて同じ値に設定する。
【0156】
続いて、ゴール距離対応目標状態確率分布加工手段113は、各目標状態とゴール領域202との間のゴール距離を算出し、小さいゴール距離を有する目標状態の選択確率が高くなるように、目標状態確率分布保持手段112が保持する確率分布を加工する。
【0157】
具体的には、前述のように、たとえば、まず、目標状態確率分布保持手段112が保持する各目標状態の確率を、それぞれゴール距離で除算し、その後、確率の和が「1」となるように、各確率を規格化すればよい。
【0158】
次に、累積見逃し確率対応目標状態確率分布加工手段113Bは、累積見逃し確率が高い目標状態ほど、選択される確率が高くなるように、目標状態確率分布保持手段112が保持する、ゴール距離対応目標状態確率分布加工手段113による加工済みの確率分布をさらに加工する。
【0159】
具体的には、たとえば、まず、目標状態確率分布保持手段112が保持する各目標状態の確率に対し、当該目標状態の累積見逃し確率を乗算し、その後、確率の和が「1」となるように、各確率を規格化すればよい。
最後に、目標状態確率的選択手段114は、目標状態確率分布保持手段112が保持する加工後の確率分布に基づき、1つの目標状態を確率的に選択する。
【0160】
以上のように、この発明の実施の形態3(図18)による目標状態選択手段110Bは、累積見逃し確率対応目標状態確率分布加工手段113Bを備えており、目標状態探索状況保持手段109が保持する目標状態ツリーからの目標状態選択において、累積見逃し確率が高いほど高確率で選択する。
【0161】
このように、目標状態ツリーからの目標状態選択において、累積見逃し確率が高い目標状態ほど選択される確率が高くなるように、各目標状態の確率分布を設定することにより、累積見逃し確率が低い(その先の探索の望みが少ない)目標状態は、選択されにくくなるので、有望な領域を優先的に探索できるようになるという効果を奏する。
【0162】
なお、図18においては、実施の形態1(図1)の構成に対して、累積見逃し確率対応目標状態確率分布加工手段113Bを追加した場合を示したが、目標状態確率分布設定手段111B内に累積見逃し確率対応目標状態確率分布加工手段113Bのみを設けてもよい。
また、前述の実施の形態2(図14)の構成に対して、累積見逃し確率対応目標状態確率分布加工手段113Bを追加してもよく、上述と同等の作用効果を奏することは言うまでもない。
【符号の説明】
【0163】
101 地形情報保持手段、102 目標情報保持手段、103 センサ情報保持手段、104 センサ配置保持手段、105 監視対象領域保持手段、106 初期目標状態指定手段、107 見逃し確率算出手段、108 累積見逃し確率算出手段、109 目標状態探索状況保持手段、110、110A、110B 目標状態選択手段、111、111A、111B 目標状態確率分布設定手段、112 目標状態確率分布保持手段、113 ゴール距離対応目標状態確率分布加工手段、113A ボロノイ辺対応目標状態確率分布加工手段、113B 累積見逃し確率対応目標状態確率分布加工手段、114 目標状態確率的選択手段、115、115A、115B 目標状態生成手段、116 目標状態候補生成手段、117、117A、117B 目標状態候補確率分布設定手段、118 目標状態候補確率分布保持手段、119 ゴール距離対応目標状態候補確率分布加工手段、119A ボロノイ辺対応目標状態候補確率分布加工手段、120 目標状態候補確率的選択手段、121 終了判定手段、201 監視対象領域、202 ゴール領域、LA〜LD、La〜Lc ゴール距離、T1〜T6、Tx 目標状態ツリー、Va〜Vc ボロノイ辺距離。

【特許請求の範囲】
【請求項1】
目標状態探索状況保持手段と、目標状態選択手段と、目標状態生成手段と、見逃し確率算出手段と、累積見逃し確率算出手段と、終了判定手段とを備え、複数のセンサの配置を評価するセンサ配置評価装置であって、
前記目標状態探索状況保持手段は、目標状態ツリーを保持し、
前記目標状態ツリーは、目標の位置または向きに関する情報を含む目標状態と、前記目標の累積見逃し確率との対をノードとするツリー構造からなり、
前記ツリー構造のルートノードは、初期目標状態に対応するノードであり、
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーにおいて、前記累積見逃し確率があらかじめ定めた閾値以上であるノードから、1つの目標状態を選択し、
前記目標状態生成手段は、前記目標状態選択手段が選択した前記目標状態に基づき、その一定時間後の目標状態を新たに生成し、
前記見逃し確率算出手段は、前記初期目標状態、または前記目標状態生成手段が生成した前記目標状態について、前記目標状態と、前記複数のセンサに関するセンサ情報およびセンサ配置情報とを利用して、前記目標状態の見逃し確率を算出し、
前記累積見逃し確率算出手段は、前記目標状態生成手段が生成した前記目標状態について、前記目標状態の生成元の目標状態の累積見逃し確率と、前記見逃し確率算出手段が算出した前記目標状態の前記見逃し確率との積を取ることにより、前記目標状態の累積見逃し確率を算出するとともに、前記目標状態ごとに、前記目標状態探索状況保持手段が保持する前記目標状態ツリーに対し、前記目標状態の生成元の目標状態に対応するノードの子ノードとして追加し、
前記終了判定手段は、前記目標状態生成手段が生成した前記目標状態が、前記目標の目的地であるゴール領域に到達している場合には、前記複数のセンサの配置が性能不十分と評価して、評価処理を終了し、また、前記目標状態探索状況保持手段が保持する前記目標状態ツリーを構成するノード数が所定値以上である場合には、前記複数のセンサの配置が性能十分と評価して、評価処理を終了することを特徴とするセンサ配置評価装置。
【請求項2】
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーからの目標状態選択において、前記目標状態と前記ゴール領域との間のゴール距離が小さいほど、高確率で選択することを特徴とする請求項1に記載のセンサ配置評価装置。
【請求項3】
前記目標状態生成手段は、前記目標状態選択手段が選択した前記目標状態に基づく目標状態生成において、前記ゴール領域との間のゴール距離が小さい目標状態を、高確率で新たに生成することを特徴とする請求項1または請求項2に記載のセンサ配置評価装置。
【請求項4】
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーからの目標状態選択において、前記複数のセンサの各位置を母点とするボロノイ図に関し、前記目標状態と、前記目標状態に最も近いボロノイ辺との間のボロノイ辺距離が小さいほど、高確率で選択することを特徴とする請求項1に記載のセンサ配置評価装置。
【請求項5】
前記目標状態生成手段は、前記目標状態選択手段が選択した前記目標状態に基づく目標状態生成において、前記複数のセンサの各位置を母点とするボロノイ図に関し、ボロノイ辺との間のボロノイ辺距離が小さい目標状態を、高確率で新たに生成することを特徴とする請求項1または請求項4に記載のセンサ配置評価装置。
【請求項6】
前記目標状態選択手段は、前記目標状態探索状況保持手段が保持する前記目標状態ツリーからの目標状態選択において、前記累積見逃し確率が高いほど高確率で選択することを特徴とする請求項1から請求項5までのいずれか1項に記載のセンサ配置評価装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate


【公開番号】特開2010−281784(P2010−281784A)
【公開日】平成22年12月16日(2010.12.16)
【国際特許分類】
【出願番号】特願2009−137169(P2009−137169)
【出願日】平成21年6月8日(2009.6.8)
【出願人】(000006013)三菱電機株式会社 (33,312)
【Fターム(参考)】