Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-11-16
2001-10-02
Issing, Gregory C. (Department: 3662)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
Reexamination Certificate
active
06298303
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a system and method for route calculation in a navigation application program.
Computer-based navigation systems are able to provide end-users, such as vehicle drivers and as well as others, with various navigating functions and features. For example, some navigation systems are able to determine an optimum route to travel by roads between locations in a geographic region. Using input from the end-user, and optionally from equipment that can determine the end-user's physical location (such as a GPS system), a navigation system can examine various routes between two locations to determine an optimum route to travel from a starting location to a destination location in the geographic region. The navigation system may then provide the end-user with information about the optimum route in the form of instructions that identify the maneuvers required to be taken by the end-user to travel from the starting location to the destination location. The navigation system may be located in an automobile and the instructions may take the form of audio instructions that are provided as the end-user is driving the route. Some navigation systems are able to show detailed maps on computer displays that outline routes to destinations, the types of maneuvers to be taken at various locations along the routes, locations of certain types of features, and so on.
In order to provide these and other navigating functions, present navigation systems include navigation application software programs and use one or more detailed databases that include data which represent physical features in geographic regions. The detailed database(s) includes data which represent the road network in a region, including the roads and intersections in the region and information about the roads and intersections, such as turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads, and so on. Further, the data may include information about points-of-interest. Presently, the collection of such geographic data and the provision of such data in a computer-usable database format are provided by Navigation Technologies of Rosemont, Ill.
Present navigation application programs and navigation systems are able to provide many advantages and many useful features. However, there continues to be a need for improvement. One area in which there is need for improvement relates to providing the end-user with better and more detailed navigation instructions at an initial stage of a route. Another area in which there is need for improvement relates to providing the end-user with better instructions as the desired destination is approached. Still another area in which navigation systems can be improved relates to providing the end-user with better instructions as to how to get back on a route to a desired destination when the end-user either accidentally or deliberately deviates from a previously calculated route. Still another area in which there is a need for improvement relates to handling of intermediate stops along a route. For example, an end-user will often want to make one or more intermediate stops between a starting location and a final destination. Thus, there is a need for a navigation system application that can not only calculate a route between two locations, but also that can calculate quickly and effectively a route that includes stops at one or more intermediate locations along the way between a starting location and a destination. A further area in which there is need for improvement relates to provision of a universal route calculation module or tool that can be readily used in a variety of different software and hardware environments without the need for extensive revisions and customizations to the tool.
Accordingly, it is an objective to provide a navigation application that provides improved route calculation features to an end-user.
SUMMARY OF THE INVENTION
To address the above concerns, according to one aspect of the present invention, there is provided a program and method for a route calculation tool for use with a navigation system and used with a map database. The route calculation tool is adapted to find at least one solution route between a first location on a road network in a geographic region and a second location on the road network in the geographic region. The route calculation tool includes a first search tree associated with the first location and a second search tree associated with the second location. Each of the search trees is adapted to hold gates. Each of the gates represents a physical position on the road network and a direction from the position to another location along a path on the represented road network. The route calculation tool also includes a priority queue associated with each of the search trees. Starting with one of the search trees, the priority queue assigns a priority to each of the gates based upon an evaluation by a search algorithm. A search engine expands the gate that has the highest priority to determine one or more successor gates thereof and compares the one or more successor gates so formed to one or more gates in the other search tree. The process of growing either or both search trees by expanding the gate that has the highest priority in its respective search tree is continued until a gate in the search tree corresponds to at least one of the one or more gates in the other search tree.
REFERENCES:
patent: 4570227 (1986-02-01), Tachi et al.
patent: 4763270 (1988-08-01), Itoh et al.
patent: 4782447 (1988-11-01), Uneo et al.
patent: 4794528 (1988-12-01), Hirose et al.
patent: 4796189 (1989-01-01), Nakayama et al.
patent: 4812990 (1989-03-01), Adams et al.
patent: 4926336 (1990-05-01), Yamada
patent: 4937753 (1990-06-01), Yamada
patent: 5031104 (1991-07-01), Ikeda et al.
patent: 5041983 (1991-08-01), Nakahara et al.
patent: 5103400 (1992-04-01), Yamada et al.
patent: 5168452 (1992-12-01), Yamada et al.
patent: 5184303 (1993-02-01), Link
patent: 5187667 (1993-02-01), Short
patent: 5204817 (1993-04-01), Yoshida
patent: 5262775 (1993-11-01), Tamai et al.
patent: 5272638 (1993-12-01), Martin et al.
patent: 5291412 (1994-03-01), Tamai et al.
patent: 5291413 (1994-03-01), Tamai et al.
patent: 5291414 (1994-03-01), Tamai et al.
patent: 5303159 (1994-04-01), Tamai et al.
patent: 5311434 (1994-05-01), Tamai
patent: 5369588 (1994-11-01), Hayami et al.
patent: 5371678 (1994-12-01), Nomura
patent: 5410485 (1995-04-01), Ichikawa
patent: 5428545 (1995-06-01), Maegawa et al.
patent: 5442349 (1995-08-01), Inoue et al.
patent: 5459667 (1995-10-01), Odagaki et al.
patent: 5467276 (1995-11-01), Tsuyuki
patent: 5475387 (1995-12-01), Matsumoto
patent: 5502640 (1996-03-01), Yagyu et al.
patent: 5506774 (1996-04-01), Nobe et al.
patent: 5506779 (1996-04-01), Kanki
patent: 5508930 (1996-04-01), Smith, Jr.
patent: 5513110 (1996-04-01), Fujita et al.
patent: 5519619 (1996-05-01), Seda
patent: 5521826 (1996-05-01), Matsumoto
patent: 5550538 (1996-08-01), Fujii et al.
patent: 5557522 (1996-09-01), Nakayama et al.
patent: 5559511 (1996-09-01), Ito et al.
patent: 5608635 (1997-03-01), Tamai
patent: 5612881 (1997-03-01), Moroto et al.
patent: 5638280 (1997-06-01), Nishimura et al.
patent: 5899955 (1999-05-01), Yagyuet al.
patent: 5938720 (1999-08-01), Tami
Khavakh Asta
McDonough William
Voloshin Oleg
Wang Yaoguang
Issing Gregory C.
Kaplan Lawrence M.
Kozak Frank J.
Navigation Technologies Corp.
LandOfFree
Method and system for route calculation in a navigation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for route calculation in a navigation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for route calculation in a navigation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2599769