Applying Evolutionary Computation to Route Planning

Period of Performance: 12/14/1998 - 06/14/1999


Phase 1 SBIR

Recipient Firm

Natural Selection, Inc.
3333 N. Torrey Pines Ct., #200
La Jolla, CA 92037
Principal Investigator

Research Topics


Missile route planning has typically been performed by human or heuristics. As such, it has proven inefficient and unable to provide solutions to complex real-world problems. The aerial asset assignment problem (N missiles to M targets) is in the class of NP-complete problems, hence the difficulty in obtaining optimal solutions in a reasonable amount of computational time. Applicable constraints reduce the size of the search space but typically only by a few orders of magnitude. Significant improvements in automated aerial asset route planning can be achieved through the innovative combination of evolutionary computation with the Valuated State Space Approach for quantifying the mission to be accomplished. The inherent flexibility of this approach facilitates planning and replanning on-the-fly, and is extensible to other problem domains.