A* 알고리즘 이해
주차사고의 비율?
→ 30% 수준 (비율이 높은 편)
→ 자율 주행 기반 자동 주차 기술이 필요
•
섬세한 경로생성 기술이 꼭 필요
Q) A* 알고리즘을 어떻게 구현하고 적용?
학습 내용)
1.
시작 단계 설정
2.
탐색 시작 단계와 경로 채점
keyword 1)
A* 알고리즘 원리 이해
→ 격자 지도 상에서 최소 비용 함수를 선택하는 A* 알고리즘의 원리 이해
keyword 2)
A* 알고리즘 단계별 원리
→ A* 알고리즘의 원리를 시작/탐색/경로 채점 단계 관점에서 원리 이해
keyword 3)
A* 알고리즘 이해
→ 단계별 설명을 통한 A* 알고리즘 적용 및 구현 가능 수준의 이해
시작 단계 설정
A* 알고리즘 예시)
최단 경로 찾기
각 노드마다 부모 자식 노드의 관계를 맺으며 진행
탐색 시작 단계와 경로 채점
F = 현재까지 이동하는 데이 걸린 비용과 예상 비용을 합친 총 비용
G = 시작점으로부터 현재 사각형까지의 경로를 따라 이동하는 데이 소요되는 비용
H = 현재 사각형에서 목적지까지의 예상 이동 비용
예상 이동 : 시작점과 목적지 사이 장애물 등은 무시하고 예상 거리 산출
맨해튼 방법 : 대각선 이동을 생각하지 않고 가로 또는 세로로 이동하는 비용만 계산
1.
먼저 시작지점에서 8방향의 총 비용 점수인 F Score 계산
•
격자 사이의 거리를 10이라 가정
•
시작 지점인 녹색 격자로부터 8방향 격자들로의 거리 파악 가능 = G
•
H는 도착점 격자까지의 거리
F = G + H
→ 최소 비용 F를 확보하는 방향으로 검색의 범위를 계속적으로 넓혀가며 탐색
→ 목적 지점이 탐색 범위 안에 들어온다면?
→ 목표 지점에서 거꾸로 시작점으로 부모 노드를 찾아가서 최종 경로를 선택
→ 부모 자식 노드는 최종 경로 선택 시 필요하므로, 탐색 시 계속적으로 업데이트가 되야 한다
포인트)
1.
A* 알고리즘은 경로생성 대표 알고리즘
2.
시작점에서 도착점까지 8방향에 대한 cost를 계속적으로 확장하여 계산
•
최종적으로 최소의 Cost를 보장하는 최단경로를 선택하게 해주는 알고리즘
3.
Grid 단위 개념과 Cost에 관한 이해만 동반된다면 어렵지 않게 Application에 적용해볼 수 있다
4.
A* 알고리즘 관련된 다양한 관점에서의 개선 알고리즘들도 많은 연구가 진행되었고, 진행 중임
