무인 로봇의 자율성이 증대됨에 따라, 단일 로봇 시스템이 아닌 군집 로봇 시스템의 활용도도 같이 증대되고 있다. 군집 로봇 시스템은 물류 이동 자동화^[1], 감시 정찰^[2], 탐색 및 구조 임무^[3,4] 등 다양한 분야에 사용되고 있다.

이러한 군집 로봇 시스템을 적용하는데 있어 대표적인 분야는 미지 영역 탐사 임무이다. 미지 영역 탐사 임무는 재난 현장에서의 구조 임무를 수행하거나^[4], 외계 행성 탐사^[5], 극지방 탐사^[6] 등에서 사용된다. 사람이 직접 접근하기 어려운 지역이거나 접근했을 때 위험이 있는 지역의 경우 군집 로봇 시스템을 이용하여 영역을 탐사하는 것이 필요하다.

미지 영역 탐사 임무에 적용되는 대표적인 방법론은 프론티어 기반 탐색 기법이다. 프론티어란 라이다와 같은 센서를 이용하여 맵을 생성했을 때 탐사된 영역과 탐사되지 않은 영역 사이의 경계를 의미한다. 프론티어 기반 탐색은 로봇들이 프론티어를 방문함으로써 미탐색 영역에 대한 많은 정보를 얻을 수 있고, 이를 통해 효율적인 탐사를 가능하게 하는 기법이다. 초기에 제안된 연구^[7]에서 군집 로봇 시스템을 대상으로 제안되었고, 군집 로봇 간 지도를 공유하지 않고 프론티어 위치만을 공유해서 통신량을 최소화한 연구^[8]도 수행되었다.

실제 미지 영역 탐사 임무는 로봇 간 통신 대역이 제한된 상황에서 수행하는 경우가 많다. 또한 각 로봇에서 취득한 지역 정보를 취합하는 데에도 많은 자원과 시간이 필요하다. 이러한 지도 융합 및 통신 과정에서 발생하는 시간 지연으로 인해 실시간으로 정보를 취합하고, 취합된 전역 정보를 공유하는 데에는 어려움이 있다. 이에 통신이 제한된 상황에서 위상지도를 활용한 다중 로봇 탐사 기법이 제안되었으나^[9,10], 실제 지도를 위상지도로 변환하는 과정에서 유실되는 정보가 있어 임무 공간의 완전한 탐사를 보장할 수 없다는 한계가 있다. 이렇듯 전역 정보가 제한된 상황에서 가용한 정보를 활용해 그룹 단위의 분산화된 의사 결정을 수행하고 전체 영역에 대한 탐사 효율을 높이는 기법이 필요하다.

본 연구에서는 ‘GCS - 그룹 리더 - 그룹 구성원’ 으로 계층화된 군집 로봇 시스템을 가정하였다. GCS에서는 각 구성원들이 얻은 지도를 융합하고, 융합된 지도를 각 그룹의 리더에게 배포한다. GCS가 지도 융합 및 배포를 수행하는 구조를 가정하여, 개별 로봇의 연산 능력이 제한된 상황에서의 활용을 상정하였다. 그룹 리더는 가지고 있는 지도 정보와 다른 그룹의 위치 정보를 활용하여 그룹 구성원들이 가야할 영역을 도출하는 역할 및 그룹 구성원이 취득한 새로운 지도 정보를 GCS로 보내는 역할을 수행한다. 할당된 영역으로 가서 탐사를 수행하는 것은 그룹 리더와 그룹 구성원이 동일하게 수행한다.

본 논문에서는 실시간 전역 정보가 제한되어 가용한 전역 정보에 지연이 발생하는 상황에서 군집 로봇 시스템이 미지의 영역을 효율적으로 탐사하기 위한 임무계획 기법을 제안하였다. 제안된 알고리즘을 통 해 세 가지 임무 공간에 대한 지도 작성 시뮬레이션을 수행하였다. 제안된 알고리즘의 성능을 분석하기 위해 베이스라인 알고리즘과 임무계획 성능을 비교하였다. 시뮬레이션 결과, 제안된 기법을 통해 실시간 전역 정보가 제한된 상황에서도 그룹 간 협업을 고려한 임무계획이 가능한 것을 확인하였으며, 임무계획 성능이 향상됨을 확인하였다. 베이스라인 알고리즘에 대한 자세한 설명은 4장에서 기술한다.

2장에서는 본 논문에서 풀고자 하는 문제를 상세하게 정의하고, 3장에서는 분산화 된 군집 로봇 시스템을 위한 임무계획 기법을 제안한다. 그리고 4장에서 시뮬레이션 결과를 분석한다. 5장에서 결론을 통해 본 논문을 마무리한다.

본 논문은 2차원 격자로 표현되는 미지의 임무 공간을 군집 로봇을 통해 탐사하고, 지도를 작성하는 문제를 다룬다. 이 때, 각 로봇은 임무 공간의 크기를 포함한 어떠한 사전 정보도 가지고 있지 않다고 가정하였다. 본 논문에서 제안하는 알고리즘은 군집 로봇이 효율적으로 임무 공간을 탐사하고 지도를 작성하기 위해 로봇 간의 협업을 고려한 임무계획을 수행하는 것을 목표로 한다.

본 연구에서는 군집 로봇들이 그룹을 형성하고, ‘GCS – 그룹 리더 – 그룹 구성원’ 으로 계층화된 군집 로봇 시스템을 가정하였다. 중앙집중형 임무계획 기법은 취합된 지도 정보와 모든 로봇의 위치를 바탕으로 임무 공간을 분할하고 탐색 영역을 할당할 수 있으므로 로봇 간의 협업 측면에서 분산형 임무계획에 비해 높은 효율성을 가진다. 그러나 이러한 방법을 사용하면 GCS의 연산량이 많아지고, 모든 로봇과 GCS가 연결되어야 하므로 통신 부담이 커진다는 문제가 있다. 따라서 계층화된 군집 로봇 시스템을 가정하고, 그룹 리더가 분산 임무계획을 수행하는 구조를 통해 높은 확장성을 가지는 알고리즘을 제안하고자 한다. 계층화된 군집 로봇 시스템에서 각 계층이 주고받는 정보는 [Fig. 1]과 같다.

[Fig. 1] 
Communicated information between GCS, group leaders, and followers

군집 로봇이 취득하는 지도 정보의 정밀도가 높을수록 이를 전달하고 융합하는데 걸리는 시간 또한 커지게 된다. 이렇듯 실제 운용 환경에서 지도 정보의 통신 및 융합 과정에서 지연이 발생하므로, 그룹 리더가 군집 임무계획을 할 때 실시간으로 업데이트 된 전역 정보를 활용하기는 매우 어렵다. 본 연구에서는 임무계획에 가용한 전역 정보에 시간 지연이 발생하는 상황에서 분산 임무계획 문제를 다룬다.

통신 및 지도 융합에서 발생하는 지연은 다음과 같이 모델링되었다. 먼저 각 그룹은 모두 동일한 시점에 임무계획을 수행한다고 가정하였다. 이 때 통신 및 지도 융합에 그룹 임무계획 주기와 같은 시간이 필요하다고 가정하였다. 즉, 그룹 리더가 임무 계획을 수행할 때, 직전 임무계획 시점에서의 전역 정보와 임무계획 사이에 취득된 지역 정보를 활용 가능하다고 할 수 있다. 이러한 통신 지연 모델은 [Fig. 2]와 같이 나타낼 수 있다.

[Fig. 2] 
Map fusion and communication delay model: The system has same amount of time delay as the mission planning interval. Global map fusion occurs after each planning, and fused global map is available at the next planning round. Group leaders perform mission planning by using previous global information (orange) and new local information gathered between planning rounds (blue)

본 논문에서 그룹 리더를 포함한 모든 군집 로봇의 탐색 및 이동 성능은 서로 동일하다고 가정하였다. 또한 군집 로봇의 위치에 대한 정확한 추정이 가능하다고 가정하였으며, 지도 작성 과정에서 발생하는 불확실성에 대해서는 고려하지 않았다. 마지막으로 임무계획 과정에서 모든 군집 로봇의 상태 정보는 실시간으로 공유된다고 가정하였다.

본 논문에서 제안한 알고리즘의 성능을 검증하기 위하여 Python 환경에서 구성된 미지의 임무 공간에 대한 탐사 및 지도 작성 시뮬레이션을 수행하였다. 시뮬레이션에 사용된 임무 공간은 다음과 같다.

[Fig. 4] ~ [Fig. 6]에서 빨간색 X표시는 임무 시작 당시의 군집 로봇의 위치를 나타낸다. 군집 로봇이 수송 로봇을 통해 운반되어 지도 작성 임무를 수행하는 상황을 상정하여, 임무 시작 시점에서 모든 군집 로봇이 동일한 위치에서 출발한다고 가정하였다. 시험 공간 1은 개방된 공간을, 시험 공간 2와 3은 작은 방이 미로와 같은 형식으로 연결되어 있는 공간이며, 시험 공간 1에서 3까지 점차 공간의 복잡도가 높아지는 상황에서 임무계획 알고리즘의 성능을 확인하고자 하였다.

[Fig. 4] 
Test map 1 (open space)

[Fig. 5] 
Test map 2 (maze 1)

[Fig. 6] 
Test map 3 (maze 2)

시뮬레이션에 사용된 문제 및 센서 파라미터는 [Table 1]과 같다.

알고리즘의 성능을 평가하는 기준으로는 주어진 임무 공간을 모두 탐사하는데 걸리는 시간(시뮬레이션 상의 step수)과 탐사 완료까지 필요한 임무계획의 횟수를 사용하였다.

전역 정보 업데이트에 지연이 있는 상황에서 제안한 알고리즘이 적절하게 작동하는 것을 검증하기 위하여 시뮬레이션 결과를 베이스라인 알고리즘과 비교하였다. 베이스라인 알고리즘은 3.3절에서 제안한 그룹 프론티어의 개념이 없는 상황에서 제한된 전역 정보만을 활용하여 분산 임무계획을 수행한다. 프론티어 분할 및 군집화 기반의 탐사 방식은 본 연구에서 제안한 알고리즘과 동일하게 작동한다. 베이스라인 알고리즘과의 비교를 통해, 전역 정보에 지연이 발생하는 상황에서 그룹 프론티어를 활용함으로써 임무계획 성능을 얼마나 개선할 수 있는가에 초점을 맞추었다.

시뮬레이션 결과 각 임무 공간에서 지도 작성 완료 시점까지 그룹의 리더가 움직인 경로를 나타내면 [Fig. 7] ~ [Fig. 9]과 같다.

[Fig. 7] 
Group leader path plot (open space)

[Fig. 8] 
Group leader path plot (maze1)

[Fig. 9] 
Group leader path plot (maze2)

그림에서 빨간색 점선은 군집 로봇의 출발 위치를 의미한다. 시뮬레이션 결과, 각 그룹이 전체 임무 공간을 분할하여 서로 협력하며 지도 작성을 수행함을 확인할 수 있다.

[Fig. 10]은 maze2 임무 공간의 지도 작성 중 그룹 프론티어가 발생하는 상황을 나타낸다. 그림에서 세 가지 색상은 각 그룹의 군집 로봇과 해당 그룹의 그룹 프론티어를 나타낸다. 그림의 상황에서 초록색과 주황색 그룹은 발견한 그룹 프론티어가 있으므로 해당 프론티어를 탐색하기 위해 그룹 내에서 임무를 할당하여 이동한다. 파란색 그룹은 그룹 프론티어가 없으므로 전역 프론티어 요소 중 가장 가까운 요소를 선택하여 이동하게 된다(이 경우 아래 방향으로 이동). 시뮬레이션 결과, 이처럼 예상한 것과 같은 거동을 보여주었으며 지도 작성 과정에서 그룹 간 협업이 잘 이루어짐을 확인하였다.

[Fig. 10] 
Example of group frontier points during mapping

세 가지 시험 환경에서의 시뮬레이션 결과 지도 작성에 걸리는 총 시간과 필요한 임무계획의 횟수는 [Table 2]와 같다.

시뮬레이션 결과 모든 시험 공간에서 탐사가 정상적으로 이루어졌으며, 그 과정에서 그룹 간, 그룹 내에서의 군집 로봇의 협업이 고려되는 것을 확인하였다. 제안한 알고리즘은 베이스라인과 비교했을 때, 평균적으로 29.45% 빠른 탐사 속도를 보여주었다(시험 공간 별 각각 16.82, 57.19, 14.35%). 제안한 알고리즘이 Maze1에서 다른 시험 공간에 비해 큰 성능 향상을 보인 이유는 베이스라인 알고리즘에서 나타난 일부 비효율적인 움직임 때문으로 보인다. 베이스라인 알고리즘의 시뮬레이션에서 소규모 미탐사 구역이 발생하여, 이를 탐사하기 위해 군집 로봇이 되돌아오는 과정에서 많은 시간이 낭비된 것을 확인하였다. 즉, Maze1의 시뮬레이션 결과는 3.3.1절에서 설명한 매커니즘이 효과적으로 작동한 사례라 할 수 있다.

임무계획 횟수의 경우 베이스라인과 비교했을 때, 평균 36.36% 감소한 것을 확인하였다(각각 35.71, 45.16, 28.2%). 전체 탐사 시간과 유사하게, 그룹 프론티어를 활용함으로써 전체 탐사 효율이 증가하고 불필요한 움직임이 줄어들어 필요한 임무계획 횟수 또한 감소한다고 할 수 있다.

종합적으로, 제안한 알고리즘을 통해 전역 정보에 지연이 있는 상황에서 그룹 간의 협업을 고려한 탐사 및 지도 작성을 위한 임무계획이 가능함을 확인하였다. 베이스라인 알고리즘과 비교했을 때, 그룹 프론티어를 활용함으로써 탐사 성능을 개선할 수 있음을 확인하였다.

본 논문에서는 다수의 군집 로봇을 활용하여 미지의 임무 공간을 탐사하는 상황에서 분산 임무계획 알고리즘을 제안하였다. 이 때 실제 알고리즘 적용시 흔히 발생하는 지도 융합/통신 제한으로 인한 전역 정보의 지연을 모델링하고, 이를 고려한 임무계획을 수행하였다. 전역 정보와 지역 정보의 차이를 기반으로 그룹 프론티어라는 개념을 정의하고, 이를 통해 실시간 전역 정보가 없더라도 서로 다른 그룹이 전체 시스템의 효율을 높이기 위해 협업할 수 있도록 하였다. 제안한 알고리즘의 성능을 검증하기 위해 세 개의 미지의 임무 공간을 탐사하는 시뮬레이션을 수행하였다. 그 결과, 전역 정보가 제한된 상황에서도 적절한 협업 및 탐사 성능을 보여주었다.