Efficient path planning method based on improved A* algorithm

Abstract

The invention requests to protect an efficient path planning method based on an improved A * algorithm. The method is an improved A * algorithm for quickly obtaining an optimal or suboptimal path in a large-area map environment. Firstly, compared with a 8-neighborhood search mode of a traditional A * algorithm, a 4-neighborhood search mode suitable for a large-area grid map is used, and calculation of some unnecessary nodes is greatly reduced. Secondly, a heuristic function is improved, and different weights are given to the estimated cost of the heuristic function, so that the mobile robot can flexibly calculate the estimated cost of the node according to the distance between the mobile robot and the starting point and the distance between the mobile robot and the target point in the planning process. And finally, a simulation test is carried out on the A * algorithm before and after improvement by selecting a plurality of groups of target points with different distances, the used time of each group of planning, the number of access nodes and the smoothness of the path are compared, and the high efficiency of the provided algorithm on path planning is verified.

Description

technical field [0001] The invention belongs to the technical field of mobile robot path planning, and relates to an efficient path planning method based on an improved A* algorithm. Background technique [0002] Path planning is a method of finding a relatively optimal path between two locations in a specific environment. In the process of mobile robot navigation, the path planning algorithm is used to determine the nodes to be traversed, and the current path is gradually determined by calculating the cost value of the nodes until the target point is reached or the search fails. In the actual environment where the distance between the starting point and the target point is far away, as the number of grids increases, the amount of computation increases exponentially, and it is particularly important to efficiently plan a feasible path. [0003] The A* algorithm is a heuristic search algorithm. Divide the entire workplace of a mobile robot into grids, each grid representing...

AI Technical Summary

Problems solved by technology

However, the traditional A* algorithm has certain limitations

The improved A* algorithm proposed by B.Fu et al. in 2018 shortens the real-time planned path by judging whether there is an obstacle between the node on the current path and the target point; however, the calculation of a large number of nodes in the path makes this improvement The efficiency of the A* algorithm is reduced, and the planned path has frequent corners and poor smoothness

Images