Optimized Passive Sonar Placement to Allow Improved Interdiction

摘要

The Art Gallery Problem (AGP) is the name given to a constrained optimization problem meant to determine the maximum amount of sensor coverage while utilizing the minimum number of resources. The AGP is significant because a common issue among surveillance and interdiction systems is obtaining an understanding of the optimal position of sensors and weapons in advance of enemy combatant maneuvers. The implication that an optimal position for a sensor to observe an event or for a weapon to engage a target autonomously is usually very clear after the target has passed, but for autonomous systems the solution must at least be conjectured in advance for deployment purposes. This applies the AGP as a means to solve where best to place underwater sensor nodes such that the amount of information acquired about a covered area is maximized while the number of resources used to gain that information is minimized. By phrasing the ISR/interdiction problem this way, the issue is addressed as an instance of the AGP. The AGP is a member of a set of computational problems designated as non-deterministic polynomial-time (NP)-hard. As a member of this set, the AGP shares its members' defining feature, namely that no one has proven that there exists a deterministic algorithm providing a computationally-tractable solution to the AGP within a finite amount of time. At best an algorithm meant to solve the AGP can asymptotically approach perfect coverage with minimal resource usage but providing perfect coverage would either break the minimal resource usage constraint or require an exponentially-growing amount of time. No perfectly-optimal solution yet exists to the AGP, however, approximately optimal solutions to the AGP can approach complete area or barrier coverage while simultaneously minimizing the number of sensors and weapons utilized. A minimal number of underwater sensor nodes deployed can greatly increase the Mean Time Between Operational Failure (MTBOF) and logistical footprint. The resulting coverage optimizes the likelihood of encounter given an arbitrary sensor profile and threat from a free field statistical model approach. The free field statistical model is particularly applicable to worst case scenario modeling in open ocean operational profiles where targets to do not follow a particular pattern in any of the modeled dimensions. We present an algorithmic testbed which shows how to achieve approximately optimal solutions to the AGP for a network of underwater sensor nodes with or without effector systems for engagement while operating under changing environmental circumstances. The means by which we accomplish this goal are three-fold: 1) Develop a 3D model for the sonar signal propagating through the underwater environment 2) Add rigorous physics-based modeling of environmental events which can affect sensor information acquisition 3) Provide innovative solutions to the AGP which account for the environmental circumstances affecting sensor performance.