Adversarial Patrolling with Drones

D 2020

Adversarial Patrolling with Drones

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

Basic information

Original name

Adversarial Patrolling with Drones

Authors

KLAŠKA, David (203 Czech Republic, belonging to the institution), Antonín KUČERA (203 Czech Republic, belonging to the institution) and Vojtěch ŘEHÁK (203 Czech Republic, guarantor, belonging to the institution)

Edition

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

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Confidentiality degree

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

Publication form

electronic version available online

RIV identification code

RIV/00216224:14330/20:00114048

Organization unit

Faculty of Informatics

ISBN

978-1-4503-7518-4

ISSN

DOI

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

Keywords in English

Single and multi-agent planning and scheduling; patrolling

Abstract

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.

Links

GA18-11193S, research and development project

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

Investor: Czech Science Foundation

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

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

Investor: Masaryk University, Category A

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

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

Investor: Masaryk University, Category A

Citovat

KLAŠKA, David, Antonín KUČERA and 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, p. 629-637. ISBN 978-1-4503-7518-4. Available from: 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 and 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, p.~629-637. ISBN~978-1-4503-7518-4. Available from: https://dx.doi.org/10.5555/3398761.3398837.

Detailed Information on Publication Record