논문

[obstacle][PRM] Autonomous UAV Exploration of Dynamic Environments Via Incremental Sampling and Probabilistic Roadmap

정지홍 2025. 6. 29. 06:09

초록

  • 자율 탐사에게는 로봇이 계속해서 여러 경로를 생성하기를 원한다.
    • 이때, rrt와 같은 샘플링 기반 방법을 사용하면 효과적이다. 하지만 이전 계획에서 얻은 샘플 정보를 활용하지 못해서 불필요한 연산이 발생한다.
    • 또한, real - time으로 동작이 가능하지만, 탐사 성능을 수치로 나타낸 연구는 드물다.
    • ==> 이러한 단점을 개선하고자, 저자는 점진적 샘플링 + PRM을 한 새로운 dynamic exploration planner를 제안한다.
  • DEP
    • 저자가 제안한 샘플링 방법은, 탐사된 영영에 노드를 점진적으로 추가하고, 고르게 분포시켜서, 최적의 경로를 확보한다.
    • 탐색 시간을 단축하고 안전성 보장을 위해서, planner는 국소적으로 경로를 최적화하고, 유클리드 부호 거리 함수 맵을 기반으로 스무딩을 한다.
    • multi-query planner인 prm을 활용함으로, 플래너는 동적 장애물을 회피하는 경로를 빠르게 찾을수 있다.
    • 실험 결과도 우수함을 보여줌.

 

 

1. INTRODUCTION

  • 자율 탐사 기술은 여러 장점때문에 주목 받는중임.
    • 자율 탐사에 사용되는 UAV는 공통적으로 풍부한 경로를 요구한다.
  • 온라인 탐사 문제는 일련의 정보성 센서 위치를 어떻게 결정할 것인지로 볼 수 있다[1].
  • 초기의 프론티어 탐사(frontier exploration) 기법은 2D 지상 로봇이 경계선(frontier)을 탐색함으로써, 미지 영역을 효율적으로 인지할 수 있음을 입증하였다2].
    • 이후 연구들[3],[4]은 이 개념을 항공 로봇으로 확장하였지만, 고차원 계획(high-dimensional planning)에서 계산 비용이 매우 높아지는 문제를 존재한다.
    • 하지만 sampling 기반 방법은 계산 효율성과 정보 흭득 기법 때문에 UAV 탐사에서 선호된다.
      • sampling기반의 방법중 single - query planner의 하나인 RRT는 한번의 반복에서 수행되는 샘플링 만으로는 전체 공간을 포괄할 수 없다는 단점이 있다. 그래서 최적의 path를 선택하는데 방해된다.
        또한 이전에 반복에서, 이미 샘플링한 영역을 반복해서 평가하니 계산이 낭비된다.
    • 탐사는 본질적으로 반복적이니 multi - query planner가 더 적합할 수 있다.
      • 일부의 트리 기반 방법이 노드를 지속적 추가 or 과거 정보 재사용을 하지만, 여전히 동적인 장애물에 대한 유연성은  부족하다.
        • 이러한 문제를 해결하고자, 저자는 DEP을 제안한다.
  • DEP은 전통적인 방법과 다르게, 점진적 샘플링으로 탐색공간의 노드 커버리지를 효과적으로 개선한다.
  • node's utility는 고유 속성으로 저장 및 갱신되니, 동적 장애물을 회피하기 위한 경로 생성이 빠르게 수행된다.
    • 여러 경로 후보에 대한 gain rate 평가를 통해서, planner의 greedy behavior를 방지한다.
    • ESDF 기반의 최적화를 적용해서, 경로 실행 시간을 최소화하고, 장애물과의 허용 거리를 유지한다.
  • DEP는 벤치마크 알고리즘들을 능가함을 보여준다.
    • 그림 1을 보면, 사무실 환경에서 roadmap시각화와 함께 동작중인 DEP planner의 예시를 보여준다.
  • 아래는 논문의 주요 기여점들이다.
    • 1. 탐사를 위한 점진적 PRM
      • 기존의 온라인 탐사 알고리즘과 다르게, 저자는 점진적으로 성장하는 PRM에서 샘플된 노드를 고르게 추가하고, 이득 평가를 수행한다.
        로봇이 수행할 path는 이러한 node의 utility를 기반으로 하며, 최고 효용을 가지는 후보를 선택한다.
    • 2. 동적 환경에서의 안전성 보장
      • 저자들이 알기로는, DEP가 동적 장애물을 포함한 미지의 환경에서 탐사 안전성을 명시적으로 고려한 최초의 방법이다.
        점진적 PRM과 ESDF기반 경로 최적화는 빠른 재계획 속도와 장애물로부터의 안전 거리를 동시에 보장한다.
    • 3. 높은 탐사 효율성
      • 고전적 방법[2]과 최근 최첨단 플래너들[5],[7]을 대상으로 한 비교 실험을 통해, 제안하는 DEP 플래너가 탐사 효율성에서 가장 우수함을 확인함.

 

 

 

2. RELATED WORK

  • 자율 탐사 알고리즘은 크게 프론티어 기반 방법(frontier-based method)과 샘플링 기반 방법(sampling-based method)으로 나눌 수 있다.
  • 초기 프론티어 탐사는 2D 지상 로봇에서 높은 효율성을 입증하였으며[2], 이후 빠르게 비행하는 UAV 탐사[13]와 3D 재구성[14]에도 확장되었습니다.
    • 반면, 샘플링 기반 방법은 프론티어가 아닌 정보 이득(information gain)을 탐사 휴리스틱으로 사용하여 최적의 관측 지점을 선택합니다[1],[15],[16].
      이 방식은 로봇 차원이 커져도 계산량이 크게 증가하지 않기 때문에 UAV 응용에 선호됩니다.
  • 정보 이론적 방법(information-theoretic method)은 정보 이득 평가를 위한 정교한 방식을 제공하며[17], 데이터 기반 접근(data-driven approach)도 시도되었으나 다양한 환경에 일반화하기 어렵다는 한계가 있습니다[18].
  • 최근에는 이종 로봇(heterogeneous robot)을 활용한 탐사 연구도 활발히 진행되고 있습니다[19].
  • 샘플링 기반 방법은 최근 UAV 탐사 분야에서 더욱 인기를 끌고 있습니다.
    • 리서딩 호라이즌 넥스트 베스트 뷰(RH-NBV , Receding horizon next-best-view ) 플래너는 로봇 탐사에 신뢰할 수 있는 해법을 제시합니다[5].
    • 이 방법은 트리를 로봇의 현재 위치에서부터 확장한 뒤, 정보 이득이 가장 높은 가지(branch)를 선택하고, 로봇은 그 가지의 첫 번째 세그먼트를 실행합니다.
    • 이 접근법에 영감을 받은 다양한 최신 연구들이 존재합니다.
      • 예컨대, [9]에서는 시각적 주목도가 높은 객체를 고려하기 위해 살리언시 이득(saliency gain)을 최적화하는 2단계 플래너를 도입합니다.
      • 샘플링 효율을 높이고 플래너가 지역 최솟값(local minima)에 빠지지 않도록 하기 위해, [6]은 이전 샘플들로부터 생성된 히스토리 그래프(historical graph)를 저장하여 탐사 잠재력(exploration potential)을 평가하며, 이와 함께 더 나은 이득 추정을 위한 자세(orientation) 최적화도 수행합니다.
      • 마찬가지로, [7]은 RH-NBV와 프론티어 기반 알고리즘을 결합하여 지역 최솟값에서 조기 종료되는 문제를 방지하는 자율 탐사 플래너(AEP)를 제안합니다.
        • 이 플래너는 목표가 될 프론티어를 캐싱(cache)하고, 캐시된 노드를 이용해 가우시안 프로세스(Gaussian process)로 정보 이득을 예측합니다.
      • [8]에서는 RRT* 기반 플래너가 리와이어링(rewiring)을 통해 트리를 지속적으로 성장·유지하며, 최적 가지에 속하지 않은 나머지 노드들도 버려지지 않도록 경로를 세밀하게 다듬습니다.
        • 이들의 TSDF 기반 재구성 이득(reconstruction gain)은 다른 샘플링 기반 방법과 비교해 3D 재구성 오차가 가장 낮게 나타났습니다.
      • 한편, 매핑 및 위치 추정 오차를 줄이기 위해 [20], [21], [22]에서는 계획 단계에서 위치 추정 불확실성(localization uncertainty)을 고려하고 있습니다.

 

 

 

III. PROBLEM DESCRIPTION

 

 

 

Problem I: Autonomous Exploration

 

 

Problem II: Dynamic Obstacle Avoidance

 

 

IV. PROPOSED METHOD

제안하는 플래너는 그림 2에 보이는 roadmap manager와 trajectory module로 나뉘며, 다음 네 단계로 구성됩니다:

  1. 로드맵 구성(roadmap construction)
  2. 노드 평가 및 갱신(node evaluation and update)
  3. 궤적 생성(trajectory generation)
  4. ESDF 기반 최적화(ESDF-based optimization)

-- 1단계에서는 이전 반복에서 사용된 로드맵에 새로운 노드를 점진적으로 추가하되, 노드가 영역 전체에 고르게 분포되도록 합니다. 이 과정은 그림 3에 시각화되어 있습니다.
-- 2단계에서는 새로 추가된 노드와 기존 노드의 정보 이득(information gain)을 평가하거나 갱신합니다.
-- 3단계에서 플래너는 각 노드에 대한 탐사 점수(exploration score)가 가장 높은 경로를 선택해 궤적을 생성합니다.
-- 4단계에서는 생성된 궤적에 대해 ESDF(Euclidean Signed Distance Function) 지도를 이용해 실행 시간을 더욱 단축하고 장애물과의 안전 거리를 보장하도록 최적화를 수행합니다.

-- 동적 장애물과 마주쳤을 때는, 이미 구축된 로드맵을 활용하여 빠르게 충돌 없는 새로운 궤적을 생성함으로써 재계획 시간을 최소화합니다.

 

 

A. RoadmapConstruction (로드맵 구성)

  • 점진적 PRM은 새로운 영역이 관측될 때마다 노드를 추가해야 합니다.
  • 환경 내 위치의 탐사 유틸리티를 정확히 추정하려면, 로드맵 노드가 관측된 영역을 포괄적으로 커버해야 합니다.
    • ( 탐사 유틸리티 : 로봇이 어떤 위치나 경로 조각을 선택했을 때 얻을 수 있는 ‘탐사 성과’를 수치화한 값 )
      • 탐사 유틸리티의 요소에는 information gain , Movement cost , safety , dynamic factors등이 존재
  • 또한 로드맵 품질을 보장하기 위해 노드들이 고르게 분포되어야 합니다.
  • 단순 무작위 샘플링은 이전에 관측된 영역에 노드가 과밀해지고 새로 관측된 영역에는 희소해지는 문제를 일으킵니다.
  • 따라서 본 연구에서는 두 단계 샘플링 전략을 채택합니다.
    • 먼저 로봇의 현재 위치 근처 국소 영역에서 랜덤 샘플을 뽑고, 그다음에 전역 영역에서 샘플링을 수행합니다.
    • 이렇게 하면 로봇 주변의 새로 관측된 영역을 더 잘 커버할 수 있습니다.
    • 샘플 개수로 직접 종료 조건을 두지 않고, 로드맵이 전역적으로 “포화(saturated)”되었을 때 샘플링을 멈춥니다.
  • 알고리즘 1은 이 점진적 PRM 샘플링 전략을 보여줍니다.
    • 랜덤 샘플을 뽑을 때마다(Line 1), 해당 샘플과 가장 가까운 기존 노드 간 거리를 확인합니다.
    • 그 거리가 임계값보다 크면 로드맵에 노드를 추가하고, 그렇지 않으면 샘플링 실패 횟수 N_f를 1만큼 증가시킵니다(Lines 13–14).
    • 실패 횟수가 미리 정한 을 넘으면 해당 지역을 포화된 것으로 간주합니다.

 

  •  전통적 PRM과 달리, 본 방법은 노드 연결 단계를 샘플링 이후 별도로 수행합니다(Alg. 2).
    • 이전 샘플링 단계에서 얻은 각 노드에 대해 이웃 노드를 탐색하고, 두 노드를 연결할 때 세 가지 제약을 고려합니다.
      • 주행 가능성(traversability), 거리(distance), 센서 범위(sensor range)(Lines 4–6).
        • 거리 제약은 로드맵 품질 유지를 위해 너무 먼 노드는 연결하지 않도록 하기 위한 것이며, 센서 범위 제약은 경로 구간에서 동적 장애물을 관측하기 위해 두 노드가 서로를 센서로 감지할 수 있어야 함을 뜻합니다.

 

 

B. NodeEvaluationandUpdateRule ( 노드 평가 및 갱신 규칙 )

  • 로드맵을 점진적으로 구성한 뒤에는 노드 평가와 갱신이 이루어집니다.
  • [5]에서 제안된 정보 이득과 유사하게, 본 논문에서의 노드 이득(node gain)은 센서의 시야(FoV) 내에서 예상되는 미지(voxel) 셀의 개수를 기반으로 계산됩니다.
  • 또한 특정 요(yaw) 각도 하나에 대한 셀 개수만 산출하는 대신, 요 각도를 개 구간으로 분할(discretize)한 뒤 각 구간별로 보이지 않는 셀 수를 계산합니다.
  • 그런 다음 이 모든 구간의 셀 수 합계를 해당 노드의 이득으로 사용합니다.
  • 이 노드 이득 값은 일반적인 탐사 유틸리티를 나타내며, 각 구간별 이득은 나중에 궤적 생성 시 보간(interpolation)에 활용하기 위해 저장합니다.
  • 그리고 unknown voxels을 3가지 유형으로 나눕니다.
    • normal unknown
    • frontier unknown : free voxel과 인접하면 만족
    • surface unknown : free voxel과 occupied voxel 양쪽과 인접해야 한다.
      • 환경 윤곽 관측과 표면 검사가 더욱 가치가 있으니, surface unknown voxels에는 가장 높은 가중치를 부여하며, frontier unknown voxels에는 두번째로 높은 가중치를, normal unknow voxels에는 가장 낮은 가중치를 부여한다.
  • node gain을 계산하는 식은 아래와 같다. ( 식 1 )
    • w_n , w_f , w_s는 각각 normal , frontier , surface의 voxels에 부여되는 가중치이다.
    • U_n,tot , U_f,tot , U_s,tot는 센서의 유효범위 내에서 각각의 unknown voxels 유형에 대해서 추정된 voxels의 개수이다
    • ==> 따라서 node gain은 위의 3가지의 unknown voxels에 대응하는 가중치를 곱한 뒤에 더한 값들이다.

식1

  • 이전 모든 노드에 대해서 매 반복마다 gain을 re-compute하는 것은 inefficient하다. 그래서 갱신이 필요한 노드의 부분집합을 결정하는 규칙을 적용한다. 
    • 1. 첫번째 단계 : 이전에 로봇이 이동한 경로(trajectory) 주변의 노드 집합인 S_n을, Euclidean distance를 기준으로 기록한다.
    • 2. 두번째 단계 : 기록된 집합 S_n에서 "gain value" or "distance to the previous trajectory"가 미리 정한 threshold보다 낮은 노드를 선별하여, 이들에 대해서는 재계산 없이 gain value를 0으로 설정한다.
      실험 결과 이 노드들은 대체적으로 exploration utility가 낮아서 exploration goal 선정시 무시해도 무방한걸로 나타났다.
    • 3. 세번째 단계 : 나머지 노드들에 대해서만 식(1)의 공식을 적용하여, gain value를 다시 계산한다. 보통 해당 단계에서는 재계산 대상 노드는 기록된 집합 S_n의 10~20%정도에 불과하다.
    • ==> exploration 과정 중에는 이미 알려진 영역의 노드들은 gain value가 0으로 수렴하고, known과 unknown 영역의 경계에 있는 노드들이 가장 높은 gain값을 가지는 경향이 있다. 

 

C. Trajectory Generation

  • total exploration time을 minimize하고자, 단위 시간당 기대 이득이 가장 높은 궤적( trajectory with the highest information gain rate)을 생성하고, 이를 궤적 함수로 사용한다.
  • 1. 목표 후보 노드 집합 수집
    • 노드의 gain을 기반으로 식2의 조건을 만족하는 set of goal candidates인 G_c를 생성한다.
      • R은 roadmap ,  n_max는 gain value가 highest한 node이다.
      • Roadmap의 모든 노드중에서, node의 gain value가 threshold λ 보다 큰 노드만 골라서 수집한다.

식 2

  • 2. 경로 탐색
    • 각 trajectory는 후보 노드들 사이를 이어주는 A* or Digkstra와 같은 그래프 탐색 알고리즘으로 최단 경로를 찾는다.
  • 3. trajectory score 계산
    • 각 궤적은 해당 경로 상의 waypoints인 n_i,yaw들에 대해서 expected gain을 합산한뒤에 execution time( 실행시간 )으로 나누어서 평가한다. ( 식 3 )
    • yaw각도는 동적 장애물 감지를 위해서 trajectory 생성 과정에서 자동 결정된다. 이는 각 방향의 이전에 저장한 gain value를 interpolate하여 사용한다.

식 3

  • 4. 실행 시간 계산
    • 분모의 실행 시간은 로봇의 사전 정의된 속도와 가속도를 바탕으로 계산한다.
    • 생성된 궤적은 로봇이 이동 경로 구간에서 예기치 않은 동적인 장애물을 감지할 수 있도록 보장한다.
  • 5. 동적 장애물 회피 시 재계획
    • 생성된 궤적은 이동 경로 상의 dynamic한 obstacle 탐지를 보장한다.
    • 만약에 잠재적인 충돌이 예측된다면, 높은 값을 적용해 새로운 궤적을 빠르게 생성한다.
      • 이때 노드 추가나 이득 재계산이 불필요하므로 즉시 대체 궤적을 얻어 안전하게 회피할 수 있다.

 

 

D. ESDF-Based Optimization

  • exploration time과 path length을 단축하고, obstacles로부터 safety distance를 늘리기 위해서 ESDF 기반 최적화를 수행한다.
  • 이 최적화의 목적은 "궤적 실행 시간( trajectory execution time )"과 "궤적이 장애물로부터 떨어진 평균 거리"를 모두 고려하는 것이다.
  • ESDF 맵에서는 각 노드가 장애물로부터 떨어진 최소 거리를 얻을 수 있다.
    • 이미 높은 정보 이득( information gain)을 갖는 궤적이 생성되어 있기 때문에, 각 노드마다 지역 최적화만 적용한다.
    • 공식은 식 4와 같다.
      • 식에서 n은 궤적의 waypoints를 의미한다. 식 4에서는 궤적 시간과 장애물 거리를 모두 초기값으로 정규화 한다.
      • 가중치 w_t와 w_d는 각각 시간과 거리의 중요도를 조절하기 위해서 사용된다.
      • 5-a : 모든 연속된 노드 쌍 사이에서 충돌, 센서 범위, 최소 거리 조건이 모두 만족되어야 한다.
      • 5-b : 각 노드는 지역(Local) 최적화로 선택된다.
      • 5-c : 각 제약 조건은 0 또는 1의 값을 가지며, 1이면 조건이 만족됨을 의미한다.
        • 5-a와 5-c에서 C_n,ni+1과 S..... D...(쓰기 귀찮아서 생략한거임)는 각각 충돌 , 센서 범위 , 최소 거리 조건을 의미한다. 그리고 이 조건들이 모두 만족되어야 최적화가 성립된다.
        • ==> 즉, 다음 노드는 반드시 이전 노드의 센서 범위 안에 있어야 하며, 장애물로부터 충분히 멀리 떨어져야 한다. 또한 두 노드가 너무 가까워지지 않도록 제약한다.

식 4
제약 조건들

  • 앞서 언급했듯이, 장애물 탐지를 위해 다음 노드는 이전 노드의 센서 범위 내에서 선택되어야 한다.
  • 또한, 각 노드에 대응하는 이득 복셀이 겹치지 않도록 두 노드가 지나치게 가까이 위치하지 않아야 합니다.
  • 지역 최적화는 식 (5b)에 반영되어 있으며, 여기서 각 노드는 초기 값의 국소 영역(Local) 내에 있어야 합니다.

 

V. IMPLEMENTATION DETAILS 

  • 플래너 구현에는 Octomap [23] 패키지를 사용한다.
  • [5]에서 제안한 것처럼, 플래너가 정보 이득을 계산할 때 사용하는 센서 범위는 실제 최대 센서 범위보다 작게 설정한다. ( d_planner < d_max ).
  • 목표 노드의 요(yaw) 각도 최적화는 [6]과 유사하며, 나머지 노드들은 동적 장애물 탐지를 위한 가시 범위를 극대화하기 위해 로봇의 이동 방향과 일치하도록 요 각도를 설정한다.
  • 종료 기준은 연속된 N 스텝 동안 새로운 노드가 추가되지 않을 때로 정의되며, 이는 더 이상 탐사할 미지 영역이 남아 있지 않음을 의미한다.
  • ESDF 기반 최적화에는 Voxblox [24] 패키지를 사용해 TSDF/ESDF 맵을 생성하고, 각 노드의 로컬 영역은 사전 정의된 한 변 길이를 갖는 바운딩 박스로 인코딩한다.
  • 장애물까지의 평균 거리는 TSDF/ESDF 맵의 해상도에 맞춰 궤적을 이산화(discretization)하여 계산하며, 빠른 플래닝을 위해 N_opt 반복 후 최적화 과정을 종료한다.

 

 

rig 4
표1
표3

 

표2
표4

VI. RESULTS AND PERFORMANCE BENCHMARKING

  • 제안한 알고리즘의 성능을 종합적으로 분석하기 위해, RGB-D 카메라를 장착한 쿼드콥터를 사용한 시뮬레이션 실험을 수행한다.
  • 시스템은 2.4 GHz Intel i7-7700HQ에서 구동된다.
  • 실험은 탐사 성능과 안전성을 평가하기 위한 것이며, 탐사 성능 평가는 RH-NBV [5], 참조 [25]에서 언급된 프론티어 기반 탐사 알고리즘, 그리고 최신 AEP [7] 플래너를 벤치마크로 선정하여 진행다.

 

 

A. Environments and Parameters

  • 실험을 위해 총 여섯 가지 목표 환경을 선택하다(표 II 참조).
    • 전반적인 탐사 성능을 평가하기 위해 크기가 다른 Café(소형), Maze(중형), Office(대형) 환경을 사용하고, 동적 장애물 회피 경로 생성 능력을 검증하기 위해 여러 사람이 이동하는 경로를 로봇이 알지 못하는 세 가지 동적 환경인 Dynamic Auditorium, Dynamic Tunnel, Dynamic Field을 포함시켰다.
  • 플래너 및 로봇 파라미터는 각각 표 I과 표 III에 제시되어 있다.
    • 이들 파라미터는 (i) 균일하게 분포된 로드맵, (ii) 효율적이고 신뢰할 수 있는 이득 추정, (iii) 빠른 재계획 속도, (iv) 합리적인 최적화 제약 조건을 달성하기 위해 선정되었다.
  • 벤치마크 플래너에는 원 논문들[5], [25], [7]에서 제안된 파라미터를 그대로 적용하였으며, 공정성을 위해 로봇 파라미터는 모든 플래너에 대해 동일하게 설정하였다.

 

표5
fig 9
fig 5

B. Exploration Performance

각 플래너에 대해 전체 탐사 시간, 경로 길이, 계산 시간을 기록하고, 10회 실험을 통해 평균 및 표준편차를 산출하였다. 표 V는 크기가 서로 다른 세 환경에서의 전반적인 탐사 성능 비교를 보여준다.

  • Cafe (Small)
    • DEP는 탐사 시간(4.77분), 전체 경로 길이(43.12m), 계산 시간(0.17분) 모두에서 가장 우수하다.
    • AEP[7]는 프론티어 탐사와 RH-NBV를 개선한 기법으로, 탐사 시간에서는 이들 두 플래너보다 빠르며, 경로 길이와 계산 시간은 유사하다. 그러나 DEP와 비교하면, AEP는 탐사 완료에 14.9% 더 오래 걸렸고 계산에는 117.6% 더 많은 시간이 소요되었으며, 경로 길이는 37.2% 더 길었다.
  • Maze (Medium)
    • DEP가 여전히 최상의 성능을 보였으며, 그 다음으로 우수한 AEP는 23.23분이 걸려 DEP(17.75분)보다 30.9% 더 오랜 탐사 시간을 필요로 했다.
    • 프론티어 탐사와 RH-NBV는 각각 34.74분, 31.44분으로 DEP보다 훨씬 긴 탐사 시간을 보였다.
  • Office (Large)
    • DEP는 탐사 시간과 계산 시간에서 가장 짧았다.
    • 프론티어 탐사는 전체 경로 길이 253.63m로 DEP(318.53m)보다 20.3% 짧았다.
    • 특히 계산 시간 면에서 DEP는 AEP 대비 36.9%, 프론티어 탐사 및 RH-NBV 대비 거의 20% 수준에 불과해 매우 빠른 성능을 보였다.

탐사 속도는 그림 9에 제시되어 있다.

  • Cafe (Small): 50초 이후 DEP가 가장 높은 탐사 속도를 보이며, AEP보다 약간 우위에 있다. RH-NBV와 프론티어 탐사는 전 과정에서 가장 낮은 속도를 기록했다.
  • Maze (Medium): 플래너 간 격차가 더욱 커진다. DEP는 기울기가 꾸준히 유지되며 거의 전체 탐사 과정에서 가장 높은 속도를 유지하고, 나머지 세 플래너는 특정 시점 이후 속도가 점차 저하된다. AEP는 프론티어 탐사 및 RH-NBV보다는 높은 속도를 보인다.

탐사 과정을 시각화하기 위해 동일한 설정에서 네 플래너를 10분간 실행하고 지도 및 궤적을 기록한 결과를 그림 5에 나타냈다.

  • DEP는 네 플래너 중 가장 넓은 영역을 탐사하였고, AEP는 프론티어 탐사와 RH-NBV보다 나은 성능을 보였다.
  • 프론티어 탐사는 되왕복 경로가 많았고, RH-NBV는 궤적이 구불구불했기 때문이다.
    • 그러나 Office (Large) 환경에서는 마지막 순간을 제외하고 세 플래너의 탐사 속도가 유사했으며, 마지막에 DEP가 약간 더 높은 탐사 속도를 보였다.

 

 

fig 7
fig 8

C. Exploration in Dynamic Environments

  •  동적 장애물이 존재하는 상황에서 안전하게 탐사할 수 있는 능력을 입증하기 위해, Dynamic Auditorium, Dynamic Tunnel, Dynamic Field 세 환경에서 플래너를 테스트했다.
  • 각 환경에는 로봇이 경로를 알지 못하는 여러 명의 사람이 걸어다니는 상황이 포함되어 있습니다.
    • 10회씩 실험을 수행하며 충돌 발생 여부를 확인하였고, 결과적으로 세 환경 모두에서 제안 플래너는 동적 장애물(사람)과 충돌 없이 안전하게 모든 환경을 완전히 탐사할 수 있음을 확인했다.
    • 각 환경에서 완전히 탐사된 지도는 그림 7과 그림 8에 시각화되어 있다.

 

 

 

VII. DISCUSSION


A. Exploration Performance Analysis

  • Cafe(소형)과 Maze(중형) 환경에서는 프론티어 탐사와 RH-NBV의 탐사 속도가 크게 떨어지는 현상이 관찰됩니다.
    • 이 원인은 정보가 많은 경로를 생성하지 못하기 때문입니다.
      • RH-NBV는 "구불구불한" 궤적을 만들기 쉽고, 샘플 개수가 제한되어 유틸리티가 높은 영역을 제대로 샘플링하지 못합니다.
      • 프론티어 기반 플래너는 탐사 유틸리티를 고려하지 않고 목표를 설정하기 때문에 근시안적 동작 및 탐사된 영역 내에서 되돌아다니는 경향이 있습니다.
      • AEP는 정보 이득이 낮을 때 캐시된 노드를 프론티어로 활용해 탐사를 유도하기 때문에 더 높은 탐사 속도를 보이지만, 여전히 전체 궤적의 유틸리티를 평가하지는 못합니다.

 

  • DEP는 로드맵을 점진적으로 구축하면서 각 영역의 유틸리티를 쉽게 산출할 수 있어, 최적의 관측 지점을 선택해 높은 유틸리티의 궤적을 생성할 수 있습니다.
  • 궤적 최적화는 샘플링의 무작위성을 보완해 경로 품질을 더욱 향상시킵니다.
    • 특히 Maze(중형)처럼 시점과 궤적 유틸리티가 더욱 중요한 환경에서 DEP의 성능이 두드러집니다.

 

  • 반면 Office(대형) 환경은 넓은 개방 공간과 여러 최적 시점·경로가 존재하기 때문에 모든 플래너가 유사한 품질의 궤적과 탐사 속도를 보입니다.
    • 하지만 표 V에서 보듯이 DEP의 전체 탐사 시간은 더 짧은데, 이는 RH-NBV와 프론티어 기반 탐사가 마지막 단계에서 작은 방을 찾는 데 오랜 시간이 소요되기 때문입니다.
    • RH-NBV의 샘플 개수가 제한적이라, 대규모 환경에서 작은 미탐사 영역을 찾는 데 더 많은 반복이 필요합니다.

 

  • 계산 시간 측면에서 DEP는 세 환경 모두에서 가장 적은 시간을 사용합니다.
    • 이는 DEP가 점진적으로 구축된 로드맵을 재사용함으로써 불필요하고 반복적인 계산을 줄일 수 있기 때문입니다.
 
 
 

B. Evaluation of ESDF-Based Optimization

  •  그림 9(왼쪽)은 궤적 최적화 적용 전후에서 플래너의 전체 성능을 비교한 결과입니다.
    • 각 환경마다 10회씩 실험하여 탐사 시간과 경로 길이를 백분율로 나타냈습니다.
  • 제안한 최적화 기법은 플래너의 성능을 크게 개선하는 것으로 나타났습니다.
    • 궤적 최적화를 적용한 경우, 전체 탐사 시간은 비최적화 대비 77.01%, 전체 경로 길이는 76.09%로 단축되었습니다.
  • 특히 표 IV는 서로 다른 환경에서 각 플래닝 반복(iteration)마다 최적화 통계를 제시합니다.
    • 각 반복에서, 최적화된 궤적의 평균 탐사 시간은 비최적화 대비 87.28%, 경로 길이는 91.86% 수준입니다.
    • 또한, 최적화된 궤적은 최근접 장애물까지의 평균 거리가 비최적화 대비 20.58% 더 멀었습니다.
    • ===> 즉, 궤적 최적화는 경로를 짧고 효율적으로 만들 뿐 아니라, 장애물로부터의 안전 거리도 크게 향상시킵니다.

 

 

 

C. Evaluation of Replanning Time

  • 네 가지 플래너의 재계획 시간을 정량적으로 비교하기 위해, Dynamic Auditorium, Dynamic Tunnel, Dynamic Field 환경에서 실험을 수행했습니다.
  • 동적 장애물을 만났을 때 각 플래너의 재계획 시간을 측정하였고, 그 결과는 그림 9(오른쪽)에 제시되어 있습니다.
  • 실험 결과, 제안한 플래너의 재계획 시간이 가장 짧았으며, RH-NBV와 프론티어 탐사는 DEP보다 약 2배의 재계획 시간이 소요되었습니다.
  • 또한 AEP의 재계획 시간도 DEP보다 61.3% 더 오래 걸렸습니다.
  • 이러한 재계획 시간 단축 효과는, 제안한 플래너가 이전에 유지하던 로드맵을 재활용하기 때문으로 설명할 수 있습니다.

 

 

VIII. CONCLUSION AND FUTURE WORK

  • 이 논문에서는 UAV 탐사를 위한 새로운 동적 탐사 플래너(DEP)를 제안하였습니다.
  • 본 알고리즘은 확률적 로드맵(PRM)의 점진적 샘플링 개념을 확장하였으며, 탐사 시간, 경로 길이, 계산 시간 측면에서 기존 벤치마크 알고리즘들을 능가함을 확인하였습니다.
  • 또한 ESDF 기반 최적화를 통해 탐사 성능이 더욱 향상됨을 실험적으로 보여주었습니다.
  • 아울러, 제안 플래너는 동적 환경에서도 안전하게 탐사를 수행할 수 있음을 입증했습니다.
  • 하지만 로봇 센서의 한계로 인해 동적 장애물을 완전히 감지하지 못할 수 있으며, 현재 방식처럼 로봇이 감지한 장애물만 회피하면 완전한 안전이 보장되지 않을 수 있습니다.
  • 앞으로는 중앙 집중식 감지 시스템을 도입해 동적 장애물을 추적하는 방안도 연구할 계획입니다