搜索路径给定时的搜索对策问题及其应用*

王天虹，宋业新，薛洪展

（海军工程大学理学院，武汉 430033）

搜索路径给定时的搜索对策问题及其应用*

王天虹，宋业新，薛洪展

（海军工程大学理学院，武汉 430033）

搜索路径给定时的最优搜索方案问题，也可以理解为是关于搜索者和目标的二人对策问题，主要讨论了当搜索路径给定时的单个搜索者和单个目标的搜索对策问题。首先根据问题的特点，利用动态规划和迭代的方法，确定关于目标逃逸路径混合策略的最优分区，证明该分区是多面体凸集；针对目标不同逃逸路径的分区，求出搜索者的最大期望收益，再将问题转化为二人有限零和对策，计算出搜索者的支付矩阵，确定最优搜索策略。最后结合海军护航行动，对我舰载直升机搜索小型海盗船进行分析和计算，说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值。

搜索对策，动态规划，迭代，最优搜索策略

Abstract：A searcher is given a search path in advance and a target selects a path from some options.In this paper we consider the search problem，describe our model and formulate it.Based on the two-person zero-sum strategies and the search theory，we discuss the search game with a single searcher and a single target when the search path is given in advance.The target selects an escape path from some options.Firstly，according to the characteristics of the problem，using the dynamic programming and the iterative approach，the searcher gains a value on the detection of the target but expends search cost by the look.A pay-off function of the game for the searcher is the expected reward which is defined as the expected value minus the expected search cost.Then the most optimal search strategy is determined.Finally，the method is combined with the helicopter searching the small pirate ships in the naval practical action，the study results do have the military application value for resource distribution and improving searching effectiveness.

Key words：search game，dynamic programming，iteration，optimal search strategies

0 引言

许多学者针对移动目标的最优搜索问题进行了研究，包括 Stone（1975）、Stewart（1980）、Eagle 和Yee（1990）等研究了搜索路径给定时的搜索问题（PCSP）。有些学者提出使用分支——定界法求解某些PCSP类问题。Hohzaki和Iida（1995）综合考虑搜索成本，建立了一个期望收益模型。这些都是当搜索路径给定时的最优搜索方案问题，也可以理解为是关于搜索者和目标的二人对策问题。Danskin（1968）把发现目标的概率作为标准，在目标的具体搜索和躲避之间给出了平衡点。Washburn（1980）提出在搜索过程中搜索者和目标轮流选择他们在搜索区域中所处的即时位置。

本文考虑搜索路径给定的搜索问题，搜索者可以在当前所处位置决定对目标进行即时搜索与否的随机策略，同时目标可以在一些路径中选择某条路径逃逸。我们利用动态规划和迭代的方法，针对目标不同逃逸路径的分区，求出搜索者的最大期望净收益，再把问题转化为二人有限零和对策，计算出支付矩阵，确定最优搜索策略。

1 问题的描述与说明

可以利用T维的0-1向量表示搜索者在T个时间点是否搜索，所有T维的0-1向量组成了一个搜索策略集合2T。例如搜索策略分别表示搜索者在时间点时搜索，不搜索，不搜索，…，其中1表示搜索，0表示不搜索。设E（t）表示搜索策略E在时间点t搜索与否的函数，可令

可以定义关于E（t）的指示函数

定理1

证利用数学归纳法进行证明。

即在 t=1的情况下式（2）成立，假设式（2）从 2到t-1均成立，

式（2）得证。

如果搜索者在时间间隔[1，t]内搜索到目标，搜索者获得搜索收益V（t），也需花费累计的搜索成本。如果搜索者在时间间隔[1，T]内没有搜索到目标，那么它就只损失累计成本。当搜索者选择搜索策略φ和目标选择逃逸路径时，在时间间隔[1，T]内，搜索者的期望支付函数为

这个支付函数也可以转换为如下形式：

定理2

证 由式（2），当 t≤T 有

当 t＜T 时

将式（9）和式（11）代入式（3）

式（4）得证。

2 搜索对策问题

建立下列动态规划问题

在k时期初，搜索者执行搜索，获得的最大收益为gk（π）

对于目标的任意策略π，均可相应计算出搜索者的最优搜索策略

引理1 每个最优π分区是一个多面体凸集。

证：假设在一个最优π分区∏中目标选择两条不同的逃逸路径π1和π2，此时搜索者的最优搜索策略是φ*。当搜索者选择搜索策略φ、目标选择逃逸策略π，在时间段或者[k，1]时间段，根据式（3）可以计算出

下面用数学归纳法证明两个最优π分区之间的边界是超平面。根据式（13），当k=1时，有

3 搜索对策问题的求解

对于支付函数

在特殊的情况下，有以下的引理。

根据引理1可知，最优π分割区域是凸多面体，fT（π）是关于π的线性函数。因此，利用式（15）和求解对应的线性规划问题，可以确定搜索者和目标的最优混合策略。

4 算例

搜索路径给定的最优搜索问题在军事、执法和安全领域中均得到不同程度的应用，如在飞机的监视搜索任务中，飞机按计划路线巡逻，并且监视着商业和军事船只。随着我海军舰艇编队在亚丁湾海域护航的常态化，如何及时发现机动灵活的小型海盗船已迫切成为我海军的一项重要任务。

可以我军舰载直升机和小型海盗船作为搜索者和目标，假定离散的搜索小区域和离散的时间点，小型海盗船有3个可供选择的逃逸路径，分别为：，。舰载直升机的预定搜索路径为，如图1所示。

图1 搜索者的搜索路径和目标的逃逸路径

下面的参数被设定为常数：

应用动态规划式（14）来解决这个问题，可以计算出该问题的最优π分区（如图2所示），其中横轴代表π（1），纵轴代表π（2），。二维π空间集合是一个由3个不等式：；包围的区域，并且被分割成4个最优π区域。在每个最优π分区中，最优搜索策略和fT（π）的计算结果如表1所示。

图2 最优π分区

表1最优π分区的最优搜索策略和fT（π）

该对策问题不存在最优纯策略，计算出搜索者的最优混合策略为

5 结论

算例的分析和计算过程，说明搜索路径给定时的最优搜索对策对于双方的资源分配和提高搜索效率具有一定的应用价值，并结合我海军护航的实际行动，为我舰载直升机搜索小型海盗船提供了理论支持和比较有效的解决方法。

搜索路径给定时的最优搜索对策问题在军事领域的其他方面也有一定的应用价值，例如两军交战的很多情形也可以利用搜索对策来描述，最优搜索对策问题的理论研究还有较大的发展空间。

［1］LAWRENCE D S.Theory of optimal search［M］.New York：Academic Press，1975.

［2］STEWART T J.Experience with a branch-and-bound algorithm for constrainted searcher motion［J］.Search Theory and Applications，1980：247-253.

［3］EAGLE J N，YEE J R.An optimal branch-and-bound procedure for the constrainted path moving target search problem［J］.Operarions Research，1990，38：110-114.

［4］RYUSUKE H，KOJI I.Path constrainted search problem with reward criterion［J］.Journal of the Operational Research Society of Japan，1995，38：254-264.

［5］RYUSUKE H，KOJI I.A search game when a search path is given［J］.European Journal of Operational Research，2000，124：114～124.

［6］THOMAS P.Oléron E，STEVEN R B.Static search games played over graphs and general metric spaces［J］.European Journal of Operational Research，2013：667–689.

［7］李维铮，李德，郑大本.运筹学［M］.北京：清华大学出版社，2006.

［8］汪贤裕，肖玉明.博弈论及其应用［M］.北京：科学出版社，2008.

［9］肖增博，雷虎民.多导弹协同攻击对策制导规律研究［J］.弹箭与制导学报，2010，30（5）：32-34.

［10］王天虹，宋业新，戴明强.模糊模式识别的应急军事物流效益评估方法 ［J］. 火力与指挥控制，2013，38（11）：36-39.

［11］沈东，魏瑞轩，茹常剑.基于数字信息素的无人机集群搜索控制方法［J］.系统工程与电子技术，2013，35（3）：591-596.

［12］薛洪展，宋业新.具有多条搜索路线和有限个搜索概率的舰潜搜索对策问题研究［J］.兵器装备工程学报，2016，37（2）：15-17.

Search Game and Application When a Search Path Given

WANG Tian-hong，SONG Ye-xin，XUE Hong-zhan
（School of Science，Naval Univ ersity of Engineering，Wuhan 430033，China）

E99；V247

A

10.3969/j.issn.1002-0640.2017.09.021

1002-0640（2017）09-0098-05

2016-06-17

2016-08-29

国家自然科学基金资助项目（71171198）

王天虹（1974- ），女，湖北咸宁人，博士研究生，讲师。研究方向：系统运筹与控制决策。