기술 요약: GNN 유도 휴리스틱을 통한 다중 에이전트 인식 계획의 확장성 개선

문제 정의

다중 에이전트 인식 계획(Multi-Agent Epistemic Planning, MEP)은 물리적 행동과 여러 에이전트의 믿음을 추론하기 위한 프레임워크입니다. 일반적인 계획법(Classical Planning)과 달리, MEP는 복잡한 믿음 관계와 고차 지식을 포착하기 위해 상태를 크립키 구조(Kripke structures; 포인티드된 방향성 레이블 그래프)로 표현해야 합니다. 이러한 표현 방식은 두 가지 주요 과제를 야기하며 이는 확장성을 저해합니다:

1. 본질적 복잡성: 인식 상태(e-states) 내에서 전이(transitions)를 적용하고 공식을 평가하는 것은 일반적인 계획법보다 계산적으로 더 까다롭습니다.
2. 효과적인 휴리스틱의 부재: 기존의 MEP 솔버들은 효과적인 휴리스틱이 부족하여 주로 정보가 없는 탐색(예: 너비 우선 탐색, BFS)에 의존합니다. 계획의 길이가 길어짐에 따라 탐색 공간이 기하급급수적으로 증가하여 계산 불가능한 상태에 이르게 됩니다. 최근의 연구(예: H-EFP)가 계획 그래프와 같은 전통적인 계획 구성 요소를 사용하여 휴리스틱을 통합하려는 시도를 했으나, 데이터 기반 방법을 통해 MEP의 확장성을 해결하려는 접근 방식은 거의 없었습니다.

방법론

저자들은 **그래프 신경망(Graph Neural Networks, GNN)**을 사용하여 MEP를 위한 휴리스틱을 생성하는 데이터 기반 접근 방식을 제안합니다. 핵심 아이디어는 GNN 기반 회귀 모델을 학습시켜 "완벽한 휴리스틱"을 근사하는 것, 즉 임의의 인식 상태에서 가장 가까운 목표 상태까지의 거리를 추정하는 것입니다.

1. 상태 표현 및 임베딩

인식 상태는 자연스럽게 그래프 구조(크립키 모델)를 가지므로, 관계적 구조를 포착할 수 있는 GNN을 선택했습니다. 본 논문은 크립키 구조 내의 "세계(worlds)"를 GNN 입력에 적합한 수치 벡터로 인코딩하는 세 가지 전략을 조사합니다:

• 심볼릭 ID 매핑(Symbolic ID Mapping): 생성 순서에 따라 세계에 순차적인 정수를 할당합니다. 계산 비용은 저렴하지만, 세계 간의 의미적 유사성을 상실하며 실행 시마다 불변성이 유지되지 않습니다.
• 해시 기반 인코딩(Hash-based Encoding): 세계의 해석(interpretation)과 반복 인덱스에 해시 함수를 적용합니다. 이는 실행 간에 일관된 식별자를 보장하며, 정보 보존과 계산 효율성 사이의 균형을 제공합니다.
• 비트마스크 인코딩(Bitmask Encoding): 플루언트(fluents)와 반복 인덱스를 인코딩하는 이진 벡터로 세계를 표현합니다. 이는 논리적 정보를 보존하지만, 높은 계산 비용이 발생하며 모델 수렴을 위해 더 큰 모델이 필요합니다.

휴리스틱이 다양한 목표 조건에 대해 일반화될 수 있도록, 저자들은 상태 임베딩을 목표의 압축된 인코딩까지 확장합니다. 이를 통해 "상태 노드"와 "목표 노드"가 서로 연결된 통합된 그래프를 생성하여, 모델이 현재 상태와 특정 목표 조건 사이의 의존성을 학습할 수 있게 합니다.

2. 데이터 생성 파이내라인

학습 데이터는 최신 EFP 플래너인 deep (기존의 SOTA EFP 플래너를 재구현한 것) 내에서 수정된 **깊이 우선 탐색(DFS)**을 사용하여 오프라인으로 생성됩니다.

• 플래너는 지정된 깊이 제한까지 상태 공간을 탐색합니다.
• 목표에 도달하면, 알고리즘은 역추적(backtrack)하여 방문한 각 e-state에 가장 가까운 목표까지의 거리에 해당하는 라벨을 할당합니다.
• 조합 폭발을 관리하기 위해, 생성 과정에서는 확률적 분기 가지치기(probabilistic branch pruning), 무작위 액션 순서 지정, 중복 상태 체크를 사용합니다.
• 허위 라벨을 방지하기 위해 도달 불가능한 상태는 폐기하며, 짧은 계획에 편향되는 것을 피하기 위해 거리 클래스의 분포를 균형 있게 조절합니다.

3. 모델 아키텍처

신경망 회귀 모델은 PyTorch를 사용하여 PyTorch Geometric으로 구현되었습니다. 아키텍처는 다음과 같이 구성됩니다:

• 비트와이즈 임베딩(Bitwise Embedding): 노드 식별자(비트 벡터)와 엣지 속성을 MLP를 통해 밀집 임베딩(dense embeddings)으로 투영합니다.
• 관계적 메시지 전달(Relational Message Passing): 두 개의 GINEConv(Edge Convolution이 포함된 Graph Isomorphism Network) 레이어가 이웃으로부터 정보를 집계하며, 이종 모달 의존성을 처리하기 위해 엣지 속성을 명시적으로 포함합니다.
• 그래프 수준 요약(Graph-Level Summarization): 평균 풀링(Mean pooling)을 통해 노드 임베딩을 고정된 크기의 그래프 표현으로 집계합니다.
• 심층 잔차 회귀 헤드(Deep Residual Regression Head): 일련의 잔차 블록(residual blocks)이 그래프 임베딩을 처리하고, 시그모이드 함수를 통해 정규화된 거리 추정치를 출력합니다.

4. 탐색 통합

학습된 GNN은 **휴리스틱 우선 탐색(Heuristics-First Search, HFS)*을 가이드하기 위해 계획 파이프라인에 통합됩니다. 또한 저자들은 A 알고리즘에서 영감을 얻어, 예측된 휴리스틱 $h(s)$에 탐색 깊이 $d(s)$를 더해 전체 점수 $f(s) = h(s) + d(s)$를 형성하는 변형 모델인 **HFS***를 평가합니다.

주요 기여

본 논문은 네 가지 주요 기여를 설명합니다:

1. 임베딩 비교: GNN 입력을 위한 세 가지 크키 구조 임베딩(Symbolic ID, Hash, Bitmask)에 대한 공식적인 정의와 경험적 비교를 수행하였으며, 해시 기반 인코딩이 가장 효과적인 절충안임을 확인했습니다.
2. 자동화된 파이프라인: MEP 환경에 특화된 GNN 회귀 모델을 학습시키기 위해 학습 데이터(상태-거리 쌍)를 생성하고 모델을 훈련하는 완전 자동화된 시스템을 구축했습니다.
3. 통합: e-state를 평가하고 탐색 과정을 가이드하기 위해 GNN 회귀 모델을 deep 플래너에 통합했습니다.
4. 포괄적인 평가: 여러 표준 도메인에 대해 정보가 없는 탐색(BFS) 및 기존 휴리스틱 기반 플래너(H-EFP)와 철저한 벤치마킹을 수행했습니다.

실험 결과

평가는 600초의 타임아웃을 설정하여 표준 MEP 벤치마크(예: Collaboration and Communication, Selective Communication, Grapevine)에서 수행되었습니다.

• 무정보 탐색 대비 확장성: GNN 가이드 탐색은 대부분의 도메인에서 너비 우선 탐색(BFS)에 비해 확장된 노드 수를 크게 줄였습니다. 예를 들어, Collaboration and Communication (CC) 도메인에서 GNN 방식은 동일한 수의 인스턴스를 해결하면서도 BFS가 평균 610개를 확장할 때 약 65개의 노드만을 확장했습니다.
• 탐색 전략: 휴리스틱과 깊이를 결합한 HFS* 변형 모델이 표준 HFS보다 우수한 성능을 보였으며, 약 32% 더 많은 인스턴스를 해결하고 확장된 노드 수를 줄였습니다.
• 일반화: CC와 GR 도メイン에서 수집된 데이터로 학습된 모델은 보지 못한(unseen) 도메인에 대해서도 일반화 능력을 보여주었으며, 노드 확장 측면에서 BFS 베이스라인을 능가했습니다.
• H-EFP와의 비교: GNN 방식은 H-EFP 플래너의 가장 우수한 개별 휴리스틱(특히 $S\_PG$ 휴리스틱)과 대등한 성능을 보였으며, H-EFP가 사용하는 특정 휴리스틱에 따라 49~82%의 범위에 있는 것과 비교하여 85.33%의 테스트 인스턴스를 해결했습니다.
• 런타임 제한 사항: 본 논문은 GNN이 탐색 공간(확장된 노드)은 줄이지만, 현재 구현에는 배치 추론(예: CUDA 배칭) 최적화가 부족하다고 언급합니다. 결과적으로 원시 해결 시간(raw solving time)은 아직 전통적인 휴리스틱과 경쟁할 수준은 아니지만, 저자들은 이 맥락에서 휴리스틱의 정보성이 주요한 확장성 지표라고 주장합니다.

의의 및 주장

저자들은 이 연구를 기계 학습과 다중 에이전트 인식 계획을 통합하는 기초적인 단계로 규정합니다. 그들의 주장은 다음과 같습니다:

• 휴리스틱 부족: MEP는 클래식 플래닝에 비해 효과적인 휴리스틱이 부족합니다. 본 연구는 GNN이 이 복잡한 그래프 기반 환경에서 완벽한 휴리스틱을 성공적으로 근사할 수 있음을 보여줍니다.
• 데이터 기반 효율성: 각 e-state를 독립적인 학습 신호로 취급함으로써 전체 궤적(trajectory)에 의존하지 않고도 데이터를 효율적으로 생성하여, 크키 모델의 관계적 구조로부터 의미 있는 패턴을 학습할 수 있습니다.
• 상보성: 저자들은 GNN이 즉각적으로 기존 휴리스틱을 대체할 것이라고 주장하지 않습니다. 대신, GNN 기반 휴리스틱이 서로의 약점을 보완할 수 있는 포트폴리오 기반 접근 방식에 통합될 때, 솔버의 커버리지를 높이는 강력한 상보적 도구 역할을 할 수 있다고 주장합니다.

결론적으로, 런타임 성능을 경쟁력 있게 만들기 위해 엔지니어링 최적화(예: 배치 프로세싱)가 필요하지만, 탐색 공간 복잡도의 감소는 MEP 확장을 위한 학습 기반 휴리스틱의 타당성을 입증합니다.