Abstract:
The traditional Dijkstra algorithm and A* algorithm have problems of too many expanded nodes and low path search efficiency. Therefore, an improved bounded suboptimal bidirectional search A* algorithm is proposed. Bidirectional search was proposed. While one point searches from start point to end point within the search area, another point searches from end point to start point, reducing the number of expanded nodes. The heuristic function of traditional A* was improved, Manhattan distance was selected for calculation and dynamic h value improvement was proposed to reduce path planning time. Bounded suboptimality was proposed, nodes within a certain range of f values were placed in focalList, and the node with the smallest h value was taken as the next expanded node to improve the purposefulness of algorithm search. Simulation verification was carried out, and the improved A* algorithm reduced the number of expanded nodes by 66.43%, 71.14%, 78.27% respectively, and the planning time was reduced by 95.63%, 96.30%, 97.65% respectively. The results show that the improved A* algorithm significantly reduces the number of expanded nodes and required time, and improves path planning efficiency.