거대한 보이지 않는 퍼즐을 상상해 보세요. 수천 대의 작은 로봇들이 중앙의 보스 없이 서로 협력해야 합니다. 이것이 바로 분산 제약 최적화(Distributed Constraint Optimization), 줄여서 DCOP의 세계입니다. 모든 플레이어가 누구와 옆에 앉을 수 있는지에 대한 자신만의 규칙을 가지고 있고, 그룹 전체의 즐거움을 극대화하고 싶어 하는 거대한 의자 뺏기 게임과 같습니다. 하지만 여기에는 함정이 있습니다. 그들은 오직 자신의 이웃에게만 속삭일 수 있으며, 퍼즐이 너무 거대해서 단 하나의 컴퓨터로는 결코 전체를 한꺼번에 해결할 수 없다는 점입니다. 이러한 설정은 지구 궤도를 도는 위성 군단처럼, 중앙 제어 장치가 갑작스러운 변화에 대응하기에는 너무 느린 실제 세계의 혼돈에 완벽하게 부합합니다. 과학자들이 던져온 핵심 질문은 이것입니다. "전체 그림을 볼 수 없을 만큼 퍼즐이 클 때, 어떻게 독립적인 에이전트들이 효율적으로 협력하게 만들 것인가?"

이 새로운 연구에 따르면, 그 답은 두 가지 영리한 기술에 있습니다. 하나는 로봇들에게 "온라인 학습"(수천 번의 플레이를 통해 실력을 키우는 비디오 게임 플레이어처럼)을 통해 실수로부터 배우도록 가르치는 것이고, 다른 하나는 "가격 책정(pricing)" 시스템을 사용하여 그들이 나쁜 아이디어에서 자연스럽게 멀어지도록 유도하는 것입니다. 실제 위성 미션의 데이터를 활용해 연구한 저자들은 이 두 가지 방법을 결합함으로써, 기존 방식들이 어려움을 겪었던 거대한 위성 스케줄링 문제를 해결할 수 있음을 발견했습니다. 모든 세부 사항을 하나의 거대한 방정식에 강제로 밀어 넣는 대신, 그들은 문제를 두 개의 층으로 나누었습니다. 즉, '누가 무엇을 할지'를 결정하는 상위 수준의 관리자와, 실제로 충돌 없이 '그 일을 어떻게 수행할지'를 결정하는 지역 전문가로 나눈 것입니다. 지역 전문가들이 작업이 너무 까다로워 맞추기 힘들 때마다 관리자에게 "가격표"를 보내게 함으로써, 시스템은 불가능한 조합을 피하는 법을 배웠습니다. 결과는 어떠했을까요? 시뮬레이션에서 이 새로운 방식은 60대의 위성 함대가 요청한 관측 요청의 99% 이상을 수행해 냈으며, 이는 기존의 가장 뛰어난 방식들이 약 87%를 달성했던 것을 능가하는 성과였습니다. 이는 마치 지휘자가 모든 바이올리니스트를 일일이 마이크로 매니징하려 하지 않고, 대신 섹션 리더들의 소리에 귀를 기울이며 오케스트라 전체가 완벽한 조화를 이룰 때까지 악보를 조정하는 것과 같습니다.

문제점: 너무 많은 위성, 부족한 두뇌

이 논문은 우주 탐사에서의 구체적인 골칫거리를 다룹니다. 바로 지구 관측 위성의 스케줄링입니다. 60대의 위성 군단(꿀벌 떼와 같은)이 도시, 폭풍 또는 재난의 사진을 찍기 위해 수천 건의 요청을 처리해야 한다고 상상해 보세요. 각 위성은 고유한 규칙을 가집니다. 동시에 두 곳을 볼 수 없고, 사진을 저장할 메모리가 제한되어 있으며, 특정 지상국 상공을 지날 때만 데이터를 다운로드할 수 있습니다.

전통적으로 과학자들은 이를 하나의 거대한 단일 퍼즐로 해결하려고 노력했습니다. 모든 규칙과 모든 위성을 거대한 컴퓨터 모델에 집어넣는 방식이었죠. 하지만 위성의 수가 늘어남에 따라 이 접근 방식은 무너집니다. 수학적 복잡성이 너무 커져서 해결하는 데 영원히 걸리거나, 아예 시스템이 다운되어 버립니다. 이는 마치 축구장 크기의 격자를 가진 스도쿠 퍼즐을 푸는 것과 같습니다. 한 번에 전체 판을 다 볼 수가 없는 것이죠.

해결책: 두 팀 전략

저자들은 업무를 두 개의 서로 다른 팀으로 나누어 협력하는 새로운 방식을 제안합니다.

팀 1: 상위 수준 할당자 (The "Meta-DCOP")
이 팀은 배차 담당자 역할을 합니다. 이들의 유일한 임무는 어떤 위성에 어떤 관측 요청을 할당할지 결정하는 것입니다. 배터리 수명이나 메모리 같은 세세한 디테일은 신경 쓰지 않습니다. 그저 업무를 배분할 뿐입니다. 이 팀은 결정을 내리기 위해 온라인 학습 알고리즘을 사용합니다. 이것은 학생들이 시험을 치르는 것과 비슷합니다. 틀린 답을 낼 때마다 그들은 약간의 "후회(regret)"를 느낍니다. 시간이 흐르면서 그들은 후회를 불러일으켰던 답은 피하고, 효과가 있었던 답을 고수하는 법을 배웁니다. 논문은 어떤 종류의 "후회 학습"이 팀이 최적의 스케줄을 가장 빠르게 찾도록 도와주는지 확인하기 위해 여러 현대적 버전을 테스트합니다.

팀 2: 지역 스케줄러 (The "Oracles")
팀 1이 할당 목록을 전달하면, 팀 2(개별 위성)는 실제로 스케줄을 짭니다. 각 위성은 자신만의 로컬 솔버(smart program)를 실행하여 할당된 작업들이 자신의 메모리, 배터리, 시야각 내에 들어맞는지 확인합니다. 만약 위성이 도저히 함께 수행할 수 없는 작업 목록을 받게 되면(마치 피자 한 판과 케이크 한 판을 동시에 먹으려고 하는 것처럼), 위성은 "안 됩니다, 이건 못 합니다"라고 말합니다.

마법의 접착제: 반복적 가격 책정 (Iterative Pricing)

여기서 논문의 핵심 혁신이 빛을 발합니다. 바로 반복적 가격 책정입니다.

과거에는 위성이 "할 수 없다"고 말하면, 시스템은 그냥 그 목록 전체를 버리고 다시 시도하거나, "이 위성에는 절대 이 특정 작업 목록을 주지 마라"는 식의 엄격한 규칙을 추가했습니다. 이는 마치 선생님이 "너 시험 망쳤으니까, 앞으로 이 시험은 다시는 못 봐"라고 말하는 것과 같은 투박한 방식입니다.

새로운 방식은 가격을 사용합니다.

1. 상위 수준 할당자가 작업을 할당합니다.
2. 지역 스케줄러가 이를 수행하려고 시도합니다.
3. 만약 위성이 특정 작업을 스케줄링하는 데 실패하면, 시스템은 그 할당에 "가격표"를 붙입니다.
4. 다음번에 상위 수준 할당자는 특정 작업과 위성의 조합이 이제 "비싸졌다"(이전에 실패했기 때문에)는 것을 인지하고, 자연스럽게 그 조합을 피하며 다른 대안을 찾습니다.

이는 시장과 같습니다. 만약 어떤 판매자가 특정 주문을 계속 이행하지 못한다면, 그 주문의 가격은 올라갑니다. 결국 시스템은 그 판매자에게 특정 업무를 주문하는 것을 금지해서가 아니라, 비용이 너무 많이 들기 때문에 주문하지 않도록 학습하게 됩니다. 이 피드백 루프는 반복적으로 일어나며, 거의 모든 것이 들어맞을 때까지 스케줄을 정교하게 다듬습니다.

결과: 완벽에 가까운 스케줄링

연구진은 실제 시나리오를 모사한 시뮬레이션에서 이 실험을 진행했습니다. 저궤도를 도는 60대의 위성이 6시간 동안 634개의 주요 도시를 촬영하는 상황입니다. 그들은 이 새로운 "반복적 가격 책정" 방식을 Neighborhood Stochastic Search (NSS)라는 유명한 기존 기법을 포함한 현재 최고의 기술들과 비교했습니다.

결과는 놀라웠습니다. 기존 방식들은 관측 요청의 약 **87%**를 성공적으로 스케줄링했습니다. 반면, 스마트한 온라인 학습과 가격 시스템을 결합한 새로운 방식은 요청의 **99.2%**를 수행해 냈습니다.

논문은 또한 이 성공의 "비용"도 살펴보았습니다. 새로운 방식은 기존 방식(84,000건의 메시지)보다 더 많은 통신(약 130만 건의 메시지)을 필요로 했습니다. 그러나 저자들은 요청을 놓치는 것이 매우 큰 비용을 초కు하는 중요한 임무에서는 이러한 트레이드오프(trade-off)가 충분히 가치 있다고 주장합니다. 그들은 이 접근 방식이 다중 에이전트 AI의 가장 큰 시연이 될 예정인 NASA의 FAME 미션을 포함하여, 실제 현장에서 사용할 준비가 되었다고 언급했습니다.

하지 않은 것 (그리고 배제한 것)

이 논문이 찾아내지 못한 점을 명시하는 것도 중요합니다. 저자들은 이러한 종류의 알고리즘을 안정화하기 위해 사용되는 두 가지 흔한 기법인 **댐핑(damping, 급격한 변화를 완화하기 위해 변화를 부드럽게 만드는 것)**과 **관성(inertia, 에이전트가 생각을 바꾸는 것을 주저하게 만드는 것)**을 테스트했습니다. 놀랍게도, 그들은 이러한 안정화 기능들을 추가하는 것이 오히려 온라인 학습 알고리즘을 악화시킨다는 것을 발견했습니다. 이 특정 유형의 문제에서는, 에이전트들이 생각을 빠르게 바꾸고 즉각적인 후회로부터 배우도록 내버려 두는 것이 안정성을 유지하려 애쓰는 것보다 더 낫다는 결론을 얻었습니다.

또한, 모든 물리적 제약 조건(메모리 제한 등)을 메인 글로벌 퍼즐에 직접 인코딩할 필요가 없다는 점도 입증했습니다. 그들의 방식은 글로벌 퍼즐을 단순하게 유지하면서도, 로컬 전문가들이 복잡한 물리 법칙을 처리하게 하고, 오직 "가격"이라는 단순한 언어로만 소통해도 충분하다는 것을 증명했습니다.

왜 중요한가

이것은 단지 위성에 관한 이야기가 아닙니다. 저자들은 이 "두 단계" 접근 방식이 큰 규모의 그룹이 고차원적인 계획을 세우면서 동시에 복잡한 로컬 문제를 해결해야 하는 모든 상황에 적용될 수 있다고 제안합니다. 배송 트럭이 스스로 경로를 찾는 것이나, 드론 군단이 패키지를 배달하는 상황 등을 생각해보세요. "누가 무엇을 할지"와 "어떻게 할지"를 분리하고, 실패로부터 배우는 가격 시스템을 사용함으로써, 우리는 슈퍼컴퓨터의 일일이 간섭 없이도 복잡한 현실의 혼돈을 처리할 수 있는, 똑똑하고 확장 가능한 시스템을 구축할 수 있습니다.