Transmission Of Routes Between Client And Server Using Route IDs

• US 20090248291A1
• Filed: 04/01/2009
• Published: 10/01/2009
• Est. Priority Date: 04/01/2008
• Status: Active Grant

• Current Assignee: Uber Technologies, Inc.
• Original Assignee: Decarta (Uber Technologies, Inc.)
• Inventors: Poppen, Richard F.
• Granted Patent: US 8,260,549 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 abbreviating 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 of the original route;

determining a heading for a first link along the route entering the node;

determining a heading for a second link along the route exiting the node;

responsive to a link exiting the node and not on the original route having a heading more parallel to the first link than does the second link, placing a breadcrumb in the abbreviated route, the breadcrumb including a representation of the coordinates of the node and a representation of the heading of the route as it enters and leaves the breadcrumb; and

placing a breadcrumb at the end of the route, the breadcrumb at the end of the route having coordinates of the location of the destination point of the route and a heading of the route as it enters the breadcrumb.

2. The method of claim A1 further comprising placing a breadcrumb at the beginning of the abbreviated 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 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 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 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 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 abbreviating 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 computer readable medium and including instructions configured to cause a computer to carry out the steps of:

for each node of the original route;

determining a heading for a first link along the route entering the node;

determining a heading for a second link along the route exiting the node;

responsive to a link exiting the node and not on the original route having a heading more parallel to the first link than does the second link, placing a breadcrumb in the abbreviated route, the breadcrumb including a representation of the coordinates of the node and a representation of the heading of the route as it enters and leaves the breadcrumb; and

placing a breadcrumb at the end of the route, the breadcrumb at the end of the route having coordinates of the location of the destination point of the route and a heading of the route as it enters the breadcrumb.