무인비행체 경로계획 기술 동향

“경로계획(Path Planning)” 기술은 가상 환경에서 캐릭터를 움직이거나 실제 환경의 로봇을 조작하는 시스템의 핵심기술 중 하나이다. 이 기술은 로보틱스 분야에서 오랜 연구 끝에 일상에서 사용되는 무인 시스템, 예를 들어 청소 로봇이나 자율주행 자동차에까지 적용되고 있다.

일반적으로 경로계획 알고리즘은 로봇이 충돌하지 않는 여러 경로 중에서 임무에 맞게 최적의 경로를 선택하는 과정이다. 이 과정은 환경 인식 정보를 바탕으로 충돌이 없는 공간을 탐색해 그래프(Graph)를 구축하고, 그래프를 목표에 맞게 평가하는 두 단계로 추상화할 수 있다. 충돌을 피하기 위한 그래프를 구축하기 위해서는 충돌 감지 알고리즘이 필요하며, 임무에 따라 최적의 경로를 선택할 수 있도록 비용 함수나 이득 함수를 적절하게 설계해야 한다. 예를 들어, 청소 로봇 시스템은 아직 청소하지 않은 공간으로 이동할수록 더 많은 이득을 얻도록 설계할 수 있고, 자율주행 자동차 시스템은 목표 지점까지의 이동 거리가 짧을수록 더 많은 이득을 얻도록 설계할 수 있다.

경로계획은 모션 플래닝(Motion Planning)이라는 고차원 공간에서 로봇의 움직임을 계획하는 기술로 확장될 수 있다[5]. 이는 2차원 및 3차원 유클리드 공간(Euclidean Space)을 넘어서 드론의 회전 운동이나 로봇 팔 관절의 움직임을 포함한 고차원 상태 공간(Configuration Space)에서의 경로를 계획한다. 하지만 고차원에서 최적의 경로를 계획하는 과정은 많은 계산량을 요구하기 때문에 이 문제를 해결하기 위한 연구가 계속 진행되고 있다.

이 절에서는 로보틱스 분야에서 사용되는 주요 경로계획 알고리즘을 기술한다. 무인비행체의 경로계획 기술도 이러한 알고리즘에 기반을 두고 있으며, 무인비행체 시스템이 적용되는 상황에 맞게 알고리즘을 변형하여 임무 수행에 필요한 최적의 경로를 계획한다.

가. Potential Field

Potential Field 경로계획 알고리즘[6]은 시작 지점부터 목표 지점까지 이동 경로를 계획하기 위해, 인력(Attractive Force)과 척력(Repulsive Force)이라는 두 가지 요소를 에너지로 정의한다. 인력은 목표 지점이 물체를 끌어당기는 힘으로 작용하며 목적지를 향하는 경로를 유도한다. 반면에, 척력은 장애물이 주변을 밀어내는 힘으로써 로봇이 장애물을 회피하도록 유도한다. 이 두 힘을 합쳐 경로를 계획하는 공간의 잠재적 에너지를 정의하며, 로봇은 잠재적 에너지가 낮아지는 지점을 따라 이동하는 경로를 생성한다.

이 방법은 다른 알고리즘에 비해 계산량이 비교적 적어 빠르게 경로를 계획할 수 있다. 하지만 복잡한 환경에서는 최종 목적지까지 이동하지 못하고 한 지점에서 맴도는 문제가 발생할 수 있다.

나. Dijkstra & A*

Dijkstra 알고리즘[7]은 그래프의 시작 노드(Node)에서 모든 노드까지의 최단 경로를 검색하는 알고리즘이다. 경로계획 그래프를 형성한 후 각 목적지로 이동할 수 있는 다양한 경로를 비교함으로써 최적의 경로를 선택할 수 있다. 하지만 그래프의 모든 경로를 검색하는 특징으로 인해 최종 목적지가 이미 결정된 상황에서 다른 노드까지 최단 경로를 계획하는 불필요한 계산을 포함한다.

A* 알고리즘[8]은 이러한 Dijkstra 알고리즘의 단점을 극복하고자, 목표 노드까지의 최단 경로를 적은 계산량으로 계산하도록 설계되었다. 목표 지점까지의 이동 비용을 휴리스틱 비용(Heuristic Cost)으로 정의하며, 값을 정확하게 추정할수록 불필요한 탐색 없이 빠르게 최단 경로를 계획할 수 있다.

로보틱스 분야에서의 A* 알고리즘은 주로 격자 형태의 상태 공간에 적용하여, 현재 지점에서부터 목표 지점까지 최단 경로를 실시간으로 찾는 시스템에 활용한다(그림 1 참고). A* 알고리즘의 휴리스틱 비용으로 격자 간 유클리드 거리(Euclidean Distance)를 사용함으로써 빠르게 최단 거리의 경로를 찾는다. 또한, 적절한 크기의 격자를 사용하면 장애물을 회피하는 최적 경로를 빠르게 계산한다. 하지만 너무 큰 격자로 상태 공간을 구성하면 경로를 찾지 못하는 문제가 발생할 수 있다. 또한, 상태 공간의 차원이 높아질수록 계산량이 급격하게 증가하기 때문에 주로 저차원 공간에서 최단 경로를 찾는 모바일 로봇 등에서 널리 사용된다.

그림 1

A* 경로계획 알고리즘

다. PRM(Probabilistic RoadMap)

샘플링(Sampling) 기반의 경로계획 알고리즘은 격자 구조를 사용하지 않고 연속된 상태 공간에서 최적의 경로를 계획하는 방법이다. 그림 2와 같이, 이 계열의 방법론은 샘플링 방식을 통해 환경과 충돌하지 않는 상태를 찾아 노드로 표현하고, 각 노드를 연결하여 경로계획 그래프를 구성한다. 그리고 생성된 그래프에서 A* 또는 Dijkstra 검색 알고리즘을 사용하여 최적의 경로를 선택한다.

그림 2

A* 샘플링 기반 PRM, RRT, RRT* 경로계획 알고리즘: 시작 지점(S), 목표 지점(G), 장애물(검정)

PRM 경로계획 알고리즘[9]은 샘플링 기반의 경로계획 알고리즘 중 하나이다. 그림 2(a)와 같이 상태 공간에서 샘플링을 통해 장애물과 충돌하지 않는 여러 노드를 먼저 생성한 후 그림 2(b)처럼 인접한 노드끼리 연결하여 경로계획 그래프를 형성한다. 결정된 목표 지점이 없는 경우에는 Dijkstra 알고리즘을 활용하여 시작 지점에서 모든 노드까지 최단 경로를 구할 수 있으며, 목표 지점이 있는 경우에는 A* 알고리즘을 적용하여 목표 지점까지의 최단 경로를 빠르게 찾을 수 있다.

PRM 경로계획 알고리즘을 활용하여 최적의 경로를 찾기 위해서는 무수히 많은 샘플링이 요구된다. 이 과정은 계산 시간이 많이 소요되나, 환경이 변하지 않을 경우, 시작점이나 목표 지점이 변경되어도 이미 구축된 그래프를 재사용할 수 있는 장점이 있다(그림 2(c), (d) 참고). 이 특성 덕분에 PRM 경로계획 알고리즘은 동적이지 않고 정적인 환경에서 특히 유용하다.

라. RRT

RRT(Rapidly-exploring Random Tree) 경로계획 알고리즘[10]은 PRM과 유사하게 샘플링 방식을 사용하지만, 구조와 확장 방식에서 차이가 있다. 그림 2와 같이 RRT 알고리즘은 시작 지점에서부터 점진적으로 확장하여 트리(Tree) 구조의 경로계획 그래프를 구축한다. 이 과정에서 샘플링된 위치 중 가장 가까운 노드를 찾고, 그 노드로부터 이동이 가능한 최대 거리 내에서 새로운 노드를 생성하여 연결한다.

RRT는 PRM과 비교할 때 그래프 구축과 경로 검색이 더 빠르다. 그러나 RRT의 무작위성 샘플링을 통한 확장 방식 때문에 실행마다 다른 경로를 생성할 수 있다. 또한, 많은 샘플링을 수행하더라도 항상 최적의 경로를 제공하는 것은 아니다. 이러한 이유로 RRT는 주로 동적인 환경이나 신속한 경로 생성이 필요한 시스템에 활용된다.

마. RRT* & RRG

RRT* 및 RRG(Rapidly-exploring Random Graph) 경로계획 알고리즘[11]은 RRT를 개선하여 최적의 경로를 보장하도록 고안되었다.

RRT*는 RRT의 샘플링 및 확장식 트리 구조를 기반으로 하지만, 새로운 노드를 추가할 때마다 시작점부터 해당 노드까지의 최적 경로를 유지하도록 트리 구조를 조정한다. 그림 2(j)와 같이 새로운 노드에 대해 이동 비용이 가장 낮은 노드를 부모 노드로 선택하고, 그림 2(k)에서처럼 필요시 주변 노드와 연결을 재구성함으로써 최단 경로를 유지한다. 이러한 특성으로 인해, 로봇 팔의 움직임 생성과 같이 최적 경로가 필요한 시스템에서 주로 활용된다.

RRG는 RRT의 확장형 샘플링 방식을 기반하면서도 트리 구조에 제약을 두지 않고 여러 노드를 연결하는 구조를 사용한다. RRG 그래프는 장애물 공간을 피하면서 시작점부터 확장되기 때문에, PRM보다 빠르게 경로계획 그래프를 구축할 수 있다. RRT 알고리즘과 비교할 때, RRG는 계산 시간이 더 오래 걸리지만, 샘플링을 많이 할수록 점점 최적의 경로를 찾아가는 특성을 가진다. 이러한 특징은 동적 환경에서도 높은 효율성과 정확성을 제공하기 때문에 탐사 경로계획에서 많이 활용된다.

바. CHOMP

CHOMP(Covariant Hamiltonian Optimization for Motion Planning) 경로계획 알고리즘[12]은 미분이 가능한 비용 함수를 사용하여 초기 경로를 최적화하는 방식이다. 이 알고리즘은 주로 장애물 회피, 경로 길이 최소화, 그리고 경로의 부드러움을 유지하기 위한 비용을 포함한 비용 함수를 설계하여 사용한다.

CHOMP의 경로 최적화 과정을 위해 모든 공간에서 장애물까지의 가장 가까운 거리를 추정해야 한다. 거리 정보를 구하는 과정에서 많은 계산량을 요구하므로, 주로 정적 환경에서 효과적이며 급격하게 변화하는 동적 환경에서는 사용 제약이 있다. 하지만 미리 계산된 거리 정보를 사용하면 고차원 환경에서도 빠르게 최적의 경로를 계획할 수 있기에, 자동화 시스템에서 정적인 상황에서 로봇 팔의 효율적인 모션 플래닝 등에 사용된다.

스위스 취리히 연방 공과대학(ETH Zürich)의 Autonomous Systems Lab 연구진은 Receding Horizon Next-Best-View 탐사 경로계획 알고리즘[12]을 개발하였다. 이 알고리즘은 소형 드론이 미지의 공간을 탐사하는 과정에서 새로운 환경 정보를 업데이트하면서도 순간마다 최적의 탐사 경로를 계획한다.

이 연구에서 소형 드론은 그림 3[13]과 같이 깊이 센서를 활용하여 주변 환경을 인식한다. 관측한 환경 정보는 장애물이 존재하는 공간, 장애물이 없는 공간, 관측하지 못한 공간을 3차원 지도 형태로 표현된다. 드론은 실시간으로 갱신하는 환경 정보를 바탕으로, 관측하지 못한 공간을 향해 비행하면서 탐사 임무를 수행한다.

그림 3

Next-Best-View Planner

출처 Reproduced with permission from [13].

ETH 연구진은 환경 정보가 업데이트될 때마다 샘플링 방식을 활용하여 최적의 탐사 경로를 생성한다. 이 Next-Best-View 경로계획 알고리즘은 드론의 3차원 공간의 위치와 요각(Yaw Angle)을 포함한 4차원 상태 공간에서 RRT 알고리즘의 샘플링 및 트리 확장 방식을 사용한다. 이렇게 구성된 RRT 경로계획 그래프는 드론의 현재 위치와 자세로부터 충돌이 발생하지 않는 공간으로 비행할 수 있는 여러 개의 탐사 경로를 포함한다.

탐사 경로계획 알고리즘은 여러 경로 중에서 탐사 이득이 최대가 되는 최적의 경로를 선택한다. ETH 연구진은 최적 경로 평가를 위해 환경 정보를 활용하여 가시적 이득(Visible Gain)을 정의하였다. 이 연구에서는 드론이 깊이 센서를 통해 새롭게 관측할 수 있는 공간의 양을 수치화하여 가시적 이득으로 표현한다. 이를 활용하여 RRT 그래프의 모든 노드에 해당하는 위치와 자세에서 가시적 이득을 평가하고, 각 탐사 경로의 모든 노드가 가진 가시적 이득을 취합하여 탐사 이득으로 정의한다. 드론은 매 순간 탐사 이득이 가장 큰 경로를 선정하여 비행함으로써 탐사 임무를 수행한다.

이 알고리즘은 특히 소형 드론에 탑재한 제한된 컴퓨팅 자원을 사용하면서도, 드론이 스스로 3차원 환경을 인식하고 새로운 경로를 계획할 수 있다는 점을 보여주었다.

미국 네바다 리노 대학(University of Nevada, Reno)과 스위스 취리히 연방 공과대학(ETH Zürich)의 공동 연구진은 지하 탐사에 특화된 경로계획 알고리즘[14,15]을 개발하였다. 이 시스템은 4족 보행 로봇과 드론을 모두 사용하여 탐사 임무를 수행한다. 이를 위해 두 로봇에 모두 적용할 수 있는 탐사 경로계획 알고리즘이 고안되었다.

이 알고리즘은 계층적 구조인 지역계획(Local Planning)과 전역계획(Global Planning)으로 나누어 동작한다(그림 4 참고). 지역계획과 전역계획 모두 샘플링 기반의 RRG 기술에 기반하고 있으나 사용 목적에 따라 적절하게 사용된다. 지역계획에서는 로봇이 현재 위치한 국소 범위 내에서 빠르게 경로를 계획한다. 반면, 전역계획은 막다른 길을 만나서 새로운 탐사 지역으로 로봇을 재배치하거나, 임무 완료 후 복귀가 필요한 상황에서 복귀 경로계획에 활용된다.

그림 4

Graph-based Exploration Planner

출처 Reproduced with permission from [14].

공동 연구진은 지역계획과 전역계획의 목적에 따라서 알고리즘의 동작 방식을 다르게 설계하였다. 그림 4와 같이, 지역계획 단계에서는 지역 경로계획 그래프를 구축한 후 탐사 경로를 빠르게 평가하는 방법을 개발하였다. 지역 그래프에 Dijkstra 검색 알고리즘을 적용하면 모든 노드까지 최단 경로를 구할 수 있으며, 동시에 모든 경로의 마지막 지점인 말단 노드(Leaf Node)를 찾을 수 있다. 말단 노드가 관측한 공간과 관측하지 못한 공간의 경계(Frontier) 근처에 위치한다는 관찰을 기반하여, 지역 경로계획 단계에서는 말단 노드에서만 탐사 이득을 평가한다. 그리고 비슷한 위치에 있는 말단 노드를 군집화하여 대표적인 탐사 경로만 평가함으로써 불필요한 계산을 줄이면서도 최적의 탐사 경로를 선택한다.

지역계획만 사용하여 탐사 임무를 진행하면, 국소 범위 내에 더 이상 탐색할 공간이 없어져서 탐사 임무를 지속할 수 없는 문제가 발생할 수 있다. 특히, 지하 환경에서는 막다른 길과 같이 지역 경로를 생성하지 못하는 문제가 빈번하게 발생한다. 공동 연구진은 이러한 문제를 극복하기 위해 새로운 경계로 탐사 임무를 진행하도록 전역계획 단계를 설계하였다(그림 4 참고). 전역계획의 경로계획 그래프는 샘플링이 아닌, 지역계획에서 선택되지 않은 탐사 경로 후보군으로 구성된다. 지역계획의 후보군은 새로운 탐사 경계 정보를 포함하고 있으므로 전역 경로계획 그래프에 추가하여 전역계획 단계에서 활용한다. 이러한 계층적 접근 방식을 활용하여 복잡한 지하 공간을 효율적으로 탐사하는 시스템을 구성하였다.

이 접근 방법은 미국 방위 고등 연구 계획국(DARPA: Defense Advanced Research Projects Agency) 주최의 지하 도전 과제(Subterranean Challenge)에서 우수성을 입증하였다. 특히, 이 연구는 지하 터널과 같이 복잡하고 제한된 환경에서 효율적인 탐사 경로를 계획하는 알고리즘을 제시하였다.

경계 기반의 탐사 경로계획 알고리즘은 환경 정보를 이용하여 먼저 탐사 경계를 추정하고, 이를 바탕으로 최적의 탐사 경로를 계획한다. 탐사 경계 근처에서 집중적으로 경로를 계획하는 특징 덕분에, 탐사하지 않은 영역을 향하여 이동하며 빠르게 새로운 공간을 관측할 수 있다.

최근, 홍콩 과기대학(HKUST)의 Aerial Robotics Group 연구진은 드론의 빠른 탐색 임무를 위한 새로운 탐사 경계 기반의 경로계획 알고리즘[16]을 개발하였다. 이 알고리즘은 경계 정보 구조(Frontier Information Structure)를 사용하여 탐사 경계를 효과적으로 관리하도록 설계되었다. 탐색 임무 전역에서 경계 영역의 크기와 분포를 균일하게 유지함으로써 서로 다른 장애물이 불규칙하게 분포된 환경에서도 효과적인 탐사 임무 수행을 위한 경로를 계획한다.

또한, 경계 정보 구조와 더불어 계층적 방법을 사용함으로써 최적의 탐사 경로를 생성한다. 그림 5[16]와 같이, 이 알고리즘의 계층적 경로계획은 경계를 관측하는 순서를 먼저 결정하고, 순서에 따라 드론의 탐사 경로를 최적화한다. 일정한 크기와 분포를 가진 경계 영역에 외판원 순환 문제(Traveling Salesman Problem)를 적용하여, 모든 경계 영역을 효율적으로 방문하는 순서를 계산한다. 이후, 경계 영역을 최대한 관찰할 수 있는 드론의 여러 자세와 경계 영역 방문 순서를 고려하여 탐사 경로계획 그래프를 구성한다. 이 경로계획 그래프는 적은 노드로 구성되어 있지만 탐사에 특화된 정보를 압축하고 있어서, 드론이 새로운 공간을 가장 잘 관측할 수 있는 탐사 경로를 효과적으로 계획하는 데 사용된다.

그림 5

Frontier-based Exploration Planner

출처 Reproduced with permission from [16].

이러한 경계 정보를 활용하는 탐사 경로계획 기술은 열린 경계 공간이 많은 환경에서 빠르게 탐사 임무를 수행하는 데 효과적이다.

단일 드론이 넓은 공간에서 탐사 임무를 수행하면 경로계획 계산의 효율과 계획 경로의 질도 감소한다. 또한, 제한된 배터리 용량으로 인해 탐사가 가능한 최대 범위도 불가피하게 제한된다. 이러한 문제를 극복하기 위해서 다수 드론을 활용한 탐사 경로계획 기술이 연구되고 있다(그림 6 참고)[17].

그림 6

Multi-UAVs Exploration in Forest

출처 Reproduced with permission from [17].

홍콩 과기대학(HKUST) 연구진은 단일 드론용 기술[16]을 다수 드론의 탐사 임무로도 확장하였다[17]. 이 알고리즘은 수평 격자 분할(Horizontal Grid Decomposition) 기술을 활용함으로써 각 드론이 서로 중복되지 않는 탐사 경로로 이동하도록 최적화한다. 또한, 개별 드론의 작업 부하와 이동 거리를 최적화하여 전체 탐사 효율을 높일 수 있도록 용량 제한 차량 경로 문제(Capacitated Vehicle Routing Problem)를 통해 해결한다.

미국 매사추세츠 공과대학교(MIT)와 미국 항공우주국(NASA)의 공동 연구진은 GPS를 사용할 수 없는 숲속 환경에서 다수의 드론용 탐색 및 구조 활동을 위한 기술을 연구했다[18]. 이 기술은 다수 드론의 협력적 동시 위치결정 및 지도작성(Collaborative SLAM) 기술을 사용하여 작성된 환경 정보를 바탕으로, 계산이 간략한 경계 기반의 탐사 경로계획 알고리즘을 사용한다. 이 시스템에서 개별 드론은 경계까지의 거리와 방향, 현재 비행 속도를 고려하여 가장 적합한 경계를 선택한다. 그리고 선택한 경계를 목적지로 A* 경로계획 알고리즘을 수행하여, 탐색하지 않은 공간을 향해 최단 거리 경로를 따라 비행한다.

스위스 취리히 연방 공과대학(ETH Zürich)의 Vision for Robotics Lab 연구진도 다수 드론을 활용하여 숲속을 신속하게 탐사하는 연구를 수행하였다[19]. 이 연구는 HKUST 연구팀의 탐사 기술[17]을 숲속 환경에 적합하도록 개선하였다. ETH 연구진은 숲과 같이 다수의 작은 경계 영역이 흩어진 환경에서 탐사 속도를 향상하기 위해 적응형 탐사 전략(Adaptive Exploration Strategy)을 설계하였다. 각 드론은 탐사 경계 영역의 크기에 따라 탐사자(Explorer) 역할과 수집가(Collector) 역할 중 하나를 선택하여 행동한다. 아직 관측하지 못한 공간이 넓은 경우에 탐사자의 행동 방식에 우선순위를 두고 탐사한다. 반면에, 어느 정도 관측된 공간에서는 공격적으로 움직이며 작은 경계 영역을 향해 움직이는 수집가 행동을 취한다. 이 시스템에서 다수의 드론은 서로 다른 두 행동 전략을 선택하면서 세밀하고 빠르게 탐사 임무를 수행한다.

한국전자통신연구원(ETRI) 자율비행연구실에서는 수목이 우거진 숲속 환경에서의 무인 탐사 및 수색 임무용 드론의 자율비행 기술을 연구한다(그림 7 참고). 운용자가 숲 공간의 탐사 영역을 할당하면, 드론은 상태 추정, 환경 인지 및 실종자 탐지, 탐사 경로계획, 궤적 생성 및 제어, 자율비행을 위한 작업 계획을 스스로 판단하며 실시간으로 탐사 임무를 수행한다.

그림 7

ETRI 숲속 경로계획 및 자율비행 기술

ETRI 연구진의 드론은 LiDAR와 IMU 센서를 장착하고 있어, 정확한 GPS 신호를 사용하기 어려운 숲속 환경에서 SLAM 기술을 통해 드론의 위치 및 자세를 추정한다. 추정한 자세를 바탕으로 LiDAR 데이터로부터 주변 환경 정보를 업데이트한다. 드론은 장애물이 있는 공간, 바닥면 공간, 아직 탐색하지 않은 공간 등 환경 정보를 계산하여 자율비행 탐사 경로계획에 활용한다.

탐사 경로계획 알고리즘은 수풀이 우거진 공간에서 효과적인 탐색 및 복귀 경로계획을 위해 Graph-based Exploration Planner[14] 기술을 기반으로 한다. 넓은 탐사 공간에서 지역 및 전역계획으로 구성된 계층적 경로계획 정책을 활용하여 높은 효율로 탐사 경로를 생성한다.

지역계획 단계에서는 RRG 방법을 사용하여 국소 범위의 경로계획 그래프를 구축한다. 이 그래프는 아직 탐색하지 않은 영역으로 향하는 탐사 경로를 결정한다. ETRI 연구진은 경로를 결정하는 단계에서 탐사 이득만 고려하는 것이 아니라, 숲속 탐사에 특화된 새로운 이득 함수를 고안했다. 드론이 좁은 수풀 사이를 자주 비행함에 따라 발생이 가능한 위험을 최소화하고자 가장 가까운 장애물까지의 거리를 고려한다. 또한, 탐사 경로는 이전에 사용된 경로와 중복되지 않도록 선정하며, 이를 통해 전체 탐사의 효율을 높이도록 이득 함수를 설계하였다. 모든 요소는 숲속 탐사 임무에서 안전하면서도 효율적인 지역 경로를 선정하도록 도와준다.

기반 기술[14]에서의 상황과 비슷하게, 지역 경로계획을 따라 탐사를 진행하다가 더 이상 탐사할 공간이 없는 상황이 발생할 수 있다. 이를 해결하기 위해서 경로계획 알고리즘은 새로운 탐색 공간으로 드론을 재배치하는 전역 경로계획을 실행한다. 전역계획 단계에서는 지역계획 시 선택하지 않은 공간 중에서 탐사 이득이 가장 높은 공간을 선택한다. 또한, 선택한 공간으로 이동하는 최적 경로를 계획할 때는 A* 경로계획 알고리즘을 통해 최단 거리 경로를 선택하거나 전역 경로계획 그래프를 활용한다. 두 알고리즘을 통해 얻은 최적 경로를 비교하여 탐사 임무에 더 적합한 경로를 선택한다. 이러한 접근 방식을 통해 드론은 숲 환경에서 빠르게 새로운 탐사 공간으로 이동하여 탐사 활동을 지속한다.

그림 7은 실제 숲속 환경에서 드론이 할당된 임무 영역을 탐사하며 실종자를 탐지하는 실험을 보여준다. 지역 및 전역 경로계획을 선택적으로 반복하며 탐사 임무를 완료하였고, 카메라와 딥러닝 탐지 기술을 활용하여 실종자를 탐지할 수 있었다.