능동 SLAM을 위한 계층적 커버리지 경로 계획 기법
; 이승환**
; Seung-Hwan Lee**
초록
본 연구에서는 능동 SLAM을 위한 계층적 커버리지 경로 계획 방법을 제안한다. 능동 SLAM은 SLAM에서 불확실성이 높은 영역을 재방문하여 SLAM 지도의 정확성을 향상하기 위한 로봇 경로를 계획하는 기술이다. 그러나, 불확실성이 높은 영역만 방문할 경우, 오히려 공분산의 지속적 상승으로 인해 SLAM 결과가 발산될 수 있다. 제안된 방법은 허용 가능한 불확실성을 넘지 않는 제약조건 아래에서 기존 방법보다 향상된 커버리지 경로 계획을 제안한다. 이를 위해 개미 군집 최적화 기법과 유전 알고리즘을 계층적 구조로 접근해 해결하였다. 시뮬레이션에서는 경로 길이, 불확실성 수치, 수행시간 면에서 제안한 방법과 기존 접근 방법과의 비교 및 분석을 수행하였다. 제안한 방법은 제약조건인 허용 가능한 불확실성을 넘지 않으며 동시에 짧은 경로 생성 성능을 보였다. 향후, 제안한 방법을 실시간으로 수행하여 SLAM의 공분산이 감소하고 지도가 정확히 작성됨을 보일 예정이다.
Abstract
In this study, we propose a hierarchical coverage path planning method for active SLAM. Active SLAM is a technique that plans robot paths to revisit areas with high uncertainty in SLAM, thereby improving SLAM accuracy. However, visiting only areas with high uncertainty can lead to divergence in SLAM due to a continuous increase in covariance. The proposed method suggests an enhanced coverage path planning under the constraint of not exceeding acceptable uncertainty. To achieve this, the ant colony optimization method and the genetic algorithm were approached in a hierarchical structure. In simulations, performance comparisons and analysis were conducted between the proposed method and conventional approaches. The proposed method demonstrated results with shorter path lengths while simultaneously not exceeding acceptable uncertainty, compared to conventional methods. In the future, we plan to demonstrate that the covariance of SLAM is reduced and the map is accurately constructed by the proposed method in real time.
Keywords:
active SLAM, coverage path planning, ant colony optimization, genetic algorithmⅠ. 서 론
능동 SLAM(Simultaneous Localization and Mapping) 문제는 위치 추정과 지도 작성 문제인 SLAM 문제[1]에 SLAM 정확도를 높이기 위한 로봇의 추가적인 경로 계획 등을 포함하는 것이다[2]. 이를 위해 추정 정확도와 관련된 유틸리티 함수를 결정[3]-[5]하고 이 함수를 이용한 로봇의 경로 계획 전략을 결정하게 된다. 일반적으로 추정 정확성이 낮은 영역은 SLAM 추정 불확실성 또는 공분산(Covariance)이 높은 영역을 의미한다[6]. 추정 불확실성이 높은 영역은 높은 센서 노이즈 또는 매칭 실패, 루프 클로징이 되지 않은 누적 오차 등이 원인이다. 루프 클로징이란 과거에 방문한 영역을 재방문하면서 로봇의 누적 위치 추정 오차가 크게 감소하는 기술을 의미한다[7]. 특히 과거에 방문한 영역 중 매칭이 잘될 수 있는 두드러진 특징점(Salient feature)을 가진 영역을 재방문하는 것을 유도한다[8]. 따라서 능동 SLAM을 위해 로봇은 이러한 요소를 잘 고려하여 로봇의 경로를 계획하고 생성해야한다.
기존 많은 능동 SLAM 문제를 풀기 위한 커버리지 경로 계획은 새로운 영역의 탐사와 불확실성이 증가하지 않도록 기존 루프 클로징 영역의 재방문 사이에서의 의사결정(Decision making)을 다루었다[9]. 따라서 최적의 경로 계획보다 한 시점에서의 최적의 의사결정이 중요하였다. 하지만 초기 탐사를 통해 SLAM이 수행되었다면, 추정 공분산의 크기에 따라 불확실성이 높고 낮음에 대한 계산이 가능하고 불확실성이 높은 영역에 대해서는 커버리지 경로 생성을 통해 해당 영역을 방문해 불확실성의 크기를 낮춰줄 필요가 있다. 대신, 이 영역은 초기 탐사 동안 불확실성이 높았으므로 불확실성이 또다시 높아지지 않도록 불확실성 수치 증가를 고려한 최적 커버리지 경로 계획이 필요하다.
따라서 본 연구에서는 성공적인 능동 SLAM을 위해 초기 SLAM을 수행한 영역 중 추정 불확실성이 높은 영역을 방문하는 커버리지 경로를 생성하는 것이 목표이다. 이때, SLAM의 추정 불확실성이 높은 영역만 로봇이 지속해서 방문하게 되면, SLAM 불확실성이 누적 증가하기 때문에, 허용 가능한 불확실성 수치 이하로 유지되도록 루프 클로징 노드를 방문하는 제약조건(Constraints)을 둔다.
본 연구의 제안 점은 다음과 같이 요약된다.
- 1. 주어진 능동 SLAM을 위한 커버리지 경로 계획 문제와 제약조건을 정의하였고, 이를 풀기 위해 대표적인 휴리스틱(Heuristic) 방법인 개미 군집 최적화(Ant colony optimization)[10]와 유전 알고리즘(Genetic algorithm)[11]을 계층적 방법으로 접근하여 해결하였다.
- 2. 실험에서 생성된 커버리지 경로 길이의 총합과 불확실성에 대한 제약조건 준수 여부를 통해 제안한 방법이 개방 루프 방법(OL, Open Loop), 철저한 재방문(ER, Exhaustive Revisit), 스위칭 방법(SW, Switching)보다 향상된 결과를 주었음을 확인하였다.
본 논문의 남은 장은 다음 순서로 작성된다. 2장에서 관련 연구가 기술된다. 3장에서는 문제의 정의 및 제안한 방법을 설명한다. 4장에서는 실험 환경에서 제약조건을 만족하며 최적 경로를 얻게 되는 제안한 방법의 성능을 보이고 실험 결과를 분석한다. 5장에서는 논문을 요약한다.
II. 관련 연구
2.1 능동 SLAM
SLAM 문제는 센서로 측정된 오차와 가중치의 역할을 하는 공분산으로부터 최적의 상태변수를 추정하는 것이다[1][12]. 하지만 일반적인 SLAM 방법은 센서로부터 취득된 정보만 활용하기 때문에 로봇의 조작을 고려하지 않는 수동적인 접근 방법이다. 이와 반대로 능동적 접근법은 취득 정보의 향상을 위한 주행 전략을 고려한다[9].
능동 SLAM[2][9][13]은 완벽한 센서 위치 추정을 기반한 능동 매핑[14][15]과 주어진 환경 내에서 로봇의 자세를 추정하는 능동 위치 추정 문제[16][17] 를 통합하고 로봇이 알려지지 않은 환경에서 자율적으로 주행하는 것을 포함한다. 특히, 로봇의 자율적 주행은 SLAM 본연의 문제인 위치 추정 및 지도 표현의 불확실성을 줄이는 방향으로 제어된다. [18]에서는 예상되는 비용과 이익에 따라 새로운 영역을 탐사하거나 이미 본 영역을 재방문하는 탐사-활용(Exploration-Exploitation) 딜레마 문제를 다루었다. 이것은 불확실한 영역을 탐사하거나 아는 영역을 재방문하여 불확실성을 낮추는 두 선택지에 대한 딜레마를 의미한다.
이러한 능동 SLAM 문제에서는 딜레마를 해결하기 위한 의사결정이 중요하고 의사결정을 위한 유틸리티 함수의 정의가 중요하다. 이 함수는 로봇 주행 액션에 따른 비용과 이득을 수치화한다. 유틸리티 함수는 많은 경우 TOED(Theory of Optimal Experimental Design)의 기준에 따라 행렬 형태인 사후 공분산(Posterior covariance)이 스칼라값으로 나타내어지는 형태로 다음과 같이 계산된다[19]. 이 유틸리티 함수를 만족하는 로봇 주행 전략을 택하게 만든다. 최적 지표로는 대부분은 공분산 행렬의 대각합(Trace)인 A-최적성[20], 최대 최소 고유치인 E-최적성[4], 공분산의 행렬식인 D-최적성[21]으로 분류된다. 최근에는 T-최적성[22]을 이용한 경우도 많이 사용된다.
능동 SLAM에서 가장 중요한 가정 중 하나는 탐사가 진행됨에 따라 불확실성이 단조 증가(Monotonicity)한다는 것이다[9]. 하지만, A-최적성과 E-최적성의 유틸리티 함수에서는 환경 조건에 따라 이 특성이 반영되지 않았다. 하지만 같은 조건들에서 D-최적성은 이 가정이 유지됨을 보였다[23]. 따라서 본 연구에서도 탐사 및 커버리지 과정에서 불확실성의 단조성을 반영하기 위해 D-최적성을 유틸리티 함수로 활용하였다.
유틸리티 함수로부터 로봇 주행 전략은 모든 가지 수의 주행 액션 중 유틸리티 함수값의 최소 또는 최대를 만드는 최적 주행 액션을 찾는 문제로 접근한다[9]. 시각(Visual) SLAM에서 루프 클로징 부재에 의한 SLAM 오차 누적 현상을 해결하기 위해 보상 프레임워크를 사용하여 탐색과 재방문 간의 균형을 자동으로 조정하는 방법들이 있다[6][24]. [6]에서는 PDN(Perception-Driven Navigation) 방법이 제안되었고, 사용자가 정의한 허용 가능한 불확실성 수치를 넘을 경우 재방문을 강요하는 방식의 보상 프레임워크를 구성하였다. 비교군으로는 철저한 재방문 방법과 개방 루프 방법이 활용되었다. [24]의 연구에서는 [25]에서 제시한 스위칭 방법을 이용하였다. D-최적성의 결과로부터 문턱값을 설정하여 결과의 범위에 따라 탐사를 진행할 것인지 루프 클로징 영역을 재방문할 것인지를 스위칭하며 결정한다. 본 연구에서도 문턱값을 두고 허용가능한 불확실성을 넘지 않는 스위칭 접근법[24], 철저한 재방문 방법, 개방 루프 방법을 모두 비교군으로 두었다.
2.2 커버리지 경로 계획
로봇이 두 지점 사이를 이동할 때, 두 지점 사이를 잇는 최적 경로를 생성하는 과정을 경로 계획이라 한다[26]. 이 경로 계획은 환경 내 여러 위치를 방문하는 문제로 확장한 경우에, 커버리지 경로 계획(Coverage path planning)으로 정의될 수 있다[27]. 특히, 감시(Surveillance)와 같은 문제에서 커버리지 경로 계획은 로봇에 장착된 센서의 센싱 범위에 따라 주요 지점만 방문하는 커버리지 방법이 필요하다[28]. [29]에서는 다각형 장애물로 이루어진 환경에서 이 문제를 풀기위해 다각형의 꼭지점을 기준으로 지도를 분할하고 분할된 영역 내에 센싱 범위를 고려하여 노드를 생성하였다. 하지만 다각형의 가정과 최소 노드 생성 개수의 면에서 한계가 있었다. [30]에서는 다각형 외의 SLAM 환경에서도 점유된(Occupied) 영역에서 노멀 벡터(Normal vector)를 이용한 최적 노드 생성을 제안하였다. 본 연구에서도 이 방법을 토대로 불확실성이 높은 영역에서 방문할 노드를 생성하였다.
센싱 범위를 고려한 노드 생성이 완료되었다면, 노드들을 방문하기 위한 경로 계획이 필요하다. 이 노드들을 최소 비용으로 방문하는 문제는 외판원 문제(Traveling salesman problem)로 정의된다. 외판원 문제는 주어진 n개의 노드를 최단 길이로 방문할 경로를 찾는 것을 목표로 한다. 이 문제는 NP hard 문제로 n이 커질수록 지수적으로 증가하는 계산량으로 인해 최적해를 찾기 어렵다. 이를 해결하기 위한 대표적인 휴리스틱 기법으로 개미 군집 최적화[10], 유전 알고리즘[11] 등이 있다. 외판원 문제에 대해 유전 알고리즘은 초기 단계에서 빠른 수렴 특성을 보여준다. 그러나 피드백 메커니즘의 부재로 최종수렴까지 시간이 오래 걸리는 단점이 있다.
이는 유전 알고리즘이 n의 규모가 크지 않을 때 외판원 문제를 해결하는 데 탁월하다. 반면, 개미 군집 최적화는 페로몬 레벨이 부족한 초기 단계에서 수렴 특성이 좋은 편은 아니지만[20], n이 크고 복잡한 문제에 대해 최적의 결과를 얻을 수 있다는 이점을 제공한다. 이 이유는 페로몬의 축적으로 대표되는 긍정적인 피드백 메커니즘이 수렴 속도를 가속화 하여 개미 군집 최적화 방법의 복잡한 작업을 보다 효율적으로 처리할 수 있도록 한다[31]. 이러한 휴리스틱 방법들은 주로 단일 로봇 커버리지 경로 계획을 해결하기 위해 활용되어왔지만, 최근에는 다중 로봇의 커버리지 경로 계획 연구에도 활용되고 있다[32].
Ⅲ. 능동 SLAM을 위한 커버리지 경로 계획
본 연구에서는 능동 SLAM을 위한 최적 커버리지 경로 계획 문제를 다룬다. 먼저 이를 위한 문제 정의와 가정이 필요하다. 그리고 문제에서 다루는 제약조건도 정의되어야 한다. 이로부터 이를 해결하기 위한 전체 프레임워크가 제안된다.
3.1 문제 정의 및 가정
본 연구에서 풀고자하는 능동 SLAM 문제는 다음과 같이 정의된다.
- 1. 초기 SLAM을 수행하여 획득한 공분산 지형 지도로부터 불확실성이 높은 영역을 선정하고 불확실성이 높은 영역을 모두 커버리지 하는 것이 목표이다.
- 2. 로봇은 센서 범위를 가진 센서를 탑재하고 있기 때문에 방문 영역은 센서 범위를 고려하여 선정되어야 한다.
- 3. 커버리지 과정에서 불확실성은 선형적으로 증가하되, 허용 가능한 불확실성 이상이 되면 필터가 발산되는 제한조건을 둔다.
공분산 지형지도란 모든 격자에서의 공분산값이 존재하는 지도로 초기 SLAM을 수행하여 일부 위치별로 희귀(Sparse)하게 획득된 공분산 정보로부터 회귀(Regression)을 통해 얻은 공분산에 대한 지도를 의미한다[33]. 센서 범위를 고려한 방문 영역 선정은 앞서 언급한 바와 같이 노멀 벡터 기반의 노드 생성 방법을 이용한다[30]. 커버리지 경로 계획 과정에서 불확실성은 다음과 같이 선형적으로 증가됨을 가정한다[9].
| (1) |
N은 커버리지 경로의 방문 노드들의 집합이다. nk는 생성된 경로의 k번째 노드를 의미한다. Ck-1와 Ck는 각각 nk-1와 nk에서의 불확실성의 크기를 의미한다. pk,k-1는 D-최적 기준에 의해 계산된 노드 간 불확실성을 의미한다. 수식에서 알 수 있듯이 Ck는 갱신되며 루프 클로징이 가능한 공분산이 낮은 영역을 방문하는 경우, 루프 클로징 발생으로 ϵ0만큼의 낮은 불확실성을 가짐을 가정한다. 이를 이용한 제약조건은 다음과 같이 정의된다.
| (2) |
CThreshold은 허용 가능한 불확실성을 의미한다. 생성된 경로 내 연속적인 노드들의 불확실성의 합은 항상 허용 가능한 불확실성을 넘지 않는다.
불확실성을 표현하기 위한 유틸리티 함수는 다음과 같이 정의된다[9].
| (3) |
이때, ∑와 λk는 각각 n x n 행렬인 사후 공분산과 그 공분산의 k번째 고유치를 의미한다. p는 유틸리티 함수에 따라 결정되고 D-최적 기준의 경우 p = 0경우에 해당된다.
불확실성이 높은 영역에서 생성된 m개의 방문 노드는 방문 노드들의 집합 N={n1,n2,...,nm}으로 표현된다.
방문 노드 간에는 이동 거리를 가지게 되고 이는 유클리디안 거리(Euclidean distance)로 계산된다. 방문 노드 간 거리 행렬을 엣지 E로 둔다면 하나의 그래프 G가 구축된다. 구축된 그래프로부터 커버리지 경로 계획 문제는 다음과 같이 정의된다[34].
| (4) |
| (5) |
| (6) |
xij는 0 또는 1인 값으로 1인 경우 서로 다른 i와 j번째 노드가 연결됨을 의미하고, 0인 경우 연결되지 않음을 의미한다. 식 (3)을 만족하는 결과가 최적 커버리지 경로 생성 결과가 된다.
3.2 제안된 방법
제안된 방법은 불확실성이 높은 영역에서 센싱 거리를 고려한 방문 노드들을 모두 방문하며 동시에 제약조건을 만족하는 최적해를 한번에 찾는 것은 쉬운 문제가 아니다. 따라서 본 연구에서는 불확실성이 높은 영역에서 생성된 방문 노드를 모두 방문하는 최적 경로를 생성하는 문제와 생성된 경로로부터 제약조건을 만족하는 최적해를 찾는 두 가지 문제를 나누어 접근한다. 전체 구조는 불확실성이 높은 영역을 방문하기 위해 그래프를 구축하는 과정, 생성된 그래프에서 초기 커버리지 경로 계획을 통해 경로를 생성하는 과정, 제약조건을 만족하며 동시에 최적 커버리지 경로를 생성하는 단계들로 이루어져 있다.
커버리지를 위한 영역은 공분산 지형지도[33]에서 불확실성이 높은 영역으로 선정된다. 선정된 영역에서 노멀 벡터를 기반으로 센싱 거리를 고려한 노드들이 생성된다[30]. 생성된 노드 간 유클리디안 거리를 계산하여 엣지에 해당하는 행렬을 만든다. 이 노드들과 엣지로 부터 그래프가 구축된다.
구축된 그래프로부터 초기 커버리지 경로 계획은 휴리스틱 경로 생성 기법 중 대표적인 피드백 방법인 개미 군집 최적화 기법을 이용한다. 앞서 언급한 바와 같이 이 방법은 방문 노드의 개수 m이 클 때에도 m! 가지의 해 중 반복을 통해 가장 최적에 근접하는 해를 찾아주는 방법이다[32].
개미 군집 최적화 기반 커버리지 경로 계획은 다음과 같은 방법으로 진행된다. 주어진 노드들로부터 개미들이 초기화 규칙에 따라 무작위로 노드를 선택한다. 각 개미들은 상태전이규칙(State transition rule)에 따라 다음에 방문할 노드를 선택하고, 반복적인 탐색과정을 거친다. 이러한 과정을 거치는 동안 개미들은 지역 갱신 규칙(Local updating rule)에 따라 방문한 각 노드에 페로몬 양을 갱신한다. 패로몬 양을 갱신하게 되면 이동 거리가 짧을수록 패로몬의 증발 확률이 감소하게 된다. 그 후 모든 개미들의 탐색과정이 종료되면 전역 갱신 규칙(Global updating rule)에 따라 다시 페로몬 양이 갱신된다.
갱신 시에는 𝛼(Pheromone coefficient), 𝛽(Heuristic coefficient), 𝜌(Pheromone’s evaporation rate)와 같은 파라미터에 의해 갱신의 양이 결정된다. 위의 과정을 반복하게 되면 길이가 긴 경로의 페로몬은 증발하게되고 짧은 경로의 패로몬 정보만 남게된다. 결국, 각 개미들은 가까운 노드를 선택하려는 휴리스틱 정보와 많은 양의 페로몬을 가진 노드를 선택하려는 페로몬 정보에 따라 탐색 경로를 완성한다. 이러한 과정은 수렴이 될 때까지 반복된다. 개미 군집 최적화의 각 파라미터는 [36]의 성능 분석 결과를 참고해 선정한다.
개미 군집 최적화로 획득된 경로는 [6]의 개방 루프 조사 방법과 유사한 접근으로 제약조건을 만족하지 못한다. 왜냐하면, 해당 경로는 불확실성이 높은 영역에서 추출된 m개의 노드 N만 반영한 결과이기 때문이다. 그림 1(a)는 개미 군집 최적화만 이용한 개방 루프 결과를 보여준다. 따라서 제약조건을 만족시키기 위해 그림 1(b)와 같이 철저한 재방문 기법을 사용할 수 있다. 하지만 이 방법은 그림과 같이 로봇의 커버리지 경로의 거리가 아주 길어지는 단점이 있다. 그림 1(c)는 개미 군집 최적화 결과에서 제약조건을 만족하지 못하는 구간에 불확실성이 낮은 루프 클로징 노드를 방문하는 경로를 삽입하는 방법이 있다. 이는 이전의 연구들[24][25]에서도 유사한 방식으로 택한 방법이다. 하지만 이 방법은 제약조건을 만족하며 동시에 상대적으로 낮은 경로 길이를 가지지만, 최적의 경로 길이는 보장하지는 못한다.
Coverage path planning approaches for active SLAM
그림 1(d)는 제약조건을 만족하며 최적 경로 길이를 가진 제안한 방법이다. 그림 1에서 알아본 바와 같이 최적 경로 길이를 생성하기 위해 최적 경로 계획을 위한 문제는 다음과 같이 정의할 수 있다. 만약, 그림 2와 같이 불확실성이 높은 영역에서 방문해야할 노드가 1-6까지로 정의되어 있고, 각 노드에 가장 가까운 루프 클로징을 만드는 A, B, C, D, E의 노드가 있는 경우를 가정한다. 철저한 재방문 방법은 ‘1→A→2→B→3→C→4→D→5→E→6’의 형태로 각 노드를 방문하게 된다. 그림 1(c)와 같은 스위칭 방식의 접근법은 1→2→2→3→3→... 과 같은 방식으로 A, B, C등의 루프 클로징 노드들을 바로 방문하지 않는다. 하지만, 만약 노드 4에서 허용된 불확실성 수치를 넘는다면, 1→2→2→3→3→C→4→...와 같은 형태의 경로를 계획한다.
Example of coverage path planning based on the constraint. Additional green transit nodes are assigned to satisfy the constraint on the path (1→2→3→4→5→6) generated by the open loop method
하지만 스위칭 방법은 경로 길이 면에서 조건을 만족하는 다른 커버리지 경로보다 더 좋은 해임을, 즉 최적임을 보장할 수 없다. 예를 들어 제약조건을 만족시키기 위한 노드 nk에서 가장 가까운 루프 클로징 노드와의 거리가 길고, 노드 nk-1에서 가장 가까운 루프 클로징 노드까지의 거리가 매우 짧다면 아직 제약조건을 고려하지 않아도 되는 노드에서 불확실성을 많이 줄여 이동할 수 있기 때문이다.
따라서 본 연구에서는 그림 2와 같이 개방 루프 방법으로 결정된 커버리지 경로에서 개별 노드별로 루프 클로징 노드를 추가 방문을 할 것인지 말 것인지에 대한 문제를 정의한다. 즉, 그림 2의 녹색 부분들에 들어갈 해를 찾는 방법으로 기존 경로(빨간색)로 이동할 것인지 루프 클로징 노드로 이동할 것인지 이진 결정 형태로 접근한다. 이 경우의 가짓수는 2m-1가지로 전체 노드 개수 m에 따라 무수히 많은 해를 확인하여야 한다. 따라서 이를 풀기 위해 유전 알고리즘을 이용하였다. 초기 경로(염색체) N1과 N2가 주어진다면, 교배가 수행된다(교배율: RCross). 이때 알고리즘의 진화 방향은 경로 비용이 감소하는 방향으로 진행되고, 이것은 그래프 엣지의 합으로 계산된다. 유전 알고리즘은 지역 최소(Local minima) 문제를 해결하기 위해 RMu 만큼의 확률로 염색체의 돌연변이가 수행된다. 또한, 병렬 연산을 위한 염색체의 개수 mch도 사전에 정의되어 활용된다. 파라미터는 [37]의 연구를 기반으로 설정하였다.
Ⅳ. 시뮬레이션
성능 평가를 위한 시뮬레이션은 실제 2개의 환경을 대상으로 진행되었다. 각 환경 지도에서 취득된 점유 격자 지도와 공분산 지형지도는 그림 3과 같다. 점유 격자 지도는 SLAM으로 생성된 지도로부터 획득되며, 흰색으로 표현된 부분은 로봇이 이동 가능한 영역이다. 공분산 지형지도는 SLAM을 통해 추정한 위치의 공분산으로부터 회귀 방법을 통해 획득된다. 그림의 연한 회색 부분은 불확실성이 높은 영역이고, 진한 회색의 영역은 불확실성이 낮은 영역이다.
A and B environments, occupancy grid maps and covariance terrain maps. The robot can move in the white area of the occupancy grid map, and the covariance terrain map represents areas with high (light grey) and low (dark gray) uncertainty
4.1 비교 방법 및 성능 평가 기준
앞서 언급한 바와 같이 성능 평가에 사용된 방법은 개방 루프 방법, 철저한 재방문 방법, 스위칭 방법, 제안한 방법 총 4가지이다. 각 방법에 대해 생성된 커버리지 경로의 총 길이(lTotal), 최대 불확실성 수치가 CThreshold를 넘는지에 대한 조건만족 여부, 수행시간(Tcycle)과 불확실성 수치의 평균값(CAverage) 4가지를 성능 평가 기준으로 두었다.
노드 생성을 위한 센싱 범위는 A환경에서 4m, B환경에서 3m로 두었으며 노드 간 최대 이동거리는 센싱 범위와 동일하다. 두 노드 간의 불확실성 증가량 ρk,k-1(식(1) 참고)은 노드 간 거리 Ek,k-1에 비례하므로 센싱 범위가 큰 A 환경에서 조금 더 큰 폭의 불확실성 증가를 보인다. 따라서 CThreshold는 A환경에서 120, B환경에서 80으로 설정하였다. 또한, 루프 클로징 노드에 방문하였을 때 초기화되는 불확실성 ϵ0는 0으로 설정하였다.
4.2 시뮬레이션 결과 분석
각 환경에 각 방법을 적용한 시뮬레이션 결과는 그림 4와 같다. 그림 4(a)-(d)는 A환경에서의 각 방법의 커버리지 경로 생성 결과이다. 그리고 그림 4(e)-(h)는 B환경에서의 각 방법의 커버리지 경로 생성 결과이다. 그림 4(a)와 그림 4(e)는 제약조건을 고려하지 않은 커버리지 경로 생성의 결과로 주어진 영역만을 커버리지하는 최적의 경로를 보여준다.
Coverage path planning results according to environments and methods
그림 4(b)와 그림 4(f)는 매 노드마다 루프 클로징 노드를 방문한 결과를 보여준다. 제약조건을 만족하되 경로의 길이가 아주 길어지는 형태이다. 그림 4(c)와 그림 4(g)는 스위칭 방법의 결과로 불확실성 수치가 허용 가능한 불확실성 수치에 다가갔을 때 루프 클로징 노드를 방문한다. 제안한 방법인 그림 4(d)와 그림 4(h)는 스위칭 방법과 유사한 경로를 보여주지만, 최적화 결과에 따라 루프 클로징 방문 시점과 위치가 차이가 있다. 그림의 시각적 결과를 명확히 비교하기 위해 다음 표를 통해 각 방법의 정량적 수치를 비교하며 세부적으로 분석한다.
표 1은 성능 평가 기준에 대한 각 방법의 정량적 수치를 나타낸다. lTotal면에서 개방 루프 방법(OL)의 경우 유일하게 루프 클로징 노드를 방문하지 않고 커버리지 경로 계획만 수행하기 때문에 모든 환경에서 가장 짧은 커버리지 경로 길이를 가진다(A환경 1329, B환경 738). 철저한 재방문 방법(ER)은 매 노드마다 루프 클로징 노드를 방문하며 가장 긴 경로 길이를 (A환경 4650, B환경 2127) 가져 경로 길이 측면에서 가장 비효율적인 성능을 보여준다.
Performance evaluation results
스위칭 방법(SW)은 철저한 재방문 방법과 비교하면 약 절반 정도의 짧은 경로 길이를 가진다. 제안된 방법은 루프 클로징 노드를 전혀 방문하지 않는 개방 루프 방법에 비해 길지만 다른 두 방법에 비해 짧은 경로 길이를 가진다(A 환경 1992, B환경 1068). 이러한 이유는 유전 알고리즘에 의해 최적 루프 클로징 노드 방문 시점을 결정하기 때문에 그 결과가 반영된 것으로 해석된다.
Ck에 대한 제약조건의 만족 여부는 개방 루프 방법을 제외한 나머지 세 방법 모두 만족함을 보였다.
그림 5는 시간에 따른 Ck의 변화를 보여준다. 개방 루프 방법은 점선으로 표기된 제약조건인 CThreshold을 넘어 발산한다. 나머지 세 방법은 제한된 Ck를 가진다. 특히 철저한 재방문 방법은 매번 루프 클로징 노드를 방문하며 가장 낮은 Ck값을 유지한다.
Ck graph over k according to coverage path planning methods
각 방법의 평균 수행시간 Tcycle는 제약조건을 고려하지 않는 개방 루프 방법이 가장 짧은 값을 가졌다. 제안된 방법은 제약조건을 고려한 최적화 시간이 필요하기 때문에 실행 시간이 가장 길다. 그럼에도 불구하고, 전체 실행 시간에 비해 6% 미만의 낮은 실행 시간 증가율을 보인다.
앞선 정량적 평가 결과를 이해하기 위해 표 2에서 각 방법을 통해 방문한 노드의 개수와 형태를 알아본다. n(N)와 n(NLoop)는 각각 불확실성이 높은 영역에서 생성된 방문 노드 개수와 제약조건을 만족시키기 위한 루프 클로징 노드 방문 횟수를 의미한다. 개방 루프 방법은 루프 클로징 노드를 방문하지 않으므로 0개의 n(NLoop)를 가진 것을 보여준다.
Total number of visited nodes
철저한 재방문 방법은 n(N)-1 만큼의 루프 클로징 노드 방문 횟수를 가졌다. 스위칭 방법과 제안한 방법은 동일한 루프 클로징 노드 방문 횟수를 가져 조건을 만족하며 철저한 재방문 방법에 비해 낮은 경로 길이를 가질 수밖에 없음을 알 수 있다.
4.3 각 방법의 불확실성 수치 변화
시뮬레이션에 적용한 4가지 방법은 불확실성 수치 Ck의 변화에 따라 서로 다른 대응 방법을 갖고 있다. 이를 위해 4가지 방법의 k에 따른 Ck의 변화를 확인하고 구조적 특성에 대해 분석한다. 앞선 그림 5는 A환경에서 각 경로 계획 방법들의 Ck 변화를 보여준다. 개방 루프 방법의 경우 로봇의 이동함에 따라 Ck 수치는 단조 증가하는 것을 볼 수 있다. 이는 불확실성 제약조건에 대한 대응이 없기 때문이다. 철저한 재방문 방법은 매번 루프 클로징 노드를 방문하기 때문에 Ck가 k에 따라 누적되지 않음을 알 수 있다. 불확실성의 면에서는 가장 작은 값을 유지함을 알 수 있다. 스위칭 방법은 철저한 재방문 방법에 비해 높은 불확실성을 가지지만 가질 수 있다.
표 3은 제안한 방법과 유사한 스위칭 방법과 제안한 방법의 CAverage는 수치 비교표이다. A환경에서 CAverage 스위칭 방법이 191.11, 제안한 방법이 189.2으로 1.91만큼 낮은 수치를 보였고, B환경에서도 제안한 방법이 기존 스위칭 방법보다 4.98만큼 낮은 수치를 보였다.
CAverage of SW and proposed methods
본 연구에서는 능동 SLAM을 위한 최적 커버리지 경로 계획 방법이 제안되었다. 능동 SLAM을 위해, 먼저 초기 SLAM에 의해 생성된 지도와 로봇 자취의 공분산 크기에 따른 공분산 지형지도를 생성하였다. SLAM 지도와 공분산 지형 지도로부터 공분산이 높은 영역이 선택되고 해당 영역을 센싱 거리를 고려하여 방문지점(노드)이 생성되었다. 대표적인 휴리스틱 기법인 개미 군집 최적화 방법을 이용하여 이 노드들을 모두 방문할 수 있는 로봇 경로를 생성하였다. 그리고 공분산에 대한 제약조건을 만족하기 위해 방문 시점과 노드가 추가 할당되었고 유전 알고리즘을 통해 최적화가 진행되었다. 실제 환경에서 획득한 두 가지 SLAM 지도와 공분산 지형지도를 토대로 제안된 방법과 기존 접근 방법들과의 비교가 수행되었다. 제안된 방법은 제약조건을 만족하는 방법 중 가장 짧은 경로 길이를 보였고, 특히 스위칭 방법보다 작은 평균 불확실성 수치를 통해 우수한 능동 SLAM을 위한 경로 계획 성능을 보여주었다. 향후 제안한 방법을 실시간 능동 SLAM 문제에 적용하여 정확한 지도를 작성하고자 한다.
Acknowledgments
이 연구는 2021년 국립대학 육성사업비로 지원되었음
References
-
C. Cadena, L. Carlone, H. Carrillo, Y. Latif, D. Scaramuzza, J. Neira, I. Reid, and J. J. Leonard, "Past, Present, and Future of Simultaneous Localization And Mapping: Towards the Robust-Perception Age", IEEE Transactions on Robotics, Vol. 32, No. 6, pp. 1309-1332, Dec. 2016.
[https://doi.org/10.1109/TRO.2016.2624754]
-
M. F. Ahmed, K. Masood, V. Fremont, and l. Fantoni, "Active SLAM: A Review on Last Decade", Sensors, Vol. 23, No. 9, pp. 1-29, Sep. 2023.
[https://doi.org/10.3390/s23198097]
- H. Chernoff, "Locally optimal designs for estimating parameters", The Annals of Mathematical Statistics, pp. 586-602, Dec. 1953.
- S. Ehrenfeld, "On the efficiency of experimental designs", The Annals of Mathematical Statistics, Vol. 26, No. 2, pp. 247-255, Jun. 1955.
- A. Wald, "On the efficient design of statistical investigations", The Annals of Mathematical Statistics, Vol. 14, No. 2, pp. 134-140, Jun. 1943.
-
A. Kim and R. Eustice, "Active visual SLAM for robotic area coverage: Theory and experiment", The International Journal of Robotics Research, Vol. 34, No. 4-5, pp. 457-475, Nov. 2014.
[https://doi.org/10.1177/0278364914547893]
-
C. Shi, X. Chen, J. Xiao, B. Dai, and H. Lu, "Fast and Accurate Deep Loop Closing and Relocalization for Reliable LiDAR SLAM", arXiv:2309.08086, Sep. 2023.
[https://doi.org/10.48550/arXiv.2309.08086]
-
P. Newman and K. Ho, "SLAM- Loop Closing with Visually Salient Features", Proc. of the 2005 IEEE International Conference on Robotics and Automation, Barcelona, Spain, pp. 635-642, Apr. 2005.
[https://doi.org/10.1109/ROBOT.2005.1570189]
-
J. A. Placed, J. Strader, H. Carrillo, N. Atanasov, V. Indelman, L. Carlone, and J. A. Castellanos, "A survey on active simultaneous localization and mapping: State of the art and new frontiers", IEEE Transactions on Robotics (T-RO), Vol. 39, No. 3, pp. 1686-1705, Mar. 2023.
[https://doi.org/10.1109/TRO.2023.3248510]
- D. Asmar, A. Elshamli, and S. Areibi, "A Comparative Assessment of ACO Algorithms Within a TSP Environment", Dynamics of Continous Discrete and Impulsive Systems-Series B-Applications & Algorithms 1, pp. 462-467, 2005.
- S. A. Haroun, B. Jamal, and E. H. Hichan, "A Performance Comparison of GA and ACO Applied to TSP", IJournal of Computer Applications, Vol. 117, No. 20, pp. 28-35, May 2015.
-
N. K. Dhiman, D. Deodhare, and D. Khemani, "Where Am I? Creating Spatial Awareness in Unmanned Ground Robots Using SLAM: A Survey", Sadhana, Vol. 40, pp. 1385-1433, Aug. 2015.
[https://doi.org/10.1007/s12046-015-0402-6]
-
H. Carrillo, I. Reid, and J. A. Castellanos, "On the comparison of uncertainty criteria for active SLAM", 2012 IEEE International Conference on Robotics and Automation, Saint Paul, MN, USA, pp. 2080-2087, May 2012.
[https://doi.org/10.1109/ICRA.2012.6224890]
-
C. Connolly, "The determination of next best views", Proc. 1985 IEEE International Conference on Robotics and Automation, St. Louis, MO, USA, Vol. 2, pp. 432-435, Mar. 1985.
[https://doi.org/10.1109/ROBOT.1985.1087372]
-
R. Zeng, Y. Wen, W. Zhao, and Y. J. Liu, "View planning in robot active vision: A survey of systems, algorithms, and applications", Computational Visual Media, pp. 1-21, Aug. 2020.
[https://doi.org/10.1007/s41095-020-0179-3]
-
D. Fox, W. Burgard, and S. Thrun, "Active Markov localization for mobile robots", Robotics and Autonomous Systems, Vol. 25, No. 3-4, pp. 195-207, Nov. 1998.
[https://doi.org/10.1016/S0921-8890(98)00049-9]
-
G. Borghi and V. Caglioti, "Minimum uncertainty explorations in the self-localization of mobile robots", IEEE Trans. on Robotics and Automation, Vol. 14, No. 6, pp. 902-911, Dec. 1998.
[https://doi.org/10.1109/70.736774]
- S. B. Thrun and K. M ¨oller, "Active exploration in dynamic environments", Advances in Neural Information Processing Systems, Vol. 4, pp. 531-538, 1991.
- J. Kiefer, "General equivalence theory for optimum designs (approximate theory)", The Annals of Statistics, Vol. 2, No. 5, pp. 849-879, Sep. 1974.
- H. Chernoff, "Locally optimal designs for estimating parameters", The Annals of Mathematical Statistics, Vol. 24, No. 4, pp. 586-602, Dec. 1953.
- A. Wald, "On the efficient design of statistical investigations", The Annals of Mathematical Statistics, Vol. 14, No. 2, pp. 134-140, Jun. 1943.
-
F. Chen, J. D. Martin, Y. Huang, J. Wang, and B. Englot, "Autonomous exploration under uncertainty via deep reinforcement learning on graphs", 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, NV, USA, pp. 6140-6147, Oct. 2020.
[https://doi.org/10.1109/IROS45743.2020.9341657]
-
H. Carrillo, Y. Latif, M. L. Rodriguez-Arevalo, J. Neira, and J. A. Castellanos, "On the monotonicity of optimality criteria during exploration in active SLAM", 2015 IEEE International Conference on Robotics and Automation (ICRA), Seattle, WA, USA, pp. 1476-1483, May 2015.
[https://doi.org/10.1109/ICRA.2015.7139384]
-
Y. Chen, S. Huang, and R. Fitch, "Active SLAM for Mobile Robots With Area Coverage and Obstacle Avoidance", IEEE/ASME Transactions on Mechatronics, Vol. 25, No. 3, pp. 1182-1192, Jun. 2020.
[https://doi.org/10.1109/TMECH.2019.2963439]
-
Y. Chen, S. Huang, R. Fitch, and J. Yu, "Efficient active SLAM based on submap joining, graph topology and convex optimization", 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, QLD, Australia, pp. 5159-5166, May 2018.
[https://doi.org/10.1109/ICRA.2018.8460864]
-
Z. Tang and H. Ma, "An overview of path planning algorithms", IOP Conference Series: Earth and Environmental Science, Vol. 804, No. 2, pp. 1-10, 2021.
[https://doi.org/10.1088/1755-1315/804/2/022024]
-
E. Galceran and M. Carreras, "A survey on coverage path planning for robotics", Robotics and Autonomous Systems, Vol. 61, No. 12, pp. 1258-1276, Dec. 2013.
[https://doi.org/10.1016/j.robot.2013.09.004]
-
S. Lee, "An Efficient Coverage Area Re-Assignment Strategy for Multi-Robot Long-Term Surveillance", IEEE Access, Vol. 11, pp. 33757-33767, Mar. 2023.
[https://doi.org/10.1109/ACCESS.2023.3260622]
-
P. Fazli, A. Davoodi, and A. K. Mackworth, "Multi-robot repeated area coverage", Autonomous Robots, Vol. 34, No. 4, pp. 251-276, Mar. 2013.
[https://doi.org/10.1007/s10514-012-9319-7]
-
D. Noh, et al., "MASS: Multi-agent scheduling system for intelligent surveillance", 2022 19th International Conference on Ubiquitous Robots (UR), Jeju, Korea, pp. 252-257, Jul. 2022.
[https://doi.org/10.1109/UR55393.2022.9826281]
-
P. Wang, J. Bai, and J. Meng, "A Hybrid Genetic Ant Colony Optimization Algorithm with an Embedded Cloud Model for Continuous Optimization", Journal of Information Processing Systems, Vol. 16, No. 5, pp. 1169-1182, Oct. 2020.
[https://doi.org/10.3745/JIPS.01.0059]
-
J. Gong and S. Lee, "Hierarchical Area-Based and Path-Based Heuristic Approaches for Multirobot Coverage Path Planning with Performance Analysis in Surveillance Systems", Sensors, Vol. 23, No. 20, pp. 1-19, Oct. 2023.
[https://doi.org/10.3390/s23208533]
- J. Kim, B. Lee, H. Kim, D. Kim, S. Kim, H. Kim, and S. Lee, "A Covariance Topography Mapping Method using Nearest Neighbor Interpolation in 3D SLAM", Proc. of Korea Artificial Intelligence Conference, Jeju, Korea, Nov. 2023.
-
I. Kara and T. Bektas, "Integer linear programming formulations of multiple salesman problems and its variations", European Journal of Operational Research, Vol. 174, No. 3, pp. 1449-1459, Nov. 2006.
[https://doi.org/10.1016/j.ejor.2005.03.008]
-
J. Gong and S. Lee, "A Study on Performance Comparison of Combination of Genetic Algorithm and Ant Colony Optimization for Multi-robot Coverage Path Planning", Journal of KIIT, Vol. 21, No. 6, pp. 55-65, May 2023.
[https://doi.org/10.14801/jkiit.2023.21.6.55]
- A. Bexhepi, A. Maxhuni, and A. Dika, "Analysis of the impact of parameters values on the Genetic Algorithm for TSP", International Journal of Computer Science Issues (IJCSI), Vol. 10, No. 1, pp. 158-164, Jan. 2013.
- D. Asmar, A. Elshamli, and S. Areibi, "A Comparative Assessment of ACO Algorithms Within a TSP Environment", Dynamics of Continous Discrete and Impulsive Systems-Series B-Applications & Algorithms, Vol. 1, pp. 462-467, 2005.
2023년 : 국립금오공과대학교 전자공학부(공학사)
2023년 ~ 현재 : 국립금오공과대학교 전자공학과 석사과정
관심분야 : 다중 로봇 커버리지, 다중 로봇 리스케줄링
2015년 : 서울대학교 전기컴퓨터학부(공학박사)
2015년 ~ 2018년 : 삼성전자 생산기술연구소 책임연구원
2018년 ~ 2023년 : 국립금오공과대학교 전자공학부 조교수
2023년 ~ 현재 : 국립금오공과대학교 전자공학부 부교수
관심분야 : 다중 로봇 SLAM, 다중 로봇 커버리지 경로 계획