기술 요약: 고전 계획 (Classical Planning) 을 위한 리프트된 액션 스키마의 미분 가능 학습

문제 정의

본 논문은 관찰된 흔적 (observational traces) 에서 고전 계획 도메인을 위한 리프트된 액션 스키마를 학습하는 과제를 다룹니다. 구체적으로 저자들은 상태가 완전히 관찰되는 (grounded STRIPS 원자로 표현됨) 반면 액션 인자는 관찰되지 않는 설정을 해결합니다. 입력은 $\langle s, a, s' \rangle$ 세트로 구성되며, 여기서 $s$와 $s'$는 grounded 상태이고 $a$는 완전한 액션 이름이거나, 일부 인자가 관찰된 STRIPS+ 액션, 또는 액션 이름만을 포함합니다.

핵심적인 어려움은 다음과 같은 두 가지를 동시에 추론하는 동형성 (isomorphism) -hard 문제에 있습니다:

1. 액션 인자: 상태 내의 어떤 객체가 액션의 매개변수에 바인딩되는지 식별합니다.
2. 리프트된 스키마: 각 액션 스키마에 대한 전제 조건 (preconditions) 과 효과 (add/delete 리스트) 를 리프트된 기호 형태로 학습합니다.

이 문제는 이미지 시퀀스와 액션 레이블로부터 학습하는 더 현실적인 작업의 단순화로 제시되며, 신경 - 기호 (neuro-symbolic) 시스템으로의 통합을 가능하게 하기 위해 기호 추상화 단계를 거의 완벽하게 해결하는 것을 목표로 합니다.

방법론: DIAS 아키텍처

저자들은 경사 하강법을 통해 액션 스키마를 학습하는 신경 아키텍처인 DIAS(Differentiable Induction of Action Schemas) 를 제안합니다. 이 접근법은 엔드 - 투 - 엔드 학습을 가능하게 하는 소프트 (soft) 미분 가능 연산을 활용하여 두 가지 주요 단계로 작동합니다.

1. 그래프 신경망 (GNN) 을 통한 객체 선택

• 그래프 구성: 상태 $s$와 $s'$로의 전이는 방향 그래프 $G$로 인코딩됩니다. 노드는 객체를 나타내고, 가장자리는 상태 내에서 참이거나 전이 중 추가/삭제된 술어 (원자) 를 나타냅니다.
• 임베딩: 관계형 그래프 합성곱 네트워크 (R-GCN) 가 그래프를 처리하여 각 객체에 대한 $d$차원 임베딩 벡터 (키 $K$) 를 생성합니다.
• 슬롯 할당: 각 액션 이름 $a$에 대해 모델은 고정된 수의 "슬롯"(액션 어너리의 상한선) 에 해당하는 학습 가능한 쿼리 벡터 $Q_a$를 유지합니다.
• 소프트 매칭: 객체 키와 액션 쿼리 간의 스케일된 점곱 어텐션을 통해 대응 행렬이 계산됩니다. 그런 다음 직사각형 Sinkhorn 알고리즘이 적용되어 소프트 할당 행렬 $\tilde{S}_a$를 생성하며, 이는 확률적으로 객체를 액션 인자 슬롯에 매핑합니다. 학습 가능한 슬롯 가중치 $w_a$는 각 슬롯의 활성화 확률을 결정하여 모델이 액션의 어너리를 추론할 수 있게 합니다.

2. 전제 조건 및 효과 학습

• 리프트된 매개변수: 모델은 모든 리프트된 원자 $p(x_i, x_j)$에 대해 양/음의 전제 조건, 추가 효과, 또는 삭제 효과인지 결정하기 위한 학습 가능한 확률 텐서를 유지합니다.
• 그라운딩 (Grounding): 소프트 할당 $\tilde{S}_a$는 이러한 리프트된 확률을 grounded 인접 행렬 공간으로 투영하여 현재 상태에서의 특정 원자가 전제 조건이나 효과일 확률을 산출합니다.
• 상태 예측:
  • 전제 조건 확인: 모델은 개별 원자 확률의 논리곱 (conjunction) 을 평가하여 모든 전제 조건이 충족될 확률 $p_{pre}$를 계산합니다. 무작위 초기화에서 발생하는 기울기 소실을 방지하기 위해, 진정한 곱으로 점진적으로 전환하는 기하평균 스케줄링 전략이 사용됩니다.
  • 효과 적용: 예측된 후속 상태 $\hat{A}'$는 현재 상태 인접 행렬 $A$에 grounded 추가/삭제 확률을 적용하고 $p_{pre}$로 스케일하여 계산됩니다.

3. 손실 함수 및 최적화

학습 목적은 복합 손실을 최소화하는 것입니다:

• 주 손실 ($L_{adj}$): 예측된 후속 상태 $\hat{A}'$와 실제 후속 상태 $A'$ 간의 이진 교차 엔트로피입니다. 이는 모델이 인자를 올바르게 선택하고 상태 변화를 예측하도록 유도합니다.
• 보조 손실 ($L_{aux}$): 최소한의 효과와 최대화된 전제 조건을 장려합니다. 이는 비활성 효과와 비활성 전제 조건에 패널티를 부과함으로써 모델이 모든 원자가 효과라고 가정하거나 전제 조건이 존재하지 않는다고 가정하는 것과 같은 사소한 해결책을 학습하는 것을 방지합니다.
• 기울기 투영: 보조 목표가 주된 목표인 상태 예측을 훼손하지 않도록 보장하기 위해 저자들은 PCGrad(Gradient Surgery) 를 사용합니다. 보조 기울기가 주 기울기와 충돌할 경우, 보조 기울기는 주 기울기에 직교하는 초평면 위에 투영되어 $L_{main}$ 최적화가 우선시되도록 합니다.

주요 결과

저자들은 세 가지 관찰 변형 (완전한 STRIPS 액션, STRIPS+ 액션, 액션 이름만) 을 사용하여 13 개의 표준 IPC 계획 도메인(예: Blocks, Logistics, Hanoi, Sokoban) 에서 DIAS 를 평가했습니다.

• 완벽한 복구: 13 개 도메인 중 8 개에서 DIAS 는 세 가지 관찰 변형 모두에 걸쳐 10 회 모든 학습 실행에서 ground-truth 리프트된 액션 스키마를 완벽하게 학습했습니다.
• 강건성:
  • 노이즈: 대부분의 도메인에서 전이당 최대 2 회까지의 무작위 뒤집힌 원자 (관찰 노이즈) 에 대해 모델은 강건함을 보였습니다. 8 회 뒤집기에서 성능이 크게 저하되었습니다.
  • 기호 방법과의 비교: L1 알고리즘 (SAT 기반 접근법) 과 비교했을 때, DIAS 는 특히 L1 이 효과에 존재하지 않는 변수와 관련된 전제 조건을 복구하지 못한 도메인에서 우수하거나 동등한 성능을 달성했습니다.
  • 실패 분석: 실패는 주로 다음 요인들로 귀결되었습니다:
    • 데드 엔드 (Dead ends): 무작위 보행이 중요한 상태 영역을 탐색하지 못하는 Sokoban 과 같은 도메인.
    • 상태 공간 구조: Sierpiński 삼각형 구조가 무작위 보행 커버리지를 제한하는 Hanoi 도메인.
    • 중복 액션: take_image와 같은 액션이 종종 상태 변화를 일으키지 않아 효과 학습을 혼란스럽게 하는 Satellite 도메인.
• MLP 제거 실험: STRIPS 효과를 다층 퍼셉트론 (MLP) 으로 대체한 제거 실험은 아키텍처가 상태 의존적 역학을 학습할 수는 있지만 고전 계획에 적합한 기호 스키마를 생성하지는 못함을 보여주었습니다. 이는 일반화를 위한 리프트된 STRIPS 공식의 필요성을 강조합니다.

의의 및 주장

본 논문은 DIAS 가 중간 기호 추상화 문제를 높은 충실도로 해결함으로써 (예: 이미지와 같은) 원시 관찰로부터 계획 도메인을 학습하는 중요한 단계라고 주장합니다.

• 미분 가능성: 주요 기여는 명시적인 액션 인자를 요구하지 않고 리프트된 액션 스키마를 학습할 수 있는 강건한 미분 가능 구성 요소이며, 이는 신경 관찰 처리와 기호 계획 사이의 간극을 메워줍니다.
• 일반화: 다양한 수의 객체에 어려움을 겪는 슬롯 기반 동적 모델 (예: RIMs) 과 달리, DIAS 는 임의의 수의 객체로 일반화되는 리프트된 표현을 학습합니다. 이는 STRIPS 의 고유한 특성이지만 데이터로부터 학습하기는 어렵습니다.
• 적은 범위: 저자들은 이 작업을 이미지로부터 학습하는 더 넓은 과제의 단순화로 명시적으로 규정합니다. 그들은 이미지에서 계획으로의 문제를 직접 해결한다고 주장하지는 않지만, 그러한 시스템을 위한 필수적이고 도전적인 전제 조건으로서 기호 추상화 단계에서 "거의 완벽에 가까운" 성능을 달성하는 것이 필요하다고 주장합니다.
• 한계: 이 접근법은 조건부 효과나 수치적 특징이 없는 순수 STRIPS 도메인을 가정하며, 액션 인자가 객체에 단사적으로 바인딩된다는 가정에 의존합니다. 또한 무작위 보행 샘플링이 상태 공간에 대한 충분한 커버리지를 제공하지 않는 도메인에서는 방법이 어려움을 겪습니다.