Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer translate in English
ISSN : 1975-6291(Print)
ISSN : 2287-3961(Online)
Journal of Korea Robotics Society Vol.8 No.4 pp.256-265
DOI : https://doi.org/10.7746/jkros.2013.8.4.256

지역 지도 기반의 이동 로봇 탐사 기법

유혜정1, 정완균

Local Map-based Exploration Strategy for Mobile Robots

Wan Kyun Chung, Hyejeong Ryu1
Mechanical Engineering, POSTECH
1Mechanical Engineering, POSTECH
Received : May. 8. 2013; Reviewed : Jun. 12. 2013; Accepted : Oct. 1. 2013

Abstract

A local map-based exploration algorithm for mobile robots is presented. Segmented frontiersand their relative transformations constitute a tree structure. By the proposed efficient frontiersegmentation and a local map management method, a robot can reduce the unknown area and update thelocal grid map which is assigned to each frontier node. Although this local map-based exploration methoduses only local maps and their adjacent node information, mapping completion and efficiency can begreatly improved by merging and updating the frontier nodes. Also, we suggest appropriate graph searchexploration methods for corridor and hall environments. The simulation demonstrates that the entireenvironment can be represented by well-distributed frontier nodes.

0015-01-0008-0004-4.pdf2.34MB

1. 서 론

 미지의 환경 지도 작성과 위치 인식은 상위 단계의 작업 수행을 위한 이동 로봇의 필수 요건이다. 많은 연구자들이 위치 인식 및 지도 작성 알고리즘들을 개발하였다[1-3]. 이 알고리즘들은 주변 환경에 대한 센서 측정값의 부정확성을 극복하여 보다 정확한 지도 작성을 목표로 하지만, 지도 작성을 위한 이동 경로 즉, 다음 목표 지점을 결정하는 과정을 다루지는 않는다.

 탐사는 지도 작성을 위해 다음 목표 지점을 자율적으로 결정하는 과정이다. 대부분의 탐사 기법은 프론티어(frontier) 영역 추출을 기반으로 한다. 프론티어 영역은 알고 있는 영역 중에서 장애물이 없는 빈(empty) 영역과 미지의 영역 사이의 경계 지역이다[4]. 다음에 탐사할 영역을 결정하기 위해서는 아직 탐사 되지 않은 지역을 구분하는 것이 필수적이며, 격자 지도를 이용하여 미지의 영역과 맞닿아 있는 프론티어를 추출하는 것은 매우 직접적이며 쉬운 방법이다. 따라서 로봇의 위치 인식을 위해 형상 지도를 사용하거나 그래프 기반의 탐사를 수행하는 경우에도, 미지의 영역을 구분하기 위해 격자 지도 상의 프론티어 격자(frontier cell)를 추출하는 것이 일반적이다[5,6].

 프론티어 기반 탐사 기법의 기본 과정은 다음과 같다: 1) 격자 지도에서 프론티어 격자를 추출한다. 2) 추출된 프론티어의 유틸리티를 계산한다. 3) 유틸리티가 가장 높은 프론티어를 선택하고, 이를 다음 탐사 목표 지점으로 결정한다. 4) 결정된 목표 지점까지 이동한다. 로봇은 1)-4)의과정을 반복하면서 지도를 확장한다. 이때, 유틸리티는 프론티어까지의 이동거리, 프론티어 주변에서 추출될 수 있는 형상을 고려한 위치 인식 성능, 지도 확장 성능 등의 가중합(weighted sum)이다.

 기존의 탐사 기법은 위치 인식 결과와 센서 정보를 이용하여 하나의 격자 지도를 작성하고 유지한다. 하지만 이 방법은 위치 인식 성능에 관계 없이 항상 하나의 격자 지도가 갱신되기 때문에, 위치 인식 결과가 부정확할 경우 작성되는 격자 지도 역시 부정확할 가능성이 크다. 격자 지도가 부정확하면 프론티어 정보 역시 부정확하기 때문에 탐사 성능이 저하될 수 있다. 현재의 위치 인식 상태를 고려하여 다음 탐사 지점을 결정하는 기법들도 있지만[9,10], 이들은 이미 부정확해진 격자 지도를 관리하거나 갱신하는 방법을 제시하지 않는다. 불확실성이 커진 로봇의 위치가 loop-closing 등에 의해 다시 회복됐다 하더라도, 과거의 모든 센서 값과 해당하는 로봇의 위치를 저장하고 있는 경우에만 격자 지도를 갱신하는 것이 가능하다. 이러한 문제를 극복하기 위해 본 논문에서 지역 지도 기반의 탐사 기법을 제안한다.

 기존의 몇 연구 그룹들은 지도 작성 기법의 정확성과 처리 속도를 향상시키기 위하여 지역 지도 기반의 지도작성 기법을 개발하였다. Estrada는 로봇의 이동 거리 혹은 불확실성의 증가량에 따라 새로운 지역 지도를 생성함으로써 넓은 환경에서 정확성을 향상시킬 수 있는 hierarchical SLAM 기법을 제안하였다[8]. Ahn은 visual plane을 기준으로 지역 지도를 작성하여 각 지역 지도들 간의 정보 교합 성능을 향상시켰다[7]. 여러 개의 지역 지도들이 가지고 있는 기준 좌표계 사이의 상대 변환은 전체 환경에 대한 위상학적 그래프를 형성하며, loop-closing에 의해 지역 지도들의 전역 일치성을 확보할 수 있다. Blanco는 로봇이 이동한 경로를 재건하여 위상학적 노드를 추출하였고, 각 노드에 수치 지역지도가 할당된 형태의 하이브리드 지도를 작성하였다[13]. 하지만 이 기법들은 그 목적이 정확한 지도 작성에 있으며, 자율적인 지도 작성 전략 및 효율성 즉, 탐사 기법을 제시하지는 않는다.

 제안된 지역 지도 기반의 탐사 기법에서는 격자 지도에서 추출된 프론티어를 분류하여 대표 노드(node)로 지정하고, 분류된 프론티어 노드 사이의 상대 위치 변환을 에지(edge)로 하는 트리 구조를 작성한다. 각각의 노드는 로봇이 그 노드를 방문했을 때 작성된 지역 격자 지도를 가지고 있다. 다음에 탐사할 노드를 결정하기 위해 깊이 우선 탐색(DFS, depth-first search)과 너비 우선 탐색(BFS, breadthfirst search) 기반의 탐사 기법을 제안하였다. 일반적인 DFS 혹은 BFS는 그래프의 구조가 명확하게 정의된 경우 적용되는데, 이동 로봇 탐사의 경우 트리 구조는 탐사가 종료될 때까지 지속적으로 확장된다. 따라서 탐사를 위한 그래프 탐색 알고리즘을 제안하며, 이는 로봇의 위치 인식 성능 향상에 효과적인 loop-closing을 유도한다. Loopclosing 이후, loop을 이루는 노드의 격자 지도들은 서로 병합된다. 로봇은 작성된 트리 구조를 따라 이동하며 지역지도를 획득하고 loop-closing에 의해 해당하는 지역 지도를 병합하는 과정을 반복하면서 미지의 영역을 줄여나갈 수 있다.

본 논문은 다음과 같이 구성된다. 2장은 지역 지도 기반의 탐사 기법에 대한 전체적인 시스템 개요를 설명한다. 3장은 격자 지도에서 프론티어 노드를 추출하는 방법 및 트리와 지도의 데이터베이스를 설명한다. 4장은 그래프 탐색을 이용한 다음 탐사 노드 설정 방법을 제시한다. 5장은 시뮬레이션 결과를 보여주며, 6장의 결론이 뒤따른다. 

2. 시스템 개요

 전체 시스템 개요는 그림 1과 같으며, 이는 전체 과정과 이에 따른 데이터베이스의 관리 및 갱신을 보여준다. 알고리즘은 크게 세 개의 부분으로 구성된다. 첫 번째는 처음 방문하는 노드에서 새로운 노드를 추출하여 데이터베이스에 등록하는 과정이며, 두 번째는 이전에 방문했던 노드에 다시 방문한 경우 즉, loop-closing이 가능한 경우 loop 노드를 찾고 해당하는 지역 지도를 병합하여 데이터 베이스를 갱신하는 과정, 세 번째는 다음에 탐사할 노드를 결정하는 과정이다.

Fig. 1. Algorithm overview

 처음 방문하는 노드에서는, 그 노드에서 작성된 지역 지도가 부여되며 리프(leaf) 노드가 아닌 경우 즉, 새로운 프론티어 격자가 존재하는 경우, 이들을 분류하여 트리를 확장한다. 제안된 방법은 프론티어를 추출하기 위해 하나의 전체 지도를 사용하는 기존의 일반적인 프론티어 탐색과 달리 오직 지역 정보만 이용해서 프론티어를 추출한다. 따라서 이전에 방문했거나 이미 알고 있는 지역임에도 불구하고, 현재 지역 지도에서는 프론티어로 인식되어 지나치게 많은 노드가 생성되어 탐사 성능이 저하 될 수 있다. 이를 극복하고 전체 환경에 대한 지도 작성의 완결성을 검사 하기 위해, 프론티어를 추출할 때 인접한 노드의 지역 지도를 병합한다. 현재의 지역 지도에서 검출된 프론티어 격자가 병합된 지도에서도 여전히 프론티어인 경우에만 새로운 노드의 등록 대상으로 간주한다.

이전에 방문했던 노드를 다시 방문하는 loop-closing의 경우는 두 가지 상황에 따라 발생한다. 첫째는 제안된 그래프 탐색 방법에 의한 것으로 로봇이 리프 노드에 도달한 경우 부모 노드로 되돌아가는 유도된 loop-closing이다. 다른 하나는 로봇이 탐사를 지속하는 동안 지역 지도 상에서 새로운 노드를 추가하는 과정에서 도달하기 전에는 새로운 노드라고 인식했다가, 노드에 도달한 이후 이미 방문했던 노드임을 알게 되는 경우이다. 이것은 우연한 loop-closing으로 지역 지도만 이용해서 프론티어 노드를 추출하기 때문에 생기는 현상이다. 본 논문에서는 이러한 loop-closing 상황을 인식하는 것에 대해서는 다루지 않고, 이러한 상황이 발생했을 경우 트리와 지도 데이터베이스 갱신에 대해서 다룬다. Loop-closing 인식은, 레이저 포인트 클라우드를 이용한 스캔 매칭 혹은 이미지 매칭과 같은 장소 인식(place recognition) 기법을 이용하여 판단할 수 있다[14-16]

작성된 트리의 에지 정보는 해당되는 loop 노드들의 상대 위치 변환을 제공하며, iterated Extended Kalman Filter(IEKF)와 같은 방법들을 이용하여 에지 정보와 재방문된 노드의 정보 교합이 이루는 제한조건을 풀 수 있다[7,8]. 따라서 loop-closing이 loop 노드들의 위치를 명확하게 할 수 있다고 가정하는 것은 타당하며, 본 논문에서는 loop-closing이 발생했을 경우 해당되는 loop 노드의 시퀀스를 찾는 방법과 각 노드에 해당되는 지역 지도들의 병합 및 트리 데이터베이스를 갱신하는 과정을 제안한다.

 다음 탐사 목표 지점 결정을 위해서 DFS 탐사와 BFS 탐사를 적용하였다. 두 탐사 방법 모두 리프 노드에 도달했을 경우 부모 노드로의 loop-closing을 유도한다.

3. 프론티어 트리

 트리 탐색 방법의 효율성은 노드의 수에 영향을 받는다. 노드의 수가 지나치게 많아지면 탐색 속도가 저하된다. 특히 제안된 방법에서는 전체 환경에 대한 탐사를 완료할때까지 노드의 수가 지속적으로 증가하기 때문에, 탐사의 효율성을 위해서 등록되는 노드의 개수를 최소화하는 과정이 필요하다. 이를 위해 격자 지도에서 검출된 모든 프론티어 격자를 노드로 등록하는 것보다, 프론티어 격자들을 분류하고, 분류된 그룹의 대표 지점을 노드로 등록하는 것이 효율적이다.

3.1 프론티어 노드 추출

현재 격자 지도에서 캐니-에지 검출기를 이용하여 에지격자들을 추출하고 각 에지 격자를 중심으로 주변 격자들의 엔트로피 합을 계산하여 프론티어 격자를 추출한다. 격자 (i, j)의 엔트로피는 식 (1)과 같으며, Pi,j(O)는 점유 확률, Pi,j(E)는 비점유 확률이다. 

 엔트로피 값은 확률분포가 균등 분포 일 때 즉, 점유 확률과 비점유 확률이 동일하게 0.5의 값을 가지는 미지의 격자일 경우 최대가 된다. 식 (2)는 에지 격자 주변의 일정 윈도우 영역 내에 해당하는 격자들의 엔트로피 합이며, 미지의 격자가 많을수록 값이 커진다. 이때 점유 확률 및 비점유 확률은 병합된 격자 지도에서 얻어진다. 이는 2장에서 언급했듯이 이미 알려진 영역에서 프론티어가 추출되는 것을 방지하기 위함이다. 현재 노드와 인접한 노드 즉, 부모 노드와 바로 직전에 방문했던 노드의 격자 지도가 병합된다. 현재 노드, 부모 노드, 직전 방문 노드에 해당하는 세 개의 격자 지도가 병합되며, 직전 방문 노드가 부모 노드일 경우 두 개의 격자 지도가 병합된다(그림 2). 지역 지도는 현재 노드의 위치를 기준으로 병합된다. 따라서 각각의 인접한 노드의 지역지도는 현재 노드의 좌표계를 중심으로 변환되며, 이를 위해 격자 지도의 강체 변환을 이용한다[11]. 현재 노드를 k , 인접한 노드를 j 라고 할 때, 격자 지도의 강체 변환식은 다음과 같다.

Fig. 2. Frontier detection on the merged map

 여기에서 Mj는 인접 노드 j 의 지역 지도이며, Mkj 는 현재 노드의 좌표계를 기준으로 변환된 인접 노드 j의 지역 지도이다. 강체 변환 행렬 T 는 현재 노드와 인접한 노드 사이의 에지 정보 즉, 상대 변환 (χk,j, yk,j, θk,j)으로부터 구해진다(식 4).

 강체 변환된 인접한 지역 지도들은 현재 노드의 지역 지도와 병합되며, 이때, 서로 중첩된 위치의 확률 데이터는 Thrun이 제안한 방법을 사용하여 갱신된다[12].

 병합된 지도의 일정 윈도우 내에서 점유 격자를 하나도 포함하지 않으면서 엔트로피 합이 일정 값 이상일 경우 프론티어 격자로 추출되며, 추출된 프론티어 격자들은 폴라 히스토그램을 이용하여 분류된다(그림 3). 이때, 분류된 프론티어 그룹의 각도 차이(Δθ )가 120°이상인 경우 n = [Δθ / 120°] 그룹으로 세분화 한다. 로봇이 완전히 개방된 공간에 있는 경우, 프론티어 격자의 히스토그램은 Δθ가 360°인 하나의 그룹이다. 이때 하나의 대표 노드만 자식노드로 등록하면 자식 노드를 탐사하고 난 이 후에도 부모 노드에서 추출된 프론티어 격자 중에 여전 히 미지의 영역으로 남아있는 격자가 존재한다. 따라서 자식 노드탐사를 완료한 이후, 부모 노드에서 추출된 프론티어 격자가 모두 알려진 영역이 되기 위해서는 최소한 세 개 이상의 자식 노드를 등록해야 한다(그림 4).

Fig. 3. Frontier segmentation using polar histogram

Fig. 4. Frontier segmentation in empty space

 각 프론티어 그룹의 평균 격자 위치(식 5)로부터 가장 가까운 격자의 위치가 대표 프론티어 노드의 위치 Node(X, Y)로 지정된다(식 6).

 분류된 대표 격자의 위치가 프론티어 트리의 노드로 등록되고, 로봇의 위치와 각각의 대표 격자 위치의 상대 변환이 트리의 에지 역할을 한다.

3.2 프론티어 트리와 지도 데이터베이스

 지역 지도 기반의 탐사는 새로운 노드가 더 이상 발견되지 않을 때까지 노드를 등록하여 트리를 확장하는 과정이다. 프론티어 트리 정보는 노드와 에지, 그리고 각 노드에 할당된 지역 지도의 데이터베이스에 저장되며, 이들은 서로의 id를 공유한다(그림 5). 트리 데이터베이스의 세부항목은 표 1과 같다.

Fig. 5. Structure of frontier tree

Table 1. Frontier tree and map database

각 노드와 지역 지도는 고유의 id를 가지고 있다. 각 노드는 방문했는지 여부를 나타내는 플래그( flagvisit )를 포함하고 있으며, 이 플래그는 노드가 등록되는 순간에는 “false”였다가, 로봇이 노드에 도달하는 순간 “true”로 바뀐다. flagloop-closing 은 노드에서 loop-closing이 완료되었는지를 나타낸다. Loop-closing에 의해 현재 노드와 자식 노드들의 상대 위치 관계가 정확하게 계산될 수 있으며, 이를 기준으로 부모와 자식 노드의 지역 지도가 서로 병합되어 동일한 지도를 공유하게 되면 부모 노드의 flagloop-closing 은 “true”가 된다. 노드 정보는 할당된 지역 지도의 id를 포함하고 있으며, 지역 지도 정보 역시 해당하는 노드들의 id와 이들의 위치를 포함하고 있다. 

에지 정보는 노드 사이의 상대 위치 변환을 저장한다. 현재 노드에서 새로운 자식 노드들이 등록될 때, “현재 노드-자식 노드”와 “자식 노드-자식 노드” 사이의 예측되는 상대 위치 변환이 Edge- 에 할당된다. Edge+ 는 로봇이 노드 i와 j 사이를 실제 이동한 거리에 의해 측정되는 값으로 가 할당되면, 도 실제 이동에 의한 값으로 갱신된다. Edge+ 는 로봇이 실제 이동한 정보를 나타내므로 유도되지 않은 loop-closing이 발생했을 경우, loop 노드의 시퀀스를 찾는데 사용된다. Edge- 를 이용해서 방문하지 않은 목표 노드의 최단 거리를 예측할 수 있다.

4. 그래프 탐색을 이용한 다음 목표 결정

 다음 목표 노드를 결정하기 위하여 작성된 프론티어트리의 에지 정보를 이용한 그래프 탐색을 수행한다. BFS와 DFS는 대표적인 그래프 탐색 알고리즘이다. 일반적으로 두 알고리즘은 트리의 구조가 명확하게 정의된 경우 시작 노드에서 목표 노드까지 최단 거리를 찾기 위해 적용된다. 반면, 이동 로봇 탐사의 경우 트리 구조는 탐사가 진행됨에 따라 확장되거나 변하기 때문에 이에 적합한 DFS와 BFS 기반의 탐사 기법을 제안한다. DFS 탐사는 리프 노드에 도달할 때까지 새로운 자식 노드를 향하여 탐사를 지속하고, 리프 노드에 도달한 이후 부모 노드로 되돌아 오는 loop-closing을 수행한다. 반면, BFS 탐사는 방문하지 않은 형제 노드를 우선으로 탐사하다가 모든 형제 노드를 탐사 한 이후 부모 노드로 되돌아가서 loop-closing 및 지도 갱신을 수행한다. 부모 노드의 loop-closing이 완료되면 loop-closing이 완료되지 않은 자식 노드로 이동하여 탐사를 계속한다(그림 6).

Fig. 6. Example of DFS exploration and BFS exploration

4.1 복도 환경을 위한 DFS 탐사

 복도 환경은 한 쪽 방향으로 지속해서 노드가 등록되는 경우가 많다. 따라서 계속 새로운 노드를 향해서 탐사하다가 복도 끝에 도달 했을 경우 즉, 현재 노드가 리프 노드이면 부모 노드로 되돌아가는 loop-closing을 유도하면서 각각의 독립된 지역 지도들을 병합하여 갱신하는 DFS 방식이 효율적이다. BFS 방식은 새로운 노드로의 탐사보다 부모 노드로의 loop-closing을 유도하는 것이 우선시 되기 때문에, 현재 노드에서 매번 부모 노드로 되돌아갔다가 자식 노드로 탐사하는 과정에 의해 탐사 경로가 지나치게 길어질 수 있다. DFS를 이용한 다음 탐사 노드 결정 과정은 그림 7과 같다.

Fig. 7. Decision process of DFS exploration

4.2 홀 환경을 위한 BFS 탐사

 홀 환경은 전 방향이 개방되어 있는 특성으로 인해 현재 위치에서 여러 방향으로 자식 노드가 생성되는 경우가 많다. 따라서 매번 새로운 노드 위주로 탐사를 진행하는 DFS를 적용할 경우 부모 노드로의 loop-closing이 지연 된다. 새로운 노드 검출을 위해 지역 지도만 사용하는 제안된 기법의 특성상, 이미 등록되었던 노드가 새로운 노드로 다시 등록되면 탐사 효율성이 저하될 수 있다. 따라서 홀 환경에서는, 형제 노드들의 탐사를 완료 했을 경우 부모 노드로의 loop-closing을 우선시하여 해당되는 지역 지도들의 병합을 유도하는 BFS 탐사를 적용하는 것이 효율적이다. 자식 노드 단계로 탐사를 진행하기 앞서, 갱신된 지도를 이용해서 각 자식 노드의 알려진 상태를 검사하여 알려진 영역에 속하는 자식 노드는 탐사 대상에서 제외하는 과정을 통해서 탐사해야 할 노드의 개수를 효율적으로 관리할 수 있다. BFS를 이용한 다음 탐사 노드 결정 과정은 그림 8과 같으며 부모 노드, 현재 노드, 형제 노드, 자식 노드의 순서로 loop-closing이 우선시 된다.

Fig. 8. Decision process of BFS exploration

4.3 Loop-closing 상황에서 데이터베이스 갱신

 지역 지도의 정보 부족을 극복하기 위해서는 loopclosing에 의해 갱신된 에지 정보를 바탕으로 해당되는 지역 지도들을 병합하는 것이 필수적이다. 지역 지도 기반의 탐사 기법은, 각 노드들이 등록될 당시의 예측된 에지 정보만 가지고 있을 경우에는 각각의 지역 지도만 소유하고 있다가, loop-closing에 의해 에지 정보가 명확해지면 해당하는 노드들의 지역 지도가 병합 및 갱신되는 과정을 반복한다. 앞서 언급했듯이 loop-closing 상황을 인지하거나[14-16], loop 제한 조건을 만족하는 에지들의 상대 변환을 구하는 방법은 기존에 제안된 방법을 적용할 수 있으므로[7,8], 본 논문에서는 loop-closing에 의해 정확한 에지 정보를 얻을 수 있다고 가정하고, 이 상황에서 제안된 프론티어트리 데이터베이스를 갱신하는 방법을 다룬다.

4.3.1 Loop 시퀀스 결정

 Loop-closing은 두 가지 경우에 의해 발생된다. 탐사 기법에 의해 유도된 자식 노드에서 부모 노드로의 loopclosing과 로봇이 특정 노드에 도달하기 전에는 방문하지 않은 노드라고 간주 했는데 도달한 이후 이전에 방문했던 노드라고 인지하는 우연한 loop-closing이다.

 전자의 경우, loop 시퀀스는 명확하다. DFS 탐사에서는 부모 노드와 바로 직전에 방문했던 자식 노드가 loop 시퀀스를 형성한다. BFS 탐사에서는 부모 노드와 여러 개의 자식 노드가 loop을 형성하며, 시퀀스는 실제로 방문한 노드들의 상대 변환을 저장하고 있는 에지 정보(표 1에서 Edge+)를 이용해서 순회 판매원 문제(TSP, Traveling Salesman Problem)의 해로 결정된다.

후자의 경우, loop 노드와 시퀀스는 일반적인 최단거리 탐색 알고리즘을 적용하여 얻는다. 에지 정보( Edge+)를 인접 행렬(adjacency matrix)로 사용하여 최단거리 탐색 알고리즘을 적용하면 loop 시퀀스를 찾을 수 있다. 이때, 출발 노드는 재방문된 노드가 되며, 도착 노드는 현재 노드를 재방문하기 직전 탐사했던 노드이다.

Loop 시퀀스에 해당하는 에지 정보를 이용한 loop 제한조건은 식 (7)과 같다. 이때 재방문된 노드의 id는 1이며 바로 직전에 방문한 노드의 id는 n이다. 

Loop 노드 사이의 에지 정보는 위 제한 조건을 만족시키는 최적 해를 구함으로써 갱신될 수 있다[7,8]

4.3.2 데이터베이스 갱신

 갱신된 에지 정보를 이용해서 loop에 해당되는 지역지도들이 병합된다. 지도 데이터베이스는 격자 지도 정보뿐만 아니라, 지도를 공유하는 노드의 id와 그 노드의 위치까지 포함하기 때문에, 병합된 격자 지도에서 이들의 위치 정보를 다시 계산해야 하며 그 과정은 표 2와 같다. 기준 노드 즉, loop의 시작 노드는 유도된 loop-closing의 경우 부모 노드, 유도되지 않은 경우 재방문 노드가 된다. 최종적으로 기준 노드를 중심으로 나머지 loop 노드들, 그리고 이들과 동일한 지역 지도를 공유했던 노드들의 위치가 갱신된다(표 2).

Table 2. Algorithm to update frontier tree DB after loop-closing

그림 9는 로봇이 노드 1에서 탐사를 시작한 후, BFS 탐사 방법에 따라 자식 노드 2, 3, 4를 순서대로 탐사한 후 다시 노드 1로 되돌아 왔을 때 지역 지도들의 병합을 보여준다. Loop 노드들 사이의 에지 , , , 는 식(7)의 제한 조건에 의해 갱신되며, 이들을 합성(composition)하여 현재 노드와 각 자식 노드사이의 상대변환을 계산한다. 자식 노드의 지역 지도는 상대변환을 이용하여 현재 노드의 좌표계로 강체 변환될 수 있다(식 3, 4). 변환된 지역 지도들은 현재 노드의 좌표계를 기준으로 병합된다.

Fig. 9. Merging local maps

5. 시뮬레이션 결과

 제안된 탐사 기법을 이용해서 전체 환경에 대한 지도

작성을 완료할 수 있는지 확인하기 위하여 시뮬레이션을 수행하였다. 로봇을 중심으로 360°전 방향에 대한 거리 값을 얻을 수 있는 레이저 스캐너가 장착되어 있다고 가정한다. 모든 시뮬레이션은 Matlab을 이용하여 수행되었으며, 레이저 데이터는 ray-traycing 알고리즘을 이용하여 시뮬레이션 되었다. 격자 지도는 Thrun이 제안한 방법을 사용해서 작성된다[12]

복도와 홀 환경에 대해서 시뮬레이션이 수행되었으며, 로봇은 각각의 환경에서, 서로 다른 다섯 개의 지점(그림 10(a)와 11(a)에서 A~E)에서 탐사를 시작하였다. 표 3과 4는 각 환경에 대한 DFS 탐사와 BFS 탐사의 시뮬레이션 결과이다. 

Fig. 10. Simulation results using DFS

Fig. 11. Simulation results using BFS

Table 3. Simulation results of the hall environment

Table 4. Simulation results of the corridor environment

홀 환경에서는 탐사를 완료할 때까지의 총 이동 거리가 BFS 탐사의 결과가 더 짧고, 복도 환경에서는 DFS가 더 짧다. BFS 탐사의 경우 상위 노드에서부터 loop-closing을 수행하여 지도를 병합하기 때문에 생성되는 프론티어 노드의 개수가 전반적으로 DFS보다 적다. DFS는 리프 노드 즉, 하위 단계의 노드부터 loop-closing을 유도하기 때문에, 홀 환경에서는 리프에 도달하기까지 지나치게 많은 노드를 생성하는 경향이 있다. 

 복도 환경에서는 매 단계마다 loop-closing을 유도하는 BFS 탐사에 비해서, 리프 노드에 도달했을 경우 loopclosing을 유도하는 DFS 탐사의 이동 거리가 더 짧다.

생성된 전체 프론티어 노드의 개수와 실제로 방문한 노드의 개수가 차이가 나는 이유는, loop 노드들의 지역 지도들을 병합하고, 각 loop 노드와 바로 인접한 노드들이 병합된 지도에서 알려져 있는 영역인지 검사하여, 알려진 영역으로 판명되면 탐사해야 할 대상에서 제외하는 과정이 수행되었기 때문이다. 탐사해야 할 노드의 개수를 효율적으로 줄여주는 과정은 탐사 효율성을 증가시키기 위해 필요하다.

 평균 계산 시간은, 홀 환경의 경우 A에서 시작한 경우를 제외하고 BFS 탐사 결과가 더 짧았다. BFS 탐사는 각 단계마다 새롭게 추출되는 프론티어 노드의 개수가 DFS 탐사 보다 적기 때문에 결과적으로 새로운 노드까지 최단거리를 계산하는 부분의 처리 속도가 DFS 탐사 보다 빠르다. 탐사를 완료하는데 소요된 총 계산 시간 역시 BFS 탐사의 경우가 더 짧다.

 복도 환경에서는 DFS 탐사의 결과가 더 짧은 평균 계산 시간과 총 계산 시간을 기록했다. BFS 탐사의 경우, 매단계마다 부모 노드로의 loop-closing에 의한 지도 데이터 베이스 갱신이 수행되기 때문에 계산 부하가 증가된다.

 그림 10과 그림 11에서 볼 수 있는 바와 같이 추출된 프론티어 노드들은 환경 전체 영역에 걸쳐서 분포되어 있고, 환경은 프론티어 노드와 노드 간의 에지 정보를 이용하여 트리 구조로 표현될 수 있다. 복도 환경에서는 한 방향으로 확장되는 트리 구조가 생성되었고(그림 9(b)), 홀 환경에서는 노드가 전 방향으로 넓게 분포하는 트리 구조가 생성되었다(그림 10(b)).

6. 결 론

 본 논문은 지역 지도를 이용한 이동 로봇의 탐사 기법을 제안하였다. 이는 기존의 프론티어 기반 탐사 기법들이 위치 인식 성능에 관계 없이 하나의 지도만을 작성하고 유지하기 때문에 작성된 지도가 부정확할 수 있는 문제를 극복하기 위함이다. 격자 지도 위에서 추출된 프론티어들은 효율적으로 분류되어, 트리 데이터베이스에 대표 노드로 등록된다. 각 환경에 적합한 그래프 탐색 알고리즘을 이용하여 다음 탐사 목표 지점이 설정되며, 탐색 알고리즘은 노드의 방문 상태에 따라서 loop-closing을 유도한다. 이에 따라 loop 노드들의 에지 정보가 정확해진다고 가정하고, loop에 관여한 노드들의 지역 지도들은 갱신된 에지 정보를 이용하여 병합된다.

또한 목표 지점까지 최단 경로를 찾는데 주로 사용되었던 DFS와 BFS를, 새로운 노드 생성을 위한 탐사 기법으로서 적용하였다. 환경 특성에 따라 다른 그래프 탐색 알고리즘을 적용한 결과, 복도 환경에서는 새로운 노드를 중심으로 탐사하는 DFS 탐사가 효율적이며, 홀 환경에서는 노드의 loop-closing을 완료하는 방향으로 탐사하는 BFS 탐사 기법이 효율적이라는 결론을 얻을 수 있었다.

Reference

1.H. Choset, and K. Nagatani "Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization", IEEE Trans. Robotics and Automation, vol. 17, no.2, pp.125-137, 2001.
2.M. G. Dissanayake, P. Newman, S. Clark, H. F. Durrant-Whyte, and M Csorba, "A solution to the simultaneous localization and map building (SLAM) problem", IEEE Trans. Robotics and Automation, vol.17, no.3, pp.229-241, 2001.
3.M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, "FastSLAM 2.0: an improved particle filtering algorithm for simultaneous localization and mapping that provably converges", in Proc. of International Joint Conference on Artificial Intelligence, pp.1151-1156, 2003.
4.B. Yamauchi, "A frontier-based approach for autonomous exploration", in Proc. of Computational Intelligence in Robotics and Automation, pp.146-151, 1997.
5.F. Bourgault, A. A. Makarenko, S. B. Williams, B. Grocholsky, and H. F. Durrant-Whyte, " Information based adaptive robotic exploration", in Proc. Of International Conference on Intelligent Robots and Systems, pp.540-545, 2002.
6.A. A. Makarenko, S. B. Williams, and H. F. Durrant-Whyte, "An experiment in integrated exploration", in Proc. of International Conference on Intelligent Robots and Systems, pp.534-539, 2002.
7.S. Ahn, J. Choi, N. L. Doh, and W. K. Chung, "A practical approach for EKF-SLAM in an indoor environment: fusing ultrasonic sensors and stereo camera", Autonomous robots, vol.24, no.3, pp.315-335, 2008.
8.C. Estrada, J. Neira, and J. D. Tard’os, "Hierarchical SLM: real-time accurate mapping of large environments", IEEE Trans. Robotics, vol.21, no.4, pp.588-596, 2005.
9.R. Sim, and N. Roy, "Global a-optimal robot exploration in SLAM", in Proc. of International Conference of Robotics and Automation, pp.661-666, 2005.
10.C. Stachniss, G. Grisetti, and W. Burgard, "Information gain-based exploration using raoblackwellized particle filters", in Proc. of Robotics: science and systems, pp.65-72, 2005.
11.S. Carpin, "Fast and accurate map merging for multirobot systems", Autonomous robots, vol.25, no.3, pp.305-316, 2008.
12.S. Thrun, "Learning occupancy grid maps with forward sensor models", Autonomous robots, vol.15, no.2, pp.111-127, 2003.
13.J. Blanco, J. Fernández-Madrigal, and J. Gonzalez, "A new approach for large-scale localization and mapping: Hybrid metric-topological SLAM", in Proc. Of International Conference of Robotics and Automation, pp.2061-2067, 2007.
14.P. Newman, and H. Kin, "SLAM-loop closing with visually salient features", in Proc. of International Conference of Robotics and Automation, pp.635-642, 2005.
15.A. Nüchter, K. Lingemann, and H. Surmann, "Heuristicbased laser scan matching for outdoor 6D SLAM", in Proc. of KI 2005: Advances in Artificial Intelligence, pp.304-319, 2005.
16.J. Choi, M. Choi, and W. Chung, "Topological localization with kidnap recovery using sonar grid map matching in a home environment", Robotics and Computer-Integrated Manufacturing, vol.28, no.3, pp.366-374.
오늘하루 팝업창 안보기 닫기