Determining alternative route by navigation system

• US 9,970,775 B2
• Filed: 11/21/2013
• Issued: 05/15/2018
• Est. Priority Date: 11/21/2013
• Status: Active Grant

• Current Assignee: Red Hat Israel Ltd. (International Business Machines Corporation)
• Original Assignee: Red Hat Israel Ltd. (International Business Machines Corporation)
• Inventors: Tsirkin, Michael
• Primary Examiner(s): Whittington, Jess
• Application Number:
  US14/085,980
• Publication Number:
  US 20150142300A1
• Time in Patent Office: 1,636 Days
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents

Abstract

Systems and methods for determining alternative navigational routes. An example method may comprise: determining a first route to a destination, the route comprising a plurality of edges of a graph representing a map of navigable paths, wherein each edge represents a path connecting two vertices and each vertex represents at least one of: an endpoint of a path or a junction of two or more paths; and determining a second route to the destination from a point located at least a defined distance from a junction comprised by the first route, along an edge not comprised by the first route.

Claims

1. A method, comprising:

determining, by a processing device of a vehicle navigation system, a first route to a destination using a first routing method, the first route comprising a plurality of edges of a graph representing a map of navigable paths, wherein each edge represents a path connecting two vertices and each vertex represents at least one of;

an endpoint of a path or a junction of two or more paths;

determining a first distance corresponding to a current speed of the vehicle navigation system as the vehicle navigation system travels on the first route;

determining a second distance corresponding to an accuracy of the vehicle navigation system in determining a position of the vehicle navigation system as the vehicle navigation system travels on the first route;

determining a plurality of other routes to the destination while a current position of the vehicle navigation system is on the first route, wherein each of the plurality of other routes begins from a starting point that corresponds to an anticipated deviation from the first route located at least a defined distance from the current position of the vehicle navigation system as the vehicle navigation system travels on the first route, along edges not comprised by the first route, wherein the defined distance is less than the first distance and greater than the second distance; and

causing a graphical user interface of the vehicle navigation system to display a second route of the plurality of other routes based on a deviation of the vehicle navigation system from the first route.

2. The method of claim 1, further comprising:

determining that the current position does not belong to the first route; and

identifying a particular route of the plurality of routes having the starting point on the edge comprising the current position.

3. The method of claim 1, wherein the first route is optimized for a first routing criterion and the plurality of other routes are optimized for a second routing criterion.

4. The method of claim 1, wherein the defined distance is determined as a defined time multiplied by a current vehicle speed.

5. The method of claim 1, wherein the defined distance is determined in view of an estimated accuracy of determining the current position.

6. The method of claim 1, further comprising:

transmitting a routing request to an external computer system to determine at least one of the first route or the plurality of other routes.

7. The method of claim 1, further comprising:

receiving a route from an external computer system to determine at least one of the first route or the plurality of other routes.

8. The method of claim 1, further comprising:

assigning a weight to an edge to determine at least one of the first route or the plurality of other routes.

9. The method of claim 8, wherein the weight represents a user preference with respect to including the path represented by the edge into the first route.

10. The method of claim 1, wherein the first routing method is different than a second routing method used to determine the second route, the second routing method being a heuristic-based routing method that is faster to calculate than the first routing method.

11. A system, comprising:

a memory; and

a processing device of a vehicle navigation system, operatively coupled to the memory, to;

determine a first route to a destination using a first routing method, the first route comprising a plurality of edges of a graph representing a map of navigable paths, wherein each edge represents a path connecting two vertices and each vertex represents at least one of;

an endpoint of a path or a junction of two or more paths;

determine a first distance corresponding to a current speed of the vehicle navigation system as the vehicle navigation system travels on the first route;

determine a second distance corresponding to an accuracy of the vehicle navigation system in determining a position of the vehicle navigation system as the vehicle navigation system travels on the first route;

determine a plurality of other routes to the destination while a current position is on the first route, wherein each of the plurality of other routes begins from a starting point that corresponds to an anticipated deviation from the first route located at least a defined distance from the current position of the vehicle navigation system as the vehicle navigation system travels on the first route, along edges not comprised by the first route, wherein the defined distance is less than the first distance and greater than the second distance; and

cause a graphical user interface to display a second route of the plurality of other routes based on a deviation of the vehicle navigation system from the first route.

12. The system of claim 11, wherein the processing device is further configured to:

determine that the current position does not belong to the first route; and

identify a particular route of the plurality of other routes having the starting point on the edge comprising the current position.

13. The system of claim 11, wherein the defined distance is determined as a defined time multiplied by a current vehicle speed.

14. The system of claim 11, wherein the defined distance is determined in view of an estimated accuracy of determining the current position.

15. The system of claim 11, wherein the processing device is further configured to:

transmit a routing request to an external computer system to determine at least one of the first route or the plurality of other routes.

16. The system of claim 11, wherein the processing device is further configured to:

assign a weight to an edge to determine at least one of the first route or the plurality of other routes.

17. The system of claim 16, wherein the weight represents a user preference with respect to including the path represented by the edge into the first route.

18. A non-transitory computer-readable storage medium comprising executable instructions to cause a processing device of a vehicle navigation system to:

determine, by the processing device, a first route to a destination using a first routing method, the first route comprising a plurality of edges of a graph representing a map of navigable paths, wherein each edge represents a path connecting two vertices and each vertex represents at least one of;

an endpoint of a path or a junction of two or more paths;

determine a first distance corresponding to a current speed of the vehicle navigation system as the vehicle navigation system travels on the first route;

determine a second distance corresponding to an accuracy of the vehicle navigation system in determining a position of the vehicle navigation system as the vehicle navigation system travels on the first route;

determine a plurality of other routes to the destination while a current position is on the first route, wherein each of the plurality of other routes begins from a starting point that corresponds to an anticipated deviation from the first route located at least a defined distance from the-current position of the vehicle navigation system as the vehicle navigation system travels on the first route, along edges not comprised by the first route, wherein the defined distance is less than the first distance and greater than the second distance; and

cause a graphical user interface to display a second route of the plurality of other routes based on a deviation of the vehicle navigation system from the first route.

19. The non-transitory computer-readable storage medium of claim 18, further comprising executable instructions to cause the processing device to:

determine that the current position does not belong to the first route; and

identify a particular route of the plurality of other routes having the starting point on the edge comprising the current position.

20. The non-transitory computer-readable storage medium of claim 18, wherein executable instructions further cause the processing device to:

assign a weight to an edge to determine at least one of the first route or the plurality of other routes.