Bakalářská práce
Získaná ocenění: Cena děkana FI za vynikající závěrečnou práci

Algoritmická analýza bezpečnostních her

Algorithmic analysis of patrolling games

Tomáš Lamser
Anotace

Patrolovací hry jsou hry dvou hráčů (obránce a útočníka) na grafu. Naším cílem je vypočítat strategii obránce. Představujeme regulární strategie, které jsou lepší, avšak robustnější než strategie poziční. Poté dokážeme některé zajímavé poznatky a vytvoříme nástroj, který s využitím lineárního programování a vylepšování strategie spočítá dobrou strategii.

Abstract

Patrolling games are games of two players (defender and attacker) on a graph. Our goal is to compute the strategy of the defender. We introduce regular strategies that are better and more robust than positional strategies. Then we prove some interesting theorems and create a tool that computes good strategies using strategy improvement by solving a linear problem.

Klíčová slova
Game Theory Stackelberg Equilibrium Patrolling Games Security Games Robotic Patrolling Strategy Synthesis teorie her Stackelbergovo equilibrium patrolovacíhry bezpečnostní hry hlídání pomocí robotů syntéza strategie
Zadání práce

Cílem bakalářské práce je podat přehled a kvalifikované srovnání existujících formálních modelů na bázi teorie her, které se používají pro optimální rozvrhování monitorovacích jednotek. Pro vybrané modely by v práci měly být navrženy příslušné analytické algoritmy a provedena jejich detailní složitostní analýza.

Výstupem přehledové části by měla být taxonomie existujících modelů a jejich variant, konceptů využívaných pro formulaci optimálních strategií a charakterizace základních atributů těchto konceptů (existence rovnovážných hodnot, existence (sub)optimálních strategií, strukturální složitost optimálních strategií, atd.).

V algoritmické části by měla být věnována zvláštní pozornost modelům, pro které dosud optimální algoritmy nalezeny nebyly. Součástí práce je i řádné srovnání nově navržených algoritmů s existujícími výsledky.

Administrativní informace
Práce zkontrolována:
25. 5. 2016 09:54, prof. RNDr. Antonín Kučera, Ph.D., učo 2508
Plný text práce
249,4 KB / soubor PDF
Přílohy (1)
Jazyk práce
angličtina angličtina
Termín obhajoby
22. 6. 2016
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Antonín Kučera, Ph.D., učo 2508
ITI FI MU

Oponent

doc. RNDr. Vojtěch Řehák, Ph.D., učo 3721
KTP FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

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