A Graph-based Framework for Coverage Analysis in Autonomous Driving

기술 요약: 자율주행 커버리지 분석을 위한 그래프 기반 프레임워크

문제 정의
자율주행 시스템의 안전성을 검증하려면 시스템이 운영 설계 영역(Operational Design Domain, ODD) 전체에 걸쳐 테스트되었는지 확인하기 위한 엄격한 커버리지 분석이 필요하다. 기존의 접근 방식은 일반적으로 커버리지 요소를 개별적으로 평가하거나 제한적인 조합(예: 2~3개 요소)으로만 평가하여, 실제 교통 장면에서 발생하는 복잡하고 고차원적인 상호작용을 포착하는 데 어려움을 겪는다. 또한, 전통적인 방법들은 무작위 샘플링에 의존하거나 다양한 교통 조건에 효율적으로 확장되지 않는 시나리오별 특정 처리 규칙을 요구하는 경우가 많다. 따라서 교통 장면을 체계적으로 표현하고, 복잡한 행위자 간의 상호작용을 포착하며, 모든 가능한 시나리오를 수동으로 일일이 정의하지 않고도 확장 가능한 커버리지 지표를 제공할 수 있는 프레임워크가 필요하다.

방법론
본 논문은 정적 맵 토폴로지와 동적 행위자 관계를 통합하는 계층적 그래프로 교통 장면을 표현하는 그래프 기반 프레임워크를 제안한다. 방법론은 세 가지 핵심 구성 요소로 이루어진다:

1. 계층적 그래프 구축:

   • 맵 그래프 (Map Graph): 도로 네트워크를 인코딩하는 유향 다중 그래프($G_{map}$)로, 노드는 차선 세그먼트를 나타내고 엣지는 공간적 관계(following, neighbor, opposite)를 나타낸다.
   • 행위자 그래프 (Actor Graph): 2단계 알고리즘을 통해 특정 타임스텝에 대한 동적 그래프($G_{actor}$)를 구축한다.
     • 1단계 (관계 발견): 거리 임계값과 맵 연결성을 기반으로 행위자 쌍 사이의 잠재적 관계를 식별한다. 관계에는 leading/following, neighbor, opposite 구성이 포함된다.
     • 2단계 (계층적 구축): 우선순위 순서(Leading/Following > Neighbor > Opposite)에 따라 엣지를 추가하여 최종 그래프를 구축하며, 중복을 방지한다. 정의된 노드 거리 제한 내에서 두 행위자 사이에 이미 경로가 존재하는 경우 직접적인 엣지를 추가하지 않는다. 이는 그래프의 연결성을 유지하면서도 계산적으로 다룰 수 있는 수준을 보장한다.
   • 시간적 확장 (Temporal Extension): 프레임워크는 시간 인덱스 기반의 그래프를 지원하여 엣지가 시간에 따라 변할 수 있도록 하며(예: 차선 변경), 등장하거나 사라지는 행위자를 처리할 수 있게 한다.

2. 부분 그래프 동형성(Subgraph Isomorphism)을 통한 커버리지 분석:

   • 이 바텀업(bottom-up) 방식은 일반적인 주행 시나리오(예: 무보호 좌회전, 컷인, 플래툰)를 나타내는 수동으로 큐레이션된 "아키타입(archetype)" 그래프 집합을 정의한다.
   • VF2 알고리즘을 사용하여 교통 장면 그래프의 부분 그래프가 이러한 아키타입과 동형인지 확인한다.
   • 이를 통해 노드 커버리지 백분율을 계산하고, 공통 발생 패턴(어떤 아키타입이 함께 나타나는지) 및 특정 시나리오 유형 내의 파라미터 분포(속도, 경로 길이)를 분석할 수 있다.

3. 그래프 임베딩(Graph Embeddings)을 통한 커버리지 분석:

   • 이 탑다운(top-down) 방식은 에지 특징을 가진 그래프 동형 네트워크(GINE)를 활용하여 교통 장면 그래프를 연속적인 벡터 공간으로 투영한다.
   • 모델은 그래프의 미니 배치에 대해 자기지도 대조 학습(self-supervised contrastive learning)을 사용하여 학습된다. 데이터 증강은 연속적 속성(속도, 경로 길이)을 섭동(perturbation)시키거나 엣지를 무작위로 제거하는 방식으로 이루어진다.
   • 결과물인 임베딩은 명시적인 시나리오 정의 없이도 유사도 기반의 커버리지 평가, 클러스터링, 이상 탐지를 가능하게 한다.

주요 기여

• 통합 그래프 표현: 맵 토폴로지와 행위자 관계를 단일 계층적 그래프 구조로 결합하여 커버리지 분석을 위해 명시적으로 설계된 새로운 프레임워크를 제공한다.
• 2단계 구축 알고리즘: 공간적 관계를 포착하면서도 중복 엣지를 방지하는 체계적인 방법을 제공하여, 다양한 수의 행위자가 포함된 장면에서도 확장성을 보장한다.
• 이중 모드 분석: 두 가지 상호 보완적인 방법을 통합하였다:
  • 부분 그래프 동형성: 사전 정의된 아키타입에 대해 해석 가능하고 세밀한 커버리지 지표를 제공한다.
  • 그래프 임베딩: 고차원 공간에서 유사도 평가 및 이상 탐지를 위한 확장 가능한 비지도 학습 방법을 제공한다.
• 갭 분석 프레임워크: 구조적 존재 여부, 파라미터 분포, 공통 발생 패턴을 비교함으로써 "정의의 구멍(definition holes, 커버리지 격차)"을 식별하는 구조화된 접근 방식을 제공한다.

결과
프레임워크는 Argoverse 2.0 데이터셋의 실제 데이터와 CARLA 시뮬레이터(Town01–07)의 합성 데이터를 사용하여 검증되었다.

• 부분 그래프 동형성 결과:

  • 두 데이터셋 모두에서 전체 노드 커버리지는 62%였다.
  • 중대한 구조적 격차가 식별되었다: CARLA는 복잡한 다중 행위자 교차로 시나리오(예: 교차로에서의 "cut-out"은 Argoverse 장면의 8.2%에서 나타난 반면 CARLA에서는 0.3%에 불과함)가 과소 표현되었다.
  • 파라미터 분석 결과, 구조적 아키타입이 존재하더라도 CARLA는 실제 데이터에서 흔히 나타나는 특정 속도 범위(예: 차선 변경 시 중·고속도)를 충족하지 못하는 경우가 많았다.
  • 공통 발생 분석은 CARLA가 simultaneous following 및 overtaking과 같은 아키타입의 현실적인 조합이 부족함을 보여주었다.

• 그래프 임베딩 결과:

  • GINE 모델은 유클리드 거리가 장면 유사도와 상관관계를 갖는 잠재 공간으로 교통 장면을 성공적으로 투영했다.
  • 차원 축소(PCA 및 t-SNE)를 통해 CARLA와 Argoverse 시나리오의 뚜렷한 클러스터를 시각화하였으며, 이는 모델이 두 데이터셋을 구분하고 서로 다른 시뮬레이션 환경을 구별할 수 있음을 확인시켜 주었다.
  • 임베딩은 명시적인 부분 그래프 매칭 없이도 구조적 및 파라미터적 차이를 탐지하는 능력을 입증하였으며, 이는 확장 가능한 커버리지 평가를 위한 사용 가능성을 뒷받침한다.

의의 및 주장
본 논문은 제안된 프레임워크가 전통적인 커버리지 분석 방법보다 다음과 같은 중요한 이점을 제공한다고 주장한다:

• 확장성: 시나리오별 처리 규칙이나 모든 테스트 케이스에 대한 수동 정의 없이도 다양한 교통 시나리오에 효율적으로 확장된다.
• 유연성: 장면 내 행로의 수를 자연스럽게 수용하며, 참여자를 제외하거나 임의의 부분 집합에 집중해야 하는 문제를 피한다.
• 상호 보완성: 부분 그래프 동형성의 해석 가능성과 그래프 임베딩의 확장성을 결합함으로써, 구조적 및 파라미터적 차원에서 커버리지 격차를 식별할 수 있는 강력한 도구를 제공한다.
• 검증 유용성: 합성 시뮬레이션 데이터(CARLA와 같은)가 실제 세계 데이터(Argoverse와 같은)의 분포를 적절히 커버하는지 검증하는 방법을 확립하여, 시뮬레이션 기반 테스트 파이프라인을 개선하기 위한 실행 가능한 통찰력을 제공한다.

저자들은 현재 작업이 수동으로 정의된 아키타입에 의존하고 있지만, 향후 연구에서는 실제 데이터로부터 이러한 아키타입을 자동으로 추출하고 시간 정보를 그래프 구조에 통합하는 방안을 조사할 것이라고 언급하였다.