1. 서 론

다중 로봇 작업 할당(Multi-Robot Task Allocation, MRTA) 문제는 다수의 로봇에게 주어진 작업 지점들을 어떻게 효율적으로 할당하느냐를 다루며, 모든 작업을 완료하는 데 필요한 총소요 시간(makespan)을 최소화하는 것이 일반적인 목표다. 이 문제는 로봇 수, 중간지점(waypoint) 분포, 경로 장애물 등의 요인이 복합적으로 작용하는 난해한 최적화 문제로 알려져 있다^[1,2]. 기존 연구에서는 Greedy 알고리즘이나 전통적인 유전 알고리즘(Genetic Algorithm, GA)을 활용한 MRTA 해법들이 제안되었으나, Greedy 방식은 국소 최적해에 쉽게 빠지고^[9], 무작위 초기 해에 기반한 메타 휴리스틱 접근은 초기 해 품질 저하 및 수렴 속도 저하를 일으키는 한계가 있다^[3,4,10]. 또한, K-Means 클러스터링을 활용하여 MRTA를 해결하고자 한 시도도 있으나^[16,17], 이는 사전 처리로 활용하는 접근으로 클러스터 개수를 사전에 결정해야 하고 각 클러스터를 구형(convex) 형태로 가정하기 때문에 MRTA처럼 작업 지점이 불규칙적으로 분포하거나 환경 변화가 잦은 상황에서 효과적이지 않을 가능성이 높다^[5,6,11]. 게다가 극단적인 위치에 있는 일부 포인트가 클러스터 중심에 큰 영향을 주어 왜곡된 클러스터를 형성하는 문제도 발생한다^[14,15].

이러한 한계를 극복하기 위해 밀도 기반 클러스터링 기법인 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)이 다양한 분야에서 활용된다^[12,13]. DBSCAN은 데이터 밀도를 기반으로 클러스터를 형성함으로써 클러스터 수를 사전에 정의할 필요가 없으며, 노이즈 포인트나 이상값을 군집 밖으로 분류해 불균일한 분포나 복잡한 환경 변화에도 유연하게 대응할 수 있다^[3,5]. 한편, GA를 적용한 최적화 문제에서 초기 해 품질 개선을 위해 도메인 지식을 반영한 초기 해 구성 방법인 초깃값 생성 유전 알고리즘(Seeding GA)이 기존 연구들에서 제안된 바 있으며, 이는 문제 특성에 적합한 초기 해를 제공함으로써, 수렴 속도 향상과 해 품질 개선에 기여한다^[1,2,7].

그림 1. 제안하는 알고리즘의 프레임워크

Fig. 1. Framework of the proposed algorithm

본 논문에서는 그림 1과 같이 MRTA 문제에서 DBSCAN으로 작업 지점을 밀도 기반으로 군집화하고, A* 알고리즘을 통해 각 클러스터 간 최적 경로를 도출한 뒤, 이를 Seeding GA 초기 해로 활용하는 새로운 접근을 제안한다. 이를 통해 MRTA의 복잡한 해공간 탐색 과정에서 초기 해 품질을 높이고, makespan을 효율적으로 단축하는 방법론을 제시한다.

이하 본문에서는 문제 정의(2장), 제안한 알고리즘 설계(3장), 시뮬레이션 및 실험 결과(4장), 결론(5장)를 순차적으로 다룬다.

2. 문제 정의

본 논문에서는 여러 대의 로봇과 각 로봇이 순회해야 할 중간 지점들이 존재하며, 각 로봇은 자신의 위치에서 출발해 할당된 중간 지점들을 순회한 후 다시 자신의 위치로 돌아와야 한다. 환경은 2차원 그리드로 표현되며, 장애물이 있을 수 있다. 로봇은 8방향(상, 하, 좌, 우 및 대각선 4방향)으로 이동할 수 있다.

먼저 2.1절에서는 문제에서 주어지는 기본적인 집합들과 파라미터들을 정의하고 설명한다. 이어서 2.2절에서는 문제 해결을 위한 핵심 요소인 의사결정 변수들을 소개한다. 2.3절에서는 의사결정 변수들로부터 도출되는 종속 변수들에 대해 다루며, 마지막으로 2.4절에서는 문제의 제약 조건들을 설명한다.

2.2 의사결정 변수

의사결정 변수는 일반적으로 최적화 과정에서 직접 결정되는 변수들을 의미한다. 중간지점 할당 변수, 경로 변수, 순서 변수가 존재하며, 수식적 표현은 이와 같다.

(6)

(7)

이때, $i=1,\: 2,\: \cdots ,\: M$ 이고, $j=1,\: 2,\: \cdots ,\: N$ 이며, $p,\: q\in V$ 이다. 식 (6)은 중간지점 할당 변수이며, 로봇 $r_{i}$가 중간지점 $w_{j}$를 방문하면 $x_{i,\: j}$가 1이 되며, 그렇지 않다면 0이 된다. 식 (7)은 경로 변수로 로봇 $r_{i}$가 중간지점 $w_{p}$에서 중간지점 $w_{q}$로 이동하면 $y_{i,\: pq}$가 1이 되며 그렇지 않다면 0이 된다.

3. 제안한 유전 알고리즘 설계

본 장에서는 makespan을 최소화하여 작업 효율을 극대화하기 위해 A* 알고리즘과 DBSCAN 군집화 기법을 기반으로 한 Seeding GA를 설계한다. Seeding GA는 사전 지식이나 휴리스틱의 출력값을 GA에 사용되는 초기 유전자를 제작하여 넣어주는 방법이다.

그림 2, 3, 4, 5, 7에 해당하는 알고리즘은 DBSCAN 알고리즘에 기반하여 저자가 구성한 알고리즘을 명시한다.

3.1 A*와 DBSCAN 기반 초기 유전자 제작

본 절에서는 Seeding GA에서의 초기 유전자 값을 도출해 내기 위한 방법에 관하여 설명한다. 이때, DBSCAN 군집화 알고리즘을 활용하여 중간 지점들을 공간적 밀도에 기반하여 군집화하고, 각 군집을 로봇에 효과적으로 할당하여 초기 경로를 생성한다. 이를 위한 과정의 개요가 그림 2에 소개되어 있다. 그림 2의 ‘Step 1’에서 중간지점 요소 간 거리와 경로를 거리 행렬(Distance Matrix)에 저장한다. 거리 행렬은 A* 알고리즘에 기반하여 계산한다. 그다음 DBSCAN 군집화를 수행하며, 군집화가 완료되면 각 로봇에게 순회해야 할 군집을 지정한다. 그 후에 노이즈 포인트로 지정된 중간지점은 가장 가까운 로봇에게 할당한다. 각 로봇에 할당된 중간 지점들을 대상으로 Nearest Neighbor 휴리스틱을 적용하여 각 로봇의 경로를 생성한다.

그림 3은 그림 2의 ‘Step 2’에 해당하는 과정을 상세히 설명한 의사코드이다. 그림 3에서, 본 논문은 최소 샘플 수를 2개로 지정하였고 $\epsilon$은 거리 행렬의 10번째 백분위수로 초기화하였다. 이는 군집을 더 세밀하고 밀집된 형태로 구성하기 위함이다. DBSCAN 알고리즘을 사용하여 군집화를 수행한다. 생성된 군집 개수가 로봇 대수 $M$ 이상이면 DBSCAN 알고리즘을 종료한다. 만약, 군집 개수가 $M$보다 작은 경우에는 $\epsilon$값을 감소시키고 군집화를 재차 수행한다. 만약, $\epsilon$값을 거리 행렬 내에 존재하는 최솟값으로 설정하였는데도 군집 개수가 부족한 경우에는 노이즈 포인트를 새로운 군집으로 만들어 군집 개수를 $M$ 이상으로 만든다.

그림 2. Seeding GA의 초기 유전자 도출 방법 개요

Fig. 2. Overview of the initial gene generation method for Seeding GA

그림 3. 초깃값 생성을 위한 DBSCAN 군집화 의사코드 (그림 2의 Step 2)

Fig. 3. Pseudocode for DBSCAN clustering for initial value generation (Step 2 of Figure 2)

그림 4는 그림 2의 ‘Step 3’에 해당하는 과정을 상세히 설명한 의사코드이다. 그림 4에서 각 군집에 소속된 중간 좌표들의 중심점을 지정한 점을 ‘대표점(representative point)’이라고 부른다. 각 군집의 대표점들과 로봇간 거리를 계산한다. 그 후에 로봇들은 순서대로 자신에게 가장 가까운 대표 점을 선택한다. 이를 남은 대표점이 없을 때까지 반복한다.

그림 2의 ‘Step 4’는 군집에 포함되지 못한 노이즈 포인트에 대해 ‘Step 3’와 유사하게 로봇에게 가까운 순서대로 할당한다.

그림 5는 그림 2의 ‘Step 5’에 해당하는 과정을 상세히 설명한 의사코드이다. 그림 5에서, 각 로봇에게 할당된 중간지점들을 대상으로 Nearest Neighbor 휴리스틱을 적용하여 각 로봇의 경로를 생성한다.

그림 4. 초깃값 생성을 위한 군집 분배 의사코드 (그림 2의 Step 3)

Fig. 4. Pseudocode for cluster distribution for initial value generation (Step 3 of Figure 2)

그림 2의 ‘Step 6’에서는 위의 과정을 통해 도출된 결괏값을 GA의 염색체 양식에 맞추어 변환한 후에 1세대 염색체에 대입한다.

그림 5. 초깃값 생성을 위한 각 로봇 경로계획 수립 의사코드 (그림 2의 Step 5)

Fig. 5. Pseudocode for establishing the path planning for each robot for initial value generation (Step 5 of Figure 2)

3.2 A* 유전 알고리즘 설계를 위한 염색체 구조 설계

본 절에서는 GA의 염색체 설계에 관해 설명한다. 그림 6의 ‘염색체 구성 방법’과 같이 ‘로봇 출발점 좌표’가 주어져 있다. 그리고, 염색체는 ‘중간지점 좌표 염색체’와 ‘로봇당 중간지점 할당 개수 염색체’가 있다. ‘중간지점 좌표 염색체’는 모든 로봇이 순회해야 할 중간 지점들을 순서대로 나열해둔 염색체이다. ‘로봇당 중간지점 할당 개수 염색체’는 각 로봇이 순회해야 할 중간지점의 개수를 담아둔 염색체이다. 그림 6의 ‘염색체 구성 예시’와 같이 로봇은 2대가 있고, 중간지점 좌표 염색체는 $[w_{1},\: w_{2},\: w_{3},\: w_{6},\: w_{5},\: w_{4}]$와 같이 되어있을 때, 로봇당 중간지점 할당 개수가 순서대로 3, 3이면 중간지점 좌표의 첫 번째 중간지점부터 3번째 중간지점까지는 1번 로봇에게 할당되는 좌표이며, 4번째 중간지점부터 6번째 중간지점까지는 2번 로봇에게 할당되는 좌표라는 의미이다. 이러한 구성을 통해 GA의 염색체를 구성하였다. 이때, ‘중간지점 좌표 염색체’와 ‘로봇당 중간지점 할당 개수 염색체’에 따라 각 로봇의 업무 순서와 업무량이 정해지므로 세대 진행 과정에서 염색체 길이가 가변하지 않는다.

그림 6. GA 설계를 위한 염색체 구성

Fig. 6. Composition of chromosomes for GA configuration

3.3 각 로봇의 업무 할당을 최적화하기 위한 유전 알고리즘 설계

그림 7은 제안한 GA의 의사코드이다. GA에는 중간지점 좌표, 로봇 좌표, 거리 행렬, 개체수, 반복 세대수, elistism 사이즈를 입력한다. 그림 7에서, 먼저 initialize_population을 이용하여 초기 개체집단을 생성한다. 이 함수는 다양한 초기 솔루션을 생성하여 탐색 공간을 넓히는 역할을 한다. 이때, A* 알고리즘-DBSCAN 알고리즘을 활용한 초기 유전자를 사용한다. Elitism에 의해 엘리트도 보존하는데 Elistism 사이즈만큼 염색체를 그대로 다음 세대로 전달한다. 엘리트 보존은 우수한 유전자를 다음 세대로 전달하여 알고리즘의 성능을 향상한다. 그 후에 Fitness function을 통해 유전자들을 적합도가 높은 순으로 정렬한다. 이때, Fitness function은 식 (14)를 사용한다. 그 후에 유전자 선별을 하는데, 본 논문에서는 적합도 높은 순으로 정렬했을 때 상위 50%를 선별한다. 그 후에 부모 풀(Parent Pool)에서 두 부모를 랜덤하게 선택하여 교차 연산(crossover)을 수행한다. 이때, 매핑된 교차(Partially Mapped Crossover, PMX)를 수행하여 부모의 유전자를 교차한다. 그 후에 돌연변이(mutation)를 거치게 된다. 돌연변이는 스왑(swap), 삽입(insertion), 역전(inversion)이 존재한다. 그 후에 적합도 계산을 한 후에 새로운 개체집단으로 현재 개체집단을 대체한다. 다음으로 현재 존재하는 염색체 중에 가장 점수가 높은 염색체에 대하여 지역 탐색(Local Search)중 하나인 2-opt 알고리즘을 적용하여 해법을 개선한다. 지역 탐색은 전역 탐색인 유전 알고리즘과 결합하여 더 나은 솔루션을 찾는 데 도움이 된다. 이를 세대수만큼 반복하여 GA의 결과값이 나오게 된다. 표 1에서는 본 논문에서 사용한 GA의 파라미터 값을 확인할 수 있다.

그림 7. GA 설계를 위한 의사코드

Fig. 7. Composition of chromosomes for GA configuration

표 1 GA에 사용된 파라미터값

Table 1 Parameters used in GA

파라미터 명	의미 및 용도	실험 내 지정값
개체집단 크기 (Population)	한 세대에서 유지되는 후보 해의 개수	100개
반복 세대 수	지정된 세대 수만큼 진화를 반복	500세대
Elitism 사이즈	Elitism를 통해 우수 해의 유실 방지	개체집단 크기의 10% 적용
변이 확률	후손 개체에 돌연변이를 발생시킬 확률	각 종류(swap, insertion, inversion)마다 5% 적용
유전자 선별	상위 개체 중 무작위 선택을 통해 우수한 해 중심으로 진화 유도	점수 높은 상위 유전자 50% 적용
지역 탐색 적용	우수 해에 대해서만 국소 최적화를 적용하여 추가 개선 유도	점수가 가장 높은 유전자 1개에 적용

4. 시뮬레이션 및 실험 결과

본 장에서는 제안된 DBSCAN 기반 Seeding GA 알고리즘의 성능을 검증하기 위한 시뮬레이션과 실험 결과를 상세하게 기술한다. 실험은 그림 8에 제시된 두 개의 맵에서 수행되었다. Map 1과 Map 2는 서로 다른 복잡도와 장애물 구성이다. 해당 Map들은 로봇의 경로 탐색과 작업 할당에 영향을 주며 Liu et al.가 문제를 제시한 이후, 여러 과학자 또한 유사한 Map을 활용하여 실험하였다^[7,10]. 각 Map에서 로봇의 수는 3대와 6대로 설정하여, 로봇 수의 변화에 따른 알고리즘의 성능을 평가하였다. 그림 8에서 로봇이 3대인 경우에는 빨간색 로봇만 기동하며, 로봇이 6대인 경우에는 빨간색과 초록색 로봇이 모두 기동한다. 파란색 원은 로봇들이 방문해야 할 중간 지점을 의미한다. 시뮬레이션은 Python 3.8을 사용하여 구현되었으며, AMD Ryzen 3900x CPU와 32GB RAM을 가진 PC에서 진행하였다.

본 실험에서는 다음의 다섯 가지 알고리즘을 비교하였다. DBSCAN GA는 본 논문에서 제안한 알고리즘으로, A* 알고리즘과 DBSCAN 군집화를 기반으로 유전자를 생성하여 GA의 초깃값에 사용한다. Greedy GA는 Liu et al.이 제안한 방식으로 A* 알고리즘과 Greedy 방법을 사용하여 초기 유전자를 생성한 후 GA에 사용한다^[7]. GA는 초기 유전자를 무작위로 생성하여 GA를 수행한다^[9]. DBSCAN은 그림 2에 제시한 방법을 사용하여 작업을 할당한다. 마지막으로, Greedy는 Greedy 알고리즘만을 사용하여 작업을 할당한다. 각 알고리즘은 동일한 조건에서 30회의 독립적인 실험을 수행하였으며, 평가 척도는 로봇들의 makespan을 최소화하는 것이다.

그림 8. 시뮬레이션 환경 지도 (좌: Map 1, 우: Map 2)

Fig. 8. Simulation environment map (Left: Map 1, Right: Map 2)

실험 결과는 그림 9와 표 2에 요약되어 있으며, 표 2에는 각 알고리즘의 평균 makespan과 표준편차를 제시하며, 그림 9는 실험 결과를 box plot으로 시각화하였다.

각 실험 조건에서 알고리즘 간 makespan 평균 차이가 통계적으로 유의미한지 검증하기 위해 일원분산분석(ANOVA)을 수행하였다. 그 결과, 모든 실험에서 $F$-값이 매우 크고, $p$-값이 0.001보다 작아 알고리즘 간 평균 makespan에 통계적으로 매우 유의미한 차이가 있음을 확인하였다.

DBSCAN GA 알고리즘은 모든 실험 조건에서 가장 낮은 평균 makespan과 낮은 표준편차를 보여, 가장 안정적이고 우수한 성능을 입증하였다. 가장 큰 개선율은 Map 1, 3대 로봇 환경에서 나타났으며, Greedy GA 대비 평균 26.16%의 성능 향상을 보였으며, 전체 평균 개선율은 15.74%이다. 이러한 결과는 DBSCAN을 통해 군집화한 결과를 GA에 초기 유전자로 사용함으로써, 초기 해의 품질을 향상시켜 GA의 탐색 효율을 높였음을 의미한다.

그림 9. 시뮬레이션 환경별 makespan 값에 대한 box plot

Fig. 9. Box plot of makespan values by simulation environment

5. 결 론

본 논문에서는 MRTA에서 makespan을 최소화하기 위한 효율적인 알고리즘으로 A* 알고리즘과 DBSCAN 군집화 알고리즘을 기반으로 한 Seedig GA를 제안하였다. 제안된 알고리즘은 초기 유전자를 생성할 때 A* 알고리즘을 활용한 최단 경로 탐색과 DBSCAN 군집화를 통한 작업 지점의 효과적인 그룹화를 결합하여, GA의 탐색 효율을 향상시켰다.

시뮬레이션 및 실험 결과, 제안된 DBSCAN 기반 Seeding GA 알고리즘은 기존의 Greedy-GA, GA, Greedy, DBSCAN 알고리즘에 비해 makespan을 유의미하게 감소시켰음을 확인하였다. 또한, 다양한 환경 지도와 로봇 수 조건에서 평균적으로 최대 26.16%의 성능 개선을 달성하였으며, 이는 통계적으로도 유의미한 결과임을 입증하였다.

특히, Greedy GA 또한 도메인 지식을 활용한 초기화 접근 방식임에도 불구하고, 제안한 DBSCAN GA가 Greedy GA 대비 유의미한 성능 향상을 달성했다는 점은 단순히 도메인 지식의 유무가 아니라, 어떠한 형태의 도메인 지식을 어떤 방식으로 활용하는지가 해 품질과 탐색 효율에 결정적인 영향을미친다는 것을 시사한다. 즉, 동일한 ‘도메인 기반 Seeding GA’ 접근 안에서도, DBSCAN을 통한 초기 해 생성 전략이 단순한 Greedy 기반 초기화보다 더욱 유리한 탐색 환경을 제공함을 확인할 수 있다. 도메인 지식 활용 방식에 따라 성능 편차가 크게 발생할 수 있음을 보여주어, 제안한 기법이 MRTA 문제에 있어 효율적이고 안정적인 해 탐색 전략으로 작용할 수 있음을 시사한다.

제안된 알고리즘은 로봇 간의 효율적인 작업 분배와 경로 계획을 가능하게 하여 시스템의 전체적인 효율성을 크게 높였다. 또한 낮은 표준편차를 보여 알고리즘의 안정성을 입증하였으며, 로봇 수가 증가하는 상황에서도 일관된 성능을 유지하여 확장성이 뛰어남을 확인하였다. 이는 다양한 산업 환경에서의 적용 가능성을 시사하며, 로봇 기술의 발전과 함께 산업 현장에서의 생산성 향상과 비용 절감에 기여할 수 있을 것으로 기대된다.

한편, GA와 A* 알고리즘 결합으로 인한 추가적 계산 시간은 실제 응용에서 고려해야 할 중요한 요소이다. 향후 연구에서는 병렬 연산, GPU 가속, 경량화된 휴리스틱 등의 최적화 기법을 도입하여 계산 시간을 단축하고, 실시간성 요구사항을 갖는 동적 환경에서의 MRTA 적용 가능성을 모색할 것이다. 또한, 로봇의 추가나 제거, 작업 지점의 변화를 비롯한 동적인 상황에서도 제안된 알고리즘이 효과적으로 작동할 수 있도록 개선하고, DBSCAN 이외의 다양한 군집화 기법이나 혼합 기법을 활용해 초기 유전자의 다양성과 품질을 더욱 향상시킬 계획이다. 이후, 실제 로봇 시스템에 본 알고리즘을 적용하여 실시간 MRTA 수행 및 성능 검증을 진행할 것이며, makespan 최소화 뿐만 아니라 에너지 소비 최적화, 로봇 간 작업 부하 균형 등의 다목적 최적화 문제로 확장함으로써 보다 종합적인 해법을 개발하고자 한다.

아울러, Constrained Optimization 기법과의 직접적인 성능 비교는 본 연구 범위를 넘어서는 확장 과제로 남아있다. 이러한 기법들은 이론적 정확성을 추구할 수 있으나, 대규모 환경이나 발 빠른 대응이 요구되는 MRTA 상황에서 연산 부담과 적용성 측면에서 제약이 있을 수 있다. 본 연구에서는 실용적이고 유연한 접근을 중시하였으나, 향후에는 문제 단순화, 추가 자원 확보 등을 통해 Constrained Optimization 접근과 정량적 비교를 시도함으로써 제안 기법의 장단점을 보다 명확히 파악하고, 다양한 조건 하에서의 일반화 가능성을 검토할 계획이다.

본 연구의 결과는 MRTA 분야에서 새로운 접근법을 제시하였으며, 복잡한 산업 요구를 충족시키고 로봇 기술의 잠재력을 최대한 활용하기 위한 기반을 마련하였다. 이를 통해 다양한 산업 분야에서의 로봇 협업 시스템 개발과 효율성 향상에 기여할 수 있을 것으로 사료된다.