The problem of designing efective systems to prevent risks and hazards caused by drones in critical areas has gained significant attention in recent years. In this short paper, we introduce the idea of computing optimal deployments of anti-drone sensors in a given region using simulation-based optimisation via heuristic-guided intelligent search and a geometric modelling of the problem, and show preliminary results in a real-world scenario.
Large critical areas often present certain characteristics that make it dificult to compute an
optimal deployment of anti-drone sensors. In [
Unfortunately, following similar methods to compute an optimal placement of the RF sensors themselves would be unviable, as, to achieve the desired accuracy in the computation of the quality of the deployment, a much finer discretisation of the RoI would be needed. Also, diferently from relay nodes, optimal positions of anti-drone RF sensors could easily belong to the 3D space, as some sensors could be optimally placed on, e.g., , the roofs or walls of buildings. All this would make a suitably-discretised version of the problem intractably large.
We introduce a computational geometry–based approach to represent the environment and the possible positions of the sensors, by defining the RoI and its obstacles (such as buildings and terrain asperities) as well as RoI priority regions and admissible sensor positions in terms of bounded convex polytopes. This allows us to achieve any desired level of accuracy, enables the eficient computation of the coverage of a given deployment via computational geometry techniques, and paves the way to the use of simulation-based optimisation approaches.
Our goal is to compute a deployment of a given set of sensors over a 3D region, optimising the
linear combination of two (possibly conflicting) performance metrics: (1) the RoI % not covered
by the sensors and (2) the economic cost of purchasing and physically deploying the sensors. The
coeficient of the linear combination are chosen so that the objective value defines an amount of
money, combining the expense for purchasing and placing the sensors and the implicit cost of
not covering part of the RoI. We implemented a simulator that takes as an input the geometric
description of the environment and a deployment of sensors and computes the associated value
of the objective function (objective value). This simulator uses the Parma Polyhedra Library
[
The latter combines derivative-free optimisation [
We evaluated the performance of our optimiser on a large, real-world scenario: the Leonardo da Vinci International airport of Rome, Italy. We used sensors with range of 1 km, which could be deployed both on the ground (but not on the runways, on the roads and on the taxiways) and on top of the buildings. We varied the number of deployed sensors between 12 and 20. In each experiment, we first sampled 100 random deployments and sorted them by their objective value (to be minimised) in ascending order. Then, we executed the optimisation algorithm multiple times using the sampled deployments as starting points, from the best to the worse. A time budget of 24 hours was set and the optimisation algorithm was run until either the whole time budget was consumed or all 100 runs were completed.
In most of the cases, the algorithm was able to quickly improve the objective value and find much better deployments than those found by random sampling. Among the best deployments found with diferent number of sensors (Figure 1), the one that employed 16 sensors showed the minimal objective value, i.e., was the one that best combined the coverage (73.1% of the RoI volume covered) and the total expense for the deployment.
Many attempts have been proposed in the literature to solve large optimisation problems
defined via logic-, automata- or constraint-based formalisms ( e.g., [
Most works focus on monitoring 2D regions, with or without obstacles (e.g., [31, 32, 33, 34, 35, 36]), hence are not easily adaptable to the localisation of flying objects. Approaches working in the 3D space [31, 37] do exist. However they typically discretise the RoI and the possible positions of sensors [38, 39], and thus do not scale over large scenarios when the targets must be localised with high accuracy.
In this short paper we have shown how to compute optimal deployments of anti-drone sensors in a given RoI through simulation-based optimisation via heuristic-guided intelligent search and geometric problem modelling. We also presented preliminary results in a real-world scenario (Leonardo da Vinci airport in Rome, Italy) which show our approach promising. [17] T. Mancini, et al., User flexibility aware price policy synthesis for smart grids, in: DSD 2015. [18] T. Mancini, et al., Parallel statistical model checking for safety verification in smart grids, in: SmartGridComm 2018, IEEE, 2018. [19] T. Mancini, et al., SyLVaaS: System level formal verification as a service, in: PDP 2015. [20] T. Mancini, et al., System level formal verification via distributed multi-core hardware in the loop simulation, in: PDP 2014, IEEE, 2014. [21] T. Mancini, et al., Anytime system level verification via random exhaustive hardware in the loop simulation, in: DSD 2014, IEEE, 2014. [22] T. Mancini, et al., Anytime system level verification via parallel random exhaustive hardware in the loop simulation, Micropr Microsys 41 (2016). [23] T. Mancini, et al., SyLVaaS: System level formal verification as a service, Fund Inf 149(1–2) (2016). [24] T. Mancini, et al., Any-horizon uniform random sampling and enumeration of constrained scenarios for simulation-based formal verification, IEEE TSE (2021). To appear. [25] T. Mancini, On minimising the maximum expected verification time, Inf Proc Lett 122 (2017). [26] E. Tronci, et al., Patient-specific models from inter-patient biological models and clinical records, in: FMCAD 2014, IEEE, 2014. [27] T. Mancini, Computing biological model parameters by parallel statistical model checking, in: IWBBIO 2015, LNCS 9044, Springer, 2015. [28] T. Mancini, et al., Computing personalised treatments through in silico clinical trials. A case study on downregulation in assisted reproduction, in: RCRA 2018, CEUR 2271, 2018. [29] S. Sinisi, et al., Complete populations of virtual patients for in silico clinical trials, Bioinf 36 (2020). [30] S. Sinisi, et al., Optimal personalised treatment computation through in silico clinical trials on patient digital twins, Fund Inf 174(3–4) (2020). [31] A. A. Altahir, et al., Visual sensor placement based on risk maps, IEEE Trans Instr Meas 69 (2019). [32] K. An, et al., Reliable sensor location for object positioning and surveillance via trilateration,
Transp Res Part B: Methodol 117 (2018). [33] L. Dai, et al., Sensor placement based on an improved genetic algorithm for connected confident information coverage in an area with obstacles, in: LCN 2017, IEEE, 2017. [34] Y.-G. Fu, J. Zhou, L. Deng, Surveillance of a 2D plane area with 3D deployed cameras,
Sensors 14 (2014). [35] Y. E. Osais, et al., Directional sensor placement with optimal sensing range, field of view and orientation, Mob Netw Appl 15 (2010). [36] X. Yang, et al., Computer-aided optimization of surveillance cameras placement on construction sites, Comp-Aided Civil Infr Eng 33(12) (2018). [37] J. Yang, et al., A 3D sensing model and practical sensor placement based on coverage and cost evaluation, in: CYBER 2015, IEEE, 2015. [38] A. Saad, et al., Toward a realistic approach for the deployment of 3d wireless sensor networks, IEEE Trans Mob Comp (2020). [39] S. Jun, et al., Placing visual sensors using heuristic algorithms for bridge surveillance, Appl Sci 8 (2018).