Maneuver generation program and method

• US 6,324,472 B1
• Filed: 11/20/2000
• Issued: 11/27/2001
• Est. Priority Date: 07/15/1997
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: OʼShea, Michael J.
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US09/716,489
• Time in Patent Office: 372 Days
• Field of Search: 701/25, 701/207, 701/211, 701/214, 701/206, 701/210, 701/300, 340/988, 340/990, 340/995, 342/357.01, 731/78.R
• US Class Current: 701/211
• CPC Class Codes: G01C 21/3626 Details of the output of route guidance instructions traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968

Abstract

A maneuver generation program for a computer-based navigation system. The navigation system provides a user with a series of maneuvering instructions to go from a first location to a second location in a geographic area. The series of maneuvering instructions are derived from a list of data entities that represent a route from the first location to the second location. The list of data entities includes data that represent a plurality of locations along the route at which maneuvering instructions may be provided. The maneuver generation program determines one and preferably no more than one maneuver type selected from a predetermined plurality of maneuver types for each location of the plurality of locations along the route. The maneuver generation program performs a series of tests upon data corresponding to each location. Each of the plurality of maneuver types is characterized by a unique set of tests selected from a predetermined superset of tests. A maneuver type is associated with a location if data corresponding to the location pass all the tests in the set of tests that characterize the maneuver type. The maneuver type associated with the location is used in providing a maneuvering instruction related to the location to the user by the navigation application.

Claims

1. A method of operation for a computer-based navigation system that provides guidance to a user of the system for traveling along a route from an origin to a destination in a geographic area, the method comprising:

receiving a list of data entities that represent the route in said geographic area between the origin and the destination, wherein said list of data entities includes data that represent a plurality of locations along said route;

for each location of said plurality of locations along said route, determining which one maneuver type, if any, selected from a predetermined plurality of maneuver types is appropriate for said location, wherein said step of determining comprises;

performing a series of tests upon data corresponding to said location; and

if a positive result is obtained in all the tests associated with one set of tests selected from a predetermined superset of tests, associating a maneuver type associated with said one set of tests with said location; and

proving said guidance as a series of maneuver instructions based on the maneuver types associated with each of the locations.

2. The method of claim 1 wherein said maneuvering instructions include required instructions and advisories.

3. The method of claim 1 wherein no maneuver type is associated with a location if all the positive results to tests fail to provide one set of tests for which all the tests associated therewith have positive results.

4. The method of claim 1 wherein said predetermined plurality of maneuver types include a first group and a second group and further wherein each maneuver type of the first group is associated with a set of tests, no subset of which defines another of the sets of tests associated with another of the maneuver types in the first group, and

wherein each of the maneuver types in the second group is defined by a set of tests a subset of which may define another of the maneuver types in the first group and the second group, and

wherein execution of the sets of tests associated with the second group are ordered relative to the sets of tests associated with the first group.

5. The method of claim 1 wherein said steps of receiving, determining, performing, and associating are performed on a server connected to the Internet.

6. The method of claim 1 wherein said steps of receiving, determining, performing, and associating are performed in a networked environment.

7. The method of claim 1 wherein the locations are nodes.

8. The method of claim 1 wherein the computer-based navigation system is a hand-held unit.

9. A method of operation for a maneuver generation program to provide guidance as a series of maneuver instructions for traveling a route from an origin to a destination in a geographic area, said series of maneuvers instructions derived from a data list representing said route, wherein said method comprises:

providing a table that defines a superset of tests and a plurality of maneuver types, wherein each maneuver type of said plurality of maneuver types is associated with a set of tests selected from said superset of tests; and

executing at least some tests of said superset of tests until all the tests in a set of tests corresponding to one of said plurality of maneuver types are satisfied.

10. The method of claim 9 wherein said step of executing is performed for each location along said route at which a maneuver is possible.

11. The method of claim 9 wherein said step of executing is performed for each node along said route.

12. The method of claim 9 further comprising:

for each location along said route at which all the tests in a set of tests corresponding to one of said plurality of maneuver types are satisfied, forming a maneuver data structure that includes data corresponding to said location.

13. The method of claim 12 further comprising:

providing an output comprised of a plurality of maneuver data structures.

14. The method of claim 13 wherein each maneuver instruction in said series of maneuver instructions is formed from a corresponding one of said plurality of maneuver data structures.

15. The method of claim 9 wherein said maneuvering instructions are provided over the Internet.

16. A method of providing a customizable set of maneuver types in a navigation system, the method comprising:

providing a table defining a superset plurality of tests to be applied to data representing locations along a route between a first location and a second location in a geographic area, wherein said table defines a first plurality of maneuver types, each of which is associated with a unique subset of tests, wherein each subset of tests is selected from said superset plurality of tests;

accepting a user-defined proposed subset of at least one test selected from said superset plurality of tests, said user-defined proposed subset defining a proposed new maneuver type; and

comparing said user-defined proposed subset of at least one test to each subset of tests associated with the first plurality of maneuver types in said table to determine the uniqueness of the user-defined proposed subset of tests defining said proposed new maneuver type.

17. The method of claim 16 further comprising the step of:

accepting said proposed new maneuver type if said user-defined proposed subset of tests is unique based upon said comparison to each subset of tests associated with the first plurality of maneuver types in said table.

18. The method of claim 16 wherein the step of accepting said proposed new maneuver type further comprises the step of:

adding the proposed new maneuver type and the user-defined proposed subset of tests associated therewith to said table.

19. The method of claim 16 further comprising the steps of:

if said user-defined proposed subset of tests is not unique based upon said comparison to at least one subset of tests associated with the first plurality of maneuver types, establishing an order in which the subset of tests defining the proposed new maneuver type are to be executed relative to the subsets of tests associated with the first plurality of maneuver types; and

accepting said proposed new maneuver type.

20. The method of claim 16 further comprising the steps of:

accepting a user-defined proposed new test; and

adding said user-defined proposed new test to said superset plurality of tests by augmenting said table.