(ECBS) 다중 에이전트 경로 찾기 문제를 위한 충돌 기반 탐색 알고리즘의 차선(次善) 버전들

발표 준비

Abstract(요약)

다중 에이전트 경로 찾기 문제(MAPF)는 각기 다른 시작 위치와 목표 위치를 가진 여러 에이전트를 위한 경로를 찾되, 에이전트들이 서로 충돌하지 않도록 하는 것입니다. 성공적인 최적 MAPF 해결책 중 하나로 충돌 기반 탐색(CBS) 알고리즘이 있습니다. CBS는 두 단계로 이루어진 알고리즘이며, 특정 조건을 통해 최적의 해결책을 반환하도록 보장합니다. 그러나 MAPF 문제를 최적으로 해결하는 것은 NP-hard 문제로 증명되었으며, 이로 인해 CBS를 포함한 모든 최적 해법은 확장성이 떨어집니다.

우리는 CBS의 최적 조건을 완화하여 해결 시간을 줄이고, 유한-부분 최적(bounded-suboptimal) 변형을 제안합니다. 이 변형은 반환되는 해결책이 최적 해결책 비용의 일정한 배수 이내에 있도록 보장합니다. 실험 결과에 따르면, 우리의 새로운 접근 방식은 실행 시간을 대폭 줄이면서도 해결책의 품질 손실을 최소화하는 이점을 제공합니다. 새로운 알고리즘들은 대부분의 경우에서 기존 알고리즘보다 더 나은 성능을 발휘합니다.

<aside> ✅

이 논문은 MAPF 문제를 효율적으로 해결하기 위해 최적 조건을 완화한 새로운 알고리즘이 기존 알고리즘보다 더 나은 성능을 보인다는 것을 주장하고 있습니다.

</aside>

Introduction(서론)

다중 에이전트 경로 찾기 문제(Multi-Agent Path Finding, MAPF)는 그래프 G=(V,E)G = (V, E)와 에이전트 집합 k로 정의됩니다. 각 에이전트 ai는 시작 위치 si와 목표 위치 gi를 가지고 있으며, 매 시간마다 인접 위치로 이동하거나 현재 위치에서 대기할 수 있으며, 두 행동 모두 비용이 1.0입니다. 이 문제의 목표는 각 에이전트가 다른 에이전트와 충돌하지 않도록 ai의 이동/대기 행동 시퀀스를 계획하여 si에서 gi로 이동하도록 하는 것입니다. 또한 누적 비용 함수가 최소화되는 것이 목표입니다. MAPF는 비디오 게임, 교통 관리, 로봇 공학, 항공 등 다양한 실제 응용 분야에서 사용될 수 있습니다.

MAPF를 최적의 방식(즉, 최소 비용의 충돌 없는 해결책)으로 해결하는 것은 NP-완전(NP-Complete) 문제로, 최적 MAPF 해결책들은 확장성 문제를 겪습니다. 부분 최적 MAPF 해결책들은 상대적으로 빠르게 실행되지만, 반환된 해결책의 품질을 보장하지 않으며 일부는 완전하지 않습니다. 유한-부분 최적(bounded suboptimal) 알고리즘은 최적 해결책 비용의 일정 배수를 넘지 않는 해결책을 보장합니다.

충돌 기반 탐색(CBS) 알고리즘은 MAPF 문제를 최적으로 해결하기 위한 2단계 알고리즘입니다. 상위 레벨은 각 에이전트에 최적의 해결책을 보장하기 위해 제한 조건 집합을 탐색하고, 하위 레벨은 상위 레벨에서 설정한 제한 조건 하에서 개별 에이전트 문제의 최적 해결책을 찾습니다.

본 논문에서는 상위와/또는 하위 레벨의 탐색을 완화하여 부분 최적 해결책을 반환할 수 있도록 하는 여러 CBS 기반의 유한-부분 및 무한-부분 최적 MAPF 해결책을 제안합니다. 먼저, 가능한 빠르게 (부분 최적일 수 있는) 해결책을 찾도록 설계된 CBS 기반 MAPF 해결책인 **Greedy-CBS (GCBS)**를 소개합니다. 다음으로, 상위 및 하위 레벨 모두에 초점 리스트(focal-list) 메커니즘을 사용하는 **Bounded CBS (BCBS)**를 제안하여 반환된 해결책이 주어진 부분 최적 경계 내에 있도록 보장합니다. 마지막으로, 상위 및 하위 레벨이 공동 부분 최적 경계를 공유하는 유한-부분 최적 MAPF 해결책인 **Enhanced CBS (ECBS)**를 소개합니다.

실험 결과, 모든 변형에서 CBS보다 상당한 속도 향상이 나타났습니다. 예를 들어, 한 도메인(DAO)에서 CBS는 최대 50명의 에이전트 문제를 해결할 수 있었던 반면, GBCS는 250명의 에이전트 문제를 모두 해결했고, ECBS는 최대 200명의 에이전트 문제 중 절반 이상을 해결하면서 최적 해보다 최대 1% 낮은 품질의 해결책을 보장했습니다. 다른 부분 최적 MAPF 해결책들과 비교했을 때, ECBS는 거의 항상 대안 유한-부분 최적 해결책들보다 더 나은 성능을 보였고, GCBS는 많은 도메인에서 최고 성능을 보였으나 모든 도메인에서 그렇지는 않았습니다.

<aside> ✅

서론에서는 다중 에이전트 경로 찾기 문제(MAPF)의 정의와 이를 해결하기 위한 접근 방식, 그리고 본 논문에서 제안하는 알고리즘을 설명합니다.

  1. MAPF 문제 정의: 여러 에이전트가 주어진 그래프 내에서 충돌 없이 각자의 목표 위치로 이동해야 하는 문제입니다. 이 문제는 비용을 최소화하는 방식으로 경로를 찾는 것을 목표로 하며, 다양한 실제 상황에서 적용할 수 있습니다(예: 비디오 게임, 교통 관리, 로봇 공학, 항공).
  2. NP-완전 문제: MAPF를 최적의 방식으로 해결하는 것은 NP-완전 문제로, 문제의 크기가 커지면 기존 최적 해법은 확장성이 떨어집니다.
  3. 해결 접근법 - 충돌 기반 탐색(CBS): 기존의 CBS 알고리즘은 두 단계로 이루어집니다. 상위 레벨에서 제한 조건을 설정하고, 하위 레벨에서 개별 에이전트가 이 제한 조건 하에서 최적 경로를 찾습니다. 이 방식은 최적 해결책을 보장하지만 속도와 확장성에서 한계가 있습니다.
  4. 논문의 기여 - 부분 최적 알고리즘 제안:
  5. 실험 결과: 새로운 알고리즘들이 기존 CBS보다 훨씬 빠르게 동작하면서도 품질 손실을 최소화함을 입증했습니다. 특히 ECBS는 다른 부분 최적 MAPF 해결책들보다 대부분의 경우 더 나은 성능을 보였고, GCBS는 일부 도메인에서 최고 성능을 나타냈습니다.

결론적으로, 논문에서는 CBS 알고리즘의 최적 조건을 완화해 MAPF 문제를 더욱 효율적으로 해결할 수 있는 방법을 제시하며, 이를 통해 확장성 문제를 해결할 수 있음을 보여주고 있습니다.

</aside>

도메인이란

MAPF 알고리즘이 적용되는 문제 환경 또는 테스트 환경을 의미

즉, 다중 에이전트 경로 찾기(MAPF) 문제를 해결할 때 에이전트들이 활동하는 특정 맵이나 상황을 가리킵니다.

각 도메인은 에이전트들의 경로 설정과 충돌 회피에 다양한 난이도를 제공할 수 있습니다.

예를 들어, 에이전트의 숫자나 장애물의 위치에 따라 도메인의 복잡도가 달라질 수 있습니다.

DAO는 “Dragon Age Origins”라는 게임의 맵을 사용한 도메인입니다. 연구자들이 비디오 게임의 실제 맵을 MAPF 실험에 활용하여 다양한 경로 설정 환경을 제공합니다. DAO 맵은 복도와 병목 구간이 많은 구조로, 에이전트들이 경로를 설정할 때 충돌이 많이 발생할 수 있는 복잡한 환경입니다.