Maneuver generation program and method

• US 6,199,013 B1
• Filed: 07/15/1997
• Issued: 03/06/2001
• Est. Priority Date: 07/15/1997
• Status: Expired due to Term

• 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:
  US08/893,201
• Time in Patent Office: 1,330 Days
• Field of Search: 701/25, 701/26, 701/200, 701/206, 701/207, 701/210, 701/211, 701/214, 701/300, 340/988, 340/990, 340/995, 731/78.R, 342/357.01
• 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. In a computer-based navigation system that provides route guidance to a user of the system, said route guidance comprised of a series of maneuver instructions to be provided to the user for the user to go from a first location in a geographic area to a second location in said geographic area, said series of maneuver instructions derived from a list of data entities representing a route in said geographic area between said first location and said second location, and wherein said list of data entities includes data representing a plurality of locations along said route at which maneuver instructions may be provided, a maneuver generation program comprising:

for each location of said plurality of locations along said route at which a maneuver instruction may be provided, means for determining one maneuver type selected from a predetermined plurality of maneuver types; and

means for performing a series of tests upon data corresponding to said location of said plurality of locations wherein each of said plurality of maneuver types is characterized by a unique set of tests selected from a predetermined superset of tests wherein a positive result in each test in any of said sets of tests characterizes said location of said plurality of locations with the maneuver type associated with said set of tests.

2. The invention of claim 1 wherein failure of any one test of said series of tests eliminates a maneuver type in which said one test is included in the unique set of tests that characterized said maneuver type.

3. The invention of claim 1 wherein said maneuver generation program further comprises:

means for outputting a plurality of maneuver descriptions wherein each maneuver description includes a maneuver ascertained by said determining means.

4. The invention of claim 3 wherein said means for outputting a plurality of maneuver descriptions provides said maneuver descriptions incrementally.

5. The invention of claim 3 further comprising:

a direction generation program that receives said plurality of maneuver descriptions from said maneuver generation program and applies a template to each maneuver description of said plurality of maneuver descriptions to output said plurality of maneuver instructions.

6. The invention of claim 5 wherein said direction generation program outputs said plurality of maneuver descriptions incrementally.

7. The invention of claim 1 wherein each data entity in said list of data entities comprises a segment data entity that represents a portion of a roadway in said geographic area and wherein each segment data entity has associated therewith a node data entity at each end thereof, and wherein said data representing a plurality of locations along said route at which maneuver instructions may be provided comprise node data entities at each end of the segment data entities that comprise said list of data entities representing said route.

8. The invention of claim 1 wherein failure of at least one test in each set of tests that characterize said maneuver types results in no maneuver instruction being provided for said location.

9. The invention of claim 1 further comprising:

means for providing multiple maneuver instructions when adjacent locations of said plurality of locations along said route at which a maneuver instruction may be provided are close together.

10. The invention of claim 1 wherein said maneuver instructions include advisory-type instructions and maneuver-type instructions.

11. The invention of claim 1 wherein said determining means is further characterized as comprising:

for each location of said plurality of locations along said route at which a maneuver instruction may be provided, means for determining not more than one maneuver type selected from the predetermined plurality of maneuver types.

12. The invention of claim 1 wherein said determining means is further characterized as comprising:

for each location of said plurality of locations along said route at which a maneuver instruction may be provided, means for determining not more than one maneuver type characterizing said location wherein said one maneuver type is selected from the predetermined plurality of maneuver types; and

means for determining that no maneuver instruction for said location is required when said series of tests does not identify any of said plurality of maneuver types as characterizing said location.

13. In a computer-based navigation system that provides route guidance to a user of the system, said route guidance comprised of a series of maneuver instructions to be provided to the user for the user to go from a first location in a geographic area to a second location in said geographic area, said series of maneuver instructions derived from a list of data entities representing a route in said geographic area between said first location and said second location, and wherein said list of data entities includes data representing a plurality of locations along said route at which maneuver instructions may be provided, a maneuver generation program comprising:

for each location of said plurality of locations along said route at which a maneuver instruction may be provided, means for determining one maneuver type selected from a predetermined plurality of maneuver types; and

means for performing a series of tests upon data corresponding to said location of said plurality of locations wherein each of said plurality of maneuver types is characterized by a set of tests selected from a predetermined superset of tests,

wherein a positive result in each test in any of said sets of tests characterizes said location of said plurality of locations with the maneuver type associated with said set of tests,

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 set 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.

14. A program stored on a computer-readable medium for providing a customizable set of maneuver types comprising:

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;

means for 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

means for 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 user-defined proposed subset of tests defining said proposed new maneuver type.

15. The invention of claim 14 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.

16. The invention of claim 14 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.

17. The invention of claim 14 further comprising the step of:

if said user-defined proposed subset of tests is not unique based upon said comparison to each 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.

18. The invention of claim 14 further comprising the step of:

means for 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.

19. In a navigation system that provides route guidance to a user of the system, said route guidance comprised of a series of maneuvers to be executed to go from a first location in a geographic area to a second location in said geographic area, said series of maneuvers derived from a list of data entities representing portions of roadways in said geographic area between said first location and said second location, a route guidance program comprising:

means for identifying in said list data indicative of locations in said geographic area where maneuvers may be required;

means for performing a series of tests upon said data indicative of locations in said geographic area where maneuvers may be required to determine a unique maneuver type from a plurality of different maneuver types to be associated with said data,

wherein the series of tests associated with each separate maneuver type are selected from a plurality of tests;

wherein failure to pass any one of said series of tests associated with a particular maneuver type eliminates the particular maneuver type;

the series of tests associated with each separate maneuver type uniquely define the associated maneuver types from other maneuver types.

20. A maneuver generation program stored on a computer-readable medium for use with a route guidance program that provides a series of maneuver instructions for going from a first location in a geographic area to a second location in said geographic area, said series of maneuvers instructions derived from a list of data entities representing portions of roadways in said geographic area between said first location and said second location, wherein said maneuver generation program comprises:

a table defining a superset plurality 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 plurality of tests; and

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

21. The maneuver generation program of claim 20 further comprising:

an output comprised of the one of said plurality of maneuver types all the tests of which are satisfied.

22. The maneuver generation program of claim 20 wherein said list of data entities includes data representing a plurality of locations along said route at which maneuver instructions may be provided, and wherein said programming routine further comprises:

means for executing at least some tests of said superset plurality of tests on data corresponding to each of said locations.

23. The maneuver generation program of claim 22 further comprising:

an output comprised of a list including the maneuver types identified by said programming means with respect to each of said locations.

24. The maneuver generation program of claim 23 wherein said list of maneuver types is returned incrementally.

25. The maneuver generation program of claim 22 wherein said programming routine ceases to execute any more tests of said superset plurality of tests with respect to each location when all the tests in a set of tests corresponding to one of said plurality of maneuver types are satisfied for the location.

26. The maneuver generation program of claim 20 wherein said list of data entities includes data representing a plurality of locations along said route at which maneuver instructions may be provided, and

wherein said programming routine executes at least some tests of said superset plurality of tests upon data corresponding to each of said locations,

wherein a maneuver type is associated with a location of said plurality of locations when all the tests in a set of tests corresponding to one of said plurality of maneuver types are satisfied by said data representing the location,

wherein no maneuver type is associated with a location of said plurality of locations when all the tests included in all the plurality of maneuver types have been executed and each of the sets of tests associated with each of the plurality of maneuver types includes at least one test that is not satisfied, and

wherein said maneuver generation program provides an output comprised of a list including the maneuver types associated with the locations at which data corresponding thereto satisfied all the tests in a set of tests corresponding to one of said plurality of maneuver types.

27. The invention of claim 20 wherein table is adaptable in size and further comprising a programming routine for modifying said table, said programming routine stored on a computer readable medium, said programming routing for modifying said table comprising:

means for changing the maneuver types in the table; and

means for checking the validity of the changes made to the maneuver types in the table.

28. The maneuver generation program of claim 20 wherein each of said set of tests associated with each of said plurality of maneuver types includes no subset of tests corresponding to the set of tests associated with another of the plurality of maneuver types.

29. A maneuver generation program stored on a computer-readable medium comprising:

means for accepting data representing a location along a route at which a maneuver instruction may be provided;

means for performing a series of tests using said data; and

means for determining a maneuver type to characterize said location upon passage of a unique subset of said series of tests, said unique subset associated with said maneuver type, said unique subset of tests selected from a superset of tests used to define a plurality of different maneuver types.

30. The invention of claim 29 wherein failure of any one test of said series of tests eliminates a maneuver type in which said one test is included in the unique set of tests that characterized said maneuver type.

31. The invention of claim 29 wherein said maneuver generation program further comprises:

means for outputting a maneuver description including the maneuver type ascertained by said determining means.

32. The invention of claim 31 further comprising:

a direction generation program that receives said maneuver description from said maneuver generation program and applies a template to said maneuver description to output a maneuver instruction.

33. The invention of claim 29 wherein failure of at least one test in each set of tests that characterize said plurality of different maneuver types results in no maneuver instruction being provided for said location.

34. The invention of claim 29 further comprising:

means for providing multiple maneuver instructions when adjacent locations along said route at which a maneuver instruction may be provided are close together.

35. The invention of claim 29 wherein said maneuver instructions include advisory-type instructions and maneuver-type instructions.

36. The invention of claim 29 wherein said determining means is further characterized determining not more than one maneuver type selected from the plurality of maneuver types.