본문 바로가기
개념공부/Path planning

A* (A star 경로 계획 알고리즘)

by Zach Choi 2022. 10. 31.
728x90
반응형
  • 알고리즘 설명

특정 지역을 그리드 맵으로 표현하여 그리드 별 비용을 계산하여 시작점부터 목적지까지 경로를 계획하는 알고리즘이다.

 

  •  특징

그리드 별 비용을 어떻게 설정하느냐에 따라 다른 경로가 계획될 수 있다.

보통 비용은 G cost : 시작 그리드  ~ 현재 그리드, H(heuristic) cost : 장애물, 현재 그리드 ~ 목적 그리드 거리로 계산한다.

G cost는 부모 그리드의 G cost + 부모 -> 자식 그리드로 이동하는데 발생한 비용으로 계산한다.

H cost 중 현재 그리드 ~ 목적 그리드의 거리 비용의 경우, 목적지점에서 BFS를 통해 계산할 수 있다.

 

  • 원리
    1. 특정 지역 그리드맵 생성
    2. 현재 그리드에서 주변 그리드 탐색
    3. 주변 그리드 중 장애물과 충돌하지 않는 그리드들을 Cost 계산 후 (G cost + H cost) 버퍼에 저장
    4. Stack에 저장되어 있는 그리드을 호출하여 2~3 반복
    5. 탐색 가능한 그리드가 없는 경우, 3~4 반복
    6. 목표 그리드에 도달한 경우, 알고리즘 종료
    7. 목표 그리드에 도달하지 못했는데, Stack에 버퍼 없는 경우 알고리즘 종료

 

  • 참고 논문
    • A Formal Basis for the Heuristic Determination of Minimum Cost Paths
728x90
반응형

'개념공부 > Path planning' 카테고리의 다른 글

Hybrid A star 경로 계획 알고리즘 설명  (0) 2023.05.01
Clothoid  (0) 2022.11.02
Review of Motion Planning  (0) 2021.07.11
Corridor Map Method(CMM) Path Planning  (0) 2021.04.08
Hermite Spline <설명, Matlab Code>  (0) 2020.10.11