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-11892309-B2
Publication Date
2024-02-06
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 generates a traversal map corresponding to terrain of a map, where the traversal map comprises a plurality of blocks and each block comprises a plurality of cells corresponding to a subpart of the block, with each block having a width defined as a first unit of cells and a height defined as a second unit of cells. Based on the traversal map, the invention generates a route between a route start-point and a route end-point, where the route is located within the map and comprises a subset of blocks from the plurality of blocks.
For the generated route, the invention generates a vectorized route comprising vertices corresponding to cells within blocks of the subset of blocks. Based on the vertices from the route start-point to the route end-point, the invention generates a visual representation of the vectorized route overlaid on the map for presentation to a user. The route generation and vectorization are performed in a manner that supports route traversal values associated with the terrain of the map.
The invention also supports generating routing at coarse and fine resolution, including generating a coarse route corresponding to a set of blocks for a map, where each block has a defined width and height in units of cells, and generating first and second fine routes based on cells for different blocks of a subset of blocks that correspond to the coarse route. Further, the invention provides an ultimate route for the map for user display based on the first fine route and the second fine route.
To support large-map routing, the invention includes loading map tiles associated with regions into memory of a computing device, processing a first set of tiles associated with a first region, then determining and loading an unloaded set of tiles associated with a region yet to be processed. The loaded second set of tiles is prioritized over a third set that remains unloaded, the second set is processed as part of generating the route, and a visual representation of the generated route is provided for display using the first and second sets of tiles in memory.
Claims Coverage
The document provides three independent claims, each defining a different core aspect of the route-generation pipeline: traversal-map block/cell routing with route vectorization and map overlay presentation, coarse-to-fine route generation across blocks along a coarse route, and map-tile loading and prioritization to support route generation and presentation for display.
Traversal-map block/cell route vectorization with visual overlay
Generating a traversal map corresponding to terrain of a map with blocks comprising cells, generating a route between a route start-point and a route end-point within the map and comprising a subset of blocks, generating a vectorized route with vertices corresponding to cells within blocks of the subset, and generating a visual representation of the vectorized route overlaid on the map for presentation to a user.
Coarse route blocks and fine routes on different blocks along the coarse route
Generating a coarse route corresponding to a set of blocks for a map with each block having a width defined as a first unit of cells and a height defined as a second unit of cells, generating a first fine route based on cells for a first block of a subset of blocks that correspond to the coarse route, generating a second fine route based on cells for a second block different than the first block of the subset that correspond to the coarse route, and providing an ultimate route for the map to a user computing device for display based on the first fine route and the second fine route.
Incremental map-tile loading with priority and visual route provision
Loading into memory of a computing device a first set of map tiles associated with a first region of a map, processing the first set of tiles as part of generating a route, determining based on the generating to load an unloaded set of map tiles associated with a region yet to be processed, loading into the memory a second set of map tiles associated with a second region when the second set is prioritized over a third set of map tiles that is unloaded, processing the second set of tiles as part of generating the route, and providing based on the first and second sets of map tiles in memory a visual representation of the generated route for display to a user.
Across the three independent claims, the inventive coverage spans block/cell traversal-map routing with vectorized vertices and a visual overlay, coarse route generation over blocks followed by fine routes for different blocks along the coarse route to form an ultimate route for user display, and incremental loading of map tiles with tile-set prioritization to enable route generation and visual route presentation based on tiles stored in memory.
Stated Advantages
Not explicitly described in patent.
Documented Applications
Not explicitly described in patent.
Interested in licensing this patent?