Patent SG-187263-A1 (SG)
Title: Method for optimally determining the characteristics and arrangement of a set of sensors for monitoring an area
Inventor: LEMER ALAIN
Filed: 2011-07-15
Abstract: IN THE MATTER OF a Singapore Application corresponding toPCT Application PCT/EP2011/062119RWS Group Ltd, of Europa House, Chiltern Park, Chiltern Hill, Chalfont St Peter, Buckinghamshire, United Kingdom, hereby solemnly and sincerely declares that, to the best of its knowledge and belief, the following document, prepared by one of its translators competent in the art and conversant with the English and French languages, is a true and correct translation of the PCT Application filed under No. PCT/EP2011/062119.Date: 6 February 2013 N. T. SIMPK1N Deputy Managing Director — UK Translation DivisionFor and on behalf of RWS Group Ltd 1METHOD FOR OPTIMALLY DETERMINING THE CHARACTERISTICS AND ARRANGEMENT OF A SET OF SENSORS FOR MONITORING AN AREA5 The subject of the present invention is a method for determining thecharacteristics and arrangement of a set of devices or sensors for monitoring a zone of interest.It applies notably in aiding the design of a system for monitoring azone of interest through a network of fixed sensors and in determining the 10 optimum position and optimum adjustment of these sensors in the zoneunder a set of given constraints.The invention applies to any type of device or sensor in particular a camera, a radar, a seismic or acoustic sensor or else a motion detection device.15The technical problem at which the present invention is aimed relates to the automatic allocation of a set of sensors, operating in a network, in a manner adapted to the monitoring of a predefined zone of interest. This problem is notably encountered by a monitoring system20 designer or a user of such a system. It consists, on the basis of a set of sensors each having specific characteristics according to particular technologies, of a set of absolute constraints to be complied with and of a set of properties that it is desired to optimize, in determining the combination, in terms of number and type from among those available, of25 sensors making it possible to satisfy these absolute constraints and to optimize these properties. A second problem is also aimed at determining the optimum position and optimum adjustment of the sensors determined previously within the monitoring zone so as to optimize performance for constrained resources.30 The network of sensors chosen must comply with one or moreabsolute constraints, for example, a maximum budget, maximum energy reserve, maximum carriage or minimum detection performance. 2The properties to be optimized are, for example, the total price of the system, a probability of target detection, an accuracy of location in two or three dimensions. The properties are classed empirically by relative significance.5 The technical problem at which the present invention is aimed is aproblem of constrained multicriterion optimization of a set of heterogeneous cost functions of arbitrary complexity. These functions being able to be of diverse nature, analytical or non-analytical, continuous or non-continuous, differentiable or non-differentiable. Some constraints may be expressed by 10 simple functions. For example, the total price of the system corresponds to a simple sum of the prices of its constituents. Likewise the total weight of the system is also obtained by the sum of the weights of each sensor. On the other hand, other constraints are modeled by more complex functions. Thus the probability of detecting a target can depend on an a priori 15 probability density of presence of the target, the target-sensor distance or indeed the intervisibility. Accuracy of location based on fusion between sensors can involve the probabilities of detection, the accuracies of elementary measurements and the mutual relative positions of the sensors. 20 The solutions of the prior art which address the problem of theoptimization of sensor networks relate essentially to the deployment of networks of wireless devices and are aimed at optimizing the means of communication. The problem area thus tackled relates in particular to the maintaining of the service and the autonomy of the antennas and not the 25 optimization of the coverage of a monitoring zone as a function of diverse constraints on the sensors.Concerning the problem area of the optimal positioning of monitoring sensors, patent application US 7395195 proposes a device allowing the representation of a network of devices, the allocation of calculation 30 resources and the positioning of said sensors. Patent application US 7693049 implements a stochastic optimization technique essentially focused on the conservation of energy resources. 3In addition to the fact that the two aforementioned patent applications are aimed at only part of the wider problem that the present invention proposes to solve, they also exhibit limitations in relation to the optimization constraints that they can take into account. Generally, the5 known schemes implement conventional optimization schemes such as the gradient scheme. Such schemes exhibit the following drawbacks. They afford a solution to the global optimization problem only if the optimization constraints are modeled by differentiable functions, this representing a significant limitation that the present invention is aimed at removing.10 Moreover these schemes do not make it possible to avoid the phenomena of local minima or maxima which represent unsatisfactory solutions. It is also possible to use schemes based on a genetic algorithm, but these are not applicable to all cost functionals and do not guarantee convergence to a valid solution in all cases.15The present invention makes it possible to remove the limitations of the prior art by proposing a completely automated solution for determining the sensors in terms of number, type and position.For this purpose, the subject of the invention is an iterative method,20 implemented by computer, of optimized design of a system for monitoring a geographical zone comprising a plurality of sensors of different types and characteristics represented by a vector S each component of which indicates the type and the characteristics of a sensor and its position in said zone, said system exhibiting a plurality of absolute technical constraints,25 said method being characterized in that it comprises at least the following steps:o a step of initializing the vector S to a solution So,o a step of perturbing the sensors making up the solution So at the iteration of index n, to obtain a new candidate solution 5,1 at the30 iteration of index n+1, said perturbation entailing changing the type or a characteristic of at least one of said sensors, the possible sensor types also including a dummy type whose 4characteristics have no impact on the global cost of the solution S,o a step of evaluating the cost of said solution srkm on the basis of a global cost function C(S) determined as a combination of a5 plurality of sub-criteria Ck(S) for optimizing at least one characteristic of said sensors of which the solution S is composed,o a step of selecting the new current solution Sn+1 at the iteration n+1 on the basis of a probability of transition 10 P transition = 77 (C (S n), C (S n_Ei )) which decreases as a functionof (C (s„, ) — C (Sr )) culminating in the selection of the newcandidate solution 5b4-1= 5e+1 or in the retaining of the previous solution S+1 =S,a step of storing, at each iteration, the best solution Sbest 15 obtained which satisfies the relation:if C(s1) < C(Sb„,),Sbes, =a test step for stopping or continuing the iterations of said method,when the stopping test is positive, a final step of producing the 20 optimal solution Sbest containing the number, the type, the characteristics and the position of the sensors suitable for monitoring said geographical zone.In a variant embodiment of the invention, the method furthermore 25 comprises a step of displaying the positions of said sensors making up the optimal solution Sbest in the geographical zone on a user interface.In another variant embodiment of the invention, the initialization step comprises at least the following sub-steps:o random selection of the type of each of said sensors from among 30 the available types, including the dummy type,o random selection of the position of each of said sensors, 5o verification of compliance, by the solution So, with all the absolute constraints.In another variant embodiment of the invention, said sensors are of passive type and are at least taken from the following set: a camera, a5 radar, a seismic sensor, an acoustic sensor, a motion detection device, a detection device based on electrical contact, a device for detecting radioelectric sources, a device for detecting nuclear sources, a magnetic, capacitive, inductive, chemical or bacteriological detection device.In another variant embodiment of the invention, said sensors are of 10 active type and are at least taken from the following set: a radar, an active acoustic detector, a LIDAR detector, a detector based on neutron activation, an active-barrier-based detector.In another variant embodiment of the invention, an absolute technicalconstraint is a constraint of maximum weight or maximum price or of 15 minimum accuracy of location over a given geographical zone.In another variant embodiment of the invention, a characteristic of asensor comprises its weight, its price, its probability of detecting a target, itsdetection radius.In another variant embodiment of the invention, an optimization sub 20 criterion is the global weight of the set of said sensors or the global price of the set of said sensors or the degree of coverage of the monitored zone or the accuracy of location of a target in the monitored zone, said sub-criterion being able to be computed numerically for the set of sensors making up the solution S. 25 In another variant embodiment of the invention, at least one of the sub criteria depends on a significance map which allocates for each mesh cell, with coordinates i,j, of the geographical zone to be mo