기술 요약: 동적 다중 에이전트 경로 탐색 방법론에 대한 검토, 시뮬레이션 및 수정

1. 문제 정의

본 논문은 동적 환경, 부분 관측성(partial observability), 그리고 에이전트 간의 협업이 교차하는 복잡한 계획 문제인 **동적 다중 에이전트 경로 탐색(Dynamic Multi-Agent Pathfinding, D-MAPF)**을 다룬다. 지도가 고정된 정적 MAPF와 달리, D-MAPF는 장애물이 알 수 없는 일정에 따라 나타나고 사라지는 환경을 포함한다. 또한, 에이전트는 전역적인 환경 지식을 갖는 대신, 자신의 특정 가시 범위(레이 캐스팅을 통해) 내로 진입했을 때만 장애물을 감지하는 부분 관측성 하에서 작동한다.

본 연구는 네 방향 연결 이동(four-connected movement)을 사용하는 그리드 기반 설정을 중심으로 하며, 여기서 여러 에이전트는 동시에 개별 목표에 도달해야 한다. 이 문제는 다음의 제약 조건을 가진다:

• 동적 장애물: 장애물은 에이전트가 감지하기 전까지는 알 수 없는 결정론적 또는 무작위 스케줄(출현/소멸 시간)을 따른다.
• 우선순위 기반 계획(Prioritized Planning): 조합 최적화의 복잡성을 관리하기 위해, 시스템은 고정된 우선순위 순서에 따라 에이전트를 순차적으로 계획하고, 이전에 계획된 에이전트를 공유 예약 테이블(reservation table) 내의 움직이는 장애물로 취급하는 분리된 접근 방방식을 사용한다.
• 최적 결합 솔버(Optimal Coupled Solvers)의 제외: 빈번한 환경 변화와 부분 관측성이 존재하는 반응형 실시간 재계획 시나리오에서의 계산 불가능성 때문에, CBS(Conflict-Based Search)와 같은 알고리즘은 제외된다.

2. 방법론

저자들은 통일된 시뮬레이션 프레워크 내에서 6가지 대표적인 알고리즘을 평가하였다. 모든 알고리즘은 공정한 비교를 위해 동일한 지도, 장애물 스케줄, 에이전트 파라미터 및 예약 시스템을 공유한다.

2.1 평가된 알고리즘

1. Dijkstra: 베이스라인이 되는 정적 플래너이다. 휴리스틱 가이드나 시간 인지 없이 각 재계획 단계에서 전체 균등 비용 탐색을 수행하며, 예약을 정적 블록으로 취급한다.
2. D Lite:* 동적 환경을 위해 설계된 증분 휴리스틱 탐색이다. 전체를 처음부터 다시 계산하는 대신, 영향을 받는 그래프 부분에 대해서만 비용 수정을 전파하여 기존 경로를 복구한다.
3. Space-Time A (STA):** 상태 표현에 시간(위치 + 타임스텝)을 통합하여 A*를 확장하였으며, 이를 통해 예약 테이블을 이용한 충돌 회피를 가능하게 한다.
4. WHCA (Windowed Hierarchical Cooperative A):** 고정된 시간 창(예: 16단계) 내로 계획을 제한하고 웨이포인트를 향해 반복적으로 계획하는 협력 알고리즘이다.
5. M (M-Star):* 독립적으로 경로를 계획하다가 충돌이 감지될 때만 조인트 구성(joint configurations)으로 탐색 공간을 확장하는 다중 에이전트 알고리즘이다.
6. A (제안된 알고리즘):** 주요 기여로서 소개된 새로운 방법론이다.

2.2 제안된 A** 알고리즘

A**는 동적이고 부분 관측 가능한 설정에서의 반응형 계획을 위해 특별히 설계되었다. 이 알고리즘의 핵심 혁신은 템플릿 기반 접근 방식을 사용하여 오프라인 기하학적 경로 생성과 온라인 시간 적응을 분리하는 것이다:

• 템플로 생성 (오프라인/사전 계산): 초기화 시 또는 에이전트가 알고 있는 장애물 집합이 변경될 때, 알고리즘은 패널티가 부여된 2D A* 탐색을 사용하여 $k$개의 후보 경로(템플릿)를 생성한다.
  • 경로를 찾은 후, 해당 경로의 모든 셀에 고정된 패널티를 추가한다.
  • 이를 통해 후속 탐색이 기하학적으로 구별되는 경로를 찾도록 강제함으로써 다양한 후보 경로 집합을 생성한다.
  • 알려진 활성 동적 장애물에는 추가 패널티를 부여하여 템플릿이 위험 지역을 피하도록 유도한다.
• 온라인 재연결 (시간 적응): 재계획이 트리거될 때(예: 장애물이 현재 경로를 막을 때), A**는 전체 공간을 탐색하지 않는다. 대신, 저장된 템플릿 상의 접근 가능한 지점으로 에이전트의 현재 위치를 재연결하려고 시도한다.
  • 현재 위치에서 특정 템플릿 지점까지 Space-Time A*를 사용하여 "브리지(bridge)"를 계산한다.
  • 경로를 따라 예상되는 절대 시간과 "테일(tail, 템플릿의 나머지 부분)"을 검증하여 경로 상에 동적 장애물이 활성화되지 않는지 확인한다.
  • 총 경로 길이를 최소화하는 브리지와 테일의 조합을 선택한다.
• 폴백(Fallback): 기존의 모든 템플릿으로의 재연결에 실패할 경우, 현재 상태로부터 새로운 템플릿을 생성하고 이 과정을 반복한다.

3. 주요 기여

본 논문은 다섯 가지 구체적인 기여를 한다:

1. 정식화 및 프레임워크: 저자들은 시간 스케줄이 있는 동적 장애물과 에이전트별 시야 범위를 가진 그리드 상의 반응형, 부분 관측 문제를 D-MAPF로 정식화하였다. 또한 벤치마킹을 위해 이 설정을 구현할 시뮬레이션 프레임워크를 제공한다.
2. 알고리즘 통합: 6가지 다양한 알고리즘(Dijkstra, D* Lite, STA*, WHCA*, M*, A**)을 공통 프레임워크에 통합하여 체계적인 벤치마킹과 직접적인 성능 비교를 가능하게 하였다.
3. 비전 기반 장애물 필터: 핵심 탐색 로직을 수정하지 않고도 모든 플래너에 부분 관측성을 강제하는 투명한 필터를 도입하여, 에이전트가 관측된 장애물에만 반응하도록 보장한다.
4. 실증적 평가: 8개의 벤치마크 맵, 10개의 에이전트 수 구성(1~10명), 100회의 반복 실험을 통해 종합적인 평가를 수행하였다. 지표로는 비용 합계(SoC), Makespan, 실패율, 계산 시간이 포함된다.
5. A의 특성 규명:** 템플릿 기반 접근 방식이 동적 환경에서 솔루션 품질과 재계획 효율성 사이의 균형을 효과적으로 맞춘다는 것을 입증하며 A**를 소개하고 평가한다.

4. 실험 결과

실험은 동적 장애물이 무작위 간격으로 나타나고 사라지는 8개의 맵(빈 공간, 미로, 무작위, 방 구성 포함)에서 수행되었다.

• 솔루션 품질 (비용 합계 - SoC):

  • A는 에이전트 수가 1명에서 9명인 구간에서 일관되게 가장 낮은 SoC를 달성하였다.
  • 템플릿 메커니즘 덕분에 A**는 기하학적으로 구별되는 경로로 전환함으로써 일시적으로 차단된 영역을 우회할 수 있으며, 이는 비용이 많이 드는 온라인 우회 경로를 줄여준다.
  • 에이전트 10명의 경우, M이 A*보다 약간 더 낮은 SoC를 기록했으나 A 역시 경쟁력 있는 성능을 보였다.
  • Dijkstra는 시간 인지가 부족하여 에이전트가 대기하거나 더 긴 우회 경로를 택하게 함으로써 (1명 제외) 가장 높은 SoC를 나타냈다.

• 계산 효율성:

  • Dijkstra와 D Lite*는 단순함과 증분적 특성 덕분에 평균 총 계산 시간이 6ms 미만으로 가장 빨랐다.
  • A는 훨씬 높은 계산 시간(수백에서 수천 밀리초 범위)을 보였다. 이러한 오버헤드는 $k$개의 템플릿을 생성하는 과정($k$번의 패널티 부여된 2D A* 실행 필요)과 브리지를 평가하는 과정(여러 번의 STA* 탐색 필요)에서 발생한다.
  • 재계획 빈도: A*는 템플릿이 미래의 충돌을 예측하기 때문에 WHCA나 Dijkstra보다 재계획을 덜 자주 수행하지만, 재계획당 비용은 높다. 결과적으로 A**의 총 계산 시간은 모든 방법 중 가장 높았다.

• 강건성 (실패율):

  • STA와 WHCA는 계획 범위 내에서 솔루션을 찾을 가능성이 높은 시간 확장 탐색 덕분에 가장 낮은 실패율(11% 미만)을 보였다.
  • A는 더 높은 실패율(평균 21%)을 보였으며, 저자들은 이를 재계획 로직의 복잡성과 동적 환경의 특정 제약 때문으로 분석하였다.
  • D Lite와 M 역시 특히 에이전트 밀도가 높은 구성에서 높은 실패율(20%)을 보였다.

5. 의의 및 주장

본 논문은 A가 부분 관측성을 가진 D-MAPF를 처리하는 데 있어 중요한 진전을 이루었다고 주장한다. 기하학적 다양성 생성과 시간적 타당성 검증을 분리함으로써, A**는 빈번한 변화와 제한된 센싱이 있는 환경에서도 효과적으로 항해하며 대부분의 구성에서 우수한 솔루션 품질(최저 SoC)을 달성한다.

저자들은 트레이드오프를 인정한다. 즉, A는 더 높은 계산 오버헤드를 대가로 더 나은 경로를 얻는다. 그러나 이들은 솔루션 품질(총 이동 시간/비용 최소화)이 원시적인 재계획 속도보다 우선시되는 시나리오에서 템플릿 기반 접근 방식이 전통적인 증분형 또는 윈도우 기반 플래너에 대한 강력한 대안이 될 수 있다고 주장한다. 본 연구는 단일 알고리즘이 모든 지표에서 압도적이지는 않지만, A가 동적이고 부분 관측 가능한 다중 에이전트 시스템에서 비용 합계를 최소화하는 데 특히 효과적임을 결론짓는다.