Automated route determination
First Claim
1. A navigation device comprising:
- a memory having processor-readable instructions stored therein; and
a processor to execute the processor-readable instructions to;
access information regarding an origin and information regarding a destination in a routing graph representing a network of roads,the origin and the destination each being represented by a link or a node, andthe routing graph including a first plurality of links,each link, of the first plurality of links, joining two nodes;
determine whether a distance between a first link, of the first plurality of links and adjacent to an end node, and the destination is within a predetermined distance;
determine, when the distance between the first link and the destination is not within the predetermined distance, whether the first link is used to enter a second plurality of links in a no-outlet region,the second plurality of links being exited only by traversing the first link used to enter the second plurality of links;
determine, based on determining that the first link is used to enter the no-outlet region, whether the destination is located within the no-outlet region;
add the first link to an adjacency set based on determining that the destination is located within the no-outlet region;
identify a second link, of the first plurality of links, adjacent to the end node;
determine that the second link is not entering the no-outlet region;
add the second link to the adjacency set;
determine a recommended route from the origin to the destination using the adjacency set list; and
cause a presentation processor to provide, for display, the recommended route.
4 Assignments
0 Petitions
Accused Products
Abstract
A preferred route may be determined from an origin location to a destination location. The determination is made by processing directed links (e.g., one-way edges) in a graph that includes one or more links and two or more nodes. The determination of a preferred route may include an estimate of the time required at one or more intersections along alternative. Individual routing preferences, such as a preference of a rural over an urban route, also may be considered. Techniques are described that may help reduce the time required to identify a preferred route, including the identification and removal of no outlet routes before processing the directed links and techniques using particular data formats.
-
Citations
20 Claims
-
1. A navigation device comprising:
-
a memory having processor-readable instructions stored therein; and a processor to execute the processor-readable instructions to; access information regarding an origin and information regarding a destination in a routing graph representing a network of roads, the origin and the destination each being represented by a link or a node, and the routing graph including a first plurality of links, each link, of the first plurality of links, joining two nodes; determine whether a distance between a first link, of the first plurality of links and adjacent to an end node, and the destination is within a predetermined distance; determine, when the distance between the first link and the destination is not within the predetermined distance, whether the first link is used to enter a second plurality of links in a no-outlet region, the second plurality of links being exited only by traversing the first link used to enter the second plurality of links; determine, based on determining that the first link is used to enter the no-outlet region, whether the destination is located within the no-outlet region; add the first link to an adjacency set based on determining that the destination is located within the no-outlet region; identify a second link, of the first plurality of links, adjacent to the end node; determine that the second link is not entering the no-outlet region; add the second link to the adjacency set; determine a recommended route from the origin to the destination using the adjacency set list; and cause a presentation processor to provide, for display, the recommended route. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A non-transitory computer-readable medium storing instructions, the instructions comprising:
-
one or more instructions, that when executed by one or more processors, cause the one or more processors to; utilize a routing system to access information regarding an origin and information regarding a destination in a routing graph representing a network of roads and including two or more nodes and one or more links, determine whether a distance between a first directed link, adjacent to a node, and the destination is within a predetermined distance; determine, when the distance between the first directed link and the destination is not within the predetermined distance, whether the first directed link is included among a set of multiple links in a no-outlet region, the set of multiple links being exited only by traversing the first directed link used to enter the set of multiple links; determine, based on determining that the first directed link is used to enter the no-outlet region, whether the destination is located within the no-outlet region; add the first directed link to an adjacency set based on determining that the destination is located within the no-outlet region; identify a second directed link adjacent to the node; determine that the second directed link is not entering the no-outlet region; add the second directed link to the adjacency set; utilize the routing system to determine a preferred route from the origin to the destination using the adjacency set; and cause a presentation processor to provide, for display, the preferred route. - View Dependent Claims (12, 13, 14)
-
-
15. A method comprising:
-
accessing, by a navigation device, information regarding an origin and information regarding a destination in a routing graph representing a network of roads, the origin and destination each being represented by a link or a node, and the routing graph including a first plurality of links, each link, of the first plurality of links, joining two nodes; determining, by the navigation device, whether a distance between a first link, of the first plurality of links and adjacent to an end node, and the destination is within a predetermined distance; determining, by the navigation device and when the distance between the first link and the destination is not within the predetermined distance, whether the first link is used to enter a second plurality of links in a no-outlet region, the second plurality of links being exited only by traversing the first link used to enter the second plurality of links; determining, by the navigation device and based on determining that the first link is used to enter the no-outlet region, whether the destination is located within the no-outlet region; adding, by the navigation device, the first link to an adjacency set based on determining that the destination is located within the no-outlet region; identifying, by the navigation device, a second link, of the first plurality of links, adjacent to the end node; determining, by the navigation device, that the second link does not enter the no-outlet region; determining, by the navigation device, a cost for the second link based on determining that the second link is not entering the no-outlet region; adding, by the navigation device, the second link to the adjacency set based on determining the cost for the second link; determining, by the navigation device, a recommended route from the origin to the destination using the adjacency set; and causing, by the navigation device, a presentation processor to provide, for display, the recommended route. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification