A* 알고리즘 (A스타, 예전자료)

 

네이버 블로그에 있는 글들을 하나씩 옮기고 있다. (2008.12월 작성)

대학원에서 로봇동작계획이란 강의를 들을때 숙제했던 내용인데 사실 지금은 기억 나지 않는다.

이런게 있었다 정도...최적경로, 길찾기 알고리즘인데 세월이 지난만큼 더 좋은 알고리즘도 많아졌을것이다.

---

 

1. A* 알고리즘이란?

 

A* 알고리즘은 초기노드(시작지점)에서 목표 노드(목표지점)까지의 경로를 찾는 그래프 탐색 알고리즘이다. 다른 그래프 탐색 알고리즘과 다른 점은 목표에 얼마나 근접한 것인지를 평가하는데 휴리스틱 함수를 사용한다는 것이다.

 

 

2. 알고리즘 순서

 

(1) 시작지점을 열린목록(Openlist)에 넣는다.

(2) 열린목록에 있는 노드 중 1개를 빼서 여덟 방향 주변노드를 탐색한다.
( 평가함수 F= G+H 를 계산 & 부모노드를 명시, 장애물과 닫힌목록은 제외한다.)
F= G+H 설명
G : 시작노드N0에서 현재노드N까지의 최단경로의 값. (수직,수평 +1, 대각선일 경우 +1.41)
H : 현재노드N에서 목표노드까지의 (조건없는)최단경로의 값. (휴리스틱요소)
F :  시작노드N0에서 목표노드까지 현재노드N을 통해 갈 수 있는 모든 가능한 경로 중  최단경로의 값이 된다.

(3) 2단계에서 뺀 노드를 닫힌목록(Closelist)에 삽입한다

(4) 2단계에서 탐색한 노드들을 열린 목록(우선순위 queue)에 삽입한다
(우선순위 큐는 가장 작은 값부터 순서대로 자동정렬되는 특성을 가지기 때문에 가장 낮은 F비용을 가진 노드를 찾을 수 있다.)

(5) 열린 목록 중 가장 앞 노드를 빼고 그 노드를 닫힌 목록에 추가한다.

(6) 5단계에서 뺀 노드의 여덟방향 주요 노드를 탐색한다.
(장애물과 닫힌목록제외, 목표노드가 있는지 조사)
(끝내는 경우: 1. 만일 목표노드가 있다면 부모노드를 추적하여 역순으로 스택에 삽입 2. 열린목록이 비어있게 될 경우 목표노드를 찾는데 실패한 것, 길이 없음.)

(7) 열린목록에 존재하지 않는 노드는 열린목록에 추가하고
중복되는 노드는 G값을 서로비교하여 더 작은 값을 열린 목록으로 교체한다.

(8) 5단계부터 반복

 

 

3. 구현코드

 

3.1 클래스화

C++을 사용하여 A*알고리즘을 클래스화 하였다. class TaskAstarPath

위의 2번에 설명된 처리순서는 TaskAstarPath의 FindShotestPath()메서드에 구현되었다.

 

3.2 클래스의 사용

(1) TaskGridMap의 CreateMap()을 사용하여 맵을 생성한다.  

(2) 맵의 데이터를 입력한다. (즉, 맵상의 각각의 셀에 255를 부여하면 장애물로 인식한다.)

(3) 시작점과 목표점을 설정하며 이 두점을 인자로 넣고 TaskAstarPath의 FindShortestPath()를 사용하면 최단경로 계산이 시작한다.
(4) 계산이 끝나면 TaskAstarPath클래스의 인스턴스는 최단 경로를 저장하고 있으므로 GetPath()에 큐 인스턴스의 포인터를 넘겨주어 경로 데이터를 받아온다.
(5) 큐 인스턴스의 pop() 메서드를 통해 경로를 하나씩 꺼내올 수 있으며 이러한 경로데이터를 텍스트나 그래픽모드로 출력할 수 있다.

 

 

4. 실행 예시 (동영상 및 사진)

 

A* 알고리즘

 

맵의 크기변경(40*40) 및 방문노드의 표시

 

 

 

5. A*의 단점

 

 

맵의 크기가 커지면 ‘열린’ 목록이나 ‘닫힌’ 목록에 수백에서 수천 개의 노드들이 들어갈 수 있기 때문에 시스템의 메모리를 전부 잡아먹을 수도 있으며, 상당히 많은 CPU 시간을 잡아먹을 수도 있다. 또한 위의 그림에서 볼 수 있듯이 시작 위치에서 목표까지의 경로가 존재하지 않으면 A*는 시작위치에서 도달 할 수 있는 모든 위치를 검색하므로 매우 비효율적이다.

 

마침.