A* 알고리즘 기초
경로생성 대표 알고리즘 (A* 알고리즘)
완전 자율 주행 시대를 위한 자율 주행 구현을 위해서는 실시간 가능한 섬세한 경로생성 기술이 필요
Q) A* 알고리즘의 개념과 원리는?
학습 내용)
1.
A* 알고리즘 개념
2.
A* 알고리즘 Grid
keyword 1)
A* 알고리즘 개요
→ 주어진 목표 꼭짓점까지 가는 최단경로임을 판단할 수 있는 테스트를 통과하는 그래프/트리 탐색 알고리즘
keyword 2)
A* 알고리즘 원리
→ 현실 세계를 격자로 표현하여 비용함수가 최소가 되는 최적 경로를 찾는 기술
keyword 3)
경로생성을 위한 A* 알고리즘
→ 자율 주행 경로생성을 위하여 A* 알고리즘 활용 가능
A* 알고리즘 개념
자율 주행차 경로생성 기술의 대표 알고리즘
→ 주어진 목표 꼭짓점까지 가는 최단경로임을 판단할 수 있는 테스트를 통과하는 그래프/트리 탐색 알고리즘 중 하나
→ 부모 자식 노드 간의 관계 → 최단 경로 선택에 활용
⇒ 빠른 경로 탐색 가능
A* 알고리즘 Grid
Grid 크기에 따른 성능 영향
A* 알고리즘은 격자 지도에서 장애물들을 고려하여 출발점부터 목표점까지 8방향에 대한 cost를 계산해서 최적 경로를 찾는 알고리즘
→ 서로 10배 차이
그리드를 25칸으로 나눈 경우
장점
•
격자 숫자가 훨씬 적기 때문에 계산 속도가 빠름
단점
•
격자 단위가 크기 때문에 섬세한 경로생성을 못함
그리드를 2500칸으로 나눈 경우
장점
•
격자 단위가 작기 때문에 섬세한 경로생성 결과 도출 가능
단점
•
탐색해야 할 격자의 개수가 많기 때문에 계산량이 많아짐
포인트)
1.
Grid Map(격자지도) 상에서 8방향의 방향성에 대해 장애물을 고려하여 Cost를 계산
•
Cost 최소화를 통해 최적의 경로를 찾아내는 알고리즘
2.
Grid의 크기를 어떻게 설정하는가?
•
결과값으로 제시할 수 있는 경로의 섬세함, 계산량이 달라짐
⇒ 주어진 환경정보와 자차의 크기에 땨라서 그리드의 크기를 적합하게 설정하는 것이 중요!
