|
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 abstract 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 nondeterministic
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.
|
