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