기술 요약: 고전 계획에서 일반적 정책 학습을 위한 효율적 선점 인코딩 및 추상화된 너비

문제 정의

일반적 계획은 단일 도메인 내에서 초기 상태, 목표, 객체 수만 다른 대규모 계획 인스턴스 집합에 걸쳐 일반화되는 정책을 학습하는 것을 목표로 합니다. 최근 그래프 신경망 (GNN) 을 활용한 접근법은 유망한 결과를 보였으나, 국제 계획 대회 (IPC) 2023 에서와 같은 대규모 인스턴스에 적용될 때 확장성과 표현력의 심각한 한계에 직면해 있습니다.

구체적으로, 반복된 너비 (Iterated Width, IW) 정책과 관련된 이전 연구들은 다중 전이를 건너뛰는'점프'를 정의하기 위해 IW(1) 선점 탐색을 사용하여 문제 구조를 단순화했습니다. 그러나 기존 구현은 두 가지 주요 병목 현상에 시달립니다:

1. 계산 비효율성: 각 후속 상태를 개별적으로 평가하면 공유된 상태 설명의 중복 인코딩이 발생하여, 객체와 원자 (atoms) 의 수가 증가함에 따라 메모리 및 계산 비용이 제대로 확장되지 않습니다.
2. 표현력 및 확장 한계: 표준 IW(1) 신규성 (novelty) 검사는 바닥 원자 (ground atoms) 의 수에 비례하여 선형적으로 확장됩니다. 수천 개의 객체가 있는 도메인에서는 바닥 원자의 수가 다항식적으로 증가하여 선점 탐색이 비효율적이 됩니다. 또한, 즉시 후속 상태에만 제한된 모델들은 복잡한 도메인 (예: C2 조각을 넘어선 논리가 필요한 도메인) 에 필요한 특성을 도출할 표현력이 부족합니다.

방법론

본 논문은 관계형 GNN(R-GNN) 을 위한 새로운 집계 - 델타 (Aggregated-Delta, AD) 인코딩과 선점 탐색을 위한 **추상화된 IW(1)(Abstracted IW(1), AIW(1))**를 결합한 통합 접근법을 제안합니다.

1. 집계 - 델타 (AD) 인코딩

현재 상태 $s$와 각 후속 상태 $s'$를 개별적으로 처리하는 대신, 저자들은 전체 선점 트리를 단일 관계 그래프로 표현하는 통합 인코딩을 도입합니다.

• 공동 표현: 루트 상태 $s$는 그 관계 집합을 통해 암시적으로 인코딩됩니다. 후속 상태는 전체 상태 설명이 아닌, 루트 상태에 대한 차이점(추가 및 삭제된 술어) 만을 인코딩하는 상태 객체 - 노드($o_{s'}$) 로 표현됩니다.
• 트리 구조: 이 인코딩에는 후속 상태 간의 전이를 나타내는 명시적 원자와 탐색 깊이를 포착하기 위한 깊이 노드가 포함됩니다. 이를 통해 R-GNN 은 후속 노드 간에 직접 정보를 교환하고 모든 상태에 대한 임베딩을 단일 순전파 (forward pass) 로 계산할 수 있습니다.
• 효율성: 이 접근법은 공유된 상태 설명의 재인코딩을 방지하여 메모리 사용량을 한 자리 수 이상 줄입니다 (테스트된 시나리오에서 24GB 이상에서 4GB 미만의 VRAM 으로 감소) 및 모든 전이를 동시에 평가할 수 있게 합니다.

2. 추상화된 IW(1)(AIW(1))

신규성 검사의 확장 병목 현상을 해결하기 위해 저자들은 신규성 테스트 동안 상태 원자를 추상화하는 IW(1) 의 완화된 변형을 제안합니다.

• 관계적 추상화: 완전히 인스턴스화된 원자를 테스트하는 대신, AIW(1) 는 $n$-ary 원자의 모든 인수를 가장 구체적인 유형으로 대체합니다 (예: 객체 $o$를 $type(o)$로 대체). 원자의 어떤 추상화된 형태라도 신규하면 해당 원자는 신규로 간주됩니다.
• 복잡도 전환: 이 수정은 신규성 탐색의 최악의 경우 복잡도를 바닥 원자의 수에 대한 선형에서 객체의 수에 대한 선형으로 변경합니다.
• 목표 보존: 목표에 언급된 원자는 목표 감지가 정확하게 유지되도록 추상화되지 않습니다.
• 이익: 이 방법은 의미 있는 하위 목표 구조를 포착하고 학습 에이전트의 비용 구조를 단순화하면서도 수천 개의 객체가 있는 인스턴스로 선점 탐색을 확장할 수 있게 합니다.

학습 절차

R-GNN 은 Hindsight Experience Replay(HER) 의 리프트 (lifted) 변형을 사용한 심층 Q-러닝으로 학습됩니다. 보상은 단계당 -1 로 정의되어, Q-값이 목표까지의 예상 전이 수의 음수를 나타내도록 합니다. 보조 순위 손실 (ranking loss) 이 도입되어 선점 트리에서 깊이 순서를 강제하며, 에이전트가 (Spanner 도메인과 같이) 너무 멀리 점프하여 발생하는 막다른 골목 (dead-ends) 을 피하도록 학습합니다.

주요 기여

1. 집계 - 델타 (AD) 인코딩: 상태 차이를 통해 전체 선점 트리를 공동으로 표현하는 R-GNN 을 위한 새로운 입력 인코딩. 이는 모든 후속 상태의 단일 통과 평가를 가능하게 하여 메모리 풋프린트와 학습 시간을 획기적으로 줄입니다.
2. 추상화된 IW(1)(AIW(1)): 유형 기반 추상화를 활용하여 원자에 대한 다항식에서 객체에 대한 선형으로 신규성 탐색 복잡도를 줄이는 확장 가능한 선점 메커니즘.
3. 최첨단 성능: AIW 와 AD 의 결합은 IPC 2023 학습 트랙 및 기타 도메인에서 새로운 성능 벤치마크를 달성하여, 이전 학습된 정책과 LAMA 와 같은 강력한 고전 계획기 모두를 능가합니다.

실험 결과

저자들은 IPC 2023 벤치마크 (10 개 도메인의 900 개 인스턴스) 와 확장된 도메인 세트 (Grid 및 Logistics 포함) 에서 접근법을 평가했습니다.

• IPC 2023 성능: AIW–AD 방법은 총 74% (900 개 인스턴스 중 668 개) 의 커버리지를 달성하여 다음과 같은 방법들을 크게 능가했습니다:
  • IW–AD(59%): 추상화의 가치 입증.
  • AIW–Ext(51%) 및 IW–Ext(51%): AD 인코딩의 가치 입증.
  • LAMA(65%): 강력한 고전적 기준선.
  • Flat AA(58%): 선점 없는 평면 정책.
• 도메인별 세부 사항:
  • Satellite: AIW–AD 는 인스턴스의 98% 를 해결하여 다른 학습 방법들이 어려움을 겪었던 해당 도메인을 완전히 해결했습니다.
  • Rovers & Childsnack: 상당한 개선이 관찰되었으나, Childsnack 의 어려운 인스턴스는 막대한 분기 계수 (수백만 개의 행동) 로 인해 여전히 도전적입니다.
  • Sokoban & Floortile: 성능은 낮게 유지되었으며, 이는 검색 없는 정책에게 PSPACE-완전 또는 구조적으로 복잡한 도메인의 알려진 어려움과 일치합니다.
• 확장성: 이 방법은 이전 IW 정책 공식이 메모리 제약으로 인해 실패했던 최대 488 개의 블록 (Blocksworld) 과 290,000 개 이상의 원자 (Rovers) 를 가진 인스턴스를 성공적으로 처리했습니다.
• 표현력: 이 접근법은 C2 논리 조각을 넘어선 특성이 필요한 도메인 (Satellite, Rovers, Grid, Logistics 등) 으로 성공적으로 일반화되어, 선점 메커니즘이 신경 아키텍처에 대한 표현적 부담을 줄여준다는 것을 시사합니다.

중요성 및 주장

본 논문은 효율적인 너비 기반 선점이 일반적 계획의 확장을 위한 핵심 촉진제라고 주장합니다. 이 연구의 중요성은 다음 두 가지 주요 영역에 있습니다:

1. 확장성: AIW 를 통해 바닥 원자의 수에서 선점 탐색의 복잡성을 분리하고, AD 를 통해 신경 인코딩의 복잡성을 전이 수에서 분리함으로써, 이전에는 학습 방법으로 해결 불가능했던 대규모 계획 인스턴스에 대한 정책 학습을 실현 가능하게 합니다.
2. 줄어든 표현력 요구 사항: 선점 메커니즘은 학습 에이전트를 위한 문제 구조를 단순화합니다. 기본 결정의 시퀀스를'건너뛰는'것으로 정책은 고수준 결정만 학습하면 됩니다. 이는 제한된 표현력을 가진 모델 (표준 R-GNN) 이 C2 논리 조각을 넘어선 복잡한 특성이 필요했을 도메인을 해결할 수 있게 합니다.

저자들은 그들의 접근법이 일반적 계획에서 새로운 최첨단을 대표한다고 결론지으며, 원칙적인 탐색 (선점) 과 효율적인 신경 인코딩을 결합하면 학습된 정책이 다양한 복잡 도메인에서 높은 성능을 유지하면서 효과적으로 확장될 수 있음을 입증했습니다.