  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 model 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 in arbitrary
graphs is APX-hard even in zero-sum games and we provide two (exponential time)
exact algorithms and two (polynomial time) approximation algorithms.
Furthermore, we analyse what happens in environments with special topologies,
showing that in linear and cycle graphs the optimal patrolling strategy can be
found in polynomial time, de facto allowing our algorithms to be used in
real-life scenarios, while in trees the problem is NP-hard. 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.
