리즈 셰프 경로

후진이 더하는 선택지

차량의 위치와 방향을 상태로 두고 전진 또는 후진을 선택한다. 조향으로 정해지는 곡률에는 제한이 있지만 진행 방향을 바꿀 수 있다. 길이는 뒤로 간 구간도 양수로 합산한다. 전진 거리에서 후진 거리를 빼는 순이동량을 최소화하는 문제가 아니다. 같은 방향으로 돌아왔더라도 실제 주행한 전체 길이를 계산한다.

바로 뒤의 목표 예제

시작이 (0,0,0), 목표가 (−2,0,0)이라면 직선 후진으로 길이 2에 도달할 수 있다. 두 위치의 직선 거리가 2이므로 이 경로가 최단이다. 목표를 향해 뒤로 움직여도 차체 방향은 그대로 0이다. 전진만 가능한 차량에서는 이 후진 경로를 사용할 수 없어 다른 회전 조합이 필요하다.

경로 조각과 방향 전환

최적 경로는 전진·후진 직선과 좌우 원호를 조합해 표현할 수 있으며 최대 다섯 개의 운동 조각이 필요한 형태가 있다. 진행 방향이 바뀌는 지점은 경로의 중요한 경계다. 기하학적 길이 문제에서는 변속 지연을 직접 비용에 넣지 않으므로, 같은 길이의 후보라도 전후진 전환 횟수에 대한 실제 선호는 다를 수 있다.

길이와 실행 비용의 차이

후진을 허용한 가능 경로 집합에는 전진만의 경로도 포함되므로 같은 조건의 최단 길이는 두빈스 최단 길이보다 커질 수 없다. 그러나 후진 속도가 느리거나 변속 시간이 길면 더 짧은 길이가 더 짧은 실행 시간을 뜻하지는 않는다. 실제 주차나 로봇 계획에서는 장애물·가속도·조향 변화율과 방향 전환 비용을 함께 확인한다.