The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Nov. 05, 2002
Filed:
Aug. 11, 1999
Ali Boroujerdi, Springfield, VA (US);
Jeffrey K. Uhlmann, Alexandria, VA (US);
The United States of America as represented by the Secretary of the Navy, Washington, DC (US);
Abstract
A system is disclosed for computing least cost paths under hard constraints such as turn angle constraints. In an explicit embodiment, a transformation is performed on a graph representation of an optimization problem to generate a transformed graph incorporating the hard constraint in the edges of the transformed graph. Unconstrained optimization is then performed on the transformed graph using an implementation of Dijkstra's algorithm. The structure of the transformed graph lends itself to searching for an optimal solution using data structures of the vertices of the original graph. In an implicit embodiment, the searching is performed using the data structures but without explicitly generating the transformed graph. The enhanced performance of the invention is sufficient to allow for dynamic re-routing of vehicles in uncertain or changing environments.