Multicriteria vehicle route-planning using parallel A * search
Michael S. Gudaitis, Gary B. Lamont, A.J. Terzuoli · 1995
Mission Route Planning involves evaluating multiple criteria to select an optimal vehicle route through an environment which may be unfriendly. The problem is NP-Complete for the bicriteria case, but reduces to O(n2) if the criteria are combined into a single cost function and the route maintains an optimal substructure. In this application, criteria for distance travelled and radar exposure are combined into a single cost function for route evaluation. Radar calculations are performed dynamically. A specific parallel A * algorithm performs independent searches through 3-D terrain in order to select optimal routes. An implementation on the Intel Paragon provides fast execution of 4 minutes or less for aircraft vehicle scenarios with 15 radars. Measured performance is generally superior to previous computational experience.