# US 2023/0408269 A1 · Route summary construction, compression and decompression

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2023/0408269 A1
- Document ID: US20230408269A1
- Status: Published application
- Kind: A1
- Application number: 17/844,098
- Filed: 2022-06-20
- Published: 2023-12-21
- Earliest claimed: 2022-06-20
- Assignees: Ford Global Technologies, LLC
- Applicants: Ford Global Technologies, LLC
- Inventors: Omar Makke; Jeremy Lerner
- Web page: https://patentgrep.com/patent/US20230408269A1

## CPC

- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)}
- G01C 21/3492: {employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968)}
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

A system includes a processor that determines a route. The processor determines a plurality of nodes along the route and alternative paths from one node to a successive node along the route through another node. The processor defines the route based on the plurality of nodes and removes at least one node between second and third nodes on the basis that the removed node lies along a least-cost path between the second and third nodes. The processor repeats removal of nodes until a set of minimum nodes to define the route with all non-least-cost path decisions is achieved as a compressed route and transmits the compressed route to at least one second processor that decompresses the compressed route through inclusion of removed nodes, the removed nodes being re-included on the basis of being nodes lying on a least-cost path between two nodes included sequentially in the compressed route.

## Claims

### Claim 1

A system comprising:
at least one first processor configured to:
determine a route to an input destination;
determine a plurality of nodes, representing decision points, along the route and alternative paths from one node to a successive node along the route through another node;
define the route based on the plurality of nodes;
remove at least one first node between second and third nodes on the defined route, the removed first node being removed on the basis that it lies along a least-cost path between the second and third nodes;
repeat removal of nodes until a set of minimum nodes to define the route with all non-least-cost path decisions is achieved as a compressed route; and
transmit the compressed route to at least one second processor;
the at least one second processor configured to:
decompress the compressed route through inclusion of removed nodes, the removed nodes being re-included on the basis of being nodes lying on a least-cost path between two nodes included sequentially in the compressed route.

### Claim 2 (depends on 1)

The system of claim 1, wherein the first and second processors respectively determine the least-cost path between the second and third nodes and the least-cost path between two nodes included sequentially in the compressed route based on the same cost data.

### Claim 3 (depends on 2)

The system of claim 2, wherein the cost data is based on distance between the nodes.

### Claim 4 (depends on 2)

The system of claim 2, wherein the cost data is based on projected travel time between the nodes, determined at a fixed point in time.

### Claim 5 (depends on 1)

The system of claim 1, wherein the nodes correspond to intersections along the route.

### Claim 6 (depends on 1)

The system of claim 1, wherein the nodes are determined based on boundaries defining node-inclusion, the boundaries including at least a requirement that the node have at least one path to a node

### Claim 7 (depends on 1)

The system of claim 1, wherein the at least one first processor is included in a vehicle or a mobile device.

### Claim 8

A method comprising:
determining a route to an input destination;
determining a plurality of nodes, representing decision points, along the route and alternative paths from one node to a successive node along the route through another node;
defining the route based on the plurality of nodes;
removing at least one first node between second and third nodes on the defined route, the removed first node being removed on the basis that it lies along a least-cost path between the second and third nodes;
repeating removal of nodes until a set of minimum nodes to define the route with all non-least-cost path decisions is achieved as a compressed route;
transmitting the compressed route;
receiving the compressed route; and
decompressing the compressed route through inclusion of removed nodes, the removed nodes being re-included on the basis of being nodes lying on a least-cost path between two nodes included sequentially in the compressed route.

### Claim 9 (depends on 8)

The method of claim 8, wherein the removing the at least one first node and re-including the removed nodes is based on the same cost data.

### Claim 10 (depends on 9)

The method of claim 9, wherein the cost data is based on distance between the nodes.

### Claim 11 (depends on 9)

The method of claim 9, wherein the cost data is based on projected travel time between the nodes, determined at a fixed point in time.

### Claim 12 (depends on 8)

The method of claim 8, wherein the nodes correspond to intersections along the route.

### Claim 13 (depends on 8)

The method of claim 8, wherein the nodes are determined based on boundaries defining node-inclusion, the boundaries including at least a requirement that the node have at least one path to a node.

### Claim 14

A non-transitory computer-readable storage medium storing instructions that, when executed, cause one or more executing processors to perform a method comprising:
determining a route to an input destination;
determining a plurality of nodes, representing decision points, along the route and alternative paths from one node to a successive node along the route through another node;
defining the route based on the plurality of nodes;
removing at least one first node between second and third nodes on the defined route, the removed first node being removed on the basis that it lies along a least-cost path between the second and third nodes;
repeating removal of nodes until a set of minimum nodes to define the route with all non-least-cost path decisions is achieved as a compressed route;
transmitting the compressed route;
receiving the compressed route; and
decompressing the compressed route through inclusion of removed nodes, the removed nodes being re-included on the basis of being nodes lying on a least-cost path between two nodes included sequentially in the compressed route.

### Claim 15 (depends on 14)

The storage medium of claim 14, wherein the removing the at least one first node and re-including the removed nodes is based on the same cost data.

### Claim 16 (depends on 15)

The storage medium of claim 15, wherein the cost data is based on distance between the nodes.

### Claim 17 (depends on 15)

The storage medium of claim 15, wherein the cost data is based on projected travel time between the nodes, determined at a fixed point in time.

### Claim 18 (depends on 14)

The storage medium of claim 14, wherein the nodes correspond to intersections along the route.

### Claim 19 (depends on 14)

The storage medium of claim 14, wherein the nodes are determined based on boundaries defining node-inclusion, the boundaries including at least a requirement that the node have at least one path to a node.
