Electronic route navigation method in a road network on a map

• US 9,784,589 B1
• Filed: 11/16/2016
• Issued: 10/10/2017
• Est. Priority Date: 11/16/2016
• Status: Active Grant

• Current Assignee: AImotive Kft
• Original Assignee: AImotive Kft
• Inventors: Gyenes, Viktor, Fenyvesi, Peter, Kishonti, Laszlo
• Primary Examiner(s): Frejd, Russell
• Application Number:
  US15/353,505
• Time in Patent Office: 328 Days
• Field of Search: None
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01C 21/3896 Transmission of map data from central databases
• CPC Class Codes: G09B 29/00 Maps; Plans; Charts; Diagrams, e.g. route diagram star maps G09B27/04; devices for holding or supporting maps A47B97/02; for computing purposes G06G1/14, G09B1/16; display boards G09F
• CPC Class Codes: G09B 29/106 using electronic means

Abstract

An electronic route navigation method is used in navigating an autonomous vehicle in a road network. In an implementation of the method a map is stored on at least one computer, and is sectioned into quads by a processor. The smallest size quads are grouped as base level quads. Extended area quads are defined to contain the area of a plurality of base level quads. Thereafter, a route along a road is calculated from a start point to a destination point. Further extended area quads on the map that do not contain the start point or the destination point are used for cross routing. In said cross routing only the road routes crossing the extended area quad leading from the start point to destination point are calculated.

Claims

1. An electronic route navigation method used in navigating an autonomous vehicle in a road network, comprising:

applying a map in which a preprocessing stage has been carried out, the map being stored in a form of a base level and one or more higher levels on at least one computer, the preprocessing stage comprising the following phases;

clipping the base level of the map with road segments of the road network into base level quads;

storing turn restrictions in the base level quads;

generating an extended area quad of a higher level by a pruning method from quads of a lower level, keeping unrestricted cross routes for the higher level extended area quad, where an extended area quad is defined to contain an area of a plurality of base level quads;

generating, using the pruning method, all higher level quads from already existing lower level quads; and

calculating a route along a road from a start point A to a destination point B, wherein

the point A is contained in a first base level quad and the point B is contained in a second base level quad,

one or more extended area quads on said map that do not contain the point A or the point B are used for cross routing, and in said cross routing only road routes crossing said one or more extended area quads, and leading from the point A to the point B are calculated.

2. The method as claimed in claim 1, wherein

total lengths, costs and/or durations of alternative routes from the point A to the point B are calculated by summing lengths, costs and/or durations of any of the following road sections;

road sections of a base level quad containing the point A,

road sections crossing at least one quad that does not contain the point A or the point B and providing a section of a route from the point A to the point B,

road sections of a base level quad leading to the point B, and

a route having a shortest route length, smallest route cost and/or shortest route duration of said alternative routes is selected based on total lengths, costs and/or durations of said alternative routes.

3. The method as claimed in claim 1, wherein the map is configured to be stored on a cloud server computer, and at least one base level quad and/or extended area quad is configured to be sent via a communication network to the autonomous car configured with a software program using said at least one quad for navigation.

4. The method as claimed in claim 1, wherein there is a hierarchical relation between base level quads and extended area quads, for example a relation like:

(extended area quad level n)=4ⁿ*(base level quad).

5. The method as claimed in claim 4, wherein

n=2 or more levels,

every level covers the same area,

every extended area quad is called a quad of a certain level, and can have a maximum of four child quads on the level below and the size of the quad is four times larger than the child quad,

the lowest level of the hierarchy is called base level, and the base level contains the detailed road network in base level quads,

every level contains less information than the level underneath.

6. The method as claimed in claim 1, wherein route calculation is influenced by any of the following criteria:

turn restrictions, closed road segments, toll roads enabled, unpaved roads enabled, ferries enabled and/or highways enabled.

7. The method as claimed in claim 1, wherein

starting from a base level quad, a search for routes from the point A to the point B goes through quad borders,

when a border of a higher level quad (n=1) is reached far enough from the start point A and the destination point B, the higher level quad is used, and/or

when a border of an even higher level quad is reached far enough from the start point A and the destination point B, the even higher level quad (n=2) is used, and so on.

8. The method as claimed in claim 1 involving an edge labelling Dijkstra'"'"'s algorithm used in computing an optimum route in a memory medium of an autonomous vehicle and/or network server for controlling the navigation of the autonomous vehicle, which may involve any of the following functions:

loading quads from the quad tree hierarchy on demand,

recognizing the predecessors of links instead of nodes,

checking the turn restrictions when extending the set of already travelled links with a new one,

excluding blocked roads from the search,

excluding the roads which don'"'"'t fit to the criteria,

calculating the distance of the currently added link from the start link according to the criteria.

9. The method as claimed in claim 1, wherein

a road in the map is blocked,

in response to a blocked road all non-base level quads having the blocked road are invalidated.

10. An electronic route navigation system used in navigating an autonomous vehicle in a road network, comprising:

a map is applied in the system in which a preprocessing stage has been carried out, the map being stored in a form of a base level and one or more higher levels on at least one computer, the preprocessing stage comprising the following phases;

the base level of the map with road segments of the road network is clipped into base level quads;

turn restrictions are stored in the base level quads;

an extended area quad of a higher level is generated by a pruning methods from quads of a lower level, keeping unrestricted cross routes for the higher level extended area quad, where an extended area quad is defined to contain an area of a plurality of base level quads;

the pruning method generates all higher level quads from already existing lower level quads; and

a route along a road is configured to be calculated from a start point A to a destination point B, wherein

the point A is contained in a first base level quad and the point B is contained in a second base level quad,

one or more extended area quads on said map that do not contain the point A or the point B are used for cross routing, and in said cross routing only road routes crossing said one or more extended area quads, and leading from the point A to the point B are configured to be calculated.

11. The system as claimed in claim 10, wherein

total lengths, costs and/or durations of alternative routes from the point A to the point B are configured to be calculated by summing lengths, costs and/or durations of any of the following road sections;

road sections of a base level quad containing the point A,

road sections crossing at least one quad that does not contain the point A or the point B and providing a section of a route from the point A to the point B,

road sections of a base level quad leading to the point B, and

a route having a shortest route length, smallest route cost and/or shortest route duration of said alternative routes is configured to be selected based on total lengths, costs and/or durations of said alternative routes.

12. The system as claimed in claim 10, wherein the map is configured to be stored on a cloud server computer, and at least one base level quad and/or extended area quad is configured to be sent via a communication network to the autonomous car configured with a software program using said at least one quad for navigation.

13. The system as claimed in claim 10, wherein there is a hierarchical relation between base level quads and extended area quads, for example a relation like:

(extended area quad level n)=4ⁿ*(base level quad).

14. The system as claimed in claim 13, wherein

n=2 or more levels,

every level covers the same area,

every extended area quad is called a quad of a certain level, and can have a maximum of four child quads on the level below and the size of the quad is four times larger than the child quad,

the lowest level of the hierarchy is called base level, and the base level contains the detailed road network in base level quads,

every level contains less information than the level underneath.

15. The system as claimed in claim 10, wherein route calculation is configured to be influenced by any of the following criteria:

turn restrictions, closed road segments, toll roads enabled, unpaved roads enabled, ferries enabled and/or highways enabled.

16. The system as claimed in claim 10, wherein

starting from a base level quad, a search for routes from the point A to the point B is configured to go through quad borders,

when a border of a higher level quad (n=1) is reached far enough from the start point A and the destination point B, the higher level quad is configured to be used, and/or

when a border of an even higher level quad is reached far enough from the start point A and the destination point B, the even higher level quad (n=2) is configured to be used, and so on.

17. The system as claimed in claim 10 involving an edge labelling Dijkstra'"'"'s algorithm used in computing an optimum route in a memory medium of an autonomous vehicle and/or network server for controlling the navigation of the autonomous vehicle, which system may be configured to involve any of the following functions:

loading quads from the quad tree hierarchy on demand,

recognizing the predecessors of links instead of nodes,

checking the turn restrictions when extending the set of already travelled links with a new one,

excluding blocked roads from the search,

excluding the roads which don'"'"'t fit to the criteria,

calculating the distance of the currently added link from the start link according to the criteria.

18. The system as claimed in claim 10, wherein

a road in the map is configured as blocked,

in response to a blocked road all non-base level quads having the blocked road are configured to be invalidated.

19. An electronic route navigation program product embodied in a non-transitory storage medium, used in navigating an autonomous vehicle in a road network, comprising:

a map is applied in the program in which a preprocessing stage has been carried out, the map being stored in a form of a base level and one or more higher levels on at least one computer, the preprocessing stage comprising the following phases;

the base level of the map with road segments of the road network is clipped into base level quads;

turn restrictions are stored in the base level quads;

an extended area quad of a higher level is generated by a pruning methods from quads of a lower level, keeping unrestricted cross routes for the higher level extended area quad, where an extended area quad is defined to contain an area of a plurality of base level quads;

the pruning method generates all higher level quads from already existing lower level quads; and

a route along a road is configured to be calculated from a start point A to a destination point B, wherein

the point A is contained in a first base level quad and the point B is contained in a second base level quad,

one or more extended area quads on said map that do not contain the point A or the point B are used for cross routing, and in said cross routing only road routes crossing said one or more extended area quads, and leading from the point A to the point B are configured to be calculated.

20. The program product as claimed in claim 19, wherein

total lengths, costs and/or durations of alternative routes from the point A to the point B are calculated by summing lengths, costs and/or durations of any of the following road sections;

road sections of a base level quad containing the point A,

road sections crossing at least one quad that do not contain the point A or the point B and providing a section of a route from the point A to the point B,

road sections of a base level quad leading to the point B, and

a routed having a shortest route length, smallest route cost and/or shortest route duration of said alternative routes is selected, based on total lengths, costs and/or durations of said alternative routes.

21. The program product as claimed in claim 19, wherein the map is configured to be stored on a cloud server computer, and at least one base level quad and/or extended area quad is configured to be sent via a communication network to the autonomous car configured with a software program using said at least one quad for navigation.

22. The program product as claimed in claim 19, wherein there is a hierarchical relation between base level quads and extended area quads, for example a relation like:

(extended area quad level n)=4n*(base level quad).

23. The program product as claimed in claim 19, wherein route calculation is influenced by any of the following criteria:

turn restrictions, closed road segments, toll roads enabled, unpaved roads enabled, ferries enabled and/or highways enabled.

24. The program product as claimed in claim 22, wherein:

n=2 or more levels,

every level covers the same area,

every extended area quad is called a quad of a certain level, and can have a maximum of four child quads on the level below and the size of the quad is four times larger than the child quad,

the lowest level of the hierarchy is called base level, and the base level contains the detailed road network in base level quads,

every level contains less information than the level underneath.

25. The program product as claimed in claim 19, wherein

start starting from a base level quad, a search for routes to the point A and the point B goes through quad borders,

when a border of a higher level quad (n=1) is reached far enough from the start point A and the destination point B, the higher level quad is used, and/or

when a border of an even higher level quad is reached far enough from the start point A and the destination point B, the even higher level quad (n=2) is used, and so on.

26. The program product as claimed in claim 19 involving an edge labelling Dijkstra'"'"'s algorithm used in computing an optimum route in a memory medium of an autonomous vehicle and/or network server for controlling the navigation of the autonomous vehicle, which may involve any of the following functions:

loading quads from the quad tree hierarchy on demand,

recognizing the predecessors of links instead of nodes,

checking the turn restrictions when extending the set of already travelled links with a new one,

excluding blocked roads from the search,

excluding the roads which don'"'"'t fit to the criteria,

calculating the distance of the currently added link from the start link according to the criteria.

27. The program product as claimed in claim 19, wherein

a road in the map is blocked,

in response to a blocked road all non-base level quads having the blocked road are invalidated.