|
Accession Number
|
ADA558916
|
|
Title
|
Efficient Algorithm for a Visibility-Based Surveillance-Evasion Game.
|
|
Publication Date
|
Jan 2012
|
|
Media Count
|
24p
|
|
Personal Author
|
R. Takei R. Tsai Y. Landa Z. Zhou
|
|
Abstract
|
We present an algorithm which computes the value function and optimal paths for a two-player static game, where the goal of one player is to maintain visibility of an adversarial player for as long as possible, and that of the adversarial player is to minimize this time. In a static game both players choose their controls at initial time and run in open-loop for t > 0 until the end-game condition is met. Compared to closed-loop (feedback strategy) games which require solving a PDE in high dimensions, we demonstrate that the static game can be solved directly in the state space by the proposed PDE-based technique. This results in significant savings in both memory and computational cost, at the expense of a simpler information pattern that is more conservative towards one player. In addition, we describe how this algorithm can be easily generalized to games with multiple evaders. Applications to target tracking and an extension to a feedback control game are also presented.
|
|
Keywords
|
Algorithms
Computational cost
Game theory
Moving targets
Partial differential equations
Static games
Theorems
Tracking
|
|
|
Source Agency
|
Non Paid ADAS
|
|
NTIS Subject Category
|
72E - Operations Research
62 - Computers, Control & Information Theory
|
|
Corporate Author
|
Texas Univ. at Austin. Inst. for Computational Engineering and Sciences.
|
|
Document Type
|
Technical report
|
|
Title Note
|
Technical rept.
|
|
NTIS Issue Number
|
1219
|
|
Contract Number
|
N00014-07-1-0810 N0014-03-1-0071
|
