Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

Result code in 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>

Result on the web

<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

—

Result language

angličtina

Original language name

Automatic Synthesis of Efficient Regular Strategies in Adversarial Patrolling Games

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>

Continuities

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

Publication year

2018

Confidentiality

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

Article name in the collection

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

ISBN

9781510868083

ISSN

1548-8403

e-ISSN

—

Number of pages

8

Pages from-to

659-666

Publisher name

International Foundation for Autonomous Agents and Multiagent Systems

Place of publication

Richland, SC

Event location

Stockholm

Event date

Jan 1, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—