Case Studies

Optimizing Sensor Placement

Frontier® Powers an Automated Sensor Placement Optimization System

Goal

Automatically determine optimal locations and parameters for cameras and other line-of-sight sensors in order to maximize coverage of specified areas of interest.

Business

Border control, physical facility security, crime prevention, asset protection, military intelligence.

Industry

Government, Security

Challenge

In order to monitor activity and track unexpected intrusion within border zones, exteriors of buildings, military bases, sensitive areas in war zones, and other areas, a variety of monitored sensors are set up in strategic locations. These sensors most commonly include line-of-sight devices such as cameras and radar, although may be augmented by seismic, electromagnetic, and other types of sensors. When the complexity of an environment moves beyond the simplest of buildings and the flattest of terrain, the question of where to place sensors becomes a difficult issue. The best sensor placement strategies should avoid blind spots and minimize the cost and number of sensors required for optimal coverage. However, attempting to create such plans by hand is time-consuming and highly prone to error and insufficient results.

It is clear that this process is best done with the help of computers, but computer applications were cumbersome. The situation is very complicated and involves many factors, including precise descriptions of the environment with details such as terrain and basic building measurements in addition to the desired type and numbers of sensors available to provide coverage. Automated sensor placement optimization systems should determine where to place sensors in order to maximize coverage and minimize cost. But the limitation of time and computer power meant that only select scenarios could be evaluated, and therefore results still were not thorough enough for the high expectations of the security industry today.

Solution

Genetic Algorithms (GA), a modern optimization technique, is well suited to the task of locating solutions within a complex system while maximizing a well-specified goal. Effective sensor placement can be achieved through GAs as they search through the haystack of possible sensor placement plans in order to find the few that do the best job. However, in order to do this, the optimization algorithm must search through tens of thousands or even tens of millions of possible sensor plans as it zeroes in on the most promising candidates. As each plan may take several seconds or more to evaluate, locating an optimal plan could take days on state-of-the-art workstations.

Watchman refines the placement of 10 sensors to maximize coverage (in red) of a San Jose city block.

Parabon's WatchmanSM applies the power of the Frontier Grid Platform to this problem, and in so doing is able to provide results in minutes or hours depending on the depth of the analysis. Taking advantage of the Origin SDK for Evolutionary Computation, Watchman applies Genetic Algorithms to search for optimal sensor plans based on environment, available sensor profiles, and any other parameters specified by a user. Watchman is an intuitive web-based application accessed through the Frontier Dashboard, available via any standard computer with internet access. Further, Watchman is a "mashup" that combines Google Maps, the computational power of the Frontier Grid Platform, and models provided by PLW Modelworks, LLC. You simply click on a Google Map, specify your area of interest, launch an optimization, and let Watchman work. Later come back to the Watchman job status page at any time from any computer or browser-enabled cell phone and monitor the progress of the job and view the results.

Results

As Watchman solutions evolve, sensor placement is overlaid on a Google Map. Sensor coverage increases until the point that a near-optimal solution has been reached, and final results are displayed. In a matter of hours, Watchman can generate optimal placement for 10 cameras covering several downtown city blocks, taking into account all of the details of a city environment.

Future Endeavors

As the optimization algorithms in Watchman are universal, the application has proven highly adaptable and easily customizable on all levels, allowing the sensor models, the rules and constraints of sensor placement, and the nature of the optimization goals to be carefully tuned to the needs of a particular application.