Optimising sampling designs for the maximum coverage problem of plume detection

•Sampling design for plume detection is a variation on the maximum coverage problem.•Complete enumeration can be accelerated by taking advantage of plume similarity.•Optimal sampling designs often share common sensors and build fences towards sources.•Greedy search is likely to find almost optimal and sometimes optimal designs.•Heuristics found single optimal sensors, spatially almost optimal results were rare.

The location of sensors to detect outbreaks of hazardous plumes in the atmosphere can be improved by considering possible paths of such plumes. Atmospheric dispersion models can provide simulations of such paths under realistic weather conditions. Numeric simulation always goes along with discretisation, and if a plume is detected or not can be regarded as a binary question. Thus optimising the locations of a fixed number of sensors can be regarded as finite; in fact it is a variety of the classical maximum coverage problem. We present an algorithm to completely solve this problem. It is based on complete deep tree search that finds all globally optimal sensor configurations, but the effort is reduced by skipping non-promising configurations and deleting redundant data. To determine the effort and to learn about optimal sensor configurations, the algorithm was tested on several scenarios based on plume simulations or on random data. This was completed by some theoretical results on the effect of problem size and plume detection probability on the effort. Finally we used the determined optimal configurations to evaluate two well known heuristics: greedy search and a genetic algorithm.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide