Search

CN-116734877-B - Robot dynamic obstacle avoidance method based on improved A-algorithm and dynamic window method

CN116734877BCN 116734877 BCN116734877 BCN 116734877BCN-116734877-B

Abstract

The invention discloses a robot dynamic obstacle avoidance method based on an improved A-algorithm and a dynamic window method, which comprises the following steps of S1, initializing a map and position information of a robot, S2, designing a self-adaptive weight heuristic search function for the A-algorithm, comprehensively considering Manhattan distance and Euclidean distance, using the improved A-algorithm to conduct preliminary global path planning, S3, deleting redundant path nodes by using a redundant point elimination method to conduct path pruning, S4, conducting smooth optimization on a global path by adopting a Minimum Snap, S5, selecting local target points from a smoothed and optimized global path node sequence, and S6, conducting local path planning by using an optimized dynamic window method between the local target points. After the A-algorithm fusion optimization dynamic window method is improved, the robot path can realize random obstacle avoidance and dynamic obstacle avoidance on the premise of being close to a global path.

Inventors

  • HU ZHANGFANG
  • WANG XINGYUAN

Assignees

  • 重庆邮电大学

Dates

Publication Date
20260512
Application Date
20230608

Claims (7)

  1. 1. The robot dynamic obstacle avoidance method based on the improved A-algorithm and the dynamic window method is characterized by comprising the following steps of: Initializing a map and robot position information; The method comprises the steps of performing global path planning by adopting an A-algorithm to generate a path node sequence, introducing an adaptive weight heuristic search function comprehensively considering Manhattan distance and Euclidean distance to guide a search direction for improving the A-algorithm, and improving a cost function of the A-algorithm The method comprises the following steps: Wherein, the Representing the actual cost from the starting node to the current node n, Representing the proportion of the manhattan distance of the current node to the target node in the total distance, And Is the abscissa and ordinate of the starting node, Weights that are heuristic functions; is a heuristic function employing manhattan distance, Is a heuristic function using Euclidean distance; And Is the abscissa and ordinate of the current node, And Is the abscissa and ordinate of the target node; carrying out path pruning on the generated path node sequence to obtain an optimized global path; The global path after path pruning optimization is input into a track optimization module, the Minimum Snap is adopted for smooth optimization, and the track can use an n-order polynomial The representation is: Wherein, the Is the track parameter, time Divided into a plurality of sections, each section is expressed as a polynomial curve: Wherein, the Track segmentation number, constructing a Minimum Snap optimization function as follows: Wherein r, c are the row index and column index of the matrix; is the parameter vector of the ith track; selecting a local target point from the smoothed and optimized global path node sequence; And (3) carrying out local path planning between the obtained local target points by using an optimized dynamic window method until reaching the global target point.
  2. 2. The robot dynamic obstacle avoidance method based on the improved a-algorithm and dynamic window method of claim 1, wherein the step of performing path pruning on the generated path node sequence comprises the following steps: Inputting the path node sequence generated by the A-algorithm into a path pruning module; And deleting redundant path nodes by using a redundant point elimination method, and performing path pruning.
  3. 3. The method for dynamically avoiding obstacle by robot based on improved a-algorithm and dynamic window method according to claim 2, wherein the method for eliminating redundant points comprises the following steps: Creating and initializing a node set ASTARNSET by taking path nodes generated by an A-algorithm as input, wherein the initial value of the ASTARNSET set is , Is the start point of the path and, The target point is the node number of the path generated by the algorithm of which m is A; Creating a key node set KeyNset for storing the optimized path nodes; From the slave Start to connect in turn Judging straight line Whether or not to pass by an obstacle, if so Is a key node and is added to KeyNset sets, otherwise, the judgment is made Is a redundant node, slave Continuing to connect back to the nodes in ASATRNSET set until connected to the target point At this time KeyNset sets contain all key nodes with a value of ; All key nodes in KeyNset sets are connected in turn, so that path pruning is completed.
  4. 4. The method for dynamically avoiding obstacles for a robot based on an improved a-algorithm and a dynamic window method according to claim 1, wherein the method for planning a local path between the obtained local target points by using an optimized dynamic window method until reaching a global target point comprises the following steps: Sampling a speed constraint space through a robot kinematic model; Normalizing each evaluation sub-function, and selecting a track with the optimal score from a plurality of groups of motion tracks according to the score of the evaluation function; updating the robot attitude information at the next moment, and if the updated robot position is a local target point, indicating that the section of local path planning is completed; And continuing to use an optimized dynamic window method to conduct local path planning among the local target points until reaching the global target point.
  5. 5. The method for dynamically avoiding obstacle for robot based on improved A-algorithm and dynamic window method according to claim 4, wherein the method for planning local path between local target points by using optimized dynamic window method until reaching global target point, further comprises combining global path information on the basis of traditional dynamic window method evaluation function to construct global path evaluation sub-function, wherein the improved evaluation function is as follows: Wherein, the An azimuth evaluation function is used for evaluating the angle difference between the tail end orientation of the current predicted track and the target point; And Is an obstacle distance evaluation function, The distance between the end of the current predicted trajectory and the static obstacle is evaluated, Evaluating the distance between the tail end of the current predicted track and the dynamic obstacle; the speed evaluation function is used for evaluating the linear speed of the current robot, so that the robot can reach the target point faster; the method is a global path offset evaluation function and is used for evaluating the distance between the end point of the current predicted track and the global path; Is a smoothing factor which is used to smooth the image, Is the weight of the azimuth evaluation function, Is the static obstacle distance evaluation function weight, Is a dynamic obstacle distance evaluation function, Is the weight of the speed evaluation function, Is a global path offset evaluation function weight.
  6. 6. The method for dynamically avoiding obstacles for a robot based on the modified a-algorithm and the dynamic window method according to claim 1, wherein initializing the map and the robot position information further comprises initializing the modified a-algorithm and optimizing parameters of the dynamic window method.
  7. 7. A computer readable storage medium having stored thereon a computer program, wherein the computer program when executed by a processor implements the steps of the robot dynamic obstacle avoidance method based on the modified a-algorithm and dynamic window method of any of claims 1 to 6.

Description

Robot dynamic obstacle avoidance method based on improved A-algorithm and dynamic window method Technical Field The invention belongs to the field of path planning of mobile robots, and particularly relates to a robot dynamic obstacle avoidance method based on an improved A-based algorithm and a dynamic window method. Background The statements in this section merely provide background information related to the present disclosure and may constitute prior art. In carrying out the present invention, the inventors have found that at least the following problems exist in the prior art. Path planning is a key technology for autonomous robot research, and has important application in the field of mobile robot navigation. The path planning can be divided into global path planning based on priori global information and local path planning based on dynamic local information according to the knowledge of the robot about the map information. The algorithm A is a commonly applied graph searching method for solving the global optimal path in a static environment, combines heuristic search with Dijkstra algorithm, and has the advantages of short planning path, simplicity in calculation and the like. However, the conventional a-algorithm has the disadvantages of high time complexity, low path smoothness, redundant nodes, close distance from the obstacle and the like.The et al propose ACCELERATED A algorithm to improve the search efficiency on the premise of ensuring the optimal path. The algorithm adopts a heuristic distance quick estimation method to reduce the calculation amount of each node, so as to accelerate the path planning process, but does not consider the safety distance between the algorithm and the obstacle. Lin M et al considers the influence of the parent node of the current node on the search path, introduces parent node information into the heuristic function and adjusts the heuristic function weight, thereby reducing the number of search nodes. Min Haitao proposes an improved a-algorithm, which avoids collisions by setting redundant safety spaces and introduces path curvature costs in heuristic function design to improve the smoothness of the path. Cao P et al propose an Any-Angle A algorithm based on a visibility graph, which can search paths at Any Angle, shortens path length and reduces search space. Cheng Chuanji et al propose a key point selection strategy to eliminate redundant nodes and unnecessary turning points. The DWA algorithm (Dynamic Window Approach) performs the robot local path planning in real time by combining the sensor information, and has good dynamic obstacle avoidance capability. Missura M proposes an improved DWA algorithm that significantly reduces the number of collisions compared to conventional DWA algorithms by building a dynamic collision model that takes into account the motion of other objects in the environment and predicts future collisions. Mai Xiquan et al introduce an evaluation sub-function related to the obstacle distribution density into the DWA evaluation function, which enables the robot to have the ability to accelerate in advance, avoiding entering the obstacle-dense area. In summary, the global path planning algorithm cannot detect dynamic obstacles in the environment and cannot avoid the dynamic obstacles. The local path planning algorithm is easy to fall into local optimum, and can not guarantee to obtain a feasible solution. Therefore, the path planning algorithm suitable for the dynamic environment needs to have the capacity of global path planning and dynamic obstacle avoidance. The patent name of application number CN202110842405.X is 'unmanned vehicle real-time global path planning method based on dynamic window of safety A guide point', A algorithm and dynamic window method are combined, the optimal safety virtual target point is quickly found out by using the safety A algorithm, then the virtual target point is used as a local target of the dynamic window method, and speed sampling is carried out, so that path planning and obstacle avoidance are realized. However, the applicant has found that the method still has some defects. First, the heuristic function of the algorithm a selects the euclidean distance, and the searching efficiency is low. Secondly, for safety consideration, the method achieves safety by avoiding passing through the top points of the obstacles when the algorithm A initially plans the paths, and considering the straight line distance between the paths and the obstacles when the redundant points are removed. Although security is achieved, the final path planning is far from the optimal path, and the optimal solution cannot be achieved. Meanwhile, the path length cannot be effectively reduced because only redundant points on the same straight line are removed and safety-based node selection is performed. Finally, the patent does not consider the case of dynamic obstacles, but can only be implemented in environments where static and ra