Adversarial Patrolling with Drones

Investor logo


This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on

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

Year of publication 2020
Type Article in Proceedings
Conference Proceedings of the 2020 International Conference on Autonomous Agents & Multiagent Systems
MU Faculty or unit

Faculty of Informatics

Keywords Single and multi-agent planning and scheduling; patrolling
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.