Search Games on Trees with Asymmetric Travel Times
Search Games on Trees with Asymmetric Travel Times
复制标题
搜索具有不对称旅行时间的树上的游戏
DOI：
10.1137/090781115
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Alpern
中科院分区：
文献类型：
--
作者：
S. Alpern
一个点H隐藏在一个根树Q中，该树被赋予节点之间的非对称距离（旅行时间）。我们确定随机搜索策略，从根开始，在最坏的情况下，最小化达到$H$的预期时间。这相当于一个零和搜索游戏$\Gamma\left（Q\right）$，最小化搜索者，最大化隐藏者，收益等于捕获时间。从搜索者的角度来看，最坏的隐藏分布（在叶子上）是这样的，在每个节点i$，每个分支的概率与从i$开始遍历它所需的最小时间成正比。最优随机搜索是深度优先搜索的混合。我们还简要地考虑了一些其他的网络和一个移动的隐藏的可能性。我们的具有不对称行进时间的公式概括了Gal [SIAM J. Control Optim.，17（1979年），第17页。99-122]的对称旅行时间，也搜索游戏的菊田[J。结果：38（1995），pp. 70-88]以及Kikuta和Ruckle [海军研究后勤师，41（1994），pp. 821-831]，他在每个节点$i$上设定了搜索成本$c_i$，并将其添加到旅行时间中以获得收益。我们还简要地考虑了如果我们允许Searcher（Hider）在任何叶子节点开始（隐藏）会发生什么。我们确定Dagan和Gal [Networks，52（2008），pp. 156-161]的对称版本，这样的游戏在我们的非对称背景下举行。
A point $H$ is hidden in a rooted tree $Q$ which is endowed with asymmetric distances (travel times) between nodes. We determine the randomized search strategy, starting from the root, which minimizes the expected time to reach $H$, in the worst case. This is equivalent to a zero-sum search game $\Gamma\left(Q\right)$, with minimizing Searcher, maximizing Hider, and payoff equal to the capture time. The worst Hiding distribution (over the leaves) from the Searcher's viewpoint is one where at every node $i$ the probability of each branch is proportional to the minimum time required to tour it from $i$. The optimal randomized search is a mixture over depth-first searches. We also consider briefly some other networks and the possibility of a mobile Hider. Our formulation with asymmetric travel times generalizes that of Gal [SIAM J. Control Optim., 17 (1979), pp. 99-122] for symmetric travel times and also the search games of Kikuta [J. Oper. Res., 38 (1995), pp. 70-88] and Kikuta and Ruckle [Naval Res. Logist., 41 (1994), pp. 821-831], who posited search costs $c_i$ at each node $i$ which were added to the travel time to obtain the payoff. We also briefly consider what happens if we allow the Searcher (Hider) to start (hide) at any leaf node. We determine when properties found by Dagan and Gal [Networks, 52 (2008), pp. 156-161] for the symmetric version of such games hold in our asymmetric context.