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.

알고리즘 특징

1. 경로 생성 방법
   1. 시작 지점에서 자차 기준 좌/우 원을 그리고 종료 지점에서 자차 기준 좌/우 원을 그린 후, 각 원 간 Tangent Point를 찾아 경로를 생성한다. 
   2. LSL, RSR / RSL, LSR, / LRL, RLR 3가지 케이스로 경로 계산 방법이 나뉜다.
2. 기타
   1. 시작 지점과 종료 지점의 원의 반지름을 다르게 설정해도 경로 생성 가능하다.
   2. 차량은 전진만 가능하다고 가정한다.
      1. 후진까지 고려한 경로 생성 알고리즘이 Reed and Shepp Curve이다.
      2. 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.
   3. 결국 두 원에 접하는 Tangent Point (Tangent Lint, Tangent Circle)을 구하는 것이 핵심이자 목표이다. 이는 기하학과 삼각 함수를 사용해 계산가능하나 벡터를 사용하면 더 빠른 연산이 가능하다.

알고리즘 구현 결과