경로 계획 개요: 샘플링, 검색, 최적화를 기반으로 모든 작업이 완료되었습니다!

1 의사결정 제어 및 동작 계획 개요

현재 의사결정 제어 방법은 순차 계획, 행동 인식 계획, 엔드 투 엔드 계획의 세 가지 범주로 나눌 수 있습니다.

• 순차적 계획: 가장 전통적인 방법인 인지, 결정 및 통제의 세 부분은 상대적으로 명확합니다.
• 행동 인식 계획: 첫 번째 방법과 비교할 때 가장 중요한 점은 인간-기계 협업 도입 운전, 차량-도로 협업 및 외부 동적 환경에 대한 차량 위험 예측
• 종단 간 계획: 대량의 데이터 교육을 통해 DL 및 DRL 기술을 얻습니다. 이미지와 같은 감각 정보부터 스티어링 휠 각도와 같은 차량 제어 입력까지의 정보 관계는 요즘 가장 인기 있는 방법 중 하나입니다.

이 글에서는 순차적 계획을 소개하고, 전체 결정 제어 시퀀스에 따른 자율주행차의 인식 제어 프로세스를 설명하고, 마지막으로 위에서 언급한 해결해야 할 문제를 간략하게 요약합니다.

자동 차량을 위한 제어 아키텍처

2 경로 계획 개요

순차 계획 프로세스는 경로 계획->의사 결정 프로세스->차량 제어로 간략하게 요약됩니다. 이 문서에서 설명하는 계획은 첫 번째와 세 번째 단계에 속합니다.

//m.sbmmt.com/link/aa7d66ed4b1c618962d406535c4d282a

무인 차량의 궤적 생성 문제에는

직접 궤적 생성 방식과 path- 속도 분해 방법 , 첫 번째 유형에 비해 경로 속도가 덜 어려워서 더 일반적으로 사용됩니다.

2.1 경로 계획 유형

경로 계획은 네 가지 주요 범주로 나눌 수 있습니다. PRM 및 RRT로 표시되는

샘플링 기반 알고리즘, A* 및 D*로 표시되는 search 기반 알고리즘, 궤적 생성 β-스플라인 곡선으로 표현되는 보간 피팅 기반 알고리즘과 MPC로 표현되는 로컬 경로 계획을 위한 최적 제어 알고리즘입니다. 이 섹션은 위의 순서로 설명됩니다.

동작 계획 기술 알고리즘 검토

3.1.1 기본 알고리즘 PRM 및 RRT

(1) PRM

PRM 알고리즘 (확률적 로드맵). PRM은 크게 두 단계로 구성되는데, 하나는 학습 단계이고 다른 하나는 쿼리 단계입니다. 첫 번째 단계인 학습 단계: 상태 공간의 안전 영역에서 n개의 점을 균일하고 무작위로 샘플링하고, 샘플이 장애물에 떨어지는 점을 삭제한 다음, 인접한 점을 연결하여 충돌 감지를 수행하고, 비를 제거합니다. - 충돌 없는 연결, 그리고 마지막으로 연결된 그래프를 얻습니다.

두 번째 단계, 쿼리 단계: 주어진 초기 상태와 목표 상태 쌍에 대해 이전 단계에서 구성한 샘플링 노드와 연속성을 사용하고 그래프 검색 방법(Dijkstra 또는 A*)을 사용하여 실행 가능한 경로를 찾습니다. PRM 구축이 완료된 후 다양한 초기 및 목표 상태의 모션 계획 문제를 해결하는 데 사용할 수 있지만 무인 차량 모션 계획에는 이 기능이 필요하지 않습니다. 또한 PRM에는 상태 간의 정확한 연결이 필요하며 이는 복잡한 미분 제약 조건이 있는 동작 계획 문제의 경우 매우 어렵습니다.

(2) RRT

RRT(신속 탐색 랜덤 트리) 알고리즘. RRT는 실제로 ​무작위로 자라는 나무

에 기초한 일련의 알고리즘을 나타냅니다. 현재 로봇공학 분야에서 가장 많이 사용되는 알고리즘입니다.

① 트리 초기화: 트리의 노드 세트와 에지 세트, 노드 세트에는 초기 상태만 포함되며 에지 세트는 비어 있습니다.

② 트리 성장: 상태 공간을 무작위로 샘플링합니다. 샘플링 지점이 상태 공간의 안전 영역에 떨어지면 현재 트리에서 샘플링 지점에 가장 가까운 노드를 선택하고 생성된 경우 샘플링 지점까지 확장합니다. 궤적은 장애물과 연결되지 않습니다. 물체가 충돌하면 궤적은 트리의 가장자리 세트에 추가되고 궤적의 끝점은 트리의 노드 세트에 추가됩니다

③ 확장될 때까지 ② 단계를 반복합니다. PRM의 무방향 그래프와 비교하면, RRT는 초기 상태를 루트 노드로, 타겟 상태를 리프 노드로 갖는 트리 구조로 구성됩니다. 건설될.

RRT는 상태 간의 정확한 연결이 필요하지 않으며 무인 차량 모션 계획과 같은 모션 역학 문제를 해결하는 데 더 적합합니다.

3.1.2 샘플링 방법의 문제점과 해결책

해결 효율성과 최적의 솔루션인지 여부. PRM과 RRT가 확률적 완전성을 갖는 이유는 구성 공간의 거의 모든 위치를 탐색하기 때문입니다.

(1) 해결 효율성

해결 효율성 향상 측면에서 RRT 최적화의 핵심 아이디어는 나무를 열린 공간으로 안내하는 것입니다. 장애물이 있는 곳에서 노드를 반복적으로 확인하지 않도록 하여 효율성을 향상시킵니다. 주요 해결책:

① 균일한 샘플링

표준 RRT 알고리즘은 상태 공간을 균일하고 무작위로 샘플링합니다. 현재 트리의 노드가 확장을 얻을 확률은 보로노이 지역 면적에 비례합니다. 트리는 상태를 향해 이동할 것입니다. 공간의 빈 영역이 성장하여 상태 공간의 자유 영역이 균일하게 채워집니다.

RRT-connect 알고리즘은 각각 initial상태와 target상태에서 시작하여 두 개의 트리를 동시에 구축합니다. 두 트리가 함께 성장하면 실행 가능한 솔루션이 발견됩니다. Go-biaing은 무작위 샘플링 시퀀스에 특정 비율로 목표 상태를 삽입하여 트리가 목표 상태를 향해 확장되도록 유도하고 솔루션 속도를 높이고 솔루션 품질을 향상시킵니다.

휴리스틱 RRT는 휴리스틱 함수를 사용하여 확장 비용이 낮은 노드의 샘플링 확률을 높이고 트리의 각 노드의 비용을 계산합니다. 그러나 복잡한 환경에서는 이 문제를 해결하기 위해 비용 함수를 정의하기가 어렵습니다. f -바이어스 샘플링 방법은 먼저 상태 공간을 그리드로 이산화한 다음 Dijkstra 알고리즘을 사용하여 각 그리드의 비용을 계산합니다. 그리드 영역에 있는 포인트의 비용 값은 이 값과 같습니다. , 이를 통해 휴리스틱 함수를 구성합니다.

② 최적화된 거리 측정법

거리는 두 구성 사이의 경로 비용을 측정하는 데 사용되며, 경험적 비용 함수 생성을 지원하고 트리 방향을 안내합니다. 그러나 장애물을 고려하면 거리 계산이 어렵다. 운동 계획에서의 거리 정의는 유클리드 거리와 유사한 정의를 채택한다. RG-RRT(재연결성 안내 RRT)는 RRT의 탐색 능력에 대한 부정확한 거리의 영향을 제거할 수 있습니다. 샘플링 지점에서 노드까지의 거리가 도달 가능한 노드 집합보다 큰 경우 트리에서 도달 가능한 노드 집합을 계산해야 합니다. 노드, 거리, 노드는 확장을 위해 선택될 수 있습니다.

3 충돌 검사 횟수 줄이기

충돌 검사 샘플링 방법의 효율성 병목 현상 중 하나는 일반적인 접근 방식이 경로를 동일한 거리로 이산화한 다음 각 구성에서 충돌 검사를 수행하는 것입니다. 가리키다. 해결 완료 RRT는 장애물에 가까운 노드를 줄여 확장 확률을 얻습니다. 입력 공간을 이산화하고 특정 입력에 해당하는 궤적이 장애물과 충돌하는 경우 해당 노드 입력에 대해 한 번만 사용합니다. 페널티 값이 노드에 추가됩니다. 페널티 값이 높을수록 노드가 확장될 확률은 낮아집니다. 동적 도메인 RRT와 적응형 동적 도메인 RRT는 샘플링 영역을 현재 트리가 위치한 로컬 공간으로 제한하여 장애물에 가까운 노드의 반복적인 확장 실패를 방지하고 알고리즘 효율성을 향상시킵니다.

4 실시간 성능 향상

Anytime RRT는 먼저 신속하게 RRT를 구축하고, 실현 가능한 솔루션을 구하고 비용을 기록한 후 샘플링을 계속하지만, 실현 가능한 솔루션의 비용을 줄이는 데 유리한 노드만 삽입합니다. 트리를 사용하여 점차적으로 더 나은 실행 가능한 솔루션을 얻습니다. 재계획은 전체 계획 작업을 여러 개의 동일한 시간 하위 작업 순서로 분해하고 현재 작업을 실행하는 동안 다음 작업을 계획합니다.

(2) optimality 문제를 해결하는 방법은 주로 다음과 같습니다.

RGG 알고리즘(무작위 기하 그래프): 무작위 기하 그래프 이론을 기반으로 표준 PRM 및 RRT를 개선한 점근적 최적 특성을 갖는 PRM RRG 및 RRT 알고리즘은 상태 공간에서 n개의 점을 무작위로 샘플링하고 r(n)보다 작은 거리의 점을 연결하여 RGG를 형성합니다.

RRT* 알고리즘: RRG 기반의 "재연결" 단계를 도입하여 새로 삽입된 노드가 인접 포인트의 상위 노드로 인접 포인트의 비용을 줄일 수 있는지 확인합니다. 그렇다면 원래 상위 및 하위 노드를 제거합니다. 현재 삽입 지점을 상위 노드로 취하는 관계, 이것이 RRT* 알고리즘입니다.

LBT-RRT 알고리즘: 많은 수의 노드 연결과 로컬 조정으로 인해 PRM 및 RRT가 매우 비효율적입니다. LBT-RRT 알고리즘은 RRG와 RRT* 알고리즘을 결합하여 점근적 최적성을 얻는 것을 전제로 더 높은 효율성을 얻습니다.

3.2 검색 기반 알고리즘

기본 아이디어는 상태 공간을 특정 방식으로 그래프으로 이산화한 다음 다양한 휴리스틱 검색 알고리즘을 사용하여실행 가능한 솔루션또는 심지어최적의 솔루션을 검색하는 것입니다. 솔루션 , 이 카테고리 알고리즘은 비교적 성숙했습니다.

검색 기반 알고리즘의 기본은 상태 격자입니다. 상태 격자는 상태 노드와 해당 노드에서 시작하여 인접 노드에 도달하는 모션 프리미티브로 구성됩니다. 상태 노드는 모션 프리미티브 변환을 다른 상태 노드로 전달할 수 있습니다. 상태 격자는 원래의 연속 상태 공간을 검색 그래프로 변환합니다. 동작 계획 문제는 그래프에서 초기 상태를 목표 상태로 변환하는 일련의 동작 프리미티브를 검색하는 것입니다. 최적의 궤적을 찾는 알고리즘입니다.

3.2.1 기본 알고리즘 구축 Dijkstra 및 A*

Dijkstra 알고리즘은 전체 구성 공간을 순회하여 각 두 그리드 사이의 거리를 구한 후 최종적으로 시작점에서 목표점까지의 최단 경로인 폭을 선택합니다. 첫 번째 Nature는 이 알고리즘에 휴리스틱 기능, 즉 검색된 노드에서 대상 노드까지의 거리를 추가하고 이를 기반으로 다시 검색하면 전체 검색으로 인한 비효율성을 피할 수 있는 A*알고리즘입니다. , 아래 그림과 같이 빨간색이 검색 영역입니다.

그림 6: A* 및 Dijkstra 알고리즘의 효과 비교

3.2.2 검색 방법의 문제점 및 제안

샘플링 기반 알고리즘과 마찬가지로 이 유형의 알고리즘도 효율적이고 효율적이어야 합니다. 최적의 성적 최적화.

효율성 향상 측면에서 A* 자체는 A* 알고리즘을 확장한 것으로, 휴리스틱 기능의 가중치를 높여 검색 방향을 대상 노드로 더욱 안내합니다. 속도는 매우 빠르지만, Local Minima에 빠지기 쉽고 Global Optimal Solution을 보장할 수 없습니다.

움직이는 차량의 경우 A*의 파생 알고리즘 D(동적 A)를 사용하면 효율성을 크게 향상시킬 수 있습니다. 또한 동적 프로그래밍을 기반으로 하는 이 알고리즘은 상태 그리드의 모션 프리미티브 비용이 시간에 따라 변하는 상황을 처리할 수 있으며, 더 적은 수의 재검색을 통해 새로운 최적의 계획을 계획할 수 있습니다. 노드 경로. LPA를 기반으로 개발된 D*-Lite는 D*와 동일한 결과를 얻을 수 있지만 효율성은 더 높습니다.

최적의 솔루션을 검색할 때 ARA*는 Weighted A* 알고리즘을 기반으로 개발된 언제든지 검색 알고리즘으로, Weighted A* 알고리즘을 여러 번 호출하여 각 호출마다 휴리스틱 기능의 가중치를 줄입니다. INCONS 세트를 도입함으로써 각 주기는 이전 주기의 정보를 계속 사용하여 경로를 최적화하고 점차적으로 최적의 솔루션에 접근할 수 있습니다.

알고리즘 효율성과 최적성의 균형 측면에서 Sandin aine 등은 휴리스틱 기능 중 하나가 단독으로 사용될 때 최적의 솔루션을 찾을 수 있도록 여러 휴리스틱 기능을 도입하여 조정을 통해 MHA* 알고리즘을 제안했습니다. 다양한 휴리스틱 함수에 의해 생성된 결과는 알고리즘의 효율성과 최적성을 고려할 수 있습니다. DMHA는 MHA를 기반으로 온라인 및 실시간으로 적절한 휴리스틱 기능을 생성하여 로컬 최소 문제를 방지합니다.

3.3 보간 피팅 기반 알고리즘

보간 피팅 기반 알고리즘은 다음과 같이 정의할 수 있습니다. 데이터 보간 및 을 사용하여 로드맵을 설명하는 데 사용되는 알려진 일련의 점 집합을 기반으로 합니다. 커브 피팅 방식은 스마트카가 이동할 경로를 생성하여 더 나은연속성과 더 높은차별성을 제공할 수 있습니다. 구체적인 방법은 다음과 같습니다.

Dubins 곡선과 Reeds and Sheep(RS) 곡선은 구성 공간의 두 점을 연결하는 최단 경로로, 각각 반전이 없는 상황과 반전이 있는 상황에 해당합니다. 모두 곡률이 최대인 호와 직선으로 구성되어 있으며, 호와 직선의 연결 부분에 곡률의 불연속성이 존재하며, 실제 차량이 이러한 곡선을 따라 주행할 경우에는 불연속적인 부분에서 정지하고 핸들을 조정해야 합니다. 계속 운전하려면 곡률이 필요합니다.

다항식 보간 곡선은 노드의 요구 사항을 충족하여 다항식 계수를 설정하고 더 나은 연속 미분성을 얻을 수 있는 방법입니다. 다항식은 측면 구속 제어에 자주 사용되며 3차 다항식은 추월 궤적에도 사용됩니다.

스플라인 곡선은 닫힌 표현을 가지며 쉽게 곡률 연속성을 보장할 수 있습니다. β-스플라인 곡선은 곡률 연속성을 얻을 수 있고, 3차 베지어 곡선은 곡률의 연속성과 경계성을 보장할 수 있으며 계산량이 상대적으로 적습니다. θ^3 곡선[43]은 7도 스플라인 곡선으로 곡률의 연속성과 곡률 미분의 연속성이라는 매우 좋은 특성을 갖고 있으며 이는 고속 차량에 매우 의미가 있습니다.

3.4 최적 제어 기반 알고리즘

MPC는 주로 장애물 회피를 위한 로컬 경로 계획을 수행할 수 있기 때문에 경로 계획으로 분류됩니다. 또한 MPC의 주요 기능은 궤도를 추적하는 것입니다. 필요한 역학 및 운동학적 제약에 대해 고려되는 문제는 편안함, 감각 정보의 불확실성, 향후 차량 간 통신의 불확실성을 고려해야 하며 로컬 궤도를 계획할 때 운전자도 제어 루프에 포함될 수 있습니다. 위에서 언급한 불확실성 문제와 드라이버를 제어 루프에 통합하는 문제는 섹션 4에서 논의됩니다. MPC 연구는 주로 최적화 이론과 엔지니어링 실습이라는 두 가지 측면에서 시작됩니다. 전자의 경우 Dimitri P. Bertsekas의 Convex Optimization Algorithms와 James B. Rawlings의 Model Predictive Control: Theory, Computation, Design을 추천합니다. 중국어 분야에서는 류하오양 선생님의 최적화 책이 상대적으로 명확하고 이해하기 쉽다고 개인적으로 느꼈습니다. 후자의 경우 우선 공젠웨이 선생님의 자율주행 MPC 책을 적극 추천합니다. 이전 버전의 책에서는 데모에 문제가 있었지만 새 버전에서는 모두 해결되었습니다.

MPC에서 사용하는 예측 모델은 컨벌루션 신경망, 퍼지 제어, 상태 공간 등 다양합니다. 그중 가장 일반적으로 사용되는 것은 상태 공간 방법입니다. MPC는 다음과 같이 간단히 표현할 수 있습니다. 필요한 동역학, 운동학 등의 제약 조건이 충족되면 모델의 최적 솔루션이 수치적 수단을 통해 해결됩니다. 최적 솔루션은 스티어링 휠 각도와 같은 상태 방정식의 제어 변수입니다. 등을 입력하고 제어량을 자동차 모델에 적용하여 속도, 가속도, 좌표 등 필요한 상태량을 구합니다.

위의 설명에서 알 수 있듯이 MPC의 핵심은 모델의 구축과 솔루션에 있습니다. 모델 구축을 어떻게 동등하게 단순화하고 솔루션의 효율성을 향상시키는 것이 최우선입니다. 차량은 서로 다른 제어 입력에 따라 서로 다른 궤적을 가지며, 각 궤적은 목적 함수 값에 해당합니다. 무인 차량은 해결 알고리즘을 사용하여 최소 목적 함수 값에 해당하는 제어량을 찾아 위의 차량에 적용합니다. , 아래 그림과 같이

모델링의 어려움을 줄이기 위해 인공 위치에너지장 모델도 모델링에 사용됩니다. 인공 위치에너지장의 기본 개념은 전기장과 유사하며, 도로 위의 장애물은 전하 극성이 다른 전하와 유사합니다. 장애물(동적, 정적)에서의 위치 에너지는 더 높으며, 무인 차량은 낮은 위치 에너지 위치를 향해 이동합니다.

4 오픈 소스 프로젝트

오픈 소스 프로젝트 추천 CppRobotics:

• Path Planning
• Dijkstra
• A Star
• RRT
• 동적 창 접근 방식
• 모델 예측 궤적 생성기
• 큐빅 스플라인 플래너
• State Lattice Planner
• Frenet Frame Trajectory

5 학습 방법

새로운 분야를 시작하기 위한 학습 맥락은 다음과 같습니다: Engineering, Theory 및 Visiontroika가 함께 진행되어 경로 계획을 수립합니다. 예:

5.1 Engineering

은 각 경로 계획 알고리즘의 내용을 이해하는 동시에 폭에서 각 알고리즘의 내용을 이해하는 동시에 깊이에서 각 알고리즘의 세부 사항을 학습하는 것을 의미합니다. . 경로 계획 분야의 알고리즘과 관련하여 현재 포괄적인 튜토리얼은 없지만 Gong Jianwei의 NMPC 동작 계획이 참고 자료가 될 수 있습니다.

5.2 이론

은 이러한 알고리즘의 작동을 뒷받침하는 수학적 원리와 이러한 알고리즘이 생성되는 이유(수학적 관점)를 이해하는 것을 말합니다.

• 최적화 이론에 속하는 최적의 제어변수(경로)를 구하기 위해 목적함수와 제약조건을 구축하고 극한값을 동시에 구하는 방법
일반적인 뉴턴법, 최속하강법 등이 있습니다. 이러한 수치해석 방법의 본질은 대수방정식을 수치적으로 푸는 데서 유래하며
• 수리적 분석에 속합니다.
해결 과정에서 볼 수 있는 미분 야코비안 행렬, 판단 조건의 벡터 노름 등은 본질적으로 1차원 수치 해를 변환하는 것이며 높은 차원에 도달하며
• 행렬 이론에 속합니다.

5.3 비전

은 과학 연구 문서 및 결과 보고서 등을 사용하여 과학 연구 및 기업에서 경로 계획의 주요 적용을 이해하는 것을 말합니다.

6 요약

이 문서에서는 현재 경로 계획의 개요를 소개하고 현재 경로 계획 방법을 이해합니다. 내용이 매우 복잡하고, 실무적인 응용지향이 없으면 단시간에 모두 배우기 어렵습니다. 필요할 때만 집중해서 학습할 수 있습니다.