کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4942141 | 1436986 | 2017 | 73 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Adversarial patrolling with spatially uncertain alarm signals
ترجمه فارسی عنوان
گشتی مخالف با سیگنال های هشدار دهنده فضایی نامشخص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
بازی های امنیتی گشتی مخالف، نظریه بازی الگوریتمی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
چکیده انگلیسی
When securing complex infrastructures or large environments, constant surveillance of every area is not affordable. To cope with this issue, a common countermeasure is the usage of cheap but wide-ranged sensors, able to detect suspicious events that occur in large areas, supporting patrollers to improve the effectiveness of their strategies. However, such sensors are commonly affected by uncertainty. In the present paper, we focus on spatially uncertain alarm signals. That is, the alarm system is able to detect an attack but it is uncertain on the exact position where the attack is taking place. This is common when the area to be secured is wide, such as in border patrolling and fair site surveillance. We propose, to the best of our knowledge, the first Patrolling Security Game where a Defender is supported by a spatially uncertain alarm system, which non-deterministically generates signals once a target is under attack. We show that finding the optimal strategy is FNP-hard even in tree graphs and APX-hard in arbitrary graphs. We provide two (exponential time) exact algorithms and two (polynomial time) approximation algorithms. Finally, we show that, without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non-negligible missed detection rates, which, unfortunately, affect every commercial alarm system. We evaluate our methods in simulation, assessing both quantitative and qualitative aspects.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 246, May 2017, Pages 220-257
Journal: Artificial Intelligence - Volume 246, May 2017, Pages 220-257
نویسندگان
Nicola Basilico, Giuseppe De Nittis, Nicola Gatti,