Minimum Risk Path Planning for Submarines through a Sensor Field

Abstract

One of the basic necessities in combat operations is the planning of paths for the traversal ofmilitary hardware and vehicles through adversarial environments. Typically, while still meetingmission objectives, the vehicle is required to arrive at a pre-described target while minimizingits risk exposure to enemy defence systems. As well as the technological constraints of thevehicle, such as fuel capacity, additional restrictions that can be imposed on the path includelimits on travelling time and route length. We specifically look at the problem of determining anoptimal submarine transit path for a submarine through a field of sonar sensors, subject to a totaltime and final position constraint. The path should be designed so as to minimize the overallprobability of detection. The strategy we propose involves a two stage approach. The first stageinvolves a discretized approximation of the problem by first constructing a grid like networkover the region. Possible paths are then restricted to the movement between the knots points (i.e.nodes) of this grid. In other words, the approximate problems involve finding the most costeffective paths through a network, subject to a total time constraint. What we have therefore is aConstrained Shortest Path Problem (CSPP). To solve the resulting CSPP we develop anefficient network heuristic method that uses a parameterization of the edge weights of thenetwork and the application of Dijkstra’s Algorithm. The second stage involves thedevelopment of an optimal control model, by introducing a very simple dynamical model for thevessel’s movements, and a solution procedure that utilizes the solution obtained in the first stageas a starting point. The optimal control model for our submarine transit path problem is in fact adiscrete valued control problem where the precise times between speed and heading switchesneed to be determined. We show that this optimal control problem can be readily solved withthe use of a technique known as the Control Parameterization Enhancing Transform (CPET),which, via a simple transformation, puts the problem into readily solvable standard canonicalform by standard optimal control software. Various aspects of our proposed method arediscussed. These include, among other things, the effects of different degrees of coarseness ofdiscretization used in the problem. A solution of the CSPP will only provide a good initial pointfor the optimal control problem if a sufficiently refined network grid model is used. We alsoshow how the subsequent number of switching points used within the optimal control phase canmake a significant difference on the final solution obtained. Computational results are presented supporting the use of our methodology.