2.1 문제 정의

다중 로봇 SLAM에서 지도병합 문제는 시스템 구성에 다라 달라질 수 있다. 본 논문에서는 2차원 LiDAR(Laser Imaging Detection And Ranging) 기반 다중 로봇 SLAM에서 격자 지도 병합 문제를 다룬다. 2차원 환경에서 다중 로봇 SLAM에서 지도 병합 문제는 아래 수식과 같이 개별 지도 간 변환 행렬(transformation matrix)⁽³⁾을 획득하는 것으로 정의될 수 있다.

여기서 $\triangle x$,$\triangle y$,$\triangle\theta$는 각각 지도 간 상대적인 $x$축 방향 이동량, $y$축 방향 이동량, 회전각도을 나타낸다.

2.2 관련 연구

지도 병합 기술은 표 1과 같이 크게 직접적 지도 병합 기술과 간접적 지도 병합 기술로 나눌 수 있다. 직접적 지도 병합 기술은 다중 로봇 시스템 구성 요소를 활용하는 것으로서, 공통 객체 기반 지도 병합, 로봇 간 관측 정보 기반 지도 병합 기술 등이 있다. 간접적 지도 병합 기술은 다중 로봇 시스템 구성 요소의 도움 없이 지도 간 매칭을 통해 지도 병합을 수행하는 것으로서, 특징점 매칭 기반 지도 병합, 스캔 매칭 기반 지도 병합, 스펙트럼 매칭 기반 지도 병합 기술 등이 있다. 각 지도 병합 기술은 다음과 같은 제한점을 갖고 있다.

먼저, 직접적 지도 병합 기술에서 로봇 관측 정보 기반 지도 병합 기술의 경우, 로봇 간 랑데부(rendezvous) 지점의 설정이 필요한데 이는 다중 로봇 시스템의 운용 자유도를 떨어뜨린다. 또한 지도 병합의 정확도가 로봇 센서의 정확도에 의존적일 수 밖에 없다. 그리고 공통 객체 기반 지도 병합 기술의 경우, 공통 객체의 종류 및 개수 설정에 대한 고려가 필요한데 이는 제한된 시스템 운용을 초래할 수 있다. 또한 지도 병합의 정확도가 영상 처리 성능에 의존적이게 된다. 그리고 간접적 지도 병합 기술에서 특징점 기반 지도 병합 기술의 경우, 과도한 계산 시간이 요구된다. 또한 지도 병합의 정확도가 데이터 연관성(data association) 문제의 영향을 받게 된다. 스캔 매칭 기반 지도 병합 기술의 경우, 과도한 계산 시간이 요구되고 충분한 오버랩(overlap) 영역이 요구된다는 제한점이 있다. 또한 스캔과 지도의 특성 차이로 인한 정확도 저하가 발생하게 된다. 스펙트럼 기반 지도 병합 기술의 경우, 충분한 오버랩(overlap) 영역이 확보되면 높은 정확도를 나타내지만, 그렇지 않을 경우 지역 국소점(local minima)에 빠질 수 있다는 제한점이 있다.

본 논문에서는 간접적 지도 병합에서 위와 같은 제한점을 극복하고 지도 병합의 정확도를 높이기 위해, 스펙트럼 기반 PSO 기법을 이용한 지도 병합 기법을 제안한다. 제안된 기법은 실제 환경에서 획득된 데이터를 이용하여 성공적으로 수행되었고, 기존 지도 병합 기법 대비 높은 정확도를 나타내었다.

3.1 격자 지도 이진화

2차원 격자 지도는 LIDAR 기반 SLAM 기술에 의해 그림 3과 같이 획득될 수 있다. 지도 간 회전각도 및 축 방향 이동량 추정을 위한 효율적 스펙트럼 추출을 위해, 격자 지도를 그림 4와 같은 이진(binary) 격자 지도로 변환하는 전처리 과정을 거친다. 각 격자의 값이 특정 기준값 이상인 경우에는 점유된(occupied) 격자로, 기준값 이하인 경우에는 비점유된(unoccupied) 격자로 처리한다.

3.2 지도 간 회전각도 추정

2차원 이진 격자 지도는 하나의 이진 이미지로 간주될 수 있다. 격자 지도에 표현된 구조물들의 공통적인 방향을 매칭하면 지도 간 회전각도를 추정할 수 있다. 구조물의 방향을 추출하기 위해 Discrete Hough Transform(DHT)⁽¹⁴⁾을 이용하여 직교좌표계 격자 지도 $M_{C}(x,\: y)$를 극좌표계 격자 지도 $M_{P}(\rho ,\:\theta)$로 표현한다. 그리고 다음과 같이 정의되는 Hough 스펙트럼(spectrum)을 계산한다.

여기서 $1^{\circ}\le\theta\le 360^{\circ}$, $1\le\rho\le\rho_{M}$. $\rho_{M}$은 $M_{P}$에서 행의 개수를 나타낸다. 2대의 로봇들로 구성된 군집 로봇 시스템을 가정하면, 로봇 1의 지도($M_{P,\:1}$)에 대한 스펙트럼 $S_{H,\:1}$과 로봇 2의 지도($M_{P,\:2}$)에 대한 스펙트럼 $S_{H,\:2}$에 대해, 다음과 같이 교차상관관계(cross-correlation)을 계산한다.

여기서 $\theta$의 해상도(resolution)는 1°이다. 그림 4의 이진 격자 지도에 대한 Hough 스펙트럼 및 교차상관관계는 그림 5와 같다. 각 수치는 정규화된 수치이다. 지도 간 각도 $\phi$는 다음과 같이 최대 교차상관관계를 나타내는 각도값으로 얻는다.

여기서 교차상관관계의 최대값은 180°를 주기로 나타나기 때문에 최대값 역시 두 군데 나타나지만, 둘 중 하나는 잘못된 추정값이다. 본 논문에서는 지도 간 회전은 180° 미만이라는 가정을 두고, $0^{\circ}\le k\le 179^{\circ}$로 설정하였다.

3.3 지도 간 축 방향 이동량 추정

이제, X 및 Y 방향으로의 상대 위치 차이를 얻기 위해, 먼저 $M_{P,\:2}$을 $\triangle\theta$만큼 회전시켜서 $\overparen{M}_{P, 2}$ 를 획득한다. 그리고 두 지도에 대한 X축 방향 스펙트럼을 다음과 같이 추출한다.

여기서 r은 지도를 이미지로 간주했을 때의 행의 개수로서, Y축 방향 격자의 개수와 동일하다. 본 논문에서 한 격자의 크기는 5cm로 설정되었다. 다음으로 Y축 방향 스펙트럼을 다음과 같이 추출한다.

여기서 c는 지도를 이미지로 간주했을 때의 열의 개수로서, X축 방향 격자의 개수와 동일하다.

위의 X 및 Y 방향으로의 스펙트럼을 이용하여 교차상관관계를 다음과 같이 계산한다.

그림 4의 이진 격자 지도에 대한 X축 및 Y축 방향 스펙트럼 및 교차상관관계는 각각 그림 6및 그림 7과 같다. 각 수치는 정규화된 수치이다. 교차상관관계에서 가장 높은 값을 나타내는 부분이 지도 간 X, Y 방향으로의 차이이므로, 다음과 같이 변환량 $\triangle x$ 및 $\triangle y$를 얻는다.

3.4 PSO 기반 최적화

PSO⁽¹⁾는 군집 지능 개념을 활용한 표본 추출 기반 최적화 알고리즘 중 하나이다. 목적 함수가 비선형적이라도 적용 가능하고 구현이 간편하기 때문에 다양한 분야에 적용되어 왔다. 격자 지도 병합에 PSO를 적용하기 위해서는 먼저 목적 함수(objective function)을 정의해야 한다. 본 연구에서는 지도 간 유사성(similarity)을 반영할 수 있는 다음과 같은 수식으로 목적 함수를 정의하였다.

여기서 r과 c는 지도를 이미지로 간주시 행과 열의 개수이고, 실험 환경의 크기 및 지도 변환 결과에 따라 달라진다. $T_{PSO}$는 PSO 표본추출 과정에서 획득한 후보 지도 변환 행렬이다.

각 파티클은 지도 간 X축 및 Y축 방향 이동량과 지도 간 회전각도를 나타낼 수 있도록, $p_{n}=[x_{n},\: y_{n},\:\theta_{n}]$으로 정의되었다. PSO는 탐색 공간 내에서 파티클들을 추출하고 해당 파티클의 품질(quality)를 수식(12)를 이용하여 평가한다. 파티클 군집은 세대(epoch)를 거치면서 최적점을 찾아가게 되는데, 각 세대에서 가장 높은 평가를 받는 파티클을 Swarm Best $p_{SB}$라 하고, 각 파티클이 세대를 거치면서 가장 높은 평가를 받았던 지점을 Personal Best $p_{PB}$라 한다. $p_{SB}$와 $p_{PB}$은 매 세대에서 파티클들이 최적점을 찾아가는 수렴 과정에서 중요한 역할을 한다. 매 세대에서 파티클들의 업데이트는 다음과 같이 진행된다. 각 파티클은 다음과 같이 업데이트된다.

여기서 $\kappa$ 및 $\epsilon$는 각각 관성 및 마찰 파라미터이다. 전체적인 알고리즘은 표 2와 같다.

4.1 실험 환경

격자 지도 획득을 위해 사용된 로봇 및 센서 시스템 구성은 다음과 같았다. 로봇은 OMOROBOT 사의 R1 모델이었고, 2D LIDAR 센서는 SLAMTEC 사의 RPLIDAR였다. 격자 지도 획득은 ROS(Robot Operating System) Melodic 기반 Google Cartographer ⁽¹⁶⁾ 알고리즘을 기반으로 수행되었다.

실험은 건물 실내 2가지 환경에서 수행되었다. 두 환경에 대해 획득한 지도는 각각 그림 8및 그림 10과 같았다. 흰색 부분이 빈 공간이고, 검정색 부분이 구조물이 있는 공간이며, 회색 부분은 아직 센서 범위가 닿지 않은 공간을 의미한다. 첫 번째 환경에서 획득된 지도들은 중첩 영역이 비교적 많은 편이었고, 두 번째 환경에서 획득된 지도들은 중첩 영역이 상대적으로 적은 편이었다. 각 실험에서 획득된 두 격자 지도들을 정확하게 병합하기 위해 제안된 기법을 적용하였다.

4.2 지도 병합 결과

본 논문에서 제안된 기법을 적용하기 위해, 먼저 획득된 격자 지도를 이진화하는 전처리 과정을 수행하였다. 그 결과는 그림 9및 그림 11과 같이 구조물에 해당되는 격자들만 남게 된다. 전처리된 이진 격자 지도들로부터 스펙트럼을 추출하고, 추출된 스펙트럼 간 계산된 교차상관관계는 그림 12및 그림 15와 같았다. 모든 수치는 정규화된(normalized) 수치이다.

첫 번째 환경에서는 가장 높은 교차상관관계를 나타내는 각도인 9도가 지도 간 회전각도로 추정되었다. 두 번째 환경에서는 가장 높은 교차상관관계를 나타내는 각도인 99도가 지도 간 회전각도로 추정되었다. 추정된 회전각도를 이용하여 두 번째 지도를 회전시킨 후, 다시 X축 및 Y축 방향 스펙트럼을 추출하고, 추출된 스펙트럼 간 계산된 교차상관관계는 각각 그림 13및 그림 14그리고 그림 15및 그림 16과 같다. 각도 추정과 마찬가지로 가장 높은 교차상관관계를 나타내는 X축 및 Y축 지점들이 해당 축 방향 이동량으로 추정된다.

획득된 지도 간 회전각도, X축 및 Y축 방향 이동량을 스펙트럼 정보와 PSO를 이용하여 지도 병합을 수행한, 제안된 기법 기반 지도병합 결과는 그림 18및 그림 19와 같다. 식(13)의 r과 c는 첫 번째 실험에서는 각각 1390 및 908이었고, 첫 번째 실험에서는 각각 1577 및 891이었다.

녹색으로 표현된 Map 2가 알고리즘에 의해 변환된 것이 빨간색으로 표현된 Transformed Map 2이다. 파란색으로 표현된 Map 1과 Transformed Map 2가 최대한 겹쳐져야 지도 병합이 성공적으로 수행된 것이라 할 수 있다. 따라서 본 논문에서 제안한 기법이 성공적으로 지도병합을 수행했음을 알 수 있다. 제안된 기법 수행시 PSO의 수행 결과는 그림 20과 같았다. 표현상 편의를 위해 X축 및 Y축 방향 이동량에 대한 수렴 결과만을 표시하였다. 최종 수렴된 파티클들의 위치 중에서 최종 Swarm Best $p_{SB}$를 최적 값으로 획득하여 적용하였다.

제안된 기법의 향상된 성능을 검토하기 위해 기존 방법들과 비교하였다. 비교 대상은 표 1에서 간접적 지도 병합 기법 중에서 기존 스펙트럼 기반 지도 병합 기법(SMM)⁽¹³⁾을 비롯하여 이미지 매칭 기법들 중 일부로 다음과 같이 설정하였다. 특징점 매칭 기법(SURF: Speeded Up Robust Features)⁽¹⁷⁾, 모서리 매칭 기법(HCD: Harris Corner Detector)⁽¹⁸⁾, 평균제곱오차(MSE: Mean Square Error) 기반 매칭 기법을 지도 병합에 적용하여 비교하였다. 기존 방법들에 의한 지도병합 결과는 그림 21및 그림 22와 같았다.

스펙트럼 정보만을 이용하는 SMM은 지도 병합을 성공적으로 수행되지 못했음을 알 수 있었다. 지도 간 회전 각도는 성공적으로 추정하였으나, 축 방향 이동량에 대한 추정 정확도는 낮았다. 이는 중첩(overlapped) 영역이 부족하여 알고리즘이 국소 최저점에 빠졌기 때문이다. SURF 기반 지도병합의 경우, 지도 간 중첩영역이 상대적으로 충분한 첫 번째 환경에서는 잘 동작하였으나, 중첩영역이 상대적으로 부족한 두 번째 환경에서는 정확도가 현저하게 떨어졌다. 이는 매칭에 필요한 공통 특징점의 개수가 적었기 때문이다. HCD 기반 지도병합 방법은 공통 코너 특징점의 개수가 적었기 때문에 두 환경 모두에서 낮은 지도병합 정확도를 나타내었다. MSE 기반 지도병합 방법 역시 중첩 영역의 부족으로 두 환경 모두에 대해 낮은 지도병합 정확도를 나타내었다.

4.3 정량적 비교 결과

격자 지도 병합의 정확도 비교를 위해 중첩 격자의 개수를 다음과 같이 매칭 점수(score)로 설정하여 정량적 비교를 수행하였다.

여기서 $X_{\max}$과 $Y_{\max}$는 각각 두 지도의 점유 격자들의 X축 및 Y축 좌표들 중에서 가장 큰 값들이다. 두 환경에 대한 정량적 비교 결과는 표 3 및 표 4와 같이 요약되었고, 각 결과는 10회 평균값이다. 정량적 비교 결과 제안된 기법이 가장 높은 정확도를 나타내었다. 특히, 중첩 영역이 상대적으로 부족했던 두 번째 환경에서도 기존 기법들보다 높은 매칭 점수를 나타냄으로써 정확한 지도병합을 수행할 수 있음을 보여주었다. 단, PSO에 사용되는 파티클 개수와 반복 횟수에 따라 계산 시간이 증가하기 때문에, 실제 시스템 적용시 요구사항에 따른 적절한 파라미터 설정이 필요하다.

4.4 3대 이상의 로봇 지도 병합 결과

다중 로봇 SLAM을 위한 지도병합과 관련한 대부분의 기존 연구에서 지도 간 매칭은 2개씩 이루어졌다. 예를 들어, 3대의 로봇을 이용한 SLAM의 경우, 먼저 첫 번째 로봇 지도와 두 번째 로봇 지도 간 매칭을 수행하여 지도 간 변환행렬을 추정한다. 그리고 나서 두 번째 로봇 지도와 세 번째 로봇 지도 간 매칭을 수행하여 지도 간 변환 행렬을 추정한다. 이렇게 순차적으로 추정된 변환 행렬들을 순차적으로 적용하여 전체 병합 지도를 획득한다.

본 연구에서 제안된 기법도 이와 같은 방법으로 3대 이상의 로봇 지도 병합에 적용될 수 있다. 두 번째 환경에서 제안된 기법을 이용한 두 번째 로봇 지도와 세 번째 로봇 지도의 병합 결과는 그림 23과 같았다. 여기서 추정된 변환 행렬을 앞서 추정된 변환 행렬과 함께 순차적으로 적용함으로써 전체 지도 병합 결과를 그림 24과 같이 획득하였다. 제안된 기법에 의해 3대의 로봇 지도들이 성공적으로 병합되었음을 알 수 있다.