Device and method for improving route planning computing devices
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-11268820-B2
Publication Date
2022-03-08
Expiration Date
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.
Core Innovation
The invention improves off-road route generation on a route planning device by applying dogleg removal to eliminate jagged paths within a route located in a map. It determines, based on terrain movement cost data, an area within the map that has uniform cost, where the area comprises a first point and a second point. Jagged paths between the first point and the second point within the uniform-cost area are eliminated by determining a straight path between the first point and the second point.
The invention generates a traversal map with the route overlaid thereon and displays the traversal map on the route planning device. In conjunction with the route generation, it uses cell adjacency to smooth the route and can apply 16-point adjacency, including chess-knight adjacencies, to shape how smooth points within the generated route are treated. The same family also describes mapping the route using greater than eight-point adjacency to map route points and using corresponding pluralities of cost values to generate the route.
The invention further includes GPU-accelerated processing concepts for efficient route planning, including rasterizing the map into blocks/cells, processing multiple blocks in parallel using a parity/checkerboard scheme that avoids edge-sharing between simultaneously processed blocks, and reducing memory/cache overhead with block-based loading and padding/region-of-influence. Traversal values are computed from terrain movement cost data plus per-cell progress toward an endpoint, route flooding updates a traversal map until steady state, endpoint seeding is performed, and route retracing and route vectorization are performed by using traversal-cell values and adjacent-cell backtracking to derive vertices list of a final route.
Claims Coverage
The independent claims cover two method claims and one computing system claim, each centered on route generation for a route planning device using dogleg removal and traversal-map output, plus alternative adjacency-based route mapping using greater than eight-point adjacency.
Dogleg removal within a uniform-cost area for route smoothing
Generating a route between a route start-point and a route end-point using dogleg removal to eliminate jagged paths within the route located in a map, where dogleg removal comprises determining, based on terrain movement cost data, an area within the map that has uniform cost (the area comprises a first point and a second point) and eliminating jagged paths between the first point and the second point within the area by determining a straight path between the first point and the second point.
Traversal map generation with route overlay and display
Generating a traversal map with the route overlaid thereon and displaying the traversal map on the route planning device.
GPU-based route generation using dogleg removal
A computing system comprising a GPU configured to generate a route between a route start-point and a route end-point using dogleg removal to eliminate jagged paths within the route located in a map, where the GPU uses dogleg removal by determining, based on terrain movement cost data, an area within the map that has uniform cost (the area comprises a first point and a second point) and eliminating jagged paths between the first point and the second point within the area by determining a straight path between the first point and the second point, then generating a traversal map with the route overlaid thereon and displaying the traversal map on the route planning device.
Greater-than-eight-point adjacency route mapping with plurality of cost values
Generating a route between a route start-point and a route end-point using greater than eight-point adjacency to map the route, where using the greater than eight-point adjacency to map the route comprises determining, based on terrain movement cost data, a plurality of cost values corresponding to a first cell associated with the route, where the plurality of cost values comprises a first set of cost values for eight cells directly adjacent to the first cell within the route and at least one other cost value for a second cell that is not directly adjacent to the first cell, and using the plurality of cost values to generate the route, then generating a traversal map with the route overlaid thereon and displaying the traversal map on the route planning device.
Across the independent claims, the core coverage is route generation that uses dogleg removal within a uniform-cost area and outputs a traversal map for display, implemented either by operating a route generator on a route planning device or by using a GPU in a computing system, with an additional approach that generates routes using greater than eight-point adjacency by determining pluralities of cost values.
Stated Advantages
Not explicitly described in patent.
Documented Applications
Not explicitly described in patent.
Interested in licensing this patent?