로봇, 자율주행 자동차, 드론이 단순히 정해진 스크립트를 따르는 것이 아니라, 서로 충돌하지 않고 움직이는 방법을 알아내기 위해 서로 고도의 심리전이 오가는 체스 게임을 벌이는 세상을 상상해 보십시오. 이것은 멀티 에이전트 로보틱스(multi-agent robotics)의 영역으로, 모든 로봇은 다른 모든 이들과의 충돌을 피하면서 자신만의 경주에서 승리하려는 플레이어가 됩니다. 이러한 결정을 실시간으로 내리기 위해 엔지니어들은 "혼합 상보성 문제(Mixed Complementarity Problem, MCP)"라는 수학적 도구를 사용합니다. MCP를 모든 플레이어가 자신의 움직임을 단독으로 바꾼다고 해서 상황을 개선할 수 없는 완벽한 균형 상태에 도달하도록 하는 거대하고 복잡한 규칙서라고 생각하십시오. 수년 동안 이 규칙서를 읽는 유일한 방법은 PATH라고 불리는 매우 강력하지만 폐쇄적인 소프트웨어를 사용하는 것이었습니다. 그것은 마치 마스터 셰프가 완벽한 요리를 만들 수 있지만, 당신은 레시피를 볼 수도, 재료를 바꿀 수도 없으며, 다음 요리를 시작하기 전에 한 번에 딱 한 접시의 요리가 완성될 때까지 기다려야만 하는 상황과 같았습니다.

이제, 새로운 팀의 연구자들이 MixedComplementarityProblems.jl이라는 완전히 새로운 오픈 소스 주방을 구축했습니다. 이들은 한 번에 한 접시의 요리를 만드는 대신, 표준 가스레인지(컴퓨터의 CPU)를 사용하든 초고속 산업용 오븐(그래픽 카드 또는 GPU)을 사용하든 상관없이 수백 가지의 요리를 동시에 만드는 방법을 찾아냈습니다. 그들의 큰 발견은 무엇일까요? 배치(batch) 단위로 요리함으로써, 이들은 기존 방식보다 약 100배 더 빠르게 이 복잡한 로봇 게임들을 해결할 수 있으며, 특수하고 비싼 하드웨어 없이도 일반 컴퓨터에서 이를 수행할 수 있다는 것입니다. 또한 그들은 레시피를 즉석에서 수정할 수 있게 만들었는데, 이는 로봇이 실수로부터 배우는 법을 가르치는 데 매우 중요합니다.

문제점: 로봇 교통 정체

로보틱스의 세계에서는 여러 에이전트(예: 고속도로 위의 자동차나 창고 안의 드론)가 동시에 움직여야 할 때 상황이 까다로워집니다. 각 에이전트는 자신의 목적지에 최대한 빨리 도착하고 싶어 하지만, 도로의 규칙을 준-수해야 하며 서로 부딪히지 않아야 합니다. 수학적으로 이것은 "비협력 게임(noncooperative game)"입니다. 이 게임의 해답은 다른 모든 이들이 하는 행동을 고려했을 때, 모두가 자신의 경로에 만족하는 특정 움직임의 집합입니다.

이 해답을 찾기 위해 로봇들은 혼합 상보성 문제(MCP)를 풀어야 합니다. MCP를 거대한, 엉클어진 매듭이라고 생각할 수 있습니다. 어떤 부분은 "당신이 차선 중간에 있다면, 속도는 0이어야 한다"라고 말합니다. 다른 부분은 "벽에 부딪히면, 멈춰야 한다"라고 말합니다. 여기에 "매개변수(parameter)"를 추가하면 매듭은 더욱 복잡해집니다(예: 자동차의 시작 위치를 바꾸거나 속도 제한을 변경하는 경우). 로보틱스에서는 다양한 시나리오(예: "차가 여기서 시작한다면? 저기서 시작한다면?")를 계획하기 위해 한 번에 수천 개의 이러한 매듭을 풀어야 할 때가 많습니다.

오랫동안 이 매듭을 푸는 업계 표준은 PATH라는 프로그램이었습니다. 그것은 신뢰할 수 있고 강력하지만, 세 가지 큰 결함이 있습니다:

1. **폐쇄형 소스(closed-source)**입니다. 즉, 개발자가 자신의 로봇에 맞게 수정하거나 커스터마이징하기 위해 내부를 들여다볼 수 없습니다.
2. 문제를 하나씩 풉니다. 만약 1,000개의 시나리오를 확인해야 한다면, 그것은 순차적으로 진행되므로 시간이 오래 걸립니다.
3. 머신 러닝과 잘 맞지 않습니다. 현대의 AI는 입력을 약간 수정했을 때 솔루션이 어떻게 변하는지(미분 과정) 알아야 하는 경우가 많지만, PATH는 이를 매우 어렵게 만듭니다.

해결책: 배치형 주방

이 논문의 저자는 Julia 프로그래밍 언어로 완전히 작성된 새로운 솔버인 MixedComplementarityProblems.jl을 구축했습니다. 그들의 접근 방식은 한 번에 한 접시의 요리를 만드는 단일 셰프에서, 전체 연회를 동시에 차려낼 수 있는 거대한 주방 팀으로 업그레이드하는 것과 같습니다.

그들이 이룬 방법은 다음과 같습니다:

1. "배치(Batched)"의 마법
하나의 로봇 게임을 풀고, 그다음 또 다른 게임을 푸는 대신, 새로운 솔버는 전체 "배치" 게임(예: 1,024개의 서로 다른 교통 시나리오)을 받아 한꺼번에 해결합니다.

• CPU (컴퓨터 프로세서) 상에서: 컴퓨터의 다중 코어를 사용합니다(마치 32명의 셰프가 병렬로 작업하는 것과 같습니다).
• GPU (그래픽 카드) 상에서: 그래픽 카드의 수천 개의 작은 코어를 사용합니다(마치 초고속 조립 라인을 사용하는 것과 같습니다).

영리한 점은 이 모든 게임이 숫자는 다르더라도 기본적인 구조(동일한 "매듭" 모양)를 공유한다는 것입니다. 솔버는 이를 인지하여 작업을 재사용하고, 각 시나리오에 대한 특정 숫자만 변경합니다.

2. "오픈 소스" 레시피
코드가 오픈 소스이고 Julia로 작성되었기 때문에, 누구나 코드를 살펴보고, 수정하거나, 자신의 로봇 소프트웨어에 연결할 수 있습니다. 또한 **자동 미분(automatic differentiation)**을 지원하는데, 이는 솔버가 "자동차의 시작 지점을 1인치 옮기면 전체 교통 패턴이 얼마나 변하는가?"를 즉각적으로 알려줄 수 있음을 의미합니다. 이는 AI 로봇을 훈련시키는 데 있어 강력한 무기가 됩니다.

3. "스마트 일시 정지(Smart Pause)"
배치 솔빙의 가장 큰 과제 중 중 하나는 어떤 문제는 쉽고, 어떤 문제는 어렵고, 어떤 문제는 불가능하다는 점입니다. 가장 어려운 문제가 끝날 때까지 기다린다면, 쉬운 문제들은 그냥 기다리며 시간을 허비하게 됩니다.
새로운 솔버는 특정 시나리오가 막혔거나 불가능하다는 것을 감지할 만큼 똑똑합니다. 솔버는 해당 문제를 "동결(freeze)"시키고 더 이상 시간을 낭비하지 않도록 멈추어, 나머지 배치가 계속 진행될 수 있도록 합니다. 이는 하나의 고집스러운 문제가 전체 그룹의 속도를 늦추는 것을 방지합니다합니다.

결과: 얼마나 빠른가?

연구진은 두 가지 유형의 문제(무작위 수학 퍼즐인 이차 계획법(Quadratic Programs)과 두 대의 차량이 충돌 없이 차선을 변경하려는 현실적인 "차선 변경" 게임)를 사용하여 기존 표준(PATH)과 새로운 솔버를 테스트했습니다.

• 신뢰성: 먼저, 새로운 솔버가 기존 솔버만큼 우수한지 확인했습니다. 결과는 동일했습니다. 새로운 솔버는 PATH와 동일한 수의 문제를 해결했으며, 이는 단순히 빠를 뿐만 아니라 정확하다는 것을 증로합니다.
• 속도: 그다음 속도를 측정했습니다.
  • 차선 변경 게임의 경우, 새로운 솔버는 1,024개의 시나리오 배치를 약 0.44초 만에 해결했습니다. 기존 PATH 방식은 46.4초가 걸렸습니다. 이는 105배의 속도 향상입니다.
  • 컴퓨터의 CPU(32개 스레드 사용)에서도 새로운 솔버는 PATH를 하나씩 실행할 때보다 100배 더 빨랐습니다.
  • GPU(그래픽 카드) 역시 매우 빨랐지만, 흥미롭게도 항상 승자인 것은 아니었습니다.

반전: 언제 GPU가 승리하는가 (그리고 언제 그렇지 않은가)

논문은 어떤 하드웨어를 사용할지에 대한 놀라운 세부 사항을 발견했습니다.

• CPU의 왕: 차선 변경 게임의 경우, CPU(32개 스레드 사용)가 실제로 GPU보다 더 빨랐습니다. 왜일까요? 차선 변경 게임의 수학적 구조가 "희소(sparse)"하기 때문입니다(대부분 빈 공간임). CPU는 빈 부분을 건너뛰고 활성화된 문제에만 집중할 수 있습니다. 반면 GPU는 동결되거나 이미 완료된 부분까지 포함하여 전체 배치를 한꺼번에 처리하려고 시도하므로 에너지를 낭비하게 됩니다.
• GPU의 챔피언: GPU는 문제가 매우 크고 "밀집(dense)"될 때(숫자로 가득 찰 때) 앞서 나갔습니다. 예를 들어, 무작위 수학 퍼즐의 크기를 키웠을 때, GPU는 CPU보다 3배 더 빨랐습니다.

이는 단 하나의 "최고의 기계"는 존재하지 않는다는 교훈을 줍니다. 만약 로봇 문제가 작고 희소하다면, 많은 코어를 가진 표준 컴퓨터가 최선입니다. 만약 문제가 거대하고 복잡하다면, 그래픽 카드가 앞서 나갑니다.

이것이 중요한 이유

이 논문은 단순히 더 빠른 계산기를 제공하는 것이 아니라, 새로운 사고방식을 제안합니다. 오픈 소스 도구를 사용하여 수천 개의 로봇 시나리오를 눈 깜짝할 사이에 해결할 수 있음을 보여줌으로써, 로보틱스의 주요 병목 현상을 제거했습니다.

• 실시간 계획: 이제 로봇은 많은 "만약에(what-if)" 시나리오를 즉각적으로 계획할 수 있어 더 안전하고 적응력이 높아집니다.
• 학습: 솔버가 미분을 지원하기 때문에, 엔지니어들은 이제 이러한 게임으로부터 직접 로봇이 더 나은 전략을 학습하도록 훈련시킬 수 있습니다.
• 접근성: 오픈 소스이므로 전 세계의 연구자들은 비싼 라이선스 비용을 지불하거나 하나의 문제가 끝날 때까지 기다릴 필요 없이 이 도구들을 사용할 수 있습니다.

요컨대, 저자는 복잡한 수학과 실제 로보틱스 사이의 가교를 구축했으며, 적절한 배치 처리 전략을 사용하면 이 혼란스러운 멀티 에이전트 로봇의 춤을 그 어느 때보다 빠르게 해결할 수 있음을 증명했습니다.