멀티에이전트 경로 계획으로 로봇 1만 대 조율하기 — CMU 로보틱스 세미나 정리

핵심 메시지

• 로봇이 수백 대를 넘어가면 개별 로봇의 똑똑함보다 교착과 정체를 막는 조율 알고리즘이 성능을 좌우한다.
• 충돌 기반 탐색 같은 고전 알고리즘은 품질은 좋지만 1분 안에 100여 대가 한계여서 실시간 운용에는 부족하다.
• 탐색 알고리즘이 만든 좋은 해를 교사로 삼아 모방 학습을 시키고, 전역 혼잡 정보와 격자 기반 통신을 더해 1만 대 규모까지 확장했다.
• 지도의 간선 가중치를 최적화해 로봇이 붐비는 구역을 스스로 피하게 만들자 실제 물류 창고 지도에서 처리량이 약 27% 늘었다.
• 계획을 시간표가 아니라 '통과 순서' 제약으로 바꾸면 로봇마다 속도가 달라도 충돌과 교착 없이 부드럽게 움직인다.

쉽게 이해하기

카네기멜런대 로보틱스 인스티튜트 세미나에서 자오양 리 조교수가 대규모 로봇 팀을 조율하는 연구를 발표했다. 발표의 출발점은 이미 현실이 된 물류 현장이다. 아마존식 물류센터에서는 수백 대의 로봇이 선반 밑으로 들어가 선반째 사람 앞으로 옮기고, 분류센터에서는 로봇들이 목적지별로 소포를 분류한다. 선반과 활송 장치가 그대로 장애물이 되기 때문에 로봇들은 몹시 혼잡한 공간을 비집고 다녀야 한다.

이런 환경에서 가장 먼저 터지는 문제는 교착이다. 발표자는 같은 판단 규칙을 쓰는 로봇 두 대가 자리를 맞바꾸려다 똑같은 선택만 반복해 영원히 멈춰 선 창고 영상, 좁은 통로에서 서로를 막아버린 식당 서빙 로봇 세 대의 영상을 예로 들었다. 두 번째 문제는 정체다. 로봇마다 각자 최단 경로를 짜고 단순한 통행 규칙으로 충돌만 피하게 하면 충돌은 막을 수 있어도 오늘날 도로처럼 곳곳에서 밀리게 된다. 세 번째는 실제 배치의 견고성으로, 배터리 잔량이나 짐 무게 때문에 로봇의 실제 속도가 계획과 어긋나고 통신 지연·유실이나 고장까지 겹친다.

그래서 목표는 세 가지로 정리된다. 어떤 상황에서도 충돌이 0이어야 하고, 1만 대 규모까지 확장돼야 하며, 교착 없이 전체 처리량을 최대로 끌어올려야 한다. 문제 자체는 다중 에이전트 경로 계획(MAPF)이라는 추상 모델로 표현된다. 격자 그래프 위에서 각 에이전트를 출발점에서 목표점까지 충돌 없이 옮기되 총 이동 시간을 줄이는 문제이고, 목표에 도착하면 곧바로 새 목표가 배정되는 변형에서는 정해진 시간 안에 처리한 목표 수, 즉 처리량이 척도가 된다.

고전적인 접근의 한계는 뚜렷하다. 모든 로봇의 위치를 묶은 결합 상태공간에서 A*를 돌리면 최적해는 나오지만 1분 제한에서 다섯 대 남짓이 한계다. 10여 년 전 제안된 충돌 기반 탐색(CBS)은 일단 각자 최단 경로를 짠 뒤 충돌이 생긴 지점에만 제약을 걸고 갈라지는 방식으로 같은 최적성을 유지하면서 120대 수준까지 올렸고, 이후 개선된 대규모 이웃 탐색 계열은 2~3천 대까지 다룬다. 그래도 중앙집중식으로 NP-난해 문제를 푸는 구조라 계산 시간이 지수적으로 늘고, 100밀리초 안에 결정을 내려야 하는 현장 요구와는 거리가 있다.

학습 기반 방법은 로봇마다 주변 시야만 보고 다음 행동을 고르게 하므로 원리상 규모에 구애받지 않지만, 실제로는 수십에서 수백 대 수준에 머물러 탐색 기반보다 못한 경우가 많았다. 발표자 연구실은 여기서 탐색 알고리즘이 만든 우수한 해를 교사 데이터로 삼는 모방 학습을 택하고 세 곳을 손봤다. 입력에는 전역 교통 상황을 담은 안내 정보를 넣어 로봇이 좁은 시야만 보고 혼잡 구역으로 뛰어드는 일을 막았고, 통신은 이웃 로봇의 잠재 표현을 원래 격자 좌표에 되돌려 배치한 뒤 다시 처리하는 방식으로 위치 정보를 정밀하게 살렸다. 마지막으로 신경망이 확률적으로 뽑은 행동은 충돌을 보장할 수 없으므로, 우선순위가 높은 로봇이 먼저 자리를 차지하고 밀린 로봇이 대안을 찾는 가벼운 우선순위 기반 트리 탐색을 후처리로 붙였다.

학습은 탐색 기반 교사가 충분히 잘 푸는 600대 규모 축소 지도에서 진행하고, 실제 평가는 1만 대에서 했다. 물류 로봇 업체가 후원한 경진대회 지도처럼 로봇 밀도가 40%에 이르는 조건에서도 처리량과 추론 속도 모두 기존 학습 기반·탐색 기반 방법을 앞섰다. 질의응답에서 발표자는 규모를 15배 더 키우는 것도 가능해 보이지만 중요한 것은 절대 대수가 아니라 로봇 밀도이며, 600대만으로도 군집 행동이 충분히 나타나기 때문에 그 크기를 학습용으로 골랐다고 설명했다.

주요 인사이트

• 알고리즘만 손볼 게 아니라 환경 자체를 최적화 대상으로 삼는 발상이 두 번째 축이다. 격자의 각 이동을 방향별 간선과 제자리 대기 간선으로 나누고 여기에 가중치를 주면, 기존 경로 계획기를 그대로 두고도 로봇의 행동을 바꿀 수 있다. 긴 통로의 한 방향 가중치를 크게 올리면 자연히 일방통행이 되고, 늘 붐비는 구역의 가중치를 올리면 로봇들이 알아서 우회한다.
• 이 가중치는 시뮬레이터를 블랙박스로 두고 진화 알고리즘류로 직접 최적화하거나, 직전 교통 흐름을 입력받아 새 가중치를 뱉는 신경망을 학습시켜 만든다. 후자는 실제 업체의 창고 지도와 실제 작업 분포에서 처리량을 약 27% 끌어올렸고, 작업 분포가 시간에 따라 바뀌는 상황에서는 가중치를 실시간으로 갱신하는 온라인 방식이 오프라인 방식보다 뚜렷이 유리했다.
• 현장에서 지금도 숙련 엔지니어가 손으로 통행 규칙을 그리고 시뮬레이터를 돌려 며칠씩 다듬는다는 점을 감안하면, 이 접근은 사람이 하던 반복 튜닝 루프를 신경망으로 대체한 것에 가깝다.
• 세 번째 축인 실행 단계는 계획 모델이 회전·가감속·통신 지연을 무시한 데서 생기는 간극을 메운다. 계획대로 시간표를 맞추려 하면 로봇들이 서로를 기다리느라 가다 서다를 반복한다. 회전과 가감속을 계획 모델에 넣으면 되지 않느냐는 접근은 이론상 맞지만 확장성을 무너뜨려, 수백 대를 풀던 알고리즘이 30대에서도 성공률 100%를 못 채웠다.
• 대신 계획 결과를 시간표가 아니라 '어느 지점을 누가 먼저 지나는가'라는 순서 제약 그래프로 바꾸면, 각 로봇은 자기 속도로 움직이다가 선행 조건이 충족될 때만 다음 칸으로 나아가면 된다. 이 방식은 충돌과 교착이 없음을 증명할 수 있고 통신 지연·유실이나 로봇 고장에도 안전이 유지되며, 바퀴형 로봇뿐 아니라 사족보행 로봇과 로봇 팔의 협동 조립까지 같은 틀로 다룰 수 있다.

자주 묻는 질문

관련 AI 소식