(57)【特許請求の範囲】
【請求項１】
警備区域内における警備員の配置の決定を支援する警備計画支援方法であって、
前記警備区域内の各警備対象及び各侵入可能位置と移動可能経路とにそれぞれ対応付けた、複数のノードとエッジとにより構成される移動経路グラフを作成し、
前記警備対象に侵入者が到達することにより生じ得る前記警備対象毎の損失を、前記移動経路グラフにおける前記警備対象のそれぞれに対応した各ノードに、危険度の初期値として設定し、
前記移動経路グラフにおいて、設定された危険度が最大である前記警備対象のノードを含むノードの集合を、前記侵入可能位置のノードを全て含むノードの集合から分離する閉曲線であって、該閉曲線が横切る前記移動経路グラフのエッジの数が最少となる該閉曲線を生成し、
前記閉曲線により分離される前記移動経路グラフの各ノードについての一対の集合である、最大の危険度が設定された警備対象のノードを含むノードの集合と前記侵入可能位置のノードを全て含むノードの集合とを一対のノードに対応付け、前記一対のノードのうちの、最大の危険度が設定された警備対象のノードを含むノードの集合に対応付けた方のノードに前記最大の危険度を設定し、前記閉曲線が横切る前記移動経路グラフのエッジの数を、前記一対のノードを繋ぐエッジに、重みとして設定した、警備領域グラフを生成し、
前記警備領域グラフに設定されたノードの危険度及びエッジの重みと、前記警備員の人数とを用いて前記警備領域グラフの各エッジの警備確率についての最適化問題を解き、
前記危険度の更新後の前記移動経路グラフにおいて前記閉曲線を更に生成し、
前記移動経路グラフにおいて、前記更に生成した前記閉曲線が横切るエッジに、過去に生成した前記閉曲線が横切るエッジ以外のエッジがあるか否かを判定し、
前記過去に生成したエッジ以外のエッジがなかったと判定した場合には、表示装置を制御して、前記過去に生成した前記閉曲線を前記移動経路グラフ上で表示させると共に、表示させた前記閉曲線について生成した前記警備領域グラフについて得られた前記警備確率の最適解を、表示させた前記閉曲線に対応づけて表示させ、
前記過去に生成したエッジ以外のエッジがあったと判定した場合には、前記更に生成した前記閉曲線に基づいた前記警備領域グラフの生成、前記危険度の更新、前記閉曲線の生成と、生成された前記閉曲線についての前記判定とを、前記過去に生成したエッジ以外のエッジがなかったと判定されるまで繰り返す、
処理をコンピュータが実行することを特徴とする警備計画支援方法。
【請求項２】
前記閉曲線の生成において、横切る前記移動経路グラフのエッジの数が最少となる前記閉曲線が複数存在する場合、予め定めた条件に従って、１つの閉曲線を、生成結果として選出する、
ことを特徴とする請求項１に記載の警備計画支援方法。
【請求項３】
前記閉曲線の生成において、横切る前記移動経路グラフのエッジの数が最少となる前記閉曲線が複数存在する場合、前記閉曲線により分離される前記移動経路グラフの各ノードについての前記一対の集合のうちの、最大の危険度が設定された警備対象のノードを含むノードの集合に含まれるノードの数が最多となる閉曲線を、生成結果として選出する、
ことを特徴とする請求項１に記載の警備計画支援方法。
【請求項４】
警備区域内における警備員の配置の決定を支援する警備計画支援装置であって、
前記警備区域内の各警備対象及び各侵入可能位置と移動可能経路とにそれぞれ対応付けた、複数のノードとエッジとにより構成される移動経路グラフを作成する作成部と、
前記警備対象に侵入者が到達することにより生じ得る前記警備対象毎の損失を、前記移動経路グラフにおける前記警備対象のそれぞれに対応した各ノードに、危険度の初期値として設定する設定部と、
前記移動経路グラフにおいて、設定された危険度が最大である前記警備対象のノードを含むノードの集合を、前記侵入可能位置のノードを全て含むノードの集合から分離する閉曲線であって、該閉曲線が横切る前記移動経路グラフのエッジの数が最少となる該閉曲線を生成する閉曲線生成部と、
前記閉曲線により分離される前記移動経路グラフの各ノードについての一対の集合である、最大の危険度が設定された警備対象のノードを含むノードの集合と前記侵入可能位置のノードを全て含むノードの集合とを一対のノードに対応付け、前記一対のノードのうちの、最大の危険度が設定された警備対象のノードを含むノードの集合に対応付けた方のノードに前記最大の危険度を設定し、前記閉曲線が横切る前記移動経路グラフのエッジの数を、前記一対のノードを繋ぐエッジに、重みとして設定した、警備領域グラフを生成する警備領域グラフ生成部と、
前記警備領域グラフに設定されたノードの危険度及びエッジの重みと、前記警備員の人数とを用いて前記警備領域グラフの各エッジの警備確率についての最適化問題を解き、前記警備確率の最適解に基づいて、前記移動経路グラフにおいて前記最大の危険度が設定された警備対象のノードを含むノードの集合に含まれる各警備対象のノードに設定されている危険度を更新する更新部と、
を備え、
前記閉曲線生成部は、前記危険度の更新後の前記移動経路グラフにおいて前記閉曲線を更に生成し、
前記警備計画支援装置は、更に、
前記移動経路グラフにおいて、前記更に生成した前記閉曲線が横切るエッジに、過去に生成した前記閉曲線が横切るエッジ以外のエッジがあるか否かを判定する判定部と、
前記過去に生成したエッジ以外のエッジがなかったと判定した場合には、表示装置を制御して、前記過去に生成した前記閉曲線を前記移動経路グラフ上で表示させると共に、表示させた前記閉曲線について生成した前記警備領域グラフについて得られた前記警備確率の最適解を、表示させた前記閉曲線に対応づけて表示させ、
前記過去に生成したエッジ以外のエッジがあったと判定した場合には、前記更に生成した前記閉曲線に基づいた前記警備領域グラフの生成、前記危険度の更新、前記閉曲線の生成と、生成された前記閉曲線についての前記判定とを、前記過去に生成したエッジ以外のエッジがなかったと判定されるまで繰り返す
制御を行う制御部と、
を備える、
ことを特徴とする警備計画支援装置。
【請求項５】
警備区域内における警備員の配置の決定の支援をコンピュータに行わせるためのプログラムであって、
前記警備区域内の各警備対象及び各侵入可能位置と移動可能経路とにそれぞれ対応付けた、複数のノードとエッジとにより構成される移動経路グラフを作成し、
前記警備対象に侵入者が到達することにより生じ得る前記警備対象毎の損失を、前記移動経路グラフにおける前記警備対象のそれぞれに対応した各ノードに、危険度の初期値として設定し、
前記移動経路グラフにおいて、設定された危険度が最大である前記警備対象のノードを含むノードの集合を、前記侵入可能位置のノードを全て含むノードの集合から分離する閉曲線であって、該閉曲線が横切る前記移動経路グラフのエッジの数が最少となる該閉曲線を生成し、
前記閉曲線により分離される前記移動経路グラフの各ノードについての一対の集合である、最大の危険度が設定された警備対象のノードを含むノードの集合と前記侵入可能位置のノードを全て含むノードの集合とを一対のノードに対応付け、前記一対のノードのうちの、最大の危険度が設定された警備対象のノードを含むノードの集合に対応付けた方のノードに前記最大の危険度を設定し、前記閉曲線が横切る前記移動経路グラフのエッジの数を、前記一対のノードを繋ぐエッジに、重みとして設定した、警備領域グラフを生成し、
前記警備領域グラフに設定されたノードの危険度及びエッジの重みと、前記警備員の人数とを用いて前記警備領域グラフの各エッジの警備確率についての最適化問題を解き、
前記危険度の更新後の前記移動経路グラフにおいて前記閉曲線を更に生成し、
前記移動経路グラフにおいて、前記更に生成した前記閉曲線が横切るエッジに、過去に生成した前記閉曲線が横切るエッジ以外のエッジがあるか否かを判定し、
前記過去に生成したエッジ以外のエッジがなかったと判定した場合には、表示装置を制御して、前記過去に生成した前記閉曲線を前記移動経路グラフ上で表示させると共に、表示させた前記閉曲線について生成した前記警備領域グラフについて得られた前記警備確率の最適解を、表示させた前記閉曲線に対応づけて表示させ、
前記過去に生成したエッジ以外のエッジがあったと判定した場合には、前記更に生成した前記閉曲線に基づいた前記警備領域グラフの生成、前記危険度の更新、前記閉曲線の生成と、生成された前記閉曲線についての前記判定とを、前記過去に生成したエッジ以外のエッジがなかったと判定されるまで繰り返す、
処理をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、警備計画支援方法、警備計画支援装置、及びプログラムに関する。
【背景技術】
【０００２】
街中や施設等の警備区域内の警備においては、侵入者が警備対象に到達することによって受ける損失の期待値が最小になるよう警備員を配置することが重要である。一方、警備員による警備においては、人的コストの面から、限られた人数の警備員を効率的に配置して警備することが望まれる。そのため、警備員の配置は、情報提示装置により提示される配置パターン等の情報を参照して決定される。
【０００３】
情報提示装置は、警備区域内の移動経路を表す経路グラフと警備条件とに基づいて複数通りの配置パターンと各配置パターンの選択確率を算出し、算出結果を経路グラフとともに表示装置等に出力する。警備条件は、移動経路における侵入者の侵入位置、警備対象の位置又は範囲、侵入者が警備対象に到達したときの損失、及び警備員の数を含む。また、配置パターン及び選択確率を表示装置等に出力する際には、経路グラフにおける警備員の配置箇所（辺）の色を変える等の方法で強調する。
【０００４】
上記の配置パターン及び選択確率は、線形計画法と混合整数計画法とを繰り返して求める（例えば非特許文献１，２を参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】M. Jain, D. Korzhyk, O. Vanek, V. Conitzer, M. Pechoucek, and M. Tambe. A Double Oracle Algorithm for Zero-Sum Security Games on Graphs.In AAMAS, 2011.
【非特許文献２】M. Jain, V. Conitzer, and M. Tambe. Security Scheduling for Real-world Networks. In AAMAS, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の情報提示装置を用いた技術では、警備効率の高い配置パターンの組み合わせ及び選択確率を算出するのに時間がかかり、かなりの処理負荷がかかる。
【０００７】
１つの側面において、本発明の目的は、警備員の配置についての確率の算出負荷の軽減を図ることを目的とする。
【課題を解決するための手段】
【０００８】
本発明の１つの態様である警備計画支援方法は、警備区域内における警備員の配置の決定を支援する警備計画支援方法であって、前記警備区域内の各警備対象及び各侵入可能位置と移動可能経路とにそれぞれ対応付けた、複数のノードとエッジとにより構成される移動経路グラフを作成し、前記警備対象に侵入者が到達することにより生じ得る前記警備対象毎の損失を、前記移動経路グラフにおける前記警備対象のそれぞれに対応した各ノードに、危険度の初期値として設定し、前記移動経路グラフにおいて、設定された危険度が最大である前記警備対象のノードを含むノードの集合を、前記侵入可能位置のノードを全て含むノードの集合から分離する閉曲線であって、該閉曲線が横切る前記移動経路グラフのエッジの数が最少となる該閉曲線を生成し、前記閉曲線により分離される前記移動経路グラフの各ノードについての一対の集合である、最大の危険度が設定された警備対象のノードを含むノードの集合と前記侵入可能位置のノードを全て含むノードの集合とを一対のノードに対応付け、前記一対のノードのうちの、最大の危険度が設定された警備対象のノードを含むノードの集合に対応付けた方のノードに前記最大の危険度を設定し、前記閉曲線が横切る前記移動経路グラフのエッジの数を、前記一対のノードを繋ぐエッジに、重みとして設定した、警備領域グラフを生成し、前記警備領域グラフに設定されたノードの危険度及びエッジの重みと、前記警備員の人数とを用いて前記警備領域グラフの各エッジの警備確率についての最適化問題を解き、前記危険度の更新後の前記移動経路グラフにおいて前記閉曲線を更に生成し、前記移動経路グラフにおいて、前記更に生成した前記閉曲線が横切るエッジに、過去に生成した前記閉曲線が横切るエッジ以外のエッジがあるか否かを判定し、前記過去に生成したエッジ以外のエッジがなかったと判定した場合には、表示装置を制御して、前記過去に生成した前記閉曲線を前記移動経路グラフ上で表示させると共に、表示させた前記閉曲線について生成した前記警備領域グラフについて得られた前記警備確率の最適解を、表示させた前記閉曲線に対応づけて表示させ、前記過去に生成したエッジ以外のエッジがあったと判定した場合には、前記更に生成した前記閉曲線に基づいた前記警備領域グラフの生成、前記危険度の更新、前記閉曲線の生成と、生成された前記閉曲線についての前記判定とを、前記過去に生成したエッジ以外のエッジがなかったと判定されるまで繰り返す、処理をコンピュータが実行する。
【発明の効果】
【０００９】
上述の態様によれば、警備員の配置についての確率の算出負荷の軽減を図ることができる。
【図面の簡単な説明】
【００１０】
【図１】警備グラフの一例を示す模式図である。
【図２】警備計画情報のデータ構造の従来例を示す模式図である。
【図３】警備計画情報の表示方法の従来例を説明する模式図である。
【図４】本発明の一実施形態に係る警備計画支援装置の機能構成を示すブロック図である。
【図５Ａ】本発明の一実施形態に係る警備計画支援方法を示すフローチャート（その１）である。
【図５Ｂ】本発明の一実施形態に係る警備計画支援方法を示すフローチャート（その２）である。
【図６】第１の実施例における各ターゲットの危険度の計算結果を示す模式図である。
【図７Ａ】第１の実施例における１回目のステップＳ４の処理の結果を示す模式図である。
【図７Ｂ】第１の実施例における１回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。
【図８Ａ】第１の実施例における２回目のステップＳ４の処理の結果を示す模式図である。
【図８Ｂ】第１の実施例における２回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。
【図９Ａ】第１の実施例における３回目のステップＳ４の処理の結果を示す模式図である。
【図９Ｂ】第１の実施例における３回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。
【図１０】第１の実施例における警備計画情報の表示例を示す模式図である。
【図１１】第１の実施例における警備計画情報の別の表示例を示す模式図である。
【図１２】警備計画支援装置のハードウェア構成を示す模式図である。
【図１３Ａ】本発明と比較する参考例を説明する模式図である。
【図１３Ｂ】参考例において生成される警備領域グラフ及び警備確率の解を示す模式図である。
【図１４】第２の実施例における各ターゲットの危険度の計算結果を示す模式図である。
【図１５】第２の実施例における１回目のステップＳ４の処理の結果を示す模式図である。
【図１６】第２の実施例における２回目のステップＳ４の処理の結果を示す模式図である。
【図１７Ａ】第２の実施例における３回目のステップＳ４の処理の結果を示す模式図である。
【図１７Ｂ】第２の実施例における３回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。
【図１８Ａ】第２の実施例における４回目のステップＳ４の処理の結果を示す模式図である。
【図１８Ｂ】第２の実施例における４回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。
【図１９】第２の実施例における警備計画情報の表示例を示す模式図である。
【発明を実施するための形態】
【００１１】
本発明は、コンピュータ等の警備計画支援装置を用い、警備計画の策定を支援するための警備計画情報を作成するものである。警備計画支援装置は、警備区域内の移動経路に警備員を配置する際の警備確率の最適解を算出し、警備確率を含む警備計画情報を作成する。更に、作成した警備計画情報を表示装置等に表示して提示することで、警備員の配置の決定を支援する。
【００１２】
警備計画支援装置は、警備区域内の移動経路を表す経路グラフと、警備条件とに基づいて、警備員の配置についての警備確率、すなわち侵入者が警備対象（ターゲット）に到達することを防げる確率を算出する。また、警備計画支援装置は、算出した警備確率を、経路グラフに警備条件を付加した警備グラフとともに液晶ディスプレイ等の表示装置に表示させる。
【００１３】
経路グラフは、警備区域内の移動経路を頂点（ノード）の集合Ｖ及び辺（エッジ）の集合Ｅで表したグラフＧ＝（Ｖ，Ｅ）である。また、警備条件は、移動経路における侵入者の侵入位置、移動経路における警備対象の位置又は範囲、侵入者が警備対象に到達したときの損失、並びに配置する警備員の数を含む。なお、警備対象の位置又は範囲は、移動経路において侵入者が目標とする位置又は範囲のことである。また、侵入者が警備対象に到達したときの損失は、侵入者が目標とする位置又は範囲に到達することにより生じ得る損害や被害の相対値である。
【００１４】
図１は、警備グラフの一例を示す模式図である。
図１に示すように、警備グラフ１００は、経路グラフＧに警備条件を付加したグラフである。この警備グラフ１００では、数字ｍを囲む円及び八角形がそれぞれ頂点Ｖｍを表し、２つの頂点Ｖｉ，Ｖｊに接続する二重線が辺Ｅｉ,ｊを表している。
【００１５】
警備グラフ１００において、太線の円で表した５個の頂点Ｖ１，Ｖ２，Ｖ３，Ｖ４，及びＶ８は、警備条件に基づき侵入者の侵入位置に設定された頂点である。
【００１６】
一方、警備グラフ１００において、八角形で表した４個の頂点Ｖ２８，Ｖ３２，Ｖ３７，及びＶ４６は、警備条件に基づき警備対象に設定された頂点である。警備対象に設定された頂点Ｖ２８，Ｖ３２，Ｖ３７，Ｖ４６の数値「ｍ：Ｕｔ」は、ｍが頂点の通し番号を表し、Ｕｔがその頂点に侵入者が到達したときの損失を表している。
【００１７】
なお、図１では、侵入位置に設定された頂点を太線の円で表示し、警備対象に設定された頂点を八角形で表示して他の頂点と区別しているが、表示装置等に表示する場合、これに限らず、表示色を変える等の方法で区別しても良い。
【００１８】
以下、図１に示した警備グラフ１００で表される警備区域内を３人の警備員で警備する場合を例に挙げ、従来例及び本発明の実施の形態等を説明する。なお、以下の説明では、侵入位置に設定された５個の頂点Ｖ１，Ｖ２，Ｖ３，Ｖ４，及びＶ８をソースともいう。また、以下の説明では、警備対象に設定された４個の頂点Ｖ２８，Ｖ３２，Ｖ３７，及びＶ４６をターゲットともいう。
【００１９】
［従来例］
図２は、警備計画情報のデータ構造の従来例を示す模式図である。図３は、警備計画情報の表示方法の従来例を説明する模式図である。
【００２０】
図１に示した警備グラフ１００のようにターゲットが複数である場合の警備員の配置についての解は、従来、線形計画法と混合整数計画法とを繰り返して求めている。ここでは詳細な計算方法についての説明を省略するが、従来の方法で警備グラフ１００における警備員の配置についての解は、図２に示すような形式で算出される。なお、図２では、グラフの辺Ｅｉ,ｊをＥ（ｉ,ｊ）としている。
【００２１】
すなわち、従来の方法では、警備員の配置に関する情報（以下「警備計画情報」ともいう）は、警備員を配置する３本の辺の集合である配置パターンと、その選択確率とにより提示される。図２に示した情報は、８通りの配置パターンがそれぞれの選択確率で選択されるよう配置パターンを変えながら警備をすると、警備確率が最も高くなるということを示している。
【００２２】
この図２に示した警備計画情報は、図３に示すように、警備グラフ１００における警備員の配置箇所（辺）の色を変えることでオペレータ等に提示される。図３において、太線で表示された辺Ｅ１７,２５，Ｅ３８,３９，Ｅ４０,４９は８通りの配置パターンから選択された１つの配置パターンを表している。また、網掛けで示された辺Ｅ５,１３，Ｅ７,１４，Ｅ８,１８，Ｅ９,１９，Ｅ１０,１５，Ｅ１２,１６，Ｅ１３,２３，Ｅ１５,２０，Ｅ１６,２２は、残りの配置パターンに含まれる辺を表している。
【００２３】
しかしながら、図２に示したような警備計画情報は、例えば、警備グラフ１００から警備員の数に応じた辺の組（配置パターン）を複数抽出し、それらの組み合わせを変えながら最適な配置パターンの組み合わせを算出する。そのため、配置パターンの組み合わせ及び選択確率の算出に時間がかかり、装置に大きな処理負荷がかかる。
【００２４】
また、図３に示したように、警備員を配置すると特定した辺を強調表示した場合、警備グラフ１００における警備員の配置箇所はわかるが、選択確率以外にどのような理由があってその配置が選出されたかまではわからない。また、強調表示された３つの辺と警備確率との関係についても表示を見ただけではわからない。そのため、専門家やオペレータが、図２に示したような情報と図３に示したような情報とに基づいて警備員の配置箇所の妥当性を評価する際には手間と時間がかかる。したがって、提示された警備計画情報に基づく警備員の配置の決定等、警備計画の是非の確認や修正に手間と時間がかかる。
【００２５】
これに対し、本発明では、以下に説明するように警備モデル１００（経路グラフＧ）を分割する最小カットを利用することで、警備員の配置箇所や配置した理由をわかりやすくし、警備員の配置箇所に対する評価をしやすくする。また、本発明では、最も危険度が高いターゲットに着目し、当該ターゲットの危険度を低下させるよう警備確率を算出することで計算量を低減し、算出負荷の低減を図る。なお、本明細書における危険度は、侵入者がターゲットに到達した際の損失の期待値を意味する。また、本明細書における警備確率は、侵入者がターゲットに到達（侵入）することを防げる確率を意味する。
【００２６】
［実施形態］
図４は、本発明の一実施形態に係る警備計画支援装置の機能構成を示すブロック図である。
【００２７】
図４に示すように、本実施形態に係る警備計画支援装置２は、入力情報受付部２０１と、警備グラフ作成部２０２と、警備計画情報生成部２０３と、表示制御部２０４と、経路情報記憶部２０５とを備える。また、警備計画支援装置２は、その他に、警備計画情報を生成する過程で算出されるデータ等を一時的に記憶するバッファ等の記憶部（図示せず）を備える。
【００２８】
入力情報受付部２０１は、マウスやキーボード等の入力装置３を介して入力される情報を受付ける。受付ける情報には、例えば、警備グラフの作成に必要な頂点の数や接続関係を表すグラフ情報、警備条件等がある。
【００２９】
警備グラフ作成部２０２は、入力情報受付部２０１で受付けた情報や、経路情報記憶部２０５に記憶された経路情報等を用いて警備グラフ１００を作成する。
【００３０】
警備計画情報生成部２０３は、作成した警備グラフ１００及び配置する警備員の数に基づいて警備確率を含む警備計画情報を生成する。
【００３１】
表示制御部２０４は、警備グラフ作成部２０２で作成した警備グラフ１００や、警備計画情報生成部２０３で生成した警備計画情報等を表示装置４に表示させる。
【００３２】
経路情報記憶部２０５には、警備グラフ１００の作成に必要な経路情報や、予め作成された経路グラフ等を記憶させる。
【００３３】
また、警備計画支援装置２における警備計画情報生成部２０３は、危険度算出部２０３ａと、最小カット算出部２０３ｂと、判定部２０３ｃと、警備領域グラフ生成部２０３ｄと、警備確率算出部２０３ｅと、を有する。
【００３４】
危険度算出部２０３ａは、警備グラフ１００における各ターゲットの危険度を算出する。本実施形態では、ターゲットが攻撃されると仮定した場合の損失Ｕｔの期待値を危険度とする。
【００３５】
最小カット算出部２０３ｂは、警備グラフ１００において最も危険度が高いターゲットの集合をソースの集合Ｓから分離する最小カットを算出する。
【００３６】
判定部２０３ｃは、最小カット算出部２０３ｂで最小カットを算出する毎に、最小カットセット（最小カットを表す閉曲線が横切る全ての辺の組み合わせ）と、図示しない記憶部に格納された集合Ｅ’の要素とを比較する。そして、最小カットセットが集合Ｅ’にない場合、当該最小カットセットを集合Ｅ’に追加する。一方、最小カットセットが集合Ｅ’にある場合、直前に警備確率算出部２０３ｅで算出した警備確率を含む警備計画情報を表示制御部２０４に出力する。
【００３７】
警備領域グラフ生成部２０３ｄは、集合Ｅ’の要素で警備グラフ１００を複数の領域に分割し、各領域を頂点とする警備領域グラフを生成する。
【００３８】
警備確率算出部２０３ｅは、警備領域グラフ上で警備確率についての最適化問題を解き、図示しない記憶部に格納された警備計画Ｘを更新する。
【００３９】
次に、図５Ａ及び図５Ｂを参照し、警備計画支援装置２を用いた警備確率算出の手順を説明する。なお、以下の説明では、最小カットを表す閉曲線のことを最小カットラインともいう。
【００４０】
図５Ａは、本発明の一実施形態に係る警備計画支援方法を示すフローチャート（その１）である。図５Ｂは、本発明の一実施形態に係る警備計画支援方法を示すフローチャート（その２）である。
【００４１】
警備計画支援装置２により警備計画情報を生成して提示する際には、図５Ａに示すように、まず、入力情報等に基づき警備グラフ１００を作成する（ステップＳ１）。ステップＳ１は、入力情報受付部２０１、警備グラフ作成部２０２、及び経路情報記憶部２０５が協働して行う。警備計画支援装置２のオペレータが入力装置３を操作して入力した経路グラフＧ＝（Ｖ，Ｅ）や警備条件等の情報は、警備グラフ作成部２０２に送られる。警備条件は、ソースの集合Ｓ、ターゲットの集合Ｔ、ターゲットが攻撃された際（侵入者がターゲットに到達した際）の損失Ｕｔ、警備員の数ｋ等を含んでいる。警備グラフ作成部２０２は、入力情報や、経路情報記憶部２０５に記憶された経路情報等に基づき、図１に示したような警備グラフ１００を作成する。また、警備グラフ作成部２０２は、作成した警備グラフ１００を、表示制御部２０４を介して表示装置４に表示させる。
【００４２】
警備グラフ１００の作成が終了すると、次に、最小カットセットに含まれる辺、すなわち最小カットラインが横切る辺の集合Ｅ’、及び警備計画Ｘを空集合に初期化する（ステップＳ２）。ステップＳ２は、警備計画情報生成部２０３が行う。警備計画Ｘは、警備確率を含む情報の集合であり、例えば、ターゲットの識別番号、当該ターゲットに基づいて求めた警備ラインの情報、及び警備確率の組を１つの要素とする。本実施形態では、警備ラインの情報として最小カットセット、すなわち最小カットラインが横切る辺の情報を用いる。
【００４３】
警備計画情報生成部２０３は、次に、警備グラフ１００における各ターゲットの危険度を算出し、最も危険度が大きいターゲットの集合Ｔ’を求める（ステップＳ３）。ステップＳ３は、危険度算出部２０３ａが行う。ターゲットの危険度は、侵入者がターゲットに到達したと仮定した場合の損失Ｕｔの期待値であり、例えば下記の式（１）により算出する。
【００４４】
（危険度）＝（１−Σｘ）・Ｕｔ  ・・・（１）
【００４５】
式（１）におけるΣｘは、ソースの集合Ｓからターゲットに至る経路の警備確率ｘの和である。警備確率ｘは、ターゲットの識別番号をキー情報として警備計画Ｘの要素を検索して取得する。
【００４６】
なお、警備計画Ｘにターゲットと対応した警備確率ｘがない場合、Σｘ＝０として式（１）の計算を行う。
【００４７】
集合Ｔ’を求めたら、警備計画情報生成部２０３は、次に、集合Ｔ’をソースの集合Ｓから分離する最小カットを求め、最小カットセット（最小カットラインが横切る全ての辺の集合）を集合Ｅ’に追加する（ステップＳ４）。ステップＳ４は、最小カット算出部２０３ｂと判定部２０３ｃとが協働して行う。最小カット算出部２０３ｂは、グラフ理論における既知の最小カットの算出方法のいずれか、例えば多項式時間アルゴリズムを用いて求める。なお、最小カットとなるパターンが複数ある場合、最小カット算出部２０３ｂは、複数のパターンから１つのパターンを選出する。パターンの選出方法は任意であり、例えば、ターゲットの集合Ｔ’側に含まれる頂点Ｖの数が最多となる最小カット、又は最少となる最小カットを選出する。
【００４８】
また、最小カットとなるパターンが複数ある場合、例えば、表示制御部２０４を介して表装置４に複数のパターン（最小カットライン）を表示してオペレータに選択させてもよい。オペレータに選択させる場合、例えば、実際の警備区域における各所の状況や専門家の助言等を参考にし、より適した最小カットを選出できる。
【００４９】
ステップＳ４では、最小カットを求めた後、判定部２０３ｃが、最小カットセットを集合Ｅ’に追加する。この際、判定部２０３ｃは、追加される辺が１つの最小カットセットの辺の組であることを識別可能な態様で、辺の組み合わせを集合Ｅ’に追加する。例えば、最小カットセットがＥｉ１,ｊ１，Ｅｉ２,ｊ２の場合、ｅ１＝｛Ｅｉ１,ｊ１，Ｅｉ２,ｊ２｝，Ｅ’＝｛ｅ１｝として、Ｅ’とＥｉ１,ｊ１，Ｅｉ２,ｊ２とを対応付けしておく。
【００５０】
なお、判定部２０３ｃは、集合Ｅ’の要素に追加する最小カットセットと合致する要素がない場合にのみ、当該最小カットセットを新たな要素として集合Ｅ’に追加する。
【００５１】
そして、判定部２０３ｃは、ステップＳ４の後、集合Ｅ’の要素が増えたかを判定し（ステップＳ５）、警備計画情報生成部２０３が次に行う処理を選択する。集合Ｅ’の要素が増えていない場合（ステップＳ５；Ｎｏ）、図５Ｂに示すように、表示制御部２０４を介して警備グラフ１００及び警備計画Ｘを表示装置４に表示させ（ステップＳ８）、処理を終了する。
【００５２】
一方、集合Ｅ’の要素が増えた場合（Ｓ５；Ｙｅｓ）、判定部２０３ｃは、警備領域グラフ生成部２０３ｄに、集合Ｅ’の要素で警備グラフを複数の領域に分割して警備領域グラフを作成する処理（ステップＳ６）を行わせる。
【００５３】
警備領域グラフ生成部２０３ｄは、集合Ｅ’の要素で警備グラフ１００（経路グラフＧ）を複数の領域に分割して警備領域グラフを生成する。警備領域グラフは、分割した各領域を頂点とし、集合Ｅ’の要素を辺とするグラフである。警備領域グラフの頂点のうち、最も危険度が大きいターゲットを含む領域と対応する頂点には、当該ターゲットに到達されたときの損失Ｕｔが対応付けられる。また、警備領域グラフにおける２つの頂点間を接続する辺には、２つの頂点に分離する最小カットの大きさ、すなわち最小カットセットに含まれる辺の数が重みとして対応付けられる。
【００５４】
警備領域グラフを生成すると、警備計画情報生成部２０３は、次に、警備領域グラフを用いて警備確率についての最適化問題を解き、警備計画Ｘを最適解に更新する（ステップＳ７）。ステップＳ７は、警備確率算出部２０３ｅが行う。警備確率算出部２０３ｅは、例えば、下記の式（２）で表される辺ｅの警備確率ｘｅについての最適化問題を解き、警備確率ｘｅの最適解を算出する。
【００５５】
【数１】
0006572553.tif 000002
【００５６】
式（２）におけるＥ’は警備領域グラフにおける辺ｅの集合である。また、式（２）におけるπ及びＵπは、それぞれ警備領域グラフにおける侵入位置からターゲットに向かう経路、及び侵入者がターゲットに到達したときの損失である。また、式（２）におけるＣｅは、警備領域グラフの辺ｅの重みである。また、式（２）におけるｋは、警備員の数である。
【００５７】
式（２）を解くことにより、警備領域グラフの辺ｅに対応する警備グラフ１００のＣｅ本の辺がいずれも警備確率ｘｅで選択される。
【００５８】
なお、式（２）は、警備確率ｘｅについての最適化問題を解くための数式の一例である。警備確率ｘｅについての最適化問題を解くための数式は、式（２）に限らず、他の既知の数式のいずれかを用いてもよい。また、警備確率ｘｅについての最適化問題を解くための数式は、既知の数式の一部を変更した数式でも良い。
【００５９】
警備計画Ｘの更新（ステップＳ７）が終了すると、ターゲットの危険度を算出する処理（ステップＳ３）に戻り、以後、ステップＳ５における判定が「Ｎｏ」になるまでステップＳ３〜Ｓ７の処理を繰り返す。
【００６０】
次に、図６〜図１０を参照し、本実施形態の警備確率算出方法をより具体的に説明する。
【００６１】
［第１の実施例］
図６は、第１の実施例における各ターゲットの危険度の計算結果を示す模式図である。図７Ａは、第１の実施例における１回目のステップＳ４の処理の結果を示す模式図である。図７Ｂは、第１の実施例における１回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。なお、図７Ｂには、図７Ａに示した閉曲線Ｌ１０１の一部分のみを示している。
【００６２】
第１の実施例では、最小カットのパターンが複数ある場合にターゲットの集合Ｔ’側に含まれる頂点Ｖの数が最多となる最小カットを選出するという条件でステップＳ４の処理を行ったときの途中経過及び最終結果を説明する。
【００６３】
図１の警備グラフ１００におけるターゲットは、頂点Ｖ２８，Ｖ３２，Ｖ３７，及びＶ４６の４個である。そして、各ターゲットに到達された場合の損失Ｕｔは、それぞれ２（Ｖ２８）、４（Ｖ３２）、５（Ｖ３７）、及び３（Ｖ４６）である。
【００６４】
また、１回目のステップＳ３の処理を行う時点では、警備計画Ｘは空集合であり警備確率ｘの情報がない。
【００６５】
したがって、１回目のステップＳ３の処理で算出される各ターゲットの危険度は、図６に示すように、それぞれ２．０００（Ｖ２８），４．０００（Ｖ３２），５．０００（Ｖ３７），及び３．０００（Ｖ４６）となる。よって、１回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３７｝になる。
【００６６】
そのため、次のステップＳ４の処理では、頂点Ｖ３７をソースの集合Ｓから分離する最小カットを算出する。ソースの集合Ｓは、図１に示したように、Ｓ＝｛Ｖ１，Ｖ２，Ｖ３，Ｖ４，Ｖ８｝である。よって、既知の方法で最小カットを求めると、その解の１つとして、図７Ａに示した閉曲線Ｌ１０１で表される最小カットが選出される。閉曲線Ｌ１０１は、上記のようにターゲット側（頂点Ｖ３７側）の領域が最大となる最小カットを表す最小カットラインである。
【００６７】
また、ステップＳ４では、閉曲線Ｌ１０１が横切る全ての辺を集合Ｅ’に追加する。図７Ａに示した例において、閉曲線Ｌ１０１は、４本の辺Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，及びＥ４８,４９を横切る。よって、１回目のステップＳ４の処理の結果、集合Ｅ’に上記の４本の辺Ｅの組ｅ１（＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝）が追加される。
【００６８】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７の処理が行われる。
【００６９】
１回目のステップＳ６では、ステップＳ４で算出した最小カット（閉曲線Ｌ１０１）により警備グラフ１００を２つの領域に分割し、図７Ｂに示すように、分割した２つの領域をそれぞれ頂点Ｖ’１，Ｖ’２とする警備領域グラフ１５０を生成する。このとき、当該２個の頂点Ｖ’１，Ｖ’２は、警備グラフ１００において閉曲線Ｌ１０１が横切る４本の辺の組に相当する１本の辺ｅ１で接続される。
【００７０】
図７Ｂに示した警備領域グラフ１５０においては、２個の頂点のうちの一方の頂点Ｖ’１がソースの集合Ｓを含み、他方の頂点Ｖ’２が最も危険度が大きいターゲット（頂点Ｖ３７）を含む。そのため、頂点Ｖ’１から侵入した侵入者が頂点Ｖ’２に到達した場合の損失Ｕπは５となる。また、辺ｅ１は、警備グラフ１００において閉曲線Ｌ１０１が横切る辺、すなわち閉曲線Ｌ１０１で表される最小カットの最小カットセットに相当する。そのため、辺ｅ１の重みＣｅ１は４となる。
【００７１】
このような条件に警備員の数ｋ＝３を加え、ステップＳ７において上記の式（２）で表される最適化問題を解くと、図７Ｂに示したように、警備確率ｘｅ１は３／４となる。
【００７２】
したがって、１回目のステップＳ７の処理では、警備確率ｘｅ１に、閉曲線Ｌ１０１の情報、及び警備グラフ１００を閉曲線Ｌ１０１で分割したときに最も危険度が大きいターゲット側に含まれる全てのターゲットの情報を対応付け、警備計画Ｘを更新する。閉曲線Ｌ１０１についての情報は、例えば閉曲線Ｌ１０１が横切る辺の情報ｅ１＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝を用いる。また、１回目の処理では、図７Ａに示したように、最も危険度が大きいターゲット側に含まれるターゲットは、頂点Ｖ３７，Ｖ４６の２個である。そのため、警備計画Ｘは、例えば、下記の式（３−１）〜（３−３）で表されるような情報に更新する。
【００７３】
Ｘ＝｛Ｘ１｝  ・・・（３−１）
Ｘ１＝｛３／４，ｅ１，Ｖ３７，Ｖ４６｝  ・・・（３−２）
ｅ１＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝  ・・・（３−３）
【００７４】
こうして１回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、２回目の処理を開始する。
【００７５】
図８Ａは、第１の実施例における２回目のステップＳ４の処理の結果を示す模式図である。図８Ｂは、第１の実施例における２回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。なお、図８Ｂには、図８Ａに示した閉曲線Ｌ１０１，Ｌ１０２の一部分のみを示している。
【００７６】
２回目のステップＳ３の処理を行う時点では、４個のターゲットのうちの頂点Ｖ３７，Ｖ４６と対応付けされた警備確率ｘｅ１（＝３／４）が警備計画Ｘに格納されている。そのため、２回目のステップＳ３の処理で頂点Ｖ３７，Ｖ４６の危険度を算出する際には、式（１）における警備確率Σｘに３／４が入力される。一方、２回目のステップＳ３においても、頂点Ｖ２８，Ｖ３２の危険度を算出する際には、式（１）における警備確率Σｘに０が入力される。したがって、２回目のステップＳ３の処理で算出される各ターゲットの危険度は、図６に示すように、２．０００（Ｖ２８），４．０００（Ｖ３２），１．２５０（Ｖ３７），及び０．７５０（Ｖ４６）となる。よって、２回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３２｝になる。
【００７７】
そのため、２回目のステップＳ４の処理では、頂点Ｖ３２をソースの集合Ｓから分離する最小カットを算出する。ここでは、図８Ａに示した閉曲線Ｌ１０２で表される、３本の辺Ｅ１０,１５，Ｅ１２,１６，及びＥ４９,５０をカットする最小カットが選出される。
【００７８】
また、ステップＳ４では、選出した最小カットを表す閉曲線Ｌ１０２が横切る３本の辺の組ｅ２（＝｛Ｅ１０,１５，Ｅ１２,１６，Ｅ４９,５０｝）が集合Ｅ’に追加される。すなわち、集合Ｅ’は、下記の式（４−１）〜（４−３）で表される情報に更新される。
【００７９】
Ｅ’＝｛ｅ１，ｅ２｝  ・・・（４−１）
ｅ１＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝  ・・・（４−２）
ｅ２＝｛Ｅ１０,１５，Ｅ１２,１６，Ｅ４９,５０｝  ・・・（４−３）
【００８０】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７が行われる。
【００８１】
２回目のステップＳ６の処理を行うとき、集合Ｅ’の要素は、上記のように閉曲線Ｌ１０１が横切る辺の組を表すｅ１と、閉曲線Ｌ１０２が横切る辺の組を表すｅ２の２つである。そのため、２回目のステップＳ６の処理では、閉曲線Ｌ１０１，Ｌ１０２で表される最小カットにより警備グラフ１００を３つの領域に分割し、図８Ｂに示すように、分割した３つの領域をそれぞれ頂点Ｖ’１，Ｖ’２，Ｖ’３とする警備領域グラフ１５１を生成する。
【００８２】
警備領域グラフ１５１では、３個の頂点のうち、２本の辺ｅ１，ｅ２が接続している頂点Ｖ’１がソースの集合Ｓを含む。
【００８３】
また、残りの２つの頂点のうち、辺ｅ１が接続している頂点Ｖ’２は閉曲線（最小カットライン）Ｌ１０１によりソースの集合Ｓから分離された領域を表している。すなわち、頂点Ｖ’２は警備グラフ１００における４個のターゲットのうちの２個（頂点Ｖ３７，Ｖ４６）を含む。頂点Ｖ３７，Ｖ４６は、頂点Ｖ３７の損失Ｕｔのほうが大きい。そのため、頂点Ｖ’１から侵入した侵入者が頂点Ｖ’２に到達した場合の損失Ｕπは頂点Ｖ３７の損失、すなわち５となる。また、辺ｅ１は、上記のように警備グラフ１００において閉曲線Ｌ１０１が横切る辺を表している。そのため、辺ｅ１の重みＣｅ１は４となる。
【００８４】
また、辺ｅ２が接続している頂点Ｖ’３は閉曲線（最小カットライン）Ｌ１０２によりソースの集合Ｓから分離された領域を表している。すなわち、頂点Ｖ’３は警備グラフ１００における４個のターゲットのうちの２個（頂点Ｖ２８，Ｖ３２）を含む。頂点Ｖ２８，Ｖ３２は、頂点Ｖ３２の損失Ｕｔのほうが大きい。そのため、頂点Ｖ’１から侵入した侵入者が頂点Ｖ’３に到達した場合の損失Ｕπは頂点Ｖ３２の損失、すなわち４となる。また、辺ｅ２は、上記のように警備グラフ１００において閉曲線Ｌ１０２が横切る辺を表している。そのため、辺ｅ２の重みＣｅ２は３となる。
【００８５】
このような条件に警備員の数ｋ＝３を加え、ステップＳ７において上記の式（２）で表される最適化問題を解くと、図８Ｂに示したように、辺ｅ１の警備確率ｘｅ１は１５／３１となる。また、辺ｅ２の警備確率ｘｅ２は１１／３１となる。
【００８６】
したがって、２回目のステップＳ７の処理では、例えば、下記の式（５−１）〜（５−５）で表されるような情報に警備計画Ｘを更新する。
【００８７】
Ｘ＝｛Ｘ１，Ｘ２｝  ・・・（５−１）
Ｘ１＝｛１５／３１，ｅ１，Ｖ３７，Ｖ４６｝  ・・・（５−２）
ｅ１＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝  ・・・（５−３）
Ｘ２＝｛１１／３１，ｅ２，Ｖ２８，Ｖ３２｝  ・・・（５−４）
ｅ２＝｛Ｅ１０,１５，Ｅ１２,１６，Ｅ４９,５０｝  ・・・（５−５）
【００８８】
こうして２回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、３回目の処理を開始する。
【００８９】
図９Ａは、第１の実施例における３回目のステップＳ４の処理の結果を示す模式図である。図９Ｂは、第１の実施例における３回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。なお、図９Ｂには、図９Ａに示した閉曲線Ｌ１０１，Ｌ１０２，Ｌ１０３の一部分のみを示している。
【００９０】
３回目のステップＳ３の処理を行う時点では、頂点Ｖ３７，Ｖ４６と対応付けされた警備確率ｘｅ１（＝１５／３１）、及び頂点Ｖ２８，Ｖ３２と対応付けされた警備確率ｘｅ２（＝１１／３１）が警備計画Ｘに格納されている。そのため、３回目のステップＳ３の処理で算出される各ターゲットの危険度は、図６に示すように、１．２９０（Ｖ２８），２．５８１（Ｖ３２），２．５８１（Ｖ３７），及び１．５４８（Ｖ４６）となる。よって、３回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３２，Ｖ３７｝になる。
【００９１】
そのため、３回目のステップＳ４の処理では、２個の頂点Ｖ３２，Ｖ３７をソースの集合Ｓから分離する最小カットを算出する。ここでは、図９Ａに示した閉曲線Ｌ１０３で表される、６本の辺Ｅ５,１３，Ｅ７,１４，Ｅ８,１８，Ｅ８,９，Ｅ３,１１，及びＥ４,１２をカットする最小カットが選出される。
【００９２】
また、ステップＳ４では、選出した最小カットを表す閉曲線Ｌ１０３が横切る６本の辺の組ｅ３（＝｛Ｅ５,１３，Ｅ７,１４，Ｅ８,１８，Ｅ８,９，Ｅ３,１１，Ｅ４,１２｝）が集合Ｅ’に追加される。すなわち、集合Ｅ’は、下記の式（６−１）〜（６−４）で表される情報に更新される。
【００９３】
Ｅ’＝｛ｅ１，ｅ２，ｅ３｝  ・・・（６−１）
ｅ１＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝  ・・・（６−２）
ｅ２＝｛Ｅ１０,１５，Ｅ１２,１６，Ｅ４９,５０｝  ・・・（６−３）
ｅ３＝｛Ｅ５,１３，Ｅ７,１４，Ｅ８,１８，Ｅ８,９，Ｅ３,１１，Ｅ４,１２｝  ・・・（６−４）
【００９４】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７が行われる。
【００９５】
３回目のステップＳ６の処理を行うとき、集合Ｅ’の要素は、上記のように閉曲線Ｌ１０１が横切る辺の組を表すｅ１、閉曲線Ｌ１０２が横切る辺の組を表すｅ２、及び閉曲線Ｌ１０３が横切る辺の組を表すｅ３の３つである。そのため、３回目のステップＳ６の処理では、警備グラフ１００を閉曲線Ｌ１０１，Ｌ１０２，Ｌ１０３で４つの領域に分割し、図９Ｂに示すように、分割した４つの領域をそれぞれ頂点Ｖ’１，Ｖ’２，Ｖ’３，Ｖ’４とする警備領域グラフ１５２を生成する。
【００９６】
警備領域グラフ１５２において、４個の頂点のうち、３本の辺ｅ１，ｅ２，ｅ３が接続している頂点Ｖ’４は、ソースの集合Ｓ、頂点Ｖ３７，Ｖ４６を含む領域、及び頂点Ｖ２８，Ｖ３２を含む領域から分離された領域を表す。図９Ａに示したように、警備グラフ１００における頂点Ｖ’４と対応する領域にはターゲットがない。そのため、頂点Ｖ’４に損失Ｕπは設定されない。
【００９７】
頂点Ｖ’４と辺ｅ３で接続している頂点Ｖ’１は、ソースの集合Ｓを表す。よって、頂点Ｖ’１にも損失Ｕπは設定されない。
【００９８】
頂点Ｖ’４と辺ｅ１で接続している頂点Ｖ’２は、閉曲線Ｌ１０１によりソースの集合Ｓから分離された領域を表しており、警備グラフ１００における４個のターゲットのうちの２個（頂点Ｖ３７，Ｖ４６）を含む。そのため、２回目の処理のときと同様、頂点Ｖ’１から侵入した侵入者が頂点Ｖ’２に到達した場合の損失Ｕπは５となる。また、辺ｅ１は警備グラフ１００において閉曲線Ｌ１０１が横切る辺を表しているので、辺ｅ１の重みＣｅ１は４となる。
【００９９】
また、頂点Ｖ’４と辺ｅ２で接続している頂点Ｖ’３は、閉曲線Ｌ１０２によりソースの集合Ｓから分離された領域を表しており、警備グラフ１００における４個のターゲットのうちの２個（頂点Ｖ２８，Ｖ３２）を含む。そのため、２回目の処理のときと同様、頂点Ｖ’１から侵入した侵入者が頂点Ｖ’３に到達した場合の損失Ｕπは４となる。また、辺ｅ２は警備グラフ１００において閉曲線Ｌ１０２が横切る辺を表しているので、辺ｅ２の重みＣｅ２は３となる。
【０１００】
このような条件に警備員の数ｋ＝３を加え、上記の式（２）で表される最適化問題を解くと、図９Ｂに示したように、辺ｅ１の警備確率ｘｅ１が３／２６、辺ｅ３の警備確率ｘｅ３が１１／２６という結果が得られる。
【０１０１】
したがって、３回目のステップＳ７の処理では、例えば、下記の式（７−１）〜（７−５）で表されるような情報に警備計画Ｘを更新する。
【０１０２】
Ｘ＝｛Ｘ１，Ｘ３｝  ・・・（７−１）
Ｘ１＝｛３／２６，ｅ１，Ｖ３７，Ｖ４６｝  ・・・（７−２）
ｅ１＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９｝  ・・・（７−３）
Ｘ３＝｛１１／２６，ｅ３，Ｖ２８，Ｖ３２，Ｖ３７，Ｖ４６｝  ・・・（７−４）
ｅ３＝｛Ｅ５,１３，Ｅ７,１４，Ｅ８,１８，Ｅ８,９，Ｅ３,１１，Ｅ４,１２｝  ・・・（７−５）
【０１０３】
こうして３回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、４回目の処理を開始する。
【０１０４】
４回目のステップＳ３の処理を行う時点では、頂点Ｖ３７，Ｖ４６と対応付けされた警備確率ｘｅ１（＝３／２６）、及び頂点Ｖ２８，Ｖ３２，Ｖ３７，Ｖ４６と対応付けされた警備確率ｘｅ３（＝１１／２６）が警備計画Ｘに格納されている。そのため、４回目のステップＳ３の処理で算出される各ターゲットの危険度は、図６に示すように、１．１５４（Ｖ２８），２．３０８（Ｖ３２），２．３０８（Ｖ３７），及び１．３８５（Ｖ４６）となる。よって、４回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３２，Ｖ３７｝になる。
【０１０５】
すなわち、４回目のステップＳ４の処理では、３回目の処理と同様、２個の頂点Ｖ３２，Ｖ３７をソースの集合Ｓから分離する最小カットを算出する。したがって、図９Ａに示した閉曲線Ｌ１０３で表される、６本の辺Ｅ５,１３，Ｅ７,１４，Ｅ８,１８，Ｅ８,９，Ｅ３,１１，及びＥ４,１２をカットする最小カットが選出される。
【０１０６】
閉曲線Ｌ１０３が横切る辺の組は、３回目のステップＳ４の処理において集合Ｅ’に追加されている。そのため、４回目のステップＳ４の処理において集合Ｅ’に新たに追加される要素（辺の組）はない。よって、ステップＳ５の判定は「Ｎｏ」となり、次にステップＳ８の処理が行われる。
【０１０７】
図１０は、第１の実施例における警備計画情報の表示例を示す模式図である。
ステップＳ８では、上記のように、警備グラフ１００に警備計画Ｘの情報（警備計画情報）を付加して表示装置４に表示させる。
【０１０８】
ステップＳ８の処理を行う時点での警備計画Ｘの情報は、３回目のステップＳ７の処理で更新した上記の式（７−１）〜（７−５）で表される情報である。このうち、式（７−３）は、１回目のステップＳ４で算出した閉曲線Ｌ１０１が横切る辺の組を表している。また、式（７−５）は、３回目のステップＳ４で算出した閉曲線Ｌ１０３が横切る辺の組を表している。
【０１０９】
よって、ステップＳ８では、図１０に示すように、閉曲線Ｌ１０１，Ｌ１０３を警備ラインとして警備グラフ１００に重ねた画像を表示装置４に表示させる。またこのとき、閉曲線Ｌ１０１の近傍には、閉曲線Ｌ１０１が横切る辺ｅ１に対する警備確率ｘｅ１（＝３／２６）を表示させる。同様に、閉曲線Ｌ１０３の近傍には、閉曲線Ｌ１０３が横切る辺ｅ３に対する警備確率ｘｅ３（＝１１／２６）を表示させる。
【０１１０】
図１０からわかるように、警備ライン（閉曲線Ｌ１０１，１０３）は、警備ラインで囲まれた領域の外側から領域内のターゲット（警備対象）に向かうことが可能な経路（辺）を横切る。例えば、侵入者が頂点Ｖ３７に向かう場合、頂点Ｖ３７をソースの集合Ｓから分離する最小カットを表す閉曲線Ｌ１０１が横切る辺Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４８,４９のいずれかを通らなければならない。加えて、警備ラインは、所定のターゲットをソースの集合Ｓから分離する際の最小カットに基づいて求めている。そのため、図１０に示した警備計画情報における警備ラインを見ることで、例えば頂点Ｖ３７，Ｖ４６に対する警備員の効率的な配置であることを容易に把握することができる。
【０１１１】
また、式（２）で表される最適化問題を解いて警備ラインを特定すると、１本の警備ラインが横切る警備モデル１００のＣｅ本の辺が同じ警備確率ｘｅで選択される。そのため、警備ラインの近傍に警備確率（例えば３／２６，１１／２６等）を表示することにより、図１０に示した警備グラフ１００に対し３人の警備員をどのように配置すると効率的であるかを容易に把握できる。図１０に示した例では、閉曲線Ｌ１０１が横切る辺に警備員を配置する頻度が３／２６となり、閉曲線Ｌ１０３が横切る辺に警備員を配置する頻度が１１／２６となるように、３人の警備員の配置箇所を変えながら警備をすればよいことが容易にわかる。
【０１１２】
よって、第１の実施例によれば、警備員の配置箇所や、そこに警備員を配置するとよい理由を容易に把握でき、警備計画の妥当性を評価しやすくなる。
【０１１３】
更に、最も危険度が大きいターゲットの危険度を低下させるというルールに従って警備確率を求めているので、専門家等の第三者に妥当性の評価を依頼する場合にルールを簡単に説明できる。加えて、ルール自体が簡素であるため、専門家等の第三者も警備計画の妥当性を評価しやすい。
【０１１４】
しかも、最も危険度が大きいターゲットをソースの集合から分離する最小カットを蓄積し、新たに算出した最小カットが既に蓄積されている場合、その時点で警備確率の算出処理を終了する。新たに算出した最小カットに基づく警備確率の計算が前回と最小カットに基づいてなされる場合、算出される警備確率は前回と同じ結果になり、それ以上ステップＳ３〜Ｓ７の処理を繰り返しても警備確率は変わらない。そのため、新たに算出した最小カットが既に蓄積されている場合に、警備確率の計算を終了することで、計算量の増大による警備計画支援装置の処理負荷の増大を抑えることができる。また、最も危険度が大きいターゲットの危険度を低下させるというルールに従って警備確率を求めているため、警備上重要となる点を見落とすことがない。
【０１１５】
図１１は、第１の実施例における警備計画情報の別の表示例を示す模式図である。
図１０に示した警備計画情報の表示例では、警備グラフ１００に、警備計画Ｘに含まれる警備確率及び警備ライン（閉曲線Ｌ１０１，Ｌ１０３）を重ねて表示している。
【０１１６】
しかしながら、警備計画情報を表示装置４に表示させるときには、これに限らず、図１１に示すように、警備グラフ１００において閉曲線Ｌ１０１，Ｌ１０３が横切る辺を、色を変える等の方法で強調しても良い。このように、閉曲線Ｌ１０１，Ｌ１０３が横切る辺を強調することで、閉曲線Ｌ１０１，Ｌ１０３の意味（すなわち警備員を配置する辺）がより明確になる。
【０１１７】
［ハードウェア構成］
図１２は、警備計画支援装置のハードウェア構成を示す模式図である。
【０１１８】
本実施形態に係る上記の警備計画支援装置２は、例えば、コンピュータと、コンピュータに図５Ａ及び図５Ｂに示した処理を実行させるプログラムとにより実現される。
【０１１９】
図１２に示すように、コンピュータ６は、プロセッサ６０１と、主記憶装置６０２と、補助記憶装置６０３と、入力装置６０４と、表示装置６０５と、記憶媒体駆動装置６０６と、通信インタフェース６０７と、を備える。また、コンピュータ６におけるこれらの要素６０１〜６０７は、バス６１０により相互に接続されており、要素間でのデータの受け渡しが可能になっている。
【０１２０】
プロセッサ６０１は、Central Processing Unit（ＣＰＵ）等、各種のプログラムを実行することによりコンピュータ６の全体の動作を制御する演算処理装置である。
【０１２１】
主記憶装置６０２は、Read Only Memory（ＲＯＭ）６０２ａ及びRandom Access Memory（ＲＡＭ）６０２ｂを有する。ＲＯＭ ６０２ａには、例えばコンピュータ６の起動時にプロセッサ６０１が読み出す所定の基本制御プログラム等が予め記録されている。また、ＲＡＭ ６０２ｂは、プロセッサ６０１が各種のプログラムを実行する際に、必要に応じて作業用記憶領域として使用する。本実施形態においては、例えば上記の処理を行っている間の辺の集合Ｅ’や警備計画Ｘ等の一時的な記憶にＲＡＭ ６０２ｂを使用する。
【０１２２】
補助記憶装置６０３は、Hard Disk Drive（ＨＤＤ）やSolid State Disk（ＳＳＤ）等の主記憶装置６０２に比べて大容量の記憶装置である。補助記憶装置６０３には、プロセッサ６０１によって実行される各種のプログラム（例えば上記の処理と対応するプログラム）や各種のデータ（例えば経路情報）を記憶する。プロセッサ６０１は、補助記憶装置６０３に記憶されているプログラムを読み出して実行するとともに、必要に応じて補助記憶装置６０３に記憶された各種データを読み出す。
【０１２３】
入力装置６０４は、例えばキーボード装置やマウス装置であり、コンピュータ６のオペレータにより操作されると、その操作内容に対応付けられている入力情報をプロセッサ６０１に送信する。
【０１２４】
表示装置６０５は、例えば液晶ディスプレイであり、プロセッサ６０１から送信される表示データに従って各種のテキスト、画像等を表示する。
【０１２５】
記憶媒体駆動装置６０６は、図示しない可搬型記録媒体に記録されているプログラムやデータの読み出し、補助記憶装置６０３に記憶されたデータ等の可搬型記録媒体への記録を行う。可搬型記録媒体としては、例えば、ＵＳＢ規格のコネクタが備えられているフラッシュメモリが利用可能である。また、可搬型記録媒体としては、Compact Disk（ＣＤ）、Digital Versatile Disc（ＤＶＤ）、Blu-ray Disc（Blu-rayは登録商標）等の光ディスクも利用可能である。
【０１２６】
通信インタフェース６０７は、コンピュータ６とインターネット等の通信ネットワーク５とを通信可能に接続し、通信ネットワークを介した外部通信装置等との通信を行う。
【０１２７】
このコンピュータ６は、プロセッサ６０１、主記憶装置６０２、補助記憶装置６０３等が所定のプログラムに従って協働して最小カットを求める計算や警備確率の計算を行い、計算結果を表示装置６０５に表示する。
【０１２８】
また、通信インタフェース６０７を備えたコンピュータ６であれば、例えば、他のコンピュータ等で作成した経路情報や警備グラフ等をコンピュータ６に送信してコンピュータ６に警備確率等を算出させることができる。また、算出した警備確率等の警備計画情報を他のコンピュータに返送し、他のコンピュータで警備計画情報を表示して警備計画の妥当性の評価等を行うこともできる。
【０１２９】
［参考例］
図１３Ａは、本発明と比較する参考例を説明する模式図である。図１３Ｂは、参考例において生成される警備領域グラフ及び警備確率の解を示す模式図である。なお、図１３Ｂには、図１３Ａに示した閉曲線Ｌ５０１〜Ｌ５０５の一部分のみを示している。
【０１３０】
本発明に係る警備確率算出方法の効果を説明するための参考例として、次のような処理を挙げる。参考例では、警備グラフ１００におけるターゲットの集合Ｔから空集合ではないターゲット部分集合Ｔｐを複数用意した後、ターゲット部分集合Ｔｐ毎に、ターゲット部分集合Ｔｐをソースの集合Ｓから分離する最小カットの計算を行う。そしてその後、複数の最小カットにより警備グラフ１００を複数の領域に分割して警備領域グラフを作成し、式（２）で表される最適化問題を解く。
【０１３１】
図１３Ａに示すように、参考例における警備グラフ１００はこれまでに例示したものと同様であり、ターゲットは頂点Ｖ２８，Ｖ３２，Ｖ３７，Ｖ４６の４個である。そのため、参考例においては、４つのターゲットからターゲット部分集合Ｔｐを用意する。このとき、ターゲット部分集合Ｔｐは、最大で２４−１通り、すなわち１５通りとなる。
【０１３２】
この１５通りのターゲット部分集合Ｔｐのそれぞれで最小カットを算出すると、例えば図１３Ａに示した閉曲線Ｌ５０１，５０２，５０３，５０４，５０５で表される、５通りの最小カットに集約される。なお、図１３Ａに示した閉曲線Ｌ５０１〜Ｌ５０５は、第１の実施例と同様、ターゲット部分集合Ｔｐ側に含まれる頂点の数が最多となる最小カットを選出したものである。
【０１３３】
この図１３Ａに示した５本の閉曲線Ｌ５０１〜Ｌ５０５で警備グラフ１００を分割し、上記の要領で警備領域グラフを作成すると、図１３Ｂに示すように、６個の頂点Ｖ’１，Ｖ’２，Ｖ’３，Ｖ’４，Ｖ’５，Ｖ’６と、４本の辺ｅ１，ｅ２，ｅ３，ｅ４とを有する警備領域グラフ１６０となる。
【０１３４】
図１３Ｂに示した警備領域グラフ１６０において、頂点Ｖ’１はソースの集合Ｓを表し、頂点Ｖ’２は閉曲線Ｌ５０１，Ｌ５０２，Ｌ５０３により他の領域から分離したターゲットのない領域を表す。また、頂点Ｖ’３は警備グラフ１００における頂点Ｖ３７を含む領域を表し、頂点Ｖ’４は警備グラフ１００における頂点Ｖ３２を含む領域を表す。また、頂点Ｖ’５は警備グラフにおける頂点Ｖ４６を表し、頂点Ｖ’６は警備グラフにおける頂点Ｖ２８を表す。したがって、警備領域グラフ１６０では、頂点Ｖ’３，Ｖ’４，Ｖ’５，Ｖ’６のそれぞれに、侵入者が頂点に到達した場合の損失Ｕπが設定される。
【０１３５】
頂点Ｖ’２，Ｖ’３を接続する辺ｅ１は、警備グラフ１００において閉曲線Ｌ５０１が横切る辺の組である。そのため、辺ｅ１の重みＣｅ１は４となる。また、頂点Ｖ’２，Ｖ’４を接続する辺ｅ２は閉曲線Ｌ５０２が横切る辺の組であるため、辺ｅ２の重みＣｅ２は３となる。同様に、頂点Ｖ’１，Ｖ’２を接続する辺ｅ３の重みＣｅ３、頂点Ｖ’３，Ｖ’５を接続する辺ｅ４の重みＣｅ４、及び頂点Ｖ’４，Ｖ’６を接続する辺ｅ５の重みＣｅ５は、それぞれ６、２、及び２となる。
【０１３６】
このような条件に警備員の数ｋ＝３を加え、上記の式（２）で表される最適化問題を解くと、図１３Ｂに示したように、辺ｅ１の警備確率ｘｅ１が３／２６、辺ｅ３の警備確率ｘｅ３が１１／２６という結果が得られる。
【０１３７】
すなわち、第１の実施例において最後に提示された警備確率は、参考例における最適化問題の解と一致している。参考例では、ターゲットの組み合わせとしてとり得る１５通りのターゲット部分集合Ｔｐについての最小カットの計算を行っているので、最適化問題の解（警備確率）は信頼性が高いといえる。したがって、第１の実施例で最後に提示された警備確率は、信頼性が高いといえる。
【０１３８】
また、上記参考例では最小カットを求める計算を１５回行うのに対し、第１の実施例では最小カットを求める計算が３回である。よって、第１の実施例では、最小カットを求める計算回数を少なくでき、かつターゲット部分集合Ｔｐの全ての組み合わせで最小カットを算出したときと同等の警備確率の信頼性を確保できる。特に、上記参考例では、ターゲットの数がｔ個である場合、ターゲット部分集合Ｔｐは２ｔ−１通りとなる。そのため、ターゲットの数が大きくなると最小カットの計算量が指数関数的に増加し、すなわち装置の処理負荷が増大する。
【０１３９】
また、参考例においては、最小カットを計算するターゲット部分集合Ｔｐの数を少なくした場合、警備する上で重要となる部分集合が含まれない可能性がある。そのような状況で最適化問題を解いた場合、上記とは違った最適解が得られ、警備員を効果的に配置できない恐れがある。
【０１４０】
これに対し、本実施形態では、最も危険度が高いターゲットに着目して最小カットの計算及び最適化問題の計算を行い当該ターゲットの危険度を低くする、という処理を繰り返す。そのため、警備する上で重要となる危険度が高いターゲットの選出漏れを防ぎ、よい警備配置を提示することができる。
【０１４１】
［第２の実施例］
図１４は、第２の実施例における各ターゲットの危険度の計算結果を示す模式図である。図１５は、第２の実施例における１回目のステップＳ４の処理の結果を示す模式図である。
【０１４２】
第２の実施例では、算出した最小カットのパターンが複数ある場合にターゲットの集合Ｔ’側に含まれる頂点Ｖの数が最少となる最小カットを選出するという条件でステップＳ４の処理を行ったときの途中経過及び最終結果を説明する。
【０１４３】
第２の実施例においても、図１の警備グラフ１００に対し１回目のステップＳ３の処理を行う時点では、警備計画Ｘは空集合であり警備確率ｘの情報がない。
【０１４４】
したがって、１回目のステップＳ３の処理で算出される各ターゲットの危険度は、図１４に示すように、それぞれ２．０００（Ｖ２８），４．０００（Ｖ３２），５．０００（Ｖ３７），及び３．０００（Ｖ４６）となる。よって、１回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３７｝になる。
【０１４５】
そのため、次のステップＳ４の処理では、頂点Ｖ３７をソースの集合Ｓ＝｛Ｖ１，Ｖ２，Ｖ３，Ｖ４，Ｖ８｝から分離する最小カットを算出する。このときの最小カットの大きさは、第１の実施例で説明したように４となる。よって、第２の実施例では、大きさが４であり、頂点Ｖ３７側に含まれる頂点の数が最少となる最小カットを選出する。すなわち、第２の実施例では、図１５に示す閉曲線Ｌ２０１で表される、頂点Ｖ３７のみをソースの集合Ｓから分離する最小カットが選出される。
【０１４６】
また、ステップＳ４では、算出した最小カットを表す閉曲線Ｌ２０１が横切る辺を集合Ｅ’に追加する。図１５に示した例において閉曲線Ｌ２０１が横切る辺は、Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，及びＥ３７,４４である。よって、１回目のステップＳ４の処理の結果、集合Ｅ’に上記の４本の辺Ｅの組ｅ１（＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝）が追加される。
【０１４７】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７の処理が行われる。
【０１４８】
１回目のステップＳ６では、警備グラフ１００を閉曲線Ｌ２０１で２つの領域に分割し、図７Ｂに示すように、分割した２つの領域をそれぞれ頂点Ｖ’１，Ｖ’２とする警備領域グラフ１５０を生成する。なお、第２の実施例で生成される警備領域グラフ１５０では、辺ｅ１の要素が図７Ｂに示した例とは異なり、ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝となる。また、第２の実施例で生成される警備領域グラフ１５０では、図７Ｂにおける閉曲線Ｌ１０１が閉曲線Ｌ２０１となる。
【０１４９】
第２の実施例の警備領域グラフ１５０における他の条件、侵入者が頂点Ｖ’２に到達した場合の損失Ｕπ、辺ｅ１の重みＣｅ１、及び警備員の数ｋは、第１の実施例と同じである。そのため、第２の実施例においても、１回目のステップＳ７において上記の式（２）で表される最適化問題を解くと、図７Ｂに示したように、警備確率ｘｅ１は３／４となる。
【０１５０】
また、上記のように、第２の実施例における１回目の処理では、最も危険度が大きいターゲット側に含まれるターゲットは、頂点Ｖ３７のみである。
【０１５１】
したがって、１回目のステップＳ７の処理の結果、警備計画Ｘは、例えば、下記の式（８−１）〜（８−３）で表されるような情報に更新される。
【０１５２】
Ｘ＝｛Ｘ１｝  ・・・（８−１）
Ｘ１＝｛３／４，ｅ１，Ｖ３７｝  ・・・（８−２）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝  ・・・（８−３）
【０１５３】
こうして１回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、２回目の処理を開始する。
【０１５４】
図１６は、第２の実施例における２回目のステップＳ４の処理の結果を示す模式図である。
【０１５５】
２回目のステップＳ３の処理を行う時点では、４個のターゲットのうちの頂点Ｖ３７と対応付けされた警備確率ｘｅ１（＝３／４）が警備計画Ｘに格納されている。そのため、２回目のステップＳ３の処理で各ターゲットの危険度を算出すると、頂点Ｖ３７の危険度のみが低下し、図１４に示すように、２．０００（Ｖ２８），４．０００（Ｖ３２），１．２５０（Ｖ３７），及び３．０００（Ｖ４６）となる。よって、２回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３２｝になる。
【０１５６】
頂点Ｖ３２をソースの集合Ｓから分離する最小カットの大きさは、第１の実施例で説明したように３である。そのため、２回目のステップＳ４の処理では、図１６に示した閉曲線Ｌ２０２で表される、頂点Ｖ３２をソースの集合Ｓから分離する最小カットが選出される。よって、閉曲線Ｌ２０２が横切る３本の辺の組ｅ２（＝｛Ｅ２９,３２，Ｅ３１,３２，Ｅ３２,３３｝）が集合Ｅ’に追加される。すなわち、集合Ｅ’は、下記の式（９−１）〜（９−３）で表される情報に更新される。
【０１５７】
Ｅ’＝｛ｅ１，ｅ２｝  ・・・（９−１）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝  ・・・（９−２）
ｅ２＝｛Ｅ２９,３２，Ｅ３１,３２，Ｅ３２,３３｝  ・・・（９−３）
【０１５８】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７が行われる。
【０１５９】
２回目のステップＳ６の処理では、式（９−１）〜（９−３）で表される情報に基づき、図８Ｂに示したような３個の頂点Ｖ’１，Ｖ’２，Ｖ’３、及び２本の辺ｅ１，ｅ２からなる警備領域グラフ１５１が生成される。なお、第２の実施形態で生成される警備領域グラフ１５１では、辺ｅ１，ｅ２の要素が図７Ｂに示した例とは異なり、それぞれ式（９−２），（９−３）で表される。
【０１６０】
第２の実施例の警備領域グラフ１５０における他の条件、侵入者が頂点Ｖ’２に到達した場合の損失Ｕπ、頂点Ｖ’３に到達した場合の損失Ｕπ、辺ｅ１の重みＣｅ１、辺ｅ２の重みＣｅ２、及び警備員の数ｋは、第１の実施例と同じである。そのため、第２の実施例においても、２回目のステップＳ７において上記の式（２）で表される最適化問題を解くと、図８Ｂに示したように、辺ｅ１の警備確率ｘｅ１は１５／３１となる。また、辺ｅ２の警備確率ｘｅ２は１１／３１となる。
【０１６１】
したがって、２回目のステップＳ７の処理の結果、警備計画Ｘは、例えば、下記の式（１０−１）〜（１０−５）で表されるような情報に更新される。
【０１６２】
Ｘ＝｛Ｘ１，Ｘ２｝  ・・・（１０−１）
Ｘ１＝｛１５／３１，ｅ１，Ｖ３７｝  ・・・（１０−２）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝      ・・・（１０−３）
Ｘ２＝｛１１／３１，ｅ２，Ｖ３２｝  ・・・（１０−４）
ｅ２＝｛Ｅ２９,３２，Ｅ３１,３２，Ｅ３２,３３｝  ・・・（１０−５）
【０１６３】
こうして２回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、３回目の処理を開始する。
【０１６４】
図１７Ａは、第２の実施例における３回目のステップＳ４の処理の結果を示す模式図である。図１７Ｂは、第２の実施例における３回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。なお、図１７Ｂには、図１７Ａに示した閉曲線Ｌ２０１，Ｌ２０２，Ｌ２０３の一部分のみを示している。
【０１６５】
３回目のステップＳ３の処理を行う時点では、頂点Ｖ３７と対応付けされた警備確率ｘｅ１（＝１５／３１）、及び頂点Ｖ３２と対応付けされた警備確率ｘｅ２（＝１１／３１）が警備計画Ｘに格納されている。そのため、３回目のステップＳ３の処理で各ターゲットの危険度を算出すると、図１４に示すように、２．０００（Ｖ２８），２．５８１（Ｖ３２），２．５８１（Ｖ３７），及び３．０００（Ｖ４６）となる。よって、３回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ４６｝になる。
【０１６６】
図１７Ａから明らかなように、頂点Ｖ４６をソースの集合Ｓから分離する最小カットの大きさは２である。そのため、３回目のステップＳ４の処理では、閉曲線Ｌ２０３で表される、頂点Ｖ４６のみをソースの集合Ｓから分離する最小カットが選出される。そして、閉曲線Ｌ２０３が横切る２本の辺の組ｅ３（＝｛Ｅ３６,４６，Ｅ４６,４７｝）が集合Ｅ’に追加される。すなわち、集合Ｅ’は、下記の式（１１−１）〜（１１−４）で表される情報に更新される。
【０１６７】
Ｅ’＝｛ｅ１，ｅ２，ｅ３｝  ・・・（１１−１）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝  ・・・（１１−２）
ｅ２＝｛Ｅ２９,３２，Ｅ３１,３２，Ｅ３２,３３｝  ・・・（１１−３）
ｅ３＝｛Ｅ３６,４６，Ｅ４６,４７｝  ・・・（１１−４）
【０１６８】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７が行われる。
【０１６９】
３回目のステップＳ６の処理を行うとき、集合Ｅ’の要素は、上記のように閉曲線Ｌ２０１が横切る辺の組を表すｅ１、閉曲線Ｌ２０２が横切る辺の組を表すｅ２、及び閉曲線Ｌ２０３が横切る辺の組を表すｅ３の３つである。そのため、３回目のステップＳ６の処理では、警備グラフ１００を閉曲線Ｌ２０１，Ｌ２０２，Ｌ２０３で４つの領域に分割し、図１７Ｂに示すように、分割した４つの領域をそれぞれ頂点Ｖ’１，Ｖ’２，Ｖ’３，Ｖ’４とする警備領域グラフ１５５を生成する。
【０１７０】
警備領域グラフ１５５では、４個の頂点のうち、３本の辺ｅ１，ｅ２，ｅ３が接続している頂点Ｖ’１はソースの集合Ｓを表す。また、頂点Ｖ’１と辺ｅ１で接続している頂点Ｖ’２は警備グラフ１００における頂点Ｖ３７を表しているので、侵入者が到達した場合の損失Ｕπは５であり、辺ｅ１の重みＣｅ１は４である。また、頂点Ｖ’１と辺ｅ２で接続している頂点Ｖ’３は警備グラフ１００における頂点Ｖ３２を表しているので、侵入者が到達した場合の損失Ｕπは４であり、辺ｅ２の重みＣｅ２は３である。また、頂点Ｖ’１と辺ｅ３で接続している頂点Ｖ’４は警備グラフ１００における頂点Ｖ４６を表しているので、侵入者が到達した場合の損失Ｕπは３であり、辺ｅ３の重みＣｅ３は２である。
【０１７１】
このような条件に警備員の数ｋ＝３を加え、上記の式（２）で表される最適化問題を解くと、図１７Ｂに示したように、辺ｅ１の警備確率ｘｅ１が６１／１３３、辺ｅ２の警備確率ｘｅ２が４３／１３３、辺ｅ３の警備確率ｘｅ３が１３／１３３という結果が得られる。
【０１７２】
したがって、２回目のステップＳ７の処理では、例えば、下記の式（１２−１）〜（１２−７）で表されるような情報に警備計画Ｘを更新する。
【０１７３】
Ｘ＝｛Ｘ１，Ｘ２，Ｘ３｝  ・・・（１２−１）
Ｘ１＝｛６１／１３３，ｅ１，Ｖ３７｝  ・・・（１２−２）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝  ・・・（１２−３）
Ｘ２＝｛４３／１３３，ｅ２，Ｖ３２｝  ・・・（１２−４）
ｅ２＝｛Ｅ２９,３２，Ｅ３１,３２，Ｅ３２,３３｝  ・・・（１２−５）
Ｘ３＝｛１３／１３３，ｅ３，Ｖ４６｝  ・・・（１２−６）
ｅ３＝｛Ｅ３６,４６，Ｅ４６,４７｝  ・・・（１２−７）
【０１７４】
こうして３回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、４回目の処理を開始する。
【０１７５】
図１８Ａは、第２の実施例における４回目のステップＳ４の処理の結果を示す模式図である。図１８Ｂは、第２の実施例における４回目のステップＳ６，Ｓ７の処理の結果を示す模式図である。なお、図１８Ｂには、図１８Ａに示した閉曲線Ｌ２０１〜Ｌ２０４の一部分のみを示している。
【０１７６】
４回目のステップＳ３の処理を行う時点では、頂点Ｖ３７と対応付けされた警備確率ｘｅ１（＝６１／１３３）、頂点Ｖ３２と対応付けされた警備確率ｘｅ２（＝４３／１３３）、及び頂点Ｖ４６と対応付けされた警備確率ｘｅ３（＝１３／１３３）が警備計画Ｘに格納されている。そのため、４回目のステップＳ３の処理で算出される各ターゲットの危険度は、図１４に示すように、２．０００（Ｖ２８），２．７０７（Ｖ３２），２．７０７（Ｖ３７），及び２．７０７（Ｖ４６）となる。よって、４回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３２，Ｖ３７，Ｖ４６｝になる。
【０１７７】
そのため、４回目のステップＳ４の処理では、３個の頂点Ｖ３２，Ｖ３７，Ｖ４６をソースの集合Ｓから分離する最小カットを算出する。詳細な説明は省略するが、頂点Ｖ３２，Ｖ３７，Ｖ４６をソースの集合Ｓから分離する最小カットは、大きさが６であり、かつ複数のパターンがある。そして、ステップＳ４では、集合Ｔ’側に含まれる頂点の数が最少となる最小カットとして、図１８Ａに示した閉曲線Ｌ２０４で表される、６本の辺Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４０,４９，Ｅ１５,２０，及びＥ１６,２２をカットする最小カットが選出される。
【０１７８】
また、ステップＳ４では、閉曲線Ｌ２０４が横切る６本の辺の組ｅ４（＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４０,４９，Ｅ１５,２０，Ｅ１６,２２｝）が集合Ｅ’に追加される。すなわち、集合Ｅ’は、下記の式（１３−１）〜（１３−５）で表される情報に更新される。
【０１７９】
Ｅ’＝｛ｅ１，ｅ２，ｅ３，ｅ４｝  ・・・（１３−１）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝  ・・・（１３−２）
ｅ２＝｛Ｅ２９,３２，Ｅ３１,３２，Ｅ３２,３３｝  ・・・（１３−３）
ｅ３＝｛Ｅ３６,４６，Ｅ４６,４７｝  ・・・（１３−４）
ｅ４＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４０,４９，Ｅ１５,２０，Ｅ１６,２２｝
・・・（１３−４）
【０１８０】
したがって、次のステップＳ５の判定は「Ｙｅｓ」となり、続けてステップＳ６，Ｓ７が行われる。
【０１８１】
４回目のステップＳ６の処理を行うとき、集合Ｅ’の要素は、閉曲線Ｌ２０１が横切る辺の組を表すｅ１、閉曲線Ｌ２０２が横切る辺の組を表すｅ２、閉曲線Ｌ２０３が横切る辺の組を表すｅ３、及び閉曲線Ｌ２０４が横切る辺の組を表すｅ４の４個である。そのため、４回目のステップＳ６の処理では、警備グラフ１００を閉曲線Ｌ２０１，Ｌ２０２，Ｌ２０３，Ｌ２０４で５つの領域に分割し、図１８Ｂに示すように、分割した５つの領域をそれぞれ頂点Ｖ’１，Ｖ’２，Ｖ’３，Ｖ’４，Ｖ’５とする警備領域グラフ１５６を生成する。
【０１８２】
警備領域グラフ１５６において、５個の頂点のうち４本の辺ｅ１，ｅ２，ｅ３，ｅ４が接続している頂点Ｖ’５は、ソースの集合Ｓ、頂点Ｖ３７，Ｖ２８，Ｖ３２から分離された領域を表す。図１８Ａに示したように、警備グラフ１００における頂点Ｖ’５と対応する領域にはターゲット（Ｖ２８）がある。そのため、頂点Ｖ’５には損失Ｕπとして２が設定される。また、頂点Ｖ’５と辺ｅ４で接続している頂点Ｖ’１は、ソースの集合Ｓを表す。よって、頂点Ｖ’１に損失Ｕπは設定されない。また、頂点Ｖ’５と辺ｅ１で接続している頂点Ｖ’２は頂点Ｖ３７を表しているので、侵入者が頂点Ｖ’２に到達した場合の損失Ｕπは５であり、辺ｅ１の重みＣｅ１は４である。また、頂点Ｖ’５と辺ｅ２で接続している頂点Ｖ’３は頂点Ｖ３２を表しているので、侵入者が頂点Ｖ’３に到達した場合の損失Ｕπは４であり、辺ｅ２の重みＣｅ２は３である。また、頂点Ｖ’５と辺ｅ３で接続している頂点Ｖ’４は頂点Ｖ４６を表しているので、侵入者が頂点Ｖ’４に到達した場合の損失Ｕπは３となり、辺ｅ３の重みＣｅ２は２となる。
【０１８３】
このような条件に警備員の数ｋ＝３を加え、上記の式（２）で表される最適化問題を解くと、図１８Ｂに示したように、辺ｅ１の警備確率ｘｅ１が３／２６、辺ｅ３の警備確率ｘｅ４が１１／２６という結果が得られる。
【０１８４】
したがって、４回目のステップＳ７の処理では、例えば、下記の式（１４−１）〜（１４−５）で表されるような情報に警備計画Ｘを更新する。
【０１８５】
Ｘ＝｛Ｘ１，Ｘ４｝  ・・・（１４−１）
Ｘ１＝｛３／２６，ｅ１，Ｖ３７｝  ・・・（１４−２）
ｅ１＝｛Ｅ２４,３７，Ｅ３６,３７，Ｅ３７,３８，Ｅ３７,４４｝  ・・・（１４−３）
Ｘ４＝｛１１／２６，ｅ４，Ｖ２８，Ｖ３２，Ｖ３７，Ｖ４６｝  ・・・（１４−４）
ｅ４＝｛Ｅ１３,２３，Ｅ１７,２５，Ｅ３８,３９，Ｅ４０,４９，Ｅ１５,２０，Ｅ１６,２２｝  
・・・（１４−５）
【０１８６】
こうして４回目のステップＳ３〜Ｓ７の処理が終了すると、ステップＳ３に戻り、５回目の処理を開始する。
【０１８７】
５回目のステップＳ３の処理を行う時点では、頂点Ｖ３７と対応付けされた警備確率ｘｅ１（＝３／２６）、及び頂点Ｖ２８，Ｖ３２，Ｖ３７，Ｖ４６と対応付けされた警備確率ｘｅ４（＝１１／２６）が警備計画Ｘに格納されている。そのため、５回目のステップＳ３の処理で算出される各ターゲットの危険度は、図１４に示すように、１．１５４（Ｖ２８），２．３０８（Ｖ３２），２．３０８（Ｖ３７），及び１．３８５（Ｖ４６）となる。よって、５回目のステップＳ３の処理において最も危険度が大きいターゲットの集合Ｔ’は、Ｔ’＝｛Ｖ３２，Ｖ３７｝になる。
【０１８８】
すなわち、５回目のステップＳ４の処理では、第１の実施例における３回目のステップＳ４の処理と同様、２個の頂点Ｖ３２，Ｖ３７をソースの集合Ｓから分離する最小カットを算出する。第１の実施例で説明したように、２個の頂点Ｖ３２，Ｖ３７をソースの集合Ｓから分離する最小カットの大きさは６である。これは、第２の実施例における４回目の処理での最小カットの大きさと同じである。そのため、５回目のステップＳ４の処理では、４回目のときと同じ閉曲線Ｌ２０４で表される最小カットが選出される。よって、５回目のステップＳ４において集合Ｅ’に新たな要素が追加されることはない。したがって、ステップＳ５の判定は「Ｎｏ」となり、次にステップＳ８の処理が行われる。
【０１８９】
図１９は、第２の実施例における警備計画情報の表示例を示す模式図である。
ステップＳ８では、上記のように、警備グラフ１００に警備計画Ｘの情報（警備計画情報）を付加して表示装置４に表示させる。
【０１９０】
ステップＳ８の処理を行う時点での警備計画Ｘの情報は、４回目のステップＳ７の処理で更新した上記の式（１４−１）〜（１４−５）で表される情報である。このうち、式（１４−３）は、１回目のステップＳ４で算出した最小カットを表す閉曲線Ｌ２０１が横切る辺の組を表している。また、式（１４−５）は、４回目のステップＳ４で算出した最小カットを表す閉曲線Ｌ２０４が横切る辺の組を表している。
【０１９１】
よって、ステップＳ８では、図１９に示すように、閉曲線Ｌ２０１、Ｌ２０４を警備ラインとして警備グラフ１００に重ねた画像を表示装置４に表示させる。またこのとき、閉曲線Ｌ２０１の近傍には、閉曲線Ｌ２０１が横切る辺ｅ１に対する警備確率ｘｅ１（＝３／２６）を表示させる。同様に、閉曲線Ｌ２０４の近傍には、閉曲線Ｌ２０４が横切る辺ｅ４に対する警備確率ｘｅ４（＝１１／２６）を表示させる。
【０１９２】
図１９からわかるように、警備ライン（閉曲線Ｌ２０１，２０４）は、警備ラインで囲まれた領域の外側から領域内のターゲット（警備対象）に向かうことが可能な経路（辺）を横切る。加えて、警備ラインは、所定のターゲットをソースの集合Ｓから分離する際の最小カットに基づいて求めている。そのため、図１９に示した警備計画情報における警備ラインを見ることで、例えば頂点Ｖ３７，Ｖ４６等に対する警備員の効率的な配置であることを容易に把握することができる。
【０１９３】
また、式（２）で表される最適化問題を解いて警備ラインを特定すると、１本の警備ラインが横切る警備モデル１００のＣｅ本の辺が同じ警備確率ｘｅで選択される。そのため、警備ラインの近傍に警備確率（例えば３／２６，１１／２６等）を表示することにより、図１９に示した警備グラフ１００に対し３人の警備員をどのように配置すると効率的であるかが容易に把握できる。図１９に示した例では、閉曲線Ｌ２０１が横切る辺に警備員を配置する頻度が３／２６となり、閉曲線Ｌ２０４が横切る辺に警備員を配置する頻度が１１／２６となるように、３人の警備員の配置箇所を変えながら警備をすればよいことが容易にわかる。
【０１９４】
よって、第２の実施例によれば、警備員の配置箇所や、そこに警備員を配置するとよい理由を容易に把握でき、警備計画の妥当性を評価しやすくなる。
【０１９５】
更に、最も危険度が大きいターゲットの危険度を低下させるというルールに従って警備確率を求めているので、専門家等の第三者に妥当性の評価を依頼する場合にルールを簡単に説明できる。加えて、ルール自体が簡素であるため、専門家等の第三者も警備計画の妥当性を評価しやすい。
【０１９６】
しかも、最も危険度が大きいターゲットの危険度を低下させるというルールに従って警備確率を求めており、かつ最終的に提示される警備計画情報は、第１の実施例で提示される警備計画情報と類似している（図１０を参照）。そのため、計算量の増大による警備計画支援装置の処理負荷の増大を抑えることができる上、警備上重要となる点を見落とすことがない。
【０１９７】
以上説明したように、本実施形態に係る警備確率算出方法及び装置では、警備グラフにおいて最も危険度が高いターゲットとソースの集合Ｓとを分離する最小カットに基づいて警備確率を算出し、最小カットを表す線と及び警備確率を警備グラフと重ねて提示する。そのため、最小カットを表す線が横切る辺に、警備確率に従って警備員を配置すれば効率よく警備できることを直感的に把握することができる。
【０１９８】
また、最小カットを算出する毎に最小カットを表す線が横切る辺の組（最小カットセット）を集合Ｅ’に追加しながら最小カット及び警備確率の算出を繰り返し、集合Ｅ’に新たに追加される辺の組がなくなった時点で最小カット及び警備確率の算出を終了する。すなわち、最も危険度が高いターゲットとソースの集合とを分離する最小カットに変化が生じなくなった時点で、最小カットの算出及び警備確率の算出を終了する。そのため、ターゲットの部分集合として考え得る全ての組み合わせで最小カットを計算する場合に比べて最小カットの計算回数が少ないにもかかわらず、得られる警備確率等に大差がない。また、最も危険度が高いターゲットの危険度を低下させる処理を繰り返すため、ターゲットの部分集合として考え得る全ての組み合わせから任意の部分集合を選出したときのように、警備する上で重要な点が欠落することがない。そのため、本実施形態に係る警備確率算出方法及び装置によれば、警備計画支援装置の処理負荷（算出負荷）の増大を抑え、短時間で信頼性の高い警備計画情報を提示することができる。
【０１９９】
更に、警備グラフを最小カットで複数の領域に分割して各領域を新たな頂点とする警備領域グラフを生成し、当該警備領域グラフ上で警備確率についての最適化問題を解く。そのため、移動経路が複雑な警備グラフであっても頂点の数が少ない警備領域グラフに簡単化して最適化問題を解くことができる。加えて、最小カットで分離した場合、侵入者が侵入位置（ソース）から警備対象（ターゲット）に到達するためには、最小カットを表す線（警備ライン）が横切る辺のいずれかを通らなければならない。そのため、最小カットが横切る辺と対応する警備グラフの辺の警備確率についての最適化問題を解くことで、警備効率のよい配置箇所を選択的に抽出し警備確率の計算を行うことができる。よって、警備計画支援装置の処理負荷を軽減できる。
【０２００】
また、算出した最小カットが複数パターンある場合、いずれの最小カットを選ぶかは任意であり、予め定めた条件に従って選出すればよい。ただし、最小カットの計算回数を少なくするという観点では、第１の実施例のように、最も危険度が大きいターゲットをソースの集合Ｓから分離したときにターゲット側に含まれる頂点の数が最多になる最小カットを選出することが好ましい。また、最小カットが複数パターンある場合、例えば処理を中断して複数パターンの最小カットを警備グラフ１００に重ねて表示装置４に表示させ、オペレータに選択させても良い。
【０２０１】
また、本実施形態では、上記の式（２）で表される最適化問題を解き、警備領域グラフ（警備グラフ１００）の警備確率を算出する例を示した。しかしながら、本発明に係る警備計画支援方法及び装置では、これに限らず、例えば、警備領域グラフ上でターゲット側に前記侵入者が侵入する確率を算出して提示しても良いし、侵入する確率に基づいて警備確率を算出して提示しても良い。
【０２０２】
また、本実施形態では、警備グラフ１００を複数の領域に分割して各領域を新たな頂点とする警備領域グラフに簡単化し、警備領域グラフ上で警備確率を算出している。しかしながら、本発明は、これに限らず、他の方法で警備グラフ１００を簡単化し、簡単化した警備グラフ上で警備確率、あるいはターゲット側に侵入者が侵入する確率を算出してもよい。
【０２０３】
以上記載した各実施例を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
警備区域内における警備員の配置の決定を支援する警備計画支援方法であって、
前記警備区域内の移動経路を表す経路グラフにおいて侵入者の目標となる複数のターゲットのそれぞれについて、前記侵入者が該ターゲットに到達した際の損失の期待値を算出し、
前記経路グラフにて前記侵入者の侵入位置となる一又は複数の位置から前記損失の期待値が最大であるターゲットを分離する場合に前記経路グラフの辺を横切る数が最少となる警備ラインを特定し、
前記経路グラフ、前記警備ライン及び前記警備員の数に基づき、前記警備ラインの前記ターゲット側に前記侵入者が侵入する確率を算出する、
処理をコンピュータが実行することを特徴とする警備計画支援方法。
（付記２）
前記損失の期待値は、侵入者が前記ターゲットに到達したときの損失と、前記ターゲット側に前記侵入者が侵入する確率とに基づいて算出する、
ことを特徴とする付記１に記載の警備計画支援方法。
（付記３）
前記コンピュータが、
前記損失の期待値を算出する処理、前記警備ラインを特定する処理、及び前記ターゲット側に前記侵入者が侵入する確率を算出する処理を繰り返すとともに、
前記警備ラインを特定する毎に該警備ラインの情報を蓄積し、
特定した警備ラインの情報が既に蓄積された情報と一致すると、最後に警備ラインを特定した時点における前記ターゲット側に前記侵入者が侵入する確率に応じた該警備ラインの警備確率を出力する、
処理を実行することを特徴とする付記２に記載の警備計画支援方法。
（付記４）
前記警備ラインの情報として、前記経路グラフにおいて前記警備ラインが横切る辺の集合を蓄積する、
ことを特徴とする付記３に記載の警備計画支援方法。
（付記５）
前記経路グラフの辺を横切る数が最少となるラインが複数パターンある場合、予め定めた条件に従って１つのラインを選出して前記警備ラインに特定する、
ことを特徴とする付記１に記載の警備計画支援方法。
（付記６）
前記経路グラフの辺を横切る数が最少となるラインが複数パターンある場合、前記ターゲットを前記侵入位置から分離したときに前記ターゲット側に含まれる頂点の数が最多となるラインを前記警備ラインに特定する、
ことを特徴とする付記１に記載の警備計画支援方法。
（付記７）
前記警備ラインと、前記ターゲット側に前記侵入者が侵入する確率に応じた前記警備ラインの警備確率とを前記経路グラフに重ねて出力する、
ことを特徴とする付記１に記載の警備計画支援方法。
（付記８）
前記コンピュータが、
前記警備ラインを特定する毎に前記警備ラインの情報を蓄積し、
前記蓄積した警備ラインの情報に基づいて前記経路グラフを複数の領域に分割して、各領域を頂点とし、前記領域の隣接関係に基づいて前記頂点同士を辺で接続した警備領域グラフを生成し、
前記警備領域グラフ上で、前記経路グラフにおける侵入位置を含む領域と対応する頂点から前記経路グラフにおけるターゲットを含む領域と対応する頂点に前記侵入者が侵入する確率を算出する、
ことを特徴とする付記１に記載の警備計画支援方法。
（付記９）
侵入者が前記ターゲットに到達した場合の損失に基づき、前記警備領域グラフにおける前記ターゲットを含む領域と対応する頂点に前記侵入者が侵入した場合の損失を設定し、
前記警備領域グラフにおける各辺に、該辺で接続された２つの頂点と対応する前記経路グラフの領域を分離する警備ラインが横切る辺の数を対応付け、
前記警備領域グラフ、前記頂点に侵入者が侵入した場合の損失、前記辺に対応付けた前記辺の数、及び配置する警備員の数を用いて、前記ターゲットを含む頂点に前記侵入者が侵入する確率を最小にする、
ことを特徴とする付記８に記載の警備計画支援方法。
（付記１０）
警備区域内における警備員の配置の決定を支援する警備計画支援装置であって、
前記警備区域内の移動経路を表す経路グラフにおいて侵入者の目標となる複数のターゲットのそれぞれについて、前記侵入者が該ターゲットに到達した際の損失の期待値を算出する損失期待値算出部と、
前記経路グラフにて前記侵入者の侵入位置となる一又は複数の位置から前記損失の期待値が最大であるターゲットを分離する場合に前記グラフの辺を横切る数が最少となる警備ラインを特定する警備ライン特定部と、
前記経路グラフ、前記警備ライン、及び前記警備員の数に基づき、前記警備ラインの前記ターゲット側に前記侵入者が侵入する確率を算出する確率算出部と、
を備えることを特徴とする警備計画支援装置。
（付記１１）
前記警備ラインの情報を蓄積する記憶部と、
前記警備ラインを特定する毎に、特定した前記警備ラインの情報と前記記憶部に蓄積された警備ラインの情報とを比較し、特定した前記警備欄の情報と一致する情報が前記記憶部にあるかを判定する判定部と、を更に備え、
特定した前記警備ラインの情報と一致する情報が前記記憶部にない場合には該警備ラインの情報を記憶部に追加し、
特定した前記警備ラインの情報と一致する情報が前記記憶部にある場合には最後に前記警備ラインを特定した時点における前記ターゲット側に前記侵入者が侵入する確率を出力する、
ことを特徴とする付記１０に記載の警備計画支援装置。
（付記１２）
前記警備ラインにより前記経路グラフを複数の領域に分割して、各領域を頂点とし、前記領域の隣接関係に基づいて前記頂点同士を辺で接続した警備領域グラフを生成する警備領域グラフ生成部、を更に備え、
前記確率算出部は、前記警備領域グラフ上で、前記経路グラフにおける侵入位置を含む領域と対応する頂点から前記経路グラフにおけるターゲットを含む領域と対応する頂点に前記侵入者が侵入する確率を算出する、
ことを特徴とする付記１０に記載の警備計画支援装置。
（付記１３）
警備区域内の移動経路を表す経路グラフにおいて侵入者の目標となる複数のターゲットのそれぞれについて、前記侵入者が該ターゲットに到達した際の損失の期待値を算出し、
前記経路グラフにて前記侵入者の侵入位置となる一又は複数の位置から前記損失の期待値が最大であるターゲットを分離する場合に前記経路グラフの辺を横切る数が最少となる警備ラインを特定し、
前記経路グラフ、前記警備ライン、及び前記警備員の数に基づき、前記警備ラインの前記ターゲット側に前記侵入者が侵入する確率を算出する、
処理をコンピュータに実行させるためのプログラム。
【符号の説明】
【０２０４】
１００  警備グラフ
１５０，１５１，１５２，１５３，１５５，１５６，１６０  警備領域グラフ
２  警備計画支援装置
２０１  入力情報受付部
２０２  警備グラフ生成部
２０３  警備計画情報生成部
２０３ａ  危険度算出部
２０３ｂ  最小カット算出部
２０３ｃ  判定部
２０３ｄ  警備領域グラフ生成部
２０３ｅ  警備確率算出部
２０４  表示制御部
２０５  経路情報記憶部
６  コンピュータ
６０１  プロセッサ
６０２  主記憶装置
６０２ａ  ＲＯＭ
６０２ｂ  ＲＡＭ
６０３  補助記憶装置
６０４，３  入力装置
６０５，４  表示装置
６０６  記憶媒体駆動装置
６０７  通信インタフェース
【図１】
0006572553.tif 000003
【図２】
0006572553.tif 000004
【図３】
0006572553.tif 000005
【図４】
0006572553.tif 000006
【図５Ａ】
0006572553.tif 000007
【図５Ｂ】
0006572553.tif 000008
【図６】
0006572553.tif 000009
【図７Ａ】
0006572553.tif 000010
【図７Ｂ】
0006572553.tif 000011
【図８Ａ】
0006572553.tif 000012
【図８Ｂ】
0006572553.tif 000013
【図９Ａ】
0006572553.tif 000014
【図９Ｂ】
0006572553.tif 000015
【図１０】
0006572553.tif 000016
【図１１】
0006572553.tif 000017
【図１２】
0006572553.tif 000018
【図１３Ａ】
0006572553.tif 000019
【図１３Ｂ】
0006572553.tif 000020
【図１４】
0006572553.tif 000021
【図１５】
0006572553.tif 000022
【図１６】
0006572553.tif 000023
【図１７Ａ】
0006572553.tif 000024
【図１７Ｂ】
0006572553.tif 000025
【図１８Ａ】
0006572553.tif 000026
【図１８Ｂ】
0006572553.tif 000027
【図１９】
0006572553.tif 000028