경로 계획

JeongChaeJin·2022년 4월 15일

자율주행

목록 보기

2/4

1. 경로계획

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

전역 경로 계획

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

지역 경로 계획

Local Map 안에서 주변 정보를 실시간으로 처리.
- 사용자가 안전하고 효율적으로 주행할 수 있도록 하는 기술
전역과 스케일 차이가 분명하다. 목적이 다르므로 풀고자하는 방법이 다른 것이다.

주행 환경 인식

주행 경로 탐색, 고정 지물 인식, 이동 물체 인식, 신호등 등 변동 물체 인식
LIDAR, RADAR, Stereo Cam, GPS, HD-Map, V2X 통신

판단/주행 전략

목적지까지 경로 계획
차로 변경, 장애물 회피 등 돌발상황에 대한 판단
학습형 제어시스템, 판단/주행제어 시스템, 주행속도 및 경로 기록

차량 제어

핸들 조절, 가속, 감속, 급제동 등
경고 및 정보 제공
ADAS, ITS

Global Path Planning

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

Local Path Planning

돌발 상황에 대응하기 위해 여러 경로가 생성되며 Selection하는 알고리즘이 필요해짐

Path 후보들을 설정하고, 후보들이 갖는 안정성, 효율성을 체크
안정성과 효율성의 trade-off를 해결해야됨
실시간성이 높은 경로계획 알고리즘이 필요 (적은 계산량)
Human-like 한 솔루션을 마련해야함
경로 계획에서 Perception 이 제공하는 정보에 따라 주행의 퀄리티가 다름
- Object Location, Direction, Velocity
- 간단한 수학 공식으로 충돌 회피를 위한 계산을 통해 안전한지를 체크할 여력이 좀 더 있다.

2. 경로 생성

Local Planning에 초점을 둔다.

경로 생성 정의

어떤 경로를 끊임 없이 실시간으로 생성해서 선택하는 알고리즘
- Lane Keeping : Vision 으로 차선 인식 -> 차선 Set Point 도출 -> Polynomial interpolation 방식으로 차로의 중심 Line 생성 -> Path Following

항상 가운데가 아닌 새로운 경로 생성이 필요한 경우 많음

신호, 주변물체 움직임 정보를 통해 경로 생성이 필요
경로 생성이란 경로 후보를 만들고 그 중 최적의 안정성, 효율성을 극대화하는 최적의 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 Contorl

하나의 점을 선택해 경로를 추종
목표 경로를 실시간으로 추종하는 알고리즘
하나의 목표지점을 골라 Steering angle을 발행

원에 홀을 만들고 그 전체 원의 r을 가지고 지속적으로 추종할수 있는 steering angle을 만든다.
추종해야되는 path의 일부분의 한 점을 끊임없이 한포인트를 계속 선택하며 맞는 우너호를 그리고 그 원의 r을 가져다가 결과적으로 곡률을 구해 끊임없이 조향각을 발생
- 즉, 차량 앞의 path 위 한 점을 원호를 그리며 따라가는 방법
Lookahead distance
- 실시간 기준 Distance 측정
- 추종해야할 점을 지속적으로 생성 -> 어떤 점을 고를 것인지 기준을 제시하는 것이 Lookahead distance (저속: 가까운 점, 고속 : 먼 점)

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

Velocity Control

Model Predictive Control

실시간성이 높은 예측 컨셉
목표 경로를 최적으로 추종하여 쫓아가는 알고리즘

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