MIT의 Walk on Decomposed Subdomains를 정리했어요. 올해 SIGGRAPH 최우수 논문인데, 분류상으로는 로보틱스가 아니라 타원형 편미분방정식을 푸는 수치해석 연구예요. 그런데 논문의 대표 그림이 잡동사니로 가득한 창고를 로봇이 지나가도록 경로를 뽑는 장면이에요. 저자들이 직접 그 목적을 적어뒀어요. 3D 가우시안 스플랫 디지털 트윈으로 휴머노이드 내비를 제로샷 전이가 실제 공간을 시뮬레이션 안으로 옮기는 이야기였다면, 이 논문은 그렇게 옮겨온 복잡한 기하 위에서 실제로 계산을 돌리는 쪽을 맡아요.
열이 흐르는 것처럼 길을 뽑아요
발상 자체는 단순해요. 목표 지점을 낮은 값으로 두고 공간 전체에 퍼지는 장을 구한 다음, 그 장을 따라 내려가면 경로가 돼요. 논문은 이걸 열 흐름 문제로 세워요. 물체와 벽은 노이만 경계로 두는데, 열이 그 표면을 통과하지 못한다는 조건이라 장애물을 자연스럽게 피해 가는 장이 나와요.
수식으로는 혼합 디리클레·노이만 경계 조건이 붙은 타원형 경계값 문제예요. 문제는 이 방정식을 복잡한 기하에서 푸는 비용이에요.
격자도 무작위 걸음도 각자 막혀 있었어요
유한차분법이나 유한요소법 같은 격자 기반 솔버는 기하가 복잡해질수록 감당이 안 돼요. 유한차분은 세밀한 경계를 표현하려면 격자를 과하게 촘촘히 해야 하고, 유한요소는 부피 메시를 만드는 비용 자체가 커요. 창고 물건 하나 옮길 때마다 메시를 다시 만들어야 한다면 쓸 수가 없어요.
반대편에는 격자가 필요 없는 몬테카를로 계열이 있어요. 임의의 점에서 무작위 걸음을 시작해 경계에 닿을 때까지 걷고, 그 통계로 값을 추정해요. 메시가 필요 없으니 기하가 아무리 복잡해도 상관없는데, 대신 분산이 커요. 특히 노이만 경계가 많은 장면에서 심해지는데, 창고가 정확히 그런 장면이에요. 결과가 잡음투성이라 그 위에서 매끄러운 경로를 뽑는 게 사실상 불가능했어요.
영역을 타일로 쪼개요
이 논문의 방법은 두 쪽을 섞어요. 먼저 영역을 서로 겹치지 않는 규칙적인 타일로 나눠요. 여기에 메시 작업은 필요 없어요. 그다음 각 타일 안에서만 짧은 무작위 걸음을 돌려서, 그 타일의 경계에서 내부로 가는 사상을 추정해요. 걸음이 타일 밖으로 나가지 않으니 길이가 확 짧아져요.
전역은 다르게 처리해요. 타일 사이의 경계면을 일시 상태로, 바깥 디리클레 경계를 흡수 상태로 두면 이산 마르코프 연쇄가 하나 만들어져요. 그러면 무작위 걸음을 실제로 시뮬레이션하는 대신 희소 선형계를 한 번 푸는 것으로 정확히 대체할 수 있어요. 무작위성이 개입하지 않으니 이 단계에서는 분산이 더해지지 않아요. 내부 값은 미리 구한 타일별 연산자에 행렬 곱을 걸어 병렬로 복원해요.
몬테카를로는 기하를 감당하는 데만 쓰고, 전역 결합은 결정론에 맡기는 분업이에요.
걸음이 635보에서 16보로 줄었어요
대표 창고 장면의 수치가 이 분업의 효과를 보여줘요. 같은 샘플 수를 쓴 조건에서 비교 대상인 Walk on Stars는 걸음 평균 635보에 10,997초가 걸렸어요. 세 시간이 넘어요. 이 논문의 방법은 평균 16보에 9.7초예요. 1,100배 넘게 빨라요.
빠르기만 한 게 아니라 정확도도 나아요. 제곱평균제곱근 오차가 0.036에서 0.008로 내려갔어요. 보통 이런 교환에서는 속도를 얻으면 정밀도를 내주는데, 여기서는 무작위 걸음이 짧아진 만큼 분산이 줄어서 두 축이 같이 좋아져요. Walk on Stars 쪽 결과는 잡음이 지배적이라 유선을 뽑는 것 자체가 무리인 반면, 이쪽은 그 위에서 바로 경로가 나와요.
도시 규모 바람 흐름을 계산한 다른 장면도 23.2초에 끝나요. 실제 데이터로 만든 도시 배치에서 건물이 바람 패턴에 주는 영향을 정상상태 유선으로 그린 장면이에요.
구현은 Dr.Jit으로 GPU에서 무작위 걸음을 모든 타일에 걸쳐 병렬로 돌리고, 광선 교차나 최근접점 같은 기하 질의는 fcpw의 공간화 법선 원뿔 계층으로 처리해요. 창고 장면은 타일을 128개로 나누고 타일당 패널 해상도를 8로 두어, 패널당 샘플 1,000개를 썼어요.
물건을 옮기면 그 근처만 다시 풀어요
로봇 쪽에서 더 중요한 성질은 따로 있어요. 창고에서 장애물을 더하거나 빼면 그 편집이 타일 몇 개의 국소 수정으로만 반영돼요. 전체를 처음부터 다시 추정할 필요 없이 바뀐 부분 주변만 다시 풀면 경로가 갱신돼요. 환경이 계속 바뀌는 현장에서는 한 번 빠른 것보다 이 성질이 더 값어치 있어요.
남는 것
제약이 뚜렷해요. 평가가 2차원에 한정돼 있어요. 저자들은 3차원 확장이 격자 기반 솔버가 겪는 것과 같은 난점을 안는다고 밝혔어요. 노이만 조건도 값이 0인 경우만 다뤘고, 더 일반적인 경계 조건은 앞으로의 과제로 남겨뒀어요.
타일당 해상도를 키우면 전역 선형계의 미지수가 그에 반비례해 줄어드는 대신 몬테카를로 부담이 커져요. 전역 결정론 계산과 국소 확률 계산 사이에서 어느 쪽에 일을 더 실을지 고르는 손잡이인 셈이에요. 너무 키우면 순수 확률적 방법의 문제가 되살아나는데, 특히 노이만이 지배적인 문제에서 분산이 감당 못 할 만큼 늘어난다고 적었어요. 문제마다 적정 지점이 다르다는 뜻이에요. 만들어지는 선형계가 비대칭이라 대칭 양정부호 행렬용 견고한 희소 솔버를 바로 쓸 수 없다는 점도 저자들이 향후 과제로 남겼어요.
로보틱스 논문으로 읽으면 안 되는 연구예요. 다만 복잡하고 계속 바뀌는 기하 위에서 장을 빠르게 푸는 도구는 경로계획과 시뮬레이션 양쪽에서 계속 필요한 것이고, 저자들이 그 쓰임을 먼저 그림으로 내놓았어요.