로봇이 단순히 정해진 스크립트를 따르는 것이 아니라, 다른 로봇이 무엇을 생각하고 있는지까지 실제로 고민하는 세상을 상상해 보십시오. 이것은 다중 에이전트 모션 플래닝(multi-agent motion planning)의 영역으로, 기계들이 서로 충돌하지 않고 복잡한 공간을 항해할 수 있도록 돕는 로봇 공학의 한 분야입니다. 이 과제를 이해하기 위해, 교통 신호도 없고 서로 대화도 나누지 않는 분주한 교차로를 떠올려 보십시오. 만약 자동차 한 대가 좌회전을 하려고 한다면, 마주 오는 차가 속도를 높일지 아니면 줄일지를 추측해야 합니다. 과거에 로봇들은 종종 지나치게 조심스럽게 행동했습니다. 마치 100% 확신이 들 때까지 절대 움직이지 않는 불안한 운전자처럼 행동하여 결국 정체를 유발하곤 했습니다. 이를 해결하기 위해 과학자들은 경제학의 개념인 '게임 이론(Game Theory)', 특히 '내쉬 균형(Nash Equilibrium)'을 살펴봅니다. 이를 완벽한 균형 상태라고 생각하십시오. 이는 다른 모든 이가 하는 행동을 고려했을 때, 자신의 움직임을 바꾸는 것이 자신에게 더 나쁜 결과를 초래하기 때문에 아무도 전략을 바꿀 이유가 없는 상태를 의미합니다. 이는 마치 모두의 전략이 완벽하게 어우러져 누구도 발을 밟지 않는 잘 짜인 춤과 같습니다.

핵심적인 질문은 이것입니다: 물리 법칙(예를 들어 자동차가 회전할 수 있는 속도) 때문에 수학적 계산이 매우 복잡해질 때, 어떻게 로봇이 실시간으로 이 완벽한 춤 동작을 찾아내게 할 것인가? 테크니온 이스라엘 공과대학교(Technion–Israel Institute of Technology) 연구진의 새로운 논문은 '게임 이론적 중첩 탐색(Game-Theoretic Nested Search, GTNS)'이라는 영리한 솔루션을 소개합니다. 그들은 기존 방식들이 지역적인 '막다른 길(dead ends)'에 갇히거나 모든 가능한 움직임을 계산하는 데 너무 많은 시간이 걸렸던 반면, 그들의 새로운 접근 방식은 마치 아주 똑똑한 탐정처럼 작동한다는 것을 발견했습니다. 모든 가능성을 거대한, 스캔 불가능한 도서관처럼 일일이 확인하는 대신, GTNS는 '중첩된(nested)' 전략을 사용합니다. 이 방식은 최적의 전체 경로를 찾는 '외부 탐색(outer search)'을 수행하면서도, 동시에 단 한 대의 로봇이라도 독자적으로 행동하여 더 나은 결과를 얻을 수 있는지 확인하는 빠른 '내부 테스트(inner test)'를 끊임없이 실행합니다. 만약 어떤 로봇이 이탈하여 더 나은 결과를 얻을 수 있다면, 그 경로는 즉시 폐기됩니다. 이를 통해 시스템은 자동차가 공격적으로 차선에 합류하거나 레이서가 다른 차량을 추월하는 것과 같은 복잡하고 현실적인 상호작용을 표준 노트북에서 단 몇 초 만에 찾아낼 수 있습니다.

문제점: 로봇의 딜레마

당신이 세 명의 친구와 함께 비디오 게임을 하고 있다고 상상해 보십시오. 모두가 결승선을 통과하고 싶어 하지만, 길은 좁고 서로 대화할 수는 없습니다. 만약 모두가 앞으로 돌진하려고 하면 충돌할 것입니다. 만약 모두가 멈춰서 기다린다면, 결코 끝에 도달하지 못할 것입니다. 현실 세계에서 자율주행 자동차와 레이싱 드론은 정확히 이 문제에 직면해 있습니다. 그들은 타인이 무엇을 할지 예측하고 즉각적으로 반응해야 합니다.

오랫동안 로봇들은 '리더를 따르기'를 하거나 지나치게 조심스럽게 행동하며 이 문제를 해결해 왔습니다. 그들은 타인이 무엇을 할지 추측하고, 안전한 경로를 선택한 뒤, 결과가 좋기를 바랐습니다. 하지만 이는 종-종 황당한 상황을 초래했습니다. 예를 들어, 자동차가 움직이는 것이 두려워 텅 빈 교차로에서 영원히 기다리는 상황 같은 것 말입니다. 다른 방법들은 '완벽한' 균형(내쉬 균형)을 찾기 위해 복잡한 수학을 사용하기도 했지만, 종종 지역적인 함정에 빠지거나 로봇이 실제 장애물이나 까다로운 회전을 처리할 수 없도록 세상을 너무 단순화해야만 했습니다.

솔루션: 두 개의 돋보기를 든 탐정

이 논문의 저자인 아비샤브 엥글(Avishav Engle)과 그의 팀은 **게임 이론적 중첩 탐사(GTNS)**라는 새로운 알고리즘을 구축했습니다. 이 알고리즘이 어떻게 작동하는지 이해하기 위해, 거대한 다층 건물(탐색 공간)에서 미스터리를 풀려는 탐정을 상상해 보십시오.

1. 외부 탐색 (탐정): 탐정은 건물을 돌아다니며 출구로 가는 최적의 경로를 찾습니다. 이것이 '외부' 계층입니다. 이는 최단 경로를 찾으려는 일반적인 GPS와 같습니다.
2. 내부 탐색 (심문): 하지만 반전이 있습니다. 탐정은 새로운 경로를 고려할 때마다 멈춰 서서 결정적인 질문을 던집니다: "만약 내가 이 시나리오의 인물 중 한 명이라면, 다른 모든 사람이 자신의 경로를 유지하는 동안 몰래 빠져나가 더 빠른 지름길을 택할 수 있을까?"
   • 이것이 '내부' 계층입니다. 이는 관련된 모든 로봇에 대한 빠르고 집중적인 체크입니다.
   • 만약 답이 "그렇다, 나는 이탈하여 승리할 수 있다"라면, 탐정은 이 경로가 진정한 내쉬 균형이 아님을 알게 됩니다. 그 경로는 즉시 폐기됩니다.
   • 만약 답이 "아니요, 더 잘할 수 없다"라면, 그 경로는 안전하고 균형 잡힌 것입니다.

이 '중첩된' 접근 방식은 강력합니다. 왜냐하면 명백히 불안정한 경로를 확인하는 데 시간을 낭비하지 않기 때문입니다. 이는 식물이 더 빨리 자랄 수 있도록 죽은 가지를 쳐내는 정원사처럼 나쁜 옵션을 조기에 제거합니다.

연구 결과: 공격적인 합류부터 공손한 양보까지

연구진은 고속도로 합류부터 레이스 트랙 추월에 이르기까지 다양한 시나리오에서 알고리즘을 테스트했습니다. 그들은 시스템의 몇 가지 '노브(knobs, 조절 장치)'를 조정함으로써 로봇의 성격을 바꿀 수 있다는 것을 발견했습니다.

• "지퍼 합류(Zip-Merge)": 한 실험에서, 그들은 로봇 1(파란색 자동차)을 더 공격적으로 만들도록 설정을 조정했습니다. 그 결과, 로봇 1은 두 대의 다른 차량 사이의 좁은 틈으로 성공적으로 끼어드는 '지퍼 합류' 동작을 수행했습니다.
• "공손한 양보(Polite Yield)": 설정을 반대로 하여 로봇 1을 더 조심스럽게 만들었을 때, 로봇 1은 다른 차량들이 지나갈 때까지 기다린 후 합류했습니다.
• 레이스 트랙: 레이싱 시뮬레이션에서, 그들은 우선순위 숫자를 변경함으로써 누가 경주에서 이길지를 결정할 수 있었습니다. 만약 로봇 1이 높은 우선순위를 가졌다면, 로봇 1은 안쪽 라인을 타고 승리했습니다. 만약 로봇 2가 우선순위를 가졌다면 역할이 뒤바뀌었습니다.

이것이 특별한 이유는 이러한 결과들이 단순한 무작위 추측이 아니기 때문입니다. 알고리즘은 솔루션이 진정한 내쉬 균형임을 보장합니다. 이는 일단 로봇들이 움직이기 시작하면, 다른 이들이 하는 행동을 고려했을 때 이미 최선을 다하고 있으므로, 그들 중 누구도 갑자기 마음을 바꿔 경로를 이탈할 이유가 없음을 의미합니다.

속도와 현실성

팀은 강력한 프로세서(Intel Core i9)를 갖춘 표준 노트북에서 이러한 시뮬레이션을 실행했습니다. 결과는 인상적이었습니다:

• 단순한 시나리오의 경우, 컴퓨터는 1초도 안 되어 솔루션을 찾아냈습니다.
• 더 복잡한 다중 로봇 고속도로 합류의 경우, 몇 초(일부 사례에서는 약 3~4초)가 소요되었습니다.
• 로봇의 수가 늘어나거나 경로가 길어지더라도, 시스템은 기존 방식만큼 느려지지 않았습니다.

논문은 수학적 계산을 용이하게 하기 위해 로봇의 물리 법칙을 단순화(예: 즉각 회전할 수 있는 점으로 가정하는 것)할 필요가 없다는 점을 명시적으로 배제합니다. GTNS는 자동차와 드론의 속도 제한 및 회전 반경을 포함한 실제의 복잡한 물리 법칙을 처리합니다.

이것이 중요한 이유

이것은 단지 이론적인 게임이 아닙니다. 이러한 상호작용을 빠르게 계산할 수 있다는 능력은, 미래에 자율주행 자동차가 교통 체증이나 사고 없이 번잡한 도시 거리를 항해할 수 있음을 의미합니다. 그들은 교통 신호나 무선 신호 없이도 통행 우선권을 협상할 수 있습니다.

연구진은 또한 그들의 방법이 AI를 위한 학습 데이터를 생성하는 데 사용될 수 있다고 언급했습니다. 이러한 '완벽하게 균형 잡힌' 상호작용을 수천 번 시뮬레이션함으로써, 그들은 다른 AI 시스템이 안전하고 예측 가능하게 행동하는 방법을 가르칠 수 있습니다.

현재 시스템은 로봇의 경로가 사전에 계획되는 환경("오픈 루프" 설정)에서 가장 잘 작동하지만, 저자들은 이것이 큰 진전이라고 제안합니다. 그들은 초기 지도를 만드는 데 시간이 걸린다는 점을 인정하지만, 일단 구축되면 시스템은 빠르고 신뢰할 수 있습니다. 그들은 이미 더 많은 로봇과 함께, 그리고 로봇이 변화에 즉각 반응해야 하는 실시간 "클로즈드 루프(closed-loop)" 상황에서도 더 잘 작동할 수 있도록 하는 방법을 연구하고 있습니다.

요약하자면, GTNS는 로봇에게 방 안의 분위기를 읽고, 누군가 충돌하거나 영원히 기다리는 일 없이 모두가 승리할 수 있는 해결책을 찾는 능력을 부여합니다. 그것은 혼란스러운 교통의 춤을 순식간에 계산된 하나의 정교한 공연으로 바꿉니다.