A Point-Based Approximate Algorithm for One-Side Partially Observable Pursuit-Evasion Games

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

A Point-Based Approximate Algorithm for One-Side Partially Observable Pursuit-Evasion Games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A Point-Based Approximate Algorithm for One-Side Partially Observable Pursuit-Evasion Games

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

<a href="/cs/project/GA15-23235S" target="_blank" >GA15-23235S: Abstrakce a extenzivní hry s nedokonalou pamětí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Decision and Game Theory for Security

ISBN

978-3-319-47412-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

20

Strana od-do

435-454

Název nakladatele

Springer

Místo vydání

Basel

Místo konání akce

New York

Datum konání akce

2. 11. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000389821200025