Data Association of Robot Localization and Mapping Using Partial Compatibility Test

(1)

Partial Compatibility Test 를 이용한 로봇의 위치 추정 및 매핑의 Data Association

염서군¹, 최윤성², 무경¹, 한창수^3,

Rui Jun Yan¹, Youn Sung Choi², Jing Wu¹, and Chang Soo Han^3,

1 한양대학교 메카트로닉스공학과 (Department of Mechatronics Engineering, Hanyang University) 2 한양대학교 기계공학과 (Department of Mechanical Engineering, Hanyang University) 3 한양대학교 로봇공학과 (Department of Robot Engineering, Hanyang University)

Corresponding author: [email protected], Tel: +82-31-400-4062 Manuscript received: 2014.11.18. / Revised: 2015.11.8. / Accepted: 2015.11.27.

This paper presents a natural corners-based SLAM (Simultaneous Localization and Mapping) with a robust data association algorithm in a real unknown environment. Corners are extracted from raw laser sensor data, which are chosen as landmarks for correcting the pose of mobile robot and building the map. In the proposed data association method, the extracted corners in every step are separated into several groups with small numbers of corners. In each group, local best matching vector between new corners and stored ones is found by joint compatibility, while nearest feature for every new corner is checked by individual compatibility. All these groups with local best matching vector and nearest feature candidate of each new corner are combined by partial compatibility with linear matching time. Finally, SLAM experiment results in an indoor environment based on the extracted corners show good robustness and low computation complexity of the proposed algorithms in comparison with existing methods.

KEYWORDS: SLAM (로봇의 위치 추정 및 매핑), Partial compatibility test (부분 호환 테스트), Data association (자료 연관), Partial compatibility branch and bound (부분 호환 분기 한정법), Nearest unit-matching branch and bound (최단 유닛 매칭 분기 한정법)

1. 서론

SLAM(Simultaneous Localization And Mapping)은 이동 로봇의 위치를 추정하면서 동시에 환경에서 추출한 특징점을 이용하여 미지 환경 지도를 작성 하는 기술이다. 새로운 센서 관측(sensor observation) 을 지도에 저장된 특징점(features)과 정확하게 관련

시키기 위해 자료 연관(data association)을 탐색 문제 (search problem)로 이용한다. 본 논문은 자연적 특징 점(natural features) 추출 및 자료 연관 문제를 다룬다.

환경 특징점의 기하학적 모양은 로봇 위치 추정, 주 행, 인지, 지도 작성에 중요한 역할을 한다. 로봇의 위치 추정 및 지도 작성을 위해 레이저 센서 혹은 비전 센서를 이용한 대부분의 실험은 컵¹이나 녹색 __________

This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

(2)

한국정밀공학회지 제 33 권 제 2 호 pp. 129-138 February 2016 / 130

원²과 같은 다양한 인공 표식(landmarks)^3-6을 이용 한다. 이동 로봇의 위치를 보정하기 위해 표식을 이 용하는 이유는 오도메트리(odometry)만 이용할 경 우 정확도가 떨어지기 때문이다.

하지만 인공 표식은 매우 드물게 적용되고 있다.

사람이 갈 수 없는 곳에는 인공 표식을 위치시킬 수 없어 활용성이 떨어지기 때문에 실제 미지 환경 에서의 자연 특징점을 이용하는 방법을 주로 이용 한다. 본 논문에서는 로봇의 위치 추정 및 지도 작 성을 위해 미지 환경의 자연적 모서리(natural corners) 를 추출하고 이를 표식으로 이용한다. 본 연구에 서 Hokuyo 레이저 센서와 Pioneer 이동 로봇을 이 용하여 얻은 원(raw) 데이터로부터 라인 세그먼트 를 추출하며 이를 모서리 추출의 기반(basis)으로 한다. 기존의 다른 연구에서는 가장 빠르고 정확 한 방법을 찾기 위해 다양한 라인 추출 방법을 비 교하였는데, 분석 결과로 Split-and-Merge와 Incremental methods가 가장 좋은 성능을 가진 것으로 보여준 다.⁷ 라인 세그먼트 또한 SLAM을 구현하기 위해 자주 사용되는 특징점 중에 하나이다.⁸

본 논문은 라인 세그먼트 추출을 구현하기 위 해 modified Split-and-Merge를 이용하며 추출된 모 서리의 불확실성 계산은 논문⁹의 라인 불확실성 계산 방법을 이용하였다. 이전 연구¹⁰에서 보인 다 른 세그먼트와 떨어져있는 라인 세그먼트의 양끝 포인트와 라인 세그먼트의 교차점을 이용하여 자 연적 모서리를 표식으로 선택하는 모서리 추출 알 고리즘을 제안한다. 새로운 센싱에서 자연적 모서 리를 추출한 후, 이 모서리들은 이전 스텝에서 저 장된 지도 특징점과 매칭되어야 한다. 그러나 대 부분의 연구는 동일한 특징점으로부터 두 개의 측 정값이 나올 수 없다는 가정하에 자료 연관 알고 리즘을 연구해왔다.^11,12

확률론적 매핑으로 많이 쓰는 두 가지 방법이 있다. 하나는 계산 복잡도(computation complexity)가 낮은 ICNN(Individual Compatibility Nearest Neighbor) algorithm^13-15이고 다른 하나는 계산 시간을 많이 소모하지만 자료 연관의 강건성을 높여주는 JCBB (Joint Compatibility Branch and Bound) algorithm¹¹이다.

두 지역적(local) 지도의 중첩을 검출하는 Randomized Joint Compatibility algorithm은 JCBB에 기반하여 개 발되었으며,¹⁶ 이는 large-scale SLAM에 적용되었다.¹⁷ 또한 ICNN과 JCBB는 다양한 SLAM 연구에서 비 교되었다.^18,19 혼잡하고 특징점이 드문 경우 다중 타켓 추적(multi-target tracking)을 위한 MDA (Multi-

Dimensional Assignment) 기반 자료 연관 알고리즘 이 다중 프레임에 대한 측정값의 joint likelihood를 목적 함수로한 센서 불확실성을 이용하여 확장된 다.²⁰ 위의 알고리즘과 달리 SMD(Squared Mahalanobis Distance)를 이용하여 alternative matching likelihood를 최대화 하기도 한다.²¹ 효율적인 integer programming 기반 자료 연관 방법이 SLAM에 적용되기도 하였 다.²²

본 논문의 자료 연관 알고리즘은 검출된 모든 특징점의 joint compatibility를 고려하지 않고 SMD 에 의존한다. 계산 시간을 짧으며 강건한 매칭 결 과를 가지기 위해 각 스텝에서 검출된 특징점을 여러 그룹으로 분리한다. 여기서 각 그룹은 소수 의 특징점을 가진다. 각 그룹에서 ICNN을 이용하 여 각 특징점에 대해 가장 가까운 단위 매칭 쌍 (unit matching pairs)을 찾고, JCBB를 이용하여 최대 단위 매칭 쌍을 포함한 local best matching vector를 찾는다. 분리된 모든 그룹에서 두 가지 형태의 매 칭 결과가 partial compatibility 고려하여 조합된다.

계산 시간을 줄이기 위해 조합 과정에서 Branch and Bound 알고리즘을 이용한다. ICNN와 JCBB를 이용하여 비교하면 제안한 방법이 ICNN을 이용할 때 보다 더 정확한 매칭 결과를 가지고, JCBB를 이용할 때 보다 더 짧은 계산 소모 시간을 가진다.

자세한 비교 결과는 다음 장에서 보여준다.

본 논문은 5장으로 구성되어 있다. 2장에서는 관련된 자료 연관 알고리즘을 보여주고, 3장에서는 새로 제안한 자료 연관 알고리즘을 보여준다. 4장 에서 제안한 알고리즘의 타당성을 증명하기 위해 기존의 방법과 제안한 방법을 이용한 SLAM 실험 비교 결과를 보여준다. 마지막 장은 결론으로 마 무리 짓는다.

2. 관련된 자료 연관 알고리즘

SLAM에서 가장 많이 쓰이는 자료 연관 알고 리즘은 ICNN with individual compatibility과 JCBB with joint compatibility가 있다. ICNN 알고리즘은 다 른 새로운 측정값을 고려하지 않고 Maximum Likelihood 에 기반한 모든 새로운 측정값에 대한 지도 특징 점에 매칭한다. 추정 파트에서 쉽게 발산할 수 있 는 잘못된 매칭을 받아들이기 위해 이 방법에서는 새로운 측정을 독립적으로 고려한다. 매칭 정확도 는 낮지만, 매칭 스텝에서 m개의 새로운 센서 측 정값과 n개의 저장된 지도 특징점이 있다면 ICNN

(3)

은 낮은 계산 복잡도 O(mn)를 장점으로 가진다.

최대 m개의 단위 매칭 쌍을 가지며 그 결과는 Fig.

1의 좌측 상단에서 보여준다. 여기서 단위 매칭 쌍은 오직 한 개의 측정값과 한 개의 저장된 특징 점을 가지며 이의 individual compatibility는 제한 조 건을 만족한다.

반면에 동일한 센싱에서 새로 검출된 측정값의 의존성은 JCBB 알고리즘에서 고려된다. joint compatibility를 체크하고 최적 매칭을 찾기 위해 Branch and Bound method를 이용하고 이의 joint Maximum Likelihood를 계산하여 가능한 전체 단위 매칭을 조합한다. 자료 연관의 강건성이 커지더라 도 측정값과 지도 특징점의 수가 많으면 매칭 스텝 에서 많은 계산 시간이 소모된다. JCBB의 솔루션 공간(solution space)은 (c + 1)^m이고 여기서 c (c < n)는 특징점 후보이다. 그리고 계산 복잡도는 O((1.53)^m) 이다.⁹ JCBB의 해석 트리(interpretation tree)는 Fig. 1의 좌측 하단에서 보여주며 측정값의 수가 증가함에 따라 테스트 매칭 벡터의 차원은 커진다.

이 두 방법은 특징점이 밀집된 환경에서 사용 하기 어렵다. 왜냐하면 ICNN는 매칭 정확도가 낮 고 JCBB는 계산 복잡도가 크기 때문이다. 이러한 단점을 제외하면 ICNN의 선형화된 계산 시간과 JCBB의 강건한 매칭을 결합하여 더 나은 자료 연

관 알고리즘을 구현할 수 있다. 그러나 JCBB를 이 용한 최적 매칭 벡터 모두가 잘 매칭될 수는 없으 며 이는 다음 실험 결과로 증명된다. Joint compatibility 임에도 불구하고 부정확한 단위 매칭의 일부가 매 칭 결과로 포함될 수 있다.

3. PCA (Partial Compatibility Algorithm) 3.1 제안한 방법

ICNN과 JCBB를 이용하여 강건한 매칭 결과를 가지면서 계산 소모 시간이 짧은 Partial compatibility algorithm을 제안한다. 처음에 한 번의 센서 스캔으 로부터 추출된 모든 모서리는 소수의 모서리를 가 지는 서로 다른 그룹으로 분리된다. 확률론적 매 핑에서 소수의 모서리로 형성된 모양(shape)은 변 하지 않고 기하학에서의 삼각형과 같다. 소수이기 때문에 잘못된 단위 매칭 쌍으로 이끌어질 확률은 낮다. 소수의 테스트가 필요하기 때문에 각 소수 그룹에서의 계산시간도 작다. 모든 그룹에서 JCBB 알고리즘은 그룹의 지역적 최적 매칭을 찾기 위해 사용하며, ICNN 알고리즘은 그룹에서의 모든 새로 운 모서리에 가장 가까운 저장된 모서리를 찾기위 해 사용한다.

각 그룹에서 p개의 새로 추출된 모서리가 있다 Fig. 1 Interpretation tree of data association algorithms: ICNN (Left-Top), JCBB (Left-Bottom) and PCA (Right)

(4)

고 가정하자. 최대 1 + p개의 멤버가 있다: ICNN으 로 p개의 가장 가까운 단위 매칭 쌍과 JCBB로 1 개의 지역적 최적 매칭 벡터. 가능한 단위 매칭 쌍 모두와 지역적 최적 매칭 벡터를 얻은 후 그룹 은 큰 그룹으로 통합되며 이의 원리는 Fig. 1의 오 른쪽에서 보여준다. 새로 추출된 전체 모서리 수 가 m이면 그룹의 수는 m / p이다. 각 그룹의 멤버 수는 상수 p + 1과 같거나 이보다 작기 때문에 이 알고리즘은 다수의 저장된 특징점을 새로 추출한 특징점과 매칭할 때도 적합하다. 새로운 모든 특 징점이 JCBB를 이용하여 얻은 저장된 특징점과

매칭되면 해석 트리의 노드 수가 더 커진다. 그러 나 PCA의 경우 소수의 모서리가 포함되며 JCBB 를 이용하면 joint compatibility를 체크하는 계산량 도 작아진다. 다음 장에서 PCA의 pseudo-code와 설명을 보여준다.

PCA의 자세한 과정은 알고리즘 1에서 보여준다.

여기서 저장된 지도 특징점 벡터 ftotal 와 새로운 측정 값 벡터 mtotal, 이 입력(inputs)이며, Vcor 는 추출된 모 서리 벡터이다. 알고리즘의 출력은 partial compatibility 를 가지는 최적 매칭 벡터 HTotalBest 이다. 처음에 새로 검출된 모든 특징점은 서로 다른 그룹으로 분리되다.

그리고 JCBB를 이용한 지역적 최적 매칭 벡터와 ICNN을 이용한 각 새로운 모서리에 대한 가장 가까 운 단위 매칭 벡터가 각 그룹에 저장된다. 가능한 후 보의 ML을 비교하여 쉽게 얻을 수 있는 ICNN을 이 용하여 JCBB에서 모든 단위 매칭의 ML은 가장 가까 운 이웃(neighbor)에 의해 계산된다.

서로 다른 그룹에서의 매칭 쌍을 조합하기 위 해 두 recursive functions을 제안한다. Branch and Bound method를 이용한 Partial Compatibility Branch and Bound (PCBB) 와 Nearest Unit-matching Branch and Bound (NUBB)이며 알고리즘 2와 3에서 보여준 다. 각 그룹에 대해 PCBB를 이용하여 지역적 최 적 매칭 벡터가 처음 얻어지며 NUBB를 이용하여 가장 가까운 단위 매칭을 차례차례 체크한다.

PCBB에서 maximum iteration time은 m / p이다. 각각 의 iteration에 대해 1 + p개의 멤버를 가지는 새로 운 그룹이 임시 최적 매칭 벡터 Hiter 와 조합된다.

Fig. 2 Algorithm 1: Partial compatibility algorithm

Fig. 3 Algorithm 2: Total best matching PCA

Fig. 4 Algorithm 3: Nearest unit-matching branch and bound

(5)

조합 과정에서 차원이 Hiter의 차원보다 작아질 때 이전에 저장된 최적 매칭 벡터 HTotalBest는 Hiter 로 대체된다. 각 그룹에 대한 지역적 매칭 벡터 H 는 처음 테스트되며 만약 이전 테스트가 실패하면 단 위 매칭 쌍이 테스트된다. NUBB에서 단위 매칭 후보가 Hiter와 조합된다. 만약 임시 벡터 Hiter의 차 원이 HTotalBest보다 작아지면 모든 단위 매칭 쌍이 체크된다.

전체 매칭 과정에서는 두 새로운 특징점이 저 장된 동일한 특징점과 매칭될 수 없다고 가정한다.

매칭된 특징점을 현재 매칭 벡터의 특징점과 매칭 되는 지를 매번 체크하기 위해서이다. 충돌 체크 를 하는 이유는 환경에서 실제 특징점에 가까운 특징점이 하나만 존재하는지를 체크하기 위해서이 다. 본 논문에서는 이동 로봇의 위치와 실제 환경 에 대해 저장된 모서리를 보정하기 위해 사용하는

적절한 모서리는 오직 한 개만 존재함을 의미한다.

그리고 알고리즘에서 함수 dim(H)는 현재 매칭 벡 터 H의 단위 매칭 쌍의 수를 말한다.

3.2 PCA 의 계산 복잡도

PCA의 장점 중 하나는 계산량이 작다는 것이 고, 이는 ICNN과 JCBB의 계산량을 이용하여 증명 된다. 동일한 가정은 이전과 같이 설정된다: 새로 운 특징점의 수는 m이고, 지도 특징점의 수는 n이 고, 각 그룹에서 특징점의 수는 p (p << m & p << n) 이다. 모든 그룹에 대해 JCBB 및 ICNN 를 이용한 계산량은 O((1.53)^p + pn)이다. 증명 과정을 간단히 하기 위해 새로운 특징점 모두에 대해 단위 매칭 쌍의 조합 모두를 체크해야 한다고 가정한다. 그 러나 PCA에서 조합의 일부만 체크된다. 체크된 부 분에서 최대 계산량은 차원이 3p이고 행렬 계산

0 5 10 15 20 25 30 35 40 45 50

0 20 40 60 80 100 120 140 160 180 200

p--The number of measuremens in each group

Logarithmic Computation Complexity

The Logarithmic Computation Complexity for two methods

PCA JCBB

0 5 10 15 20 25 30 35 40 45 50

4 6 8 10 12 14 16 18 20 22

PCA JCBB

0 5 10 15 20 25 30 35 40 45 50

4 6 8 10 12 14 16 18 20 22

PCA JCBB

0 5 10 15 20 25 30 35 40 45 50

0 10 20 30 40 50 60 70 80 90 100

PCA JCBB

Fig. 5 Comparison of logarithmic computation complexity of JCBB and PCA (Left-Top: m=50; Right-Top: m=1 00; Left-Bottom: m=500; Right-Bottom: m=1000, n =1000, p=1:50)

(6)

분석에 따른 계산량이 O((3p)³)인 매칭 벡터의 공 분산 행렬 계산에 관한 것이다.

각 그룹에서 최대 2^p의 테스팅 벡터가 있고 결 과는 O((2^p)(3p)³)이다. m / p 그룹에서 대한 총 계산 복잡도는 아래와 같다.

(^1.53)^p ^{(2 )( )}^p ³

m m

O mn p

p p

⎛ + + ⎞

⎜ ⎟

⎝ ⎠ (1) 모든 그룹의 계산이 끝난 후 최대 1+2^p 의 요 소를 가진 그룹은 JCBB를 이용하여 체크된다. m / p의 새로운 측정을 1 + 2p개인 저장된 특징점 후보 로 간주할 수 있다. 여기서 저장된 특징점 후보는 솔루션 공간이 (1+2^p)^m/p인 하나의 빈 매칭 벡터를 포함한다. p는 작은 상수이므로, 계산 복잡도는 O((1.53)^m/p)를 가진다. 식(1)의 결과는 PCA의 실제 복잡도보다 크다. 또한 그 합은 O((1.53)^m) 보다 작 으며 아래에서 증명된다.

( ) ( )

( )

1.53 (2 )( ) 1.533

1.53

p p mp

m p

m m

O mn p

p p

O

⎛ + + + ⎞

⎜ ⎟

⎝ ⎠

⎛ ⎞

≈ ⎜⎝ ⎟⎠

(2)

계산 복잡도는 p값이 증가함에 따라 줄어든다.

심지어 p = 3일 때 식은 O(1.15^m)에 따라 변하고 ICNN과 비교하여 JCBB는 아래와 같다.

( ) ¹³

( )

( ) 1.53 1.53 1.15

mp m m

O mn <O⎛⎜⎝ ⎞⎟⎠<O⎛⎜⎜⎝⎛⎜⎝ ⎞⎟⎠ ⎞⎟⎟⎠=O

(3)

and

( )

( ) 1.53^m^p ( ) 1.53^m

O PCA <O⎛⎜⎝ ⎞⎟⎠⇒O PCA <O (4)

적절한 p값을 가질 경우 식(2)에서 JCBB와 PCA의 대수적 계산 복잡도는 다른 측정값의 수와 비교되며 Fig. 5에서 보여준다. p값을 1부터 50까지 로 변화시키고 저장된 지도 특징점 수 n을 4가지 경우에서 1000으로 가정한다.

p = 2 - 5 (m = 50), p = 4 - 6 (m = 100), p = 10 - 12 (m

= 500), p = 16 - 18 (m = 1000) 일 때 PCA의 계산 복 잡도가 가장 낮다. 새로운 측정값의 수가 증가함 에 따라 p값은 증가한다. p = 1, p = m일 때 극단적 인 상황이 발생하고, 이는 그림에서 볼 수 있다.

단지 하나의 새로운 특징점이 각 그룹에 포함되어

있는 경우, 모든 새로운 특징점의 최적 매칭은 ICNN을 이용한 단위 매칭 쌍의 조합이 될 것이다.

또한 단 하나의 그룹만 있는 경우 매칭 결과와 매 칭 시간은 JCBB를 이용했을 때와 동일하다.

4. 실험 결과

실험은 PIONEER 3-DX 이동로봇과 270도의 측 정 범위를 가진 HOKUYO laser sensor를 이용하여 수행되었다. 이동 로봇의 궤적 스케치 지도와 60x15 미터의 실제 실험 환경은 Fig. 6에서 보여준 다. 로봇의 오도메트리에 의한 원 데이터를 이용 하여 구성한 지도와 로봇의 궤적은 Fig. 7에서 보 여주며, 여기서 작고 검은 포인트는 환경에서 얻 Fig. 6 Sketch map of the mobile robot trajectory and

pictures of real unknown environment in the experiment

Fig. 7 Map and trajectory of mobile robot are constructed based on odometry data and raw laser sensor data

(7)

어진 센서 데이터이며 이동 로봇의 위치는 센서 스캔이 얻어지는 순간이다.

추출된 자연적 모서리에 기반한 다른 3가지의 자료 연관 알고리즘(ICNN, JCBB and PCA)을 이용 하여 SLAM 실험이 수행되었다. 실험에서 이동 로 봇은 절대 좌표계에서 원점으로 가정된 초기 위치 부터 이동을 하며 마지막 스텝에서는 다시 원 위 치로 돌아온다. 그러므로 마지막 스텝에서는 loop closure가 체크된다. 매칭된 모서리의 수가 많아지 기 때문에 계산량은 점점 더 커진다. 환경으로부 터의 센서 포인트는 로봇의 이동에 따라 차례차례 축적된다.

ICNN을 이용한 SLAM 결과는 이전 단계에서 의 데이터 포인트와 센서 포인트는 중첩되지 않으 며 이는 Fig. 8의 좌측 상단에서 보여준다. 일부 개 체는 실제 형상과 동일하게 작성되지 않으며 이동 로봇과 표식의 보정에 대한 정확도가 떨어짐을 보 여준다. 반대로 JCBB를 이용한 SLAM 결과는 ICNN을 이용한 것보다 나은 결과를 보이며 Fig. 8 의 좌측 중단에서 보여준다. 대부분의 센서 포인 트는 이전 데이터와 중첩이 되지만 일부는 그렇지 않다. 더 많은 새로운 측정값이 JCBB의 최적 매칭 벡터에 포함된다. 하지만 일부 가능한 부정확한 단위 매칭 쌍 때문에 매칭 벡터의 매칭되어 저장 Fig. 8 Comparison of SLAM results by using different data association algorithms: ICNN (first row), JCBB (second

row) and PCA (third row). The left column of three rows displays the environment mapping result and the robot trajectory with odometry data (red line), the motion command (black line) and correction using algorithms. The middle column of every row shows the computation time in prediction part, matching part and update part with the corresponding method. The right column in each row expresses the number of total corners, number of new extracted corners and the number of new corners in the best matching vector at every step

(8)

된 모서리를 이용한 보정은 완벽하지 않다. PCA를 이용한 SLAM 결과는 각 스텝에서 이동 로봇의 보정이 잘 수행되며, 이는 Fig. 8의 좌측 하단에서 보여준다. PCA로 보정된 위치에 기반한 센서 포인 트는 같은 위치에서 항상 축적되며 이는 ICNN과 JCBB를 이용한 결과보다 더 우수하다. 본 실험에 서는 모든 단계에서 새롭게 추출된 모서리가 모든 그룹에서의 세 개의 모서리를 가진 다른 작은 그 룹으로 분할된다.

모든 스텝에서의 예측 시간, 매칭 시간, 업데이 트 시간을 Fig. 8의 중간 열에서 보여준다. 추출된 모서리의 수가 약간 변하기 때문에 모든 스텝에서 세 개의 알고리즘을 이용한 예측 시간은 거의 일 정하다. ICNN은 단위 매칭 쌍만 있어서 35개의 조 합만 테스트된다. 마지막 스텝에서 저장된 모서리 수가 최대 임에도 ICNN은 테스트를 하는데 약 25 초 밖에 걸리지 않는다. ICNN을 이용한 매칭 시간 은 저장된 모서리의 수가 증가함에 따라 선형성을 가진다. 모든 새로운 모서리에 대해 가능한 후보 의 수가 많기 때문에 JCBB의 매칭 시간은 기하급 수적으로 증가한다. 특별한 경우로는 12개의 새로 운 모서리가 추출되는 47번째 단계로 매우 큰 계 산 시간을 가지고 있고 가능한 모서리의 수는 다 음의 벡터로 표현된다.

[0 0 0 9 8 3 6 7 1 0 1 0] (5)

Joint compatibility를 체크하기 전에 저장된 모서 리와 추출된 모서리의 단위 매칭 쌍은 ML를 이용 한 individual compatibility에 의해 체크된다. 7개의 새 로운 모서리는 최소 하나의 저장된 모서리와 매치 되며 일부는 약간 더 크다. 이 단계에서 매칭 시간 이 3091초가 소모되며 Fig. 8의 가운데 열에서 보여 주고 JCBB가 특징점이 밀집된 환경에서는 부적합 함을 보여준다. JCBB를 이용하면 2³⁵개의 조합을 테 스트하기 때문에 많은 계산 시간을 소모하게된다.

하지만 partial compatibility를 이용하면 PCA는 식(1)과 (2)만 이용하여 상대적으로 소수의 조합만 테스트한다. 동일한 경우 PCA의 매칭 시간은 JCBB 보다 훨씬 빠른 대략 72초가 소모된다. loop closure가 검출되기 때문에 최종 단계에서 매칭 시 간은 전체 단계 중 가장 크다. 모든 단계에서 새 로 추출된 모서리의 수와 매칭된 모서리의 수는 우측 열에서 보여준다.

명확한 비교 결과를 확인하기 위해 ICNN, JCBB,

PCA를 이용하여 모든 단계에서의 총 매칭 시간과 전체 모서리를 비교하는 자료를 Fig. 9에서 보여준 다. 여기서 ICNN과 PCA의 매칭 시간이 JCBB보다 훨씬 느리게 증가함을 볼 수 있다. 물론 PCA의 매 칭 시간이 ICNN보다 크고 JCBB보다 작다. 매칭 시 간에 반해 PCA의 전체 모서리 수는 JCBB보다 작 고 ICNN보다 크다. 모든 단계에서 새로운 모서리와 매칭되는 저장된 모서리가 많아질수록 소요되는 계 산 시간이 더 커지기 때문에 본 결과를 더욱 쉽게 이해할 수 있다. 더 많은 모서리가 성공적으로 매칭 되는 경우, 적은 수의 새로 추출된 모서리가 상태 벡터에서 저장된 새로운 특징점으로 간주된다.

0 20 40 60 80 100 120

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

Number of steps

Time(sec)

Total Matching time of SLAM by using ICNN, JCBB and PCA ICNN

JCBB PCA

0 20 40 60 80 100 120

0 50 100 150 200 250 300

Number of steps

Number of Corners

Total corners of SLAM by using ICNN, JCBB and PCA ICNN

JCBB PCA

Fig. 9 Comparison of the total matching time (Top) and number of total corners (Bottom) in the previous steps with three data association algorithms, ICNN, JCBB and PCA

(9)

5. 결론

본 논문에서는 로봇의 위치 추정 및 매핑을 위 해 새로 제안한 자료 연관 알고리즘을 이용하여 자 연 모서리를 추출하며 이를 표식으로 한다. PCA 알 고리즘은 잘 알려진 두 알고리즘 ICNN 및 JCBB에 기반하여 제안되었다. 세 가지 자료 연관 알고리즘 으로 SLAM 실험을 수행하였으며 모서리를 기반으 로 하였다. 비교 결과로부터 모든 단계에서 PCA를 이용하여 로봇의 위치를 보정하는 것이 ICNN과 JCBB를 이용한 것보다 우수하다는 것을 증명하였 다. 그리고 새로 추출된 모서리를 위해 저장된 가능 한 모서리의 수가 매우 높은 경우 PCA의 매칭 시 간이 JCBB보다 더 작음을 알 수 있었다. 이러한 실 험 결과는 PCA가 효율적이고 특징점이 밀집된 미 지의 환경에서도 사용될 수 있음을 보여준다.

후 기

본 연구는 산업통상자원부가 출연하고 한국산 업기술평가관리원에서 위탁 시행한 로봇산업융합 핵심기술개발사업 (과제번호: 10038660)의 지원으로 연구되었음.

REFERENCES

1. Choi, K.-S. and Lee, S.-G., “Enhanced Slam for a Mobile Robot Using Extended Kalman Filter and Neural Networks,” Int. J. Precis. Eng. Manuf., Vol. 11, No. 2, pp. 255-264, 2010.

2. Mata, M., Armingol, J. M., De La Escalera, A., and Salichs, M. A., “A Visual Landmark Recognition System for Topological Navigation of Mobile Robots,” Proc. of the IEEE International Conference on Robotics and Automation, pp. 1124-1129, 2001.

3. Guanghui, L. and Zhijian, J., “An Artificial Landmark Design Based on Mobile Robot Localization and Navigation,” Proc. of the IEEE International Conference on Intelligent Computation Technology and Automation, pp. 588-591, 2011.

4. Meyer-Delius, D., Beinhofer, M., Kleiner, A., and Burgard, W., “Using Artificial Landmarks to Reduce the Ambiguity in the Environment of a Mobile Robot,” Proc. of the IEEE International Conference on Robotics and Automation, pp. 5173-5178, 2011.

5. Ronzoni, D., Olmi, R., Secchi, C., and Fantuzzi, C.,

“AGV Global Localization Using Indistinguishable Artificial Landmarks,” Proc. of the IEEE International Conference on Robotics and Automation, pp. 287- 292, 2011.

6. Yan, R.-J., Wu, J., Yuan, C., and Han, C.-S., “Extraction of Different Types of Geometrical Features from Raw Sensor Data of Two-Dimensional LRF,” Journal of Institute of Control, Robotics and Systems, Vol. 21, No. 3, pp. 265-275, 2015.

7. Nguyen, V., Gächter, S., Martinelli, A., Tomatis, N., and Siegwart, R., “A Comparison of Line Extraction Algorithms Using 2D Range Data for Indoor Mobile Robotics,”

Autonomous Robots, Vol. 23, No. 2, pp. 97-111, 2007.

8. Yan, R.-J., Wu, J., Lee, J. Y., and Han, C.-S.,

“Representation of 3D Environment Map Using B- Spline Surface with Two Mutually Perpendicular LRFs,” Mathematical Problems in Engineering, Vol.

501, Paper No. 690310, 2015.

9. Arras, K. O. and Siegwart, R. Y., “Feature Extraction and Scene Interpretation for Map-Based Navigation and Map Building,” Proc. of the International Society for Optics and Photonics on Intelligent Systems &

Advanced Manufacturing, pp. 42-53, 1998.

10. Yan, R., Wu, J., Wang, W., Lim, S., Lee, J., et al.,

“Natural Corners Extraction Algorithm in 2D Unknown Indoor Environment with Laser Sensor,”

Proc. of the IEEE International Conference on Control, Automation and Systems, pp. 983-987, 2012.

11. Neira, J. and Tardós, J. D., “Data Association in Stochastic Mapping Using the Joint Compatibility Test,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 6, pp. 890-897, 2001.

12. Kaess, M., Ranganathan, A., and Dellaert, F., “iSAM:

Incremental Smoothing and Mapping,” IEEE Transactions on Robotics, Vol. 24, No. 6, pp. 1365-1378, 2008.

13. Castellanos, J., Montiel, J., Neira, J., and Tardós, J. D.,

“The SPmap: A Probabilistic Framework for Simultaneous Localization and Map Building,” IEEE Transactions on Robotics and Automation, Vol. 15, No. 5, pp. 948- 952, 1999.

14. Feder, H. J. S., Leonard, J. J., and Smith, C. M.,

“Adaptive Mobile Robot Navigation and Mapping,”

The International Journal of Robotics Research, Vol.

18, No. 7, pp. 650-668, 1999.

(10)

15. Yan, R. J., Choi, Y. S., Wu, J., and Han, C. S.,

“Arc/Line Segments-Based SLAM by Updating Accumulated Sensor Data,” Journal of Institute of Control, Robotics and Systems, Vol. 21, No. 10, pp.

936-943, 2015.

16. Pérez, L. M. P., “Divide and Conquer: EKF SLAM in O(n),” IEEE Transactions on Robotics and Automation, Vol. 24, pp. 1107-1120, 2008.

17. Paz, L. M., Piniés, P., Tardós, J. D., and Neira, J.,

“Large-Scale 6-DOF Slam with Stereo-in-Hand,”

IEEE Transactions on Robotics, Vol. 24, No. 5, pp.

946-957, 2008.

18. Temeltas, H. and Kayak, D., “Slam for Robot Navigation,” IEEE Transactions on Aerospace and Electronic Systems Magazine, Vol. 23, No. 12, pp.

16-19, 2008.

19. Li, Y., Li, S., Song, Q., Liu, H., and Meng, M. Q.-H.,

“Fast and Robust Data Association Using Posterior Based Approximate Joint Compatibility Test,” IEEE Transactions on Industrial Informatics, Vol. 10, No. 1, pp. 331-339, 2014.

20. Wijesoma, W. S., Perera, L. L., and Adams, M. D.,

“Toward Multidimensional Assignment Data Association in Robot Localization and Mapping,” IEEE Transactions on Robotics, Vol. 22, No. 2, pp. 350-365, 2006.

21. Blanco, J.-L., González-Jiménez, J., and Fernández- Madrigal, J.-A., “An Alternative to the Mahalanobis Distance for Determining Optimal Correspondences in Data Association,” IEEE Transactions on Robotics, Vol. 28, No. 4, pp. 980-986, 2012.

22. Zhang, S., Xie, L., and Adams, M., “An Efficient Data Association Approach to Simultaneous Localization and Map Building,” The International Journal of Robotics Research, Vol. 24, No. 1, pp. 49-60, 2005.