Transmission of routes between client and server using route IDs

• US 8,260,549 B2
• Filed: 04/01/2009
• Issued: 09/04/2012
• Est. Priority Date: 04/01/2008
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Poppen, Richard F.
• Primary Examiner(s): Lubin, Valerie
• Application Number:
  US12/416,920
• Publication Number:
  US 20090248291A1
• Time in Patent Office: 1,252 Days
• Field of Search: 701/213
• US Class Current: 701/421
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once

Abstract

Dehydration of routes enables transmitting a description of a route requiring much less space than full specification of the route. A series of “breadcrumbs” and hints are used for dehydration. A breadcrumb includes coordinates of a point, a heading at which the route enters the breadcrumb, and a heading at which the route leaves the breadcrumb. A dehydration module places a breadcrumb at the location marking the beginning of the route, and having a leaving heading identifying the link in the original route. The node at the end of each link in the original route is examined. If the link leaving the node is the most parallel link to the link entering the node, nothing is added to the dehydrated route. If not, a breadcrumb is added to the dehydrated route, specifying the coordinates of the point, the entering heading of the breadcrumb and the leaving heading of the breadcrumb.

Claims

1. A method for creating an abbreviated description of an original navigation route, the navigation route having an originating point and a destination point, and represented by a plurality of links, each joining a plurality of nodes, the method comprising:

for each node reached by an incoming link on the original route and having multiple exiting links, each exiting link having a heading;

determining, by at least one computer, a heading of the incoming link;

determining, by the computer, the heading of the exiting link;

along the route exiting the node;

responsive to a determination by the computer that the exiting link along the route is not the most parallel exiting link to the incoming link, placing, by the computer, a breadcrumb in the abbreviated description of the route, the breadcrumb including coordinates of a point represented by the node, a representation of a heading of the incoming link, and a representation of a heading of the exiting link along the original route; and

placing, by the computer, a breadcrumb at the end of the abbreviated description of the original route, the breadcrumb including coordinates of a node representing a point at the end of the route and a representation of a heading of an incoming link to the node.

2. The method of claim 1 further comprising placing a breadcrumb at the beginning of the abbreviated description of the original route, the breadcrumb having coordinates of the location of the originating point and a heading of the route as it leaves the breadcrumb.

3. A method for determining an original navigation route from an abbreviated route description, the abbreviated description including a plurality of breadcrumbs, each breadcrumb including coordinates of a location along the route and at least one of an entering heading and a leaving heading, the method comprising:

determining, by at least one computer, an origination point for the original route as a point identified by coordinates of a breadcrumb in the abbreviated route and notated as representing the origination point;

selecting as a link in the original route a link most closely parallel to a leaving heading specified by the breadcrumb representing the origination point;

for each node at the end of a link selected as a link in the original route;

inserting, by the computer, a node at the end of the selected link into the original route;

responsive to no breadcrumb in the abbreviated route having coordinates identifying the node, selecting, by the computer, as the next link in the original route a link leaving the node most parallel to the link entering the node;

responsive to one of the breadcrumbs in the abbreviated route having coordinates identifying the node, selecting, by the computer, as the next link in the original route a link leaving the node most parallel to the leaving heading of the matching breadcrumb; and

displaying the original route in a user interface of a navigation device.

4. A computer program product for creating an abbreviated description of an original navigation route, the navigation route having an originating point and a destination point, and represented by a plurality of links, each joining a plurality of nodes, the computer program product stored on a non-transitory computer readable medium and including instructions configured to cause a computer to carry out the steps of:

for each node reached by an incomining link on the original route and having multiple exiting links, each exiting link having a heading;

determining, by at least one computer, a heading of the incoming link;

determining, by the computer, the heading of the exiting link along the route exiting the node;

responsive to a determination by the computer that the exiting link along the route is not the most parallel exiting link to the incoming link, placing, by the computer, a breadcrumb in the abbreviated description of the route, the breadcrumb including coordinates of a point prepresented by the node, a representation of a heading of the incoming link, and a representation of a heading of the exiting link along the original route; and

placing, by the computer, a breadcrumb at the end of the abbreviated description of the original route, the breadcrumb including coordinates of a node representing a point at the end of the route and a representation of a heading of an incoming link to the node.