다중 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF)은 장애물과 충돌을 피하면서 지도 위의 수많은 에이전트를 출발 지점에서 목적지까지 이동시키는 문제다. 창고 물류, 공항 물류, 무인 항공기 교통 관리, 주차 경로 안내, 비디오 게임 등 다양한 분야에 활용된다.
창고에서 자동으로 물품을 배송하는 경우처럼 에이전트가 지속적으로 이동하면, 문제는 평생 다중 에이전트 경로 탐색(lifelong MAPF, L-MAPF)이라는 새로운 형태로 전환된다. 에이전트는 목적지에 도착하자마자 새로운 목적지를 할당받는다. 따라서 장애물과 다른 에이전트와의 충돌을 피하면서 배송 물량과 같은 처리량을 높게 유지해야 한다.
이러한 평생 설정을 위해 다양한 방법이 제안되어 왔다. 대표적인 기준선인 백트래킹을 활용한 우선순위 상속(Priority Inheritance with Backtracking, PIBT)은 매우 빠르고 확장성이 높은 방법으로 강력한 기준선 역할을 하지만, 탐욕적으로 동작할 수 있다. PIBT와 대조적으로 널리 사용되는 또 다른 해법은 롤링 호라이즌 충돌 해결(Rolling-Horizon Collision Resolution, RHCR) 프레임워크다. RHCR은 높은 처리량을 달성하는 측면에서 가장 성능이 뛰어난 해법 중 하나로 평가된다.
하지만 RHCR은 특히 PIBT와 비교할 때 계산 비용이 높다. 창고에서의 로봇 주행처럼 실제적인 시나리오에서는 RHCR이 짧은 시간 안에 일회성 MAPF 솔버를 반복해서 실행해야 한다. 우선순위 기반 탐색(Priority Based Search, PBS)과 같은 비최적 솔버를 사용하더라도 RHCR의 계산 비용이 지수적으로 증가하는 현상을 관찰할 수 있다. 연구 커뮤니티에서는 RHCR을 기준선으로 실행하는 일이 시뮬레이션의 계산 비용을 크게 높이는 요소로 여겨지며, 시간 제한에 도달하기 전에 부분 계획을 보고하거나 더 작은 문제 집합에서 실행하는 경우가 많다. 실제로는 시간 제한에 도달하면 PIBT와 같은 다른 알고리즘으로 전환하는 폴백 메커니즘과 함께 RHCR을 사용할 수 있다.
에이전트 간 병렬화를 통해 RHCR을 가속하는 방안은 매력적으로 보이지만, RHCR의 성능을 희생하지 않으면서 이론적으로 타당한 방식으로 병렬화하는 방법은 여전히 해결되지 않은 문제로 남아 있다.
기여
이 연구의 목표는 이론적으로 타당한 병렬 RHCR 방법을 개발해 RHCR의 높은 처리량을 유지하거나 넘어서는 동시에, RHCR보다 훨씬 적은 계산 비용으로 계획을 수립하는 것이다. 이를 위해 RHCR을 위한 새로운 이론적 기반을 마련하고, 그 결과로 그룹 분산 RHCR(Group Decentralized RHCR, GD-RHCR)이라는 이론적으로 타당한 RHCR 병렬화 방법을 제안한다.
RHCR이 이미 처리할 수 있는 소규모 에이전트 수에서는 GD-RHCR이 많은 경우 비슷한 처리량을 달성하면서도 계획 수립 속도는 크게 향상된다. PIBT만 처리할 수 있는 대규모 에이전트 수에서도 GD-RHCR은 문제를 해결할 수 있으며, 일관되게 더 높은 처리량을 달성한다.
실험적 검증
다양한 지도에서 GD-RHCR을 실험적으로 검증했다. 평균 계획 수립 시간은 [보고된 속도 향상 계수]배 단축되며, RHCR의 성능이 붕괴하기 전까지 RHCR과 대등한 성능을 보인다. 또한 GD-RHCR은 에이전트 수가 많은 영역에서도 우수한 성능을 유지하며, PIBT 및 성능이 붕괴한 RHCR에 비해 처리량을 최대 [보고된 처리량 향상 폭]까지 높인다.
관련 연구
학습 기반 MAPF 방법
학습 기반 방법은 강화학습이나 모방학습을 직접 사용해 MAPF 문제를 해결한다. 이러한 방법은 분산화를 통해 어느 정도 병렬화를 수행할 수 있지만, 병렬화 또는 분산화로 인해 성능이 얼마나 저하되는지에 대한 보장은 없다.
평생 MAPF
평생 MAPF 연구는 대체로 느리지만 높은 품질의 해를 제공하는 RHCR과, 빠르지만 탐욕적인 PIBT 계열 해법으로 나뉜다.
RHCR은 일회성 MAPF 솔버를 평생 설정으로 확장할 수 있게 해주지만, 일회성 MAPF가 NP-hard이기 때문에 계산 시간이 크게 늘어날 수 있다.
PIBT는 일회성 상황과 평생 설정 모두에서 사용할 수 있는 방법이다. PIBT와 그 변형들은 여전히 빠른 대안이지만 탐욕적으로 동작하며, 그래프가 이중 연결이 아닐 때 교착 상태에 빠지는 경우가 많다.
이와 마찬가지로 다중 에이전트 강화학습 및 모방학습 방법도 이 설정을 위해 개발되어 왔다.
MAPF에서의 그룹화
여러 선행 연구에서는 에이전트를 그룹으로 묶어 계산을 가속하려고 시도했다. 정적 그룹화 방법은 지도를 여러 하위 영역으로 나누고 각 영역의 에이전트를 하나의 그룹으로 취급할 수 있다. 또 다른 연구에서는 더 정교한 방법을 통해 독립적인 그룹 구성을 동적으로 식별하려고 했다.
이는 함께 잘 협력할 수 있는 조정 그룹을 식별하기보다는, 완전성 보장을 유지하는 알고리즘의 속도를 높이는 맥락에서 이루어진다.
국소 상호 의존 다중 에이전트 MDP
MAPF 연구와 인접한 분야에서는 동적인 국소 의존성을 지닌 할인형 다중 에이전트 마르코프 결정 과정 환경에 대한 연구에서 최근 중요한 진전이 있었다. 국소 상호 의존 다중 에이전트 MDP(Locally Interdependent Multi-Agent MDP, LI-MDP)라는 모델은 국소적 상호작용을 지닌 다중 에이전트 시스템을 위한 이론적 모델로 제안되었다.
같은 연구에서는 가시성에 기반해 에이전트를 추이적으로 연결하는 그룹 분산 설정도 제안했다. 연결된 에이전트는 서로 협력할 수 있다. 중앙집중식 설정과 분산식 설정의 중간에 해당하는 이 특수한 관측 가능성 구조는 분산식 설정에서는 얻을 수 없는 강력한 이론적 보장을 제공한다. 예를 들어 가시성에 대해 최적해에 지수적으로 가까운 성능을 보장하면서도 에이전트 그룹이 병렬로 계획을 수립할 수 있다.
LI-MDP 프레임워크는 RHCR과 같은 기존 방법의 효과를 이해하고 준최적성에 가까운 성능을 증명하는 데 통찰을 제공한다. 또한 이러한 관측 가능성 구조를 통합한 GD-RHCR과 같은 새로운 방법을 제안하는 데 활용할 수 있다.
결론 및 향후 연구
이 연구는 LI-MDP 문헌의 방법을 활용해 RHCR의 이론적 기반을 제시한다. 이어 이러한 분석 기법을 바탕으로 새로운 GD-RHCR 프레임워크를 도출했다. GD-RHCR은 RHCR과 유사한 이론적 보장을 충족하며, RHCR보다 많은 에이전트 수에서도 다양한 지도에서 실험적으로 우수한 성능을 보인다.
그룹 분산은 MAPF 커뮤니티에서 비교적 새로운 개념이며, 다양한 방식으로 통합할 수 있다. 예를 들어 기존 학습 기반 방법과 결합하거나 PIBT와 같은 다른 방법을 병렬화하는 데 활용할 수 있다. 또한 이 연구는 위치나 환경에 따라 서로 다른 알고리즘을 사용할 수 있는 간단한 기반을 마련해, 앞으로 다양한 연구 방향을 열어 준다.
감사의 글
Guannan Qu는 NSF Grants 2339112 및 2512805, Jane Street, Pennsylvania Infrastructure Technology Alliance의 지원을 받았다. Jiaoyang Li는 NSF Grants 2328671 및 2441629의 지원을 받았다. Alex DeWeese는 Leo Finzi Memorial Fellowship in Electrical & Computer Engineering, David H. Barakat and LaVerne Owen-Barakat CIT Dean’s Fellowship, Fritsch Family Fellowship의 지원을 받았다.
절제 실험
warehouse-10-20-10-2-1에서 수행한 절제 실험 결과는 논문의 절제 실험 결과에 제시되어 있다.
자주 묻는 질문
평생 다중 에이전트 경로 탐색이란 무엇인가? 평생 MAPF는 에이전트가 이전 목적지에 도착할 때마다 새로운 목적지를 계속 할당하면서, 충돌을 피하고 높은 처리량을 유지하도록 하는 문제다.
RHCR의 계산 비용이 높은 이유는 무엇인가? RHCR은 일회성 MAPF 솔버를 반복해서 사용하는데, 이 솔버의 계산 비용은 에이전트 수가 많아질수록 지수적으로 증가해 시간 제한을 초과할 수 있다.
GD-RHCR이란 무엇인가? GD-RHCR은 RHCR을 그룹 단위로 분산 병렬화한 방법으로, 에이전트 그룹이 서로 협력하면서 병렬로 계획을 수립할 수 있게 한다.
GD-RHCR은 PIBT와 어떻게 비교되는가? GD-RHCR은 RHCR보다 많은 에이전트 수를 처리하며, 보고된 실험에서 PIBT보다 일관되게 높은 처리량을 달성한다.