Path finding method based on A star optimization algorithm

Abstract

The invention provides a path finding method based on an A star optimization algorithm. The method comprises the steps of: giving a grid chart of a map, determining the position coordinates of a corresponding obstacle point, and determining the coordinates of a starting point and a target point, constructing a linear function between the starting point and the target point, solving a key point where a straight line intersects with the grid, then solving related adjacent nodes, and judging whether nodes coinciding with the obstacle point exist in the nodes or not, if the node does not coincidewith the obstacle node, enabling the searched optimal path to be a straight line between the starting point and the target point of the automobile, if an obstacle point is encountered, internally calling an A star algorithm, and putting non-obstacle nodes around the point into an open list, judging whether the open list is empty or not, taking a point with the smallest f value out from the open list to serve as the next step of path finding, judging whether the point is a target point or not, and if so, determining that path finding succeeds and ending the algorithm, or otherwise, continuing path finding, setting the point as the current point, and continuing the path finding process. According to the method, the algorithm is optimized by preprocessing the obstacle, so that the node searchtime is shortened, and the calculation memory is reduced.

Description

technical field [0001] The invention relates to the technical field of unmanned vehicles, in particular to a pathfinding method based on an A-star optimization algorithm. Background technique [0002] A driverless car is a smart car that senses the road environment through an on-board sensor system, automatically plans a driving route, and controls the vehicle to reach a predetermined target. Unmanned vehicles integrate many technologies such as automatic control, architecture, artificial intelligence and visual computing. They are the product of highly developed computer science, pattern recognition and intelligent control technologies, and are also an important indicator of a country's scientific research strength and industrial level. , has broad application prospects in national defense and national economy. [0003] Among them, pathfinding is one of the basic problems of unmanned vehicles, that is, the vehicle arrives from point A on the map to point B according to the...

AI Technical Summary

Problems solved by technology

[0006] A pathfinding method based on the A-star optimization algorithm provided by the present invention solves the problem that the traditional heuristic A-star search algorithm will search for many useless nodes in the face of obstacles, resulting in increased search time and calculation memory. Driving the car can smoothly avoid obstacles, reducing the time and computing memory used for searching

Images