1. 서 론
군집 로봇이란 상대적으로 작은 크기와 단순한 구조를 가지는 다수의 로봇을 네트워크를 이루어 운용하는 것을 말한다. 네트워크를 통해 연결된 다수의 군집 로봇을 분산 배치함으로써, 단일 운용되는 대형, 고가의 로봇과 비교했을 때 높은 확장성과 강건성, 다양한 임무 환경에 적응할 수 있는 유연성을 갖춰 새로운 무기체계의 운용 개념으로 주목받고 있다. 실제로 감시정찰 및 수색 임무에서 군집 로봇의 장점을 활용한 사례가 미국 DARPA 주관의 OFFSET 프로그램이다. 해당 프로그램에서는 도시 지역에서의 감시정찰, 강습 및 점령 임무를 수행 가능한 복합 군집 로봇의 운용 전술을 개발하고 실증하는 성과를 보였다.
소형 군집 로봇의 장점이 유의미하게 활용될 수 있는 또 다른 문제로는 미지의 임무 공간에 대한 탐사 및 지도 작성이 있다. 소형 군집 로봇은 작은 크기의 이점을 살려 대형 로봇이나 사람이 접근하기 어려운 지역을 효과적으로 탐사할 수 있다. 또한 미지의 위험 요소가 존재하는 임무 공간을 사람을 대신하여 탐사하고, 이 과정에서 위험 요소에 대한 평가를 위한 분산화 된 정보 취득에서도 장점을 보인다.
이러한 문제에서 다중 군집 로봇을 효과적으로 활용하는 방안은 로봇에 위계를 부여하는 것이다. 여기서 위계란, 군집 로봇의 그룹을 형성하고 그룹 별로 리더와 팔로워 로봇을 나누어 로봇의 임무 계획 및 의사 결정 과정을 분산화하는 것을 말한다. 이렇게 함으로써 시스템 전체의 연산 및 통신 부담을 줄이고, 시스템의 확장성과 강건성을 높일 수 있다. 이 때, 군집 로봇 시스템의 효용성을 높이기 위해서는 분산화된 임무 계획 과정에서 그룹 간의 협업을 고려할 필요가 있다.
로봇을 이용해 임무 공간을 탐사하는 방법은 다양한 분야에서 연구되고 있다. 극지방이나 타 행성을 탐사하거나[1,2], 바닷속을 탐사하는 연구가 제안되었다[3]. 미국 DARPA 주관의 Subterranean challenge에서는 그래프 기반의 경로 계획법을 통한 탐사 알고리즘이 제안되었다[4,5]. 또한 임무 공간 탐사에서 군집 로봇을 활용하는 방법으로 frontier 기반의 탐사 방법과 로봇 간의 협업을 고려하는 방법에 대해서 연구된 바 있다[6,7]. 그러나 기존의 군집 로봇 탐사 알고리즘의 경우 로봇 간 협업에 대한 고려가 부족하고, 특히 군집 로봇이 위계를 가지고 있는 경우, 이러한 구조에 맞는 임무 계획 방법 연구가 필요하다.
따라서 본 연구의 목표는 그룹을 이루고 있는 다수의 군집 로봇을 활용하여 미지의 임무 공간에 대한 탐사 및 지도 작성을 효과적으로 수행하는 알고리즘을 개발하는 것이다. 이를 위해 분산화된 임무 계획 과정에서 그룹 간의 협업을 고려하는 방안을 제안하고자 한다.
2. 문제 정의
본 연구는 2차원 격자를 통해 표현되는 임무 공간을 군집 로봇을 통해 탐사하고 지도를 작성하는 문제를 다룬다. 이때, SLAM(Simultaneous Localization and Mapping) 기법 등을 통해 군집 로봇의 위치가 파악되며, 이를 다른 그룹과 공유할 수 있는 상황을 가정하였다[8-11]. 군집 로봇이 각자 그룹을 이루고 있을 때, 시스템의 효율적인 운용을 위해 다음과 같이 하이브리드 임무 계획 아키텍처를 정의하였다.
2.1 하이브리드 임무 계획 아키텍처
군집 로봇이 형성하고 있는 그룹에는 리더와 팔로워 로봇이 존재하며, 팔로워 로봇은 리더 로봇을 통해 중앙과 통신이 연결되어 있다고 가정한다. 리더와 팔로워를 포함하는 각 그룹의 로봇이 지도 작성을 수행하고 그 결과를 리더가 취합하여 군집 로봇의 현재 상태와 함께 중앙으로 전달한다. 중앙에서는 각 그룹에서 전달받은 정보를 융합해 전역 정보를 그룹 리더에게 배포한다. 그룹 리더는 전역 지도 정보와 자신의 그룹을 포함한 군집 로봇들의 상태 정보를 활용해 다른 그룹과의 협업을 고려한 군집 임무 계획을 수행한다. 이렇듯 개별 군집 로봇, 리더, 중앙의 위계를 가지는 구조에서 그룹 별로 분산화된 임무 계획을 수행하는 구조를 하이브리드 임무 계획 아키텍처라 정의한다.
2.2 지도 작성
본 연구에서 지도 작성 문제는 정해진 시간 내에 최대한 많은 영역을 탐사하거나 최대한 짧은 시간에 정해진 임무 공간을 탐사하여 지도를 작성하는 것을 목표로 한다. 이때, 지도 작성 로봇은 그룹을 형성하고 있으며 그룹 구성원에 대한 지도 작성 임무 계획은 그룹의 리더가 수행한다. 군집 로봇이 그룹을 형성하고 있을 때, 전체 시스템의 지도 작성 효율을 높이기 위해서는 그룹 간의 협업을 고려해야 한다. 그룹 간의 협업을 효과적으로 고려하기 위해 그룹 리더가 임무 계획 과정에서 활용 가능한 전역 지도 정보와 현재 군집 로봇의 상태 정보를 바탕으로 각 그룹이 탐색할 영역을 분할한다. 그룹 별 탐색 영역을 분할한 이후, 그룹 리더는 개별 로봇이 방문할 경로점을 선택하고 할당한다.
2.1절에서 정의된 하이브리드 임무 계획 아키텍처 하에서 지도 작성 과업을 수행할 때, 각 계층이 주고받는 정보는 Fig. 1과 같이 나타낼 수 있다.
3. 지도 작성을 위한 임무 계획 알고리즘
Frontier exploration[6,7]이란 미지의 공간을 탐사하고 지도를 작성하는 대표적인 방법론 중 하나이다. 여기서 frontier point란 작성된 지도 상에서 탐색된 개방점(open cell) 중 미탐색 영역과 접하고 있는 점을 말한다. Frontier exploration이란 이렇게 정의된 frontier point 들을 차례로 방문하면서 임무 공간을 탐색하는 방법이다. Frontier point는 탐색된 영역과 미탐색 영역의 경계에 위치하므로 일반적으로 frontier point를 방문함으로써 미탐색 영역에 대한 많은 양의 신규 정보를 취득할 수 있으며, frontier point는 탐색된 개방점에 속하기 때문에 현재 위치에서 가고자 하는 frontier point 까지 실현 가능한 경로가 항상 존재한다는 특징이 있다. 이러한 특징으로 인해 임의의 특징을 가지는 미지의 임무 공간에서도 잘 작동한다는 장점이 있다.
본 연구에서 다루는 지도 작성 임무 계획 알고리즘은 frontier exploration 기법을 기반으로 하여, 다수의 그룹으로 구성된 군집 로봇을 활용해 임무 공간을 효율적으로 탐사하기 위한 알고리즘이다. 이를 위해 군집 로봇의 그룹 간, 그룹 내의 협업을 고려하면서, 임무 계획 과정을 분산화하여 시스템의 확장성을 높이는 방안을 제시한다. 본 연구에서 제안하는 지도 작성 군집 임무 계획 알고리즘은 크게 1) 센서 모델을 통한 지역 지도(local map) 작성 및 지도 융합(map fusion) 2) Frontier segmentation 기반 탐색 영역 할당 3) Frontier point clustering 기반 그룹별 임무 계획으로 구성된다. 3.1과 3.2 절에서는 알고리즘의 구성 요소 중 2번, 3번 요소에 대해 자세하게 서술한다.
3.1 Frontier segmentation 기반 탐색 영역 할당
지도 작성 문제에서 그룹 간의 협업을 고려하는 가장 명확한 방법은 탐색해야 할 영역을 분할하여 그룹별로 할당하는 것이다. 본 문제에서 전역 지도 정보와 모든 그룹의 군집 로봇의 현재 상태가 공유되고 있다고 가정하였으므로, 각 그룹의 리더는 자신의 그룹이 어떤 영역을 방문하는 것이 전체 시스템 측면에서 가장 효과적인지를 판단할 수 있다.
먼저 전역 지도에서 frontier point들이 구성하고 있는 요소(segment)를 추출하여 그룹이 방문할 일차적인 탐색 영역을 찾는 과정을 거친다. DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[12] 알고리즘을 통해 frontier point의 군집화를 수행하면 이러한 요소를 추출하면서 장애물 등으로 인해 분리된 요소를 구분할 수 있다. 이후 그룹의 수와 추출된 요소의 수에 따라 다음과 같이 탐색 영역을 할당할 수 있다.
-
1) 그룹의 수가 요소의 수보다 작은 경우
이 경우 전체 요소 중 그룹의 수만큼 방문할 요소를 선택해야 한다. 헝가리안 알고리즘[13]을 통해 방문할 요소를 선택하는 과정은 다음과 같다.Dij를 i번째 그룹 리더와 j번째 요소의 중심 간의거리라 하고, Wj 를 j번째 요소에 속한 frontier point의 수라 할 때, 비용 행렬 Cij는 다음과 같이 정의된다.그룹과 요소 간 할당 인덱스를 xij라 할 때(할당될 경우 1, 그렇지 않으면 0), 헝가리안 알고리즘을 통한 할당 문제는 다음의 최적화 문제로 정의된다.subject to, -
2) 그룹의 수와 요소의 수가 같은 경우
이 경우 그룹의 수와 요소의 수가 같으므로 요소에 특별한 조정이 필요하지 않다. 따라서 요소 선택 과정 없이 헝가리안 알고리즘을 통해 각 그룹이 방문할 요소를 할당할 수 있다. -
3) 그룹의 수가 요소의 수보다 큰 경우
이 경우 많은 frontier point를 포함하는 영역의 지도 작성을 다수의 그룹이 함께 수행해야 한다. 때문에 K-means 알고리즘을 활용하여 요소의 수가 그룹의 수와 같아질 때까지 가장 큰 요소를 분할한다. 이후에는 2)와 동일하게 헝가리안 알고리즘을 통해 각 그룹에 탐색 영역을 할당할 수 있다.
3.2 Frontier point clustering을 통한 그룹 별 임무 계획
그룹 별로 탐색 영역을 할당한 이후, 각 그룹의 리더는 할당 받은 영역 내에서 임무 계획을 수행한다. 탐색 영역 내의 frontier point 중에서 개별 로봇이 실제로 방문할 경로점을 선택하기 위해 K-means clustering 을 활용하였다. K-means clustering을 통해 그룹 내 로봇의 수만큼의 frontier cluster를 형성하고, 각 cluster의 중심점에서 가장 가까운 frontier point를 경로점으로 선택하였다. Clustering 과정을 통해, 선택되는 경로점의 다양성을 높임으로써 그룹 내에서 로봇들이 협업하며 과업을 수행할 수 있도록 하였다. 이후 통신의 용이성을 확보하기 위해 선택된 경로점 중, 그 중점에 가장 가까운 경로점을 리더에게 할당하고(팔로워에서 리더를 거쳐 중앙으로 통신이 이어질 수 있도록), 나머지 경로점은 헝가리안 알고리즘을 통해 그룹 내 로봇의 이동 거리 합이 최소가 되도록 개별 로봇에게 할당한다.
3.1, 3.2절에서 설명한 임무 계획 알고리즘은 현재 그룹 리더가 가지고 있는 전역 정보를 바탕으로 시스템의 전체 효율성을 높이기 위해 다른 그룹이 수행할 임무를 예상하고 자기 그룹의 임무를 선택하는 방식으로 작동한다. 따라서 전체 시스템 측면에서 임무 계획의 효율성을 높이기 위해서는 모든 그룹이 동시에 임무를 계획해야 한다. 이러한 경우, 과업를 먼저 끝낸 로봇이 아직 완료하지 못한 로봇을 기다려야 하는 문제가 발생할 수 있다. 이러한 문제를 방지하기 위해, 과업을 먼저 끝낸 로봇이 대기하는 최대 시간을 정하고, 해당 시간이 지날 경우 모든 그룹에 대해 임무를 다시 계획하는 방법을 활용하였다. 본 논문에서는 30 step 이상 기다릴 경우, 임무를 다시 계획하도록 설정하였다.
4. 지도 작성 시뮬레이션 및 결과
본 논문에서 제안한 알고리즘의 성능을 검증하기 위해 군집 임무 계획 알고리즘을 통해 미지의 임무 공간을 탐사하는 시뮬레이션을 진행하였다. 시뮬레이션을 위해 다음과 같은 세 개의 시험 공간을 격자 공간상에 모델링하였다.
Fig. 2 ∼ 4에서 빨간색 X표시는 군집 로봇의 초기 위치를 나타낸다. 시험 공간 1은 개방된 하나의 방을, 시험 공간 2와 3은 작은 크기의 여러 방이 연결된 미로 형태의 공간을 나타낸다. 시험 공간 1에서 3까지 이르기까지 서로 다른 복잡도를 가지는 상황에서 알고리즘의 거동을 파악하고자 하였다.
시뮬레이션에 사용된 문제 및 센서 파라미터는 Table 1과 같다.
알고리즘 성능 평가 기준은 시뮬레이션 환경에서 주어진 임무 공간 탐사를 완료하는 데 걸리는 시간 (시뮬레이션 상의 step 수)을 사용하였다. 여기서 탐사 완료는 임무 공간에 존재하는 모든 탐사 가능한 점이 관측되었을 때를 의미한다. 시간이 적게 걸릴수록 주어진 자원을 효율적으로 활용하여 임무를 계획했다고 할 수 있다.
제안한 알고리즘과 비교하기 위한 baseline으로, 제안한 알고리즘과 동일한 frontier exploration 기반의 중앙 집중형 임무 계획 알고리즘을 활용하였다. 중앙 집중형 임무 계획 알고리즘은 전체 군집 로봇의 임무 계획을 모두 중앙에서 처리하는 방식으로, 개별 로봇 단위로 가장 효율적인 임무를 계획할 수 있으나 임무 계획 과정에서 많은 연산 및 통신 부담이 발생하고, 더 큰 문제로의 확장이 어렵다는 단점이 있다. 따라서 중앙 집중형 임무 계획 알고리즘을 이상적인 경우라 할 때, 임무 계획 과정을 분산화하면서도 얼마나 중앙 집중형 알고리즘과 유사한 수준의 성능을 보여줄 수 있는가에 초점을 맞추었다.
Fig. 5 ∼ 7에서 각 그룹이 리더를 중심으로 서로 다른 구역/방을 나누어 탐사하는 것을 확인할 수 있다. 이를 통해 임무 공간 탐사 과정에서 군집 로봇 간의 협업이 고려되고 있음을 알 수 있다.
세 시험 환경에서 임무 공간 탐사 완료까지 걸리는 시간은 Table 2와 같다.
Table 2.
Simulation result
| Open | Maze 1 | Maze 2 | |
|---|---|---|---|
| Ours | 9 / 187 | 19 / 551 | 20 / 520 |
| Baseline | 8 / 140 | 13 / 348 | 17 / 488 |
Table 2에서 앞의 숫자는 전체 임무 계획 횟수, 뒤의 숫자는 탐사에 걸린 총 시간을 의미한다. 시뮬레이션 결과, 제안한 알고리즘은 중앙 집중형 알고리즘보다 평균적으로 33 % 느린 탐사 시간을 보였다. 제안한 알고리즘에서는 하나의 구역을 탐사하기 위해 그룹이 함께 방문하는 구조이기 때문에, 모든 개별 로봇의 탐사가 따로 계획되는 중앙 집중형 알고리즘에 비해 탐사 속도가 느린 것으로 보인다. 그러나 제안한 알고리즘은 각 그룹의 임무 계획을 중앙이 아닌 그룹 리더 단에서 수립하기 때문에, 임무 계획에 필요한 연산을 그룹 리더가 나누어 수행할 수 있다. 동일한 이유로, 전체 임무 탐사에 필요한 임무 계획의 횟수도 제안한 알고리즘이 중앙 집중형에 비해 크게 나타났지만, 임무 계획이 분산 수행된다는 것을 고려하면 전체 그룹의 임무 계획에 필요한 시간은 더 짧다고 할 수 있다. 이렇듯 분산 임무 계획 알고리즘의 장점에서 파생되는 확장 가능성을 고려한다면 제안한 알고리즘이 적절한 탐사 성능을 가진다 할 수 있다.
각 시험 공간별로 중앙 집중형 알고리즘과 성능을 비교하면 각각 33.5, 58.3, 6.5 % 긴 탐사 완료 시간을 보였다(Open, Maze1, Maze2 순서). Open에서 Maze2로 갈수록 시험 공간의 복잡도(전체 공간의 크기, 구역의 수)가 증가하나, 중앙 집중형 알고리즘에 대한 상대 성능은 이러한 복잡도와는 일관된 경향성을 보이지는 않았다. 제안한 알고리즘이 시험 환경의 복잡도에 직접적인 영향을 받지 않는다고 볼 수 있다. 오히려 탐사 과정에서 발생하는 frontier segment의 수와 위치, 크기에 따른 각 그룹의 탐사 우선순위에 영향을 받는 것으로 보인다.
Table 3은 조기 재계획 기법 유무에 따른 시뮬레이션 결과를 나타낸다.
Table 3.
Simulation result – without early replanning
| Open | Maze 1 | Maze 2 | |
|---|---|---|---|
| w/o replanning | 8 / 180 | 14 / 793 | 17 / 597 |
| w/ replanning | 9 / 187 | 19 / 551 | 20 / 520 |
시험 결과, 조기 재계획을 적용했을 때 각 군집의 거동에는 큰 변화가 없지만, 전체 임무 계획 횟수는 소폭 증가하고 탐사 시간은 평균 13 % 감소하는 것을 확인하였다. 다만, Open 맵에서 예외적으로 임무 계획 횟수와 탐사 시간 모두 소폭 증가하였는데, 이는 탐사가 거의 완료된 시점에서 한 그룹이 남은 frontier point를 방문하는 것을 나머지 그룹이 긴 시간 대기했기 때문으로 보인다.
5. 결 론
본 연구에서는 다수의 군집 로봇을 활용하여 미지의 임무 공간을 탐사하는 분산화된 임무 계획 알고리즘을 제안하였다. Frontier exploration 알고리즘을 기반으로, 임무 공간상의 탐색 영역을 분할하고 frontier clustering을 통해 경로점을 선택하여 그룹 간, 그룹 내의 협업을 모두 고려할 수 있게 하였다. 제안한 알고리즘의 성능을 검증하기 위해 세 개의 시험 환경을 탐사하는 시뮬레이션을 진행하였다. 시뮬레이션 결과, 제안한 알고리즘은 적절한 탐사 성능을 보였으며 임무 계획 분산화를 통해 연산 및 통신 부담을 줄일 수 있을 것으로 기대된다.
PDF Links
PubReader
ePub Link
Full text via DOI
Download Citation
