Real-time mission adaptable route planner

Abstract

A hybrid of grid-based and graph-based search computations, together with provision of a sparse search technique effectively limited to high-probability candidate nodes provides accommodation of path constraints in an optimization search problem in substantially real-time with limited computational resources and memory. A grid of best cost (BC) values are computed from a grid of map cost (MC) values and used to evaluate nodes included in the search. Minimum segment/vector length, maximum turn angle, and maximum path length along a search path are used to limit the number of search vectors generated in the sparse search. A min-heap is preferably used as a comparison engine to compare cost values of a plurality of nodes to accumulate candidate nodes for expansion and determine which node at the terminus of a partial search path provides the greatest likelihood of being included in a near-optimal complete solution, allowing the search to effectively jump between branches to carry out further expansion of a node without retracing portions of the search path. Capacity of the comparison engine can be limited in the interest of expediting of processing and values may be excluded or discarded therefrom. Other constraints such as approach trajectory are accommodated by altering MC and BC values in a pattern or in accordance with a function of a parameter such as altitude or by testing of the search path previously traversed.