Scalable Algorithms with Provable Optimality Bounds for the Multiple Watchman Route Problem

논문 개요: 다중 감시자 경로 문제 (MWRP) 를 위한 확장 가능하고 최적성 보장이 있는 알고리즘

이 논문은 **다중 감시자 경로 문제 (Multiple Watchman Route Problem, MWRP)**를 해결하기 위한 새로운 최적 탐색 알고리즘과 경계 하위 최적 (Bounded Suboptimal) 알고리즘들을 제안합니다. MWRP 는 $M$명의 감시자 (Watchman) 가 지도상의 모든 위치를 최소 한 명 이상 볼 수 있도록 경로 집합을 찾는 문제입니다. 특히, **최대 경로 길이 (Makespan)**를 최소화하는 목표에 초점을 맞추고 있습니다.

1. 문제 정의 (Problem Formulation)

• 목표: $M$명의 에이전트 (감시자) 가 시작점에서 출발하여 이동하며, 지도상의 모든 자유 셀 (Free Cell) 을 최소 한 번 이상 시야 (Line-of-Sight, LOS) 에 들어오게 하는 경로 집합 $\pi = \{\pi_1, ..., \pi_M\}$을 찾는 것입니다.
• 비용 함수: 각 에이전트의 경로 길이의 최댓값인 Makespan ($O(\pi) = \max_k c(\pi_k)$) 을 최소화하는 것을 목표로 합니다. (재난 구조, 화재 진압 등 시간 민감적 시나리오에 적합)
• 특징:
  • 그래프 기반 (2D 그리드) 환경에서 작동하며, 임의의 LOS 함수를 지원합니다.
  • 에이전트 간 충돌은 고려하지 않으며 (한 셀에 여러 에이전트 존재 가능), 사전에 알려진 맵 구조와 시작 위치를 가정합니다.
  • 기존 연구 (MWRP-A*) 는 작은 맵 (약 200 셀) 에서만 작동 가능했으나, 실제 적용을 위해 수천 개의 셀을 가진 맵을 처리할 수 있는 확장성이 필요했습니다.

2. 주요 방법론 및 기여 (Methodology & Contributions)

저자들은 세 가지 핵심 기여를 통해 문제의 확장성과 최적성을 달성했습니다.

A. 최적 탐색 알고리즘: MWRP-CP3
기존의 MWRP-A* 알고리즘을 기반으로 상태 공간을 대폭 축소하고 휴리스틱 계산 효율을 극대화한 알고리즘입니다.

1. 상태 공간 축소 (State Space Reduction):
   • 셀 지배 (Cell Dominance, CD): 한 셀을 보는 것이 다른 셀을 보는 것을 보장하는 경우 (시야 집합이 포함 관계일 때), 더 넓은 시야를 가진 셀만 고려하도록 불필요한 셀을 제거합니다.
   • 경로 지배 (Path Dominance, PD): 에이전트가 특정 셀을 보러 가는 경로상에서 다른 셀을 필연적으로 보게 되는 경우, 중간에 있는 셀을 제거합니다.
   • 효과: 복잡한 맵에서 탐색 공간 (State Space) 을 95% 이상 축소하며, 최적성 보장을 유지합니다.
2. 휴리스틱 개선 (Heuristic Enhancements):
   • 피벗 가지치기 (Pivot Pruning): mTSP (Multiple Traveling Salesman Problem) 휴리스틱 계산 시, 해답의 길이를 단축시키는 '단축 (Shortcut)' 역할을 하는 피벗 (Pivot) 을 제거하여 휴리스틱 값을 더 보수적이고 강력하게 만듭니다.
   • 병렬 휴리스틱 계산 (Parallel Heuristic Calculation): A* 확장 시, 다음에 확장될 노드들의 mTSP 휴리스틱 계산을 배치 (Batch) 로 병렬 처리하여 계산 시간을 단축합니다.

B. 경계 하위 최적 탐색 (Bounded Suboptimal Search, BSS)
대규모 맵과 에이전트 수에 대해 최적해를 보장하지는 않지만, 최적해 대비 일정 비율 ($w$) 이내의 해를 보장하는 알고리즘들을 제안합니다.

1. Minimax Weighted A (MxWA):**
   • Makespan 문제 (최댓값 최소화) 에 특화된 Weighted A* 변형입니다.
   • 각 에이전트의 가중치 적용된 비용 ($g_k + w \cdot h_k$) 중 최댓값을 노드의 $f$-값으로 사용하여, 전체 Makespan 을 최소화하는 방향으로 탐색을 유도합니다.
   • Anytime MxWA (AMxWA)**로 확장하여 초기 해를 찾은 후에도 더 나은 해를 계속 탐색합니다.
2. Focal Search (FS) 기반 알고리즘:
   • Focal Search 를 적용하여 OPEN 리스트 내의 하위 집합 (FOCAL) 에서 탐색합니다.
   • **SORC (Sum Of Remaining Costs)**와 **MORC (Max Of Remaining Costs)**라는 두 가지 새로운 휴리스틱을 제안하여 잔여 탐색 노력을 추정합니다.
   • **Anytime Focal Search (AFS)**를 통해 점진적인 해 개선을 지원합니다.

C. 후처리 프레임워크 (Postprocessing Framework)

• 기존에 찾은 하위 최적 해 (Suboptimal Solution) 의 품질을 빠르게 개선하는 방법입니다.
• 가장 긴 경로를 가진 에이전트 (최대 비용 에이전트) 를 식별하고, 다른 에이전트들이 이미 커버하는 영역을 제외한 **최소 책임 영역 (Minimum Responsibility)**만 해당 에이전트가 다시 탐색하도록 단일 에이전트 문제로 분해 (Decomposition) 하여 최적화합니다.

3. 실험 결과 (Experimental Results)

• 성능 향상 (MWRP-CP3):
  • 기존 최적 알고리즘 (MWRP-A*) 대비 200 배 이상 빠른 실행 속도를 달성했습니다.
  • 복잡한 맵에서 탐색 공간을 95% 이상 줄여, 기존에는 해결 불가능했던 대규모 맵 (수천 셀) 에서도 최적해를 찾을 수 있게 되었습니다.
• 확장성 (Scalability):
  • 제안된 하위 최적 알고리즘 (MxWA*, FS) 은 1,500 개 이상의 그리드 셀과 5 명 이상의 에이전트가 포함된 맵에서도 성공적으로 작동했습니다.
  • MxWA*는 에이전트 수가 증가할 때 Focal Search 기반 알고리즘보다 더 우수한 성능을 보였습니다.
• 후처리 효과:
  • 하위 최적 해에 후처리를 적용하면 실행 시간은 8% 만 증가하면서 해의 품질 (Cost) 이 크게 개선되어, MxWA*의 경우 거의 최적해에 근접하는 결과를 얻었습니다.
• Ablation Study:
  • 피벗 가지치기 (PP) 와 병렬 휴리스틱 계산 (PHC) 은 모두 실행 속도를 크게 향상시켰으며, 특히 에이전트 수가 많을 때 그 효과가 두드러졌습니다.

4. 의의 및 결론 (Significance)

이 연구는 다중 에이전트 감시자 경로 문제 (MWRP) 를 해결하는 데 있어 실용적인 확장성과 이론적 최적성을 동시에 달성한 획기적인 성과를 거두었습니다.

1. 실제 적용 가능성: 기존 알고리즘이 처리하지 못했던 대규모 맵과 다수 에이전트 시나리오를 처리할 수 있게 되어, 재난 구조, 화재 진압, 대규모 지역 정찰 등 실제 시간 민감적 임무에 직접 적용 가능한 솔루션을 제공합니다.
2. 알고리즘적 혁신: Makespan 목적 함수에 특화된 Weighted A* 변형 (MxWA*) 과 상태 공간 축소 기법 (CD, PD) 은 유사한 다중 에이전트 경로 계획 문제에 적용 가능한 새로운 패러다임을 제시합니다.
3. 유연한 접근: 최적 해가 필요한 경우 (MWRP-CP3), 빠른 하위 최적 해가 필요한 경우 (BSS), 그리고 기존 해를 개선해야 하는 경우 (Postprocessing) 에 맞춰 다양한 전략을 제공하여 다양한 제약 조건 하에서 유연하게 대응할 수 있습니다.

결론적으로, 이 논문은 복잡한 다중 에이전트 탐색 문제를 해결하기 위한 가장 빠르고 확장 가능한 최적 및 하위 최적 알고리즘 프레임워크를 제시하며, 관련 분야의 새로운 기준 (Baseline) 을 설정했습니다.