具有多条搜索路线和有限个搜索概率的舰潜搜索对策问题研究

薛洪展，宋业新

(海军工程大学理学院，武汉　430033)



具有多条搜索路线和有限个搜索概率的舰潜搜索对策问题研究

薛洪展，宋业新

(海军工程大学理学院，武汉430033)

摘要：舰潜搜索是海上作战巡逻中的重要问题，针对舰潜搜索在海上巡逻中的一些实际情况，描述一个军舰具有多条搜索路线作为选择，并在所述位置区域存在有限个搜索概率的搜索对策问题，以军舰和潜艇的搜索路径选择为双方策略，根据舰艇巡逻的期望值即期望收益减去搜索成本，建立支付函数，进而建立舰潜搜索的矩阵对策模型，得到搜索双方的最优搜索策略，并通过例子，证明所述方法的有效性。

关键词：舰潜搜索；搜索对策；对策论

Citation format:XUE Hong-zhan, SONG Ye-xin.Research on Problem of Search Game with Multiple Search Routes and Limited Search [J].Journal of Ordnance Equipment Engineering,2016(2):15-17.

搜索对策理论是军事运筹学的两个重要分支搜索论和对策论结合而产生的一个新的军事运筹学分支。关于搜索对策的有关研究，文献[1]论述了关于对移动目标的搜索的搜索力量最优分配，文献[2-3]论述了运用分支定界的方法分析搜索者移动路线受限的问题，称为路线限制搜索问题(PCSP)，文献[4]论述了搜索路线的复杂性，并证明了路线限制搜索问题(PCSP)的NP完全性，文献[5]论述了在搜索空间内目标隐藏且目标不移动的SSSG问题，文献[6]论述了考虑搜索者在搜索过程中获得收益但也存在搜索成本的模型，文献[7]用分支定界的方法获得在给定路线上搜索者在所处位置是否进行搜索的最优策略，以上文献分别进行了搜索对策中有关搜索力量分配、搜索路线限制、搜索成本以及搜索概率方面的研究，研究的都是搜索对策某一方面的问题。文献[8]论述搜索者在搜索过程中受到被搜索者所处环境的影响，并且搜索概率和搜索位置相关,被搜索者在移动到不同位置时要考虑该位置的风险，文献[9]论述了搜索者搜索路线给定，搜索概率作为搜索者的随机策略，并运用动态规划进行优化求解。本文在文献[9]给定一条路线的基础上，论述搜索者有多条搜索路线并存在有限个搜索概率的舰潜搜索问题，以路线的选择为策略，针对路线不同，搜索概率以及搜索收益与搜索成本的影响，结合搜索对策的知识，建立了矩阵对策模型，进而得到双方的最优策略。并结合军事例子进行论述。

1具有多条搜索路线和有限个搜索概率的舰潜搜索对策

1.1舰潜搜索对策问题描述

假设有红、蓝两个海上舰艇编队进行对抗，设红方编队的潜艇准备潜入蓝方海域进行情报收集，在蓝方编队海域有军舰按作战计划进行海上巡逻，以防止红方的潜入。将双方的作战海域划分成离散的位置区域l∈A={1，2，…,k}，将时间离散为时间单元t∈B={1,…,h}，A×B构成红蓝双方的作战空间。

潜艇的路线集合为S1={J1,J2,…,Jn}，

军舰的路线集合为S2={R1,R2,…,Rm}

当潜艇选择路线Ji∈S1时，在t∈B时刻，潜艇的位置为Ji(t)∈{Ji(1),Ji(2),…,Ji(h)}；

当军舰选择路线Rj∈S2时，在t∈B时刻，军舰的位置为Rj(t)∈{Rj(1),Rj(2),…,Rj(h)}；

pl∈{p1,p2,…,pk}表示当军舰和潜艇在相同位置区域内，且军舰决定在此区域搜索时，潜艇被搜索到的概率；

VRj(t)表示当军舰选择路线Rj∈S2时，在t时刻搜索到潜艇所增加的收益。cRj(l,t)表示当军舰选择路线Rj∈S2时，由于t时刻在l区域进行搜索，消耗的搜索成本。

搜索行动在搜索到潜艇或搜索时间到达限制时间h时结束。军舰作为理性的一方要使其期望值最大化。

1.2舰潜搜索对策模型建立

1.2.1舰潜搜索对策策略集

本文以军舰和潜艇的路线选择确定策略集，军舰策略集为S2={R1,R2,…,Rm}，潜艇策略集为S1={J1,J2,…,Jn}。

1.2.2舰潜搜索对策模型的支付函数

本文以期望收益为标准，期望值为期望收益减去搜索成本，从而得到支付函数。

定义如下：

当军舰采用策略Rj∈S2，潜艇选择策略Ji∈S1时，在时间[1,h]上没有搜索到的概率为

军舰增加收益VRj(t)，消耗累积搜索成本

以期望值为支付函数的舰潜搜索对策构建出矩阵对策G={S2,S1;A},根据此矩阵对策得到军舰的最优策略。矩阵对策的解法有公式法、图解法、方程组法等，结合这些方法，解出矩阵对策的解，得到所求解。

2案例假定

此矩阵有鞍点(R1,J1)和(R1,J3)，可得军舰的最优策略为R1={2,2,2},期望收益为8，潜艇策略为J1,J3,关于结果的定性解释可以从图1得到一些。潜艇应避免选择和军舰相同的路线J2，以及和军舰相交过多的路线，这也使得军舰很难预料潜艇会选择那条路线。军舰在只考虑搜到潜艇的前提下，肯定是在所有位置都搜索，但本文考虑搜索成本，所以军舰必须结合成本、位置相交以及搜索概率综合考虑。

图1　路线图

3结论

在本文中，探讨了多条搜索路线、多个搜索概率的搜索问题，即军舰搜索路线有多条，并且在某一时刻的搜索概率不是固定的，潜艇有多条路线可选择。军舰在搜索潜艇时会获得收益也会花费搜索成本。采用期望收益即期望值减去期望的搜索成本作为此问题的标准。这个标准从花费成本方面考虑本问题，搜索者在搜索过程中，受到各方面因素的约束，从例子可以看出，相对搜索概率来说，路线的选择影响最大，本文考虑的问题贴合实际，具有一定的实用性。

参考文献：

[1]STONE L D.Theory of Optimal Search[M].New York,Academic Press,1975.

[2]EAGLE Y,YEE J R.An optimal branch-and-bound procedure for the constrained path moving target search problem[J].Operations Research,1990,38:110-114.

[3]STEWART T J.Experience with a branch-and-bound algorithm for constrained searcher motion[J].Search Theory and Applications,1984(10):247-253.

[4]TRUMMEL K E,WEISIGNER J R.The complexity of the optimal searcher path problem[J].Operations Research,1986(34):324-327.

[5]THOMAS P,STEVEN R B.Static search games played over graphs and general metric spaces[J].European Journal of Operational Research,2013(5):77-82.

[6]HOHZAKI R,LIDA K.Path constrained search problem with reward criterion[J].Journal of the Operations Research Society of Japan,1995(38):254-264.

[7]HOHZAKI R,LIDA K.An optimal search plan for a moving target when a search path is given[J].Mathematica Japonica,1995(41):175-184.

[8]MCCORMICK G H,OWEN G.Manhunting—A simple search game[J].International Game Theory Review,2010(23):239-308.

[9]HOHZAKI R,LIDA K.A search game when a search path is given[J].European Journal of Operational Research,1999,124(2000):114-124

(责任编辑周江川)

Research on Problem of Search Game with Multiple Search Routes and Limited Search

XUE Hong-zhan, SONG Ye-xin

(College of Science, Naval University of Engineering, Wuhan 430033, China)

Abstract:Submarine searching is a prime issue in submarine war patrol. One of the most common problems in a warship encounters in submarine is that the submarine has multiple searching routes and limited searching probabilities whose solution was explored in this essay. The author studied tactical behaviors of mutual searching routes and analyzed the functional relationship between the expected return and cost in submarine war patrols. A submarine searching matrix model was then built from where an optimal searching tactic was chosen. The validity and fidelity of the optimal searching tactic were tested against practical examples.

Key words:submarine search; search game; game theory

文章编号：1006-0707(2016)02-0015-03

中图分类号：O225

文献标识码：A

doi:10.11809/scbgxb2016.02.004

作者简介：薛洪展(1990—)，男，硕士研究生，主要从事军事系统建模与运筹决策研究；宋业新(1968—)，男，教授，博士生导师，主要从事军事系统建模、优化决策、对策理论研究。

基金项目：国家自然科学基金项目资助(71171198)

收稿日期：2015-06-16；修回日期：2015-07-05

本文引用格式：薛洪展，宋业新.具有多条搜索路线和有限个搜索概率的舰潜搜索对策问题研究[J].兵器装备工程学报，2016(2):15-17.

【装备理论与装备技术】