Distance-Constrained Unlabeled Multi-Agent Pathfinding

수천 대의 작고 동일한 배송 로봇들이 충전 스테이션에서 패키지 더미를 향해 질주해야 하는 북적이는 도시를 상상해 보십시오. 로봇 공학의 세계에서 이것은 다중 에이전트 경로 탐색(Multi-Agent Pathfinding, MAPF)이라고 불립니다. 보통 우리는 로봇들에게 "서로 충돌하지 마라"라고만 말합니다. 하지만 현실 세계는 훨씬 더 복잡합니다. 드론의 프로펠러가 이웃에게 먼지를 뿌릴 수도 있고, 대형 창고 로봇은 선반을 치지 않도록 안전 여유 공간을 확보해야 할 수도 있습니다. 이는 로봇들이 단순히 서로 "가까이" 있어서는 안 되며, 항상 특정 거리를 유지해야 함을 의미합니다.

이 논문이 다루는 과제는 서로 일정 수 이상의 발걸음보다 가까워져서는 안 되는 수백 명의 동일한 무용수들을 위한 춤을 안무하는 것과 같습니다. 만약 너무 가까워지면 그것은 "충돌"이 됩니다. 반전은 무엇일까요? 무용수들은 익명입니다. 즉, 특정 무용수가 반드시 특정 위치에 도달할 필요는 없으며, 모든 이가 안전하게 목적지에 도착하기만 하면 됩니다. 이는 간단해 보이지만, "멀리 떨어져 있어야 한다"라는 규칙을 추가하면 수학적으로 매우 어려워집니다. 마치 조각들이 계속 모양을 바꾸는 퍼즐을 푸는 것과 같으며, 때로는 문제를 해결하는 데 우주의 나이만큼 긴 시간이 걸릴 수도 있습니다.

이 논문은 저자들이 거리 r 독립 미식별 다중 에이전트 경로 탐색(또는 짧게 rIUMAPF)이라고 부르는 새로운 사고방식을 소개합니다. 그들은 표준 버전의 문제는 해결하기 쉽지만, "멀리 떨어져 있으라"는 규칙을 추가하면 컴퓨터가 솔루션의 존재 여부를 파악하는 것조차 악몽이 된다는 사실을 발견했습니다. 하지만 저자들은 손을 놓는 대신, 이 괴물을 상대하기 위해 두 가지 서로 다른 도구를 구축했습니다.

첫 번째 도구는 초정밀 설계자와 같습니다. 이 도구는 정수 선형 계획법(Integer Linear Programming, ILP)이라는 방법을 사용하여 가장 효율적이고 최적인 경로를 찾아냅니다. 이를 컴퓨터에서 작동시키기 위해 저자들은 영리한 "압축" 기술을 발명했습니다. 거대하고 쓸모없는 복도가 많은 미로를 상상해 보십시오. 설계자는 이 빈 공간들을 지나가는 로봇을 흡수하는 작은 마법의 블랙홀으로 축소하여, 미로를 훨씬 작고 빠르게 해결할 수 있게 만듭니다. 이 방식은 소규모 로봇 그룹에는 매우 효과적이지만, 로봇이 수백 대가 되면 수학적 계산이 너무 무거워져 설계자가 멈춰버리게 됩니다.

두 번째 도구는 빠르고 직관적인 즉흥 연주자입니다. 처음부터 끝까지 완벽한 경로를 계산하는 대신, 이 도구는 IU-PIBT라고 불리는 "구성 생성기"를 사용합니다. 이것은 현재 상황을 보고 각 로봇에게 "좋아요, 당신은 저기로 가고, 당신은 이리로 가세요"라고 단계별로 지시하는 교통 경찰과 같습니다. 이 방식은 매우 빠르며 거대한 로봇 떼도 처리할 수 있습니다. 그러나 때때로 교통 경찰이 혼란에 빠져 로봇들이 목적지에 도달하지 못한 채 제자리에서 뱅뱅 도는 현상(라이브락, livelock)이 발생할 수 있습니다. 이를 해결하기 위해 저자들은 IU-LaCAM이라는 "탐색" 레이어를 추가했습니다. 이는 교통 경찰을 지켜보는 스마트한 감독관 역할을 합니다. 만약 로봇들이 뱅뱅 돌기 시작하면, 감독관이 개입하여 목표를 재할당하고 교착 상태를 깨뜨립니다.

결과는 인상적입니다. 이 문제는 이론적으로 최악의 경우 영원히 걸릴 수도 있을 만큼 어렵지만, 저자들의 방법은 실제 적용 시 놀라울 정도로 잘 작동합니다. 저자들의 "즉흥 연주자"(IU-LaCAM)는 수백 명의 에이전트를 넓은 지도 위에서 몇 초 만에 처리하며, 다른 방법들을 당황하게 만들 문제를 해결해 냅니다. 저자들은 "설계자"(ILP)가 작고 고품질인 계획을 세우는 데는 뛰어나지만, 대규모의 혼돈 속에서는 "즉흥 연주자"가 영웅이라는 사실을 발견했습니다. 흥anche, 저자들은 더 큰 안전 거리(더 큰 "r")를 갖는 것이 오히려 문제를 더 쉽게 만들 수 있다는 점도 발견했는데, 이는 로봇들이 좁고 붐비는 통로에서 갇히는 것을 사전에 방지해주기 때문입니다.

요약하자면, 이 논문은 엄격한 안전 규칙과 동일한 로봇들이 있더라도 거대한 집단의 경로를 찾아낼 수 있음을 증명합니다. 저자들은 모든 가능한 버전을 해결한 것은 아닙니다(어떤 버전은 여전히 어떤 컴퓨터로도 풀 수 없을 만큼 어렵습니다). 하지만 그들은 우리가 거대한 로봇 군집을 대상으로 "이론적으로 불가능한" 상태에서 "실제로 실행 가능한" 상태로 나아갈 수 있게 해주는 도구 상자를 만들어냈습니다.