[논문 리뷰] Implementation of the Pure Pursuit Path Tracking Algorithm

이건희·2026년 7월 27일

논문 Review

목록 보기

2/18

Implementation of the Pure Pursuit Path Tracking Algorithm
R. Craig Coulter (1992) — CMU-RI-TR-92-01
The Robotics Institute, Carnegie Mellon University

Abstract
본 기술보고서의 주된 목적은 pure pursuit 경로 추종 알고리즘의 구현을 상세히 기술하는 것이다. 지난 몇 년간 이 알고리즘이 거둔 성공을 고려할 때, 향후 지상 기반 내비게이션 문제에도 다시 사용될 가능성이 높다고 판단된다. 본 보고서는 이 방법의 기하학적 유도 과정과, 파라미터의 함수로서 알고리즘의 성능에 대한 몇 가지 통찰도 함께 제시한다.

1. Introduction

Pure Pursuit 알고리즘은 Robotics Institute에서 수년간 사용되어 왔다. Terragator를 시작으로 NavLab, 그리고 이후 NavLab II(HMMWV)에도 적용되었다. Amidi는 이 알고리즘을 다양한 조건에서 구현하고 테스트했으며, 범용 추종 알고리즘으로서 가장 큰 가능성을 보임을 확인했다.
본 논문의 목적은 Pure Pursuit 알고리즘의 구현을 상세히 기술하는 것으로, 해당 방법에 대한 기하학적 유도 과정과 파라미터의 함수로서 알고리즘의 성능에 대한 몇 가지 통찰도 포함된다. 이 기술은 향후 지상 기반 내비게이션 문제에도 사용될 가능성이 높다고 판단된다.
Pure Pursuit 알고리즘은 본래 로봇을 경로로 복귀시키는 데 필요한 호(arc)를 계산하는 방법으로 고안되었다. 이는 차량을 현재 위치로부터 어떤 목표 위치로 이동시키는 곡률(curvature)을 계산하는 방식으로 작동하는 추종 알고리즘이다. 알고리즘의 핵심은 경로상에서 차량으로부터 일정 거리만큼 앞선 지점을 목표 위치로 선택한다는 것이다. 즉 경로상에서 자신보다 일정 거리 앞에 있는 점을 추격한다고 보는 것이며, "pure pursuit"라는 이름도 여기서 유래했다. 사람이 운전할 때와 유사하며, 이 전방주시거리(lookahead distance)는 도로의 굴곡과 시야 가림 등을 반영해 운전 중에도 계속 변화한다.

알고리즘의 역사: Pure Pursuit는 1980년대 초 6륜 스키드 조향 로봇인 Terragator에서, 경로로 복귀하는 데 필요한 호를 계산하는 방법으로 처음 고안되었다(원 유도는 Wallace의 연구를 참고). 이후 NavLab 프로젝트에서 quintic polynomial 방식, "제어이론" 기반 방식 등 여러 경로 추종 알고리즘과 비교되었고, Amidi의 석사 논문에서 Pure Pursuit가 가장 강건하고 신뢰할 수 있는 방법임이 확인되었다. 흥미로운 일화로, 저자가 NavLab II의 추종기를 다시 작성하던 중 기존 코드가 두 개의 서로 다른 lookahead distance(18m와 4.5m)를 혼용해 실행되고 있었다는 버그를 발견했는데, 그럼에도 추종 성능이 상당히 준수했다는 사실이 이 알고리즘의 강건함을 보여주는 사례로 언급된다.

2. Theoretical Derivation

Pure Pursuit 접근법은 목표점(goal point)이라 불리는 선택된 경로상의 점으로 차량을 이끌 곡률을 기하학적으로 결정하는 방법이다. 목표점은 현재 차량의 위치로부터 전방주시거리(lookahead distance)만큼 떨어진 하나의 경로상의 점을 의미한다. 현재 지점과 목표점을 잇는 호(arc)가 구성되고, 이 호의 현의 길이(chord length)가 전방주시거리가 된다.

Fig.1을 보면 좌표축의 원점에 차량이 있고, 후륜 축에 X축이 지나간다. 차량의 좌표계가 후륜 차동장치(rear differential)에 위치하고 X축이 후륜축과 동일선상에 있을 경우, 추진(propulsion)과 조향(steering)이 기하학적으로 분리된다.

원점으로부터 전방주시거리 $l$ 만큼 떨어진 경로 위의 점 $(x, y)$ 가 표기되어 있으며, 목표는 원점과 $(x,y)$ 를 잇고 현의 길이가 $l$ 인 호의 곡률을 구하는 것이다.

Figure 1의 작은 직각삼각형의 기하학적 관계로부터 다음 식(2.1)이 성립하고,

x^2 + y^2 = l^2

X축 위 선분들의 합으로부터 다음 식(2.2)이 성립한다.

x + d = r

식 (2.1)은 원점을 중심으로 하는 반지름이 $l$ 인 원을 나타낸다. 이는 차량이 취할 수 있는 목표점들의 궤적이다.
식 (2.2)는 원점과 목표점을 잇는 호의 반지름 $r$ 과, 목표점의 차량으로부터 X축 오프셋 $x$ 사이의 관계를 나타낸다. 단순히 호의 반지름과 x 오프셋이 서로 독립적이며 $d$ 만큼 차이 난다는 것을 의미한다.

이어서 호의 곡률과 전방주시거리 사이의 관계를 유도하면 다음과 같다.

d = r - x

r^2 - 2rx + x^2 + y^2 = r^2

x^2 + y^2 = 2rx

식 (2.1)의 $x^2+y^2=l^2$ 을 대입하면,

l^2 = 2rx \quad\Rightarrow\quad r = \frac{l^2}{2x}

곡률 $\gamma$ 는 반지름의 역수이므로,

\gamma = \frac{1}{r} = \frac{2x}{l^2}

이렇게 유도된 곡률 식은 목표점의 x 오프셋과, 전방주시거리의 역제곱(inverse square)에 의해 곡률이 결정됨을 보여준다. 이는 이득(gain)이 $l$ 의 역제곱의 2배인 비례 제어기(proportional controller)와 형태적으로 유사하지만, 여기서의 "오차(error)"는 차량 전방에 있는 한 점의 x 오프셋이라는 점에서 다르다.

3. Implementation

전체적인 방법 자체는 비교적 단순하며, 구현 역시 마찬가지다. 실질적인 구현상의 어려움은 대부분 경로 정보를 어떻게 다룰 것인가(통신, 시각화, 플래너로부터 전달받은 새로운 정보로 경로를 갱신하는 방법)에 있으며, 이 부분도 그렇게 복잡하지는 않다.

3.1 Path Representation

경로는 이산적인 점들의 집합으로 표현된다. 일반적으로 경로점은 다음의 정보를 담는 구조체 형태다.

전역 좌표계 상의 x 위치
전역 좌표계 상의 y 위치
전역 좌표계 상의 헤딩
이 지점에서의 경로 곡률
경로 시작점으로부터 이 점까지의 (직선을 따른) 거리

3.2 Communication and Path Management

Tracker는 보통 한 대의 컴퓨터에서 실행되고 Planner는 다른 컴퓨터에서 실행된다. 내비게이션 사이클 동안 planner는 새로 인지된 지형을 통과하는 새로운 경로 세그먼트를 찾아낸다. 이 과정에서 추종기(tracker)는 기존 경로를 따라 차량을 이동시키고 있으며, planner가 계산을 마치면 새로운 경로를 추종기에 전달해야 한다. 이 새로운 경로는 기존 경로와 부분적으로 겹칠 가능성이 높으므로, 계획기는 기존 경로의 어떤 부분을 새로운 정보로 덮어써도 되는지도 함께 전달해야 한다.

추종기는 차량의 센서 모듈과 인터페이스하기 위한 수단도 필요하다. 저자의 구현에서 추종기는 중앙 차량 컨트롤러와 인터페이스를 가지며, 이 컨트롤러가 현재 차량 pose를 알려주고, 추종기는 이 컨트롤러에 주행 요청을 전달한다.

3.3 Pursuit Algorithm

현재 차량 위치 파악
차량에 가장 가까운 경로점 찾기
목표점 찾기
목표점을 차량 좌표계로 변환
곡률을 계산하고 차량에게 그 곡률로 조향을 설정하도록 요청
차량의 위치를 갱신

1) 현재 차량 위치 파악: $(x, y, \text{헤딩})$ 형태로 차량의 위치를 보고하는 함수를 제공하는 중앙 차량 컨트롤러를 통해, 초기화 시점의 차량 위치를 기준으로 보고받는다.

2) 차량에 가장 가까운 경로점 찾기: 기하학적 유도 과정에서 목표점은 차량으로부터 하나의 전방주시거리 이내에 있어야 한다고 명시했다. 전방주시거리에 있는 점이 여러 개일 수 있으므로, 차량에 가장 가까운 경로점을 먼저 찾고, 그 지점부터 경로를 따라 올라가며 전방주시거리만큼 떨어진 점 중 가장 가까운 것을 목표점으로 설정한다.

3) 목표점 찾기: 목표점은 경로를 따라 이동하면서 각 경로점과 차량의 현재 위치 사이의 거리를 계산함으로써 찾는다. 경로점의 위치는 전역 프레임에 기록되어 있으므로 이 계산은 전역 좌표계에서 수행한다.

4) 목표점을 차량 좌표계로 변환: 곡률에 대한 기하학적 유도는 차량 좌표계에서 이루어졌고, 차량에 대한 곡률 명령 역시 차량 좌표계에서 의미를 가지므로, 찾은 목표점을 차량 좌표계로 변환해야 한다.

5) 곡률을 계산: 앞서 유도한 곡률 방정식 $\gamma = 2x/l^2$ 을 이용해 원하는 차량 곡률을 계산한다. 이 곡률은 차량의 온보드 컨트롤러에 의해 조향각으로 변환된다.

6) 차량의 위치 갱신: 시뮬레이션 중에는 이 명령이 차량의 위치와 헤딩에 어떤 영향을 미치는지 판단할 필요가 있다.

4. Properties of the Algorithm

4.1 Lookahead Distance 변화의 효과

Pure Pursuit 알고리즘에는 lookahead distance(전방주시거리)라는 하나의 파라미터가 있으며, 이 값의 변화가 미치는 효과는 다음 두 가지 상황 중 하나의 맥락에서 고려되어야 한다.

경로 재획득(Regaining a path): 차량이 경로로부터 큰 거리만큼 떨어져 있어, 그 경로에 도달해야 하는 상황
경로 유지(Maintaining the path): 차량이 이미 경로 위에 있고, 그 경로 위에 계속 머물고자 하는 상황

첫 번째 문제에 대해서는, $l$ 이 길어질수록 경로에 점진적으로, 진동이 적게 수렴한다. Pure Pursuit의 수렴 거동은 2차 시스템의 스텝 응답과 유사한 형태를 보이며, $l$ 은 감쇠비(damping factor)처럼 작용하는 경향이 있다.

두 번째 문제에 대해서는, $l$ 이 길수록 추종할 수 있는 곡률의 정도가 낮아진다. 이 알고리즘은 차량이 호를 그리며 주행하도록 곡률을 계산하는데, 차량과 목표점 사이의 경로가 충분히 굽어 있다면 두 점을 잇는 단일 호가 존재하지 않게 되고, 어떤 호를 따라 주행하더라도 오차가 유발된다.

4.2 Non Unique Lookahead for a Given Path Curvature

본 논문에서 다루는 경로 추종 문제는 경로에 진입하는 것이 아니라 경로에 머무르는 것이 주된 목적이다. 이를 위해 경로의 곡률과 최적의 lookahead distance 사이의 닫힌 형태(closed-form) 관계를 찾는 것이 매우 유용할 것이다. 이 관계를 찾는다면 경로의 곡률이 변화함에 따라 lookahead distance도 그에 맞게 변화시킬 수 있을 것이다.

이 문제의 해를 찾는다는 것은 lookahead distance와 곡률 사이에 일대일 관계가 존재함을 의미한다. Fig.3의 원은 곡률이 일정한 경로이며, 경로 추종에 사용할 수 있는 lookahead distance가 하나로 정해져야 한다.

원 안의 이등변삼각형을 보면, 목표점까지의 호를 밑변 $l$ 로 하는 이등변삼각형을 통해 원을 구성할 수 있다. 그림에서 볼 수 있듯, 이 조건을 만족시키는 lookahead distance는 하나가 아니라 $(0, 2r)$ 범위에서 여러 개가 존재한다. 즉 lookahead distance가 주어지면 곡률은 하나로 정해지지만, 반대로 곡률이 주어졌을 때 lookahead distance는 유일하게 정해지지 않는다.

4.3 Comments

이 방법에는 동역학과 관련된 한계점이 있다. 이 방법은 차량이나 그 액추에이터의 성능을 모델링하지 않으며, 요청된 곡률에 완벽하게 응답한다고 가정하기 때문에 다음 두 가지 문제를 야기한다.

고속 주행 중 급격한 곡률 변화가 요청될 수 있으며, 이는 차량 후미의 미끄러짐(skid)을 유발한다.
조향(steering)의 1차 지연(first order lag) 때문에, 차량이 원하는 만큼 빠르게 경로에 접근하지 못한다.

References

Amidi, O., Integrated Mobile Robot Control, Master's thesis, Dept. of Electrical and Computer Engineering, CMU, May 1990.
Shin, D.H., High Performance Tracking of Explicit Paths by Roadworthy Mobile Robots, Doctoral thesis, Dept. of Civil Engineering, CMU, May 1990.
Wallace, R. et al., "First Results in Robot Road-Following", CMU-RI-TR-88-4.