A search game on a hypergraph with booby traps
A search game on a hypergraph with booby traps
复制标题
带有陷阱的超图上的搜索游戏
DOI：
10.1016/j.tcs.2020.03.011
复制
发表时间：
2020
影响因子：
1.1
通讯作者：
Lin, Kyle Y.
中科院分区：
文献类型：
--
作者：
Lidbetter, Thomas;Lin, Kyle Y.
位于超图G的顶点上的一组n个盒子包含已知但不同的奖励。搜索者打开G的某个超边中的所有盒子，目的是收集最大可能的总奖励。然而，有些盒子是陷阱。如果搜索者打开了一个陷阱盒子，搜索结束，她失去了所有收集的奖励。我们假设诱杀装置的数量k是已知的，我们将问题建模为最大化搜索者和最小化隐藏者之间的零和游戏，其中隐藏者选择k个盒子来设置诱杀装置，搜索者在某个超边缘打开所有盒子。收益是搜索者收集的总奖励。这个模型可以反映一个军事行动，其中一架无人机从守卫的地点收集情报，一个诱杀盒被打开对应于无人机被摧毁或失去能力。它还可以模拟机器调度问题，其中成功处理作业可以获得奖励，但机器可能会崩溃。当G是一个1-一致超图（超边都是单点）时，我们解决了这个博弈，所以搜索者只能打开1个盒子。当G是完全超图（包含所有可能的超边）时，我们在几种情况下解决了这个博弈：（1）每个盒子中的奖励相同，（2）k= 1，（3）n= 4和k= 2。这几种情况的解表明，一般的简单，封闭形式的解决方案的游戏似乎不太可能。
A set of n boxes, located on the vertices of a hypergraph G, contain known but different rewards. A Searcher opens all the boxes in some hyperedge of G with the objective of collecting the maximum possible total reward. Some of the boxes, however, are booby trapped. If the Searcher opens a booby trapped box, the search ends and she loses all her collected rewards. We assume the number k of booby traps is known, and we model the problem as a zero-sum game between the maximizing Searcher and a minimizing Hider, where the Hider chooses k boxes to booby trap and the Searcher opens all the boxes in some hyperedge. The payoff is the total reward collected by the Searcher. This model could reflect a military operation in which a drone gathers intelligence from guarded locations, and a booby trapped box being opened corresponds to the drone being destroyed or incapacitated. It could also model a machine scheduling problem, in which rewards are obtained from successfully processing jobs but the machine may crash. We solve the game when G is a 1-uniform hypergraph (the hyperedges are all singletons), so the Searcher can open just 1 box. When G is the complete hypergraph (containing all possible hyperedges), we solve the game in a few cases:(1) same reward in each box,(2) k= 1, and (3) n= 4 and k= 2. The solutions to these few cases indicate that a general simple, closed form solution to the game appears unlikely.
在并行机器上对不可靠的作业进行排序
影响因子：
2
作者：
A. Agnetis;P. Detti;M. Pranzo;M. Sodhi
通讯作者：
M. Sodhi
在不同地点连续进行捉迷藏和追击躲避
影响因子：
3.9
作者：
S. Gal;Jérôme Casas
通讯作者：
Jérôme Casas
搜索具有多个隐藏物体的游戏
DOI：
10.1137/120893938
发表时间：
2013
期刊：
SIAM J. Control. Optim.
影响因子：
--
作者：
T. Lidbetter
通讯作者：
T. Lidbetter