MAGIC, 지도 불확실성에서 공간 상관을 활용한 다중 에이전트 경로 탐색

초기 지도에 알려지지 않은 장애물이 있고 관측이 공간적으로 상관될 때, 국소 관측으로 관측되지 않은 위치의 주행 가능성을 추론해 다중 에이전트 경로를 어떻게 개선할 수 있는가?

실제 창고에서는 낙하물, 유출 등으로 지도와 다른 고정 장애물이 생기는데, 기존 MAPF는 모든 정적 장애물을 사전에 안다고 가정한다. MAPF-OU나 MAPF-IM 같은 기존 기법은 직접 관측한 위치만 반영하고 공간 상관을 이용하지 않아, 관측하지 않은 인근 장애물 때문에 나중에 비용이 큰 경로 재탐색을 겪는다.

MAPF-OU는 미래 관측에 분기하는 조건부 계획을 만들지만 불확실성이 커지면 계산 비용이 급증한다. MAPF-IM은 계획과 실행을 번갈아 하며 직접 관측된 위치가 바뀌면 재계획하지만, 관측 지점 밖의 주행 가능성은 추론하지 못한다. 기존의 가이던스 그래프나 불확실 그래프 단일 에이전트 계획도 다중 에이전트 충돌 해결과 결합하지 않았다.

MAGIC은 GMRF 잠재 점수와 Bernoulli probit 모델로 불확실한 위치 간 공간 상관을 표현한다. 에이전트가 인접한 불확실 위치를 관측하면 GaBP로 주변 미관측 위치의 사후 확률을 근사 추론한다. 각 간선의 주행 가능성은 양 끝점 신뢰도의 최솟값으로 추정하고, 해당 간선을 제거했을 때의 최단 우회 거리를 계산해 간선 비용 c_t(e)=b*1+(1-b)*C_det로 만든다. 이 비용을 CBS, EECBS, PBS, PIBT, LaCAM 등 표준 MAPF 플래너에 넘겨 충돌 없는 경로를 생성하며, 새로운 관측이 생길 때마다 신뢰도와 비용을 갱신하고 재계획한다.

소형 맵 5종, 시나리오당 25개×3 실현의 375개 인스턴스에서 CBS 기준으로 불확실 비율 φ=0.30일 때 MAGIC은 전체 정보 최적 SoC 대비 3.6% 높았고, optimistic replanning은 9.4%, MAPF-IM은 14.9% 높았다. 차단율 ρ=0.30에서 MAGIC 2.7%, optimistic 6.7%, MAPF-IM 12.4%였다. ρ=0에서는 MAGIC이 2.9% 높아 보수적 비용 때문에 손해를 보였다. 소형/중형/대형 티어에서 MAGIC은 MAPF-IM보다 96.3% 인스턴스에서 실행 SoC가 낮았고, 15개 플래너 구성 모두 평균 비율이 1 미만이었다. 중형 PBS 0.987, 대형 PIBT 0.992, 초대형 LaCAM 0.995 등 같은 플래너 대비 optimistic replanning보다 낮았다. 다만 대형 팀으로 갈수록 이점이 줄었고, 일부 설정에서 성공률은 계산 부담으로 optimistic replanning보다 낮았다. MAPF-IM은 n=100에서 성공 사례가 없었다. 사전 확률 정렬 실험에서는 aligned prior가 reversed prior보다 성공 사례의 실행 SoC를 3.40% 낮췄다.

저자들은 GMRF/GaBP 추론이 사이클 그래프에서 분산 근사에 그친다는 점, 간선 비용이 정확한 기대 비용이 아닌 국소 우회 대리 비용이라는 점을 밝혔다. 관측이 주행 가능이어도 재계획을 유발해 일부 어려운 인스턴스에서 성공률이 optimistic replanning보다 낮았고, 이는 계산 트레이드오프다. 실험은 일회성 MAPF에 한정됐고 실행 중 환경이 변하는 평생 과제는 다루지 않았다. 물리 로봇 검증은 TurtleBot 2대 규모의 정성 시연에 그쳤고, 코드 공개 여부는 논문에 보고되지 않았다.