 |
A * search is an optimal path search algorithm using Grid Map. According to the form f(n)= g(n)+ h(n), A* search will operate on 8 neighbors of the center at each step where f(n) is the evaluation function, g(n) is the cost of moving from the starting point to the specified point. H(n) is the estimated distance from the current node to the endpoint, which is an estimate of the remaining distance, not the actual value. It is an ideal value that ignores the effect of obstacles. In order to estimate h(n), there are three kinds of distance metrics can be used in path planning which are Euclidean Distance, Manhattan Distance, Chebyshev Distance.
In our scenario, we choose Manhattan Distance to metric the distance between two points, which can be formulated by this formula. The Manhattan Distance can be used to measure the distance of a point that can be reached in four directions to another point.
This Figure shows the results of path planning using A* while the green square is the start point, the red square is the end point and the blue point is the obstacles. Also, the green border squares are points in the open list, yellow border squares are points in the close list, the yellow arrow in the square points to the father node, and the number in the upper left corner of the square represents the F value, the G value in the lower left corner, and the H value in the lower right corner.
|
IEEE/ICACT20230128 Slide.08
[Big Slide]
[YouTube]