Towards Selecting the Best Abstraction for a Patrolling Game
Anjon Basak, Christopher D. Kiekintveld, Владик Крейнович · scholarworks - UTEP (The University of Texas at El Paso) · 2015
When the number of possible strategies is large, it is not computa-tionally feasible to compute the optimal strategy for the original game. Instead, we select our strategy based on an approximate approximate description of the original game. The quality of the resulting strategy depends on which approximation we select. In this paper, on an example of a simple game, we show how to nd the optimal approximation, the approximation whose use results in the best strategy. 1 Formulation of the Problem Need for abstraction. Ideally, in a conflict situation, we should select a strategy which is optimal in some reasonable sense. For example, in a zero-sum game, it makes sense to select a strategy that minimizes the worst-case loss. The more strategies we need to consider, the more computations we need to perform to find the optimal strategy. When the number of strategies becomes large, it is often not feasible to exactly compute the optimal strategy. In such