고전적 계획법(Classical Planning)에서 일반적인 정책 학습을 위한 효율적인 Lookahead 인코딩 및 추상화된

일반화된 계획법(Generalized planning)은 고전적 계획법(Classical planning) 도메인 내의 여러 인스턴스 집합에 걸쳐 일반화될 수 있는 정책(Policies)을 학습하는 것을 목표로 합니다. 최근의 그래프 신경망 (Graph Neural Network, GNN) 접근 방식들은 여러 도메인에서 거의 완벽한 정책을 학습해 왔습니다. 본 연구는 최근 발표된 반복 너비 (Iterated Width, IW) 정책 아이디어를 개선합니다. 해당 방식에서 정책은 여러 전이(Transitions)를 건너뛸 수 있는 IW-lookahead 탐색을 통해 후속 범위를 확장하며, 이를 통해 문제 구조를 단순화합니다. 그러나 각 전이가 개별적으로 평가되기 때문에 계산 비용이 확장 불가능(Unscalable)해지고 표현력(Expressivity)의 한계가 발생합니다. 또한, IW(1)은 원자(Atoms)의 수에 따라 선형적으로 확장되기 때문에 매력적이지만, International Planning Competition (IPC) 2023 벤치마크와 같이 수천 개의 객체가 고려되는 경우에는 비효율적이 됩니다. 우리는 이 두 가지 한계를 모두 해결합니다. 첫째, 전체 탐색 트리(Search tree)에 대해 훨씬 더 효율적인 홀리스틱 인코딩 (Holistic encoding)을 도입합니다. 이는 IW(1)에 도달 가능한 상태들을 현재 상태와의 관계적 차이(Relational differences)로만 공동 표현하여, 관계형 GNN (Relational GNNs, R-GNNs)이 단 한 번의 순전파 (Forward pass)로 모든 전이를 점수화할 수 있게 합니다. 둘째, 새로움 검사 (Novelty checks) 과정에서 관계적 추상화 (Relational abstraction)를 통해 확장성을 개선하는 추상화된 IW(1) (Abstracted IW(1))을 정의합니다. 완전히 인스턴스화된 원자 (Fully instantiated atoms)를 테스트하는 대신, 하나의 인자를 제외한 모든 인자를 해당 타입 (Type)으로 교체함으로써 각 원자를 추상화합니다. 만약 추상화된 형태 중 어느 하나라도 새롭다면, 원래의 원자도 새로운 것으로 간주합니다. 이러한 구조적 압축은 의미 있는 하위 목표 구조 (Subgoal structure)를 보존하면서, 새로움 탐색의 확장성을 원자 (Atoms) 단위에서 객체 (Objects) 단위로 전환합니다. 우리는 하이퍼스케일링 (Hyperscaling) IPC 2023 벤치마크와 $C_2$ 논리 파편 (Logic fragment) 이상의 특징을 요구하는 도메인을 포함한 다양한 도메인에서 우리의 기여를 평가합니다. 우리의 정책은 고전적 플래너인 LAMA를 포함한 이전 연구들을 크게 능가하며 새로운 최첨단 (State-of-the-art) 성능을 달성합니다.