Shortest Path Algorithms on Grid Graphs with Applications to Strike Planning.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 12, 1997
- Accession Number
- ADA321664
Entities
People
- J. L. Kennington
- K. H. Lewis
- R. V. Helgason
Organizations
- Southern Methodist University