Master's thesis

Solving patrolling games using optimization techniques

Optimalizační metody pro řešení patrolovacích her

Bc. David Klaška, UČO 374303
Abstract

Práce se zabývá patrolovacími hrami. Tyto hry hrají na orientovaných grafech dva protivníci: jeden hráč (nazývaný útočník) hodlá podniknout útok na jeden z vrcholů grafu, zatímco druhý hráč (nazývaný obránce) se pohybuje po hranách grafu tak, aby případný útok odhalil dříve, než bude úspěšně dokončen. Nejprve ukazujeme příklady patrolovacích her se zajímavými vlastnostmi. Konkrétně dokazujeme, že existuje …more

Abstract

In this thesis, we study patrolling games. These games are played on a directed graph by two adversaries: one of the players (called attacker or in- truder) plans to arrive at a vertex in order to perform an attack there while the other player (called defender or patroller) keeps moving along the edges of the graph, hoping to catch the intruder while the attack is in progress, or to discourage him …more

Keywords
patrolling games complete information stochastic games game theory gradient ascent optimization methods strategy synthesis
Thesis description
Cílem práce je prozkoumat možnosti řešení patrolovacích her na orientovaných grafech pomocí optimalizačních metod. Student se zaměří na oblast gradientních metod. Práce by měla obsahovat přehled relevatních výsledků. Zejména by však měla obsahovat funkční implementaci systému pro řešení patrolovacích her. V ideálním případě by práce mohla přinést nové teoretické poznatky v oblasti řešení patrolovacích her z pohledu optimalizačních metod (např. matematické vlastnosti hodnotové funkce, vlastnosti gradientu této funkce apod.)
Administrative information
The thesis has been checked:
9/1/2017 10:22, doc. RNDr. Tomáš Brázdil, Ph.D., MBA, UČO 4074
Full text of thesis
334,2 KB / file PDF
Attachments (1)
Language used
English English
Defence date
7/2/2017
The thesis was defended successfully

Supervisor

doc. RNDr. Tomáš Brázdil, Ph.D., MBA, UČO 4074
ITI FI MU

Reader

RNDr. Nikola Beneš, Ph.D., UČO 72525
KPSK FI MU

Literature

  • ABAFFY, Michal; Tomáš BRÁZDIL; Vojtěch ŘEHÁK; Branislav BOŠANSKÝ; Antonín KUČERA and Jan KRČÁL. Solving adversarial patrolling games with bounded error: (extended abstract). In Alessio Lomuscio, Paul Scerri, Ana Bazzan, and Michael Huhns. Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'14). Richland, SC, USA: International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS), 2014, p. 1617-1618. ISBN 978-1-4503-2738-1.
  • ALPERN, Steve; Alec MORTON and Katerina PAPADAKI. Patrolling Games. Operations Research. 2011, vol. 59, No 5, p. 1246-1257.
Cite this text
Masaryk University Faculty of Informatics
Programme
Informatics
Field of Study

Theses on a related topic

List of theses with an identical keyword.

Similar documents

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.