DETERMINING ALTERNATIVE ROUTE BY NAVIGATION SYSTEM

• US 20150142300A1
• Filed: 11/21/2013
• Published: 05/21/2015
• 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
• Granted Patent: US 9,970,775 B2
• Time in Patent Office: Days
• US Class Current: 701/410
• 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 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.

2. The method of claim 1, further comprising:

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

identifying a second route having the starting point on an edge comprising the current position.

3. The method of claim 1, wherein the first route optimizes a first routing criterion and the second route optimizes a second routing criterion.

4. The method of claim 1, wherein determining the first route is performed using a first routing method and determining the second route is performed using a second routing method.

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

6. The method of claim 1, wherein the defined distance is determined based on an estimated accuracy of determining own current position.

7. The method of claim 1, wherein determining at least one of:

the first route or the second route comprises transmitting a routing request to an external computer system.

8. The method of claim 1, wherein determining at least one of:

the first route or the second route comprises receiving a route from an external computer system.

9. The method of claim 1, wherein determining at least one of:

the first route or the second route comprises assigning a weight to an edge.

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

12. The system of claim 10, wherein the processors are further to:

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

identify a second route having the starting point on an edge comprising the current position.

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

14. The system of claim 10, wherein the defined distance is determined based on an estimated accuracy of determining own current position.

15. The system of claim 10, wherein determining at least one of:

the first route or the second route comprises transmitting a routing request to an external computer system.

16. The system of claim 10, wherein determining at least one of:

the first route or the second route comprises assigning a weight to an edge.

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

11. A system, comprising:

a memory; and

one or more processors, coupled to the memory, to;

determine 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

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

18. A non-transitory computer-readable storage medium comprising executable instructions that, when executed by a processing device, cause the processing device to perform operations, comprising:

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.

19. The non-transitory computer-readable storage medium of claim 18, further comprising executable instructions that, when executed by a processing device, cause the processing device to perform operations, comprising:

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

identifying a second route having the starting point on an edge comprising the current position.

20. The non-transitory computer-readable storage medium of claim 18, wherein determining at least one of:

the first route or the second route comprises assigning a weight to an edge.