Device and method for improving route planning computing devices
First Claim
Patent Images
1. A method of operating a route generator of a route planning device, the method including:
- identifying blocks in a map, the blocks corresponding to different sections of physical terrain;
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. A method of operating a route generator of a route planning device, the method including:
-
identifying blocks in a map, the blocks corresponding to different sections of physical terrain; 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of operating a route generator including:
-
loading data for a first block of cells of a cost map into cache memory of a Graphics Processing Unit, wherein loading of data for one cell in the first block requires loading of data for all cells in the first block, and loading a second set of cells wherein each cell in the second set is not in the first block and shares either an edge or is diagonally adjacent with a cell in the first block, wherein the ratio of the number of cells in the first block to the number of cells in the second set is less than 1;
8, wherein the combination of the first block of cells and the second set of cells provide all map data needed to produce traversal values for all cells of the first block, wherein traversal values are values that consider the cost data and data indicating progress towards a route endpoint. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A method of operating a route generator including:
-
determining that a first cell is to be processed as part of determining a route; determining that the first cell is within a first block containing at least two cells; loading data needed to analyze all cells within the first block from a first non-volatile memory into a volatile memory accessible by a processor, the data needed to analyze all cells within the first block including all cells that share at least one of an edge and a corner with a cell in the first block; and once all data needed to analyze all cells within the first block is loaded into the volatile memory, analyzing all cells within the first block. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification