论文标题
机器人监视的随机策略作为Stackelberg游戏
Stochastic Strategies for Robotic Surveillance as Stackelberg Games
论文作者
论文摘要
本文研究了一个随机的机器人监视问题，其中移动机器人在图表上随机移动以捕获潜在的入侵者，该入侵者会策略性地攻击图表上的位置。认为入侵者被认为是无所不知的：它知道移动代理的当前位置，并且可以学习监视策略。移动机器人的目标是设计一种随机策略，以最大程度地提高捕获入侵者的可能性。我们将监视机器人与入侵者之间的战略相互作用建模为Stackelberg游戏，并研究了基于Star，Complete和line Graphs的最佳和最佳Markov链的最佳和次优链。我们首先在捕获概率上得出了通用上限，即监视剂的性能极限。我们表明，该上限在完整的图中很紧，并进一步提供了自然设计的次级临时保证。对于星形和线条图，我们首先表征了监视剂和入侵者的主要策略。然后，我们严格地证明了监视剂的最佳策略。
This paper studies a stochastic robotic surveillance problem where a mobile robot moves randomly on a graph to capture a potential intruder that strategically attacks a location on the graph. The intruder is assumed to be omniscient: it knows the current location of the mobile agent and can learn the surveillance strategy. The goal for the mobile robot is to design a stochastic strategy so as to maximize the probability of capturing the intruder. We model the strategic interactions between the surveillance robot and the intruder as a Stackelberg game, and optimal and suboptimal Markov chain based surveillance strategies in star, complete and line graphs are studied. We first derive a universal upper bound on the capture probability, i.e., the performance limit for the surveillance agent. We show that this upper bound is tight in the complete graph and further provide suboptimality guarantees for a natural design. For the star and line graphs, we first characterize dominant strategies for the surveillance agent and the intruder. Then, we rigorously prove the optimal strategy for the surveillance agent.
