A Point-Based Approximate Algorithm for One-Side Partially Observable Pursuit-Evasion Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00306672" target="_blank" >RIV/68407700:21230/16:00306672 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-47413-7_25" target="_blank" >http://dx.doi.org/10.1007/978-3-319-47413-7_25</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-47413-7_25" target="_blank" >10.1007/978-3-319-47413-7_25</a>
Alternative languages
Result language
angličtina
Original language name
A Point-Based Approximate Algorithm for One-Side Partially Observable Pursuit-Evasion Games
Original language description
Pursuit-evasion games model many security problems where an evader is trying to escape a group of pursuing units. We consider a variant with partial observability and simultaneous moves of all units, and assume the worst-case setup, where the evader knows the location of pursuer’s units, but the pursuer does not know the location of the evader. Recent work has shown that the solution of such games is compactly representable as a collection of finite-dimensional value functions. We extend this result and propose the first practical algorithm for approximating optimal policies in pursuit-evasion games with one-sided partial observability. Our approach extends the point-based updates that exist for POMDPs to one-sided partially observable stochastic games. The experimental evaluation on multiple graphs shows significant improvementsover approximate algorithms that operate on finite game trees.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
JC - Computer hardware and software
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA15-23235S" target="_blank" >GA15-23235S: Abstractions and Extensive-Form Games with Imperfect Recall</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Decision and Game Theory for Security
ISBN
978-3-319-47412-0
ISSN
0302-9743
e-ISSN
—
Number of pages
20
Pages from-to
435-454
Publisher name
Springer
Place of publication
Basel
Event location
New York
Event date
Nov 2, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000389821200025