KLAŠKA, David, Antonín KUČERA and Vojtěch ŘEHÁK. Adversarial Patrolling with Drones. 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, 9 pp. ISBN 978-1-4503-7518-4. doi:10.5555/3398761.3398837.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
Organization unit Faculty of Informatics
ISBN 978-1-4503-7518-4
Doi http://dx.doi.org/10.5555/3398761.3398837
Keywords in English Single and multi-agent planning and scheduling; patrolling
Tags formela-conference
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 7/9/2020 14:15.
Abstract
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 projectName: Algoritmy pro diskrétní systémy a hry s nekonečně mnoha stavy
Investor: Czech Science Foundation, Standard Projects
PrintDisplayed: 27/9/2020 10:32