# US 11,892,309 B2 · Device and method for improving route planning computing devices

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

- Number: US 11,892,309 B2
- Document ID: US11892309B2
- Status: Granted
- Kind: B2
- Application number: 17/688,061
- Filed: 2022-03-07
- Published: 2022-06-16
- Granted: 2024-02-06
- Earliest claimed: 2016-09-16
- Assignees: Polaris Industries Inc.
- Applicants: Polaris Industries Inc.
- Inventors: Erik S. Freed
- Web page: https://patentgrep.com/patent/US11892309B2

## CPC

- G01C 21/3461: {Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types or segments such as motorways, toll roads or ferries}
- G01C 21/20: Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence)
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G06F 12/0868: Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
- G06F 12/0873: Mapping of cache memory to specific storage devices or parts thereof
- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06F 2212/1016: Performance improvement
- G06F 2212/302: In image processor or graphics adapter
- G06F 2212/454: Vector or matrix data
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR

## Abstract

A route generator and method of operating the same including; calculating route traversal values for a plurality of blocks in a first group simultaneously, each block including a plurality of cells, traversal values being values that consider terrain movement cost data and data indicating progress towards a route endpoint on a per-cell basis, wherein the plurality of blocks are chosen such that the blocks in the first group fail to share any edges with other blocks in the first group.

## Claims

### Claim 1

A method for generating a route, the method comprising:
generating a traversal map corresponding to terrain of a map, the traversal map comprising a plurality of blocks, wherein:
each block of the plurality of blocks comprises a plurality of cells that each correspond to a subpart of the block; and
each block has a width defined as a first unit of cells and a height defined as a second unit of cells;
generating, based on the traversal map, a route between a route start-point and a route end-point, wherein the route is located within the map and comprises a subset of blocks from the plurality of blocks;
generating, for the generated route, a vectorized route comprising vertices from the route start-point to the route-end point that each correspond to a cell within a block of the subset of blocks; and
generating, based on the vertices from the route start-point to the route-end point, a visual representation of the vectorized route overlaid on the map for presentation to a user.

### Claim 2 (depends on 1)

The method of claim 1, wherein generating the vectorized route comprises:
identifying, for a cell associated with the route, an adjacent cell having the largest negative traversal value; and
generating a vertex in the vectorized route corresponding to the identified cell.

### Claim 3 (depends on 1)

The method of claim 1, wherein each block of the plurality of blocks is assigned one of two polarity values.

### Claim 4 (depends on 3)

The method of claim 3, wherein:
each block having a first polarity is laterally adjacent other blocks having only a second polarity; and
each block having the first polarity is diagonally adjacent other blocks having only the first polarity.

### Claim 5 (depends on 1)

The method of claim 1, wherein route traversal values for at least two of the plurality of blocks are contemporaneously calculated by a graphics processing unit.

### Claim 6

A method for generating a route, the method comprising:
generating a coarse route corresponding to a set of blocks for a map, wherein each block of the set of blocks has:
a width defined as a first unit of cells; and
a height defined as a second unit of cells;
generating, based on a plurality of cells for a first block of a subset of blocks that correspond to the coarse route, a first fine route;
generating, based on a plurality of cells for a second block of the subset of blocks that correspond to the coarse route, a second fine route, wherein the second block is different than the first block; and
providing, to a user computing device for display to a user of the user computing device, an ultimate route for the map based on the first fine route and the second fine route that is rendered by the user computing device.

### Claim 7 (depends on 6)

The method of claim 6, wherein the ultimate route is generated based on a plurality of cells for a subset of blocks that correspond only to the coarse route.

### Claim 8 (depends on 6)

The method of claim 6, wherein:
a plurality of fine routes including the fine route are generated; and
the coarse route is used to limit generation of the plurality of fine routes.

### Claim 9 (depends on 6)

The method of claim 6, wherein generating the coarse route comprises determining, based on terrain movement cost data, a plurality of cost values comprising:
a cost value for each block directly adjacent to the block of the subset of blocks; and
a cost value for a block that is not directly adjacent to the block.

### Claim 10 (depends on 6)

The method of claim 6, wherein the plurality of cells for the block that corresponds to the coarse route is treated as a single entity when generating the coarse route.

### Claim 11

A method for generating a route, the method comprising:
loading, into memory of a computing device, a first set of map tiles associated with a first region of a map;
processing, as part of generating a route for the map, the first set of tiles associated with the first region;
determining, based on the generating, to load an unloaded set of map tiles associated with a region of the map that is yet to be processed;
based on determining to load the unloaded set of map tiles:
loading, into the memory of the computing device, a second set of map tiles associated with a second region of the map, wherein the second set of map tiles is prioritized over a third set of map tiles that is unloaded; and
processing, as part of generating the route, the second set of map tiles; and
providing, based on the first set of map tiles and the second set of map tiles in the memory, a visual representation of the generated route for display, by a computing device, to a user.

### Claim 12 (depends on 11)

The method of claim 11, wherein determining to load the unloaded set of map tiles comprises evaluating a proximity of the generating to the region of the map that is yet to be processed.

### Claim 13 (depends on 11)

The method of claim 11, wherein the second set of map tiles is more proximate to the first region than the third set of map tiles.

### Claim 14 (depends on 11)

The method of claim 11, wherein processing the first set of tiles comprises processing a set of blocks for the first region, wherein each block of the set of blocks comprises a plurality of cells.

### Claim 15 (depends on 11)

The method of claim 11, wherein the first set of map tiles and the second set of map tiles are each loaded into cache memory of a graphics processing unit.

### Claim 16 (depends on 11)

The method of claim 11, wherein the first set of map tiles and the second set of map tiles are each obtained from a remote database.