Cruise missile mission planning: A heuristic algorithm for automatic path generation

This manuscript presents a heuristic algorithm based on geometric concepts for the problem of finding a path composed of line segments from a given or igin to a given destination in the presence of polygonal obstacles. The bas ic idea involves constructing circumscribing triangles around the obstacles to be avoided. Our heuristic algorithm considers paths composed primarily of line segments corresponding to partial edges of these circumscribing tri angles, and uses a simple branch-and-bound procedure to find a relatively s hort path of this type. This work was motivated by the military planning pr oblem of developing mission plans for cruise missiles, but is applicable to any two-dimensional path-planning problem involving obstacles.