Adversarial Patrolling with Drones

D 2020

Adversarial Patrolling with Drones

KLAŠKA, David, Antonín KUČERA a Vojtěch ŘEHÁK

Základní údaje

Originální název

Adversarial Patrolling with Drones

Autoři

KLAŠKA, David (203 Česká republika, domácí), Antonín KUČERA (203 Česká republika, domácí) a Vojtěch ŘEHÁK (203 Česká republika, garant, domácí)

Vydání

Richland, SC, Proceedings of the 2020 International Conference on Autonomous Agents & Multiagent Systems, od s. 629-637, 9 s. 2020

Nakladatel

International Foundation for Autonomous Agents and Multiagent Systems

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/20:00114048

Organizační jednotka

Fakulta informatiky

ISBN

978-1-4503-7518-4

ISSN

DOI

http://dx.doi.org/10.5555/3398761.3398837

Klíčová slova anglicky

Single and multi-agent planning and scheduling; patrolling

Štítky

core_A, firank_1, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 30. 4. 2021 07:54, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

We investigate adversarial patrolling where the Defender is an autonomous device with a limited energy resource (e.g., a drone). Every eligible Defender’s policy must prevent draining the energy resource before arriving to a refill station, and this constraint substantially complicates the problem of computing an efficient Defender’s policy. Furthermore, the existing infinite-horizon models assume Attackers with unbounded patience willing to wait arbitrarily long for a good attack opportunity. We show this assumption is inappropriate in the setting with drones because here the expected waiting time for an optimal attack opportunity can be extremely large. To overcome this problem, we introduce and justify a new concept of impatient Attacker, and design a polynomial time algorithm for computing a Defender’s policy achieving protection close to the optimal value against an impatient Attacker. Since our algorithm can quickly evaluate the protection achievable for various topologies of refill stations, we can also optimize their displacement. We implement the algorithm and demonstrate its functionality on instances of realistic size.

Návaznosti

GA18-11193S, projekt VaV

Název: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

Investor: Grantová agentura ČR, Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy

MUNI/A/1050/2019, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX (Akronym: SV-FI MAV IX)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace IX, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

MUNI/A/1076/2019, interní kód MU

Název: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20 (Akronym: SKOMU)

Investor: Masarykova univerzita, Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity 20, DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

KLAŠKA, David, Antonín KUČERA a Vojtěch ŘEHÁK. Adversarial Patrolling with Drones. Online. In Proceedings of the 2020 International Conference on Autonomous Agents & Multiagent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2020, s. 629-637. ISBN 978-1-4503-7518-4. Dostupné z: https://dx.doi.org/10.5555/3398761.3398837.

@inproceedings{1618996,
   author = {Klaška, David and Kučera, Antonín and Řehák, Vojtěch},
   address = {Richland, SC},
   booktitle = {Proceedings of the 2020 International Conference on Autonomous Agents & Multiagent Systems},
   doi = {http://dx.doi.org/10.5555/3398761.3398837},
   keywords = {Single and multi-agent planning and scheduling; patrolling},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Richland, SC},
   isbn = {978-1-4503-7518-4},
   pages = {629-637},
   publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
   title = {Adversarial Patrolling with Drones},
   year = {2020}
}

TY  - JOUR
ID  - 1618996
AU  - Klaška, David - Kučera, Antonín - Řehák, Vojtěch
PY  - 2020
TI  - Adversarial Patrolling with Drones
PB  - International Foundation for Autonomous Agents and Multiagent Systems
CY  - Richland, SC
SN  - 9781450375184
KW  - Single and multi-agent planning and scheduling
KW  - patrolling
N2  - We investigate adversarial patrolling where the Defender is an autonomous device with a limited energy resource (e.g., a drone). Every eligible Defender’s policy must prevent draining the energy resource before arriving to a refill station, and this constraint substantially complicates the problem of computing an efficient Defender’s policy. Furthermore, the existing infinite-horizon models assume Attackers with unbounded patience willing to wait arbitrarily long for a good attack opportunity. We show this assumption is inappropriate in the setting with drones because here the expected waiting time for an optimal attack opportunity can be extremely large. To overcome this problem, we introduce and justify a new concept of impatient Attacker, and design a polynomial time algorithm for computing a Defender’s policy achieving protection close to the optimal value against an impatient Attacker. Since our algorithm can quickly evaluate the protection achievable for various topologies of refill stations, we can also optimize their displacement. We implement the algorithm and demonstrate its functionality on instances of realistic size.
ER  -

KLAŠKA, David, Antonín KUČERA a Vojtěch ŘEHÁK. Adversarial Patrolling with Drones. Online. In \textit{Proceedings of the 2020 International Conference on Autonomous Agents \&{} Multiagent Systems}. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2020, s.~629-637. ISBN~978-1-4503-7518-4. Dostupné z: https://dx.doi.org/10.5555/3398761.3398837.

Podrobný výpis o publikaci