Path Planning

1. 경로계획

• 정의 : 한 지점에서 다른 한 지점까지 가는 동안 일어날 수 있는 모든 상황을 고려하여 주행을 진행하는 기술입니다.
• 종류 : 전역 경로 계획 & 지역 경로 계획

- Global Path Planning

Global Map 안에서 출발 지점 ~ 도착 지점까지 갈 수 있는 수많은 경로 중에서 하나의 경로를 선택하는 기술입니다.

최소 비용, 최단 거리, 단순 정도 등에 따라 경로 선택

 

- Local Path Planning

Local Map 안에서 주변 정보를 실시간으로 처리합니다 => 사용자가 안전하고 효율적으로 주행할 수 있도록 하는 기술

전역 경로 계획과 스케일 차이가 있어 목적이 다르고 풀고자 하는 방법이 다릅니다.

1. 돌발 상황에 대응하기 위한 여러 경로가 생성되며 Selection하는 알고리즘 필요
2. Path 후보들을 설정하고, 후보들이 가지는 안정성, 효율성을 체크
3. 실시간성이 높은 경로계획 알고리즘이 필요 (적은 계산량)
4. Human-like 한 솔루션을 마련해야함
5. 경로 계획에서 Perception이 제공하는 정보에 따라 주행의 퀄리티가 다름.
   1. Object Location , Direction, Velocity
   2. 간단한 수학 공식으로 충돌 회피를 위한 계산을 통해 안전한지를 체크할 여력이 있슴.

 

• 주행 환경 인식
  • 주행 경로 탐색, 고정 지물 인식, 이동 물체 인식, 신호등 변동 물체 인식
  • LIDAR, RADAR, Stereo Cam, GPS, HD-Map, V2X 통신
• 판단 주행 전략
  • 목적지까지 경로 계획
  • 차로 변경, 장애물 회피 등과 같은 돌발상황에 대한 판단
  • 학습형 제어시스템, 판단/주행제어 시스템, 주행속도 및 경로 기록
• 차량 제어
  • 핸들 조절, 가속, 감속, 급제동 등
  • 경고 및 정보 제공
  • ADAS, ITS

 

 

 

2. 경로 생성

- Local Planning을 중점으로 합니다.

 

정의 : 어떤 경로를 끊임없이 실시간으로 생성하여 선택하는 알고리즘

• Lane Keeping 
  • Vision으로 차선 인식 -> 차선 Set Point 도출 -> Polynomial interpolation 방식으로 차로 중심 Line 생성                 -> Path Following

 

[주변에 차가 없는 경우]

• Lane 중점으로 쫓아가면 됨
• 주변의 다른 차량들이 차선을 잘 지킨다면 자신의 Lane만 인식

[주변 차량이 내 차선에 인접하거나 차폭이 넓은 차량이 주변에 주행하는 경우]

• 주변 차량의 위치를 고려해 실시간으로 미세한 주행경로 변경이 필요함

==> 이렇듯 항상 가운데가 아닌 새로운 경로 생성이 필요한 경우 많습니다.

 

 

[교차로를 지나는 경우]

• 신호만 고려하여 직진 여부만 생각하면 된다. -> decision making을 통한 경로 생성
• 주변 동적 물체 이동경로를 고려해서 경로 생성

==>경로 생성이란 경로 후보를 만들고 그 중 최적의 안정성, 효율성을 극대화하는 최적의 path를 선택하는 것입니다.

 

 

 

Astar Algorithm

최단 경로를 찾아내는 그래프/트리 탐색 알고리즘입니다.

2D Grid로 현실을 표현해 Grid Map 상에서 최단경로 탐색하여 판단합니다.

이떄 8방향 Cost를 계산해서 최적 경로를 찾는 알고리즘입니다.

 

트리구조

 - 그래프 일종, 여러 노드가 한 노드를 가리킬 수 없는 구조

• 5x5 방을 100개 단위로 100x100으로 쪼갠다면 하나의 grid는 5cmx5cm 사이즈를 가지게 됩니다.
  • 얼마나 잘게 나누냐에 따라 Resolution이 결정된다.
  • 계산량을 고려해 실시간성을 갖춰야합니다.
• 기준점, 사람, 차량, 지형 표현이 가능한 적절한 단위를 선택해야합니다.
• free : space 물체가 없는 영역
• occupied space : 어떤 물체, 장애물이 있는 영역

-탐색 영역 Search

- 탐색 시작

• Open List에 주변 8개 Grid를 삽입
  • Open List : 지나갈 수 있는 길을 의미하는 Set
  • Closed List : 최적 score를 가지는 Set
• 시작점은 Closed List에 삽입

경로 채점 (Path Scoring)

• F = G + H
  • F : Total Score , 현재 이동하는데 걸린 비용과 앞으로 예상 비용을 합친 총 total cost
  • G : 시작점으로부터 현재 사각형까지 경로를 따라 이동하는데 소요되는 비용
  • H : 현재 사각형에서 목적지 B까지의 예상 이동 비용
    • 주변 지형, 지물에 상관하지 않고 예상 이동 비용을 구함

계속 탐색

• Open List에서 가장 작은 F 선택 이후 Closed List에 추가
• 인접 사각형 반복적으로 확인 (가장 작은 Cost Node 가 부모노드가 됨)
• Open List에서 가장 작은 F를 선택하고 Closed List 추가 반복하며 계속적으로 Closed List를 조사하며 점차 확산

경로 선택

• Open List가 비어있는 경우 -> 실패
• 목표 사각형이 Open List에 들어가는 경우 -> 성공
• 도착점이 OpenList에 들어가게되면 Closed List 안에서 부모 노드를 가리키는 방향으로 선을 잇게 됩니다.                     즉, 출발점이 나오게되며 거꾸로 길을 잇는 것으로 볼 수 있습니다.

 

 

RRT/RRT* algorithm

RRT (Rapidly-exploring Random Tree)

무작위 샘플링을 사용하여 고차원의 구성 공간을 탐색하는 경로 계획 알고리즘

• 샘플링 기반에 의거한 방식
• 시작점, 목적지가 정해지면 임의의 x_rand를 뽑아 검색 트리 T를 계속 확장
• 목적지에 빨리 가고 싶은 경우 x_rand를 균등 분포가 아닌 목적지에 치우치게 하는 분포 형태도 활용이 가능

트리 T가 목적지에 도달 시 목적지부터 시작점까지 재귀적으로 트리를 검색해 경로를 선택합니다.

트리 구조가 퍼져나가는 알고리즘입니다.

랜덤 샘플링이라는 것은 Optimality를 보장하지 않습니다.

 

RRT_star

RRT의 Optimality를 향상 시킨 알고리즘입니다

새로운 State를 뽑을때마다 new state의 neighbor들은 optimal path로 rewiring 하는 과정이 가장 큰 차이로 볼 수 있습니다.

x_rand의 일정 반경에 있는 best parent node를 탐색하므로 optimality가 부여됩니다.

• 새로운 best parent가 선정되면 그 주변 노드들을 또 뒤져서 cost를 기준으로 새로 만든 노드와의 재해석으로                 rewiring이 적용됩니다.
  • rewiring : 최저 cost로 가는 경로가 맞는지를 체크해 edge를 끊거나 새로운 edge를 만들어내는 과정

주변 obstacle 정보를 고려해 반복적으로 트리 구조를 확장 & Real Time 보장해야합니다.

• 실시간성을 위해 적정량의 트리 구조를 만들어야합니다.

 

 

 

3. 경로 추종

경로 생성 과정으로 선택된 실시간 경로를 차량이 정확하게 따라갈 수 있도록 주행하는 기술입니다.

제어 기술과 연관성이 매우 높습니다.

• Steering angle과  Velocity 신호를 최적으로 생성해내는 것이 중요 포인트입니다.

 

Pure Pursuit Control

하나의 점을 생성해 경로를 추종

-> 목표 경로를 실시간으로 추종하는 알고리즘을 사용합니다.

-> 하나의 목표지점을 골라 Steering angle을 발행

원에 홀을 만들고 그 전체 원의 r을 가지고 지속적으로 추종할 수 있는 steering angle을 만듭니다.

추종해야되는 path의 일부분의 한 점을 끊임없이 한포인트를 계속 선택하며 맞는 원호를 그리고 그 원의 r을 가져다가 결과적으로 곡률을 구해 끊임없이 조향각을 발생합니다.

• 즉, 차량 앞의 path 위 한 점을 원호를 그리며 따라가는 방법입니다.

Lookahead distance

• 실시간 기준 Distance 측정
• 추종해야할 점을 지속적으로 생성합니다 -> 어떤 점을 고를 것인지 기준을 제시하는 것이 Lookahead distance             (저속 : 가까운 점, 고속 : 먼 점)

1. Lookahead distance 기준으로 하나의 점을 정함
2. 차와 점을 잇는 원을 그림
3. r(반지름)을 구함
4. 곡률 계산
5. Steering angle 계산

• r을 구할 수 있다면 곡률을 구할 수 있습니다.
• 곡률은 steering angle과 비례 관계입니다. (차체폭, 길이 등으로 계산 가능)
• 고속도로에서는 Lookahead distance를 멀리, 곡선이 심한 코너에서는 매우 짧게 잡아야합니다.
  • 멀리잡으면 곡률이 매우 커서 Steering이 거의 0에 수렴
  • 짧게 잡으면 곡률이 작으므로 Steering이 매우 큼 (곡선 주행)
• 즉시 포인트를 잡아야 하므로 이후 상황 예측 불가
• Way Point의 Set을 미리 검사하도록 보완해야합니다. (미래 예측 포인트, 도로 곡률 고려)
  • 미리 Lookahead distance를 조절해주는 아이디어가 추가되어야합니다.

 

 

Model Predictive Control

실시간성이 높은 예측 컨셉

목표 경로를 최적으로 추종하여 쫓아가는 알고리즘

• Control input 이나 Measurement output도 예측되는 영역까지 있기 때문에 단순히 끊임없이 실시간으로 현재까지 정보만을 이용하는 제어 방법보다는 예측이 되므로 좀 더 안정성이 높은 알고리즘을 만들 수 있음
• Pure Pursuit은 기하학적 접근 방법, 당양한 동력학적 변수가 제외됨, 미래 예측이 어려움
• Model Predictive Control은 모델 예측 접근 방법이고, 실시간 예측 및 추종, 광범위한 범위에서 주목받는 연구분야

 

• PID 방법 -> Feedback loop 의 기본적 방법

 

MPC vs PID

PID : feedback loop은 Gain Parameter를 잘못 설정하면 oscillation 발생

MPC : 현상을 모델링되어 있으며, cross-track error로 얼마나 어긋나 있는지를 확인하며 보낼 수 있습니다.

Cost Function : cost를 Minimize 할 수 있도록 조향각/속도를 결정

차량 제어를 위한 Cost 설정 및 cost term들은 제각각 의미 보유합니다.

• 자율주행에 필요한 Cost를 제시해줍니다.
• 매우 짧은 시간에 대한 예측은 가능합니다
  • dt와 샘플 개수를 설정합니다. 이는 안정적인 주행경로를 제시할 수 있게 합니다.
• t 영역 정보로 t+1을 예측해 보다 안정적 주행 기술을 달성하고자합니다.

 

 

MPC vs Pure Pursuit

-> 기하학적인 접근과 모델적 접근으로 동기가 아예 다릅니다.

-> 두 제어 알고리즘 모두 간단한 경우의 경로 추종은 무리없이 가능합니다.