Accession Number : ADA321664

Title :   Shortest Path Algorithms on Grid Graphs with Applications to Strike Planning.

Descriptive Note : Final rept. 1 Feb 96-31 Jan 97,

Corporate Author : SOUTHERN METHODIST UNIV DALLAS TX DEPT OF COMPUTER SCIENCE AND ENGINEERING

Personal Author(s) : Helgason, R. V. ; Kennington, J. L. ; Lewis, K. H.

PDF Url : ADA321664

Report Date : 12 FEB 1997

Pagination or Media Count : 101

Abstract : This document contains three technical reports related to the problem of developing mission plans for a cruise missile. The first report presents algorithms for finding the safest path through a graph and for finding the safest corridor in a grid graph. The second report presents anew effective algorithm for finding a path from a designated origin to a designated destination which avoids all threat regions represented by circles. This algorithm does not require the imposition of a grid over the region and avoids threats by moving along the edges of triangles which enclose the threats. The third report gives an algorithm which obtains short paths which satisfy some side restriction on the probability of success. These paths may take short cuts through the threat regions as long as the side constraint is satisfied.

Descriptors :   *GUIDED MISSILE TRAJECTORIES, *GRAPHS, *PATHS, *CRUISE MISSILES, *PROJECTIVE GEOMETRY, ALGORITHMS, THREATS, GRIDS, REGIONS, SHORT RANGE(TIME), PLANNING, MISSIONS, AVOIDANCE, STRIKE WARFARE, CIRCLES, TRIANGLES.

Subject Categories : Numerical Mathematics
      Guided Missile Traj, Accuracy and Ballistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE