Yellow triangles: radar units, here max range 3
Turquoise cells: perfectly covered cells
Blue cells: cells with over-coverage 2 or 3
Orange cells: under-covered cells
Red triangle: selected radar unit
Black checkers: cells covered by red unit
The problem is to allocate a number of radar stations for observation of a geographic area, such that each point is observed by at least three stations. As customary in the radar surveillance domain, the area is divided into hexagonal cells and radar stations are located in a number of cells. Each radar station can divide its signal scope circle into six sectors and each station can vary the signal strength in each sector independently from zero to some given maximum distance. Each cell must be covered by 3 radar stations (desired coverage, dc=3) and all coverage beyond this is to be minimized over-coverage for economic reasons and for detectability. Cells that physically cannot be covered by at least three stations must be covered by as many stations as possible and are then factored out.
The radar map below illustrates a small covering problem. The covering of the cells below is optimal: The over-coverage of the solution is 6 and the LP lower bound is 5.5 (which proves the optimality). An over-constrained pseudo-Boolean encoding (.epb file) was solved to produce this solution by WSAT(PB) in approx. 1s.
|
|
Legend: Yellow triangles: radar units, here max range 3 Turquoise cells: perfectly covered cells Blue cells: cells with over-coverage 2 or 3 Orange cells: under-covered cells Red triangle: selected radar unit Black checkers: cells covered by red unit |
The modelling was developed by Seif Haridi, Per Brand and Olle Olsson at SICS. WSAT(PB) is being developed by J.P. Walser at Programming Systems Lab, Saarbruecken. The map is a screen shot of the Argus application developed at SICS and written in Oz.