STEALTH TERRAIN NAVIGATION

A method for solving visibility-based terrain path planning problems using massively parallel hypercube machines is proposed. A typical example is to find a path that is hidden from moving adversaries. This kind of problem can be generalized as a time-varying constrained path planning problem, and is proven to be computationally hard. The method we propose is an approximation based on both temporal and spatial sampling. Since a 2-D grid cell representation of terrain can be embedded into a hypercube with extra links for fast communication, our method can be very efficient when implemented on hypercube machines. The time complexity is in general O(T x E x log N) using O(N) processors, where T is the number of temporal samples, E is the number of adversary agents, and N is the number of grid cells on the terrain. It is also shown that the method can be applied to several realistic problems with a variety of path optimization. All algorithms have been implemented on the Connection Machine CM-2 and results of experiments are presented.