Dubins Path Algorithm

Dubins Path 알고리즘은 로봇이나 차량과 같은 이동체가 제한된 반경 내에서 움직일 때 최적의 경로를 계획하는 알고리즘
이동체의 회전 반경과 가능한 직진 거리의 제약 조건을 고려해 경로를 생성한다
로봇이 갈 수 있는 경로를 미리 계산(offline)
미리 계산된 경로를 이용하여 경로 planning(online)

Dubins Path 장점

• 최소한의 회전을 사용해 경로를 계획한다. 회전 능력을 최대한 활용해서 목표 지점에 빠르게 도착
• 간단한 수학 모델을 사용하기 때문에 구현이 어렵지 않다
• 회전 반경과 직진 거리 제약 조건을 고려해 실제 환경의 이동체의 제약을 잘 반영
• 미리 계산된 경로로 탐색을 하기 때문에 연산 속도가 매우 빠름

단점

• 높은 속도로 이동하거나 복잡한 환경에서 적합하지 않음
• 경로 길이가 너무 긴 경우 정확도가 떨어질 수 있음
• 모든 경우를 미리 계산해놓을 수 없기 때문에 완벽한 최단 루트를 구하기 어려움

Motion primitives

• Dubins Path 에선 Motion primitives를 사용
• 간단한 움직임 패턴이나 동작을 나타내며 정해진 패턴을 합쳐서 복잡한 루트를 생성한다
• 직진, 좌회전, 우회전과 같은 기본 움직임을 Motion primitives로 사용해서 주차하거나 자율주행에 사용하도록 경로를 생성하고 제어할 수 있다

Vehicle model

• State : x, y, θ
• Input : curvature u(steering)

x' = cosθ
y' = sinθ
θ' = u
(') = d/dX

Six words

{LRL, RLR, LSL, LSR, RSL, RSR}

위처럼 6가지 루트가 존재하는데
1. 각 시작 점을 기준으로 원을 그림
2. 벡터에서 왼쪽에 원이 존재하면 L, 오른쪽이면 R
3. 왼쪽, 오른쪽으로 돌고 직진하면 S 오른쪽으로 가거나 왼쪽으로 가면 R, L
4. 이동한 방향에 맞게 LRL, RLR, LSL, LSR, RSL, RSR 중 정함
5. 각 θ값은 초록색처럼 정함

기본 구현

class DubinsPath(object):
    def __init__(self, t=0, p=1e10, q=0, type=None):
        self.t = t
        self.p = p
        self.q = q
        self.length_ = [t, p, q]
        self.type = type
        self.controls = None

    def length(self):
        return self.t + self.p + self.q

LSL

RSR

RSL

LSR

RLR

LRL