Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning

기술 요약: XDiffuser – 장기 계획용 확산을 위한 외적 그래프 안내

문제 제기
이 논문은 짧은 시간 범위의 잠재적 비최적 궤적 데이터셋만 주어졌을 때, 연속 상태 공간에서 작동하는 로봇을 위한 오프라인 장기 운동 계획의 과제를 다룹니다. 확산 기반 계획기 (예: Diffuser) 는 일관된 궤적을 샘플링함으로써 유망한 "추론으로서의 계획 (planning-as-inference)" 접근법을 제공하지만, 훈련 중 관찰된 적이 없는 목표 장기 분포가 주어지면 어려움을 겪습니다.

기존의 구성적 확산 방법은 겹치는 짧은 세그먼트를 이어붙임으로써 이를 해결하려 시도합니다. 그러나 저자들은 국소적 일관성(인접한 세그먼트가 겹치도록 보장하는 것) 에만 의존하는 것은 긴 체인에서 전역적 일관성을 보장하기에 불충분하다고 주장합니다. 시간 범위가 커질수록 추론 과정은 취약해지며, 국소적으로 타당한 세그먼트들이 상호 양립할 수 없어 작업 완료나 제약 조건 충족에 실패하게 됩니다. 또한, 최근의 내적 탐색(denoising 루프 내부에서 수행되는 탐색) 을 수행하는 접근법은 일관성을 개선하지만, 시간 범위와 탐색 깊이에 따라 확장성이 떨어지는 막대한 계산 비용을 초래합니다.

방법론: XDiffuser
저자들은 XDiffuser(eXtrinsic search-guided Diffuser) 를 제안하며, 이는 전역 조정을 국소 궤적 생성과 분리합니다. XDiffuser 는 확산 과정 중 탐색을 수행하는 대신, 사전 훈련된 구성적 확산 모델을 안내하기 위해 확산 과정 외부에서 외적 탐색을 수행합니다. 이 방법은 세 가지 주요 단계로 구성됩니다:

1. 연결성 그래프 구성:

   • 오프라인 데이터셋 위에 희소 비방향 그래프 $G = (V, E)$가 구성됩니다.
   • 정점 (Vertices) 은 데이터셋에서 샘플링된 상태들입니다.
   • 간선 (Edges) 은 학습된 **시간 거리 표현 (Temporal Distance Representation, TDR)**을 사용하여 결정되며, 여기서 잠재 TDR 공간의 유클리드 거리는 시간적 근접성을 반영합니다.
   • 이 그래프는 부드러운 동역학을 보장하지는 않지만 거친 도달 가능성을 포착하는 경량 "연결성 오라클" 역할을 합니다.

2. 외적 그래프 탐색 (계획):

   • 테스트 시, 목표 도달을 위한 Dijkstra, 다중 에이전트를 위한 우선순위 기반 계획기, 또는 점검을 위한 MILP 솔버와 같은 작업별 그래프 알고리즘이 $G$에서 실행됩니다.
   • 이는 시간적 웨이포인트 (temporal waypoints) $W = \{(w_m, \hat{t}_m)\}$의 시퀀스인 고수준 계획을 생성합니다.
   • 경로는 다운샘플링되어 희소한 발판 (scaffold) 을 생성하고, 타이밍은 확산 모델의 청크 (chunking) 기능과 정렬되도록 시간적으로 확장됩니다.

3. 웨이포인트 안내 구성적 확산:

   • 사전 훈련된 짧은 시간 범위 확산 모델이 연속 궤적을 생성합니다.
   • 그래프에서 유도된 웨이포인트는 하드 제약이 아닌 소프트 에너지 항(안내) 으로 작용합니다.
   • 각 웨이포인트의 명목 시간 주변에 삼각형 안내 윈도우 $\lambda_m(t)$가 정의됩니다. 확산 점수는 웨이포인트 비용 함수 $E_W(\tau)$의 기울기에 의해 증폭되는데, 이는 웨이포인트에서의 편차를 패널티로 부과합니다.
   • 이는 denoising 과정을 확산 사전 (prior) 에 따라 국소적으로 타당하고, 그래프 계획에 따라 전역적으로 일관된 궤적으로 편향시킵니다.

주요 기여

• 외적 탐색 vs 내적 탐색: 이 논문은 외적 탐색(denoising 외부) 이 장기 계획에 있어 내적 탐색보다 더 효과적인 탐색 모드라고 주장합니다. 이는 탐색의 부담을 효율적인 고전적 그래프 알고리즘으로 이전하여, 내적 방법이 요구하는 반복적이고 비용이 큰 확산 모델 평가를 피합니다.
• 모듈성과 확장성: 검색 계층을 생성 계층과 분리함으로써, XDiffuser 는 적응형 시간 범위 선택(그래프 경로 지속 시간에서 추론됨) 을 지원하며, 확산 모델을 재훈련하지 않고도 테스트 시 다양한 계획 알고리즘의 통합을 가능하게 합니다.
• 보이지 않는 작업으로의 일반화: 이 프레임워크는 단일 사전 훈련된 확산 모델이 고수준 그래프 목표만 변경함으로써 복잡한 보이지 않는 조합적 작업 (예: 다중 에이전트 조정, 외판원 문제 스타일의 점검) 을 해결할 수 있게 합니다.

실험 결과
저자들은 OGBench 스위트와 맞춤형 교량 점검 시뮬레이션에서 XDiffuser 를 평가했습니다:

• 장기 목표 도달: AntMaze Explore Large 데이터셋 (저품질, 무작위 보행 데이터) 에서 XDiffuser 는 98.5% 의 성공률을 달성하여, 기본 구성적 확산 (CD) 베이스라인 (27%) 과 CDGS 및 C-MCTD 와 같은 다른 탐색 증강 베이스라인을 크게 능가했습니다. 이러한 이득은 국소적 이어붙임이 실패하는 저품질 데이터 영역에서 가장 두드러졌습니다.
• 다중 에이전트 경로 찾기 (MAPF): 단일 에이전트로 훈련된 모델을 사용한 제로샷 다중 에이전트 설정 (2~4 에이전트) 에서, XDiffuser(우선순위 계획기 사용) 는 4 에이전트 시 58.3% 의 성공률을 보인 반면, Prioritized CDGS 는 **13.3%**에 그쳤습니다. 또한 내적 탐색 방법과 비교하여 분 단위가 아닌 초 단위로 계획을 수립하는 등 뛰어난 효율성을 입증했습니다.
• 점검 계획: 최대 128 개의 관심 지점 (POIs) 이 있는 교량에 대한 드론 점검의 경우, MILP 안내 XDiffuser 는 95% 이상의 커버리지를 달성한 반면, 내적 탐색 베이스라인 (IP-CDGS) 은 50% 미만의 커버리지에서 정체되어 국소적 탐색이 전역 조합적 제약 조건을 해결할 수 없음을 강조했습니다.

의의 및 주장
이 논문은 순수한 "추론으로서의 계획"의 근본적 한계는 장기 분포가 보이지 않을 때 국소적 일관성만으로는 전역적으로 일관된 행동을 보장할 수 없다는 점이라고 주장합니다. XDiffuser 는 두 패러다임의 강점을 활용함으로써 이를 해결합니다:

1. 그래프 탐색은 필요한 전역 구조와 조합적 추론을 제공합니다.
2. 확산은 매끄럽고 동역학적으로 실행 가능한 궤적 합성을 제공합니다.

저자들은 이 분해가 효율적(denoiser 호출의 지수적 확장 회피) 이고 유연하며, 훈련 분포에 명시적으로 포함되지 않은 다양한 복잡한 계획 작업에 걸쳐 단일 생성 모델을 재사용할 수 있게 한다고 강조합니다. 이 연구는 특히 불완전한 데이터를 가진 장기 작업의 경우, 반복적 denoising 을 통해 전역 일관성을 순수하게 학습하려는 시도보다 "먼저 계획하고 나중에 확산 (Plan First, Diffuse Later)" 전략이 우월함을 시사합니다.