Method for establishing optimized paths of movement of vehicles
First Claim
1. A method for planning an optimized routing for a vehicle, said method comprising:
- discretizing a region between a starting point and a destination by establishing a first node grid;
establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and
determining a predeterminable region around the first polygonal path;
establishing within said predeterminable region a more finely divided second node grid; and
from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus for planning vehicle trajectories or routing in which a first optimized route between a starting point and a destination is established with regard to a first, relatively coarse node grid, using known techniques. In order to further refine route selection, a second relatively finer node grid is then established within a predeterminable area or volume that is adjacent yo the first optimized route, along its length. The latter finer node grid is then used to establish a second enhanced polygonal path from among the possible polygonal paths between the starting and destination points according to the finer node grid, once again using a known optimization technique.
-
Citations
17 Claims
-
1. A method for planning an optimized routing for a vehicle, said method comprising:
-
discretizing a region between a starting point and a destination by establishing a first node grid;
establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and
determining a predeterminable region around the first polygonal path;
establishing within said predeterminable region a more finely divided second node grid; and
from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer readable medium encoded with a computer program that includes instructions which, when loaded into a computer, cause the computer to perform an optimized route selection for a vehicle, according to the following steps:
-
discretizing a region between a starting point and a destination by establishing a first node grid;
establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and
determining a predeterminable region around the first polygonal path;
establishing within said predeterminable region a more finely divided second node grid; and
from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid. - View Dependent Claims (9, 10, 11, 12, 17)
-
-
13. A system for planning an optimized routing for a vehicle, said system comprising:
-
a computer;
a memory contained in said computer and having stored therein data which are indicative of parameters that influence desirability of possible alternative routes; and
a computer readable medium which is accessible by said computer, and which has encoded therein a computer program which, when loaded into said computer, causes it to perform an optimized route selection for a vehicle, including discretizing a region between a starting point and a destination by establishing a first node grid;
establishing a first polygonal path which is optimal with regard to at least one predetermined optimization parameter, from among possible polygonal paths between the starting point and destination and extending over the first node grid; and
determining a predeterminable region around the first polygonal path;
establishing within said predeterminable region a more finely divided second node grid; and
from among possible paths between the starting point and destination, establishing a second polygonal path which is optimized with respect to the predetermined optimization parameter based on nodes contained in the second node grid. - View Dependent Claims (14, 15, 16)
-
Specification