Adversarial Patrolling with Drones

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00114048" target="_blank" >RIV/00216224:14330/20:00114048 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.5555/3398761.3398837" target="_blank" >http://dx.doi.org/10.5555/3398761.3398837</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5555/3398761.3398837" target="_blank" >10.5555/3398761.3398837</a>

Result language

angličtina

Original language name

Adversarial Patrolling with Drones

Original language 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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 2020 International Conference on Autonomous Agents & Multiagent Systems

ISBN

9781450375184

ISSN

1548-8403

e-ISSN

—

Number of pages

9

Pages from-to

629-637

Publisher name

International Foundation for Autonomous Agents and Multiagent Systems

Place of publication

Richland, SC

Event location

Auckland New Zealand

Event date

Jan 1, 2020

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—