CN108763287B - Construction method of large-scale passable regional driving map and unmanned application method thereof - Google Patents
Construction method of large-scale passable regional driving map and unmanned application method thereof Download PDFInfo
- Publication number
- CN108763287B CN108763287B CN201810333301.4A CN201810333301A CN108763287B CN 108763287 B CN108763287 B CN 108763287B CN 201810333301 A CN201810333301 A CN 201810333301A CN 108763287 B CN108763287 B CN 108763287B
- Authority
- CN
- China
- Prior art keywords
- map
- tree
- subgraph
- sub
- vehicle
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 238000000034 method Methods 0.000 title claims abstract description 56
- 238000010276 construction Methods 0.000 title claims abstract description 18
- 238000013507 mapping Methods 0.000 claims abstract description 27
- 238000012423 maintenance Methods 0.000 claims abstract description 6
- 230000008569 process Effects 0.000 claims description 20
- 230000004888 barrier function Effects 0.000 claims description 10
- 230000004927 fusion Effects 0.000 claims description 8
- 238000000638 solvent extraction Methods 0.000 claims description 7
- 230000003044 adaptive effect Effects 0.000 claims description 5
- 238000001914 filtration Methods 0.000 claims description 3
- 230000007246 mechanism Effects 0.000 claims description 2
- 230000002093 peripheral effect Effects 0.000 claims description 2
- 230000011218 segmentation Effects 0.000 claims description 2
- 238000012217 deletion Methods 0.000 claims 1
- 230000037430 deletion Effects 0.000 claims 1
- 238000003780 insertion Methods 0.000 claims 1
- 230000037431 insertion Effects 0.000 claims 1
- 239000013589 supplement Substances 0.000 claims 1
- 230000001502 supplementing effect Effects 0.000 abstract 1
- 238000000605 extraction Methods 0.000 description 9
- 238000010586 diagram Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 230000000903 blocking effect Effects 0.000 description 2
- 238000007726 management method Methods 0.000 description 2
- 230000009466 transformation Effects 0.000 description 2
- 238000012935 Averaging Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 238000007796 conventional method Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 230000004807 localization Effects 0.000 description 1
- 230000005055 memory storage Effects 0.000 description 1
- 230000008447 perception Effects 0.000 description 1
- 238000012216 screening Methods 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3407—Route searching; Route guidance specially adapted for specific applications
- G01C21/3415—Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Traffic Control Systems (AREA)
Abstract
本发明大规模可通行区域驾驶地图的构建方法及其无人驾驶应用方法是一种面向无人驾驶需求的大规模可通行区域驾驶地图的全自动建图、更新以及在线分发方法。本发明提出了一种基于多线激光雷达的大规模可通行区域地图的全自动建图、更新方法与在线分发方法。利用装备有多线激光雷达的采集车实现地图构建与更新，将建图结果上传至服务器进行维护，服务器通过响应多辆无人车的在线请求分发其周边的可通行区域高精地图，从而为无人驾驶提供决策和规划参考，补充甚至部分取代无人车的自身传感器系统。可为道路上运行的多辆无人车提供高精度、高可用的可通行区域地图服务，能够提高无人驾驶的安全性并大幅降低单辆无人车传感器配置成本。
The method for constructing a large-scale passable area driving map and the unmanned driving application method of the present invention is a fully automatic mapping, updating and online distribution method for a large-scale passable area driving map oriented to the needs of unmanned driving. The invention proposes a fully automatic mapping, updating method and online distribution method of a large-scale passable area map based on multi-line laser radar. Use the acquisition vehicle equipped with multi-line lidar to realize map construction and update, upload the map construction results to the server for maintenance, and the server distributes the high-precision map of the passable area around it by responding to the online requests of multiple unmanned vehicles, so as to provide Unmanned driving provides decision-making and planning reference, supplementing or even partially replacing the self-driving car’s own sensor system. It can provide high-precision and high-availability map services of passable areas for multiple unmanned vehicles running on the road, which can improve the safety of unmanned vehicles and greatly reduce the cost of sensor configuration for a single unmanned vehicle.
Description
Technical Field
The invention relates to a full-automatic map building, updating and online distribution method of a large-scale passable regional driving map facing to the unmanned driving requirement. The method can provide high-precision and high-availability passable regional map service for a plurality of unmanned vehicles running on the road, and can improve the safety of unmanned driving and greatly reduce the configuration cost of a single unmanned vehicle sensor as autonomous decision reference and driving guarantee.
Background
The current unmanned driving demands for high-precision driving maps are increasing day by day, and the existing manual or semi-automatic map building method relying on manual work is rich in information, low in efficiency, difficult to update and high in cost. High-precision mapping and storage cost based on laser radar original point cloud is high, and the method is difficult to expand to large scale and share with multiple vehicles. And the feature mapping based on computer vision is mainly used for positioning and cannot provide a passable area range required by unmanned vehicle decision making. A common mapping method based on probability grids in the robot field can realize full-automatic mapping of obstacle distribution in a small-range area, such as an indoor space. However, the prior art is limited by the capacity of the probability grid memory storage, and cannot be expanded to large-scale scenes. Therefore, there is a need for an automated, highly available, and large-scale mapping and updating system to meet the map requirements of unmanned vehicle driving.
Disclosure of Invention
The invention provides a full-automatic map building and updating method and an online distribution method of a large-scale passable regional map based on a multiline laser radar, and aims at the unmanned application requirement. The method comprises the steps that map construction and updating are achieved through a collection vehicle equipped with a multi-line laser radar, a map construction result is uploaded to a server for maintenance, the server distributes high-precision maps of passable areas around the unmanned vehicles through responding to online requests of the unmanned vehicles, decision and planning references are provided for unmanned driving, and a sensor system of the unmanned vehicles is supplemented or even partially replaced.
The technical scheme adopted by the invention is as follows (attached to a system flow chart 11):
technical scheme one of method needing protection
A construction method of a large-scale passable area driving map is characterized by comprising the following steps:
1. on the acquisition vehicle system, scanning a road environment by using a multi-line laser radar, and realizing ground filtering and barrier segmentation by using elevation difference to obtain a real-time road boundary barrier distribution map; and performing trafficable region probability grid mapping on road boundary barrier distribution of multiple frames by combining high-precision pose information provided by a differential Global Navigation Satellite System (GNSS) and inertial navigation equipment. (this step follows the conventional technique which has been generally used)
2. On the acquisition vehicle system, in the probability grid graph building process, self-adaptive subgraph block building is carried out according to the radar frame number and the acquisition vehicle motion variation, and R-Tree is introduced to build a spatial index by taking subgraphs of different sizes as nodes. And moving the nodes far away from the acquisition vehicle out of the memory in real time according to the R-Tree and storing the nodes on the disk, and simultaneously reading back the memory of the nodes close to the acquisition vehicle existing in the disk, thereby realizing dynamic memory scheduling in the process of establishing the graph and realizing large-scale graph establishment (the step is one of innovations of the method).
3. And storing the R-Tree and all node data thereof to a disk after the map is built and suspended. The map building process can be continuously read and recovered by the acquisition vehicle map building system, so that the map building of the built map area is updated and expanded, and the acquisition vehicle system realizes the automation of map large-scale map building and updating (the step is one of innovations of the method).
Method technical scheme II needing protection
1. The unmanned application method of the large-scale passable regional driving map after being constructed is characterized in that after a collection vehicle system completes map construction, R-Tree and all sub-map data thereof are uploaded to a server, and map online distribution service is provided. The server responds to concurrent requests of a plurality of unmanned vehicle clients, utilizes the R-Tree index to quickly search subgraph nodes adjacent to the unmanned vehicle clients, fuses the subgraph nodes and sends the subgraph nodes to the unmanned vehicles in real time, so that the subgraph nodes are assisted to carry out high-precision passable area maps in a visible range, and decision and planning processes of unmanned driving are assisted (the step is innovative by the method).
The invention has the beneficial effects that:
1. the full-automatic map building and updating of the high-precision passable regional map facing to the unmanned driving requirement are realized, manual interaction is not needed, the map building process can be interrupted and recovered, and the technical usability is high;
2. the map building result is maintained through the server, map requests of a plurality of unmanned vehicle clients can be responded in a concurrent mode, high-precision passable area map fusion results are distributed quickly according to needs, and therefore the sensing cost of the unmanned vehicle system is reduced, and the cost of the unmanned vehicle sensing system can be effectively reduced;
the innovation points are as follows:
1. based on the spatial index of the integrated R-Tree, efficient subgraph search and dynamic memory scheduling are realized in map building, updating, expanding and map distribution services, so that map building of any scale and real-time map distribution and fusion can be realized under the condition of limited memory occupation;
the map of the passable area with high availability and high precision for the unmanned vehicle system is provided, the defects of the sensor of the unmanned vehicle can be overcome, the configuration cost is reduced, and the driving safety is improved.
Drawings
FIG. 1 schematic of a map collection vehicle processing platform
FIG. 2 extraction of front and rear effects of passable road region (front (a); rear (b))
FIG. 3 is a flow chart of adaptive map partitioning and dynamic memory scheduling (step 2)
FIG. 4R-Tree spatial index graphic representation (where R8-R19 recite specific two-dimensional geometric data in part)
FIG. 5 subgraph and Global map schematic
FIG. 6 is a flowchart of map updating and expanding (step 3)
FIG. 7 is a flow chart of client request and processing (step 4)
FIG. 8 is an example of a mapping result of a large navigable area
FIG. 9 navigable area map fusion results
FIG. 10 is a schematic diagram of a map processing and distributing system in embodiment 2
FIG. 11 is a block flow diagram of a system and application for creating a graph
Detailed Description
The driving path planning of the unmanned vehicle depends on the perception of the surrounding environment, and the sensor is limited by factors such as resolution, shielding and weather, so that the passable area range is difficult to robustly extract. Therefore, high-precision automatic map construction is carried out on passable areas limited by static barriers such as road edges and guardrails by the collected vehicles, and online distribution is carried out by using the server, so that high-availability passable area map information can be provided for a plurality of unmanned vehicles, the correctness of decision and path planning is ensured, the dependence of the unmanned vehicles on sensors is reduced, and the cost of the unmanned vehicles is further reduced. Based on the technical scheme of the invention, the technical scheme of the invention is described in more detail with reference to the accompanying drawings.
The steps are as follows in sequence:
example 1
Construction process of large-scale passable area driving map
1. Extraction of passable region and probability grid construction map
1.1 passable region extraction based on multiline lidar
The road environment around the vehicle is scanned by a multiline lidar (see fig. 1) arranged on an acquisition platform truck. And obtaining road boundary obstacle distribution by using a point cloud screening method based on the height difference, namely passing areas.
1.1.1 multiline lidar layout and external parameter calibration
The invention adopts a multi-line laser radar (a plurality of 16 lines, 32 lines or a single 64 lines and the like) which is arranged on the roof of a collecting vehicle. Enabling its scanning area to cover the entire road area. And calibrating the external parameters of the laser radar by an automatic or manual method. And converting the three-dimensional point cloud expressed in the radar coordinate system into a vehicle local positioning coordinate system through coordinate system transformation.
1.1.2 passable region extraction
Dividing the visible plane range of the radar into grid units with the size of 1m x 1m, and counting the minimum value z of the cloud height values of three-dimensional points in each grid unit areaminGiven a threshold value Δ1The coordinates in the point cloud data of the area satisfy z-zmin>Δ1The points of (a) are marked as obstacle points. The obstacle points are then projected onto a two-dimensional grid cell map (e.g., 0.2m x 0.2m) of the resolution required to construct the map. And traversing the grid units, counting the number of the barrier points in each grid unit, and comparing the number with the vertical passable range of the vehicle. If the obstacle point is located in the passing range of the vehicle, the grid cell is marked as an obstacle cell, and the rest are passable areas. The passable area extraction is as shown in fig. 2 before and after.
1.2 probability grid map of passable area
Because the extraction result of the passable area of a single frame may cause the robustness problem due to noise and the like, the probability grid mapping method needs to use the extraction results of multiple frames to construct the probability grid map. And establishing a Cartesian coordinate system by taking the starting point of the map as the origin of the coordinate system of the global map, wherein the positive east and the positive north are respectively the positive directions of X, Y. In the mapping process, the high-precision pose of the acquisition vehicle is acquired in real time, and the point cloud is converted from the vehicle local positioning coordinate system to the global coordinate system (see step 1.2.1). And initializing and updating the probability value of the barrier in the grid unit map by using the extraction result of the multi-frame passable area, so as to realize the construction of a probability grid map (see step 1.2.2).
1.2.1 pose data acquisition and coordinate System transformation
And the RTK GPS, inertial navigation and vehicle speed information are fused through the extended Kalman filtering, so that high-frequency and high-precision vehicle pose data are acquired in good and temporary missing areas of the RTK GPS. The coordinates of the obstacle in the passable area are then converted from the vehicle local localization coordinate system to the global coordinate system (equation 1) using coordinate conversion.
Wherein P (P)x_global,py_global) Representing the coordinates of the obstacle mesh in a global coordinate system, P (P)x_local,px_local) And representing the coordinates of the obstacle grid under the vehicle local positioning coordinate system, wherein theta is a course angle, and delta x and delta y are offsets between the origin of the vehicle local positioning coordinate system and the origin of the mapping.
1.2.2 probability grid map initialization and update
The probability grid map describes the likelihood of a certain map grid cell as an obstacle using probability values. A higher set probability value represents a higher probability that the grid cell is an obstacle. Dividing the corresponding grid cells in the probability grid map into two sets of barrier (hit) and barrier-free (miss) based on the accessible region extraction result of each frame, and distributing probability value phit0.55 or pmiss0.45. If the grid cells are initialized, the result is subsequently extracted according to the passable area of each frameProbability updating is performed on the grid cell probability values (see equation 2).
Wherein M isnewFor updated grid cell probability values, MoldFor the pre-update grid cell probability values, clamp is a function that limits the valid range of probability values.
2. Adaptive blocking and dynamic memory scheduling
The probability grid map in step 1 needs to allocate a memory space with a fixed size according to the mapping range, so that the probability grid map is difficult to be expanded to mapping application in a large-scale scene due to the limitation of the memory size. Therefore, in order to realize large-scale map building, the probability grid map needs to be subjected to self-adaptive partitioning and a subgraph is built. The invention also provides a method for constructing R-Tree space index for the subgraph and realizing the dynamic scheduling mechanism of the subgraph, which realizes the basic constancy of memory occupation and has a flow chart shown in figure 3.
The details are as follows:
2.1 map adaptive partitioning
A self-adaptive map blocking method is provided, which integrates the number of radar scanning frames and the motion variation of a collection vehicle, and automatically blocks a grid map in the map building process. First, the initial sub-graph range is a range a with the current position as the center point0*a0A square area of (a). And when the number of effective scanning frames exceeds a set threshold or the collection vehicle moves out of the range of the subgraph, finishing the construction of the current subgraph. The sub-graph is assigned an ID and a minimum outer bounding rectangle (MBR) of the sub-graph is created and inserted as a node into the R-Tree. While a sub-graph is created and initialized for receiving data, adjacent sub-graphs contain overlapping parts (about 10% of the sub-graph size).
2.2 dynamic scheduling of memory based on R-Tree
The R-Tree is a dynamic balance search Tree, and the average operation complexity of the R-Tree and various varieties thereof is logarithmic, so that the operations of inserting, updating, deleting, searching and the like of indexes of the space object represented by the MBR can be efficiently performed.
2.2.1 maintenance of R-Tree
Each node in the R-Tree includes 1 to n units consisting of a subpicture number ID and an MBR of a spatial object, i.e., (MBR, ID). Wherein n is an adjustable parameter used for clustering adjacent units so as to reduce the index data volume. When a subgraph node is newly added into the R-Tree, the inserting position is selected to add the new node according to the principle of minimizing the MBR overlapping area of the R-Tree node, the subgraph ID is used as the unique identification index of the node, and the x is calculated by the space coordinate of the subgraphmin、yminAnd xmax、xmaxAnd the range attribute determines the MBR of the subgraph. (FIG. 4 is an example of a map R-Tree structure).
2.2.2 dynamic scheduling method for internal memory
In the real-time graph building process, after the sub-graph blocks are added into the R-Tree, space query is carried out on the basis of the R-Tree (see step 4.2), n sub-graphs near the current position of the vehicle are searched, and the rest sub-graphs are written out according to the identification IDs, transferred and stored to a disk and removed from a memory. And when the vehicle moves to the established map area, searching node numbers through the R-Tree index, reading corresponding sub-map blocks by a magnetic disk, loading the sub-map blocks into a memory, and updating the grid map. Therefore, the subgraph dynamically moves out and reads back in the memory and the disk, dynamic scheduling of the memory is realized, constant memory occupation of the graph building system is ensured, and large-scale graph building is realized (the subgraph and global map result is shown in fig. 5).
3. Automatic expansion and updating of large-scale passable area map
Because the map building of a large-scale area cannot be completed once in practical use, and the map needs to be updated due to road building, route change and other reasons, the map building result is required to be easy to update and expand.
The mapping system provided by the invention can be restored to the last mapping process according to the current position coordinate by using a dynamic scheduling method: and after the map is built, outputting the generated map file of the passable area, and simultaneously storing the initial position coordinate of the map and the R-Tree spatial index of the sub-map block information to a magnetic disk.
When the map needs to be expanded or updated, the sub-graph files in the disk, the corresponding R-Tree spatial index and the initial position configuration information are read, the mapping system can be restored to the previous mapping process, the map is subjected to probability updating and new area expansion mapping from any position on the basis of the existing mapping area, incremental mapping and automatic updating are achieved, and mapping and maintenance of the large-scale map are achieved, and the process diagram is shown in
Fig. 6.
Example 2
The following step 4 is further provided on the basis of example 1 to introduce the application of the map in unmanned driving
4. Accessible regional map management and application, the flow chart is shown in fig. 7.
In order to realize the concurrent map service of the unmanned vehicle client, a server platform is constructed by a MapServer open source map engine and is used for publishing the large-scale passable area driving map finally established based on the embodiment 1. Because the whole passable area map is composed of a plurality of overlapped subgraphs, the tasks of subgraph search, fusion and online distribution are efficiently completed through R-Tree space index according to the position coordinates of the client. And for the overlapped areas of the multiple sub-images, fusing the probability grids of the overlapped areas in a weighting mode to generate a final passable area binary map.
4.1 location-based client search request
When a client side sends a map request to a server in unmanned driving, based on the position of the user, the server side utilizes the R-Tree corresponding to the sub-graph data to perform adjacent sub-graph search (the specific method is shown in the implementation step 4.2), and the sub-graph data which is inquired to meet the distance condition is used as a fusion object.
4.2R-Tree based subgraph search
After a search request with a rectangle with the peripheral range (L x W) of a vehicle body of a client side as a space target search rectangle is given, recursive traversal is carried out from a root node of the R-Tree, a node pointer contained in the R-Tree is traversed from top to bottom in a mode of average time complexity O (logN), space polygon containing query is carried out (N is the total number of index data), and N sub-graph index IDs near the current position of the vehicle are rapidly queried and obtained.
4.3 subgraph fusion
Assigning values w to n sub-graphs containing overlapping regions according to timestampsiProbability p of map grid of final passable areaiWeighted averaging is performed to obtain an obstacle probability value representation result p' (equation 3). Taking a probability threshold value theta as an obstacle classification basis, and taking p'>The grid cells of θ are marked as obstacles, and a binary map of the area where no-one vehicles can pass can be obtained, as shown in fig. 8. According to the pose of the unmanned vehicle client, a local map of the unmanned vehicle in the passable area under the current pose can be obtained, high-precision analysis reference is provided for driving decision and path planning (as shown in fig. 9), and the sensing range and the obstacle result of a vehicle sensor are supplemented.
4.4 Online distribution
The system is based on a mature map engine, can respond to map requests of multiple clients, realizes rapid map downloading and caching, and meets the real-time requirement of unmanned driving. The map management and distribution system flow is shown in fig. 10.
Claims (3)
1. A construction method of a large-scale passable area driving map is characterized by comprising the following steps:
step 1, scanning a road environment by using a multi-line laser radar on a vehicle collection system, and realizing ground filtering and barrier segmentation by using elevation difference to obtain a real-time road boundary barrier distribution map; combining high-precision pose information provided by a differential global satellite navigation system and inertial navigation equipment, and performing trafficable region probability grid mapping on road boundary barrier distribution of multiple frames;
step 2, on the acquisition vehicle system, performing adaptive subgraph block construction according to the radar frame number and the acquisition vehicle motion variation quantity in the probability grid graph construction process, and introducing R-Tree to construct a spatial index by taking subgraphs of different sizes as nodes; moving the nodes far away from the acquisition vehicle out of the memory and storing the nodes on a magnetic disk in real time according to the R-Tree, and simultaneously reading back the memory of the nodes close to the acquisition vehicle existing in the magnetic disk, thereby realizing dynamic memory scheduling in the process of establishing the graph and realizing large-scale graph establishment;
step 3, storing the R-Tree and all node data thereof to a disk after the construction of the map is paused; the acquisition vehicle map building system continues to read and recover the map building process, so that the map building of the built map area is updated and expanded, and the acquisition vehicle system realizes the automation of large-scale map building and updating of the map;
the probability grid map in the step 1 allocates a memory space with a fixed size according to the mapping range, so that the probability grid map is limited by the memory size and is difficult to expand to mapping application in a large-scale scene; therefore, in order to realize large-scale map building, the probability grid map is subjected to self-adaptive partitioning to build a sub-map; constructing an R-Tree space index for the subgraph, and realizing the basic constancy of memory occupation by a method of realizing a dynamic scheduling mechanism of the subgraph;
the details are as follows:
2.1 map adaptive partitioning
Providing a self-adaptive map partitioning method, which integrates the number of radar scanning frames and the motion variation of an acquisition vehicle, and automatically partitioning a grid map in the map building process; first, the initial sub-graph range is a range a with the current position as the center point0*a0A square region of (a); when the number of effective scanning frames exceeds a set threshold or the collection vehicle moves out of the range of the subgraph, completing the construction of the current subgraph; assigning an ID to the subgraph and creating a minimum outer bounding rectangle (MBR) of the subgraph, which is inserted into the R-Tree as a node; simultaneously, a sub-graph is newly built and initialized for receiving data, and adjacent sub-graphs contain overlapping parts;
2.2 dynamic scheduling of memory based on R-Tree
The R-Tree is a dynamic balance search Tree, and the average operation complexity of the R-Tree and various varieties thereof is logarithmic, so that the spatial object represented by the MBR is subjected to index insertion, updating, deletion and search operation;
2.2.1 maintenance of R-Tree
Each node in the R-Tree comprises 1 to n units consisting of a subgraph number ID and an MBR of a spatial object; n is an adjustable parameter and is used for clustering adjacent units so as to reduce the index data volume; when a subgraph node is newly added into the R-Tree, the inserting position is selected to add the new node according to the principle of minimizing the MBR overlapping area of the R-Tree node, the subgraph ID is used as the unique identification index of the node, and the x is calculated by the space coordinate of the subgraphmin、yminAnd xmax、ymaxDetermining MBR of the subgraph according to the range attribute;
2.2.2 dynamic scheduling method for internal memory
In the real-time graph building process, after sub-graph blocks are added into the R-Tree, space query is carried out on the basis of the R-Tree, n sub-graphs near the current position of the vehicle are searched, and the rest sub-graphs are written out according to the identification ID, transferred and stored to a disk and removed from a memory; when the vehicle moves to the established map area, searching node numbers through R-Tree indexes, reading corresponding sub-map blocks by a magnetic disk, loading the sub-map blocks into a memory, and updating the grid map; therefore, the subgraph carries out dynamic moving-out and read-back in the memory and the disk, realizes dynamic scheduling of the memory, ensures constant memory occupation of the graph building system, and realizes large-scale graph building.
2. The method for constructing the large-scale trafficable region driving map according to claim 1, wherein the mapping system in step 3 recovers to the previous mapping process according to the current position coordinates by using a dynamic scheduling method: after the map building is completed, outputting the generated map file of the passable area, and simultaneously storing the initial position coordinate of the map and the R-Tree spatial index of the sub-map block information to a magnetic disk;
when the map needs to be expanded or updated, the sub-graph files in the disk, the corresponding R-Tree spatial index and the initial position configuration information are read, the map building system is recovered to the previous map building process, on the basis of the existing map building area, the map is subjected to probability updating and new area expansion map building for many times from any position, incremental map building and automatic updating are achieved, and therefore large-scale map building and maintenance are achieved.
3. A method for applying a large-scale passable regional driving map in unmanned driving after the map is built is characterized in that after a collection vehicle system completes map building, R-Tree and all sub-map data thereof are uploaded to a server, and map online distribution service is provided; the server responds to concurrent requests of a plurality of unmanned vehicle clients, utilizes the R-Tree index to quickly search subgraph nodes adjacent to the unmanned vehicle clients, fuses the subgraph nodes and sends the subgraph nodes to the unmanned vehicles in real time, so that the subgraph nodes are assisted to carry out high-precision passable area maps in a beyond visible range, and decision and planning processes of unmanned driving are assisted;
the method comprises the following steps:
4.1 location-based client search request
When a client side sends a map request to a server in unmanned driving, based on the position of a user, the server side utilizes an R-Tree corresponding to the sub-graph data to perform adjacent sub-graph search, and the sub-graph data which meets the distance condition after being inquired is used as a fusion object;
4.2R-Tree based subgraph search
After a search request with a rectangle with the peripheral range of L W of a vehicle body of a client side as a space target search rectangle is given, performing recursive traversal from a root node of the R-Tree, performing space polygon inclusion query by traversing node pointers contained in the R-Tree from top to bottom in an average time complexity O (logN) mode, and rapidly querying and obtaining n sub-graph index IDs near the current position of the vehicle; n is the total number of index data;
4.3 subgraph fusion
Assigning values w to n sub-graphs containing overlapping regions according to timestampsiProbability p of map grid of final passable areaiCarrying out weighted average, wherein i is 1,2.. n, and obtaining an obstacle probability value representation result p'; taking a probability threshold value theta as an obstacle classification basis, and taking p'>Marking the grid unit of theta as an obstacle, and then obtaining a binary map of the passable area of the unmanned vehicle; obtaining the passable area unmanned vehicle under the current pose according to the pose of the unmanned vehicle clientThe local map provides high-precision analysis reference for driving decision and path planning, and supplements the sensing range of a sensor of the vehicle and the obstacle result;
4.4 Online distribution
The system responds to the map requests of multiple clients based on the map engine, realizes rapid map downloading and caching, and meets the real-time requirement of unmanned driving.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810333301.4A CN108763287B (en) | 2018-04-13 | 2018-04-13 | Construction method of large-scale passable regional driving map and unmanned application method thereof |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810333301.4A CN108763287B (en) | 2018-04-13 | 2018-04-13 | Construction method of large-scale passable regional driving map and unmanned application method thereof |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN108763287A CN108763287A (en) | 2018-11-06 |
| CN108763287B true CN108763287B (en) | 2021-11-12 |
Family
ID=64010726
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810333301.4A Expired - Fee Related CN108763287B (en) | 2018-04-13 | 2018-04-13 | Construction method of large-scale passable regional driving map and unmanned application method thereof |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN108763287B (en) |
Families Citing this family (22)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109738910A (en) * | 2019-01-28 | 2019-05-10 | 重庆邮电大学 | A road edge detection method based on 3D lidar |
| DE102019107414A1 (en) * | 2019-03-22 | 2020-09-24 | Zf Automotive Germany Gmbh | Method and control device for a system for controlling a motor vehicle |
| CN109855630A (en) * | 2019-03-26 | 2019-06-07 | 盐城工学院 | A kind of Map building method of intelligent robot |
| CN110243369A (en) * | 2019-04-30 | 2019-09-17 | 北京云迹科技有限公司 | Drawing method and device are remotely built suitable for robot localization |
| CN110209750B (en) * | 2019-05-08 | 2022-04-26 | 杭州迦智科技有限公司 | Map processing method, device, storage medium and processor |
| CN110456745B (en) * | 2019-07-29 | 2022-08-23 | 湖南大学 | Full-automatic underground mining transportation system |
| CN110426035B (en) * | 2019-08-13 | 2023-01-24 | 哈尔滨理工大学 | Positioning and mapping method based on monocular vision and inertial navigation information fusion |
| CN110608739B (en) * | 2019-08-21 | 2021-07-27 | 深圳市人工智能与机器人研究院 | Method, system and electronic device for locating moving target in interference environment |
| CN110487293A (en) * | 2019-08-29 | 2019-11-22 | 湖南大学 | A kind of efficient and privacy paths planning method based on extensive road network |
| CN110851556B (en) * | 2019-11-20 | 2023-02-17 | 苏州博众智能机器人有限公司 | Mobile robot mapping method, device, equipment and storage medium |
| CN113498474B (en) * | 2020-01-21 | 2024-07-19 | 深圳元戎启行科技有限公司 | High-precision map updating method, device, computer equipment and storage medium |
| CN111397611B (en) * | 2020-03-05 | 2022-07-05 | 北京百度网讯科技有限公司 | Path planning method and device and electronic equipment |
| CN111623788A (en) * | 2020-05-29 | 2020-09-04 | 长沙酷哇人工智能及大数据产业技术研究院有限公司 | Construction method of high-precision map for unmanned driving |
| CN113805787A (en) * | 2020-06-11 | 2021-12-17 | 中移(苏州)软件技术有限公司 | Data writing method, apparatus, device and storage medium |
| CN112082565B (en) * | 2020-07-30 | 2022-12-09 | 西安交通大学 | Method, device and storage medium for location and navigation without support |
| CN111949753B (en) * | 2020-08-17 | 2024-10-29 | 三一机器人科技有限公司 | Large scene layer switching, positioning and transition method and device |
| CN112180940A (en) * | 2020-10-16 | 2021-01-05 | 三一机器人科技有限公司 | Mapping method and device for reverse positioning and vehicle operation method and device |
| CN115143977B (en) * | 2021-03-30 | 2025-07-08 | 武汉智行者科技有限公司 | Quick high-precision map construction method and device and vehicle |
| CN113220818B (en) * | 2021-05-27 | 2023-04-07 | 南昌智能新能源汽车研究院 | Automatic mapping and high-precision positioning method for parking lot |
| CN114609646B (en) * | 2022-03-16 | 2025-06-03 | 上海擎朗智能科技有限公司 | Laser mapping method, device, medium and electronic equipment |
| CN115407769A (en) * | 2022-08-05 | 2022-11-29 | 金陵科技学院 | Control method and system of mobile handling robot based on Cartographer algorithm |
| CN115326100B (en) * | 2022-10-17 | 2023-03-03 | 北京智行者科技股份有限公司 | Path planning method, device, automatic driving equipment and computer storage medium |
Family Cites Families (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101354261A (en) * | 2007-07-27 | 2009-01-28 | 北京灵图软件技术有限公司 | System and method for updating data of navigation system and navigation system |
| CN101719154B (en) * | 2009-12-24 | 2012-03-28 | 北京中科通图信息技术有限公司 | Grid structure-based spatial index establishing method and grid structure-based spatial index establishing system |
| CN102982487A (en) * | 2011-09-05 | 2013-03-20 | 镇江佳得信息技术有限公司 | Geographic information system for tap water pipeline network management |
| US9222791B2 (en) * | 2012-10-11 | 2015-12-29 | Microsoft Technology Licensing, Llc | Query scenarios for customizable route planning |
| CN104819724B (en) * | 2015-03-02 | 2018-04-03 | 北京理工大学 | A kind of autonomous travel assist system of Unmanned Ground Vehicle based on GIS |
| CN106441319B (en) * | 2016-09-23 | 2019-07-16 | 中国科学院合肥物质科学研究院 | A system and method for generating a lane-level navigation map of an unmanned vehicle |
-
2018
- 2018-04-13 CN CN201810333301.4A patent/CN108763287B/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN108763287A (en) | 2018-11-06 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN108763287B (en) | Construction method of large-scale passable regional driving map and unmanned application method thereof | |
| CN111220993B (en) | Target scene positioning method and device, computer equipment and storage medium | |
| CN112837414B (en) | Method for constructing three-dimensional high-precision map based on vehicle-mounted point cloud data | |
| CN113593017B (en) | Method, device, equipment and storage medium for constructing surface three-dimensional model of strip mine | |
| JP2019120927A (en) | Method and device for creating grid map | |
| CN114065339B (en) | A method for site selection of high tower construction based on three-dimensional visualization model | |
| CN108387241A (en) | Update the method and system of the positioning map of automatic driving vehicle | |
| US20210001891A1 (en) | Training data generation for dynamic objects using high definition map data | |
| CN115494533B (en) | Vehicle positioning method, device, storage medium and positioning system | |
| CN117576652B (en) | Road object identification method and device, storage medium and electronic equipment | |
| CN114509065B (en) | Map construction method, system, vehicle terminal, server and storage medium | |
| CN113838129A (en) | Method, device and system for obtaining pose information | |
| CN112991487A (en) | System for multithreading real-time construction of orthoimage semantic map | |
| CN115014329A (en) | Positioning initialization method and automatic driving system | |
| CN110174115B (en) | Method and device for automatically generating high-precision positioning map based on perception data | |
| KR102587445B1 (en) | 3d mapping method with time series information using drone | |
| CN114758086A (en) | Method and device for constructing urban road information model | |
| KR102408981B1 (en) | Method for Creating ND Map and Updating map Using it | |
| CN117685954B (en) | A multimodal semantic map construction system and method for mining areas | |
| CN110472327B (en) | Urban multi-layer temperature and humidity sensing space-time system design method | |
| KR102540634B1 (en) | Method for create a projection-based colormap and computer program recorded on record-medium for executing method therefor | |
| KR102540629B1 (en) | Method for generate training data for transportation facility and computer program recorded on record-medium for executing method therefor | |
| WO2023053670A1 (en) | Information processing method, program, and information processing device | |
| CN117075140A (en) | Dual-matching robust laser positioning method and system applied to dynamic environment | |
| CN113227713A (en) | Method and system for generating environment model for positioning |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20211112 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |