KR20210061461A - 자율 차량 계획 - Google Patents

Abstract

자율 차량(AV) 계획 방법은: AV와 관련된 센서 입력들을 수신하는 단계와; 직면한 주행 시나리오를 결정하기 위해 상기 AV와 관련된 센서 입력들을 처리하는 단계와; AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고 상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고, 상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정된다.

Description

자율 차량 계획

본 발명은 자율 차량(AV) 기동 계획에 관한 것이다.

자율 주행 차량이라고도 하는 자율 차량은 외부 환경을 모니터링하기 위한 센서 시스템 및 이러한 센서들을 사용하여 자동으로 주행 결정들을 내리고 실행할 수 있는 제어 시스템을 갖춘 차량을 말한다. 여기에는 특히 센서 시스템으로부터의 입력을 기반으로 차량의 속도와 이동 방향을 자동으로 조정하는 기능이 포함된다. 완전 자율 주행 또는 "무인" 차량은 인간 운전자의 입력없이 작동할 수 있는 충분한 의사 결정 능력을 갖추고 있다. 그러나, 여기에서 사용된 자율 차량이라는 용어는 자율적 의사 결정 능력이 더 제한적이므로 여전히 사람 운전자의 감독이 필요한 준 자율 차량들(semi-autonomous vehicles)에도 적용된다.

직면한 주행 시나리오를 안전하고 효과적으로 탐색하기 위해, 자율 차량 계획자는 직면한 시나리오에서 실행될 기동들의 시퀀스를 계획할 수 있어야 한다. 본 발명은 컴퓨터로 구현된 AV 플래너가 다른 차량들/에이전트들의 예상되는 행동을 고려하여 직면한 주행 시나리오에서 상이한 일련의 기동들의 가능한 효과에 대해 추론할 수 있도록 하는 추론 프레임워크를 제공하여, 해당 시나리오에서 실행될 적절한 기동들(자아 차량 기동들(ego vehicle maneuvers))의 시퀀스를 결정할 수 있다.

본 발명의 양태들은 자율 차량(AV) 계획 방법에 관한 것으로서,

AV와 관련된 센서 신호들(입력들)을 수신하는 단계와;

직면한 주행 시나리오를 결정하기 위해 상기 센서 입력들을 처리하는 단계와;

AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고

상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,

상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트(행위자)의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정된다.

상기 외부 에이전트의 예상되는 행동은 상기 센서 신호들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 생성 행동 모델을 적용함으로써 시뮬레이션된다.

상기 생성 행동 모델은 또한 하나 이상의 자아 차량 파라미터(계획 방법에 의해 실행되거나 통제되는 자아 차량에 대한 다른 행위자의 반응을 모델링하기 위한 것) 및/또는 주행 시나리오의 하나 이상의 파라미터(예를 들어, 환경에 대한 다른 행위자의 반응을 모델링하기 위한 도로 레이아웃/다른 운전 환경 파라미터)에 적용될 수 있다.

본 발명의 제1 양태에서, 상기 생성 행동 모델은 관찰된 실제 주행 행동의 예들을 기반으로 훈련된 기계 학습(ML) 모델이다.

즉, 상기 제1 양태는 자율 차량(AV) 계획 방법을 제공하고, 이 방법은:

AV와 관련된 센서 입력들을 수신하는 단계와;

직면한 주행 시나리오를 결정하기 위해 상기 AV와 관련된 센서 입력들을 처리하는 단계와;

AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고

상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,

상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정되며, 그리고

상기 외부 에이전트의 예상되는 행동은 상기 센서 입력들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 생성 행동 모델을 적용함으로써 시뮬레이션되고, 상기 생성 행동 모델은 관찰된 실제 주행 행동의 예들을 기반으로 훈련된 기계 학습(ML) 모델이다.

실시예들에서, 객체 추적은 상기 외부 에이전트의 관찰된 추적을 결정하기 위해 상기 센서 입력들에 적용될 수 있고, 상기 외부 에이전트의 예상되는 행동은 상기 관찰된 추적에 기초하여 시뮬레이션될 수 있다.

상기 생성 모델을 훈련시키는데 사용되는 관찰된 실제 주행 행동의 예들 중 적어도 일부는 폐쇄 회로 텔레비전 데이터로부터 추출될 수 있다.

상기 생성 행동 모델은 훈련된 신경 네트워크를 포함할 수 있다.

상기 외부 에이전트의 예상되는 행동은, 상기 직면한 주행 시나리오의 주행 영역에 대해 학습된 공간적 마르코프 모델의 학습된 점유 확률 및/또는 천이 확률을 사용하여 시뮬레이션될 수 있다.

상기 트리 검색 알고리즘은 확률적 트리 검색 알고리즘일 수 있다.

상기 트리 검색 알고리즘은 몬테카를로 트리 검색(MCTS) 알고리즘일 수 있다.

상기 주행 시나리오는 정의된 시나리오 서술 언어에 따라 주행 시나리오 파라미터들을 센서 입력들로부터 추출함으로써 결정될 수 있다.

상기 생성 행동 모델은 또한 하나 이상의 자아 차량 파라미터 및/또는 상기 주행 시나리오의 하나 이상의 파라미터에 적용된다.

본 발명의 제2 양태에서, 상기 생성 행동 모델은 예상되는 행동을 시뮬레이션하기 위해 하나 이상의 관찰된 파라미터에 역 계획 방법을 적용하는 역 플래너의 형태를 가진다.

즉, 제2 양태는 자율 차량(AV) 계획 방법을 제공하고, 이 방법은:

AV와 관련된 센서 입력들을 수신하는 단계와;

직면한 주행 시나리오를 결정하기 위해 상기 센서 입력들을 처리하는 단계와;

AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고

상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,

상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정되며, 그리고

상기 외부 에이전트의 예상되는 행동은 상기 센서 입력들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 역 계획 방법을 적용함으로써 시뮬레이션된다.

역 계획 방법은 직면한 주행 시나리오에서 외부 행위자에 대한 이용 가능한 목표들 세트를 결정하는 단계, 및 예상되는 행동을 시뮬레이션하기 위해 이용 가능한 목표들의 세트에 대해 확률적 또는 결정론적 목표 인식을 적용하는 단계를 포함할 수 있다. 결정론적 목표 인식은 이용 가능한 목표들 중 하나를 외부 행위자가 구현하는 것으로 식별하는 것을 의미한다. 확률적 목표 인식은 이용 가능한 목표들 중 적어도 하나에 대해 외부 에이전트가 해당 목표를 구현할 확률(예를 들어, 외부 행위자가 해당 목표를 구현할 확률인 각 목표에 대한 확률)을 추정하는 것을 의미한다.

객체 추적은, 상기 직면한 주행 시나리오에서 적어도 하나의 외부 행위자를 추적하고, 시간 간격에 걸쳐 상기 외부 행위자의 관찰된 추적을 결정하기 위해 상기 센서 입력들에 적용될 수 있다.

상기 역 계획 방법은:

상기 직면한 주행 시나리오에서 상기 외부 행위자에 대해 이용 가능한 목표들의 세트를 결정하는 단계와;

상기 이용 가능한 목표들 각각에 대해, 예측된 궤적 모델을 결정하는 단계와;

상기 외부 행위자의 관찰된 추적을 상기 이용 가능한 목표들 각각에 대한 예측된 궤적 모델과 비교하여 해당 목표의 가능성을 결정하는 단계와; 그리고

상기 외부 행위자의 예상되는 행동을 시뮬레이션하기 위해 상기 목표들 중 적어도 하나의 결정된 가능성을 사용하는 단계를 포함할 수 있다.

상기 외부 행위자의 예상되는 행동을 시뮬레이션하기 위해 상기 목표들 중 적어도 하나의 결정된 가능성을 사용하는 단계는, 적어도 하나의 목표에 대한 예측된 궤적 모델 및 해당 목표의 결정된 가능성에 기초하여 상기 외부 행위자에 대한 적어도 하나의 예측된 궤적을 계산하는 단계를 포함할 수 있다.

각 목표에 대한 예측된 궤적 모델은 해당 목표와 관련된 예측된 궤적들의 분포일 수 있다.

각 목표 G_i에 대한 분포는 예측된 궤적들의 세트에서 각 예측된 궤적 T에 대한 조건부 확률 p(T|G_i)을 포함할 수 있고, 해당 목표의 가능성 p(G_i|τ)은 관찰된 추적 τ이 주어지면 적어도 하나의 예측된 궤적 확률 p(T|τ)을 추정하기 위해 사용된다.

상기 관찰된 추적은 해당 목표에 대한 가장 유용한 궤적 모델을 예측하는데 사용되고, 상기 비교는 상기 가장 유용한 궤적 모델을 상기 예측된 궤적 모델과 비교하는 것을 포함한다.

상기 관찰된 추적은 상기 외부 행위자의 현재 기동 및/또는 미래 기동을 예측하는데 사용되며, 상기 예측된 현재 또는 미래 기동은 상기 가장 유용한 궤적 모델을 결정하기 위해 사용될 수 있다.

다중 기동들의 시퀀스가 적어도 하나의 목표에 대해 결정될 수 있고, 그리고 상기 가장 유용한 궤적 모델은 상기 다중 기동들과 각각 연관된 부분 궤적 모델들에 기초하여 해당 목표에 대해 결정될 수 있다.

각각의 부분 궤적 모델은 하나 이상의 타겟 움직임 값을 포함할 수 있고, 상기 가장 유용한 궤적 모델의 미래 부분의 하나 이상의 움직임 값은 움직임 평활화를 상기 타겟 움직임 값에 적용함으로써 결정될 수 있다.

각 목표에 대한 예측된 궤적 모델은 해당 목표에 대한 단일 예측된 궤적일 수 있다.

각 목표에 대한 가장 유용한 궤적 모델은 단일의 가장 유용한 궤적일 수 있다.

각 기동에 대한 부분 궤적 모델은 해당 기동에 대해 가장 가능성이 높은 부분 궤적일 수 있다.

정의된 비용 함수는, 각 목표에 대한 예측된 궤적 모델 및 가장 유용한 궤적 모델 모두에 적용되어 상기 궤적 모델들의 각 비용을 결정하고, 상기 비교는 이러한 비용들을 비교하는 것을 포함한다.

상기 비용 함수는, 안전하지 않은 궤적들에 불이익을 주는 동안 감소된 주행 시간을 보상할 수 있다.

상기 비용 함수는 또한 편안함의 부족에 불이익을 줄 수 있다.

상기 외부 에이전트의 예상되는 행동은 상기 목표들의 결정된 가능성에 기초하여 이용 가능한 목표들의 세트로부터 하나의 목표를 샘플링함으로써 시뮬레이션될 수 있다.

상이한 목표 분포들이 상이한 기동들 또는 기동 시퀀스들에 대해 결정되고, 그리고 외부 에이전트의 예상되는 행동은 기동 분포에 기초하여 가능한 기동들의 세트로부터 하나의 기동 또는 기동 시퀀스를 샘플링하고, 이후, 해당 기동 또는 기동 시퀀스에 대해 결정된 목표 분포에 기초하여 이용 가능한 목표들의 세트로부터 목표를 샘플링함으로써 시뮬레이션될 수 있다.

상기 기동 분포는 기동 레벨에서 역 계획을 사용하여 결정될 수 있고, 상기 역 계획은: 가능한 기동들 각각에 대해, 예측된 궤적 모델을 결정하는 것과; 그리고 상기 외부 행위자의 관찰된 추적을 상기 가능한 기동들 각각에 대한 예측된 궤적 모델과 비교하여 해당 기동의 가능성을 결정하기 것을 포함할 수 있다.

상기 트리 검색 알고리즘은 상이한 샘플링된 목표들을 갖는 다중 구성된 게임 트리들에 대해 여러 번 수행될 수 있고, AV 기동들의 시퀀스는 상기 다중 구성된 게임 트리들 내의 경로들에 대한 통계적 분석에 기초하여 AV 플래너에 의해 결정될 수 있다.

객체 추적은, 상기 직면한 주행 시나리오에서 적어도 하나의 외부 행위자를 추적하고, 시간 간격에 걸쳐 상기 외부 행위자의 관찰된 추적을 결정하기 위해 상기 센서 입력들에 적용될 수 있고,

상기 역 계획 방법은:

상기 직면한 주행 시나리오에서 상기 외부 행위자에 대해 가능한 기동들의 세트를 결정하는 단계와;

상기 가능한 기동들 각각에 대해, 예측된 궤적 모델을 결정하는 단계와;

상기 외부 행위자의 관찰된 추적을 상기 가능한 기동들 각각에 대한 예측된 궤적 모델과 비교하여 해당 기동의 가능성을 결정하는 단계와; 그리고

상기 외부 행위자의 예상되는 행동을 시뮬레이션하기 위해 상기 기동들 중 적어도 하나의 결정된 가능성을 사용하는 단계를 포함할 수 있다.

각 기동에 대한 예측된 궤적 모델은 해당 기동과 관련된 단일 궤적일 수 있다.

각 기동에 대한 예측된 궤적 모델은 해당 기동과 관련된 예측된 궤적들의 분포일 수 있다.

본 발명의 제3 양태는 자율 차량(AV) 계획 방법을 제공하고, 이 방법은:

AV와 관련된 센서 입력들을 수신하는 단계와;

직면한 주행 시나리오를 결정하기 위해 상기 센서 입력들을 처리하는 단계와;

AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고

상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,

상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정되며, 그리고

상기 외부 에이전트의 예상되는 행동은 상기 센서 입력들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 목표 인식을 적용함으로써 시뮬레이션된다.

상기 목표 인식은, 이용 가능한 목표들의 세트: 상기 하나 이상의 관찰된 파라미터들에 기초한 상기 목표에 대한 가장 유용한 궤적 모델 및 상기 목표에 대한 최적의 궤적 모델 중 각 목표에 대해 계산하는 것을 포함할 수 있다.

상기 목표 인식은 확률적이며, 목표 분포는 각 목표에 대해 최적의 궤적 모델과 가장 유용한 궤적 모델을 비교함으로써 결정될 수 있다.

정의된 비용 함수는 각 목표에 대해 예측된 궤적 모델과 가장 유용한 궤적 모델 모두에 적용되어 해당 궤적 모델들의 각 비용을 결정하고, 해당 궤적 모델들은 해당 궤적 모델들의 비용들을 비교함으로써 비교될 수 있다.

다중 목표 분포들은 다중 가능한 기동들 또는 기동 시퀀스들에 대해 결정될 수 있다.

상기 예상되는 행동은 상기 목표 분포에 기초하여 이용 가능한 목표들의 세트로부터 샘플링된 목표에 기초하여 시뮬레이션될 수 있다.

상기 예상되는 행동은, 상기 외부 에이전트에 대해 결정된 기동 분포에 기초하여 가능한 기동들로부터 적어도 하나의 기동을 샘플링하고, 그 후 상기 샘플링된 기동에 대해 결정된 목표 분포로부터 상기 목표를 샘플링함으로써 시뮬레이션될 수 있다.

상기 트리 검색 알고리즘은 상이한 샘플링된 목표들을 갖는 다중 구성된 게임 트리들에 대해 여러 번 수행되고, AV 기동들의 시퀀스는 상기 다중 구성된 게임 트리들 내의 경로들에 대한 통계적 분석에 기초하여 AV 플래너에 의해 결정될 수 있다.

상기 목표 인식은 대안으로 목표 인식 결정 트리를 사용하여 수행될 수 있다.

본 발명의 다른 양태는 자율 차량을 구성하는 방법을 제공하고, 이 방법은:

훈련 시스템에서, 하나 이상의 주행 영역으로부터 캡처된 실제 주행 행동 데이터를 수신하는 단계와;

생성 모델 훈련에 사용하기 위해 실제 주행 행동의 예들을 추출하도록 상기 실제 주행 행동을 처리하는 단계와;

상기 추출된 주행 행동 예들을 사용하여 외부 에이전트의 하나 이상의 관찰 된 파라미터들에 기초하여 상기 외부 에이전트의 행동을 예측하도록 생성 행동 모델을 훈련시키는 단계와; 그리고

상기 훈련된 생성 행동 모델을 자율 차량의 전자 저장소에 저장하는 단계를 포함하고,

상기 자율 차량은 상기 생성 행동 모델을 사용하여 여기에 개시된 임의의 양태의 방법 또는 임의의 실시예를 구현하도록 구성된 자율 차량 플래너를 포함한다.

위에서 언급된 센서 입력은 AV 센서 시스템으로부터 수신된 센서 입력들을 포함할 수 있다. 추가로 또는 대안으로, 센서 입력들은 통신 링크를 통해 수신된 외부 캡처된 센서 입력들을 포함할 수 있다.

본 발명의 다른 양태는 자율 차량(AV) 계획 방법을 제공하고, 이 방법은:

AV와 관련된 센서 입력들을 수신하는 단계와;

직면한 주행 시나리오를 결정하기 위해 상기 AV와 관련된 센서 입력들을 처리하는 단계와;

AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고

상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,

상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정된다.

상기 특징들 중 임의의 것이 그 실시예들에서 구현될 수 있다.

본 발명의 추가 양태들은 본 명세서에 개시된 임의의 방법 단계들 실행하도록 구성된 실행 하드웨어를 포함하는 컴퓨터 시스템, 및 실행될 때 임의의 방법 단계들을 구현하도록 구성된 실행 가능한 명령어들을 포함하는 컴퓨터 프로그램을 제공한다.

또 다른 양태들은, 여기에 개시된 방법 단계들 중 임의의 것을 구현하도록 구성된 컴퓨터 시스템에 구현된 자율 차량(AV) 플래너와 자율 차량 플래너 및 자율 차량 플래너에 결합되고 자율 차량 플래너에 의해 생성된 제어 신호들에 응답하는 구동 메커니즘을 포함하는 자율 차량을 제공한다.

본 발명의 더 나은 이해를 위해, 그리고 동일한 실시예들이 어떻게 실행될 수 있는지 보여주기 위해, 다음의 도면들을 참조한다:
도 1은 자율 차량 컴퓨터 시스템에서 구현된 기능적 컴포넌트들을 보여주는 개략적인 기능적 블록 다이어그램을 도시한다.
도 2는 자율 차량 기동 계획에 사용될 수 있는 예시적인 게임 트리를 도시한다.
도 3은 실행될 일련의 기동들을 게임 트리로부터 선택하는데 사용될 수 있는 트리 검색 알고리즘에 대한 흐름도를 도시한다.
도 4는 생성적 행동 모델을 훈련하기 위한 훈련 시스템의 개략적인 기능 블록 다이어그램을 도시한다.
도 5a 내지 도 5c는 시뮬레이터에서 구현된 현재 기술들의 예들을 도시한다.
도 6은 역 계획 방법에 대한 흐름도를 도시한다.
도 7a 내지 도 7c는 역 계획의 특정 원칙을 예시로 도시한다.
도 8은 두 가지 가능한 기동들에 기반한 트리 검색의 예를 도시한다.
도 9는 3개 이상의 기동들에 기반한 트리 검색의 예를 도시한다.
도 10은 예시적인 역 계획 방법에 대한 흐름도를 도시한다.
도 11은 다른 목표 인식 방법에 대한 결정 트리를 도시한다.
도 12는 역 계획의 예측들을 통합하는 기동 계획 방법에 대한 개략적인 기능 블록 다이어그램을 도시한다.
도 13은 CCTV 데이터에서 학습된 궤적 모델의 예를 도시한다.
도 14a 내지 도 14c는 서술된 기술들이 구현될 수 있는 예시적인 시나리오들을 도시한다.
도 15는 다른 에이전트(들)에 대한 확률적 예측들과 함께 적용된 몬테카를로 트리 검색의 특정 원리들을 나타내는 상위 레벨의 순서도를 도시한다.
도 16은 CCTV로 모니터링되는 영역에서 정상적인 주행 행동을 모델링하는 공간적 마르코프 모델의 예를 도시한다.

본 발명의 예시적인 실시예들이 아래에 상세히 서술된다. 먼저 본 발명에 대한 몇 가지 유용한 맥락이 서술된다.

도 1은 AV(자아 차량)의 온-보드 컴퓨터 시스템(A1), 즉, 데이터 처리 컴포넌트(A2), 예측 컴포넌트(A4) 및 AV 플래너(A6)에 구현된 특정 기능 컴포넌트들의 매우 개략적인 기능 블록 다이어그램을 도시한다.

데이터 처리 컴포넌트(A2)는 AV의 온-보드 센서 시스템(A8)으로부터 센서 데이터를 수신한다. 온-보드 센서 시스템(A8)은 상이한 형태들을 취할 수 있지만, 일반적으로 이미지 캡처 디바이스들(카메라들), LiDAR 유닛들 등, 위성 위치 센서(들)(GPS 등), 움직임 센서(들)(가속도계들, 자이로스코프들 등) 등을 포함하여 주변 환경과 해당 환경 내 AV 및 기타 행위자들(차량들, 보행자들 등)의 상태에 대한 자세한 정보를 추출할 수 있는 풍부한 센서 데이터를 종합적으로 제공한다.

그러나, 본 기술들은 AV 자체의 온-보드 광학 센서들(이미지 캡처 디바이스들, 라이더 등)를 사용하여 캡처된 이미지 데이터 등을 사용하는데 제한되지 않는다. 방법은 외부에서 캡처된 센서 데이터, 예를 들어, AV 근처의 외부 이미지 캡처 유닛들에 의해 캡처된 CCTV 이미지들 등을 사용하여 대안적으로 또는 추가적으로 적용될 수 있다. 이 경우, 방법을 구현하는데 사용되는 센서 입력들 중 적어도 일부는 하나 이상의 무선 통신 링크를 통해 외부 센서 데이터 소스들로부터 AV에 의해 수신될 수 있다.

데이터 처리 시스템(A2)은 이러한 정보를 추출하기 위해 센서 데이터를 처리한다. 여기에는 일반적으로 다양한 형태들의 기계 학습(ML)/인공 지능(AI) 처리가 포함된다. 본 맥락에서 관련된 데이터 처리 시스템(A2)의 기능들은 위치 파악(블록 A10), 객체 검출(블록 A12) 및 객체 추적(블록 A14)을 포함한다.

주변 환경과 그 안의 AV 위치에 대한 인식을 제공하기 위해 위치 파악이 수행된다. 이를 위해 시각 및 지도 기반 위치 파악을 포함하여 다양한 위치 파악 기술들이 사용될 수 있다. 예를 들어, "차량 위치 파악(Vehicle Localization)"이라는 제목의 영국 특허 출원 번호 1812658.1이 참조되며, 이는 그 전체가 여기에 참조로 포함된다. 이것은 시각적 검출과 미리 결정된 지도 데이터의 조합을 사용하는 적절한 위치 파악 방법을 개시한다. 세분화는, 도로 및/또는 주변 환경의 기타 구조와 관련하여 지도 참조 프레임에서 AV 위치의 정확하고 강력한 추정치를 결정하기 위해, 시각적(이미지) 데이터에 적용되어 주변 도로 구조를 감지하고, 이를 HD(고화질)지도와 같은 미리 결정된 지도 데이터와 일치시키며, 이는 시각적 감지와 지도 기반 추론의 조합을 통해 시각적 데이터와 지도 데이터를 병합하여 결정된다. 위치 추정치를 결정하려면, 구조 매칭으로부터 결정된 개별 위치 추정은 입자 필터링 또는 이와 유사한 것을 사용하여 다른 위치 추정(들)(예를 들어, GPS)과 결합되어, 개별 위치 추정들의 정확도 변동들에 견고한 참조 프레임에서 AV에 대한 정확한 위치 추정을 제공한다. 지도에서 AV의 위치를 정확하게 파악한 후, 시각적으로 감지된 도로 구조는 미리 결정된 지도 데이터와 병합되어 차량의 현재 및 과거 주변 환경을 실시간 지도 형태로 포괄적으로 표현하고 지도 참조 프레임에서 AV 위치에 대한 정확하고 강력한 추정치를 제공한다. 본 문맥에서 용어 "지도 데이터"는 시각적(또는 다른 센서 기반) 감지를 미리 결정된 지도 데이터와 병합함으로써 유도된 라이브 지도의 지도 데이터를 포함하지만, 또한 미리 결정된 지도 데이터 또는 시각/센서 감지만으로 파생된 지도 데이터를 포함한다.

객체 검출은 센서 데이터에 적용되어 차량들, 보행자들 및 AV가 안전하게 반응할 수 있어야 하는 기타 외부 행위자들과 같은 환경 내 외부 객체들을 검출하고 위치를 파악한다. 이것은, 예를 들어, 3D 바운딩 박스 검출의 한 형태를 포함할 수 있으며, 여기서 환경 내 및/또는 자아 차량에 대한 물체의 위치, 방향 및 크기가 추정된다. 이것은, 예를 들어, RGBD(적색 녹색 청색 깊이), LiDAR 포인트 클라우드 등과 같은 (3D) 이미지 데이터에 적용될 수 있다. 이를 통해, 이러한 외부 행위자들의 위치 및 기타 물리적 속성들이 지도에서 결정될 수 있다.

객체 추적은 환경 내에서 검출된 객체들의 움직임을 추적하는데 사용된다. 결과는 객체 추적을 통해 시간이 지남이 따라 결정되는 각 객체의 관찰된 추적(τ)이다. 관찰된 추적 τ는 움직이는 객체의 이력으로, 시간이 지남에 따라 움직이는 객체의 경로를 캡처하고, 다른 시점에서 객체의 과거 속도, 가속도 등과 같은 다른 정보를 캡처할 수도 있다.

객체 검출 및 객체 추적과 함께 사용하면 외부 행위자들이 AV 주변의 결정된지도에서 포괄적으로 위치를 파악하고 추적할 수 있다.

객체 검출 및 객체 추적은 그 자체로 잘 알려져 있으며 공개적으로 이용 가능한 다양한 최신 모델들을 사용하여 현재 상황에서 수행될 수 있다.

위치 추적, 객체 검출 및 객체 추적의 조합을 통해, 데이터 처리 컴포넌트(A2)는, AV가 추적할 수 있었던 그러한 행위자들의 과거 흔적들과 뿐만 아니라 자아 차량의 주변 환경, 해당 환경 내의 외부 행위자들의 현재 상태(검출가능한 범위까지의 위치, 방향, 속도 등)에 대한 포괄적인 표현을 제공한다. 이것은 최신 위치 및 환경 인식을 제공하기 위해 실시간으로 지속적으로 업데이트된다.

예측 컴포넌트(A4)는, 이 정보를 예측 분석의 기초로 사용하여 AV 주변에서 외부 행위자들의 미래 행동에 대해 예측한다. 적합한 예측 방법론들의 예들이 아래에 설명되어 있다.

AV 플래너(A6)는 추출된 자아의 주변 환경과 그 안의 외부 에이전트들에 대한 정보를 AV 계획의 기초로 예측 컴포넌트(A4)가 제공하는 행동 예측들과 함께 사용한다. 즉, 예측 컴포넌트(A4)에 의한 예측 분석은 데이터 처리 컴포넌트에 의해 센서 데이터로부터 추출된 정보 위에 예측 정보의 층을 추가하고, 이는 AV 플래너(A6)에 의해 AV 계획 결정들의 기초로서 사용된다. 이것은 일반적으로 AV 플래너(A6)가 다양한 높은 레벨의 결정들을 내리고 높은 레벨의 결정들을 구현하는데 필요한 더 낮은 레벨들의 결정을 내리는 계층적 계획 프로세스의 일부이다. 최종 결과는 일련의 실시간 낮은 레벨의 행위 결정들이다. 이러한 결정들을 구현하기 위해, AV 플래너(A6)는 차량의 속도 및 방향을 (예를 들어, 스티어링, 브레이크, 가속, 기어 변경 등을 통해) 제어하기 위해 AV의 구동 매커니즘(A16)에 적어도 부분적으로 입력되는 제어 신호들을 생성한다. 시그널링과 같은 2차 액션들을 실행하기 위해 제어 신호들도 생성된다.

시나리오 추출 컴포넌트(A3)는 데이터 처리 컴포넌트(A2)의 출력들을 사용하여 자아 차량에 대한 직면한 주행 시나리오를 결정한다. 결정된 주행 시나리오는 캡처된 센서 데이터에서 추출된 주행 시나리오 파라미터들을 포함하며, 이는 AV에서 발생된 실제 시나리오를 간결하지만 실제 시뮬레이션들의 기초로 사용할 수 있을만큼 충분히 상세하게 표현한다. 이것은 그러한 시뮬레이션들의 기초로 사용할 수 있는 구조화된 시나리오 서술 언어로 공식화된다. 공식 시나리오 서술 언어로 된 시나리오 서술의 예는 부록 A에 제공된다.

시뮬레이터(A5)는 만난 주행 시나리오의 매개 변수를 수신하고 이러한 매개 변수를 기반으로 시뮬레이션을 실행할 수 있다. 이는 서로 다른 가정들하에서 직면한 주행 시나리오에서 일어날 수 있는 상황에 대한 시뮬레이션들이다. 이러한 시뮬레이션들은 AV 계획의 기초로 사용되며, 이는 AV 플래너(A6)가 정의된 목표를 실행하기 위해 (즉, 지도의 특정 위치에 도달하는 것과 같은 원하는 결과를 달성하기 위해) 직면한 주행 시나리오에서 취할 전체적인 최적의 기동 순서들을 결정하기 위한 목적으로 여러 시뮬레이션들을 실행한다. 아래 설명된 예들에서, 시뮬레이션들은 AV 플래너(A6)의 기동 선택 컴포넌트(A7)에 의해 실행되는 몬테카를로 트리 검색(MCTS)의 일부로 실행된다.

예측 컴포넌트(A4)의 기능은 시뮬레이션들의 일부로 실행될 예측된 외부 에이전트 행위들을 모델링하는 것이다. 즉, 예측된 행위가 기동 계획의 기반이 되는 시뮬레이션들에 통합될 수 있도록 직면한 주행 시나리오에서 외부 행위자들의 행위를 예측하기 위한 외부 에이전트 행위 모델을 실행하는 것이다.

기동 계획

자아 차량이 이동할 때 정의된 목표를 실행하기 위해 수행할 기동들을 계획해야 한다. 표시된 것처럼, 이는 의사 결정 프로세스를 위한 휴리스틱 검색 알고리즘인 몬테카를로 트리 검색을 사용하여 달성할 수 있다. 몬테카를로 트리 검색은 "온라인" 추론 프로세스이다. 즉, AV 플래너 A6가 실시간으로 실제 주행 결정들을 내리기 위해 수행한다.

MCTS는 게임 트리에 적용된다. 게임 트리는 게임 이론에서 비롯된 데이터 구조로, 이는 의미있는 점수를 받을 수 있는 상이한 가능한 결과들에 대한 체계적인 분석을 통해 합리적인 의사 결정을 위한 프레임 워크를 제공한다. 완전히 구성된 게임 트리는 한정된 수의 "움직임"으로 "게임"의 가능한 모든 결과를 캡처하고, 여기서 게임이라는 용어는 의사 결정 에이전트들 간의 전략적 상호 작용들(이동들)의 공식 모델을 의미하기 위해 수학적 의미에서 사용된다. 트리 검색 알고리즘은 정의된 보상 (점수) 함수와 관련하여 (전세계적으로) 최적인 게임 트리를 통한 특정 경로에 해당하는 일련의 움직임들을 결정하는 것을 목적으로 게임 트리에 적용할 수 있다.

MCTS는 게임 트리 검색을 위한 효율적인 확률 트리 검색 알고리즘이다. 게임 트리는 상이한 경로들을 탐색함에 따라 동적으로 구성된다. MCTS의 이점은 게임 트리를 통해 가능한 모든 경로를 완전히 탐색할 필요없이 점근적으로 정확한 근사치를 제공할 수 있다는 것이다. 즉, 가능한 모든 움직임들의 시퀀스를 고려해야 하는 것은 아니며, 이는 게임 트리를 완전히 구성할 필요가 없음을 의미한다. 이 경우 MCTS는 전 세계적으로 최적의 움직임들의 시퀀스를 찾을 수 있다고 보장하지 않지만, 알고리즘은 적절한 시간과 계산 리소스들이 주어지면 충분히 최적화된 솔루션으로 수렴될 것이다.

현재의 맥락에서, 본 발명의 목적을 위해 고유한 시퀀스들로 취급되는 개별적인 일련의 정렬된 기동들에 대한 변형이 있을 수 있음을 유의해야 한다. 예를 들어, 시간 tO와 t1 사이의 "차선 따르기" 및 t1과 t2 사이의 "차선 전환"은 시간 t0와 t1'(t1과 상이함) 사이에 "차선을 따르고" 그리고 t1'과 t2 사이의 차선을 전환하는 상이한 시퀀스로 간주될 수 있는데, 이는 차선 따르기에서 차선 전환으로의 변경이 상이한 각 시간들에서 발생하기 때문이다.

현재의 맥락에서, 움직임들을 기동들을 주도하고 있다. 자아 차량이 탐색할 필요가 있는 실제 주행 시나리오를 만나면, MCTS는 마주한 주행 시나리오에서 상이한 자아 기동들(즉, 자아 차량의 AV 플래너(A6)가 취할 수 있는 기동들)의 상이한 가능한 결과들에 대해 체계적으로 추론하는 수단으로 적용되고, 외부의 에이전트들(다른 차량들, 보행자들 등)의 예측된 행위를 고려한다. 이는, 위와 같이 캡처된 센서 데이터를 기반으로 마주한 주행 시나리오를 파라미터화하고 그리고 추출된 주행 시나리오 파라미터들 및 예측 컴포넌트(A4)에 의해 모델링된 외부 에이전트 행위를 기반으로 시뮬레이터(A5)에서 상이한 시뮬레이션들을 구동함으로써 달성된다.

MCTS와 같은 확률적 트리 검색 알고리즘을 사용하면 실시간 AV 의사 결정의 일부로 큰 게임 트리들에서도 충분히 최적의 기동들의 시퀀스를 찾을 수 있다. 현재 맥락에서는, 시나리오에 많은 에이전트가 있을 수 있으므로 게임 트리가 클 수 있다.

이러한 시뮬레이션들의 결과들은 게임 트리를 통해 가능한 상이한 경로들을 채점할 목적으로 정의된 보상 함수를 평가하는 데 사용되며, 결과적으로 보상 함수와 관련하여 MCTS 실행을 글로벌 최적 경로로 유도한다.

예시적인 게임 트리(D00)가 도 2에 도시된다.

게임 트리(D00)는 (편의상 시간 t=0으로 정의된) 마주친 주행 시나리오의 현재 상태(s0)를 나타내는 루트 노드(D02)를 갖는다. 이것은 자아 차량의 실제 현재 상태 및 마주친 주행 시나리오 내에서 외부 에이전트의 현재 상태(위치, 속도, 가속도 등)를 주변 환경, 특히 주변 도로 레이아웃/구조와 관련하여 캡처한다.

MCT D00의 추가 노드는 미래의 상이한 시간들에서 자아 차량의 동작에 대한 다양한 가정하에서 주행 시나리오의 예상된(예를 들어, 예측된, 미래) 상태들을 나타낸다. MCT D00의 구조를 통해 AV 플래너(A6)는, 자아 차량이 주어진 기동들의 시퀀스를 수행할 경우 주행 시나리오에서 일어날 수 있는 일을 추론할 수 있다.

이러한 추론을 용이하게 하기 위해, MCT D00은 다음과 같이 구성된다.

가능한 기동들은 몬테 카를로 트리 D00의 에지들로 표시된다. 자아 차량의 가능한 기동들은 현재 상태 s₀ 및 실행될 정의된 목표를 고려하여 가정된다.

루트 노드(D02) 이외의 각 노드는 다른 노드(부모 노드)의 자식 노드이며, 주행 시나리오의 예상 상태를 나타낸다. 예상된 상태는 이제 설명되는 바와 같이 특정 세트의 관련 가정하에 시뮬레이터(A5)에서 실행되는 마주친 주행 시나리오의 시뮬레이션에 기초하여 각각의 그러한 노드에 대해 결정된다.

각 부모 노드에서 해당 자식 노드까지 에지가 도시된다. 각 부모-자식 노드 쌍 사이의 에지는 부모 노드에 의해 표현된 주행 시나리오의 상태(시간 t)에서 AV 플래너(A6)가 취할 수 있는 대응하는 기동을 나타낸다. 차례로, 자식 노드는 이 기동이 간격 △t 동안 수행되는 경우 주행 시나리오의 예상 상태(시간 t+△t)를 나타낸다.

각 자식 노드의 예측된 주행 시나리오 상태는 주행 시나리오의 적절한 시뮬레이션을 기반으로 부모 노드가 나타내는 주행 시나리오 상태를 업데이트하여 결정된다. 주행 시나리오 시뮬레이션은, 추출된 주행 시나리오 설명 파라미터들; 부모 상태(이는 예를 들어 시뮬레이션의 시작 상태로 사용될 수 있음); 부모 노드와 자식 노드 사이의 대응하는 기동(성능은 시간 t와 t+△t 사이에 시뮬레이션됨); 및 시간 t와 t+△t 사이의 시뮬레이션된 외부 에이전트 행동(예측 컴포넌트(A4)에 의해 모델링됨)에 기초하여 실행된다.

간격 △t에서 자아 차량에 의한 해당 기동의 성능은, 부모 노드가 나타내는 주행 시나리오의 상태, 해당 시간 간격 △t의 외부 에이전트 행동 및 수행할 기동을 고려하여 AV 플래너(A6)가 실제 생활에서 취할 행동을 시뮬레이션하거나 "롤 아웃(rolling out)"함으로써 시뮬레이션된다.

자아 차량에 의한 기동의 성능은 특정 상태에서 문제의 기동을 수행하기 위해 학습되었거나 달리 결정된 "행동 정책(action policy)"을 사용하여 시뮬레이션할 수 있다. 행동 정책은 또한 AV 플래너(A6)에 의해 실제 세계에서 그 기동을 수행하기 위한 기초로 사용된다. 행동 정책은, 예를 들어, 강화 학습(reinforcement learning: RL)을 통해 "오프라인(offline)"으로 학습할 수 있다. 예를 들어, "자율 차량 기동(Autonomous Vehicle Manoeuvers)"이라는 제목의 영국 특허 출원 번호 1816852.6이 참조되며, 이는 그 전체가 여기에 참조로 포함된다. 이것은 관찰된 주행 행동 데이터로부터 훈련 시나리오가 결정되는 기동 학습을 위한 프레임 워크를 개시한다.

표시된 바와 같이, 외부 에이전트 행동은 예측 컴포넌트(A4)의 외부 에이전트 행동 모델을 실행하여 시뮬레이션된다. 적절한 행동 시뮬레이션 모델의 예들은 나중에 서술된다.

예를 들어, 도 2는 루트 노드(D02)에서 루트 노드의 3개의 직접 자식 노드들(각각 D06a-c 레이블이 지정됨)까지의 에지들(D04a-c)을 도시한다. 이들 에지 (D04a-c) 각각은 그들이 확장하는 노드(이 경우 루트 노드(D02))의 주행 시나리오의 상태 s₀에서 수행될 수 있는 상이한 기동을 나타낸다. 자식 노드들 각각은 s₀ 상태에서 시작하여 자아 차량이 해당 기동을 수행하는 경우 예측되는 주행 시나리오의 후속 상태(각각 s_1A, s_1B, s_1C)를 나타낸다.

예를 들어, 에지들(D04a-c)은 부모 상태 s₀에 대한 다중 차선 주행 시나리오에서 "차선 따르기(follow lane)", "좌측 차선 전환(switch lane left)" 및 "우측 차선 전환(switch lane right)"에 각각 대응할 수 있다. 상태 s₀에서 자아 차량은 현재 차선에 있다 - 적용 가능한 시간 간격 △t 동안 현재 차선을 유지하기 위해 후속 차선 기동이 수행된다; 차선 좌/우 전환은 각각 현재 차선의 좌/우 차선으로 이동을 시도하기 위해 수행된다. 상태들 s_1A, s_1B, s_1C는 관련 시간 간격 동안 외부 에이전트 행동을 고려하여 관련 기동 따라 부모 상태 s₀를 진행하여 획득된다.

적용할 수 있는 다른 예시적인 기동들은 (예를 들어, 원형 교차로를 탐색할 때) 감속, 계속 및 나가기가 있다.

이해되는 바와 같이, 트리 아래에 있는 노드들의 주행 시나리오 상태는 각각의 부모 상태들에서 시작하여 정확히 동일한 방식으로 획득된다.

특정 노드들은 종료(터미널) 노드들, 즉, 도 2의 노드들(D08 및 D10)과 같이 자식이 없는 노드이다. 이것은 "최종 상태"를 나타내고, 넓은 의미에서 자아 차량이 정의된 목표(성공)를 성공적으로 실행한 지점 또는 정의된 목표가 실패한 것으로 결정된 지점에 해당한다. 실패는 상황들에 따라 다양하게 정의될 수 있으나, 예를 들어, 차량이 목표를 중단하도록 강요당함; 차량이 불충분한 진행을 갖는다고 결정됨; 그리고 차량이 충돌하거나 또는 안전상의 이유로 고장이 난 것 등을 포함할 수 있다. 상황에 따라, 루트 노드(D02)에서 시작하여, 종료 노드에 도달하기 위해 기동 또는 일련의 기동들이 필요할 수 있다.

선택적으로, 최종 목표는 두 개 이상의 중간 목표들로 세분화될 수 있으며, 이는 최종 목표가 너무 멀 때 적합할 수 있다. 이러한 맥락에서, 각 중간 목표는 중간 목표의 최종 상태들을 나타내는 종료 노드들을 갖는 자체 게임 트리를 기반으로 실행될 수 있다(그러나 반드시 최종 목표의 최종 상태는 아님).

게임 트리(D00)는, 게임 트리(D00)를 통한 모든 가능한 경로가 한정된 수의 움직임들 후에 종료 노드에서 결국 종료된다는 점에서 한정된 트리이다.

각 종료 노드에는 보상 함수에 따라 점수(보상)가 할당되며, 이는 그것이 나타내는 결과의 만족도를 나타낸다. 이것은 성공과 실패에 대해 각각 2개의 점수를 갖는 간단한 이진 체계일 수 있으며, 더 풍부한 점수 매커니즘이 적절하게 적용될 수 있다. 예를 들어, 성공적인 결과들은, 짧은 시간 내에 도달하거나 상황에 적합한 기준에 따라 더 바람직한 경우 더 높은 점수를 받을 수 있다. 게임 트리를 통해 가능한 각 경로에 할당된 점수는 단순히 종료 노드에 할당된 점수이다.

보상은 반드시 터미널 상태에서만 제공되는 것은 아니다. 고려되는 각 경로에는 보상 함수에 따라 점수(보상)가 할당되며, 이는 그것이 나타내는 결과의 만족도를 나타낸다. 이것은 성공과 실패에 대해 각각 2개의 점수들을 갖는 간단한 이진 체계일 수 있으며, 더 풍부한 점수 매커니즘이 적절하게 적용될 수 있다. 예를 들어, 성공적인 결과들은 짧은 시간 내에 도달하거나 상황에 적합한 기준에 따라 더 바람직한 경우 더 높은 점수를 받을 수 있다.

본 예에서, 게임은 각각의 에지가 자아 차량의 기동에 대응한다는 점에서 싱글 플레이어 모델이다. 외부 에이전트들의 행동들은 적용 가능한 부모 노드에서 적용 가능한 자식 노드로 이동할 때 발생하는 상태 변경들의 일부로 캡처된다. 이 방법은 다른 에이전트들이 할 수 있는 작업을 롤 아웃하지만, 다른 에이전트들이 자아 차량에 대해 가정된 행동에 어떻게 반응할 수 있는지를 반드시 그 롤아웃에 통합하지는 않는다(그러나 둘 다 제외되지는 않는다). 즉, 생성 행동은 자아 차량과 그 주변(주행 컨텍스트, 예를 들어, 도로 레이아웃)에 대한 외부 행위자의 반응을 모델링할 수 있지만, 더 간단한 모델로 수용 가능한 결과들을 얻을 수 있기 때문에 외부 행위자에 의한 높은 레벨의 의사 결정을 모델링할 필요는 없다. 그러나 현재의 기술은 외부 행위자(예를 들어, 역 계획)에 의한 높은 레벨의 계획 모델을 통합하도록 확장될 수 있다.

가능한(즉, 현실적으로 달성 가능한) 기동들로만 가설을 세울 수 있다. 예를 들어, 차량이 T 교차로(부모 상태에 해당)와 관련된 특정 위치에 있는 경우, 정지, 좌회전, 우회전의 세 가지 가능한 기동들이 있을 수 있지만 계속 직진하는 것은 선택 사항이 아니다.

다른 예로서, 다중 차선 도로에서 이용 가능한 기동들은 차선을 따르고 차선을 전환할 수 있다. MCTS는 차선 변경 기동을 시작하는 것이 안전할 때까지 차량이 후속 차선 기동을 유지하도록 이러한 기동 순서들을 지정하는 데 사용된다.

이 모델은 차량들이 현실에서 어떻게 행동할 수 있는지에 대한 이해 수준을 통합할 수 있다. 예를 들어, 차량의 한 가지 한계는 그 자리에서 회전할 수 없다는 것이다. 따라서 불가능한 차량 행동들을 요구하는 모든 기동들은 가정되지 않는다.

게임 트리(D00)를 통해 최적의 경로를 식별하는 한 가지 방법은 가능한 모든 종료 노드의 점수를 평가하고 점수가 가장 높은 경로를 선택하는 것이다. 그러나 실제로는 특히 실시간으로 불가능할 수 있다.

이러한 상황에서 MCTS와 같은 확률적 트리 검색을 사용하면 적절한 양의 컴퓨팅 리소스들을 사용하여 합리적인 시간 내에 최적에 적어도 충분히 가까운 경로를 찾을 수 있다.

도 8은 주어진 목표에 대해 2개의 가능한 기동들이 있을 때 사용될 수 있는 MCT(800)의 간단한 예를 도시한다. 예를 들어, 목표는 곁길에서 특정 방향으로 교통 흐름에 합류하는 것일 수 있다. 이 예에서 AV는 도로에 합류하기 위해 좌회전해야 한다. 두 도로가 모두 단일 차선인 경우, AV가 구현할 수 있는 두 가지 가능한 기동들은 정지하거나 좌회전하는 것이다. 이는 차량이 "정지"에서 좌회전으로 변경되는 시기에 따라 여러 가지 가능한 기동 시퀀스들 - 예를 들어, (정지, 정지, 회전, 회전, ...) 대 (정지, 정지, 정지, 회전, ...) 등등을 발생시킨다.

AV의 현재 상태 s₀는 AV가 교차점에 접근할 때의 상태이다. 이것은 시간 t₀에서 루트 노드(802)에 의해 표현된다. AV는 교차로에서 멈추거나 도로에서 좌회전할 수 있다. 이러한 두 가지 가능한 기동들은 각각 에지들(804a 및 804b)로 표시된다.

주요 도로에 합류하는 목표를 달성하기 위해, AV는 좌측 에지(804b)로 회전하는 기동을 해야한다. 하지만, 이것은 언제든지 구현될 수 있다. MCT(800)는 5개의 시간 간격 △t 각각 후에 AV의 예측된 상태들을 보여 주지만, 더 많거나 적은 시간 간격이 고려될 수 있음을 이해할 수 있을 것이다. 상태들이 결정되는 시간 간격들은 도 8의 MCT에서 동일하게 도시되지만, 각 반복의 시간 간격들은 다를 수 있음을 알 수 있다.

AV는 s₀ 상태에서 시작된다. 에지(804b)를 따라 곧바로 주요 도로로 좌회전하기로 선택하면, 예측 상태는 자식 노드(806b)로 표시되는 s_1B이다. AV가 주요 도로에 합류했기 때문에 이것은 종결 노드이다. 상태 s_1B가 AV에 대한 안전한 상태이면, 종료 노드(806b)는 성공이다. 그러나 상태 s_1B가 안전하지 않은 경우, 예를 들어 AV가 외부 에이전트와 충돌했거나 가까워지면, 종료 노드(806b)는 실패이다.

대안적으로, t₀에서, AV는 에지(804a)를 따르는 정지 기동을 구현할 수 있다. 따라서, 결과 예측 상태 s_1A는 주요 도로와의 교차점에서 정지된 AV에 해당한다. 그 다음, AV는 시간 t₀+△t에서 좌회전 기동을 구현할지, 에지(804b)를 취할 것인지 또는 정지 상태를 유지하여 에지(804a)를 취할 것인지를 결정해야 한다.

다시, 이것은 주요 도로의 AV에 대응하는 상태 S_2B를 갖는 하나의 종료 노드(810b)와 AV가 주요 도로에 합류하지 않았기 때문에 종료 노드가 아닌 하나의 자식 노드(810a)를 초래한다. 이것은 각 추가 시간 단계에 대해 반복되며, 경로는 주요 도로에 합류한 AV에 해당하는 상태로 종료된다. 이러한 상태들 중 일부는 실패하는 반면, 다른 상태들은 성공한다. 그런 다음 구성된 MCT로부터 최적의 경로를 찾는다. 도 9는 2개의 차선이 있는 도로로부터 원형 교차로에 접근하는 AV에 대한 예시적인 MCT를 도시한다. 도 5a 내지 5c는 이러한 시나리오를 도시한다(아래 참조).

목표는 AV가 원형 교차로에 합류하는 것이다. 초기 상태 s₀는 왼쪽 차선에서 원형 교차로에 접근하는 AV를 포함한다. AV는 정지, 차선 따르기, 오른쪽으로 전환의 세 가지 가능한 기동들을 수행할 수 있다. 이 3개의 기동들은 각각 에지들(904a, 904b, 904c)로 표시된다. 결과 상태들 s_1A, s_1B 및 s_1C는 각각 원형 교차로와의 교차점에서 정차하거나, 현재 차선에서 원형 교차로에 합류하거나 또는 도로의 오른쪽 차선으로 전환하는 AV에 해당한다.

AV가 에지(904b)를 따르는 경우, 결과 상태 s_1B는 종료 노드(906b)이다. AV가 원형 교차로에 합류했기 때문이다. 종료 노드(906b)는 성공적인 노드일 수도 있고 아닐 수도 있다.

AV가 에지(904c)를 따라 오른쪽으로 이동하는 기동을 구현하면, AV는 도로의 오른쪽 차선으로 들어간다. 이후, AV는 앞으로 계속 가거나(에지(908b)) 또는 정지(에지(908a))하는 옵션을 갖는다. 계속해서 전진함으로써, AV는 원형 교차로에 합류하여, 경로는 종료 노드(910b)로 종료된다. 그러나 AV가 정지하면, AV는 다음 시간 간격에서 정지 또는 차선 따라 가기(즉, 오른쪽 차선에서 원형 교차로에 합류)의 기동을 구현할 수 있다.

AV가 에지(904a)를 따라 현재 상태 s₀에서 정지 기동을 구현하면, 세 가지 기동들인 정지, 차선 따르기, 및 우측으로 이동 중 하나를 다시 구현할 수 있는 옵션을 갖는다.

후속 차선 기동이 구현될 때마다, AV가 원형 교차로에 합류했기 때문에 종료 노드가 생성된다. 오른쪽으로 이동하는 기동이 구현되면, 오른쪽으로 이동하는 기동은 다음 반복에서 구현할 수 없으므로 자식 노드들의 수가 하나씩 감소한다. 정지 기동이 구현되면 3개의 기동들 모두 가능하다. 이러한 방식으로 가능한 모든 경로들에 대해 MCT를 구성할 수 있다. MCT가 구성되면 최적의 경로를 찾는다.

위에서 언급했듯이, 충분히 최적의 솔루션을 찾기 위해 MCT들을 완전히 구성할 필요는 없다.

도 3은 도 2의 게임 트리(D00)에서 수행될 수 있는 예시적인 MCTS 알고리즘에 대한 흐름도를 도시한다. MCTS 방법 자체가 알려져 있으므로, 관련 단계들은 현재 맥락에서 MCTS의 적용을 입증하기 위해 간략하게 서술된다.

MCTS는 고려중인 종료 노드들로부터 보상의 "역 전파(backpropagation)" 형태로 간주될 수 있는 확률적 계산을 기반으로 반복적으로 작동한다(이는 신경 네트워크들에서 역 전파에 사용되는 체인 규칙과 상이한 확률적 계산이다).

게임 트리(D00)는 MCTS가 수행될 때 동적으로 구성되며 실제로는 부분적으로만 구성될 것이다. 새로운 상태가 발생할 때마다 노드들이 추가되고 해당 상태에서 차량이 수행할 수 있는 가능한 기동들이 가정된다. 이것은 종료 노드에 도달할 때까지 계속된다.

각 반복은 처음에 루트 노드(D02)를 선택하는 것부터 시작하여 기존 트리를 순회하여 시작된다(단계 E0). 선택된 노드들은 방문한 것으로 표시되고(E2), 루트 노드에서 종료 노드까지 게임 트리(D00)을 통한 단일 경로가 시도된다(E4). 이는 위에서 서술한 것처럼, 종료 노드에 도달할 때까지 주행 시나리오의 상태(루트 노드 상태에서 시작)의 연속적인 변경을 결정하기 위해 시뮬레이션들을 실행하는 것을 의미한다. 확장은 무작위로 지정된다. 즉, 기동이 무작위로 선택되고 새 노드가 트리에 추가된다. 새로운 노드가 종료가 아닌 경우, 롤 아웃이 종료 노드로 시뮬레이션된다. 롤아웃은 또한 무작위화된다. 즉, 리프 노드(leaf node)에서 시작하여 터미널 노드로 진행하기 위해 기동들이 무작위로 선택된다. 이후, 반복은 위와 같이 점수가 매겨지고 해당 점수에 대한 정보는 방문한 노드들를 통해 다시 전파된다(E6). 다음으로, 방문하지 않은 노드가 선택되고(E8), 프로세스는 새로 선택된 노드로 단계 E2부터 반복된다.

각 반복은 처음에 루트 노드(D02)의 선택으로 시작하여 이전에 방문한 적이 없는 노드를 "방문(visiting)"함으로써 시작될 수 있다(단계 E0). 선택된 노드는 방문한 것으로 표시되고(E2), 선택된 노드에서 종료 노드까지 게임 트리(D00)을 통한 단일 경로가 확장된다(E4). 이는 위에서 서술된 것처럼, 종료 노드에 도달할 때까지 주행 시나리오의 상태(선택된 노드의 상태에서 시작함)의 연속적인 변경들을 결정하기 위해 시뮬레이션들을 실행하는 것을 의미한다. 경로 확장은 무작위화된다. 즉, 현재 선택된 노드에서 시작하여 종료 노드로 진행하기 위해 기동들이 무작위로 선택된다. 종료 노드는 위와 같이 점수가 매겨지고 해당 점수에 대한 정보는 확장된 경로(E6)를 통해 다시 전파된다(참고: 확장된 경로를 따른 노드들은 방문한 것으로 표시되지 않음). 다음으로, 방문하지 않은 노드가 선택되고(E8), 프로세스는 새로 선택된 노드로 단계 E2부터 반복된다. 방문하지 않은 노드는 지금까지 게임 트리를 통해 역 전파된 점수 정보를 기반으로 선택되며, 이는 (시간이 지남에 따라) 노드 선택을 보다 유망한 결과로 편향시키는 방식으로, 원치 않는 수렴의 위험을 단순한 로컬 최적화로 완화할 수 있는 충분한 레벨의 탐색을 계속 장려한다.

프로세스는 종료될 때까지 계속 반복된다(E10). 이는 예를 들어 특정 시간 제한에 도달했거나 특정 반복 횟수가 실행된 경우 등이 될 수 있다. MCTS의 장점은 언제든지 종료할 수 있다는 것이다. 실행 시간이 길수록 평균적으로 전 세계적으로 최적의 솔루션에 가까워진다.

종료시, AV 플래너(A6)는, 가장 유망하다고 판단되는 확장된 경로들 중 하나를 선택하고 그리고 실제 주행 시나리오에서 발생하는 기동들의 해당 시퀀스를 실행하기 위해 AV를 제어하기 위한 제어 신호들(E12)을 생성한다.

가장 유망한 경로는 최대 점수를 가진 경로일 수 있다. 그러나 점수 이외의 정보도 고려될 수 있다(아래 참조).

AV에 의해 발생하는 실제 주행 시나리오에서, 일반적으로 도로 레이아웃이 고정되고 알려지지만 시나리오의 다른 차량들/행위자들은 동적이다. 따라서 시간이 지남에 따라 MCTS 절차가 실행됨에 따라 새로운 행위자들이 감지될 수 있다. 진행중인 MCTS 절차 중에 새로운 행위자가 감지되면, 기존 노드와 구성된 에지들을 포함하는 구성된 게임 트리의 구조가 유지된다. 그러나 시뮬레이션들은 새로 감지된 에이전트(들)의 시뮬레이션된 행위를 고려하여 보상 함수들을 다시 계산하기 위해 기존 게임 트리에서 다시 실행된다.

그림 5a는 시뮬레이터의 원형 교차로 주행 시나리오에 적용된 MCTS 프로세스의 예를 도시한다. 자아 차량은 참조 번호 500으로 표시되며, 원형 교차로에 다른 차량(502)이 있는 경우 원형 교차로 시나리오에서 안전하게 계획할 필요가 있다. 이것은 기동들 "감속(slowdown)", "차선 따르기(follow lane)" 및 "오른쪽 차선으로 전환(switch to right lane)"(오른쪽으로 전환)의 충분한 광학적 시퀀스를 선택함으로써 수행한다.

도 5b는 MCTS에 의해 상이한 기동 시퀀스들이 어떻게 평가되는지 도시한다.

도 5c는 원형 교차로에 진입하기 위해 기동 시퀀스를 선택하고 실행하는 자아 차량(500)을 도시한다. 이후, 프로세스를 반복하여 원형 교차로에서 나가기 위한 기동 시퀀스를 결정하고 실행한다.

아래에 서술된 것처럼, MCTS는 다른 에이전트들의 행동에 대한 확률적 예측들로 구현할 수 있다. 예를 들어, 다음은 확률적 기동 감지와 확률적 목표 인식을 모두 고려한다. 확률적 예측들을 사용하면, 프로세스 시작시 관련 분포 또는 분포들을 샘플링하여 결정적 예측 또는 예측들(샘플들)의 세트를 효과적으로 얻는다. 이후, MCTS는 확률적 예측들로부터 샘플링된 상이한 결정적 예측들로 반복된다.

도 15는 확률적 예측들로 구현된 MTCS의 상위 레벨 순서도를 도시한다.

단계 1502에서, 외부 행위자에 대해 적어도 하나의 확률적 예측이 결정된다. 이것은, 예를 들어 에이전트 P(M|τ)의 가능한 기동들에 대한 분포 및/또는 가능한 목표들 P(G|0)에 대한 분포(아래 참조)가 될 수 있다.

표기법 0은 관측들의 세트를 의미한다. 관측치 0은 관측된 추적 τ 자체(0 = τ)일 수 있지만, 0이 이 점에서 반드시 제한되는 것은 아니다. 예를 들어, 일 구현에서, 관측치 0은 에이전트의 기동 M_j를 포함할 수 있으며, 이 경우 표기법 P(G|M_j)가 사용될 수 있다(관측치 0이 추가 파라미터들을 포함할 수 있으므로 속기일 수 있음)(추적 τ에서 기동들이 추론될 수 있음에 유의).

단계 1504에서, 단계 1504의 분포(들)는 결정론적 예측(들)의 세트를 얻기 위해 샘플링된다. 예를 들어 R(M|τ)는 실제 현재 기동 M_j를 선택하기 위해 샘플링될 수 있고 그리고/또는 P(G|0)는 통계적으로 견고한 방식으로 실제 현재 목표를 선택하기 위해 샘플링될 수 있다(그 결과, 더 가능성 있는 목표들, 기동들 등이 선택될 가능성이 더 높다).

단계 1506에서, MCTS 프로세스는 전술한 바와 같이 전체적으로 수행된다. 이것은 트리를 탐색하기 위해 MCTS 프로세스 내에서 수행되는 반복 단계들과 구별하기 위해 MCTS 프로세스의 "슈퍼 반복(super-iteration)"으로 반복될 수 있다.

MCTS의 다중 슈퍼 반복들은 확률적 예측들의 상이한 샘플링으로, 예를 들어, 동일한 목표/기동 분포들 P(G|0)/P(M|T)로부터 단계 1504에서 샘플링된 상이한 목표들/기동들로 반복된다. 즉, 확률적 예측(들)은 각 슈퍼 반복에 대해 단계 1504에서 재샘플링된다. 이 반복은 정지 조건들의 세트가 충족될 때까지(1508) - 예를 들어, 시간 제한에 도달하거나 특정 수의 슈퍼 반복들이 수행될 때까지 수행되는 것으로 도시된다.

MCTS 프로세스의 모든 슈퍼 반복들을 완료한 후, 모든 결과들의 통계 분석은 자아 차량에 대한 가장 유망한 기동 시퀀스를 선택하기 위해 단계 1510에서 적용된다.

전체 결과들의 단계 1510에서 통계 분석은 MCTS의 각 슈퍼 반복에서 결정된 점수들을 고려한다. 그러나, 주어진 기동 시퀀스와 관련된 "신뢰도"와 같은 다른 정보도 고려할 수 있다. 신뢰도는 시뮬레이션을 통해 기동 시퀀스가 테스트된 정도를 반영한다. 예를 들어, 특정 기동 시퀀스가 MCTS 슈퍼 반복에서 높은 점수를 받았지만, 다른 슈퍼 반복들에서는 테스트되지 않았을 수 있다. 이 경우, 시퀀스는 점수가 높지만 신뢰도가 낮으며, 신뢰도가 높은 낮은 점수 기동 시퀀스(즉, 보다 광범위하게 테스트됨)를 선호하는 경우 무시될 수 있다.

외부 에이전트 행동 시뮬레이션

게임 트리(D00)가 구축됨에 따라 주행 시나리오 상태 변화들을 결정하기 위해서는 외부 행위자들의 미래 움직임을 예측할 필요가 있다. 언급한 바와 같이, 이러한 외부 에이전트 행동은 예측 컴포넌트(A4)에 의해 이러한 목적으로 모델링된다.

이러한 맥락에서 다양한 형태들의 생성 모델이 사용될 수 있다.

적합한 모델의 한 가지 예는 "역 플래너"이다. 예를 들어, "자율 차량 계획 및 예측(Autonomous Vehicle Planning and Prediction)"이라는 제목의 영국 특허 출원 번호 1816850.0이 참조되며, 이는 그 전체가 여기에 참조로 포함된다. 이것은 외부 에이전트 행동을 시뮬레이션하기 위해 현재 맥락에서 사용될 수 있는 역 플래너를 개시한다. 역 계획은 아래에서 서술된다.

에이전트는 반드시 동일한 방법을 사용하지는 않지만 차량과 동일한 레벨에서 계획을 수행한다고 가정할 수 있다.

예측을 위해 차량과 외부 에이전트들이 공유한다고 가정하는 지식이 지도이다.

기동 계획을 위한 MCTS가 목표 인식과 결합 될 수 있는 특정 메커니즘에 대한 추가적인 세부사항들은 역 계획의 서술 후 나중에 서술된다.

역 계획 컴포넌트(A24)는 도 1에서 예측 컴포넌트(A4)의 일부를 형성하는 것으로 도시된다. 역 계획 컴포넌트(A24)(역 플래너)는 나중에 서술하는 "역 계획"을 구현한다.

추가적으로 또는 대안적으로, 생성 모델은 CCTV(폐쇄 회로 텔레비전) 영상과 같은 실제 주행 행동 데이터를 사용하여 에이전트들의 미래 움직임들을 예측하도록 훈련될 수 있다.

그러한 예 중 하나는 신경 네트워크 기반 모델(또는 기타 학습 가능한 함수 근사치)로서, 에이전트가 움직일 가능성을 예측하기 위해 t₀ 이전의 짧은 시간 동안 외부 에이전트의 관찰된 추적과 같은 관찰자 파라미터(들)를 사용한다. 이것은 확률적 모델일 수도 있고 결정적일 수도 있다. 이러한 모델들은, 모델이 이전에 접하지 않은 주행 상황들(예를 들어, 알 수 없는 도로 레이아웃)에서 현실적인 행동을 생성하는 데 사용할 수 있으며, 적절하게 훈련된 경우 훈련 예시들에서 일반화하는 이러한 모델들의 능력을 활용한다.

또 다른 예는, 예를 들어 CCTY 영상을 기반으로 해당 주행 영역을 직접 관찰하여 파생된 알려진 주행 영역의 모델이다. 예를 들어, 도시 주행 상황들에서 복잡한/바쁜 교차로, 로터리 등과 같은 어려운 주행 영역들에 대한 모델들이 만들어질 수 있다. 그러한 모델 중 하나가 공간적 마르코프 모델로, 구동 영역이 그리드 셀들로 분할되고, 그리고 그리드 셀들에 대한 점유 확률들 및/또는 그리드 셀들 간의 전이 확률들은 장기 관찰을 통해 결정되며, 이를 통해 관찰된 매개 변수(들)에 기반하여 외부 에이전트 행동을 예측하는데 사용할 수 있다.

이들은 훈련된 행동 생성 모델들의 예들이다.

도 4를 참조하면, 생성 모델(F06)을 훈련하여 훈련 컴퓨터 시스템(F00)에서 외부 에이전트 행동을 오프라인으로 시뮬레이션할 수 있다. CCTV 데이터와 같은 실제 주행 행동 데이터(F01)는 훈련 시스템의 행동 추출 컴포넌트(F02)에서 수신되고, 이러한 행동 추출 컴포넌트(F02)는 훈련에 사용할 주행 행동의 예들을 추출하기 위해 데이터를 처리한다. 훈련 컴포넌트(F04)는 위에서 서술한 것처럼 관찰된 파라미터들(예를 들어, 관찰된 추적)을 기반으로 외부 차량 행동을 시뮬레이션하기 위해 생성 모델(F06)을 훈련하기 위해 이러한 예들을 사용한다. 훈련 컴포넌트(F04) 및 행동 추출 컴포넌트(F02)는 훈련 시스템(F00)(도시되지 않음)의 하나 이상의 프로세서에서 실행되는 훈련 시스템(F00)의 기능 컴포넌트들이다. 이러한 방식으로 생성 모델(F06)을 훈련시킨 후, 이를 자율 차량의 온보드 컴퓨터 시스템 AI의 전자 저장 장치로 전송하여 AV에 통합하여 예측 컴포넌트(A4)가 위의 기능들을 수행할 수 있도록 할 수 있다.

역 계획

정의된 목표를 안전하고 효과적으로 실행하기 위해 자아 차량이 취해야 할 일련의 기동, 행동 등을 결정하는 것과 같은 AV 계획 결정을 AV 플래너(A6)에서 지원하기 위해, 역 플래너(A24)는 근처의 외부 행위자들의 움직임을 예측하고, 이는 현재 문맥에서 에이전트로 지칭될 수 있다. 역 플래너(A24)는 위의 맥락에서 적용될 수 있는 생성적 행동 모델의 한 예이다.

역 계획은 외부 행위자의 현재 기동에 대한 확률적 예측을 하기 위해 기동 레벨에서 구현될 수 있다. 예를 들어, 역 플래너(A24)는, 추적 τ를 포함하는 (또는 파생된) 관련 관찰 세트가 주어지면, "차선 따르기", "차선 전환" 등과 같은 가용 기동들 M 세트에 대한 확률 분포 P(M|τ)를 예측할 수 있다. 기동 레벨에서의 역 계획은 (확률적) 기동 검출의 한 형태이다.

대안적으로 또는 추가적으로, 역 계획은 외부 행위자의 현재 목표에 대한 확률적 예측을 하기 위해 목표 레벨에서 구현될 수 있다. 예를 들어, 역 플래너(A24)는 이용 가능한 목표들 G의 세트에 대한 확률 분포 P(G|0)를 예측할 수 있다. 예를 들어, 좌회전 주행 시나리오에서, 목표는 "좌회전" 목표 또는 "계속 직진" 목표 (즉, 현재 도로에 남아 있고 좌회전하지 않음)가 될 수 있으며 적절한 목표 위치로 캡처된다. 목표 레벨에서의 역 계획은 (확률적) 목표 인식의 한 형태이다.

목표 인식 및 기동 검출은 일반적으로 다른 시간 척도들에서 작동할 것이다. 목표 인식은 일반적으로 기동 검출보다 미래의 더 긴 기간을 고려한다. 예를 들어, 기동 예측은 미래를 몇 초(예를 들어, 5초)로 볼 수 있는 반면, 목표 인식은 (상황에 따라) 이보다 더 앞서 볼 수 있다. 따라서, 목표 인식은 일반적으로 기동 인식보다 더 긴 궤적들(즉, 미래의 궤적들)을 고려한다.

예를 들어, 목표는 자아 차량이 지도상의 현재 위치로부터 도달하려고 시도하는 지도(즉, 지도 기준 프레임에서)의 원하는 위치(기준점)로 캡처될 수 있고, 만나는 도로 레이아웃과 관련하여 원하는 위치가 정의된다. 예를 들어, 원하는 위치는 특정 교차로, 차선 레이아웃, 원형 교차로 출구 등과 관련하여 정의될 수 있다. 주변 도로 레이아웃과 외부 행위자들을 감안할 때, 원하는 위치에 도달하여 해당 목표를 성공적으로 실행하기 위해 차량이 취할 수 있는 다양한 경로들/동작들이 있을 것이다. 자아 차량이 그렇게 하는 것, 예를 들어, 잘못 선택된 초기 행동들의 시퀀스는 차량이 원치 않는 원형 교차로 출구로 나가거나 그렇지 않으면 목표를 계속 실행하는 것이 안전하지 않을 때 외부 행위자의 행동으로 인해 목표를 중단하게 만들 수 있는 것을 막는 자아 차량 행동들도 있을 것이다. 외부 행위자들의 행동에 대한 신뢰할 수 있는 예측을 계획에 통합하면 AV 플래너(A6)가 안전하고 효과적으로 계획하여 중단된 목표들의 발생을 최소화할 수 있다.

목표 레벨에서 구현되면, 역 계획은 각 외부 에이전트에 대해 상이한 가능한 목표들을 가정한 다음 에이전트가 각 목표를 달성할 수 있는 방법과 각 궤적을 따를 가능성에 대한 궤적들을 생성한다. 기본 가정은 각 외부 에이전트가 생성 모델을 사용하여 예측할 수 있는 방식으로 작동할 것이라는 점이다.

본 맥락에서 역 계획은 AV 예측 컴포넌트(A4)에 의해 구현될 수 있는 특정 클래스의 예측 방법들을 지칭한다. 즉, 역 기획 방식은, 외부 행위자들이 예측 가능한 방식으로 계획한다고 가정하여 외부 행위자들 및 특히 다른 차량들의 행동을 예측하는 특별한 방법이다.

"역 계획"이라는 용어는 외부 행위자가 예측 가능한 방식으로 결정을 계획할 것이라는 기본 가정을 나타낸다. 좀 더 공식적으로는, 다른 차량이 가설을 세울 수 있는 생성 모델을 사용하여 계획하고 실행할 것이라는 가정이다.

이제 역 계획 방법이 방법에 대한 순서도를 보여주는 도 6을 참조하여 서술될 것이다. 이것은 목표 레벨의 역 계획을 고려하지만 기본 원칙들은 기동 레벨의 역 계획에도 동일하게 적용된다. 방법의 단계들은 역 플래너(A24)에 의해 실시간 또는 의사 실시간으로 반복적으로 수행되므로 AV 플래너(A6)가 항상 충분히 최신 예측을 사용할 수 있다. 이 방법은 데이터 처리 시스템(A2)에서 제공하는 정보, 즉, 주변 환경/도로 레이아웃, 환경 내의 다른 행위자들의 위치/상태, 객체 추적을 통해 관찰된 행위자들의 흔적에 관한 정보를 사용한다.

다음 단계들은 고려중인 하나 이상의 외부 행위자들(차량들, 보행자들, 자전거타는 사람들 등) 각각에 대해 수행되며, 이러한 행위자들은 다음 예들에서 AV 이외의 차량들이다.

단계 SB2(도 6)에서는, 문제의 다른 차량에 대해 가정된 목표들의 세트가 결정된다. 다른 차량이 현재 이러한 목표들 중 하나를 실행하고 있다고 가정하자. 적절한 가설 목표들의 세트를 결정하기 위해, 다른 차량 근처의 도로 레이아웃과 같은 주행 상황이 결정된다.

외부 에이전트 목표들은 일반적으로 지도를 기반으로 가정된다. 예를 들어, 도로 교차로, 원형 교차로 또는 지도에 표시된 기타 도로 레이아웃(주행 상황) 근처에 있는 외부 차량들의 세트가 있는 경우, 적절한 목표들은 도로 레이아웃만으로 가정할 수 있다(에이전트의 관찰된 과거 행동을 고려하지 않음). 예를 들어, 좌회전 교차로 근처에 일련의 외부 에이전트가 있는 경우, 가정된 목표들은 좌회전하고 계속 직진할 수 있다. 표시된 대로 이러한 목표들은 지도상의 적절한 목표 위치들(예를 들어, 참조 지점)을 참조하여 정의된다.

그러나 이용 가능한 목표는 다양한 방법들로 가정될 수 있다. 예를 들어, 관찰된 과거 행동(예를 들어, 시간 t 이전에 관찰된 추적)은 외부 에이전트 목표들을 가정할 때 고려될 수 있거나 또는 지도 기반 및 역사적 행동 기반 추론의 조합을 사용하여 목표를 가설할 수 있다.

과거의 행동이 이용 가능한 목표들을 가설하는데 사용되지 않는 경우에도, 그럼에도 불구하고 각 목표의 가능성을 결정하는 데 사용된다(P(G|0)는 에이전트 행동의 관찰들 0에 의존하기 때문이다).

가정된 목표들의 세트를 결정한 후, 각 목표에 대해 다음 단계들을 수행한다.

단계 SB4에서, 예상된 궤적 모델이 문제의 가정된 목표에 대해 결정된다. 예상된 궤적 모델은 특정 목표를 실행하고 있다는 가정하에 다른 차량의 향후 행동을 시뮬레이션하는 모델이다. 특히, 예상된 궤적 모델은, 다른 차량이 주어진 시간 △t 내에서(시간 t에서 시간 t + △t까지) 특정 경로 또는 경로들(궤적들)을 택할 가능성이 얼마인지를 나타내고, 이는 해당 기간 △t 동안 해당 목표를 실행한다고 가정한다. 표시된 바와 같이, 차량이 실행하는 목표는 지도에 기반한 종점에 의해 파라미터화될 수 있다. 예를 들어, 목표가 계속 직진하는 것(예를 들어, 좌회전이 아닌)이라면, 종점은 같은 차선에 있는 차량보다 앞서 설정된 거리(예를 들어, 40m)에 있는 도로의 한 지점일 수 있다. 대안으로, 예를 들어, 다중 차선 시나리오에서, 목표 위치는 특정 차선을 지정하지 않고 전방 도로를 따라 약간의 거리가 될 수 있다(자세한 내용은 아래 참조).

예상된 궤적 모델은 단순히 주어진 목표에 대한 (단일) 예측된 경로일 수 있지만, 현재 예시들에서는 해당 목표에 대한 예측된 경로 분포의 형태를 취한다. 예측된 경로 분포는 시간 t에서 외부 차량의 위치 r_t가 주어진 문제의 목표에 대해 n 개의 예측된 경로들의 개별 세트를 합성함으로써 현재 인스턴스의 각 목표에 대해 제공되며, 이에 의해 적어도 시간 간격 △t 동안 예측된 경로 분포를 제공한다.

예를 들어, 도 7a는 특정 외부 차량에 대해 예측된 바와 같이 목표들 G₁ 및 G₂에 대한 각각의 예측 경로 세트 R_G1, P_G2를 도시한다. 목표들 G₁, G₂는 지도의 지점들 또는 영역들이 될 수 있는 지도 기준 프레임에서 기준 위치들 R₁, R₂에 대해 각각 정의된다. 시간 t에서 외부 차량의 위치 r_t와 각 목표의 기준점들 R₁, R₂가 주어지면 예측 경로 세트 P_G1, P_G2가 목표 G₁, G₂에 대해 각각 합성된다.

이 예에서는 각 목표가 단일 기준점/영역에 대해 간단히 정의되지만, 이해되는 바와 같이, 목표들은 다른 방식으로, 예를 들어, 상황에 적합한 다수의 기준점들을 참조하여 정의될 수 있다. 일반적으로, 목표는 하나 이상의 목표 파라미터의 세트에 의해 정의되며, 이는 일반적으로 자율 주행의 맥락에서 지도 참조 프레임에 정의된다. 지도 참조 프레임의 참조 위치는 목표 파라미터의 한 예이며, 이러한 참조 위치들과 관련된 모든 서술은 다른 유형들의 목표 파라미터에도 동일하게 적용된다.

좌회전 예에 따라, "계속 직진" 목표를 위해 한 세트의 경로들이 생성되며, 이는 다른 차량이 "계속" 목표를 실행하는 경우 취할 수 있는 경로들이고, 그리고 "좌회전" 목표를 위해 다른 세트의 경로들이 생성되며, 이는 다른 차량이 "좌회전" 목표를 실행하는 경우 취할 수 있는 경로들이다.

생성 모델을 이러한 경로들을 합성하기 위해 사용될 수 있다. 기본 가정은 다른 차량이 이 모델로 계획하고 실행한다는 것이다. 이 모델은 (다른 차량들이 자아 차량과 동일한 방식으로 계획할 것이라는 가정하에) AV 플래너(A6) 자체에 해당할 수 있지만 AV의 자체 플래너와 상이할 수도 있다.

예를 들어, RRT(Rapidly Exploring Random Tree) 모델을 사용하여 각 목표에 대해 경로들을 합성할 수 있다. 그림 7A의 예에 따라, 각 목표 G₁, G₂에 대해 해당 목표에 대한 참조 위치(각각 R₁, R₂)와 외부 차량의 현재 위치 r₀을 기반으로 예측 경로들 공간(검색 공간)이 정의된다. 이후, 검색 공간을 무작위로 샘플링하여 (무작위화된 입력 파라미터들을 기반으로) n 개의 경로들의 세트와 각 경로의 가능성을 결정한다. 각 목표에 대해 n 개의 경로들을 시뮬레이션하기 위해, RRT의 관련 파라미터들이 n 번 무작위화되어 검색 공간에 대해 적절하게 편향된 n 개의 무작위 검색들을 수행한다.

예를 들어, "안전한 동작 계획을 위한 충돌 확률의 효율적인 계산"이라는 제목의 GB 특허 출원 번호 1803292.0(전체 내용이 여기에 참조로 포함됨)은, 역 계획을 구현하기 위해 현재 맥락에서 사용할 수 있는 RRT 모델을 개시한다. 주어진 궤적을 따라 충돌의 확률론적 위험이 계산되고 안전에 따라 후보 궤적들의 순위를 매기는데 사용된다. 이는 차례로 외부 차량이 해당 목표를 실행하기 위해 더 안전한 경로들을 취할 가능성이 더 높다는 가정하에 각 샘플링 경로의 가능성을 제공한다. 즉, 가정된 안전과의 관계를 기반으로 경로 확률들을 결정할 수 있다. 샘플링된 경로들 및 그 확률들은 궤적 모델의 한 예이다. 그러나, 이것은 적절한 생성 모델의 한 예일 뿐이며 생성된 모델의 다른 형태들도 사용할 수 있다. 대체 궤적 모델의 예는 나중에 서술된다.

이러한 예 중 하나는 관찰된 추적 및 실행될 목표가 주어진 경로 예측 모델 (예를 들어, 예측된 경로 또는 예측된 경로들의 분포)을 출력하도록 훈련된 신경 네트워크 기반 모델이다. 네트워크는 실제 주행 행동 예들을 기반으로 훈련된다. 예를 들어, 신경 네트워크는 도시 주행 환경에서 캡처된 CCTV(폐쇄 회로 텔레비전) 데이터의 큰 코퍼스에서 추출된 예들을 기반으로 훈련될 수 있다.

또 다른 예는 공간적 마르코프 모델(또는 유사한 모델)이며, 이는 충분한 시간 동안 주행 영역을 모니터링함으로써 특정 주행 영역에 대해 미리 결정될 수 있다(위 참조).

일반적으로, 역 플래너(A24)는 상이한 가설 목표들과 관련하여 추론할 수 있는 모든 모델이 될 수 있다.

단계 SB6에서, 기간 △t(즉, 시간 t와 t + △t 사이)에 걸쳐 실제로 관찰된 다른 차량의 추적은, 그 목표에 대한 가능성을 결정하기 위해 △t 동안 해당 목표와 관련된 경로들의 분포에 매칭된다.

예를 들어, 도 7b는 시간 t와 t + △t 사이에 해당 차량의 실제 관찰된 추적 τ를 보여준다. 실제 추적 τ를 각 목표 G₁, G₂ (도 7a)에 대한 예측 경로 분포와 일치시킴으로써, 각 목표 G1, G2의 가능성은 시간 간격 △t에 대해 확률적으로 결정될 수 있다. 이것은 소프트 매칭의 한 형태일 수 있다. 목표 가능성은 외부 차량의 관찰된 추적 τ를 고려하여 가정된 각 목표의 조건부 확률, 즉 p(G_i|τ)로 캡처될 수 있고, 이 확률 p(G_i|τ)은 관찰된 추적 τ가 주어졌을 때 시간 간격 △t 동안 외부 차량이 목표 G_i를 실행하고 있을 것으로 추정되는 확률이다.

즉, 역 플래너(A24)는, 다른 차량이 해당 기간 동안 해당 목표를 실행했다고 가정하에, 가정된 각 목표에 대해 다른 차량이 시간 간격 △t에서 취할 수 있는 가능한 경로들의 세트와 각 경로의 가능성(즉, 다른 차량이 해당 목표를 실행했다면 시간 간격 △t 동안 수행했을 수 있는 작업)을 예측하는데 사용된다. 그런 다음, 해당 기간 내에 다른 차량의 실제 추적(즉, 다른 차량이 실제로 수행한 작업)과 비교하여 △t 기간 동안 각 목표의 가능성을 결정한다.

도 7c를 참조하면, 관찰된 추적 τ가 주어지면 각 목표의 가능성이 알려져 있으므로, 관찰된 추적 τ가 주어지면 시간 t + △t 후 주어진 예측 경로(궤적) T의 (절대) 가능성은 예를 들어 다음과 같이 결정될 수 있다.

여기서, p(G_i|τ)는 위에서 정의되고, p(T|G_i)는 시간 t + △t에서 목표 G_i에 대한 경로 분포가 주어진 경우 경로 T를 취하는 에이전트의 예측된 확률이다. 표기법 "△t" 및 "△T"는 본 명세서에서 동일하다는 점에 유의한다. 또한, 궤적들을 나타내는데 사용되는 수학적 표기법(그리스어 소문자 또는 대문자 "tau", 즉 τ, T)과 시간을 나타내는 데 사용되는 표기법(소문자 또는 라틴 대문자 "t", 즉 t, T) 간의 차이에 유의한다.

궤적은 단순한 공간 경로 일 수 있지만 상기 서술은 움직임 정보(예를 들어, 스피드/속도 정보, 가속도)를 포함하는 궤적에도 동일하게 적용된다. 후자의 경우, 2개의 궤적들은 동일한 공간 경로에 대응할 수 있지만(또는 궤적들의 적어도 각각의 부분은 동일한 공간 경로에 대응할 수 있음), 그럼에도 불구하고 예를 들어 서로 다른 궤적일 수 있는데, 이는 상이한 속도 정보와 관련되기 때문이다(예를 들어, 하나는 실질적으로 동일한 공간 경로를 따라 이동하지만 공간 경로를 따라 적어도 일부 지점에서 더 낮은 속도로 이동하는 차량에 해당할 수 있다). 예를 들어, 궤적은 연관된 속도 또는 공간 경로의 각 지점 또는 섹션들과 연관된 속도들의 세트와 결합된 공간 경로의 형태를 취할 수 있다. 확장은 관련 가속도 값(들) 등을 추가로 통합할 수 있다.

도면들에서는 도시되지 않지만, p(T|G_i)가 결정되는 시간 t + △t에서의 경로 분포는, 위와 같이 목표 G_i에 대해 시간 t + △t에서 역 플래너(A24)를 다시 실행하여 그 자체로 결정될 수 있지만, 그에 따라 예상 궤적 모델을 업데이트하기 위해 시간 t + △t에서 외부 에이전트 r_{t + △t}의 새로운 결정된 위치를 사용한다. 목표 파라미터들은 역 플래너(A24)를 다시 실행하기 위해 이 시점에서 업데이트되거나 업데이트되지 않았을 수 있다. 데이터 기반 행동 모델이 사용되는 경우, 예측된 궤적 모델을 업데이트하기 위해 유사하게 행동 모델을 해당 시점에 다시 실행할 수 있다.

위의 단계들은 시간이 지남에 따라 가능하면 실시간으로 반복적으로 수행된다. 목표에 도달하지 못한 외부 에이전트의 경우, 처음에는 상이한 목표들에 대한 경로 분포들이 초기에 유사하기 때문에 실행중인 목표를 명확하게 결정하는 것이 불가능할 수 있고, 그리고 이것은 가정된 목표들의 세트에 대한 확률들의 분포에 반영될 것이다. 경로 분포들이 분산됨에 따라, 확률 분포는 일반적으로 경로 분포가 분산됨에 따라 특정 목표를 향해 왜곡되기 시작할 것이다.

기동들의 역 계획

위는 목표들에 대한 역 계획을 고려한다. 표시된 것처럼, 역 계획은 또한 일련의 가정된 기동들 M을 통해 기동 수준에서 구현할 수도 있다.

예를 들어, 다른 차량이 현재 인접 교차로들이 없는 다차선 도로에서 주행 중이라면, 가정된 기동들의 세트 M은 "차선 따르기" 및 "차선 전환"으로 구성될 수 있다. 이 경우, "차선 따르기" 기동을 위해 한 세트의 경로들이 생성되고, 이 경로들은 다른 차량이 현재 "차선 따르기" 기동을 실행하고 있을 경우 다른 차량이 취할 것으로 예상되는 경로들이며, 그리고 "차선 전환" 기동을 위해 또 다른 경로들의 세트가 생성되며, 이는 다른 차량이 "차선 전환" 기동을 실행하는 경우 취할 수 있는 경로들이다. 위의 서술은 기동 레벨의 역 계획에도 동일하게 적용되지만, 가정된 목표 세트 G 대신 가정된 기동들 M 세트가 적용된다.

기동 레벨 역 계획의 경우, 외부 에이전트의 관찰된 추적 τ은 가능한 기동들 세트 M의 각 기동 M_j∈M의 확률을 추정하기 위해 사용될 수 있다. 각 기동 M_j∈M에 대해, 예측된 궤적 모델은 그림 7a에서와 같이 시간 t에 대해 결정된다. 예측된 궤적 모델은 단일 궤적 또는 궤적 분포일 수 있다. 그런 다음, 실제 관찰된 추적 τ를 각 기동 Mj에 대한 궤적 모델과 비교하여(그림 7b에서와 같이), 그 기동 P (Mj|τ)의 확률은 관찰된 추적 τ이 그 기동 M_j에 대한 궤적 모델과 일치하는 정도를 기반으로 추정될 수 있다. 위와 같이, 이는 소프트 매칭의 한 형태가 될 수 있다.

다음 예에서, 계산들을 단순화하기 위해, 각 기동 M_j는 역 계획을 위해 단일 궤적에 맵핑된다. 궤적 분포와 관련된 기동의 경우, 역 계획의 목적으로 분포의 모드 또는 가장 가능성이 높은 궤적을 취할 수 있다. 이 경우,

되도록 단일 궤적 T_j가 존재한다고 가정되고, 그리고 모든 다른 궤적들의 확률은 0으로 가정된다.

위에서 사용된 표기법은, 주어진 기동 M_j에 관련된 궤적 T_j와 주어진 목표 G_i에 대해 평가된 궤적 T를 구별한다.

목표 G_i에 도달하기 위해, 외부 에이전트는 기동들의 시퀀스, 예를 들어, (M_j, M_k,...)를 실행할 수 있다. 이 경우, 전체 목표 궤적(즉, 목표 G_i에 도달하기위한)은 개별 기동 M_i, M_j, ...와 관련된 기동 궤적들의 조합으로 결정될 수 있다. 예를 들어, 후술하는 구현에서, 목표 궤적은 기동 궤적들을 결합하고 여기에 속도 평활화를 적용하여 결정된다. 이런 이유로, 기동 M_i와 연관된 (또는 이와 관련하여 평가된) 궤적 T_i는 "부분 궤적(partial trajectory)"으로 지칭될 수 있으며, 목표와 관련된 (또는 이와 관련하여 평가된) 궤적 T는 "전체 궤적(full trajectory)"이라고 지칭될 수 있다.

특정 목표 G_i에 대한 다중 궤적들이 고려되는 경우, 표기법 T⁽ⁿ⁾은 목표 G_i에 대한 n 번째 궤적을 언급하기 위해 T 대신 사용될 수 있다.

부분 궤적들과 기동들 사이의 "일대일" 관계에 대한 위의 단순화 가정은 계산 부담을 줄이면서 수용 가능한 성능을 제공하는 것으로 밝혀졌다. 하지만, 궤적들과 기동들 사이의 "일대일" 관계에 대한 가정을 암시하지 않는 대체 구현들은 그럼에도 불구하고 실행 가능하다. 이 단순화된 가정 없이, 더 일반적인 베이지안 계속 관계가 유지된다.

여기서

는 기동 M_l이 주어진 부분 궤적 T_j의 확률이다. 이 경우, 상기 모드/가장 가능성이 높은 부분 궤적을 가정하는 대신, 부분 궤적을 p(T_j|M_l)에서 샘플링 할 수 있고, 그리고 상기 모드/가장 가능성이 높은 부분 궤적에 관한 본 문서의 모든 서술은 그 경우에 샘플링된 궤적에도 동일하게 적용된다.

역 계획-예시 구현

추가 예시로서, 목표 인식을 위한 역 계획의 예시적인 구현이 이제 더 상세히 설명될 것이다. 이것은 하나 이상의 외부 에이전트에 대해 설정된 이용 가능한 목표 G에 대한 확률 분포 P(G|0), 즉, 이용 가능한 각 목표에 대해, 에이전트가 현재 해당 목표를 구현하고 있을 것으로 예상되는 확률을 예측하기 위해 목표 레벨에서 역 계획을 사용한다.

서술된 구현은 확률적 기동 검출을 추가적으로 사용하여 외부 에이전트의 관찰된 추적 τ가 주어지면 가능한 기동들의 세트 M에 대한 분포 R(M|τ), 즉, 가능한 각 기동에 대해, 에이전트가 현재 해당 기동을 실행하고 있을 것으로 예상되는 확률을 예측한다. 기동 예측들은 나중에 서술된 것처럼 목표 예측들에 반영된다. 예를 들어, 기동 검출은 기동 레벨에서 역 계획을 사용하여 구현할 수 있다.

즉, 기동 레벨과 목표 레벨 모두에서 서술된 구현 이유이다.

목표 인식

목표 인식은 에이전트의 과거 행동 및 기타 상황 정보를 관찰하여 에이전트(외부 행위자 - 다음 예들에서는 대상 차량이지만 언급된 다른 형태의 행위자 일 수 있음)의 에이전트 목표를 추론하는 프로세스이다.

현재의 맥락에서, 목표는 일반적으로 고속도로/교차로의 다양한 출구 또는 상이한 차선들과 같이 역 플래너(A24)가 추론하는 목표의 차량에 대한 대상 위치를 지정한다. 다른 에이전트의 목표들에 대한 지식은 가정된 목표들과 관련하여 에이전트의 행동에 대해 예측할 수 있기 때문에 계획 프로세스를 알려줄 수 있다.

목표 인식을 사용하면 AV 시스템의 "설명 가능성(explainability)"도 높아진다. 설명 가능성은 인간에게 결정을 설명하는 시스템의 능력을 나타낸다. 목표 추론 프로세스(자아 차량이 다른 차량의 목표가 상이한 시간들에 있다고 믿었던 것)를 기록하면 의사 결정 추적 및 디버깅을 위한 해석 가능한 정보를 제공할 수 있다.

목표들은 결정론적 또는 확률론적으로 추론될 수 있다. 다음 예들에서, 목표들은 일련의 관련 관찰들 O이 주어지면 확률적으로 추론된다. 즉, 목표 사후 P(G|0)는 이용 가능한 목표들 G의 유한 세트에 대해 추정되며, P(G_i|0)는 관찰들 O이 주어졌을 때 외부 에이전트가 목표

를 가질 확률이다.

MCTS의 맥락에서, 목표들은 확률적으로 추론되어 위와 같은 의미로 트리가 전개됨에 따라 외부 행위자의 미래 궤적에 대해 합리적으로 예측할 수 있다.

기동들 및 목표들

먼저, 이용 가능한 목표들 및 기동들을 결정하는 예시적인 체계가 서술된다. 이 서술은 나중에 서술된 역 계획의 특정 구현과 관련된 컨텍스트를 제공한다. 그러나, 서술은 이와 관련하여 제한되지 않으며 MCTS의 다른 구현들에도 동일하게 적용되고, 상기 MCTS의 다른 구현들은, 역 계획/목표 인식의 대체 구현들 및 목표 인식을 사용하지 않는 구현들(예를 들어, 상위 레벨 목표 인식 없이 데이터 기반 행동 모델들을 사용하는 위에 제공된 예들)을 포함한다.

다중 정책 기준

"다중 정책 방법"이 기준선으로 사용된다. 다중 정책 방법의 기본 가정은 자아 차량을 포함한 모든 차량들(또는 보다 일반적으로 외부 행위자들)이 차선 따르기, 차선 변경, 회전 등과 같은 한정된 수의 기동들 중 하나를 실행하고 있다는 것이다. 이러한 기동들은 본 명세서에서 "기동 정책들(maneuver policies)"이라고도 할 수 있다(기동 정책, 즉, 유한한 세트의 기동들 중 하나의 기동과 선택된 기동 정책을 실행하는 데 사용될 수 있는 행동 정책 사이의 차이에 주목한다. 기동의 영어/미국 철자들(manoeuvre/maneuver)은 여기에서 혼용된다).

"타겟" 행위자는 행동이 예측되는 외부 행위자를 의미한다. 하나 또는 여러 대상 차량들(또는 다른 행위자들)에 대해 예측들이 이루어질 수 있으며, 위의 가정들의 세트는 각 대상 행위자에 적용된다. 앞 단락의 기동 정책 예들은 실제로 "폐쇄 루프(closed-loop)"이다. 즉, 센서 피드백을 고려하고 선행 차량(선행 차량은 대상 차량이 따라가는 차량)까지 속도와 거리를 자동으로 변경한다. 그러나, 아래에 설명된 바와 같이, 역 계획을 위해, 계산 효율성이 증가하고 역 플래너(A24)의 성능에 큰 영향을 주지 않으면서 "개방 루프(open-loop)" 기동들로 모델링될 수 있다. 다음 예에서는 대상 차량 및 주요 차량이 자동차들이지만, 서술은 모든 형태의 행위자(차량들, 보행자들, 자전거 타는 사람들 등)에 동일하게 적용된다. 마찬가지로, 이 예에서는 자율 주행 차량(자아 자동차)을 고려하지만 서술은 모든 형태의 자율 주행 차량에 적용된다.

아래에서 상세히 설명되는, 도 12는 예측 컴포넌트(A4)의 일부로서 기동 검출기(1102)를 도시한다.

일례로서, 기동 검출기(1102)는 전술한 방식으로, 기동 레벨에서 역 계획을 구현할 수 있다.

다른 예로서, 기동 검출기(1102)는 베이지안 변화점 검출 방법을 구현할 수 있다. 이 방법은, 대상 차량의 관찰된 낮은 레벨 궤적을 기동들의 시퀀스로 분할하는데 사용되며, 가장 최근의 세그먼트는 차량의 현재 실행중인 기동의 예측으로 사용된다. 이 예측을 사용하여, 자아 자동차가 사용할 수 있는 각 기동에 대해 다수의 전진 궤적들을 시뮬레이션하고 가장 좋은 평가를 받은 기동이 실행을 위해 선택된다.

베이지안 변화점 검출은 그 자체로 알려져 있으며, 시스템의 기본 숨겨진 상태에서 변화들을 확률적으로 검출하는 것을 말한다. 현재의 맥락에서, 특정 시간에 외부 행위자의 숨겨진 상태는 해당 시점에서 실행중인 기동 정책으로 정의된다. 이러한 숨겨진 상태는 직접 관찰할 수 없으므로 숨겨진 상태(이 예에서는 관찰된 추적)로 인한 관찰들을 통해 추론되어야 한다. 이를 통해, 현재 시점에서 이용 가능한 각 기동의 확률, 즉, 외부 행위자가 현재 해당 기동을 실행할 확률을 추정할 수 있다.

예를 들어, 숨겨진 마르코프 모델(HHM)을 사용하여 HHM의 숨겨진 상태들로 기동들을 나타낼 수 있으며, 여기서 관찰된 추적은 HMM의 상태 전이들에서 발생하는 것으로 모델링된다.

아래에 설명된 것처럼, 계획 프로세스를 상당히 단순화하기 위해 상대적으로 작은 기동 정책들의 세트를 정의할 수 있다. 속도 및 거리와 같은 낮은 레벨의 계획을 포괄하는 방식으로 기동 정책들이 정의되어 있기 때문에 이러한 작은 집합을 정의하는 것이 가능하다. 마찬가지로, 다른 자동차들이 이러한 동일한 정책들 중 하나를 실행하는 것으로 간주되기 때문에, 낮은 레벨의 궤적들을 고려할 때 현재의 기동들은 효율적으로 추론될 수 있다.

이 다중 정책 방법 자체는 다른 자동차들의 현재 기동만을 예측하지만 미래 기동들을 예측하려고 시도하지 않는다는 점에서 근시안적이다. 역 계획은 이 방법을 기반으로 나중에 설명하는 것처럼 향후 조치를 예측한다.

기동들

기본 기동들

기동들은 계획 및 예측에 사용되는 기본 행동들을 나타낸다. 이 예에서는 다음과 같은 "기본(basic)"(기초) 기동들이 고려된다.

차선 따라 가기

왼쪽/오른쪽으로 차선 변경

좌/우회전(주행 방향에서 가장 가까운 차선으로 회전)

중지/주의

설명된 기술들은 대안적 또는 추가적 기동들로 확장될 수 있음을 이해될 것이다.

각각의 기본 기동에는 그와 관련된 적용 가능성 및 종료 조건이 지정되어 있다. 기동은 해당 상태가 기동의 적용 가능 조건을 충족하는 경우에만 주어진 상태에서 사용할 수 있다. 예를 들어, 왼쪽으로 차선 변경은 차의 왼쪽에 차선이 있고 해당 차선에 차를 위한 충분한 열린 공간이 있는 경우에만 가능하다. 적용 가능성 조건은 트래픽 규칙들을 인코딩할 수도 있다. 상태가 종료 조건을 충족하면 기동이 종료된다. 차선 변경 기동의 경우, 차량이 차선에 도착하고 차선 방향과 정렬된 경우이다.

기동의 시작과 끝 사이에, 기동은 자아 자동차가 따라갈 기준 경로와 경로를 따라 목표 속도를 지정한다. 현재 문맥에서, 궤적은 쌍(정적 기준 경로, 목표 속도들)으로 정의된다. 즉, 정적 참조 경로와 관련된 목표 속도들의 세트이다(위 참조).

그러나, 일반적으로, 기동은 여러 궤적들과 연관된다. 예를 들어, 예측의 맥락에서, 기동은 궤적 분포, 즉, 각각 지정된 확률(즉, 현재 해당 기동을 실행하고 있다고 가정할 때 외부 행위자가 해당 궤적을 따를 확률)을 갖는 궤적들의 세트와 연관될 수 있다.

차선 따르기 및 주의와 같은 일부 기동들에는 자연적인 종료 조건들이 없다. 이러한 기동들의 경우, 종료 조건이 파라미터로 지정된다. "매크로 동작(Macro actions)"(아래 참조)은 컨텍스트 정보를 기반으로 이러한 파라미터들을 자동으로 설정한다.

주의 기동은 매크로 동작에 사용되는 정지 기동의 변형이다. 주의는 차량의 속도를 줄이고 파라미터로 지정된 위치로 계속 이동한다. 그 위치에서, 종료 조건이 충족되면 기동이 종료되고, 그렇지 않으면, 차량이 완전히 정지한 후 종료 조건이 충족되면 종료된다. 종료 조건은 지정된 차선들에서 다가오는 차량들을 확인하는 데 사용된다(파라미터로 제공됨). 차선들이 지정되지 않은 경우, 종료 조건은 항상 참이다. 이를 통해, 차량은 다가오는 차량들이 있을 때 안전하고 원활한 출입을 계획할 수 있다. 좌/우 매크로를 종료할 때만 주의하는 특별한 경우에서, 다가오는 차량이 정지하고 제어 차량이 회전 기동을 완료하는 데 필요한 시간 동안 정지 상태를 유지할 것으로 예상되는 경우, 강제 종료가 허용된다. 이는 아래에 서술된 시나리오 3과 같은 특별한 경우들에서 가능하다.

일부 기본 기동들은 추가 파라미터들이 있거나 회전 기동과 같은 매우 특정 위치들에서만 가능하기 때문에 매크로 동작들 내에서만 사용된다.

다음 예들에서, 2개의 유형의 기본 기동들: 역 계획(예측) 또는 더 일반적인, 즉, 도 1의 목표 인식 컴포넌트(A24)에 의한 목표 인식을 위한 개방 루프 기동들, 및 AV의 플래너에서 MCTS 자아 계획을 위한 폐쇄 루프 기동들을 사용한다. 이것들은 아래 섹션들에 상세히 서술된다.

폐쇄 루프 기동들

센서들의 피드백을 사용하는 경우 기본 기동은 폐쇄 루프이다. 이것은 기동들의 상이한 정도의 자동화를 포함할 수 있다. 여기서는, 각 폐쇄 루프 기동이 차량의 속도 및 선행 차량까지의 거리를 자동으로 제어한다고 가정한다(ACC (Adaptive Cruise Control)의 한 형태). 또한, 각 기동은 비상 브레이크를 자동으로 시작할 수 있다고 가정한다.

이 시스템은 기동들의 특정 구현에 대해 불가지론적이며, 본질적으로 이를 "블랙 박스(black box)" 기능으로 간주한다. 이것은, 유연성의 이점을 가지고 있으며, 상이한 표현들을 간단하게 통합할 수 있다. 가능한 구현들은 다음과 같다.

유한 상태 머신 또는 프로그래밍 로직을 사용하여 하드 코딩된 휴리스틱

운동학적 자전거 모델로 정의된 모션 프리미티브들을 사용하는 격자 경로 플래너

제약 최적화 플래너

위 목록의 계획 방법들은 상태 변경 후 반복적으로 호출하여 폐쇄 루프로 만들 수 있다.

개방 루프 기동들

폐쇄 루프 기동들과 달리 개방 루프 기동들은 센서 피드백을 사용하지 않는다. 개방 루프 기동은 피드백으로 이러한 경로들을 수정하지 않고 참조 경로(또는 경로들을 통한 분포)를 지정한다. 이를 통해 더 간단하고 계산적으로 비용이 적게 드는 기동들을 구현할 수 있다.

다시 말하지만, 시스템은 개방 루프 기동들의 표현에 대해 불가지론적이다.

개방 루프 기동들을 구현하는 간단하지만 효과적인 방법은 다항식 함수를 도로 토폴로지에서 추출한 점들의 집합에 맞춘다. 목표 속도들은 상수 또는 기타 시계열로 설정될 수 있다. 이것은 궤적들에 대한 분포가 아닌 하나의 궤적을 계산하는데, 이는 많은 실제 상황들에서 충분한 것으로 밝혀졌다.

또 다른 구현에서는 위에서 설명한 종류의 동작 모델(예를 들어, 가우시안 프로세스 또는 신경 네트워크)을 사용하여 주행 궤적들을 수집한다. 이 궤적 데이터는 다음과 같은 상이한 방식들로 생성될 수 있다.

시뮬레이션에서, 다양한 상황들에서 해당 폐쇄 루프 기동을 사용

실제 주행 데이터로부터 AV 플랫폼으로 생성

실제 CCTV 데이터로부터, 인식된 기동들로 분할

예로서, 도 13은 시간에 따른 CCTV 영상에서 관찰된 궤적들에 맞춰진 가우시안 궤적 모델(1202)의 예를 보여준다.

주의 기동에 사용되는, "다가오는 차량들이 없어질 때까지 기다림(wait until oncoming traffic is clear)"과 같은 조건들은, 조건이 참일 것으로 예측될 때까지 지정된 시간 동안 기다림(예를 들어, 차량들이 없어진다고 예측될 때까지 기다림)으로써 개방 루프 기동들로 실현될 수 있다.

목표 속도들 및 속도 평활

언급한 바와 같이, 본 예에서, 궤적은 목표 속도들의 세트와 결합된 정적 경로로 정의된다.

목표 속도들은 기본 기동들 내에서 설정된다. 일반적으로, 차량들이 특정 지역에서 특정 속도(예를 들어, 제한 속도)로 주행을 시도한다고 (예를 들어) 가정할 수 있다. 이 목표는 전방에 느린 차가 있거나 (이 경우 차의 속도가 새로운 목표가 되는 경우) 또는 주행 경로의 곡률 등으로 인해 필요한 경우 감소한다.

개방 루프 차선 따라 가기의 경우, 목표 속도들은 최소(속도 제한, 전방 차량 속도)로 설정된다.

단순성으로 인해 이 방법은 계산 비용이 저렴하지만 충돌하는 다른 차량들에 대한 예측된 궤적들로 이어질 수 있다. 예를 들어, 아래 시나리오 1에서, 트럭은 제한 속도에서 (앞에 차량이 없기 때문에) 계속 직진할 것으로 예측되고, 속도 제한에서 자동차 2가 추월하는 구간(차선 추월 구간 동안)도 가정된다. 자동차 2에 대한 역 계획이 실제로 트럭에 대해 일정한 속도를 가정되었기 때문에, 자동차 2와 트럭에 대한 예측된 궤적들이 충돌할 수 있다. 그러나, 이 경우와 다른 많은 경우들에는, 이러한 불일치가 에고 플래너(A6)에 문제를 일으키지 않는다는 것이 밝혀졌다. 이 단순한 방법의 예측 결과를 사용하여 안전하고 효과적인 계획 결정을 내릴 수 있다.

곡선 궤적들(예를 들어, 선회 및 차선 변경)을 생성하는 기본 기동들 내에서, 목표 속도들은 로컬 곡률을 기반으로 하는 휴리스틱을 사용하여 설정된다. 이 함수는 아래에 나타나고, 여기서

은 목표 속도이고

는 점 곡률이다. 다른 용어들은 적절한 값들로 설정된 상수들이다.

점 곡률은 아래 방정식으로 주어지며, 여기서 x와 y는 데카르트 좌표들이다. x와 y의 미분들은 유한 차분을 사용하여 차량의 목표 경로에서 추정된다.

속도 평활화

속도들은 기본 기동들 내부에 설정되어 있기 때문에, 두 번의 후속 기동들은 속도가 갑작스럽게 변경될 수 있다. 전형적인 예는 차선을 따라 가고 회전 기동하는 것이다.

이 효과를 보완하기 위해, 제어력과 현실감을 향상시키기 위해 상이한 기동들에 따른 결과적인 완전한 궤적을 속도에서 평활화할 수 있다. 주어진 궤적에서 목표 속도들을 최적화하는 속도 평활화 기능이 사용된다. 속도 평활화는 예측(역 계획)과 MCTS 자아 계획 모두에 사용된다.

속도 평활화는 주어진 경로를 따라 궤적에 대한 최적화 문제로 공식화된다. 길이 방향 위치들에서 점들의 세트

, 각각 점의 목표 속도

, 연속적이고 미분 가능한 함수

가 장착된다고 가정하자. 그런 다음, 시간 수평선 T_H (예를 들어 목표 속도들을 사용하여 추정될 수 있음), 두 시점들

사이에 경과한 시간, 및 최적화의 기타 파라미터들(예를 들어, 최대 속도,

및 가속도,

)를 고려하면, 평활화 문제는 다음과 같이 정의된다.

문제의 솔루션에서, 공간적으로 리샘플링하는 것은

에서 실제로 얻을 수있는 값들을 얻기 위해 사용될 수 있다. 마지막으로 달성 가능한 위치는

로 주어진다.

이면, 이 솔루션에서만 리샘플링 할 수 있다.

대안으로, 유사한 문제는

로부터 시작하여 풀 수 있고, 조건이 달성될 때까지 이 절차는 반복될 수 있다.

가속도와 같은 궤적과 관련된 다른 파라미터(들)을 모델링하고 문제에 대한 확장으로서 이러한 파라미터(들)에 제약들을 부과하는 것도 가능하다.

속도 평활화는 입력 궤적에서 속도가 0임을 나타내야하며, 이는 완전 정지를 나타낸다. 이를 달성하는 간단한 방법은, 궤적을 중지 이벤트들(제로 속도)로 구분된 세그먼트들로 분할하고 각 세그먼트에 평활화 기능을 적용하는 것이다.

매크로 액션들

여기에서 "매크로 액션들"이라고 하는 특별한 종류의 기동은 다음 두 가지 중요한 방식들로 플래너를 완화한다. 이것들은 일반적인 기동들의 순서를 지정하고, 그리고 상황 정보(일반적으로 도로 레이아웃)를 기반으로 기본 기동들에서 자유 파라미터들을 자동으로 설정한다.

이 예에서는, 다음 매크로 동작들이 사용된다(대괄호들로 표시된 기동 파라미터들을 포함).

계속 차선: 순서를 지정<차선 따라 가기(눈에 보이는 차선 끝까지, 즉 차선 목표)>

왼쪽/오른쪽 출구: 순서를 지정<차선 따라 가기(전환점 근처까지), 주의(다가오는 차량들이 전혀 없음/안전한 거리까지), 좌/우회전>. 출구 지점은 자아 자동차의 목표에 해당하는 지점으로 자동 설정되어 매크로 동작이 이전 출구 지점들을 건너뛸 수 있도록 한다(이는 원형 교차로에서 특히 유용함).

교차 도로: 순서를 지정<차선 따라 가기(건널목 근처까지), 주의(건널목에서 다가오는 차량들이 전혀 없음/안전한 거리까지), 차선 따라 가기(건널목 이후 까지)>

추월: 순서를 지정<오른쪽으로 차선 변경, 차선 따라 가기(자아 자동차가 다른 차(들)를 지나갈 때까지), 왼쪽으로 차선 변경>

매크로 동작의 적용 가능 조건은, 매크로 동작에서 제1 기동의 적용 가능 조건과 가능한 추가 조건들에 의해 제공된다. 예를 들어, <우측 출구>의 추가 조건은 차량이 주행 방향에서 가장 오른쪽 차선에 있고 목표 출구 지점이 차량 앞의 같은 차선에 있다는 것이다. <교차 도로>의 추가 조건은, 자아 자동차가 다른 차량보다 먼저 양보해야 하는 도로 건널목이 있다는 것이다(아래 시나리오 3 참조). 매크로 동작의 종료 조건은 매크로 동작의 마지막 기동에 의해 제공된다.

매크로 동작은 계획 및 예측 프로세스의 속도를 크게 높일 수 있는데, 이는 단일 매크로 동작으로 주어진 목표를 달성하기에 충분할 수 있기 때문이다. 예를 들어, 아래 시나리오 2에서, 자아 자동차의 목표가 G3이면, 단일 매크로 동작 <우측 출구>가 이미 목표를 달성할 것이다. 매크로 동작들은 기동들 사이의 전환 지점들을 자동으로 처리하므로 유용하고, 그렇지 않으면 명시적으로 계획될 필요가 있다(예를 들어, 차선 따르기와 같은 기동의 개방 종료 조건 설정).

이 작업에 사용된 매크로 동작들은 분해 가능한 동작들의 계층을 정의하지 않는다. 그들은 단순히 유연한 방식으로 일련의 동작들을 정의한다. 매크로 동작들은 계획 검색 공간에 암시적으로 포함된다.

언급했듯이, 아래에 서술된 MCTS 프로세스의 특정 예에 대해, 매크로 동작들의 모든 기본 기동들은 폐쇄 루프이고, 역 계획의 경우, 모든 기본 기동들은 개방 루프이다.

목표들 및 목표 생성

자아 자동차의 목표들

자아 자동차의 목표들은 경로 계획을 기반으로 생성된다. 경로 플래너(A25, 도 1)는 주석이 달린 도로 지도(차선 방향들, 교통 표지판들 등으로 주석이 달림) 및 시작/종료 위치들을 입력으로 사용한다. 에고 자동차가 통과해야 하는 도로 세그먼트들의 순서와 방향들을 지정하는 시작에서 끝 위치까지의 경로를 계산한다. 이 경로는 플래너(A6)로 전달되며, 여기에서 다음과 같이 에고 자동차의 목표들을 생성하는데 사용된다. 개념적으로, 플래너(A6)은 아래에 표시된 시나리오 그림들과 유사하게 자아 자동차를 중심으로 하는 뷰 영역(예를 들어, 정사각형 또는 원형 또는 임의의 적절한 모양)으로 맵을 "확대"한다. 이 보기 영역은 자아 자동차와 함께 계속 이동한다. 어느 시점에서든, 자아 자동차의 목표는, 경로의 다음 출구 지점(자동차가 현재 도로에서 연결 도로로 변경할 필요가 있는 곳) 또는 경로의 다음 출구 지점이 아직 보이지 않는 경우 현재 차선의 보이는 끝에 의해 주어진다. 예를 들어, 시나리오 1 아래의 다음 출구 지점이 보이지 않으므로 목표는 G1이다. 아래 시나리오 2에서는, 출구 지점이 표시되고 새 목표가 G3이된다.

다른 자동차들의 목표

예를 들어, 다른 자동차의 목표들은 가능한 출구 지점들과 에고 자동차의 시야 영역에 의해 경계가 지정된 자동차 방향의 가시적인 도로 끝으로 정의될 수 있다. 휴리스틱 목표 생성 기능은 도로 레이아웃 및 교통 규칙들에 대한 정보(예를 들어, SDL 도로 그래프 사용)를 사용하여 주어진 보기 영역에서 자동차에 대해 가능한 목표들의 세트를 열거하는데 사용된다. 목표들이 많을 때(예를 들어, 출구 지점들이 많을 때) 계산 시간을 줄이기 위해, 이 기능은 차량 앞의 동일한 차선에 이미 두 개의 이전 출구 지점들이 있는 경우 차량의 출구 지점 목표를 무시할 수 있다.

"당신이 내 앞에 있기를 바랍니다(I want you to be in front of me)"와 같은 다른 유형의 목표들을 지정할 수 있다. 이러한 목표들은 환경의 현재 자동차들의 구성에 따라 동적으로 추가 및 제거될 수 있다. 아래 시나리오 서술들은 목표들의 예들을 제공한다.

목표 인식

이러한 예시적인 구현에서, 목표 인식은 이제 도 10을 참조하여 설명될 "비용 불이익들(cost penalties)"에 기초하여 수행된다.

본 문맥에서 "계획"은 목표에 도달하기 위해 선택된 하나 이상의 기본 기동들의 순서를 의미한다. 어떤 경우에는 이러한 기본 기동들의 순서가 매크로 동작으로 정의될 수 있다. 매크로 동작이나 여러 기본 기동들의 다른 시퀀스를 사용하면, 각 기본 기동은 부분 궤적과 연관되며, 부분 궤적은 속도 평활화를 사용하여 결합되어 목표에 도달하기 위한 전체 궤적을 결정한다.

도 10은 비용 패널티들을 기반으로 이용 가능한 목표들의 제한된 세트로부터 외부 행위자의 목표를 확률적으로 추론하는 방법에 대한 개략적인 순서도를 도시한다. 도 10의 오른쪽에는 이용 가능한 두 가지 목표들이 있는 시나리오에 적용되는 단계들의 예시가 도시된다.

1. G₁ - 눈에 보이는 도로 끝에서 목표 위치로 정의되는 현재 도로를 계속 따라간다(보다 일반적으로 현재 도로에서 차량 앞의 기준점으로 정의됨).

2. G2 - 출구 위치로 정의된, 우회전 출구로 나옴.

관찰된 차량에 대해 가능한 목표들의 세트와 차량이 실행한 과거의 기본 기동들의 순서를 고려할 때, 목표들에 대한 사후 분포는 역 계획 프로세스를 사용하여 계산될 수 있다. 이 방법은 일련의 관측치들 0(예를 들어, 위의 예에서와 같이 관측된 트레이스

)에 대해 가능한 목표들 G에 대해 베이지안 사후 확률 P(G│0) ~ L(0│G)P(G), 목표들에 대한 사전 분포 P(G) 및 우도 함수 L(0│G)를 계산한다.

표기법 P(0│G) 및 L(0│G)는 동등하며 목표 G가 주어진 경우 관측치 0의 조건부 확률을 의미한다. 표기법 "L"은 이러한 확률들이 통계적 의미에서 우도라는 사실과 일치하여 사용된다(이 개시의 앞부분에서 우도라는 용어는 일상적인 의미로 사용되며 반드시 이러한 특정 통계가 아니라는 점에 유의해야 한다. 의미는 문맥상 명확할 것이다).

목표는 목표 위치로 정의되고, 표기법 G_i는 해당 지역의 목표 위치를 나타내는데 사용될 수 있다. 목표 위치 G_i는 공간의 한 지점이 될 수 있지만, 지역이 될 수도 있고 도로를 따라 특정 거리에 해당할 수도 있다. 예를 들어, 목표 위치는 도로에 수직인 선으로 정의될 수 있으며, 이 경우 자동차가 해당 선에 도달하면 목표에 도달했다고 한다(도로에서의 측면 위치에 관계없이).

주어진 목표

에 대한 우도 L(0│G)은 두 계획들의 각 비용 간의 차이 (비용 패널티)로 정의된다.

1. 자동차의 초기 위치 r_t(시간 t)에서 목표 위치 G_i까지의 최적 계획, 즉, 시간 t 이후에 자동차의 관찰된 행동에 관계없이 r_t에서 G_i로가는 최적의 계획. 이것은 기본 기동, 매크로 동작 또는 매크로 동작 이외의 여러 기본 기동들의 시퀀스로 실행될 수 있다. 여러 개의 기본 기동들을 사용하면, 그와 관련된 부분 궤적들이 결합되어 초기 위치 r_t에서 목표 G_i에 도달하기 위한 최적의 전체 궤적들을 제공한다(시간 t 이후에 자동차의 실제 관찰된 동작에 관계없이).

2. "가장 유용한" 계획 - 이것은 시간 t와 시간 t+△t 사이에서 관찰된 자동차의 행동을 고려하여 r_t에서 목표 위치 G_i까지의 최적 계획으로 정의된다. 즉, 이 계획이 후속 시간 간격 △t에서 실제로 관찰된 동작과 일치해야 한다는 추가 제약 조건으로 r_t에서 G_i로 얻을 수 있는 최선의 계획이다. 즉, 자동차의 초기 위치 r_t에서 목표 G_i까지 최적의 계획으로, 이 계획은 관측들 0과 관련된다. 이것은 자동차들이 목표들을 달성하기 위해 최적의 계획들을 실행할 가능성이 더 높지만 어느 정도의 편차를 허용한다고 가정한다. 이것은 또한 기본 기동, 매크로 동작 또는 매크로 동작 이외의 여러 기본 기동들의 시퀀스로 실행될 수 있다. 다수의 기본 기동들로, 이와 관련된 부분 궤적들은 결합되어 초기 위치 r_t에서 목표 G_i에 도달하기 위한 "가장 유용한" 전체 궤적을 제공하지만 t에서 t + △t까지의 간격에서 자동차의 실제 관찰된 행동을 고려한다. 가장 유용한 궤적에는 실제 관찰된 궤적과 일치하는 간격 [t, t + △t]에 대한 관찰된 부분과 이후의 시간 간격에 대한 미래 부분이 있으며, 가장 유용한 전체 궤적과 관련된 전체 비용을 최소화하도록 선택된다(관찰된 비용과 미래 부분의 전체 비용).

이것은 목표에 도달하기 위한 전체 경로를 고려하기 때문에 목표 인식의 한 형태이다(다중 기동들과 관련된 여러 부분 궤적들을 기반으로 할 수 있음).

전체 궤적에 할당된 비용은 나중에 서술되는 다양한 요소들을 고려할 수 있다. 여기에는 주행 시간(목표에 도달하는데 더 오래 걸리는 궤적들에 불이익을 줌), 안전(안전하지 않은 궤적들에 불이익을 줌) 및 편안함(예를 들어, 과도한 움직인 있는 궤적들에 불이익을 줌)이 포함된다.

예를 들어, 자동차의 초기 위치 r_t는 자동차에서 처음으로 관찰된 위치일 수 있다. 합리적인 접근 방식은 초기 위치 r_t를 정의하기 위해 자아 자동차의 센서 범위에 의해 정의된 과거 관찰들의 이동 창을 사용하는 것이다.

도 10의 단계 1004에서 각 목표 G₁, G₂에 대해 최적 계획(위의 1)이 계산된다. 일단 계산되면, 예를 들어, A* 검색을 사용하여 각 목표 G₁, G₂에 대해 최적의 궤적을 결정할 수 있다(자세한 내용은 아래 참조). 최적 궤적을 계산한 후, 최적 궤적과 관련된 전체 비용을 계산할 수 있다(아래 설명도 참조). 최적 궤적은 전체 궤적, 즉 초기 위치 r_t에서 문제의 목표에 도달하기 위한 것이다.

도 10의 예에서, 궤적들은 시간상 균등하게 간격을 두고 있는 궤적을 따라 점들로 표시된다. 따라서, 균등한 간격의 점들은 일정한 속도를 의미하고 점들 사이의 거리 증가(감소)는 가속(감속)을 의미한다. 흰색 원들은 최적의 궤적 지점들을 나타내는데 사용된다. 따라서, 목표 G₁의 경우, 최적 궤적은 일정한 속도로 도로를 따라 이어지는 직선 경로인 반면, 목표 G₂의 경우, 차량이 출구로 향하는 전환점에 가까워짐에 따라 최적 궤적이 점차 느려지는 것을 알 수 있다.

단계 1006에서, 각 목표 G₁, G₂에 대해 가장 유용한 계획(위 2)이 계산된다. 표시된 대로, 이들은 시간 t(자동차가 초기 위치 r_t에 있을 때)와 현재 시간 t + △t 사이의 실제 관측치 0을 고려한다. 이러한 관측치 0은 검은색 원들을 사용하여 도 10에 표시된 관측된 낮은 레벨 트레이스 τ를 포함할 수 있다.

그 맥락에서, 관측치 0은 대안적으로 또는 추가적으로 자동차의 현재 기동을 포함할 수 있다. 즉, 각 목표의 확률은 현재 자동차에 의해 실행되고 있는 기동에 따라 추정될 수 있다. 과거에 관찰된 기동들을 추가로 포함할 수 있다.

도 10에 명시적으로 표시되지는 않았지만, 위에서 서술한 것처럼, 확률론적 기동 감지가 적용되어 자동차의 가능한 현재 기동에 대한 확률 분포를 예측한다. 따라서, 현재 기동은 가능한 현재 기동들에 대한 분포 p(M│τ) 측면에서 확실히 알 수는 없지만 확률적으로만 알 수 있다. 이 문제는 먼저 p(M│τ)에서 현재 동작 M_j를 샘플링한 다음 해당 현재 기동 M_j에 대한 목표 확률 분포 p(G | 0)에서 샘플링하여 해결할 수 있다(즉, M_j를 포함하는 관측치 0).

가장 유용한 계획에서, 가장 유용한 궤적을 결정할 수 있으며 (자세한 내용은 아래 참조), 그 후 가장 유용한 궤적에 대해 전체 비용을 결정할 수 있다(아래 설명 참조). 이것은 또한 초기 위치 r_t에서 목표 위치 G_i까지의 완전한 궤적이라는 의미에서 전체 궤적이다. 가장 유용한 궤적은 실제 관찰된 궤적(즉, 도 10의 검은색 원)과 일치하는 시간 t와 t + △t 사이에 관찰된 부분이 있고, 그리고 추가적으로 대각선으로 음영 처리된 원들을 사용하여 도 10에 표시된 t + △t 이후 시간에 대한 미래 부분을 포함한다.

묘사된 예에서, 목표 G₁에 대해 가장 유용한 궤적의 관측된 부분(검은색 원들)과 미래 부분(대각선으로 음영 처리된 원들)이 해당 목표 G₁에 대한 최적의 궤적(흰색 원)과 합리적으로 잘 일치함을 알 수 있다. 따라서, 최적 궤적의 비용과 가장 유용한 궤적의 비용 간의 차이인 목표 G₁에 대한 비용 패널티는 상대적으로 낮다.

그러나, 목표 G₂의 경우, 관측된 궤적(검은색 원)이 최적 궤적(흰색 원)에서 상당히 크게 벗어나며, 이는 자동차가 최적 궤적에서 요구하는 범위까지 t + △t 시간에서 실패했기 때문이다. 이러한 불일치가 반드시 그 자체로 상당한 비용 패널티를 초래하지는 않는다(구현의 세부 사항들에 따라 다를 수도 있고 아닐 수도 있음). 그러나, 관찰된 행동의 결과로서, 가장 유용한 궤적의 미래 부분(즉, 시간 t + △t 이후 부분)에는 반드시 급제동(자동차의 현재 위치에서 G₂로 가는 최저 비용 경로는 자동차 상황을 감안할 때 급제동이 필요하다는 사실을 반영)이 포함되어야 함을 알 수 있다 - 이는 비용 함수에 의해 불이익을 받는다. 최적 궤적 비용과의 이러한 불일치는 목표 G₂에 대해 더 높은 비용 패널티를 의미한다.

단계 1008에서, 각 목표 G₁, G₂에 대해, 목표 우도 L(0|G)은 비용 패널티 측면, 즉, 단계 1004에서 계산된 최적 계획 비용과 해당 목표에 대해 단계 1006에서 계산된 가장 유용한 계획의 비용 간의 차이에서 계산된다. 이것은, 차례로, 목표 우도 및 목표 사전 확률에 기초하여 목표 사후 확률 P(G|0)가 계산될 수 있도록 한다(단계 1010).

사전 확률 P(G)는 특정 목표들의 "내재된" 확률에 대한 지식을 인코딩하는 데 사용할 수 있다. 예를 들어, 도 10의 시나리오에서, 우회전하는 자동차는 상대적으로 드물게 존재하며, 이는 P(G₂)<P(G₁)로 사전 인코딩될 수 있다. 이것은 G₂에 유리하게 목표 G₁를 효과적으로 편향시킬 것이다. 이러한 사전 지식이 없는 시나리오들의 경우, 각 목표는 특정 자동차의 개별 행동에 대한 관찰이 없으면 똑같이 가능성이 있다고 가정할 수 있다. 즉, P(G₁) = P(G₂).

위는, 목표가 주어지면 해당 목표에 대한 최적의 계획이 자동차의 초기 위치 r_t를 고려하여 결정될 수 있고, 그 목표에 가장 유용한 계획은 후속 시간 간격 △t의 관측치를 통해 결정될 수 있다고 가정한다. 또한, 최적(가장 유용한) 계획이 주어지면 최적(가장 유용한) 궤적이 결정될 수 있다고 가정한다. 이러한 방식으로 목표들을 궤적들에 대한 계획들에 맵핑하는 한 가지 메커니즘은 이제 서술할 A* 검색을 사용한다.

확률적 계획 인식 알고리즘

A* 검색

"A* 검색"은 매크로 동작들을 포함한 개방 루프 기동들에 대해 수행된다. 기동들은 적용가능성 조건들에 따라 필터링된다. 기본 기동들이 궤적들에 대한 분포들을 지정하면, 적절한 단일 궤적은, 예를 들어, 모드 또는 가장 가능성이 높은 궤적으로 선택될 수 있다.

A* 검색은 노드들 및 에지들의 가중치 그래프로 공식화된 알려진 방법이다. 현재 상황에서는 주어진 위치(시작 노드로 표시)에서 지정된 목표 G_i에 도달하기 위한 최적의 계획을 찾는 것을 목표로 한다. 그래프의 노드들은 기동들(기본 기동들 또는 매크로 동작들)을 나타내며, 목표는 상대적으로 낮은 비용으로 목표에 도달하는 일련의 노드들(및 시퀀스 기동들)을 찾는 것이다. 각 노드 n에 대해, "지금까지의 비용" g(n)은 시작 노드에서 노드 n까지의 비용으로 정의되고 휴리스틱 함수 h(n)은 n에서 목표까지의 비용 추정치를 제공한다. 검색은 시작 노드에서 시작되고, 각 노드에서 다음과 같이 정의된 가장 낮은 노드 비용을 갖는 다음 노드로 시퀀스를 확장한다.

환경에 있는 다른 모든 자동차들이 등속 모델을 사용한다는 단순한 가정이 사용될 수 있다.

초기 위치 r_t에서 목표 G_i까지 최적의 궤적을 찾기 위해, 검색은 시간 t와 위치 r_t에서 실행되는 자동차에 의한 기동으로 시작된다. 시간 간격 △t에서 관측치 0이 주어졌을 때 자동차의 현재 위치 r_{t + △t}에서 목표까지 가장 유용한 궤적을 찾기 위해, 검색은 감지된 현재 기동과 현재 위치 r_{t + △t}으로 시작된다.

전술한 기동 감지 방법을 사용하여 기동들을 감지할 수 있다. 이것은 일반적으로 가능한 현재 기동들에 대한 확률 분포를 초래할 것이다. 역 계획은 현재 예상되는 모든 기동에 대해 수행되어야 하며, 이는 목표들에 대해 상이한 사후로 이어질 수 있기 때문이다. 따라서, 현재 가능한 각 기동은 자체 목표 사후를 생성한다. 계산 효율성을 위해, n개의 가장 가능성이 높은 현재 기동들이 고려되고, 다른 기동들은 무시되며, 여기서 n은 적절하게 설정할 수 있는 메소드 파라미터이다.

현재 위치(현재 검색 노드)에 도달하기 위한 지금까지의 비용 g(n)은 기본 기동들에 지정된 경로들 및 속도들을 기반으로 현재 위치까지의 예상 주행 시간으로 정의될 수 있다.

목표까지 남은 비용을 추정하기 위한 비용 휴리스틱 h(n)은 제한 속도에서 직선을 통해 현재 위치에서 목표 위치까지의 주행 시간으로 제공된다. 참고로, 검색을 효과적으로 안내하기 위해, h(n)은 검색을 안내하기 위해 남은 최소 비용의 추정치만 제공하면 된다. 따라서, 성능에 영향을 주지 않고 상대적으로 대략적인 가정을 할 수 있다.

최적의 계획을 찾은 후, 계획의 기동들 전반에 걸쳐 완전한 궤적이 생성된다. 그런 다음, 속도 평활화가 전체 궤적에 적용되고, 전체 비용 함수가 계산되어 (아래 비용 함수 섹션 참조) 계획의 최종 비용을 얻는다. 이 마지막 단계(평활화 및 전체 비용 기능 적용)는 아래 제동 예에서와 같이 속도를 기반으로 추가 "단서들(clues)"을 포착할 수 있게 한다.

이미 관찰된 궤적의 어떤 부분에도 속도 평활화가 적용되지 않는다. 그렇지 않으면, 속도 평활화의 효과는 특정 목표들을 암시하는 증거를 제거하는 것일 수 있다(도 10의 예에 대한 자세한 내용은 아래 참조).

차량이 기동 중 중간에 있는 경우들(예를 들어, 차선 변경)을 설명하기 위해, 앞으로 더 계획하기 전에 완료할 수 있도록, 자동차의 현재 실행 중인 기동을 인식할 필요가 있다.

검색 공간을 줄이기 위해, 기본 회전 및 신중한 기동들은 매크로 동작들 외부에서 사용되지 않으므로 검색 공간에서 제거될 수 있다. 차선 따라 가기 기동은, 최종 조건이 기본값으로 고정된 길이로 설정된 경우 매크로 동작 외부의 기본 기동으로 여전히 유용할 수 있다.

현재 예들은 역 계획 중 외부 행위자들 간의 충돌들을 확인하지 않는다. 이것이 가능하더라도 전체 프로세스를 더 비싸게 만들 것이다. 또한, 다른 차량들의 일정한 속도와 같은 일부 단순화된 가정들로 인해, 충돌이 불가피하게 발생하는 상황이 있을 수 있다. 아래에 설명된 다중 에이전트 MCTS 방법은 이러한 충돌 검사를 처리할 수 있다.

또는, 역 계획의 일부로 가능한 충돌들을 추론하도록 프로세스를 확장될 수 있다.

A* 검색과 관련하여 위에서 설명한 가정은 계산 효율성과 성능 사이에 좋은 균형을 제공하는 것으로 밝혀졌다. 물론, 일정하지 않은 속도 모델들과 같은 사이한 가정들의 세트들이 사용될 수 있음을 이해할 수 있을 것이다. 또 다른 예로서, 위의 내용은, 기동과 관련된 가장 가능성이 높은 궤적만을 고려하여 본질적으로 검색 문제를 결정론적 문제로 전환한다. 그러나, 이것은 전체 또는 잘린 궤적 분포를 기반으로하는 확률적 검색으로 동일하게 확장될 수 있다. 즉, 위에서는 단일 궤적들의 형태의 전체/부분 궤적 모델들을 고려하는 반면, 기술들은 전체/부분 궤적 분포들에도 적용될 수 있다.

멀티 스레딩은 각 목표 G에 대해 독립적인 스레드들을 사용하여 프로세스 속도를 높이는 데 사용될 수 있다. 자동차들이 독립적인 목표들을 가지고 있다는 추가 가정하에, 다른 자동차에 대해 하나의 프로세스/스레드를 사용하여 추가 병렬화를 달성할 수 있다.

제동

위의 방법에서 제동이 별개의 기동으로 인식되지는 않지만, 이 방법은 목표들의 가능성에서 제동을 설명할 수 있다.

예를 들어, 도 10에서 도시되고 위에서 서술된 시나리오를 고려한다. 자동차의 초기 위치에서 G2로의 최적 계획은 우측 출구 매크로 동작에 의해 제공된다. 속도 평활화를 적용한 후, 결과는 자동차가 전환점에 도달할 때까지 지속적으로 느려지는 궤적이다. 이 최적 궤적의 비용은 C2로 표시된다.

자동차가 차선을 따르는 것이 관찰되었다고 가정하면, 이제 전환점에 반쯤 가까워지고 G2의 최적의 궤적과 비슷하게 감속한다. 따라서, G2에 대한 궤적이 경쟁하면, C2와 유사한 비용의 궤적이 생성된다. 반면에, 초기 상태에서 G1에 대한 최적의 궤적은 그러한 제동을 수반하지 않을 것이며, (시간 차이 및 급작스러운 움직임으로 인해) 상당한 비용 차이를 초래할 것이다. 따라서, G2의 사후 확률은 증가하는 반면 G1의 확률은 감소한다.

(제외로: 이미 관찰된 궤적의 어떤 부분에도 속도 평활화가 적용되지 않는다는 점이 위에서 언급되었다. 그 이유는 다음 예에서 분명하다. 속도 평활화가 전체 궤적에 적용되면, 평활화는 이미 관찰된 차선 따라 가기 기동의 일부에서 속도들도 감소시킨다. 제동이 더 이상 그렇게 갑작스럽지 않기 때문에 이것은 더 낮은 비용 패널티로 이어질 것이다. 즉, 궤적을 초기 관측 위치에서 최적 궤적과 더 비슷하게 만든다. 따라서, 평활화는 과거 궤적을 수정할 수 없는 상수들로 취급하는 것이 적절하다.)

이제 차가 차선을 따라 가지만 감속하는 대신 일정한 속도로 관찰되는 것으로 가정하자. 이 궤적이 G2까지 계속되면, 갑작스런 제동이 수반되어 C2보다 훨씬 높은 비용이 발생한다. 반면에, 목표 G1(차선 유지)까지 궤적을 계속하는 것은 본질적으로 초기 상태에서 G1에 대한 최적의 계획이다. 따라서, G2는 사후 확률이 감소하고 G1이 증가한다.

마지막으로, 차가 차선을 따라가는 것이 관찰되고, 갑자기 전환점 근처에서 감속한다고 가정하자. 이러한 갑작스런 제동은 G2 및 G1 모두에 대해 상당한 비용 불이익을 초래할 것인데, 이는 초기 상태에서 최적의 궤적에 있지 않기 때문이다. 따라서, 두 목표들의 비용이 증가하여 두 목표들의 상대적 확률에 작은 변화가 발생한다.

목표 트리들을 통한 목표 인식

역 계획 방법의 대안으로, 결정 트리를 사용하여 목표 감지를 구현할 수 있다.

목표 인식을 위한 의사 결정 트리의 예가 도 11에 도시된다.

목표들의 세트 G가 주어지면, 목표들에 대한 사후 분포는 베이즈 정리 P(G|0) ~ L(0|G)P(G)를 사용하여 계산된다. 목표 G에 대한 우도 L(0|G)은 G와 함께 생성될 수 있는 G와 관련된 트리에 의해 계산된다. 트리는 [0,1] 범위에서 정규화된 점수를 계산하여 목표의 우도를 나타내며, 0은 목표에 대한 지원이 없음을 나타낸다.

예시적인 번호들을 사용하는 시나리오 2(오른쪽 출구)의 목표 G2에 대한 예시적인 트리가 오른쪽에 도시된다.

트리는 다음과 같은 몇 가지 조건들을 테스트한다.

차량이 목표를 위해 올바른 차선에 있는지 여부

차량이 올바른 방향을 가리키는지 여부

출구 지점이 자동차의 다음 줄에 있는지 여부(즉, 자동차에 더 가까운 동일한 차선에 다른 출구들이 없음)

자동차가 감속하고 있는지 여부

각 분기에서, 트리는 조건을 테스트하고, 점수(1로 시작)에 [0,1] 범위의 일부 인수를 곱하여 트리 종료 노드에서 최종 점수를 얻는다. 상이한 분기들은 다른 조건들에 대해 테스트할 수 있으며, 분기들에 제공된 인수들은 테스트 조건들의 다른 중요성을 반영하기 위해 상이할 수 있다. 곱셈 인수에 대한 대안은 트리 분기들 따라 인수들을 추가하고 노드 깊이를 종료하여 정규화하는 것이다.

트리들을 사용하는 이 방법에는 두 가지 주요 이점들이 있다. 트리들은 평가하기가 저렴하고, 트리들은 사람이 쉽게 해석할 수 있다(설명 가능성 추가).

의사 결정 트리는 회귀 트리 학습을 위한 C4.5 또는 알고리즘들과 같은 알고리즘을 사용하여 실제 또는 시뮬레이션된 주행 행동 데이터(예를 들어, 시뮬레이션 또는 CCTV)를 기반으로 구성될 수 있다. 예를 들어, 이진 특성들의 모음(테스트 조건들)을 지정할 수 있으며, 트리 학습 알고리즘은 특정 목표들에 대해 기록된 지상 검증 데이터를 바탕으로 최적의 특징들의 하위 집합과 부분 점수들을 찾는다.

목표들로부터 궤적들을 예측

자동차의 가능한 궤적들과 주어진 목표에 대한 관련 확률들을 예측하기 위해, 역 계획에 사용된 것과 동일한 A* 검색 방법을 사용할 수 있다. 최적의 계획을 찾은 후 A*를 종료하는 대신, 고정 시간 예산이 부과되고 알고리즘이 관련 비용들(일부 고정된 수의 계획들까지 가능)로 계획들의 세트를 계산할 수 있다. A* 검색이 목표에 도달하는 노드를 찾을 때마다, 해당 계획이 계획들의 세트에 추가된다. 궤적들은 계획의 기동들에 의해 주어진 부분 궤적들을 연결하여 계획들에서 생성된다.

계획들에서 추출된 궤적들에 대한 분포는 다음과 같은 소프트맥스 분포(궤적 모델)를 사용하여 계산할 수 있다.

여기서

은 목표에 대한 n번째 전체 궤적,

는 궤적

의 비용(평활화 후의 전체 비용), 및

은 궤적

에 대한 배율 인수이다(위에서 언급한 바와 같이, 표기법

은 주어진 기동 M_j에 대한 부분 궤적 T_j와 구별하기 위해 목표에 대한 n번째 전체 궤적에 사용된다). 이것은 최적에 더 가까운 궤적들이 더 가능성이 높다는 가정을 인코딩한다. 배율 인수는 관찰된 데이터를 기반으로 특정 궤적들의 가중치를 낮추는 데 사용될 수 있다. 즉, 궤적 예측 모델이 관련 예시들에서 학습 될 수 있도록 한다. 또는, 상수 배율 인수(예를 들어, 값 1)를 사용할 수 있다.

위의 소프트맥스 궤적 모델은 RRT를 통해 얻은 궤적 모델의 대안으로 사용할 수 있다.

역 계획에서와 같이, 이러한 궤적들의 세트는 각 예측 현재된 기동에 대해 생성되며 가장 가능성이 높은 현재 기동들과 같은 일부 하위 집합에 초점을 맞춘다. A*는 현재 기동을 완료한 후 시작되며, 최종 궤적들은 현재 기동의 나머지를 포함한다.

이것은 하나의 최적 궤적이 아닌 다양한 그럴듯한 궤적들을 예측하고, 이는 다중 궤적들이 (거의) 최소 비용을 달성하지만 자아 차량의 일 부분상에서 상이한 행동들을 요구할 수 있는 상이한 예측들로 이어지는 상황이 있기 때문에 유익하다.

목표 인식과 MCTS 통합

목표 인식과 위의 MCTS 기동 계획 프로세스를 통합하기 위한 구체적인 메커니즘이 이제 서술될 것이다. 이 조합은 일반적인 상호 작용 인식 기동 플래너를 제공한다.

현재 기동 및 목표 샘플링

도 12는 역 계획의 결과들을 MCTS 롤아웃의 일부로 적용할 수 있는 메커니즘의 개략적인 개요를 보여준다. 이것은 위에서 설명한 그림 15와 관련하여 위에서 설명한 원칙을 적용하며, 여기서 MCTS는 다른 에이전트(들)에 대한 확률적 예측들의 상이한 샘플링들로 여러 번 수행된다.

기동 검출기(1102)는 전술한 방식으로 대상 행위자에 대한 현재 기동 확률 분포를 검출한다. 각 기동

에 대해(M은 이용 가능한 기동들의 유한 세트임), 이것은 관찰된 낮은 레벨의 추적 τ, 즉 P(M|τ)가 주어지면 대상 행위자가 현재 그 기동을 구현하고 있을 확률을 제공한다.

각 MCTS 슈퍼 반복은 다음과 같이 시작된다. 각각의 다른 자동차에 대해:

1. 예측된 현재 기동들 및 그 확률들의 세트에서 현재 기동을 샘플링한다. 즉, P(M|τ)에 기반한 현재 기동 M_j를 샘플링한다(블록 1104, 도 12).

2. 샘플링된 현재 기동에 해당하는 목표 사후 확률 P(G|0)로부터 목표를 샘플링한다. 즉, 샘플링된 현재 기동 M_j(관측치들 0의 일부를 형성하는 것으로 간주 될 수 있음)로 위의 역 계획 단계들을 적용한다.

이러한 샘플들, 즉, 샘플링된 현재 기동 M_j 및 샘플링된 목표 G_i는 MCTS 프로세스의 전체 슈퍼 반복에서 사용된다. 위의 단계 1과 단계 2는 각 MCTS 슈퍼 반복이 시작될 때 수행되며, 반복은 (루트 노트에서 터미널 노드까지) 해당 수퍼 반복에서 트리의 모든 노드에 적용된다.

도 12에서, 속기 표기법 P(G|M_i) 및 P(G|M_k)는 각각 현재 기동 M_i 및 M_j가 주어진 목표 사후들을 표시하는데 사용된다. 관측치들 O는 단순히 현재의 기동보다 더 광범위할 수 있다는 점에 유의해야 한다(예를 들어, 이전 기동(들)의 시퀀스를 포함). 이 표기법을 사용하여, 위의 단계 1에서, 기동 M_i가 샘플링되면, 이후, 단계 2에서부터 목표 사후 확률 P(G|M_i)가 샘플링되는 반면, 기동 M_j가 샘플링되면, 목표 사후 확률 P(G|M_k)가 사용된다.

결합된 사후에서 샘플링하는 것은 일관성없는 롤아웃들을 방지한다. 예를 들어, 자동차에 두 개의 가능한 목표들이 있고, 동일한 확률로 두 개의 예측된 현재 기동들이 있는 상황을 고려해보자. 제1 기동에 대한 목표 사후들은 제1 목표에 모든 확률을 두는 반면, 제2 기동에 대한 목표 사후는 제2 목표에 대한 모든 확률을 둔다. 따라서, 결합된 목표 사후는 두 목표들 모두에 동일한 확률을 부여한다(반대로, 결합된 목표 사후에서 목표를 샘플링한 다음 현재 기동을 샘플링하는 경우, 샘플링된 목표에 대한 궤적이 없는 현재 기동으로 끝날 수 있다(예를 들어, 제1 기동에서 제2 목표까지의 경로가 없다)).

궤적 샘플링이 있는 단일 에이전트 MCTS

서로의 자동차에 대해 샘플링된 현재 기동 및 목표가 주어지면, 해당 움직임 궤적들은 예측된 궤적들 및 확률들의 관련된 세트로부터 샘플링된다. 이러한 궤적들은 롤아웃을 따라 각 자동차의 움직임들을 예측하는데 사용된다.

자아 계획은 현재 상태에서 적용할 수 있는 매크로 동작들을 포함하여 일련의 폐쇄 루프 기동들에 대해 수행된다. 많은 경우들에서, 하나의 매크로 동작만으로도 에고 자동차의 목표를 달성하기에 충분할 수 있다. 목표는 계획 중에 가능한 한 빨리 이러한 매크로 동작들을 찾는 것이다. 간단한 접근 방식은 매크로 동작이 항상 먼저 시도되도록 기동들의 세트를 주문하는 것이다. 대안으로, 주어진 목표에 대해, 일반적으로 목표를 달성하는 매크로 동작을 반환하는 "최선의 제1 추측(best first guess)" 기능이 제공될 수 있다. 현재 매크로 액션을 적용할 수 없는 경우(예를 들어, 에고 자동차가 중간 차선에 있을 때 왼쪽으로 나가기), 그런 다음 이상적으로 플래너는 이를 적용할 수 있는 방법을 신속하게 찾아야 한다(예를 들어, 먼저 기본 차선을 좌측으로 변경하는 기동을 사용한 다음 왼쪽 출구에 대한 매크로 동작 사용).

자아 차량의 기동을 선택한 후, 기동이 끝날 때까지 환경이 전방으로 시뮬레이션된다. 여기에는, 에고 차량과 동일한 시점까지 다른 자동차들의 궤적들을 전방 시뮬레이션하는 것은 물론 환경에서 다른 모델링된 프로세스들도 포함된다. 전방 시뮬레이션 중 자아 차량이 다른 차량들과 충돌하는지 확인하기 위해 충돌 검사기가 적용된다. 충돌이 발생하면, 검색 트리의 해당 분기가 즉시 "절단(cut)"된다(예를 들어, 더 이상 탐색되지 않음).

MCTS는 아래 섹션에 정의된 비용 함수를 사용한다. MCTS가 목표를 달성하는 계획들만 생성하도록 보장하기 위해, 비용 함수는 롤아웃이 목표에 도달한 경우에만 적용된다. 보다 정확하게는, 속도 평활화를 적용한 후, 롤아웃의 기동들에 의해 생성된 궤적에 비용 함수가 적용된다. 그런 다음, 평활화된 궤적의 결과 비용이 검색 트리 위로 전파된다. 따라서, MCTS는 목표를 달성하는 실행 가능한 계획들만 검색하고 그것들 중 가장 좋은 계획을 검색한다.

매크로 동작들을 사용한다는 것은, 성공적인 계획들에 일반적으로 1 내지 5 개의 기동들(매크로 동작들을 포함)이 포함된다는 것을 의미한다. 따라서, 검색 속도를 높이기 위해, MCTS 검색을 깊이 5에서 절단(종료)할 수 있다.

목표 인식 기능이 있는 단일 에이전트 MCTS에 대한 의사 코드 알고리즘은 부록 B에 제공된다.

속도 향상

가능한 속도 향상은 다음과 같다:

예를 들어, 롤아웃들을 생성하고 통계들을 업데이트하기 위해 여러 스레드들을 사용하여 MCTS에서 다양한 정도들의 멀티-스레딩을 사용하는 것이 가능할 수 있다.

계획 품질을 낮추는 대신 폐쇄 루프 기동들이 아닌 개방 루프 기동들을 계획함으로써 계산 비용들을 줄일 수 있다. MCTS 계획 후 실행되는 기동은 항상 폐쇄 루프이다.

비용 함수

비용 함수는 역 계획 및 MCTS에 사용되어 주행 궤적의 비용을 정량화한다. 궤적 T는 차량이 따라가는 기준 경로와 경로를 따른 일련의 목표 속도들로 구성된다. 비용 함수는 궤적을 입력으로 받아 실제 값 비용 C(T)를 반환한다. 비용 함수는 주어진 궤적에 대해 평가하기에 저렴해야 하며, 계산 비용은 최대 0(|T|)까지 증가해야한다.

예를 들어, 비용은 여러 비용 요소들의 가중(선형) 합계로 정의될 수 있다.

여기에는 다음이 포함된다.

시간: 자동차가 궤적을 완료하는데 얼마나 많은 시간이 필요한가? (참고: 목표 속도들에 따라 달라지므로 참조 경로의 길이와 동일하지 않다.)

곡률: 궤적은 얼마나 "굽어 있는가"? 곡률이 더 좁아지면 비용이 기하급수적으로 높아진다. 각속도를 프록시로 사용할 수 있다.

속도 변화: 궤적을 따라 속도가 얼마나 변하는가? 높은 변화율(예를 들어, 갑작스러운 감속)은 기하 급수적으로 더 높은 비용을 초래한다.

"안전": 안전에 대한 프록시로서 "비용 요소"는 궤적 동안 다른 차량과의 최소 거리의 함수로 계산될 수 있으며 지수 비용이 부과된다(거리 임계 값을 초과하는 차량은 무시됨). 즉, 가장 작은 거리가 줄어들수록 비용이 기하급수적으로 증가한다.

이러한 비용 요소의 대부분은 궤적을 통해 시간을 앞당기고 이전/새로운 위치 벡터들 및 목표 속도들을 기반으로 간단한 계산들을 수행하여 반복적으로 계산할 수 있다. 비용 요소들의 가중치는 경험적 테스트를 기반으로 조정되어야 한다.

정규화

다른 비용 요소들의 비교 가능성을 보장하려면, 모든 비용 요소들을 동일한 범위 [0,1]로 정규화하는 것이 좋다. 또한, 가중치들이 음수가 아니고 합이 1이 되도록 가중치를 정규화하는데 도움이 된다. 이러한 정규화 단계들은 C(T)가 [0,1]에 있는지 확인하며, 이는 비용들이 [0,1] 범위에 있다는 UCB/UCT의 가정을 충족한다.

비용 요소들이 최소/최대 함수(예를 들어, 최대 요율, 다른 자동차들과의 최소 거리)로 정의되면 정규화가 더 쉬워질 수 있다.

대안적이고 저렴한 접근 방식은 비용들을 궤적들보다는 기동들과 연관시키는 것이다. 예를 들어, 계획의 비용을 계획의 기본 기동들의 수로 정의한다. 이것은 기동들에 의해 생성된 궤적들에 변동성이 없거나 거의 없는 경우(예를 들어, 항상 동일한 폴리-스플라인을 따르는 차선 변경) 적절한 접근 방법이 될 수 있다. 그러나, 기동들이 궤적들의 묶음을 생성하거나 궤적들이 차량 구성과 같은 동적 측면들에 의존할 수 있는 경우(예를 들어, 가까운 차량 뒤의 차선 변경 대 가깝지 않은 차량 뒤의 차선 변경), 이후, 동일한 기동이 상황에 따라 상당히 상이한 궤적들을 초래할 수 있기 때문에 기동들에 고정 비용을 할당하는 것이 적절하지 않을 수 있다.

예시 시나리오들

이제 목표들의 개념을 설명하고 목표 인식이 자아 자동차의 결정에 어떻게 영향을 미칠 수 있는지 강조하기 위해 3개의 예시 시나리오들을 서술할 것이다. 시나리오들은 또한 제안된 방법에 대한 몇 가지 경계 상황들을 보여준다. 3개의 시나리오들은 각각 도 14a 내지 도 14c에 표시된다.

시나리오 1: 저속 트럭을 추월하는 자동차(도 14a)

자동차 2는 느리게 움직이는 트럭 1 뒤에 있다. G1이라고 표시된 자동차 2의 목표 위치가 표시된다. 이 시나리오에서는, 자동차 2가 트럭을 추월하기 위해 자아 차선으로 이동할 수 있다.

근시 기준선만으로는 자동차 2의 차선 따르기 기동에 대부분/모든 사후 확률을 배치하여 차선 변경이 임박할 것이라고 예측하지 못하며, 이는 차선 변경이 미래 기동들에 대한 이유가 아니기 때문이다. 자동차 2가 자아 자동차와 유사한 비용 함수(즉, 시간 요소 포함)를 사용하고 G1을 달성하기 위해 자동차 2에 대해 역으로 계획한다고 가정하면, 이 방법은 자동차 2에 대한 차선 변경 기동과 속도 제한에서 차선 따르기를 예측할 수 있다. 자동차 2가 자아 자동차에서 좋은 거리에 있다면, 이 예측은 자아 자동차가 반응하지 않게 할 것이다. 그러나, 자동차 2가 에고 자동차에 가까우면(도면 참조), 에고 자동차는 속도를 줄이고 자동차 2와 거리를 유지하기로 결정할 수 있다.

시나리오 2: 출구로 차선을 변경하는 자동차(도 14b)

다른 차량들 G1과 G2에 대한 두 가지 가능한 목표들은 도로 레이아웃을 기반으로 생성된다. G1/G2는 모두 자동차 2에서 가능하지만, G1만 자동차 3에서 가능하다.

자동차 2가 오른쪽 차선 변경을 실행하는 것이 관찰된다. 자동차 2에 대한 역 계획과 가능한 각 목표에 따라, 차선 변경은 G2를 매우 잘 나타낸다. 차선 변경 후, G2에 대한 최적의 계획은 속도를 줄인 후(속도 평활화로 인해) 우회전 후 후속 차선을 규정한다. 이 순서를 고려하고 자아 차량의 목표가 G1이라고 가정하면, MCTS 플래너는 자동차 2의 감속이 자아 차량의 목적 함수에 너무 많은 불이익을 준다는 것을 깨달을 수 있고(이는 자아 차량도 속도를 늦추게 하기 때문이다), 따라서 자동차 2가 차선 변경을 완료한 후 차선들을 왼쪽으로 변경하기로 결정할 수 있다.

근시 기준선은 자동차 2가 오른쪽 차선으로 변경되고 있다는 것만 인식할 수 있지만 후속 감속을 예측하지 못한다. 기준선은 여전히 차선 변경을 실행할 수 있지만, 감속이 이미 진행된 후에 만 가능하다.

시나리오 3: 대기중인 자동차 앞에서 이동(도 14c)

도로 레이아웃에 따라 다른 자동차들에 대한 4개의 가능한 목표들이 표시된다. 에고 자동차가 교차로에서 기다리고 있다.

자동차 3의 감속이 관찰되지 않아, G2가 가장 가능성이 높다는 것을 나타낸다(그러나, G3/4는 여전히 가능하지만 강력한 제동 비용이 발생함).

자동차 2가 G3에 도달하기 위한 계획과 일치하는 표시된 위치에서 정지했다. 자동차 3이 다가오고 일정한 속도를 사용하기 때문에 자동차 2는 정지하고 자동차 3이 지나갈 때까지 기다린 다음 G3로 우회전해야 한다. 반대로, 표시된 위치에서 정지하는 것은 G1 또는 G4를 나타내지 않는다(G2는 자동차 2의 유효한 목표가 아님).

추론된 목표들 및 계획들의 집합체를 감안할 때, 자아 자동차는 자동차 2가 자동차 3이 지나가기를 기다리는 동안 도로에서 안전하게 좌회전할 수 있음을 인식할 수 있다.

근시 기준선은 자동차 2의 정지 기동을 인식하지만, 후속 기동들을 예측할 수 없다.

데이터 기반 행동 모델들

위에서 설명한 것처럼, 행위자들의 학습된 행동은 실제 시뮬레이션들을 제공하기 위해 MCTS 시뮬레이션들 내에서 사용될 수 있다. 이러한 생성 행동 모델들은 역 계획과 함께 사용하거나 역 계획의 대안으로 사용할 수 있다. 즉, 학습된 생성 행동 모델들은 역 계획을 구현하지 않고 사용할 수 있다(예를 들어, 목표들, 기동 들 등을 추론할 필요없이 학습된 모델을 사용하여 하나 이상의 궤적을 간단히 생성할 수 있음). 언급한 봐와 같이, 이러한 모델들의 예시들에는 공간 마르코프 모델들 및 신경 네트워크가 포함된다.

예를 들어, 생성적 행동 모델은 모니터링된 주행 영역 내의 복수의 공간 영역들에 기반한 공간적 마르코프 모델(SMM)일 수 있으며, 여기서 다음 중 적어도 하나: 각각의 공간 영역과 관련된 추정된 점유 확률, 및 복수의 공간 영역 쌍들 각각과 관련된 추정된 천이 확률이 계산된다.

공간 영역들은 모니터링되는 주행 영역에 중첩된 그리드의 셀들일 수 있다. 이것은 도로 구조 및/또는 모니터링되는 주행 영역의 다른 구조를 고려할 수 있으며, 예를 들어, 수동으로 주석을 달거나 지도에서 결정될 수 있다.

표기법 p_i는 공간 영역 i에 대한 추정된 점유 확률을 의미하고, p_ij는 공간 영역 i에서 공간 영역 j로의 천이의 추정된 확률을 의미한다. SMM에서, p(T|모델)는 모델이 주어진 주행 경로(궤적) T에 의해 횡단되는 일련의 그리드 셀들(또는 다른 공간 영역들)과 관련된 점유 및/또는 천이 확률을 기반으로 결정될 수 있다.

주행 행동 데이터는 이미지 데이터 및/또는 움직임 센서 데이터 등과 같은 모든 형태의 센서 데이터를 포함할 수 있다. 데이터는 적절한 방식으로 수집할 수 있지만, CCTV(폐쇄 회로 텔레비전) 시스템들은 특히 CCTV 범위가 양호한 도시 환경에서 주행 행동 데이터를 수집하는데 특히 편리한 수단을 제공한다. 예를 들어, 본 발명은 복잡한 주행 상황(예를 들어, 복잡한 원형 교차로들, 다중 차선 교차로들, 사각 지대들 등)으로부터의 CCTV가 주행 행동 데이터의 풍부한 소스를 제공한다는 것을 인식한다.

다음 예들에서는, CCTV 이미지 데이터와 같은 실제 주행 행동 데이터는 훈련용 모델을 생성하고 주행 중 행위자들의 행동을 예측하는데 사용된다.

일정 기간 동안 고정된 영역에 대한 실제 데이터가 수집될 수 있다. 데이터가 수집될 수 있는 기간은, 예를 들어, 해당 지역을 통과하는 차량들의 정확한 표현을 생성하기 위해 24시간이 될 수 있다. 교차로와 같이 위치가 작을 수 있다. 데이터 수집 가능성을 최대화하기 위해 많은 양의 차량들이 통과하는 영역이 선택될 수 있다.

도로 레이아웃(주행 상황)에 대한 데이터가 수집된다. HD(고화질) 지도와 같은 지도에서 가져오거나 CCTV 영상에서 수집하여 수동 또는 자동으로 입력할 수 있다. 예를 들어, CCTV 영상에 수동으로 주석을 달 수 있다.

수집된 데이터에서 행위자들의 위치들 및 움직임들에 대한 정보는 수집된 데이터에서 추출되어 정상적인 주행 동작의 공간적 마르코프(상태 천이) 모델(SMM)을 구축하는데 사용된다. 상태 천이 모델은 정상적인 동작의 단순화된 표현을 제공하기 위해 사용될 수 있는 이산 셀 근사 모델이다. 이를 위해, CCTV 영상에 캡처된 위치에 그리드를 적용할 수 있다. 이 그리드는 셀당 5 내지 10cm 범위에 있을 수 있다.

그런 다음 각 그리드 셀에서 에이전트들의 행동을 해당 기간에 걸쳐 분석할 수 있다. 이 분석에서 추출된 정보는 예를 들어 수집된 데이터 기간 동안 각 그리드 요소의 점유 빈도 및 각 요소들에서 주변 요소들로의 기간 동안 이루어진 천이들의 수를 포함할 수 있다. 이 정보는 점유 확률 추정값 p_i을 각 그리드 셀에 할당하고 천이 확률 추정값 p_i,j을 각 그리드 셀들 i, j의 각 쌍에 할당하는 데 사용될 수 있다.

예를 들어, 도 16은 CCTV 카메라의 시야 내에서 도로 레이아웃에 대해 결정된 SMM을 도시한다. 이 경우 도로 레이아웃은 고정 그리드가 겹쳐진 비교적 복잡한 교차로의 일부이다. 그리드의 두 셀들은, 예를 들어, 참조 기호 i 및 j로 표시되며 실제 차량들의 관찰을 통해 결정된 점유 확률 p_i 및 p_j를 갖는다. 셀 i와 셀 j 사이의 천이 확률 p_i,j는 배우가 셀 i에서 셀 j로 직접 이동할 확률이며 관찰을 통해 결정된다.

이해되는 바와 같이, 상기 서술은 예상되는 차량 동작을 모델링하기 위한 적절한 모델들의 일부 예들 만을 고려한다. 적절한 모델들의 다른 예들은 마르코프 의사 결정 프로세스 모델과 데이터에 대한 보상들을 포함한다. 이 경우, 훈련은 마르코프 의사 결정 프로세스 모델을 피팅하고, 데이터에 대한 보상들에 의해 수행된다.

하드웨어 레벨에서, AV의 온보드 컴퓨터 시스템(A1)은 위의 기능들을 수행하는 알고리즘들을 실행할 수 있는 실행 하드웨어를 포함한다. 실행 하드웨어는 범용 또는 특수 목적의 실행 하드웨어 또는 이들의 조합일 수 있지만, 일반적으로 중앙 처리 장치(CPU)와 같은 하나 이상의 프로세서를 포함하며, 가속기(예를 들어, GPU)들, FPGA(Field Programmable Gate-array)들 또는 기타 프로그래밍 가능한 하드웨어 및/또는 ASIC(application-specific integrated circuit) 등(이에 한정되지 않음)과 같은 특수 하드웨어와 함께 작동할 수 있다. 안전하고 신뢰할 수 있는 연산을 보장하기 위해 충분한 정확성과 속도(종종 실시간)로 정교하고 복잡한 ML/AI 모델들을 사용하는 복잡한 데이터 처리 연산들을 수행해야 하는 경우, 온보드 컴퓨터 시스템은 문제의 모델들 및 알고리즘들을 구현하도록 맞춤화된 특수 컴퓨터 하드웨어를 사용하여 매우 정교할 수 있다. 특히, AI 분야에서 혁신이 진행되는 속도를 감안할 때, 하드웨어 레벨 및 기능/소프트웨어 레벨 모두에서 AV 온 보드 컴퓨터 시스템 AI의 아키텍처는 다양한 형태들을 취할 수 있음을 알 수 있을 것이다. 여기서, 데이터 처리 컴포넌트(A2), 예측 컴포넌트(A4) 및 AV 플래너(A6)와 같은 컴퓨터 시스템에 구현된 기능 컴포넌트 등은 컴퓨터 시스템에 의해 구현된 특정 기능의 높은 레벨들의 표현, 즉, 상황들에 적합한 컴퓨터 시스템의 범용 및/또는 특수 하드웨어(의 조합)에 의해 수행되는 기능들이다.

부록 A - 시나리오 서술 예

부록 B

Claims (45)

1. 자율 차량(AV) 계획 방법으로서,
   AV와 관련된 센서 입력들을 수신하는 단계와;
   직면한 주행 시나리오를 결정하기 위해 상기 AV와 관련된 센서 입력들을 처리하는 단계와;
   AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동(maneuver)들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고
   상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,
   상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정되며, 그리고
   상기 외부 에이전트의 예상되는 행동은 상기 센서 입력들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 생성 행동 모델을 적용함으로써 시뮬레이션되고, 상기 생성 행동 모델은 관찰된 실제 주행 행동의 예들을 기반으로 훈련된 기계 학습(ML) 모델인 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
2. 제1항에 있어서,
   객체 추적은 상기 외부 에이전트의 관찰된 추적을 결정하기 위해 상기 센서 입력들에 적용되고, 상기 외부 에이전트의 예상되는 행동은 상기 관찰된 추적에 기초하여 시뮬레이션되는 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
3. 제1항 또는 제2항에 있어서,
   상기 생성 모델을 훈련시키는데 사용되는 관찰된 실제 주행 행동의 예들 중 적어도 일부는 폐쇄 회로 텔레비전 데이터로부터 추출되는 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
4. 제1항 내지 제3항 중 어느 한 항에 있어서,
   상기 생성 행동 모델은 훈련된 신경 네트워크를 포함하는 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
5. 제1항 내지 제3항 중 어느 한 항에 있어서,
   상기 외부 에이전트의 예상되는 행동은, 상기 직면한 주행 시나리오의 주행 영역에 대해 학습된 공간적 마르코프 모델의 학습된 점유 확률 및/또는 천이 확률을 사용하여 시뮬레이션 되는 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
6. 제1항 내지 제5항 중 어느 한 항에 있어서,
   상기 트리 검색 알고리즘은 확률적 트리 검색 알고리즘인 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
7. 제6항에 있어서,
   상기 트리 검색 알고리즘은 몬테카를로 트리 검색(MCTS) 알고리즘인 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
8. 제1항 내지 제7항 중 어느 한 항에 있어서,
   상기 주행 시나리오는 정의된 시나리오 서술 언어에 따라 주행 시나리오 파라미터들을 센서 입력들로부터 추출함으로써 결정되는 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
9. 제2항 내지 제8항 중 어느 한 항에 있어서,
   상기 생성 행동 모델은 또한 하나 이상의 자아 차량(ego vehicle) 파라미터 및/또는 상기 주행 시나리오의 하나 이상의 파라미터에 적용되는 것을 특징으로 하는
   자율 차량(AV) 계획 방법.
10. 자율 차량(AV) 계획 방법으로서,
    AV와 관련된 센서 입력들을 수신하는 단계와;
    직면한 주행 시나리오를 결정하기 위해 상기 센서 입력들을 처리하는 단계와;
    AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고
    상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,
    상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정되며, 그리고
    상기 외부 에이전트의 예상되는 행동은 상기 센서 입력들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 역 계획 방법을 적용함으로써 시뮬레이션되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
11. 제10항에 있어서,
    객체 추적은, 상기 직면한 주행 시나리오에서 적어도 하나의 외부 행위자를 추적하고, 시간 간격에 걸쳐 상기 외부 행위자의 관찰된 추적을 결정하기 위해 상기 센서 입력들에 적용되고,
    상기 역 계획 방법은:
    상기 직면한 주행 시나리오에서 상기 외부 행위자에 대해 이용 가능한 목표들의 세트를 결정하는 단계와;
    상기 이용 가능한 목표들 각각에 대해, 예측된 궤적 모델을 결정하는 단계와;
    상기 외부 행위자의 관찰된 추적을 상기 이용 가능한 목표들 각각에 대한 예측된 궤적 모델과 비교하여 해당 목표의 가능성을 결정하는 단계와; 그리고
    상기 외부 행위자의 예상되는 행동을 시뮬레이션하기 위해 상기 목표들 중 적어도 하나의 결정된 가능성을 사용하는 단계를 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
12. 제11항에 있어서,
    상기 외부 행위자의 예상되는 행동을 시뮬레이션하기 위해 상기 목표들 중 적어도 하나의 결정된 가능성을 사용하는 단계는, 적어도 하나의 목표에 대한 예측된 궤적 모델 및 해당 목표의 결정된 가능성에 기초하여 상기 외부 행위자에 대한 적어도 하나의 예측된 궤적을 계산하는 단계를 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
13. 제10항 내지 제12항 중 어느 한 항에 있어서,
    각 목표에 대한 예측된 궤적 모델은 해당 목표와 관련된 예측된 궤적들의 분포인 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
14. 제13항에 있어서,
    각 목표 G_i에 대한 분포는 예측된 궤적들의 세트에서 각 예측된 궤적 T에 대한 조건부 확률 p(T|G_i)을 포함하고, 해당 목표의 가능성 p(G_i|τ)은 관찰된 추적 τ이 주어지면 적어도 하나의 예측된 궤적 확률 p(T|τ)을 추정하기 위해 사용되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
15. 제11항 내지 제14항 중 어느 한 항에 있어서,
    상기 관찰된 추적은 해당 목표에 대한 가장 유용한 궤적 모델을 예측하는데 사용되고, 상기 비교는 상기 가장 유용한 궤적 모델을 상기 예측된 궤적 모델과 비교하는 것을 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
16. 제11항 또는 제15항에 있어서,
    상기 관찰된 추적은 상기 외부 행위자의 현재 기동 및/또는 미래 기동을 예측하는데 사용되며, 상기 예측된 현재 또는 미래 기동은 상기 가장 유용한 궤적 모델을 결정하기 위해 사용되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
17. 제16항에 있어서,
    다중 기동들의 시퀀스가 적어도 하나의 목표에 대해 결정되고, 상기 가장 유용한 궤적 모델은 상기 다중 기동들과 각각 연관된 부분 궤적 모델들에 기초하여 해당 목표에 대해 결정되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
18. 제17항에 있어서,
    각각의 부분 궤적 모델은 하나 이상의 타겟 움직임 값을 포함하고, 상기 가장 유용한 궤적 모델의 미래 부분의 하나 이상의 움직임 값은 움직임 평활화를 상기 타겟 움직임 값에 적용함으로써 결정되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
19. 제11항, 제12항 또는 제15항 내지 제18항 중 어느 한 항에 있어서,
    각 목표에 대한 예측된 궤적 모델은 해당 목표에 대한 단일 예측된 궤적인 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
20. 제15항 내지 제19항 중 어느 한 항에 있어서,
    각 목표에 대한 가장 유용한 궤적 모델은 단일의 가장 유용한 궤적인 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
21. 제17항 또는 제20항에 있어서,
    각 기동에 대한 부분 궤적 모델은 해당 기동에 대해 가장 가능성이 높은 부분 궤적인 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
22. 제15항 내지 제21항 중 어느 한 항에 있어서,
    정의된 비용 함수는, 각 목표에 대한 예측된 궤적 모델 및 가장 유용한 궤적 모델 모두에 적용되어 상기 궤적 모델들의 각 비용을 결정하고, 상기 비교는 이러한 비용들을 비교하는 것을 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
23. 제22항에 있어서,
    상기 비용 함수는, 안전하지 않은 궤적들에 불이익을 주는 동안 감소된 주행 시간을 보상하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
24. 제23항에 있어서,
    상기 비용 함수는 또한 편안함의 부족에 불이익을 주는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
25. 제11항 내지 제24항 중 어느 한 항에 있어서,
    상기 외부 에이전트의 예상되는 행동은 상기 목표들의 결정된 가능성에 기초하여 이용 가능한 목표들의 세트로부터 하나의 목표를 샘플링함으로써 시뮬레이션되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
26. 제25항에 있어서,
    상이한 목표 분포들이 상이한 기동들 또는 기동 시퀀스들에 대해 결정되고, 그리고 외부 에이전트의 예상되는 행동은 기동 분포에 기초하여 가능한 기동들의 세트로부터 하나의 기동 또는 기동 시퀀스를 샘플링하고, 이후, 해당 기동 또는 기동 시퀀스에 대해 결정된 목표 분포에 기초하여 이용 가능한 목표들의 세트로부터 목표를 샘플링함으로써 시뮬레이션되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
27. 제25항 또는 제26항에 있어서,
    상기 기동 분포는 기동 레벨에서 역 계획을 사용하여 결정되며,
    상기 역 계획은:
    가능한 기동들 각각에 대해, 예측된 궤적 모델을 결정하는 것과; 그리고
    상기 외부 행위자의 관찰된 추적을 상기 가능한 기동들 각각에 대한 예측된 궤적 모델과 비교하여 해당 기동의 가능성을 결정하기 것을 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
28. 제25항 내지 제27항 중 어느 한 항에 있어서,
    상기 트리 검색 알고리즘은 상이한 샘플링된 목표들을 갖는 다중 구성된 게임 트리들에 대해 여러 번 수행되고, AV 기동들의 시퀀스는 상기 다중 구성된 게임 트리들 내의 경로들에 대한 통계적 분석에 기초하여 AV 플래너에 의해 결정되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
29. 제10항에 있어서,
    객체 추적은, 상기 직면한 주행 시나리오에서 적어도 하나의 외부 행위자를 추적하고, 시간 간격에 걸쳐 상기 외부 행위자의 관찰된 추적을 결정하기 위해 상기 센서 입력들에 적용되고,
    상기 역 계획 방법은:
    상기 직면한 주행 시나리오에서 상기 외부 행위자에 대해 가능한 기동들의 세트를 결정하는 단계와;
    상기 가능한 기동들 각각에 대해, 예측된 궤적 모델을 결정하는 단계와;
    상기 외부 행위자의 관찰된 추적을 상기 가능한 기동들 각각에 대한 예측된 궤적 모델과 비교하여 해당 기동의 가능성을 결정하는 단계와; 그리고
    상기 외부 행위자의 예상되는 행동을 시뮬레이션하기 위해 상기 기동들 중 적어도 하나의 결정된 가능성을 사용하는 단계를 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
30. 제29항에 있어서,
    각 기동에 대한 예측된 궤적 모델은 해당 기동과 관련된 단일 궤적인 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
31. 제29항 또는 제30항에 있어서,
    각 기동에 대한 예측된 궤적 모델은 해당 기동과 관련된 예측된 궤적들의 분포인 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
32. 자율 차량(AV) 계획 방법으로서,
    AV와 관련된 센서 입력들을 수신하는 단계와;
    직면한 주행 시나리오를 결정하기 위해 상기 센서 입력들을 처리하는 단계와;
    AV 플래너에서, 구성된 게임 트리를 통해 경로에 해당하는 AV 기동들의 시퀀스를 결정하기 위해 트리 검색 알고리즘을 실행하는 단계와; 그리고
    상기 결정된 AV 기동들의 시퀀스를 실행하기 위한 AV 제어 신호들을 생성하는 단계를 포함하고,
    상기 게임 트리는 상기 직면한 주행 시나리오의 예상되는 상태들을 나타내는 복수의 노드들을 가지며, 각 자식 노드의 상기 주행 시나리오의 예상되는 상태는 (i) 후보 AV 기동 및 (ii) 상기 직면한 주행 시나리오에서 적어도 하나의 외부 에이전트의 예상되는 행동에 기초하여 부모 노드의 주행 시나리오 상태를 업데이트함으로써 결정되며, 그리고
    상기 외부 에이전트의 예상되는 행동은 상기 센서 입력들로부터 유도된 상기 외부 에이전트의 하나 이상의 관찰된 파라미터들에 목표 인식을 적용함으로써 시뮬레이션되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
33. 제32항에 있어서,
    상기 목표 인식은, 이용 가능한 목표들의 세트: 상기 하나 이상의 관찰된 파라미터들에 기초한 상기 목표에 대한 가장 유용한 궤적 모델, 및 상기 목표에 대한 최적의 궤적 모델 중 각 목표에 대해 계산하는 것을 포함하는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
34. 제33항에 있어서,
    상기 목표 인식은 확률적이며, 목표 분포는 각 목표에 대한 최적의 궤적 모델과 가장 유용한 궤적 모델을 비교함으로써 결정되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
35. 제34항에 있어서,
    정의된 비용 함수는 각 목표에 대해 예측된 궤적 모델과 가장 유용한 궤적 모델 모두에 적용되어 해당 궤적 모델들의 각 비용을 결정하고, 해당 궤적 모델들은 해당 궤적 모델들의 비용들을 비교함으로써 비교되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
36. 제34항 또는 제35항에 있어서,
    다중 목표 분포들은 다중 가능한 기동들 또는 기동 시퀀스들에 대해 결정되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
37. 제34항 내지 제36항 중 어느 한 항에 있어서,
    상기 예상되는 행동은 상기 목표 분포에 기초하여 이용 가능한 목표들의 세트로부터 샘플링된 목표에 기초하여 시뮬레이션되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
38. 제36항 또는 제37항에 있어서,
    상기 예상되는 행동은, 상기 외부 에이전트에 대해 결정된 기동 분포에 기초하여 가능한 기동들로부터 적어도 하나의 기동을 샘플링하고, 그 후 상기 샘플링된 기동에 대해 결정된 목표 분포로부터 상기 목표를 샘플링함으로써 시뮬레이션되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
39. 제37항 또는 제38항에 있어서,
    상기 트리 검색 알고리즘은 상이한 샘플링된 목표들을 갖는 다중 구성된 게임 트리들에 대해 여러 번 수행되고, AV 기동들의 시퀀스는 상기 다중 구성된 게임 트리들 내의 경로들에 대한 통계적 분석에 기초하여 AV 플래너에 의해 결정되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
40. 제32항에 있어서,
    상기 목표 인식은 목표 인식 결정 트리를 사용하여 수행되는 것을 특징으로 하는
    자율 차량(AV) 계획 방법.
41. 자율 차량을 구성하는 방법으로서,
    훈련 시스템에서, 하나 이상의 주행 영역으로부터 캡처된 실제 주행 행동 데이터를 수신하는 단계와;
    생성 모델 훈련에 사용하기 위해 실제 주행 행동의 예들을 추출하도록 상기 실제 주행 행동을 처리하는 단계와;
    상기 추출된 주행 행동 예들을 사용하여 외부 에이전트의 하나 이상의 관찰 된 파라미터들에 기초하여 상기 외부 에이전트의 행동을 예측하도록 생성 행동 모델을 훈련시키는 단계와; 그리고
    상기 훈련된 생성 행동 모델을 자율 차량의 전자 저장소에 저장하는 단계를 포함하고,
    상기 자율 차량은 상기 생성 행동 모델을 사용하여 제1항 내지 제40항 중 어느 한 항의 단계를 구현하도록 구성된 자율 차량 플래너를 포함하는 것을 특징으로 하는
    자율 차량을 구성하는 방법
42. 제1항 내지 제41항 중 어느 한 항의 방법 단계를 실행하도록 구성된 실행 하드웨어를 포함하는 컴퓨터 시스템.
43. 실행될 때, 제1항 내지 제40항 중 어느 한 항의 방법을 구현하도록 구성된 실행 가능한 명령어들을 포함하는 컴퓨터 프로그램.
44. 제1항 내지 제40항 중 어느 한 항의 방법을 구현하도록 구성된 자율 차량(AV) 플래너.
45. 제44항의 자율 차량 플래너 및 상기 자율 차량 플래너에 결합되고 상기 자율 차량 플래너에 의해 생성된 제어 신호들에 응답하는 구동 메커니즘을 포함하는 자율 차량.

Images