Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00088484" target="_blank" >RIV/00216224:14330/16:00088484 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

Popis výsledku v původním jazyce

In patrolling problems, the task is to compute an optimal strategy for a patroller who moves among vulnerable targets and aims at detecting possible intrusions. Previous approaches to this problem utilize non-linear programming to synthesize (sub)optimal patroller's strategies, which has a negative impact on their scalability. Further, the solution space is usually restricted to positional strategies or to strategies dependent on a bounded history of patroller's moves. In this paper we introduce regular strategies that utilize deterministic finite-state automata to collect some information about the whole history of patroller's moves, and show that regular strategies are strictly more powerful than strategies dependent on a bounded history. Further, we design a strategy improvement technique for regular strategies which completely avoids solving large non-linear programs.

Název v anglickém jazyce

Regular Strategies and Strategy Improvement: Efficient Tools for Solving Large Patrolling Problems

Popis výsledku anglicky

In patrolling problems, the task is to compute an optimal strategy for a patroller who moves among vulnerable targets and aims at detecting possible intrusions. Previous approaches to this problem utilize non-linear programming to synthesize (sub)optimal patroller's strategies, which has a negative impact on their scalability. Further, the solution space is usually restricted to positional strategies or to strategies dependent on a bounded history of patroller's moves. In this paper we introduce regular strategies that utilize deterministic finite-state automata to collect some information about the whole history of patroller's moves, and show that regular strategies are strictly more powerful than strategies dependent on a bounded history. Further, we design a strategy improvement technique for regular strategies which completely avoids solving large non-linear programs.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA15-17564S" target="_blank" >GA15-17564S: Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů</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

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

ISBN

9781450342391

ISSN

1548-8403

e-ISSN

—

Počet stran výsledku

9

Strana od-do

1171-1179

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Singapore

Datum konání akce

9. 5. 2016

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

WRD - Celosvětová akce

Kód UT WoS článku

—