  The increasing spreading of small commercial Unmanned Aerial Vehicles (UAVs,
aka drones) presents serious threats for critical areas such as airports, power
plants, governmental and military facilities. In fact, such UAVs can easily
disturb or jam radio communications, collide with other flying objects, perform
espionage activity, and carry offensive payloads, e.g., weapons or explosives.
A central problem when designing surveillance solutions for the localization of
unauthorized UAVs in critical areas is to decide how many triangulating sensors
to use, and where to deploy them to optimise both coverage and cost
effectiveness.
  In this article, we compute deployments of triangulating sensors for UAV
localization, optimizing a given blend of metrics, namely: coverage under
multiple sensing quality levels, cost-effectiveness, fault-tolerance. We focus
on large, complex 3D regions, which exhibit obstacles (e.g., buildings),
varying terrain elevation, different coverage priorities, constraints on
possible sensors placement. Our novel approach relies on computational geometry
and statistical model checking, and enables the effective use of off-the-shelf
AI-based black-box optimizers. Moreover, our method allows us to compute a
closed-form, analytical representation of the region uncovered by a sensor
deployment, which provides the means for rigorous, formal certification of the
quality of the latter.
  We show the practical feasibility of our approach by computing optimal sensor
deployments for UAV localization in two large, complex 3D critical regions, the
Rome Leonardo Da Vinci International Airport (FCO) and the Vienna International
Center (VIC), using NOMAD as our state-of-the-art underlying optimization
engine. Results show that we can compute optimal sensor deployments within a
few hours on a standard workstation and within minutes on a small parallel
infrastructure.
