BFS 및 K-Means 기반 결합 초기화를 이용한 다중 로봇 커버리지의 DARP 초기 위치 결정 및 수렴 효율 향상

Ⅰ. 서 론

MRS(Multi-Robot System)은 물류 및 제조 현장, 대형 인프라 점검, 재난 대응과 같은 다양한 응용 분야에서 작업 시간을 단축하고 시스템의 안정성과 강인성을 향상시킬 수 있는 중요한 기술로 인식되고 있다[1]. 동일한 작업 공간에서 여러 로봇이 동시에 이동하며 임무를 수행할 경우 단일 로봇 대비 높은 작업 처리 효율을 기대할 수 있지만, 이와 동시에 로봇 간 충돌과 교착, 병목 구간에서의 간섭, 그리고 작업 부하의 불균형과 같은 복합적인 문제가 수반된다. 따라서 MRPP(Multi-Robot Path Planning) 또는 MRCPP(Multi-Robot Coverage Path Planning)문제에서는 로봇 간 충돌을 방지하는 동시에 개별 로봇의 임무를 균등하게 조정하는 기법이 요구되며, 이러한 요소는 시스템 전반의 임무 수행 성능을 결정짓는 핵심 요인이라 할 수 있다[2][3].

이러한 요구를 만족하기 위한 대표적 접근으로, 작업 공간을 격자 형태로 모델링한 뒤 각 로봇에 담당 영역을 분할하여 커버리지를 수행하는 분할 기반 방식이 널리 사용되어 왔다[4]-[14]. 그중 DARP(Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning) 알고리즘[5]은 격자 환경에서 셀을 반복적으로 재할당하여 로봇 간 작업량을 균형화하면서도 각 로봇의 담당 영역이 연결성을 유지하도록 유도하는 방법으로 알려져 있다. DARP는 균등한 영역 분할과 연결성 유지를 동시에 지향하며, 분할 결과를 기반으로 각 로봇이 자신의 인접 영역을 중심으로 커버리지를 수행하게 함으로써 전체 커버리지 수행을 체계화할 수 있다. 그러나 실제 실내 환경과 같이 장애물이 많고 통로가 협소하며 구조가 불규칙한 경우, 로봇의 초기 위치가 분할 초기 단계의 불균형 및 연결성 문제를 유발하여 DARP의 수렴 반복을 증가시키고 실행 시간을 악화시킬 수 있다. 즉, 로봇의 초기 위치는 단순한 시작 조건이 아니라 DARP의 초기 분할 품질을 결정하는 핵심 요인이다. 초기 위치가 부적절할 경우 초기 분할 단계에서 (i) 작업량 불균형이 커지고 (ii) 담당 영역의 연결성이 약화되며, 이로 인해 연결성 보정이 반복적으로 발생하여 반복 횟수와 실행 시간이 급증할 수 있다. 본 논문에서는 설정한 종료 조건(최대 반복 횟수 𝐼max) 내에 수렴 조건을 만족하지 못하는 경우를 Failed로 정의한다(Ⅴ장). 또한 초기 분할의 품질 저하는 로봇 간 경로 중첩/교차 가능성을 증가시켜 운영 안정성 측면에서도 불리하게 작용할 수 있으며, 결과적으로 DARP의 재할당 반복을 증가시켜 수렴 속도와 계산 효율을 악화시키고 임무 완료 시간과 같은 최종 커버리지 성능에도 부정적 영향을 미친다. 기존 연구는 DARP의 성능 향상을 위해 가중치/비용 모델을 도입하여 분할 목적을 확장하거나[6], A* 알고리즘 도입을 통한 향상[7] 또는 3D환경에서의 해석을 위한 방식 등을 제안해 왔으나[8], 실제 환경에서 반복 횟수와 수렴 안정성을 좌우하는 초기 조건의 체계적 설계는 상대적으로 덜 다루어진 경향이 있다.

본 논문은 이러한 문제의식을 바탕으로, BFS(Breadth-First Search)와 K-Means 군집화를 결합하여 DARP의 초기 조건을 개선하는 새로운 초기 위치 결정 방법을 제안한다. 본 논문의 중요한 핵심은 다음과 같다.

(1) DARP의 초기 위치 민감도를 정량적으로 분석하고, 초기화 문제를 수렴 효율에 직접 영향을 미치는 핵심 요소로 정의/분석하였다.

(2) BFS와 K-Means를 결합한 선택적 초기화 절차를 제안하여 초기 분할의 연결성과 공간적 균형성을 개선하고, 불리한 초기 조건에서 발생하는 과도한 재할당 부담을 완화하였다.

(3) 실험을 통해 제안 방법이 반복 횟수를 복잡 환경에서 최대 약 75%, 일반 환경에서 최대 약 60%까지 감소시켜 수렴 효율과 안정성을 향상시킴을 확인하였다.

논문의 구성은 다음과 같다. Ⅱ장에서는 관련 연구를 정리한다. Ⅲ장에서는 초기 1회 분할에서 계산되는 불균형율을 정의하고 이를 기반으로 DARP는 반복수, 수행 시간의 수렴성 예측 모델을 제시한다. Ⅳ장에서는 BFS–K-Means 결합 초기화와 임계값 기반 재초기화 로직을 포함한 제안 파이프라인을 설명한다. Ⅴ장에서는 시뮬레이션 환경과 실험 조건 및 평가 지표를, Ⅵ장에서는 결과 분석을 제시한다. 마지막으로 Ⅶ장에서는 결론 및 향후 연구를 논의한다.

II. 관련 연구

MRCPP[3]는 일반적으로 작업 공간을 각 로봇의 담당 구역으로 분할한 뒤, 각 구역 내부에서 완전 커버 경로를 생성하는 방식으로 수행된다. 이때 전체 성능은 단순히 각 로봇의 지역 경로 생성 성능만으로 결정되지 않으며, 초기 분할이 얼마나 균형 있고 안정적으로 형성되는지에 크게 좌우된다[5]. 특히 DARP와 같이 반복적 재할당을 통해 균형성과 연결성을 동시에 만족시키는 분할 기반 알고리즘에서는, 초기 배치 이후 경계 수정의 규모, 반복 횟수, 계산 시간, 나아가 비수렴 가능성에까지 직접적인 영향을 미친다. 따라서 본 연구의 대상인 초기 배치 설계는 단순한 전처리 요소가 아니라, 분할 기반 MRCPP의 수렴 안정성과 실행 효율을 좌우하는 핵심 설계 변수로 볼 수 있다.

MRCPP에서 초기 배치 관점의 가장 직관적인 접근은 로봇의 초기 위치 또는 시드를 기준으로 거리 기반 분할을 수행하는 방식이며, Voronoi 계열 방법은 이러한 초기화의 대표적인 기준선으로 널리 활용되어 왔다[9]. Voronoi 기반 초기화는 거리 중심의 빠른 공간 분산에는 유리하지만, 병목 및 협소 통로가 많은 환경의 연결 구조를 직접 반영하지 않으며, 작업량 균형 또한 초기 시드의 배치와 공간 형상에 크게 좌우된다. 기존 영역 분할의 시작 위치 민감성을 완화하기 위해, N. Baras et al.[10]은 Affinity Propagation 기반의 영역 분할 기법을 제안하였다. 그러나 이러한 접근은 초기 영역 분할 자체를 개선하는 데 초점을 두며, 격자 기반 환경에서 균형성과 연결성을 반복적으로 보정하는 구조와는 차이가 있다. 이를 대표적으로 다루는 방법이 DARP이다. DARP는 격자 환경을 로봇 수만큼 분할하되, 각 로봇에 할당되는 셀 수를 균등하게 맞추면서 연결된 구역을 형성하도록 반복적으로 셀을 재할당하는 대표적 분할 기반 MRCPP 알고리즘이다. DARP는 비교적 단순한 구조 안에서 초기 배치와 균형성을 동시에 다룰 수 있다는 장점이 있으나, 초기 조건에 민감하다는 한계를 가진다. 특히 장애물이 많고 병목이 빈번한 환경에서는 균형 회복을 위한 반복 재할당이 증가하여 수렴 속도와 실행 효율이 저하될 수 있다[5]. DARP의 후속 연구들은 주로 분할 규칙과 후속 경로 생성 절차를 개선하는 방향으로 확장되어 왔다. 예를 들어, weighted DARP는 가중 비용을 반영하여 불균일한 커버리지를 다룰 수 있도록 하였다[6]. N. Baras et al.[7]은 2D뿐 아니라 3D 환경에서도 적용 가능한 다중 로봇 커버리지 경로 계획 기법을 제안하고, 로봇의 속도와 유형 차이를 반영한 경로 생성을 수행하였다. 또한, Y. Huang et al.[8]은 개선된 DARP에 A*와 STC를 결합하여 영역 할당 이후의 커버리지 효율성을 향상시키고자 하였다. H. Lee et al.[11]은 비격자 road-network 환경에서 graph-adapted K-means와 bipartite matching을 이용하여 초기 위치를 반영한 MRCPP 기법을 제안하였다. 최근 Y. Wang et al.[14]의 IB-DARP는 방향성을 고려한 분할과 반복적 경매 기반 균형 조정을 도입하여, 기존 DARP에서 문제로 지적되던 작업 불균형과 경로 충돌을 완화하고 전역적 부하 균형과 계획 효율을 향상시켰다. 그러나 이러한 연구들은 주로 목적 함수, 재할당 규칙, 또는 특정 응용 환경에서의 임무 할당과 경로 계획의 통합에 초점을 두고 있다. 따라서, 초기 배치 자체가 DARP의 수렴 특성이나 반복 재할당 부담에 미치는 영향을 직접적으로 분석하는 관점은 상대적으로 부족하다.

정리하면, 기존 연구는 Voronoi 계열 초기화의 빠른 공간 분산, DARP 계열의 반복적 균형화, 그리고 다양한 확장 연구의 목적 함수 및 응용 환경 적응에 중점을 두어 왔다. 반면, 표 1에서 확인할 수 있듯이 복잡한 격자 환경에서 DARP의 초기화 단계 자체를 구조적으로 설계하고 그 영향을 분석한 연구는 상대적으로 제한적이다. 이에 본 연구는 BFS 기반 연결성 반영 후보 영역 구성과 K-Means 기반 초기 중심 재정렬을 결합하여, 초기 분할 품질을 향상시키는 선택적 초기화 절차를 제안한다.

Table 1.

Comparison of Representative Methods in MRCPP

III. 제안 모델: 초기 분할 불균형율 기반 DARP 수렴 예측

작업공간 분할에 기반한 MRCPP 문제에서 영역 분할의 우수성은 전체 임무 완료 시간과 로봇의 에너지 소모에 직접적인 영향을 미치는 핵심적인 요인이다. 분할 기반 알고리즘은 다수 로봇에 할당되는 영역의 균형성과 연결성을 동시에 충족해야 하며, 초기 분할이 불안정할 경우 재할당 과정이 반복적으로 발생하여 계산 비용이 급격히 증가할 수 있다. 격자 환경에서 영역의 균등 분할과 연결성 유지를 동시에 달성하기 위한 대표적인 알고리즘으로 DARP가 널리 사용되고 있다. 그러나 DARP는 초기 로봇 위치 설정에 민감하다는 한계를 가지며, 초기 불균형이 크게 발생할 경우 수렴 속도가 저하되고 전체 수행 시간이 증가하는 문제가 초래된다.

본 연구는 DARP의 성능 저하가 초기 영역 분할 단계에서의 불균형율 증가로부터 주로 발생한다고 가정하고, 초기 불균형율을 사전에 정량 평가하여 DARP 적용 방식을 선택할 수 있는 예측 모델을 제안한다. 제안 모델은 DARP를 전체 반복 수행하기 전에 1회(초기 1-iteration)만 실행하여 얻은 초기 분할 결과로부터 불균형율 α를 계산하고, 이를 통해 이후 총 반복 횟수 β 및 실행 시간 𝑇의 급증 가능성을 예측한다. 예측 결과를 바탕으로 α가 임계값 α_th를 초과하는 경우에만 BFS–K-Means 결합 초기화를 적용하여 α를 낮춘 뒤 DARP를 수행한다. 이를 통해 불필요한 전처리 비용을 줄이면서도 비효율적인 초기 조건을 효과적으로 배제할 수 있다.

초기 분할의 균형 정도를 수치화하기 위해 Jain’s Fairness Index[15]를 사용한다. 로봇 𝑖가 담당하는 셀 수를 x_i, 전체 로봇 수를 𝑛이라 할 때 공정성 지수 J는 다음과 같이 정의된다.

식 (1)은 J가 1에 가까울수록 로봇 간 작업량(셀 수) 분배가 균등함을 의미한다. 본 연구에서는 공정성 지수를 기반으로 정규화된 불균형율 α를 다음과 같이 정의한다.

식 (2)는 α는 0에 가까울수록 균형 분할이며 값이 커질수록 초기 분할이 불균형함을 의미한다. 특히 α는 DARP 전체 수행 이전, 즉 초기 분할 직후(초기 1-iteration 이후)에 계산 가능한 지표이므로, α를 통해 DARP 단독 적용의 효율성을 사전에 예측할 수 있다.

3.1 초기 분할 불균형의 관찰

그림 1은 동일한 지도 환경에서 6대 로봇의 초기 위치를 달리하여 DARP를 1회 수행했을 때의 초기 분할 결과 예시를 보여준다. 그림 1(c)와 같이 초기 위치가 유리한 경우 로봇별 담당 영역이 비교적 균등하고 연결된 형태로 형성되지만, 초기 위치가 불리한 경우 특정 로봇에 과도한 셀이 할당되거나 일부 로봇의 영역이 단절되는 현상이 나타난다. 특히, 이러한 현상은 그림 1(a), 그림 1(b), 그림 1(d)에서 확인할 수 있으며, 이로 인해 DARP의 연결성 회복을 위한 반복적 보정이 증가할 수 있다.

Fig. 1.

Visual comparison of the initial DARP execution and imbalance rates under different initial robot placements. The region assignments of six robots are illustrated using different colors

본 테스트에서는 총 4,520개의 셀로 구성된 격자 공간을 6대 로봇(R1,...,R6)이 각자 동시에 분할하는 환경을 가정하였으며, 이상적 균등 분할 셀 수는 약 753개이며 전체 4520개를 6개 로봇이 균등하게 나눈 영역을 의미한다. 그러나 표 1의 결과에서 확인되듯이 초기 위치가 무작위로 설정된 경우, 로봇별 할당 셀 수는 큰 편차를 보였고, 일부 로봇이 1,500개 이상의 셀을 담당하는 반면 다른 로봇은 200개 수준만 담당하는 경우도 관측되었다. 이러한 초기 분할 편차는 작업 부하 불균형을 유발할 뿐 아니라, 연결성과 균형성을 동시에 만족시키기 위한 경계 재조정(cell re-assignment)을 반복적으로 요구하여 DARP의 반복 횟수와 실행 시간을 증가시키는 원인으로 작용한다. 표 1의 시나리오 3과 나머지 시나리오의 비교 결과는 이를 뒷받침한다.

Table 1.

Analysis results of imbalance rates according to initial robot positions

3.2 불균형율–반복수 관계 및 임계값

그림 2와 표 2는 그림 1과 같은 환경에서 초기 불균형율 α와 DARP 반복수 간의 관계를 정량적으로 분석한 결과이다. 실험 결과, α가 임계값 α_th보다 작은 경우에는 빠르게 수렴하는 반면, 이를 초과하면 반복수가 급격히 증가하는 경향이 관측되었다. 해당 테스트에서 임계값 α_th는 초기 불균형율–반복수 관계에서 관찰된 전이점을 바탕으로 경험적으로 0.21로 설정되었다. 이는 α_th가 DARP의 효율적 수렴 구간과 반복 횟수가 급증하는 비효율 구간을 구분하는 기준으로 작용할 수 있음을 의미한다.

Fig. 2.

Relationship between imbalance rate and the number of iterations, and the necessity of a threshold

Table 2.

Imbalance rate and total number of iterations according to initial robot positions in DARP

이 경향을 반영하여, 반복수 β를 α의 함수로 근사한 예측식을 다음과 같이 정의한다.

$\[ \widehat{\beta }\left(\alpha \right)=\left\{\begin{array}{ccc}{c}_0+c_1\alpha ,\hfill & \hfill & \alpha \le {\alpha }_{th}\hfill \\ c_2\text{exp}\left(c_3\left(\alpha -{\alpha }_{th}\right)\right)+c_4,\hfill & \hfill & \alpha >{\alpha }_{th}\hfill \end{array}\right. \]$

(3)

식 (3)의 회귀 계수 c₀∼c₄는 표 2의 실험 데이터를 이용한 최소자승 회귀를 통해 추정하였으며, 각각 –26850, 6333, 2.88, 2.88×10-23, 114.79, 3717.70으로 나타났다. 본 piecewise 모델의 결정계수는 R² = 0.56이는 초기 불균형율이 반복 횟수 증가 경향을 부분적으로 설명함을 의미한다.

Ⅳ. 제안 방법: BFS+K-Means 결합 초기화 및 전체 파이프라인

본 장에서는 Ⅲ장에서 제안한 불균형율 기반 선택 전략을 실제 알고리즘으로 구현하기 위해, BFS와 K-Means를 결합한 초기화 절차를 제안한다. 제안 방법의 목적은 (i) 초기 위치가 한 구역에 몰려 발생하는 공간적 불균형을 완화하고, (ii) 복잡 지형(병목, 협소 통로)에서 초기 영역이 단절되지 않도록 연결성을 반영한 초기 후보 영역을 구성한 뒤, (iii) DARP를 안정적으로 수렴시키는 것이다.

4.1 제안 방법 개요

제안 파이프라인은 초기 1회 DARP 수행 후 계산되는 불균형율이 임계값 α_th를 초과하는 경우에만 활성화되며, 그림 3과 같이 (i) BFS 기반 연결성 반영 후보 영역 구성, (ii) K-Means 기반 초기 배치 재정렬, (iii) DARP 수행 및 불균형율 재평가의 단계로 구성된다. 먼저, BFS는 점유격자 지도에서 자유공간의 연결 구조를 반영하여 로봇 수 𝑛에 맞는 후보 영역을 구성한다. 이후 K-Means는 각 후보 영역의 중심점을 계산하여 로봇의 초기 중심을 재배치함으로써 공간적으로 보다 균등한 분포를 유도한다. 마지막으로 DARP는 재설정된 초기 배치를 입력으로 수행되며, 이때 계산된 불균형율이 임계값 α_th를 초과하지 않으면 추가적인 재초기화 없이 최대 반복 횟수 (𝐼max=10,000) 내에서 작업 공간을 균형 있게 분할하고, 각 로봇의 커버리지 경로 생성에 필요한 담당 영역을 도출한다. 본 연구에서는 이러한 재초기화 과정을 최대 2회까지 수행하도록 설정하였다. 결과적으로 본 파이프라인은 무작위 초기 배치에서 발생하는 불균형을 완화하여 DARP의 수렴 속도를 향상시키기 위한 선택적 초기화 절차로 사용된다.

Fig. 3.

Structure of the BFS+K-Means hybrid initialization (Input–output perspective)

4.2 BFS 기반 전처리

그림 4는 본 연구에서 제안한 방법의 실제 수행 과정의 예시를 보여준다. 먼저, 그림 4(a)와 같이 각 로봇의 초기 위치가 주어진 상황을 가정한다. 주어진 초기 위치를 기준으로 그림 4(b)와 같이 BFS가 수행된다. 본 연구에서 BFS는 최단 경로 계산 목적이 아니라, 점유격자 지도에서 자유공간의 연결 구조를 반영하여 로봇 수 𝑛에 맞는 클러스터를 초기 후보 영역으로 구성하기 위한 전처리로 사용된다. 구체적으로, 지도 내 자유공간을 BFS가 가능한 인접 셀 연결 그래프로 간주하고, 병목/협소 통로를 포함한 환경에서도 단절 영역이 최소화되도록 초기 영역을 확장하며 후보 구역을 형성한다.

Fig. 4.

Example of the BFS + K-Means hybrid initialization method based DARP

4.4 불균형율 기반 재초기화 루프

본 연구에서 제안하는 초기화 전략은 결합 초기화를 항상 수행하는 방식이 아니라, 3장에서 정의한 초기 분할 불균형율 α를 이용해 결합 여부를 선택적으로 결정하는 구조를 따른다. 그림 5는 이 의사결정 과정을 포함한 전체 파이프 라인을 나타낸다. 핵심 아이디어는 DARP의 수렴 성능이 초기 조건에 민감하다는 점을 이용하여, 초기 1회 분할에서 관측되는 불균형율 α를 사전 진단 지표로 사용하고, 초기 조건이 불균형하다고 판단되는 경우에만 재초기화를 수행함으로써 불필요한 전처리 비용을 줄이는 데 있다. 사용자는 점유격자 지도 𝑀과 로봇 수 𝑛을 입력으로 제공한다. 초기 로봇 위치 𝑃(0)는 사용자 지정 또는 무작위 배치로 설정될 수 있다. 이후 DARP를 완전 수렴시키기 전에 초기 조건의 유불리를 판단하기 위해 DARP를 1회만 수행한다. 이때 얻어지는 1회 분할 결과 𝑋(0)는 로봇별 할당 셀 수를 포함하며, 본 연구는 이를 통해 식 (1)의 공정성 지수 𝐽(0)를 계산하고 식 (2)의 불균형율 α(0)를 산출한다. 산출된 α(0)는 임계값 α_th와 비교된다. 여기서 사용되는 임계값 α_th는 대상 환경의 구조적 특성과 로봇 수에 따라 조정될 수 있는 운용 파라미터이다. 따라서 실제 시스템 적용 시에는 대표 지도 및 초기 배치 조건에 대한 사전 실험을 통해 α분포와 반복 횟수의 증가 양상을 확인하고, 이를 바탕으로 α_th를 재설정하는 방식이 가장 적절하다. 만약 α(0) ≤ α_th이면 초기 분할이 충분히 균형적이라고 판단하여 추가 초기화 과정 없이 표준 DARP를 반복 수행해 수렴시킨다.

Fig. 5.

Overall proposed pipeline

반대로 α(0) > α_th이면 초기 분할이 불균형하여 이후 반복 과정에서 경계 재조정과 연결성 회복이 과도하게 발생할 가능성이 높다고 판단하고, 재초기화 단계로 전환한다. 재초기화 단계에서는 먼저 BFS 기반 전처리를 통해 자유공간의 연결 구조를 반영한 셀 후보 집합을 구성하여 단절되거나 병목으로 분리된 영역을 사전에 배제한다. 이후 해당 후보 셀 집합에 대해 K-Means를 적용하여 공간적으로 균형 잡힌 중심점을 산출하고, 이를 새로운 초기 로봇 위치 𝑃(1)으로 설정한다. 이후 동일하게 DARP를 1회 수행하여 𝑋(1)을 얻고 불균형율 α(1)를 재계산한다. 만약 α(1) ≤ α_th이면 해당 초기 위치를 확정한 뒤 DARP를 수렴까지 수행한다. 반대로 α(1) > α_th이면 다음 재초기화 반복으로 진행한다. 이러한 재초기화는 최대 𝐿회까지만 허용되며, 𝐿회 이후에도 임계값을 만족하지 못하는 경우에는 마지막으로 생성된 초기 위치를 사용하여 DARP를 수행한다. 이는 무한 루프를 방지하면서도 최악의 초기 조건에서 반복 횟수 폭증을 완화하기 위한 제한 장치이다. 정리하면, 제안 구조는 전처리를 항상 수행하는 방식에 비해 평균 계산 부담을 낮추면서도, 불리한 초기 조건에서 발생하는 비효율을 줄일 수 있다.

Ⅴ. 시뮬레이션

본 연구는 제안한 방법이 DARP의 수렴 특성과 실행 효율을 어떻게 개선하는지 정량적으로 검증하기 위해 다양한 시뮬레이션 환경을 구성하였다. 시뮬레이션은 (i) 단순 환경에서의 기본 특성 확인과 (ii) 실제 환경 기반 복잡 지형에서의 일반화 성능 검증을 모두 포함하도록 설계하였다. DARP의 최대 반복 횟수 𝐼_max 와 재초기화 반복 횟수 𝐿는 실험적으로 각각 10,000회와 2회로 설정하였다.

5.1 시뮬레이션 지도 환경

그림 6은 본 연구에서 사용한 대표적인 지도 환경과 각 환경에서의 DARP 수행 결과를 보여준다. 그림 6(a)의 사각형 일반 지형은 장애물이 거의 없고 구조가 단순한 환경으로, 이상적인 조건에서 DARP의 균등 분할 특성과 수렴 거동을 관찰하기 위한 기준 환경으로 사용된다. 이에 대한 DARP 수행 결과는 그림 6(b)에 제시되어 있다. 반면, 그림 6(c)의 인천공항 여객터미널 기반 복잡 지형은 복도, 교차로, 병목 구간이 복잡하게 연결된 구조를 가지므로, 초기 위치에 따른 분할 불균형과 연결성 문제를 유도하기에 적합하다. 해당 환경에서의 DARP 수행 결과는 그림 6(d)에 나타나 있다. 따라서 본 연구에서는 그림 6(a)와 같은 일반 환경과 그림 6(c)와 같은 복잡 환경을 활용하여 초기 조건에 따른 DARP의 수렴 특성과 제안한 방법의 성능을 분석한다.

Fig. 6.

DARP Results in various map environments

5.2 실험 시나리오의 비교 알고리즘 및 평가 지표

DARP 알고리즘의 수렴 성능이 로봇의 초기 위치 분포에 의해 크게 좌우된다는 가설에 기반하여, 초기 배치가 총 반복 횟수 β 및 실행 시간 𝑇에 미치는 영향을 정량적으로 분석하였다. 분석에서는 그림 7과 같이 초기 위치가 유도하는 대표적 상황을 고려하였다. 로봇이 병목 구간 또는 좁은 통로 인근에 배치되는 경우(그림 7(a))에는 초기 분할 단계에서 연결성 제약이 강화되어 경계 재조정이 빈번해질 수 있다(반복횟수 증가). 또한 로봇들이 입구 근처에 서로 밀집한 상태로 시작하는 경우(그림 7(b))에는 초기 중심이 한 영역에 편향되어 특정 로봇에 셀이 과도하게 할당될 가능성이 높다. 반면 자유공간에 충분히 분산된 원거리 분포(Far distribution, 그림 7(c))에서는 초기 분할이 상대적으로 안정적으로 형성된다. 반대로 특정 구역에 로봇이 밀집된 근거리 분포(Near distribution, 그림 7(d))에서는 초기 불균형이 크게 발생하여 수렴 속도가 저하되거나, 경우에 따라 수렴 실패 가능성이 증가한다.

Fig. 7.

Results of DARP execution under different initial robot position settings

실험은 사각형 표준 지도 환경에서 로봇 수 𝑛을 1대부터 10대까지 단계적으로 증가시키며, 원거리 분포와 근거리 분포의 두 조건에서 DARP의 수렴 특성을 비교하는 방식으로 수행하였다. 또한 초기 분할 상태가 이후 수렴 성능을 얼마나 설명하는지를 확인하기 위해, DARP를 1회 수행한 직후 로봇별 할당 셀 수로부터 공정성 지수 𝐽와 불균형율 α을 계산하였다. 이후 α와 β, 𝑇 간의 상관관계를 함께 분석하였다.

비교 알고리즘은 다음 세 가지로 구성하였다.

(1) Baseline 1 (Random + DARP): 무작위 초기 위치를 사용한 DARP 단독 적용으로, 초기 조건의 영향을 가장 직접적으로 관찰하기 위한 기준선이다.

(2) Baseline 2 (K-Means + DARP): K-Means로 초기 중심을 분산시켜 공간적 균형을 유도함으로써 초기 분할 불균형 완화 효과를 평가한다.

(3) Proposed (BFS + K-Means + DARP): K-Means 기반 공간적 균형에 더해, BFS 기반 전처리로 자유공간의 연결 구조를 반영하여 병목/협소 구간에서 초기 단절 가능성을 낮추도록 설계하였다.

VI. 결과 분석

본 장에서는 DARP의 다양한 특성과 제안한 방법의 성능을 분석하는 과정으로, 각 조건별로 10회 독립적으로 반복 수행한 평균값을 기준으로 정리하였다. 각 반복에서는 주어진 조건은 유지하되, 초기 위치의 세부 좌표를 무작위로 변화시켜 실험을 수행하였다.

6.1 초기 분포에 따른 DARP 수렴 특성

표 3은 사각형 일반 지도 환경에서 로봇 수 𝑛(1–10대)와 초기 위치 분포 조건에 따른 DARP의 총 반복 횟수 𝐾 및 실행 시간 𝑇를 정리한 결과이다. 본 표의 목적은 그림 7(c)의 원거리 분포에서 로봇 수 증가에 따른 기본 수렴 특성을 확인하고, 해당 성능을 기준선으로 제시하는 데 있다. 원거리 분포에서는 초기 분할 불균형율이 0∼0.17로 매우 낮게 유지되었다. 이 조건에서는 각 로봇의 담당 영역이 초기부터 비교적 분리되어 형성되므로, DARP는 반복 횟수가 비교적 적은 상태에서 수렴한다. 로봇 수가 증가함에 따라 총 반복 횟수는 2대일 때 11회에서 10대일 때 832회로 증가하고, 실행 시간 𝑇 역시 약 24초에서 37초 범위로 증가하였으나, 전체적인 증가 양상은 비교적 완만하게 나타났다.

Table 3.

Performance under far-apart robot distribution with varying number of robots

반면 표 4의 근거리 분포에서는 초기 불균형율 α가 급격히 증가하는 경우가 관측되었다. 이 조건에서는 초기 중심이 한 구역에 몰리면서 일부 로봇에 과도한 셀이 할당되고 연결성 보정이 반복되며 수렴이 크게 지연된다. 실제로 반복수는 3대 225회에서 8대 4,237회로 폭발적으로 증가하였고, 9대 이상에서는 초기 분할 불균형 및 반복적 재할당이 증가하여, 설정한 종료 조건 내에 수렴하지 못하는 사례(Failed)가 발생하였다. 실행 시간 또한 비선형적으로 증가하여 6대의 동일한 로봇 수에서 원거리 분포 27.8초 대비 근거리 분포의 48초로 실행 시간이 크게 증가하였다. 특히 α가 0.7 수준에 도달하는 구간부터 실행 시간이 90초를 초과하는 사례가 발생하여 계산 부담이 급격히 증가함을 확인하였다.

Table 4.

Performance under close-togeter distribution with varying number of robots

이 결과는 DARP의 연산 구조상 초기 불균형이 클수록 영역 경계의 안정성이 저하되고, 연결성을 유지하기 위한 재할당 과정이 반복적으로 발생하여, 그에 따라 반복 횟수와 전체 실행 시간이 급격히 증가할 수 있음을 의미한다. 따라서 실제 환경에서 DARP를 적용하기 위해서는 로봇 수의 설정뿐만 아니라, 초기 배치 단계에서 영역 간 불균형 수준을 최소화하는 설계 전략이 필수적으로 요구된다.

6.2 불균형율 임계값 기반 선택 전략의 필요성

표 5의 시나리오 1~5는 그림 7(a)와 그림 7(b)에서와 같이 병목 구간 및 입구 인접 배치가 포함된 조건에서의 실험 결과를 나타낸다.

Table 5.

Imbalance rates after the initial DARP execution across various scenarios

특히 좁은 통로 인근에 로봇이 배치되는 경우, DARP 1회 수행 직후 계산되는 초기 불균형율 α(0)가 임계값 α_th를 초과하면 반복 횟수와 실행 시간이 크게 증가하는 경향이 나타났다. 또한 표 5의 시나리오 6~10은 그림 7(c)와 그림 7(d)에서와 같이 로봇 간 초기 거리의 분산 정도를 반영한 결과로, 환경 구조적 요인뿐만 아니라 초기 위치 분포 자체가 α(0)를 증가시키고, 그 결과 𝐾와 𝑇의 악화를 유발할 수 있음을 확인하였다. 즉, α는 사후 결과가 아니라 사전 판단 지표로서 의미가 있으며, α를 기준으로 결합 초기화 적용 여부를 선택하는 전략(3장 및 4장)이 타당함을 뒷받침한다. 다만, 본 연구에서 사용한 임계값 α_th=0.21은 실험 환경에서 관찰된 전이 구간을 기준으로 설정한 경험적 값이므로, 모든 운용 조건에서 동일하게 최적임을 보장하지는 않는다. 따라서 실제 적용에서는 대표 환경에 대한 사전 시험을 통해 α와 반복수 관계를 확인하고, 그 전이 지점을 기준으로 임계값을 재보정하는 것이 바람직하다.

6.3 DARP 초기화 성능 비교

본 절에서는 복잡한 환경과 일반 환경에서 6~8대의 로봇을 이용한 4가지 시나리오에서 서로 다른 방식에 따른 성능 차이를 비교 및 분석한다. 먼저 복잡 환경에서의 초기 위치를 고려하지 않은 DARP(Standalone)와 K-Means 초기화, 그리고 BFS+K-Means 결합 초기화의 성능을 표 6~8에 제시하였다.

Table 6.

DARP performance in a complex environment

Table 7.

K-Means-Based initialization method

Table 8.

BFS + K-Means hybrid method in a complex environment

표 6에서 기본 DARP 방식은 모든 시나리오에서 최종 불균형율 0.00에 도달하였으나, 평균 반복 횟수는 약 2,838.5회, 평균 실행 시간은 약 33.28초로 비교적 크게 나타났다. 반면 표 7의 K-Means 초기화 방식은 평균 반복 횟수를 1,452.0회로 줄여 기본 DARP 대비 약 48.8% 감소 효과를 보였으며, 평균 실행 시간도 21.04초로 약 36.8% 단축되었다. 이는 초기 중심점 재배치를 통해 로봇 간 초기 편중을 완화함으로써 DARP의 반복적 재조정 부담이 줄어든 결과이다. 표 8의 BFS+K-Means 결합 초기화 방식은 평균 반복 횟수 709.75회, 평균 실행 시간 18.07초를 기록하여, 세 방법 중 가장 우수한 성능을 보였다. 이는 기본 DARP 대비 반복 횟수를 약 75.0%, 실행 시간을 약 45.7% 줄인 결과이며, 표 7의 K-Means 단독 초기화와 비교하더라도 평균 반복 횟수는 약 51.1%, 실행 시간은 약 14.1% 추가로 감소하였다. 이러한 결과는 BFS 전처리가 복잡 지형의 자유공간 연결 구조를 반영하여 초기 후보 영역을 보다 안정적으로 형성하고, 이후 K-Means가 초기 중심을 재정렬함으로써 초기 단절 가능성과 경계 보정 부담을 함께 완화하기 때문이다.

복잡한 환경 조건에서 서로 다른 초기화 방법에 따른 반복 횟수 결과(표 6~8)를 그림 8의 boxplot으로 정리하였다. 기존 DARP는 반복 횟수의 중앙값이 상대적으로 높고, 사분위 범위와 전체 분산 또한 크게 나타나 초기 조건에 따른 민감도가 큰 것으로 확인된다. K-Means 기반 초기화는 반복 횟수를 일정 수준 감소시키는 경향을 보이나, 여전히 분포의 변동 폭이 남아 있다. 반면, BFS와 K-Means를 결합한 제안 방법은 반복 횟수의 중앙값을 크게 낮추고 분포의 폭 또한 줄이는 경향을 보여, 보다 안정적이고 예측 가능한 수렴 특성을 나타낸다.

Fig. 8.

Comparison of DARP convergence iteration distributions by initialization method in a complex environment

마지막으로 일반 환경에서도 동일한 비교를 수행하여 초기화 방식에 따른 성능 변화를 표 9~11에 정리하였다. 표 9에서 초기 위치를 고려하지 않은 DARP 방식은 평균 반복 횟수 1375회, 평균 실행 시간 42.35초를 나타냈다. 이는 초기 로봇 위치가 적절히 분산되지 않은 경우, DARP가 영역 균등화를 위해 반복적인 경계 조정을 많이 수행해야 함을 의미한다. 표 10의 K-Means 기반 초기화는 평균 반복 횟수를 720회로 감소시켜 기존 방식 대비 약 47.6% 줄였으며, 평균 실행 시간도 34.08초로 약 19.5% 단축하였다. 표 11의 BFS+K-Means 결합 초기화는 평균 반복 횟수가 약 551.75회로 가장 작게 나타나, 연결 구조를 반영한 전처리가 반복적 재조정 부담을 크게 줄였음을 보여준다.

Table 9.

DARP(Standalone) performance in a normal environment

Table 10.

K-Means-Based initialization method in a normal environment

Table 11.

BFS + K-Means hybrid method in a normal environment

일반 환경에서도 동일한 방식으로 반복 횟수 결과를 그림 9에 boxplot으로 정리하였다. 전체적으로 복잡한 환경에 비해 반복 횟수 수준은 낮지만, 초기화 방법에 따른 분포 차이는 유사하게 나타난다. 특히 제안 방법은 기존 DARP 및 K-Means 기반 초기화에 비해 향상된 결과를 보임을 알 수 있다.

Fig. 9.

Comparison of DARP convergence iteration distributions by initialization method in a normal environment

종합하면, 초기 위치를 고려하지 않은 DARP는 높은 초기 불균형율로 인해 반복 횟수와 실행 시간이 증가하는 경향을 보였으며, 특히 로봇 밀집 배치나 병목/협소 구간이 포함된 조건에서 수렴 성능이 급격히 악화되었다. 반면 K-Means 기반 초기화는 초기 중심 분산을 통해 불균형을 완화하여 반복 횟수와 실행 시간을 일관되게 감소시켰다. 더 나아가 BFS–K-Means 결합 초기화는 복잡 지형에서 연결 구조를 반영함으로써 동일한 수준의 공정성을 유지하면서도 반복 횟수를 추가로 감소시켜, DARP의 수렴 효율을 가장 효과적으로 향상시키는 것으로 확인되었다.

Ⅶ. 결 론

본 연구는 격자 기반 다중 로봇 커버리지 경로 계획에서 DARP 알고리즘의 성능이 초기 로봇 위치에 민감하다는 문제에 주목하였다. DARP를 1회 수행한 직후의 초기 분할 결과로부터 공정성 지수 𝐽와 불균형율 를 정의하고, α가 DARP의 총 반복 횟수 𝐾 및 실행 시간 𝑇의 증가와 강한 상관관계를 가진다는 점을 정량적으로 분석하였다. 실험 결과 α가 임계값 α_th를 초과하는 구간에서 반복 횟수와 실행 시간이 급격히 증가하며, 일부 조건에서는 종료 조건 내 수렴 실패(Failed)가 발생함을 확인하였다. 이를 바탕으로 본 연구는 α를 사전 진단 지표로 활용하여, 초기 위치를 고려하지 않은 DARP 단독 적용과 초기 위치를 고려한 초기화 적용 여부를 선택적으로 결정하는 전략을 제안하였다. 또한 본 연구는 K-Means 및 BFS를 결합한 초기화 구조를 제안하였다. K-Means 기반 초기화는 초기 중심을 공간적으로 분산시켜 초기 분할의 편향을 완화하고, BFS를 추가한 결합 초기화는 자유공간의 연결 구조와 장애물 분포를 반영하여 병목/협소 구간에서의 단절 가능성을 낮추도록 설계하였다. 실험 결과 BFS+K-Means 결합 초기화는 DARP 단독 적용 대비 반복 횟수와 실행 시간을 유의미하게 감소시키면서도, 안정적인 분할 품질을 유지하였다. 향후 연구에서는 제안한 초기화 선택 구조를 다양한 실내 및 실외 환경과 동적 장애물이 존재하는 상황으로 확장하여 그 유효성을 검증할 계획이다. 또한 본 연구에서 사용한 임계값을 보편적 고정값으로 두기보다, 지도 구조, 장애물 분포, 로봇 수, 초기 배치 특성 등 환경 특징량에 따라 자동으로 조정하는 adaptive threshold selection 기법으로 확장하고자 한다. 더 나아가 강화학습 기반 기법 또는 온라인 재초기화 전략과 결합함으로써 초기 불균형율 예측과 초기화 선택 과정을 자동화하고, 궁극적으로 실시간 다중 로봇 커버리지 운용이 가능한 통합 구조로 발전시키고자 한다.

Acknowledgments

이 연구는 정부(과학기술정보통신부)의 재원으로 정보통신기획평가원-대학ICT연구센터(ITRC)의 지원(IITP-2026-RS-2024-00437190, 100%)과 (2026)년도 교육부 및 경상북도의 재원으로 경북RISE센터의 지원을 받아 수행된 지역혁신중심 대학지원체계(RISE)-(특성화 대학)의 결과입니다(2026-rise-15-105)

References

• M. H. Zafar, E. F. Langås, and F. Sanfilippo, "Exploring the Synergies Between Collaborative Robotics, Digital Twins, Augmentation, and Industry 5.0 for Smart Manufacturing: A State-of-the-Art Review", Robotics and Computer-Integrated Manufacturing, Vol. 89, pp. 1-29, Oct. 2024. [https://doi.org/10.1016/j.rcim.2024.102769]
• R. Stern, "Multi-Agent Path Finding—An Overview", Lecture Notes in Computer Science, pp. 96-115, Jul. 2019. [https://doi.org/10.1007/978-3-030-33274-7_6]
• J. Gong and S. Lee, "Hierarchical Area-Based and Path-Based Heuristic Approaches for Multi-Robot Coverage Path Planning With Performance Analysis", Sensors, Vol. 23, No. 20, pp. 1-19, Oct. 2023. [https://doi.org/10.3390/s23208533]
• H. Choset, "Coverage for Robotics—A Survey of Recent Results", Annals of Mathematics and Artificial Intelligence, Vol. 31, pp. 113-126, Oct. 2001. [https://doi.org/10.1023/A:1016639210559]
• A. C. Kapoutsis and S. A. Chatzichristofis, "DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning", Journal of Intelligent & Robotic Systems, Vol. 86, pp. 663-680, Jan. 2017. [https://doi.org/10.1007/s10846-016-0461-x]
• O. Idir and A. Renzaglia, "Multi-Robot Weighted Coverage Path Planning: A Solution Based on the DARP Algorithm", 2022 17th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, pp. 98-104, Dec. 2022. [https://doi.org/10.1109/ICARCV57592.2022.10004273]
• N. Baras, M. Dasygenis, and N. Ploskas, "Multi-Robot Coverage Path Planning in 3-Dimensional Environments", 2019 8th International Conference on Modern Circuits and Systems Technologies (MOCAST), Thessaloniki, Greece, pp. 1-4, May 2019. [https://doi.org/10.1109/MOCAST.2019.8741700]
• Y. Huang, M. Li, and T. Zhao, "A Multi-Robot Coverage Path Planning Algorithm Based on Improved DARP Algorithm", arXiv preprint, arXiv:2304.09741, , pp. 1-16, Apr. 2023. [https://doi.org/10.48550/arXiv.2304.09741]
• M. Zhou, J. Li, C. Wang, J. Wang, and L. Wang, "Applications of Voronoi Diagrams in Multi-Robot Coverage: A Review", Journal of Marine Science and Engineering, Vol. 12, No. 6, pp. 1-21, Jun. 2024. [https://doi.org/10.3390/jmse12061022]
• N. Baras and M. Dasygenis, "Area Division Using Affinity Propagation for Multi-Robot Coverage Path Planning", Applied Sciences, Vol. 13, No. 14, pp. 1-15, Jul. 2023. [https://doi.org/10.3390/app13148207]
• H. Lee and M. Lee, "Multi-Agent Coverage Path Planning Using Graph-Adapted K-Means in Road Network Digital Twin", Electronics, Vol. 14, No. 19, pp. 1-22, Oct. 2025. [https://doi.org/10.3390/electronics14193921]
• J. Tang, Z. Mao, and H. Ma, "Large-Scale Multi-Robot Coverage Path Planning via Local Search", AAAI Conf. on Artificial Intelligence (AAAI), Vancouver, Canada, Vol. 38, No. 16, pp. 17567-17574, Feb. 2024. [https://doi.org/10.1609/aaai.v38i16.29707]
• R. Mitra and I. Saha, "Online On-Demand Multi-Robot Coverage Path Planning", 2024 IEEE International Conference on Robotics and Automation (ICRA), Yokohama, Japan, pp. 14583-14589, May 2024. [https://doi.org/10.1109/ICRA57147.2024.10611610]
• Y. Wang and L. Luo, "IB-DARP: An Algorithm for Multi-Vessel Collaborative Task and Path Planning", Journal of Marine Science & Engineering, Vol. 14, No. 2, pp. 1-28, Jan. 2026. [https://doi.org/10.3390/jmse14020165]
• H. Ban and J. Kaiyi, "Fair resource allocation in multi-task learning", ICML'24: the 41st International Conference on Machine Learning, Vienna, Austria, No. 109, pp. 2715-2731, Jul. 2024. [https://doi.org/10.48550/arXiv.2402.15638]