Device and method for improving route planning computing devices

• US 10,274,331 B2
• Filed: 09/16/2016
• Issued: 04/30/2019
• Est. Priority Date: 09/16/2016
• Status: Active Grant

• Current Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Original Assignee: Polaris Industries Incorporated (Polaris Inc.)
• Inventors: Freed, Erik S.
• Primary Examiner(s): Jos, Basil T.
• Application Number:
  US15/267,942
• Publication Number:
  US 20180080781A1
• Time in Patent Office: 956 Days
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/302 In image processor or graphics adapter
• CPC Class Codes: G06F 2212/454 Vector or matrix data
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

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

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.

2. The method of claim 1, wherein the route traversal values for the plurality of blocks are simultaneously calculated by a Graphics Processing Unit.

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

4. The method of claim 3, wherein each block having a first polarity is laterally adjacent other blocks having only a second polarity.

5. The method of claim 3, wherein each block having a first polarity is diagonally adjacent other blocks having only the first polarity.

6. The method of claim 3, wherein blocks in the first group share a common polarity.

7. The method of claim 1, wherein when a traversal value for any cell in any block is calculated, traversal values for all cells in that block are required to be calculated.

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.

9. The method of claim 8, further including processing the cost data for the first block to generate traversal values for the first block.

10. The method of claim 8, wherein the first block includes at least 1024 cells and the second set includes no more than 272 cells.

11. The method of claim 8, wherein when a traversal value for any cell in any block is calculated, traversal values for all cells in that block are required to be calculated.

12. The method of claim 8, further including:

generating traversal values for the first block of cells, wherein the only cost values used to generate the traversal values for the first block of cells are those of the first and second sets of cells.

13. The method of claim 12, further including:

generating a route from a start position to a destination position responsive to the generated traversal values.

14. The method of claim 8, wherein each cell has only single cost value and a single traversal value associated therewith.

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.

16. The method of claim 15, wherein each cell loaded has only a single cost value and a single traversal value assigned thereto.

17. The method of claim 15, wherein determining that a first cell is to be processed includes processing a second block that does not contain the first cell, where such processing indicates that the first block is adjacent to the second block.

18. The method of claim 15, wherein the processor is a Graphics Processing Unit and multiple blocks are processed simultaneously.

19. The method of claim 15, wherein each block includes a number of cells that is a power of 2.

20. The method of claim 15, wherein the volatile memory is cache memory onboard the processor.