Shortest Path Algorithms on Grid Graphs with Applications to Strike Planning

摘要

This document contains three technical reports related to the problem ofdeveloping 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.