CN-122015846-A - Self-adaptive routless path planning system and method based on grid quantification

CN122015846ACN 122015846 ACN122015846 ACN 122015846ACN-122015846-A

Abstract

The invention relates to a self-adaptive rout planning system and method based on grid quantification, wherein the system comprises a data layer, a logic operation layer, an application layer and a grid tile generation layer, wherein the data layer provides a data reading interface for the logic operation layer, the logic operation layer comprises grid division, the logic operation layer comprises uniform square grid division of an area to be planned, grid quantification scoring, construction of a navigation body passing property scoring rule base, quantization scoring in each grid, final superposition of scores of various data, generation of grid tiles, generation of tiles from the grid quantized data, multi-level multi-resolution multiple tile data, grid routing, calculation of the path based on the tile grid data by utilizing a shortest path planning algorithm, dynamic loading of required tile data during path searching, and the application layer comprises operation control of the logic operation layer and result output control of upper layer application. The method solves the problems of single grid granularity, insufficient environment characteristic expression, weak dynamic planning capability and the like of the path planning technology.

Inventors

WANG GUANGMIN
LIU JIALING
LUO LIN
YANG HUI
CHENG HONGJUN
ZHANG HAOBO
ZHU MINSHENG

Assignees

华东计算技术研究所（中国电子科技集团公司第三十二研究所）

Dates

Publication Date: 20260512
Application Date: 20260116

Claims (8)

1. An adaptive routless path planning system based on grid quantization, the system comprising: The data layer provides a data reading interface for the logic operation layer and comprises road network data, digital elevation data, geological data, topography data, dynamic data and other data; the logic operation layer comprises grid division, grid quantization scoring, grid tile generation and path planning, and is specifically as follows: grid division, namely uniformly square grid division is carried out on the area to be planned; the grid quantization scoring comprises the steps of constructing a navigation body trafficability scoring rule base, namely, a scoring rule of a navigation body under each data, and dynamically adjusting the scoring rule, wherein for each data, the quantization scoring is carried out in each grid, the scoring basis is derived from the navigation body trafficability scoring rule base, the score is normalized, and the scoring of a plurality of data is finally overlapped and then normalized; Generating grid tiles, namely, introducing a tile data organization mode, dividing complete grid data into sub-data areas with the same size, dividing a road-free grid area into four tile data sub-areas, wherein each tile data is a square area and comprises the same number of grids; grid path planning, namely calculating a path based on tile grid data by utilizing a shortest path planning algorithm, dynamically loading required tile data when searching the path, and releasing certain tile data from a memory after using the tile data; the application layer is the operation control of the logic operation layer and the result output control of the upper layer.
2. The adaptive carrierless path planning system based on grid quantization of claim 1, wherein the data layer comprises: Road network data, namely road network data used for path planning, wherein the data comprises attributes such as road grade, road width and road accessory information; The digital elevation data is used for calculating elevation information of each grid and further obtaining gradient and slope information of each grid; geological data, namely under the field environment, the navigation body is sensitive to the geological environment; the topography data comprises buildings, rivers, lakes, shrub vegetation, fences and guardrails, and is an obstacle for a navigation body and cannot pass through; dynamic data, namely data which can influence navigation traffic caused by sporadic events, wherein the dynamic data comprises bridge fracture and pavement collapse caused by natural disasters; other data, other factors that may affect navigation body traffic.
3. The adaptive carrierless path planning system based on grid quantization of claim 1, wherein the logic operation layer comprises: grid division, wherein the side length of the grid is 1-1.5 times of the length of the navigation body; Grid quantization score, wherein the quantization score is normalized to 0 and 1, the higher the score is, the better the trafficability is, the navigation passing-through scoring rule base is formed according to experience or technical personnel investigation scoring, Grid tile generation, namely enabling tile data required by path finding calculation to be dynamically loaded during path planning, and simultaneously releasing unnecessary tile data in time; grid path planning, namely utilizing an A-algorithm as a shortest path planning algorithm.
4. The adaptive routless path planning system based on grid quantification according to claim 1, wherein the grid partitioning adopts an adaptive grid partitioning rule, adopts a quadtree partitioning method, and is convenient for conducting grid dynamic partitioning or aggregation according to different navigation body shape parameters by recursively partitioning a two-dimensional space into four quadrants, and can adapt to various navigation bodies by utilizing the same set of grids through the partitioning and aggregation of grids.
5. The adaptive carrierless path planning system based on grid quantization of claim 1, wherein the grid quantization scoring uses a multi-data factor fast grid quantization rule, and when each grid is quantized, the following grid scoring rule is formulated: evaluating the trafficability of all grids for each factor, finding out all grids meeting the 'one-ticket overrule system', wherein the trafficability is marked as 0, and the trafficability is marked as 1 if the trafficability is not met; overlapping the evaluation result of each factor on each grid, wherein when the trafficability of any factor is 0, the trafficability of the grid is 0, otherwise, the trafficability of the grid is 1; And sequentially re-scoring all the overlapped grids with the trafficability of 1.
6. The grid quantization based adaptive routless path planning system of claim 1, where in grid tile generation, tile data structure: Each tile data contains the following data: the tile range is that the latitude and longitude range covered by the tile is expressed by the latitude and longitude of the lower left point and the latitude and longitude of the upper right point of the tile, namely, the minimum longitude, the minimum latitude, the maximum longitude and the maximum latitude are expressed; index or data information of grids contained in the tiles, which grids are covered by the tiles, available grid index or specific grid information; storing the tile numbers around the tile, storing the connectivity of the tile and the tile, storing the information so as to quickly find the next tile to be loaded when seeking a road, and quickly judging whether the next tile to be loaded is needed or not; the tiles need to be encoded, namely each tile has a unique number; tile partitioning rules: Each tile is a square area with the same size and consistent coverage, and is an integer multiple of the grid side length in the longitude and latitude ranges; the tile size is matched and configured according to actual operation, and the tile side length is 10-50 times of the grid side length.
7. The grid quantization-based adaptive routless path planning system of claim 1, wherein the grid path planning further comprises the steps of accessing the dynamic data into the path planning data in real time in actual application, and performing grid quantization on the dynamic data by utilizing a shortest path planning algorithm, and performing space superposition calculation with an original grid quantization result.
8. A grid quantization based adaptive routless path planning method, for implementing the grid quantization based adaptive routless path planning system as set forth in any one of claims 1-7, comprising: step 1) meshing the range of the non-path data; Step 2) carrying out gridding scoring on each data in the range, wherein the final result of each grid is normalized trafficability scoring, and the higher the scoring is, the better the trafficability is; Step 3) generating tiles for grid merging organization; Step 4) path planning is carried out on the grid after grading to form a path from a starting point to an end point; Step 4.1) inputting path planning data, including longitude and latitude of a starting point, navigation body type and specific length, width, height and weight parameters; Step 4.2) loading tile data of the starting point and the ending point, and carrying out path finding by utilizing a shortest path algorithm; step 4.3) judging the new data position traversed by the path searching, judging whether new tile data are to be loaded or not, and timely releasing the used tile data; Step 4.4) searching for the shortest path to the endpoint.

Description

Self-adaptive routless path planning system and method based on grid quantification Technical Field The invention relates to an intelligent navigation and path planning technology, in particular to a general path planning system based on a grid quantification method, which is suitable for dynamic path generation under the condition of no-road network topography. Background 1. State of the art For the scenes without clear roads, such as off-road, field operation and the like, researchers develop path planning methods based on environments, such as grid maps, voronoi maps and the like. Such techniques enable feasible path searches in the no-path region through environmental modeling and obstacle detection. The method is technically characterized by 1) adopting an environment discretization processing method, 2) having stronger environment adaptability, and 3) having higher path safety. 2. Problems associated with the prior art 2.1 The limitation of the grid quantification method is that the existing grid quantification method solves the problem of environmental modeling to a certain extent, but still has obvious defects: the grid granularity is single, namely 1) the grid with fixed size is difficult to adapt to planning requirements of different precision, 2) the calculation amount is excessive or the precision is insufficient in a complex environment, and 3) the reconstruction of data is required to be independently carried out for each navigation body. The environment characteristic expression is insufficient, namely 1) the traditional grid mainly represents obstacle information, and 2) quantitative expression of multidimensional characteristics such as terrain gradient, surface attachment coefficient and the like is lacking. 2.2 The dynamic programming capability is weak, and the prior related technology shows obvious defects when dealing with dynamic environment changes: The real-time performance is poor, 1) the re-planning response speed is low, and 2) the real-time performance requirement in a high-speed moving scene cannot be met. Disclosure of Invention The application aims to carry out grid quantization on a non-path area by utilizing a grid quantization method, comprehensively considers the maneuverability of a navigation body to score the quantized grid, carries out A-calculation on a grid map after the quantization scoring, and provides a self-adaptive non-path planning system and method based on grid quantization, so as to solve the problems of single grid granularity, insufficient environmental characteristic expression, weak dynamic planning capacity and the like of the conventional path planning technology, and meanwhile, a grid dynamic updating mechanism is added to solve the problem of weak dynamic planning capacity. The technical scheme of the invention is as follows: an adaptive routless path planning system based on grid quantization, the system comprising: The data layer provides a data reading interface for the logic operation layer and comprises road network data, digital elevation data, geological data, topography data, dynamic data and other data; the logic operation layer comprises grid division, grid quantization scoring, grid tile generation and path planning, and is specifically as follows: grid division, namely uniformly square grid division is carried out on the area to be planned; the grid quantization scoring comprises the steps of constructing a navigation body trafficability scoring rule base, namely, a scoring rule of a navigation body under each data, and dynamically adjusting the scoring rule, wherein for each data, the quantization scoring is carried out in each grid, the scoring basis is derived from the navigation body trafficability scoring rule base, the score is normalized, and the scoring of a plurality of data is finally overlapped and then normalized; Generating grid tiles, namely, introducing a tile data organization mode, dividing complete grid data into sub-data areas with the same size, dividing a road-free grid area into four tile data sub-areas, wherein each tile data is a square area and comprises the same number of grids; grid path planning, namely calculating a path based on tile grid data by utilizing a shortest path planning algorithm, dynamically loading required tile data when searching the path, and releasing certain tile data from a memory after using the tile data; the application layer is the operation control of the logic operation layer and the result output control of the upper layer. Further, the data layer specifically includes: Road network data, namely road network data used for path planning, wherein the data comprises attributes such as road grade, road width and road accessory information; The digital elevation data is used for calculating elevation information of each grid and further obtaining gradient and slope information of each grid; geological data, namely under the field environment, the navigation body is sensitive to the geol