초록 ▼

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

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.

대표청구항 ▼

1. A method for finding a constrained least-cost path from a source vertex to a sink vertex in a directed graph representing a physical system, the graph having multiple vertices located between the source vertex and the sink vertex, each vertex of the graph having a corresponding searchable data st

1. A method for finding a constrained least-cost path from a source vertex to a sink vertex in a directed graph representing a physical system, the graph having multiple vertices located between the source vertex and the sink vertex, each vertex of the graph having a corresponding searchable data structure identifying a set of adjacent vertices, each vertex of the graph being connected by an edge to another vertex, and each edge having an associated cost, the method comprising:(a) inserting a data item with an associated priority of zero corresponding to the source vertex into an initially empty priority queue; (b) retrieving and deleting from the priority queue a minimum priority data item indicating a current vertex of the graph and having an associated priority; (c) identifying from the corresponding searchable data structure each vertex of the graph adjacent to the current vertex and reachable therefrom in accordance with a predetermined condition; (d) deleting an identified adjacent vertex from the corresponding searchable data structure; (e) inserting into the priority queue a corresponding data item with an associated priority for the identified adjacent vertex without replacing any data item associated with the identified adjacent vertex that is already in the priority queue; (f) repeating steps (b) through (e) until the current vertex is the sink vertex, and (g) when the current vertex is the sink vertex, determining the least cost-path from the minimum priority of the data item associated with the sink vertex.