Adaptive Sliding Window for Graph-Based SLAM

Abstract

제안하는 가변 슬라이딩 윈도우는 그래프 기반의 위치인식 및 지도작성에서 로봇의 경로를 점진적으로 보정하는 고정 크기 슬라이딩 윈도우의 문제점을 개선한 방법이다. 슬라이딩 윈도우를 연결이 약한 부분을 중심으로 두 그룹으로 나눈 다음, 가장 최근에 추가된 노드와 관련이 없는 그룹을 슬라이딩 윈도우에서 제외시키면서 슬라이딩 윈도우의 크기를 변화시킨다. 슬라이딩 윈도우를 두 그룹으로 나누는 시점의 판단은 이미지 분할 기술로 잘 알려진 N-cut을 이용한다. 이 때, 가중치 행렬은 그래프 기반의 Front-end에서 생성된 두 노드 사이의 공간적인 위치 관계의 정보 행렬을 이용하여 생성한다.가변 슬라이딩 윈도우를 사용하면 두 노드 사이의 공간적인 위치 관계의 정보 행렬의 손실과 선형화 오차를 최소화하는 최적의 윈도우 사이즈 얻을 수 있다. 따라서, 위치 인식 오차가 줄어든다. 게다가, 최적의 윈도우 사이즈 때문에 가변 슬라이딩 윈도우는 효율적인 계층 구조를 만들 수 있다는 추가적인 이점이 존재한다. 상위 레벨의 그래프를 만들기 위해, 슬라이딩 윈도우에서 제외되는 노드들을 고정시켜 상위 레벨의 노드들로 만든다.가변 슬라이딩 윈도우의 효율성을 검증하기 위하여 실험실에서 얻어진 데이터와 슈퍼빌 아파트에서 얻어진 데이터를 바탕으로 고정 크기 슬라이딩 윈도우와 비교하였다. 가변 슬라이딩 윈도우를 그래프 기반의 Back-end에 적용한 결과 고정 크기 슬라이딩 윈도우보다 정확한 위치 인식이 가능했으며, 로봇 경로 보정 시간도 단축되는 것을 확인하였다.

We propose the Adaptive Sliding Window (ASW) which is a novel approach to solve the graph-based simultaneous localization and mapping (SLAM) problem. We adjust the size of the sliding window for incremental optimization by eliminating the portion of the graph which shows the lowest similarity between the eliminated graph and the remaining part of graph and by dropping poses which are not related to the latest robot pose. The decision is made by utilizing a graph-cut algorithm, where the weight matrix is created from the constraints’ information matrices estimated by the front-end system. Our method provides the optimal window size that minimizes the information loss of spatial constraint and linearization error. Therefore, our approach increases localization accuracy, and construct the hierarchical structure of the graph for global correction efficiently. To make a high-level graph for local map, we create a high-level node (local map) by immobilizing the truncated part from the sliding window. The local maps can be efficiently matched in the front-end system to estimate the constraints between the high-level nodes. We validated our algorithm on the indoor datasets obtained in our lab environment and in the apartment to demonstrate the effectiveness of the proposed method. When our approach applied to the graph-based SLAM back-end, we improved both localization accuracy (by reducing the information loss) and computational efficiency simultaneously.