Search

CN-121977604-A - Off-road intelligent vehicle global path planning method based on bidirectional alternate search A

CN121977604ACN 121977604 ACN121977604 ACN 121977604ACN-121977604-A

Abstract

The invention is suitable for the technical field of intelligent vehicle path planning, and provides a global path planning method of an off-road intelligent vehicle based on bidirectional alternate search A.A first layer generates a global original broken line path through a bidirectional alternate search A.A hierarchical processing architecture is adopted in the method; and the second layer performs node filtering and smoothing processing on the path, eliminates redundant nodes and meets the kinematic constraint of the vehicle. The method effectively solves the problems of low path planning efficiency, poor terrain adaptability, insufficient path smoothness and the like in the off-road environment, and realizes safe, efficient and feasible global path planning. The planning path of the invention not only maintains the terrain traffic optimality, but also has continuous and conductive geometric characteristics, can be directly used for vehicle tracking control, and obviously improves the autonomous running capability of the off-road vehicle under complex terrain.

Inventors

  • ZHANG ZE
  • LIU KE
  • LEI YULONG
  • FU YAO
  • LIU YUTONG
  • WANG XINLEI
  • WANG XIANG

Assignees

  • 吉林大学

Dates

Publication Date
20260505
Application Date
20260409

Claims (8)

  1. 1. The global path planning method for the off-road intelligent vehicle based on the bidirectional alternate search A is characterized by comprising the following steps of: Step 1, building a global grid map, wherein the grid map comprises elevation information, and calculating the gradient and rolling resistance coefficient of each grid based on the elevation information; step 2, calculating the potential field of the rugged terrain based on the gradient and the rolling resistance coefficient, and determining the actual cost from the starting point to the current node in the A-algorithm And heuristic functions from the current node to the target node ; Step 3, adopting BAS strategy to search path, starting from the starting point Start the forward search from the end point Starting reverse search, and exchanging information of the current optimal boundary nodes of the two parties in real time in the forward search and reverse search processes so as to mutually guide the search direction of the other party; Step 4, when the forward search node and the backward search node meet, path splicing is carried out to generate a path from the starting point To the end point Is a broken line path of the original; step 5, filtering key nodes of the original broken line path, removing redundant nodes, and generating a sparse broken line path formed by the key nodes; And 6, carrying out path smoothing by adopting a Bezier curve based on key nodes in the sparse broken line path, and synchronously applying turning constraint, terrain constraint and connection constraint in the smoothing process, thereby realizing curvature continuity and heading smooth transition of the global path on the premise of ensuring path trafficability and terrain adaptability.
  2. 2. The global path planning method for an off-road intelligent vehicle based on the bidirectional alternate search a of claim 1, wherein the step 1 comprises the following specific steps: step 1.1, constructing a DEM; The construction method of the DEM comprises dividing a research area into square grids with equal size, recording an altitude, namely an elevation value, converting continuous curved surface topography into a two-dimensional matrix composed of square grids, wherein each element in the matrix represents the elevation value corresponding to the square grid; step 1.2, ground characteristic analysis; step 1.2.1, calculating the slope of the terrain; the terrain of the off-road environment is evaluated based on the DEM, and 3 is adopted for calculating the surface gradient 3 Moving window method to process the raster data, taking the raster to be calculated as center, taking the elevation values of 8 adjacent grids around it to calculate the east-west direction elevation change rate And the elevation change rate in the north-south direction : (1) (2) Wherein, the Is the length of the side of the grid, Is the elevation value of the grid; slope angle of intermediate grid The method comprises the following steps: (3) Gradient of slope Expressed in percent, then formula (3) becomes: (4) taking 40% of the intermediate value as a gradient constraint threshold, and endowing infinite passing cost with grid units with gradients exceeding the value; step 1.2.2, calculating the ground surface traffic cost based on the rolling resistance coefficient; introducing a rolling resistance coefficient as a traffic cost index to quantify traffic difficulty of different road surface types, wherein the rolling resistance coefficient is used for calculating the traffic difficulty of different road surface types Is defined as the ratio of the traction force required by the vehicle to overcome the deformation of the road surface to the normal load of the vehicle, is used for representing the softness degree and the passing difficulty of the road surface, and is characterized by the passing cost of the ground surface of the grid unit The definition is as follows: (5)。
  3. 3. the global path planning method for an off-road intelligent vehicle based on the bi-directional alternate search a of claim 2, wherein the step 2 comprises the following specific steps: Step 2.1, calculating a rugged topography potential field; Introducing artificial potential field method for any grid unit The repulsive force total potential field value The definition is as follows: (6) In the formula, The repulsive force intensity coefficient is used for adjusting the overall size of repulsive force; Is a grid unit To the first Undulating grid Is a distance of (2); Taking a fixed constant of 0.001 for an extremely small positive number, and preventing the time division mother from being equal to 0 when the distance is 0; Is a grid unit Total number of surrounding undulating grids; 2.2, improving the evaluation function; Introducing BAS strategy to heuristic function And simultaneously, according to the gradient calculation, the calculation of the earth surface passing cost based on the rolling resistance coefficient and the construction of a terrain potential field, setting a cost function as follows: (7) In the formula, Representing the total cost; The repulsive potential field value of the current node; 、 And The weight coefficient for each cost satisfies the addition equal to 1; Is an exponential weighting factor; 1) Practical cost In the iterative process of improving the algorithm A, from the current node Extending to child nodes When the actual cost of the child node needs to be updated In such a way that the actual cost from the starting point to the current node Adding the terrain passing cost of the current node to its extended child node, whereby the actual cost function improves as: (8) Wherein, the Is the current node; Is that Expansion child nodes of the point; Is the Euclidean distance between grids; Is the gradient of the grid; 2) Heuristic function Design two sub-functions And , To meet the vehicle kinematics constraints, ignoring the shortest path of the collision factor, A shortest path that satisfies the obstacle avoidance constraint but ignores the vehicle dynamics constraint; Is that And By the maximum value of (2) And The natural difference of calculated values under different distances realizes the dominance of different stages by taking the maximum value, and simultaneously considers the extra cost of estimating the obstacle in the path The modified heuristic functions are as follows: (9) (10) Wherein, the A basic estimation term as a heuristic function; Implementation is based on Reeds-Shepp curves; the method is realized by an improved ant colony algorithm, an obstacle area is set to be an unviewable area based on a grid map, a collision-free shortest path is searched through an ant colony pheromone positive feedback mechanism, and the path length of the section is taken as a function value; The estimated cost for modifying the modified heuristic function is corrected; the method comprises the steps that on a connection line between a current node and a father node, the Euclidean distance from the connection line is smaller than the number of obstacle points with set threshold values; and the unit obstacle cost coefficient is used for quantifying the influence degree of a single obstacle point meeting the condition on the estimated cost of the path.
  4. 4. The global path planning method for an off-road intelligent vehicle based on the bidirectional alternate search a of claim 1, wherein the step 3 comprises the following specific steps: Initialization phase, initializing forward open list Reverse open list And corresponding closed list 、 Initializing a forward and reverse father node pointer table; Termination condition judgment, if And (3) with If the paths are all empty, the paths do not exist, the searching fails, and the algorithm is terminated; Forward expansion if Non-empty, pop up the evaluation function value therein The smallest node is used as the current forward node Move it into Checking Whether or not to be present in If yes, judging that the two-way meeting is carried out, jumping to the step 4, otherwise, carrying out the two-way meeting on All 8 neighborhood feasible neighbor nodes of (a) If (if) Calculating the cost according to the evaluation function formula and updating ; Reverse expansion with current forward node To search for targets, the search step is the same as forward expansion.
  5. 5. The global path planning method for an off-road intelligent vehicle based on the bidirectional alternate search a of claim 1, wherein the specific steps of the step 5 are as follows: 1) Initializing with starting point As the current anchor point And add it to the set of key nodes ; 2) Forward search from current anchor point Initially, the subsequent nodes are connected sequentially and backward Judging Whether collision with an obstacle occurs; 3) Multiple constraint collision detection: alignment segment Executing four joint tests including geometric collision test, safety margin test, topography cost test and steering capability test, if all the four tests are passed, continuing to expand backwards, if any one of the four tests is not passed, stopping expanding the current anchor point; 4) Key node extraction, namely extracting the last collision-free node As key nodes, join a set of key nodes And set it as the new current anchor point ; 5) Iteratively performing, namely repeating the steps 2) to 4) until the current anchor point Reaching the end point And will Joining a set of key nodes ; 6) Path reconstruction, connecting key node set in turn And generating a filtered sparse polyline path.
  6. 6. The global path planning method for an off-road intelligent vehicle based on the bi-directional alternate search a of claim 5, wherein in step 5, the four joint tests are specifically: geometric collision test, namely adopting a straight line grid traversal method to ensure that no barrier grid is penetrated; safety margin inspection, namely ensuring that the safety distance between the line segment and the outer edge of all obstacle expansion areas is kept at least one grid; The terrain cost test comprises the steps of calculating the average unit terrain cost of the area where the line segment passes, and judging that the line segment cannot pass if the average unit terrain cost exceeds 1.5 times of the average cost of the corresponding section of the original path; Steering ability test, namely estimating the current anchor point of the vehicle And the course angle variation formed by the key node and the last key node ensures that the single steering angle does not exceed the maximum steering angle of the vehicle.
  7. 7. The global path planning method of intelligent off-road vehicle based on the bi-directional alternate search A of claim 5, wherein in said step 6, a third-order Bezier curve and control parameters for determining the position of the control point are introduced, the intermediate control point is parameterized into the form of "start point/end point + -scaling factor x segment length x heading vector" 、 And The control point generation mode of the three-order Bessel curve segment is as follows: (11) (12) (13) (14) Wherein, the Representing the direction of travel of the current segment just entered; representing the direction of travel to leave the current segment; representing the distance from the start point to the end point of the current segment; And Is a proportionality coefficient; Introducing control points to incorporate turn constraints, terrain constraints, and connection constraints, wherein: Turning constraint, namely after Bezier curve is generated, equidistant curvature sampling is carried out on the curve, so as to ensure the curvature of any point If the curve exceeds the limit, the curve bending degree is reduced by adaptively adjusting the control point parameters until the constraint is met; The terrain constraint comprises defining the path-terrain deviation cost, namely the weighted gradient and the resistance integral value of the area where the curve passes, if the deviation cost exceeds a preset threshold value, tightening the control points to the original fold line so as to avoid the smooth path from invading into the steep slope or the high resistance area; The connection constraint is that the adjacent Bessel curve segments are required to meet the condition that the positions of the adjacent Bessel curve segments are continuous and tangential at the connection points so as to ensure the smooth transition of the course of the global path, and the natural connection between the segments is realized by forced collinear adjustment of the control points of the front and rear segments, so that the steering abrupt change is avoided.
  8. 8. The off-road intelligent vehicle global path planning method based on bidirectional alternate search a of claim 7, wherein the scaling factor And Default to 0.5, if the curvature exceeds the preset threshold, reducing with a conventional step size of 0.05-0.1 And The curve is regenerated again until the constraint is met or the lower engineering experience value is smaller than 0.1, and 0.1 is taken as And Is a minimum of (2).

Description

Off-road intelligent vehicle global path planning method based on bidirectional alternate search A Technical Field The invention belongs to the technical field of intelligent vehicle path planning, and particularly relates to a global path planning method for an off-road intelligent vehicle based on bidirectional alternate search A. Background Path planning is one of the core functions of an intelligent vehicle to achieve autonomous navigation. Under a structured road scene, a path planning method based on a high-precision map and lane line constraint is relatively mature. However, the off-road environment has unstructured features such as no clear road sign, variable relief, complex ground properties and the like, and provides a serious challenge for the path planning algorithm. At present, the most widely applied algorithm in the field of global path planning is an A-algorithm, which guides the search direction through a heuristic function, can quickly generate a path from a starting point to an end point in a rasterized map, has completeness and optimality, and is widely applied to a path generation task of a mobile robot. The standard A algorithm has three significant defects in the application of the cross-country large-scale map, namely, firstly, the searching efficiency is low due to huge node expansion quantity, the real-time requirement is difficult to meet, secondly, the heuristic function only considers Euclidean distance or simple obstacle distance, the real influence of terrain factors such as gradient resistance, rolling resistance and the like on the vehicle passing cannot be effectively quantized, the planned path is shortest in geometry but not feasible physically, thirdly, the algorithm is output as a broken line path, a large number of sharp turning points exist, and the algorithm is required to be smoothed by post-processing (such as Bezier curve fitting). The existing post-treatment method carries out the geometric continuity and kinematic constraint fracture treatment, and when the smooth path does not meet the minimum turning radius or the safety constraint of the terrain, the geometric continuity and the kinematic constraint fracture treatment need to be repeatedly corrected and even re-planned, so that the overall efficiency is low. Aiming at the problems, the prior research provides two improvement directions, namely, one type introduces the attitude cost of terrain gradient, roll angle and the like into a cost function of A, improves the terrain traffic capacity of a path but does not solve the problem of searching efficiency, and the other type adopts a mixed A algorithm to embed kinematic constraint, and the vehicle dynamics characteristic is considered, but the calculation complexity is too high, so that the large-scale cross-country global planning is difficult to support. The existing scheme can not realize the collaborative optimization of high search efficiency, terrain adaptability and kinematic constraint at the same time, so that the technical bottleneck of low efficiency and poor feasibility still exists in path planning in an off-road environment. Disclosure of Invention The embodiment of the invention aims to provide a global path planning method for an off-road intelligent vehicle based on bidirectional alternate search A, and aims to solve the problems in the background art. The embodiment of the invention is realized in such a way that the global path planning method of the off-road intelligent vehicle based on the bidirectional alternate search A comprises the following steps: Step 1, building a global grid map, wherein the grid map comprises elevation information, and calculating the gradient and rolling resistance coefficient of each grid based on the elevation information; step 2, calculating the potential field of the rugged terrain based on the gradient and the rolling resistance coefficient, and determining the actual cost from the starting point to the current node in the A-algorithm And heuristic functions from the current node to the target node; Step 3, adopting a Bidirectional Alternate Search (BAS) strategy to search paths from the starting pointStart the forward search from the end pointStarting reverse search, and exchanging information of the current optimal boundary nodes of the two parties in real time in the forward search and reverse search processes so as to mutually guide the search direction of the other party; Step 4, when the forward search node and the backward search node meet, path splicing is carried out to generate a path from the starting point To the end pointIs a broken line path of the original; step 5, filtering key nodes of the original broken line path, removing redundant nodes, and generating a sparse broken line path formed by the key nodes; And 6, carrying out path smoothing by adopting a Bezier curve based on key nodes in the sparse broken line path, and synchronously applying turning constraint, terrain constraint and conne