두빈스 경로

점 사이 거리와 다른 문제

시작과 목표에는 위치뿐 아니라 차량 방향도 포함한다. 가장 가까운 두 점을 직선으로 이으면 출발 방향이나 도착 방향을 맞추지 못할 수 있다. 회전 반지름이 ρ 이상이어야 한다는 조건은 |κ|≤1/ρ라는 곡률 제한이다. 경로 길이를 최소화하며 속도가 일정한 모델에서는 이동 시간 최소화와도 대응한다.

여섯 가지 후보 형태

최소 반지름 좌회전 원호를 L, 우회전을 R, 직선을 S로 쓰면 최단 후보는 LSL, LSR, RSL, RSR, LRL, RLR의 여섯 형태로 정리된다. 길이가 0인 조각이 포함되는 퇴화 경우도 있다. 각 형태의 기하학적 실행 가능성과 조각 길이를 계산한 뒤 가능한 후보 중 가장 짧은 것을 선택한다. 기호만으로 특정 목표의 답이 결정되지는 않는다.

직선 이동의 하한 예제

시작 배치가 (0,0,0), 목표가 (5,0,0)이고 방향각 0이 x축 양의 방향이라면 길이 5의 직선이 가능하다. 두 점의 유클리드 거리가 5이므로 이보다 짧은 경로는 없다. 반면 목표 위치가 같아도 방향이 π이면 그 직선은 도착 방향을 만족하지 않는다. 위치 거리만으로 같은 최적 비용을 주면 방향 조건을 놓친다.

실차에 적용할 때

이상적인 최단 경로는 원호와 직선이 만나는 곳에서 곡률이 갑자기 바뀔 수 있다. 실제 조향 속도 제한을 만족하려면 곡률 변화까지 고려해 추가 조정해야 한다. 또한 이 해는 장애물이 없는 모델의 결과다. 장애물이 있으면 후보 구간의 충돌 검사와 전역 계획이 필요하며, 길이 최적성을 실제 시간·승차감 최적성으로 그대로 옮기지 않는다.