Autonomous Detection and Coverage of Unknown Target Areas by Multi-Agent Systems

1. 문제 정의 (Problem Statement)

기존의 다중 에이전트 커버리지 (Coverage) 알고리즘들은 대부분 커버해야 할 목표 영역의 위치, 모양, 크기 등에 대한 사전 정보 (Prior Knowledge) 를 전제로 합니다. 그러나 실제 응용 환경 (환경 모니터링, 협력 수송 등) 에서는 목표 영역이 불명확하거나, 여러 개의 분리된 영역이 존재하며, 에이전트들이 사전 지식을 가지고 있지 않은 경우가 많습니다.

• 기존 연구의 한계:
  • 단일 연속 영역에 초점을 맞춰, 여러 개의 불연속적 (disconnected) 이거나 공간적으로 산재된 목표 영역을 동시에 처리하는 능력이 부족함.
  • 휴리스틱 기반 방법 (인공 잠재장 등) 은 국소 최적해 (Local Minima) 에 빠질 위험이 있으며, 전역 최적성을 보장하지 못함.
• 본 연구의 목표: 사전 정보가 없는 미지의 환경에서 다중 에이전트 시스템이 목표 영역을 자율적으로 탐지하고, 협업하여 최적의 공간 분포를 이루며 전체 영역을 커버하는 새로운 제어 알고리즘 개발.

2. 제안된 방법론 (Methodology)

본 논문은 센서 기반 탐지, 동적 밀도 함수, 중심 보로노이 테셀레이션 (CVT), 그리고 제어 장벽 함수 (CBF) 를 통합한 하이브리드 제어 프레임워크를 제안합니다.

2.1. 동적 밀도 함수 (Dynamic Density Function)

에이전트들은 목표 영역을 발견할 때까지 무작위로 탐색하거나 분산된 상태를 유지하다가, 센서 범위 내에서 목표 영역을 감지하면 밀도 함수 $\phi(q, t)$ 를 동적으로 생성합니다.

• 수식: 가우시안 함수의 합으로 구성되며, 에이전트 $i$가 목표를 감지하면 해당 위치 $(\mu_{xi}, \mu_{yi})$ 를 중심으로 밀도 피크가 생성됩니다.
  $$\phi(q, t) = \phi_0 + \sum_{i=1}^{N} \rho_i(t) \frac{\omega_i}{2\pi\sigma_{xi}\sigma_{yi}} \exp\left(-\frac{1}{2}\left(\frac{(q_x-\mu_{xi})^2}{\sigma_{xi}^2} + \frac{(q_y-\mu_{yi})^2}{\sigma_{yi}^2}\right)\right)$$
• 동작 원리:
  • $\rho_i(t)=1$: 에이전트 $i$가 목표를 감지함 (밀도 피크 생성).
  • $\rho_i(t)=0$: 감지하지 못함.
  • 이 함수는 목표 영역의 실제 모양과 위치에 따라 에이전트들을 끌어당기는 '가상 힘' 역할을 하여, 기하학적 중심이 아닌 실제 감지된 영역의 형태에 맞춰 에이전트들을 분포시킵니다.

2.2. 중심 보로노이 테셀레이션 (Centroidal Voronoi Tessellation, CVT)

에이전트들의 위치를 최적화하기 위해 CVT 를 활용합니다.

• 목적 함수: 위치 비용 함수 $H(p, t)$ 를 최소화합니다.
  $$H(p, t) = \sum_{i=1}^{N} \int_{V_i} \|q - p_i\|^2 \phi(q, t) dq$$
  여기서 $V_i$는 에이전트 $i$의 보로노이 셀입니다.
• 최적 조건: 각 에이전트가 자신의 보로노이 셀의 중심 (Centroid) 에 위치할 때 비용이 최소화됩니다. 에이전트들은 이 중심점을 향해 이동함으로써 목표 영역에 균일하게 분포하게 됩니다.

2.3. 충돌 회피를 위한 제어 장벽 함수 (Control Barrier Functions, CBF)

안전한 커버리지를 위해 CBF 를 제어 입력에 통합합니다.

• 안전 집합: 에이전트 간 거리가 최소 안전 거리 $d_{min}$ 이상 유지되도록 제약합니다.
  $$h_{ij}(t) = \|p_i(t) - p_j(t)\|^2 - d_{min}^2 \ge 0$$
• 제어 입력: CVT 기반의 이상적인 제어 입력 ($u_{nom}$) 을 CBF 제약 조건 하에서 최적화하는 2 차 계획법 (Quadratic Program, QP) 을 풀어 실제 제어 입력 $u_i$를 결정합니다. 이를 통해 충돌을 방지하면서도 커버리지 목표를 달성합니다.

3. 주요 기여 (Key Contributions)

1. 미지 환경에서의 자율 탐지 및 커버리지: 목표 영역의 위치, 개수, 모양에 대한 사전 지식 없이도, 에이전트들이 센서 정보를 기반으로 목표를 발견하고 집단적으로 커버하는 알고리즘 제안.
2. 다중 불연속 영역 처리: 단일 영역뿐만 아니라 공간적으로 분리된 여러 개의 목표 영역을 동시에 처리하고, 영역의 크기에 비례하여 에이전트 수를 동적으로 할당하는 능력 (Size-aware distribution).
3. 안전성 보장: CVT 기반의 최적 분포와 CBF 기반의 충돌 회피를 통합하여, 효율성과 안전성을 동시에 확보하는 통합 제어 프레임워크 구축.
4. 중앙 집중식 아키텍처의 확장성 검증: 에이전트 수와 목표 영역 수를 증가시킨 시뮬레이션을 통해 알고리즘의 확장성과 강건성을 입증.

4. 시뮬레이션 결과 (Simulation Results)

Python 을 이용한 시뮬레이션을 통해 제안된 방법의 유효성을 검증했습니다.

• 시나리오 1 (2 개 목표 영역, 10 에이전트):
  • 초기에는 에이전트들이 균일하게 분산되어 탐색.
  • 일부 에이전트가 목표를 감지하면 밀도 함수가 생성되고, 다른 에이전트들이 유입됨.
  • 최종적으로 CVT 를 통해 두 목표 영역에 에이전트들이 균일하게 분포하고, CBF 로 인해 충돌 없이 안전 거리를 유지함.
• 시나리오 2 (3 개 목표 영역, 15 에이전트):
  • 3 개의 분리된 영역을 성공적으로 커버.
  • 에이전트들이 3 개의 그룹으로 자동 조직화되어 각 영역을 담당.
  • 최소 에이전트 간 거리가 안전 임계값을 지속적으로 상회함을 확인.
• 시나리오 3 (이질적인 크기 목표 영역, 15 에이전트):
  • 크기가 다른 3 개의 목표 영역에 대해, 큰 영역일수록 더 많은 에이전트가 할당됨 (밀도 함수의 중첩 효과).
  • 목표 영역의 기하학적 정보를 명시적으로 알지 못하더라도, 밀도 함수를 통해 작업 수요를 자동으로 반영하여 에이전트 수가 비례적으로 분배됨.

5. 의의 및 결론 (Significance and Conclusion)

• 의의: 본 연구는 실제 환경에서 발생할 수 있는 불확실성 (미지의 목표, 분리된 영역) 을 해결할 수 있는 강력한 다중 에이전트 제어 전략을 제시합니다. 특히, 휴리스틱 방법의 국소 최적해 문제와 모델 기반 방법의 사전 지식 의존성을 동시에 극복한 점이 특징입니다.
• 한계 및 향후 과제: 현재 알고리즘은 중앙 집중식 (Centralized) 제어에 의존하고 있어, 에이전트 수가 매우 많아지면 확장성 (Scalability) 이 제한될 수 있으며, 단일 에이전트의 고장이 전체 시스템 성능에 영향을 줄 수 있습니다. 향후 연구에서는 분산형 (Decentralized) 알고리즘으로의 전환 및 실제 물리 시스템 (협력 수송 등) 에의 적용을 목표로 하고 있습니다.

요약하자면, 이 논문은 센서 정보를 기반으로 동적으로 밀도 함수를 생성하고, 이를 CVT 와 CBF 와 결합하여 미지의 다중 목표 영역을 안전하고 효율적으로 커버하는 새로운 다중 에이전트 제어 알고리즘을 제안하고 시뮬레이션을 통해 그 유효성을 입증한 연구입니다.