본문 바로가기

개념공부/Path planning9

Frenet coordinate Frenet Coordinate (Frenet Frame, S-N coordinate) S-N 좌표계 라고도 한다. Reference Path(기준 방향)의 Arc Length 방향 및 이의 수직 방향을 축으로 위치 공간을 표현하는 좌표계이다. 추종 경로가 있을 때, 이를 기반으로 위치 상태 값을 표시할 수 있다. Reference Path의 Unit Length 별로 상태 값을 표시하여 계산해야 할 상태 값을 줄일 수 있는 것이 장점이다. ex) Cartesian Coordinate : x, y, theta (heading) / Fresent coordinate : ds, dy, dtheta (ds는 unit length이므로 변수가 아님) 최적화 / Gradient Descent 시 상태 값을 줄여 .. 2023. 5. 7.
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 .. 2023. 5. 1.
Hybrid A star 경로 계획 알고리즘 설명 알고리즘 설명 Hybrid A star 은 시작지점에서 목적지점까지 충돌 없이 Kinematic Feasible한 Sub Optimal Path를 생성할 수 있는 알고리즘이다. Hybrid A star 경로 계획 알고리즘은 아래 논문에서 제안된 방법이다. Dolgov, Dmitri, et al. "Practical search techniques in path planning for autonomous driving." Ann Arbor 1001.48105 (2008): 18-80. 기존 A star 경로 계획 알고리즘 대비 2가지가 개선되었다. Kinematic Feasible 경로 생성 가능 H cost 사용하여 Search 횟수 절감 (Non-holonomic without obstacle Cost.. 2023. 5. 1.
Clothoid 특징길이가 증가함에 따라 곡률이 선형으로 증가하는 곡선곡률이 선형으로 증가하는 특징이 있어, 곡률이 다른 두 선을 연결하는 중간 선으로 사용된다. 대표적으로 직선과 원을 연결하는 선으로 사용된다. (ex/ 고속도로 직선 구간과 곡선구간을 연결할 때 클로소이드를 사용한다.) 원리Clothoid는 Frenal Integral로 정의된다. 상기 수식에서 a는 클로소이드의 형상을 조절하는 파라미터이다. 2RL = 1 / (a^2) 의 수식이 성립한다. 즉, 클로소이드의 길이가 L이면서, 곡률 반경이 R로 끝나는 클로소이드 형상을 파라미터 a의 값으로 결정할 수 있다. 이때 클로소이드는 곡률 반경이 무한대인 직선에서 시작한다. 자율주행차량의 경로 생성 적용 시G2 연속 (Curvature 연속) 경로 생성을 위해.. 2022. 11. 2.
A* (A star 경로 계획 알고리즘) 알고리즘 설명 특정 지역을 그리드 맵으로 표현하여 그리드 별 비용을 계산하여 시작점부터 목적지까지 경로를 계획하는 알고리즘이다. 특징 그리드 별 비용을 어떻게 설정하느냐에 따라 다른 경로가 계획될 수 있다. 보통 비용은 G cost : 시작 그리드 ~ 현재 그리드, H(heuristic) cost : 장애물, 현재 그리드 ~ 목적 그리드 거리로 계산한다. G cost는 부모 그리드의 G cost + 부모 -> 자식 그리드로 이동하는데 발생한 비용으로 계산한다. H cost 중 현재 그리드 ~ 목적 그리드의 거리 비용의 경우, 목적지점에서 BFS를 통해 계산할 수 있다. 원리 특정 지역 그리드맵 생성 현재 그리드에서 주변 그리드 탐색 주변 그리드 중 장애물과 충돌하지 않는 그리드들을 Cost 계산 후 (G.. 2022. 10. 31.
Review of Motion Planning Path Planning 알고리즘을 개발 원리 및 시기에 따라 Traditional Algorithm과 ML-based Algorithm으로 분류한다. Tradition Algorithm은 Graph Based method, Sampling based method, Curve Interpolation으로 구분한다. ML-based Algorithm 은 Supervised Learning, Optimal Value Reinforcement Learning, Policy Gradient Reinforcement Learning. Graph Search Based Algorithm 1. Dijsktra's Algorithm 2. A* Algorithm Hybrid A*, Field D*, Anytime A*,.. 2021. 7. 11.

티스토리툴바