Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
Tags
- Frenet Coordinate
- 소프티어
- path planning
- GNN
- CPP
- Leetcode
- self driving car
- CUDA
- Motion Planning
- Recursion
- Hybrid A star
- autonomous vehicle
- 선형대수
- DynamicProgramming
- GIT
- 백준
- 강화학습
- 수치최적화
- Dubins Path
- 동적라이브러리
- C
- MDP
- 공유라이브러리
- solver
- OSQP
- 경로생성
- C++
- Graph Neural Network
- 정적라이브러리
- PathPlanning
Archives
- Today
- Total
Swimmer
A* (A star 경로 계획 알고리즘) 본문
- 알고리즘 설명
특정 지역을 그리드 맵으로 표현하여 그리드 별 비용을 계산하여 시작점부터 목적지까지 경로를 계획하는 알고리즘이다.
- 특징
그리드 별 비용을 어떻게 설정하느냐에 따라 다른 경로가 계획될 수 있다.
보통 비용은 G cost : 시작 그리드 ~ 현재 그리드, H(heuristic) cost : 장애물, 현재 그리드 ~ 목적 그리드 거리로 계산한다.
G cost는 부모 그리드의 G cost + 부모 -> 자식 그리드로 이동하는데 발생한 비용으로 계산한다.
H cost 중 현재 그리드 ~ 목적 그리드의 거리 비용의 경우, 목적지점에서 BFS를 통해 계산할 수 있다.
- 원리
- 특정 지역 그리드맵 생성
- 현재 그리드에서 주변 그리드 탐색
- 주변 그리드 중 장애물과 충돌하지 않는 그리드들을 Cost 계산 후 (G cost + H cost) 버퍼에 저장
- Stack에 저장되어 있는 그리드을 호출하여 2~3 반복
- 탐색 가능한 그리드가 없는 경우, 3~4 반복
- 목표 그리드에 도달한 경우, 알고리즘 종료
- 목표 그리드에 도달하지 못했는데, Stack에 버퍼 없는 경우 알고리즘 종료
- 참고 논문
- A Formal Basis for the Heuristic Determination of Minimum Cost Paths
'개념공부 > 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 |
Comments