Real-time mission adaptable route planner
US6259988A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jul 20, 1998 |
| Grant date | Jul 10, 2001 |
| Priority date | — |
| Expiry date | Jul 20, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q30/0284
- WIPO fieldMeasurement
- WIPO sectorInstruments
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 discar…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.