Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F18%3A00100830" target="_blank" >RIV/00216224:14330/18:00100830 - isvavai.cz</a>

Výsledek na webu

<a href="http://dl.acm.org/citation.cfm?id=3237383.3237481" target="_blank" >http://dl.acm.org/citation.cfm?id=3237383.3237481</a>

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

Popis výsledku v původním jazyce

We give a polynomial-time algorithm for synthesizing efficient regular strategies in adversarial patrolling games with general topology. Regular strategies use finite memory to gather some relevant information about the history of Defender's moves which results in substantially better protection of the targets. So far, the scope of automatic strategy synthesis was limited to positional strategies (which ignore the history) or to regular strategies where the underlying finite-memory observer had to be supplied manually. Furthermore, the existing methods do not give any information on how far are the constructed strategies from being optimal. In this paper, we try to overcome these limitations. We develop a novel gradient-based algorithm for synthesizing regular strategies where the underlying finite-memory observers are constructed algorithmically. The running time of our algorithm is polynomial which makes the algorithm applicable to instances of realistic size. Furthermore, we develop an algorithm for computing an upper bound on the best achievable protection, and compare the quality of the constructed strategies against this bound. Thus, we can effectively measure the "distance'' of the constructed strategies from optimal strategies, and our experiments show that this distance is often quite small.

Název v anglickém jazyce

Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

Popis výsledku anglicky

We give a polynomial-time algorithm for synthesizing efficient regular strategies in adversarial patrolling games with general topology. Regular strategies use finite memory to gather some relevant information about the history of Defender's moves which results in substantially better protection of the targets. So far, the scope of automatic strategy synthesis was limited to positional strategies (which ignore the history) or to regular strategies where the underlying finite-memory observer had to be supplied manually. Furthermore, the existing methods do not give any information on how far are the constructed strategies from being optimal. In this paper, we try to overcome these limitations. We develop a novel gradient-based algorithm for synthesizing regular strategies where the underlying finite-memory observers are constructed algorithmically. The running time of our algorithm is polynomial which makes the algorithm applicable to instances of realistic size. Furthermore, we develop an algorithm for computing an upper bound on the best achievable protection, and compare the quality of the constructed strategies against this bound. Thus, we can effectively measure the "distance'' of the constructed strategies from optimal strategies, and our experiments show that this distance is often quite small.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA18-11193S" target="_blank" >GA18-11193S: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy</a><br>

Návaznosti

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

Rok uplatnění

2018

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

Proceedings of the 2018 International Conference on Autonomous Agents & Multiagent Systems

ISBN

9781510868083

ISSN

1548-8403

e-ISSN

—

Počet stran výsledku

8

Strana od-do

659-666

Název nakladatele

International Foundation for Autonomous Agents and Multiagent Systems

Místo vydání

Richland, SC

Místo konání akce

Stockholm

Datum konání akce

1. 1. 2018

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

WRD - Celosvětová akce

Kód UT WoS článku

—