좋은 기호는 솔버가 필요로 하는 이산 약속을 드러낸다

무엇인가

이 논문은 하이브리드 이산-연속 로봇 계획에서 어떤 기호가 계산적으로 유용한지를 추론 알고리즘 중심으로 정의한다. 기존 방법은 사람이 정의한 기호 집합이나 언어 감독에서 얻은 기호를 쓰지만, 왜 그 기호가 솔버에 도움이 되는지는 묻지 않는다. 저자들은 좋은 기호가 원래 계획 문제의 전역 최적해를 보존하면서 조건부 하위 문제를 풀기 쉽게 만드는 이산 커밋을 드러내야 한다고 주장하고, 이를 solver-sufficient symbolization으로 형식화한다.

어떻게 동작하나

PWA 시스템에서는 finite-horizon 문제를 모드 z와 연속 변수 xi의 MILP로 두고, symbolization map Phi와 조건부 문제 P_joint^psi를 정의한다. 목표는 Eq. 2의 분해에서 전역 최적해를 유지하면서 Solve(P_joint^psi)의 복잡도를 줄이는 것이다. relative affine-TU certificate W를 찾아 psi=Wz를 기호로 삼고, psi를 고정하면 [P~d;Ed;W]가 TU가 되어 조건부 정수 문제가 정확한 LP 완화로 풀린다. relative affine-TU dimension kappa는 환원 불가능한 이산 변수 수를 나타내며, 문제 난이도가 최대 2^kappa 모드로 특성화된다.

무엇과 다른가

최소 affine-TU dimension을 구하는 것은 NP-hard라서, 저자들은 Counterexample-Guided Partition Refinement(CPR)로 certificate W를 구성한다. CPR은 Ed로 표현되지 않는 Bd 방향에서 W0를 초기화하고, 현재 W_i에 대해 Pd를 residualize해 검증 행렬 M_i를 만든 뒤 TU oracle로 확인한다. 실패하면 Sparsify가 같은 행 공간의 다른 0,±1 기저로 재표현해 거짓 장애물을 제거하고, 그래도 실패하면 Split이 최소 비-TU 부분행렬을 찾아 한 열의 변수를 새 기호로 승격한다. 이 CEGAR 루프는 조건부 문제가 LP로 풀릴 때까지 반복된다.

어떻게 쓰나

신경망 에너지 함수 h_s(x)를 최소화하는 설정에서는 명시적 모드 z 없이도 기호를 발명한다. τ-admissible path는 지금까지의 최저 에너지보다 τ 이상 일시적으로 올라가는 것을 허용하는 경로이고, 영역 R이 τ-descent faithful하다는 것은 R 안 어느 초기화에서도 τ 이내의 근최적점에 도달할 수 있음을 뜻한다. 기호는 W(x)=(q1(u1^T x),...,qk(uk^T x))처럼 선형 투영과 양자화기로 정의되어 결정 공간을 영역 R_psi로 나눈다. Neural CPR은 다중 시작 descent 샘플로 m-최근접 이웃 그래프를 만들고, 그래프 위에서 검증한 뒤 재샘플링으로 거짓 분리를 합치고, gradient 방향이 뒤집히는 전이점에서 새 투영 방향과 임계값을 추가한다. 각 영역에서 confined descent를 수행하고 가장 낮은 목적값을 고르면, Proposition B.4에 의해 전역 최적값의 τ 이내가 보장된다.

전제와 한계

실험은 PWA에서 2D 조작 3개와 다지 그리퍼 인핸드 재배향 3개, 네트워크 설정에서 D3IL 3개와 실제 로봇 2개로 구성된다. PWA 베이스라인은 CoCo, GBD-MPC, PDDLStream with LLM-invented symbols, PGS, IVNTR, pix2pred이고, 신경망 베이스라인은 BESO, IBC, DDPM, ACT, BeT의 에너지 기반 변형이다. 저자들은 성공률(SR)과 추론 시간 단축(IS), 그리고 신경망에서 τ-근방 도달에 필요한 descent 수(DC_10^-3)를 보고한다. 원문 발췌에는 표의 구체 수치가 제시되지 않아 숫자를 인용하지 않지만, 본문은 기호가 해 품질을 크게 유지하면서 풀이 비용과 DC_10^-3를 줄였다고 주장한다. CoCo는 완전한 이산 배정을 고정해 LP를 만들므로 최적해를 배제할 수 있는 반면, 제안 방법은 충실한 완화에 필요한 커밋만 노출해 더 낮은 차원의 기호 탐색을 한다고 설명한다.

MPushT에서는 127개 factor를 가진 9개 MILP를 수동 구성해, factor 비활성화 시 성공률 감소인 task necessity(TN)와 CPR 기호가 해당 factor를 얼마나 자주 결정하는지인 solver necessity(SN)를 측정한다. SN이 높을수록 TN과 명확한 인간 의미를 가진 factor 비율이 높았고, 예를 들어 줄기 아래를 미는 z2가 상단 모서리를 미는 z1보다 SN과 TN이 높았다. 또한 Aligning의 안쪽/바깥쪽 push, Avoiding의 장애물 왼쪽/오른쪽 통과처럼 서로 다른 에너지 basin이 기호 영역으로 발견되며, VLM으로 롤아웃 비디오에 행동 라벨을 붙이고 추론 시 원하는 기호 값을 수동 설정해 SR과 preference success rate(PR)를 높였다. 계획 지평이 길어지면 기호 차원 k가 대체로 증가하고 SR은 완만히 감소하며, Avoiding은 Aligning보다 훨씬 적은 기호를 필요로 했다.

개발자에게 이 논문은 기호를 사람이 의미 있게 보이는 설명으로 고르는 대신, 솔버가 실제로 비싼 이산 결정을 줄이는 방향으로 설계하라는 지침을 준다. MILP 기반 접촉 계획에서는 relative affine-TU 차원과 CPR로 조건부 LP 완화 가능성을 확인하고, 확산/플로우 정책에서는 에너지 지형의 basin을 기호로 나눠 다중 시작 비용과 조종성을 관리할 수 있다. 다만 저자들이 밝힌 한계는 기호 모델이 u^T x인 선형 투영에 제한된다는 점이며, 학습된 특징 공간에서 모드가 선형 분리되지 않으면 비선형 u(x)가 필요할 수 있다. 또한 Neural CPR의 검증은 연속 영역이 아니라 샘플 그래프 위에서 정확하고, 긴 지평에서는 기호 차원 증가와 성공률 저하가 나타난다. PWA 실패는 너무 짧은 계획 지평에서 이른 커밋이 후속 전이를 무효화하는 데서 주로 발생한다고 밝힌다.