A*(A star) Algorithm

주어진 출발점에서 목표 지점까지 가는 최단 경로를 나타내는 graph search algorithm이다.

에이스타(A*; A-star) 알고리즘은 경로 탐색 및 길 찾기 문제를 해결하기 위한 효율적인 알고리즘 중 하나로 특히 그래프 기반의 환경에서 시작점과 목적지 간의 최적 경로를 찾는 데 사용된다. 에이스타 알고리즘은 다익스트라(Djikstra) 알고리즘의 변형으로, 휴리스틱(Heuristic) 함수를 사용하여 탐색을 가속화하고 최적 경로를 빠르게 찾을 수 있다.

 

아래의 식으로 단순하게 cost를 구해 경로를 생성한다.

cost = actual_cost + heuristic_cost

heuristic_cost : 현재 노드에서 목적지까지의 추정 거리

 

각 지점에서 목표 지점까지의 거리에 대해, 정확하지는 않지만 어떠한 힌트가 있는 경우에 유용하다는 코멘트가 있다. 대략 정적으로 크게 변동성 없는 환경에서 map 정보를 전부 가지고 있다면 적은 메모리로 간단하게 구현해 사용할 수 있다는 평가가 많지만, 그에 따라 Local Planner의 역할이 보다 중요해진다. Obstacle Avoidance가 적용되지 않기에 local planner가 제대로 돌지 않으면 바로 추돌할거다...

이미지는 랜덤 생성한 맵 상에서 경로를 찾아가는 것을 시각화한 것이다.

다익스트라와 달리 전체를 탐색하지 않고 cost가 가장 작은 범위에서만 탐색을 해 연산량이 확연히 적어짐을 알 수 있다.