Patent ID: 7467154

Claim:
A computer-implemented method of generating an optimal path through a lattice, the lattice comprising at least a start point and an end point, the method comprising: performing a search on the lattice to identify a first path through the lattice; determining number of points (N) in the identified first path; determining a midpoint (MP) of the first path where MP=N/2, if N is an odd number the determined midpoint value is rounded up to a next integer; designating a first portion of the lattice to be the area covered between the start point and the determined midpoint, and a second portion of the lattice to be the area covered between the determined midpoint and the end point; performing a search procedure on the first portion of the lattice to identify a second path; performing a search procedure on the second portion of the lattice to identify a third path; performing a search procedure on a third portion of the lattice to identify a fourth path, wherein the third portion overlaps with the first portion and the second portion, the third portion starts approximately one-fourth from the start point to the end point of the first path and ends approximately three-fourth's from the start point to the end point of the first path, such that the third portion encompasses the middle distance of the first path; iterating, while a condition is true, the designation of the first and second portions of the lattice and the search procedures to identify the second path, the third path, and the fourth path; and returning an optimal path though the lattice, the optimal path is a combination of the second path, the third path, and the fourth path.