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
- 공유라이브러리
- 선형대수
- C
- 강화학습
- MDP
- 소프티어
- 정적라이브러리
- 수치최적화
- CPP
- GNN
- 경로생성
- Hybrid A star
- OSQP
- 동적라이브러리
- Frenet Coordinate
- self driving car
- Graph Neural Network
- Recursion
- GIT
- autonomous vehicle
- CUDA
- PathPlanning
- Motion Planning
- C++
- solver
- path planning
- 백준
- DynamicProgramming
- Dubins Path
- Leetcode
Archives
- Today
- Total
Swimmer
Dubins Path 본문
알고리즘 설명
- Dubins Path는 시작지점 및 헤딩, 종료지점 및 헤딩이 주어졌을 때 회전 반경이 일정한 원과 직선으로 연결하는 경로이다. 경로 내 원, 직선의 Segment 구성 및 회전 순서에 따라 총 6가지의 경로가 존재한다.
- 시계 방향의 원호를 L, 반시계 방햐의 원호를 R, 직선을 S라고 할때 LSL, LSR, RSL, RSR, LRL, RLR 총 6가지의 케이스가 존재한다.
- 원호를 C, 직선을 S라고 하면 CCC, CSC 두가지의 케이스의 경로를 생성할 수 있다. 이때 CCC는 두 점의 거리와 회전반경에 따라 경로가 존재하지 않을 수 있다.
- Dubins Path는 아래 논문에서 제안되었다.
- Dubins, L. E. (July 1957). "On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents". American Journal of Mathematics. 79 (3): 497–516.
알고리즘 특징
- 경로 생성 방법
- 시작 지점에서 자차 기준 좌/우 원을 그리고 종료 지점에서 자차 기준 좌/우 원을 그린 후, 각 원 간 Tangent Point를 찾아 경로를 생성한다.
- LSL, RSR / RSL, LSR, / LRL, RLR 3가지 케이스로 경로 계산 방법이 나뉜다.
- 기타
- 시작 지점과 종료 지점의 원의 반지름을 다르게 설정해도 경로 생성 가능하다.
- 차량은 전진만 가능하다고 가정한다.
- 후진까지 고려한 경로 생성 알고리즘이 Reed and Shepp Curve이다.
- Reeds, James, and Lawrence Shepp. "Optimal paths for a car that goes both forwards and backwards." Pacific journal of mathematics 145.2 (1990): 367-393.
- 결국 두 원에 접하는 Tangent Point (Tangent Lint, Tangent Circle)을 구하는 것이 핵심이자 목표이다. 이는 기하학과 삼각 함수를 사용해 계산가능하나 벡터를 사용하면 더 빠른 연산이 가능하다.
알고리즘 구현 결과
'개념공부 > Path planning' 카테고리의 다른 글
Frenet coordinate (0) | 2023.05.07 |
---|---|
Hybrid A star 경로 계획 알고리즘 설명 (0) | 2023.05.01 |
Clothoid (0) | 2022.11.02 |
A* (A star 경로 계획 알고리즘) (0) | 2022.10.31 |
Review of Motion Planning (0) | 2021.07.11 |
Comments