복합적인 실내 환경 내 신뢰성 있는 자율 비행을 위한 3차원 장애물 지도 생성 및 경로 계획 알고리즘

1. 서 론

최근 대두되고 있는 국가 재난 상황에서 무인 이동체의 운용은 인명 및 재산 피해를 최소화하는 이점을 가지며 각광받고 있다. 여러 무인 이동체 플랫폼 중 UAV는 3차원 환경 내 유연한 운용이 가능하고 4족 보행 로봇 또는 바퀴 기반의 모바일 로봇 운용이 불가능한 복잡한 환경 내에서 여러 미션들을 수행할 수 있는 장점이 있어, 재난 환경 내 탐사를 위한 대표적인 플랫폼으로 고려되어진다^[1-3]. UAV의 유연한 운용을 위해 복잡한 환경 내 장애물 회피 경로 생성 알고리즘은 필수적인 요소이며 이를 위해 국내 및 해외 연구진들은 기존의 기법들을 발전시키거나 새로운 기법들^[4-6]을 적용시켜 UAV의 장애물 회피 성능을 발전시켰다. 하지만 무게에 큰 영향을 받는 드론의 물리적 특성상 고성능 컴퓨터의 사용이 제한되고 비교적 낮은 무게의 온보드 컴퓨터들을 사용하기 때문에 복잡한 환경에서도 계산량이 낮으며 신뢰성 있는 장애물 회피 경로 생성 알고리즘의 필드 성능 검증은 아직 미비한 실정이다. 따라서 본 논문에서는 다양한 복합적인 환경 내 신뢰성 있는 자율 비행을 위해 UAV [Fig. 1]에 탑재할 수 있는 3차원 장애물 지도 생성 및 경로 생성 알고리즘에 대해 제안하려고 한다.

[Fig. 1]

Deployed UAV for this study

UAV를 위한 장애물 회피 경로 생성 기법으로는 대표적으로 격자 기반 탐색 기법인 A*^[7] 알고리즘과 랜덤 샘플링 기반 탐색 기법인 RRT*^[8] 알고리즘이 있다. A*알고리즘은 경로를 탐색할 공간을 격자화 시켜 이웃 격자와의 연결성을 이용해 목적지까지 최단 비용을 가지는 경로를 구한다. 반면에 RRT* 알고리즘은 경로를 탐색할 공간에 무작위 샘플링을 활용하여 트리를 구성하고 목적지까지 확장한 후 재귀적으로 경로를 구한다. 두 알고리즘들은 계산량, 효율성, 최적성 측면에서 발전된 여러 연구들로 발전되어 왔으며 격자 기반 알고리즘으로는 Ego planner^[6]와 Faster planner^[5]가 제안되었고, 랜덤 샘플링 기반으로는 Informed RRT^[9]와 GMR-RRT*^[10]가 제안되었다. 하지만 이 알고리즘들은 기본적으로 3차원 공간을 직접적으로 탐색하는 접근들이며, 3차원 공간내 장애물 배치가 복잡하거나 탐색해야 하는 공간이 커지게 되면 계산량이 기하 급수적으로 커진다는 단점이 있다.

이러한 서로 다른 특성을 가지는 A* 와 RRT* 기반 알고리즘은 가장 보편적으로 사용되는 기법들이지만, 실제 UAV의 자율 비행 필드 테스트 시 에는 경로 생성 결과의 최적성, 계산량, 신뢰성(운용자가 어느정도 예상할 수 있는 경로) 측면에서 장점을 가지는 A* 기반 알고리즘이 주로 사용되며^[11], 본 논문 또한 격자 기반 탐색 기법에 집중하려 한다.

격자 기반 장애물 회피 경로 생성은 크게 2가지 단계로 구분되어진다. 첫번째는 경로 생성을 위한 3차원 장애물 지도(Costmap) 생성이며 두번째는 생성된 3차원 장애물 지도 내 신뢰성 있는 경로 생성 알고리즘이다. 3차원 장애물 지도 생성과 경로 생성 알고리즘은 탐색하려는 공간, 경로 생성의 해상도(Grid resolution) 등 여러 기준에 따라 계산량 및 성능이 민감하게 달라지는데, 신뢰성을 위해 경로 생성의 해상도를 높이게 되면 높은 계산 비용을 야기하여 실시간성에 제한이 있고, 실시간성을 보장하기 위해 탐색하려는 공간과 해상도를 낮추게 되면 복잡한 환경 내 신뢰성 있는 경로 생성 결과가 제한되는 Trade-off 관계가 있다.

기존의 기법들은 SLAM으로 생성한 3차원 지도 내 UAV의 현재 위치에서 목적지까지 3차원 공간에 존재하는 모든 격자(Grid) 내 경로 생성을 시도한다^[12]. 이러한 기존 기법들은 큰 계산 비용을 요구하며 실시간으로 신뢰성 있는 결과를 얻기 힘든 단점이 있다. 이러한 단점을 보완시키기 위해 본 논문에서는 실시간성이 보장되고 신뢰성 있는 장애물 회피 경로 생성을 위해 3차원 장애물 지도를 2차원 장애물 지도들로 분리하고 각각의 2차원 장애물 지도 내에서 장애물과의 거리 또한 고려된 신뢰성 있는 경로 생성 알고리즘을 제안한다. 제안하는 기법은 분리된 여러 2차원 장애물 지도 내 생성된 경로들 중 제안하는 비용 함수에 따라 가장 낮은 비용을 가지는 경로(Best path)가 선택되며 한번 선택된 Best path는 새로 업데이트된 3차원 장애물 지도 내 장애물 충돌이 있거나, UAV가 목적지까지 도착하게 되면 새로 업데이트 되는 방식으로 운용된다. 우리는 제안한 알고리즘을 사용하여 실제 실내 환경에서 자율 비행 실험을 통해 제안하는 시스템의 신뢰성 및 실시간성을 검증한다. 본 논문의 주된 기여는 다음과 같다.

• ‧ 3차원 회피 기동을 위해 LiDAR 스캔 또는 LiDAR SLAM으로부터 얻은 3차원 포인트 클라우드 데이터를 UAV 기준 롤 방향(Roll direction)으로 회전시켜 수평 평면에 해당하는 포인트들로 2차원 지도들을 생성한다.
• ‧ 생성된 2차원 지도들 내 장애물과의 거리가 고려된 유클리디안 거리(Euclidean distance) 기반 거리 비중 지도(Distance weight map)를 생성한다.
• ‧ 각각의 2차원 장애물 지도들과 거리 비중 지도들을 A* 알고리즘과 결합하여 경로들을 생성하고 그 중 제안하는 비용 함수를 사용하여 Best path를 선택한다.

2. 알고리즘

2.1 롤 방향 회전을 통한 3차원 장애물 지도 생성 알고리즘

복잡한 환경 내 UAV의 신뢰성 있는 자율 비행을 위해 3차원 장애물 지도 생성은 필수적이다. 이를 위해 LiDAR 센서로부터 얻은 scan 데이터 또는 LiDAR 센서 기반 SLAM으로부터 생성된 3차원 맵 데이터를 사용할 수 있으며, 데이터의 일관성과 Field of View (FOV)로 인한 장애물 정보 소실을 고려하여 본 논문에서는 LiDAR 센서 기반 SLAM 알고리즘에서 생성된 3차원 맵 데이터를 사용한다. LiDAR 센서 기반 SLAM은 본 연구진이 개발한 LiDAR Inertial Odometry 기법^[13]을 사용하였다. UAV가 자율 비행을 하며 생성한 3차원 맵 데이터를 $$ \mathit{M}=\left\{M_0,M_1,\cdots ,M_{n-1}\right\}$$ 이라 할 때 LIO로부터 추정한 맵 좌표계 내 UAV의 위치 T_t ∈ SE(3)를 사용하여 변환된 센서 좌표계(Body 좌표계) 내 3차원 맵 데이터 ^BM는 다음과 같이 표현할 수 있다.

$\[ {}^{\mathbf{B}}\mathit{M}={\mathbf{T}}_t^{-1}\mathit{M}, \]$

(1)

식 (1)에서 ^BM는 센서 좌표계 내 3차원 맵 포인트들의 x, y, z 값을 의미하며 ($$ {}^{\mathbf{B}}{\mathit{M}}_k\in R^3$$), M은 LiDAR 키프레임이 생성될 때 같이 업데이트 되어진다. UAV의 경로 생성을 위한 탐색 범위를 S (m)라 할 때 장애물 지도 생성을 위한 맵 포인트 $$ \mathit{U}=\left\{U_0,U_1,\cdots ,U_{n-1}\right\}$$는 ^BM 내에서 유클리디언 거리가 S 이내인 포인트들의 집합으로 구성된다(U_k∈R³).

기존의 3차원 격자 기반 경로 생성 알고리즘은 U 내 특정 격자 해상도를 적용하여 격자들을 생성하고 각 격자들의 연결성과 장애물 정보들을 고려하여 경로 생성을 수행한다. 하지만 이러한 기법의 접근은 특히 3차원 공간 내에서 격자의 해상도 및 장애물들의 배치에 따라 계산량이 매우 크게 변동하기 때문에 실시간으로 신뢰성 있는 경로 생성을 하는데 제약이 있다. 따라서 우리는 U를 롤(roll) 방향으로 θ degree씩 회전시키며 2차원 평면에 포함되는 포인트들을 생성하는 방법을 제안한다. U를 roll 방향으로 θ degree씩 회전시키며 z축 절대값이 d_z 이하인 포인트들의 집합 $$ {\mathbf{G}}_k^{\theta }$$는 다음과 같이 표현할 수 있으며 각 $$ {\mathbf{G}}_k^{\theta }$$을 포함하는 2차원 평면은 [Fig. 2]에 보여 진다.

$\[ {\mathbf{G}}_k^{\theta }=\left\{\left(x,y,z\right)\in \left({\mathit{R}}_g^{-1}{\mathit{R}}_{x_{k\theta }}^{-1}\mathit{U}\right)\left|\left|z\right|\right.\le d_z\right\}, \]$

(2)

[Fig. 2]

The planes that include each Gkθ. The grid resolution and width of each plane are generated differently depending on the k, and the number of planes varies depending on θ. The height of the planes is S and is the same for all planes

식 (2)에서 R_g는 현재 UAV의 위치에서 목적지까지의 상대적 회전 행렬을 의미한다. 마지막으로 R_xkθ는 x축으로(roll 방향) kθ degree 만큼의 회전 행렬을 의미한다$$ \left(k=\left\{\mathrm{0,1},\cdots ,\frac{180}{\theta }-1\right\}\right)$$. 제안하는 roll 방향 회전을 통한 포인트 추출방식은, θ에 따라 생성되는 2차원 평면들의 개수가 정해지며 θ의 크기에 따라 계산량과 경로 생성 신뢰성 사이 Trade-off 관계가 성립된다.

제안하는 $$ {\mathbf{G}}_k^{\theta }$$ 생성은 신뢰성 있는 자율 비행을 위해 3가지 전략을 가진다. 첫번째로 roll 회전각도에 따라 서로 다른 격자 해상도를 가진다. 두번째로 각 회전 각도에 따라 서로 다른 안전 거리(Safety distance)를 가진다. 마지막으로 각 회전 각도에 따라 서로 다른 평면의 너비(Width)를 가진다. 이는 UAV가 고도만 변경할 수 있는 상황, 평면 공간 내에서만 운용되어도 되는 상황, x, y, z 축 모두 제어되어야 하는 상황에 따라 안전하고 신뢰성 있는 운용을 위함이다.

기존에 특정 고도를 나누어 여러 층의 2차원 장애물 지도를 생성하는 방식에 비해 제안하는 장애물 지도 생성 방식은 유연한 UAV 경로 생성(대각선, 고도만 변경, 고도 유지 및 평면 비행 등)이 가능하다는 이점이 있다. 제안하는 기법을 사용하여 생성한 $$ {\mathbf{G}}_k^{\theta }$$의 예시는 [Fig. 3]에 보여 진다. 다음으로 우리는 생성된 $$ {\mathbf{G}}_k^{\theta }$$을 사용하여 각각의 2차원 격자 장애물 지도를 생성하였다. $$ {\mathbf{G}}_k^{\theta }$$에 포함된 포인트들을 $$ {\mathrm{G}}_{k,i}^{\theta }\left(i=\mathrm{0,1}, \cdots j-1\right)=\left\{x_i,y_i,z_i\right\}$$라 할 때 각 $$ {\mathbf{G}}_k^{\theta }$$에 해당하는 2차원 격자 장애물 지도 $$ {\mathrm{C}}_k^{\theta }$$는 다음과 같이 표현할 수 있으며 결과는 [Fig. 4]에 보여 진다.

$\[ r_i=⌊\frac{\left|x_{min }\right|}{res}+1+\frac{x_i}{res}⌋, \]$

(3)

$\[ c_i=⌊\frac{\left|y_{min}\right|}{res}+1+\frac{y_i}{res}⌋\text{,} \]$

(4)

$\[ {\mathrm{C}}_k^{\theta }\left[r_i\right]\left[c_i\right]=100 \]$

(5)

[Fig. 3]

Gkθ examples generated using the proposed method. In this figure, θ and dz were set to 30 degree and 0.2 respectively, and the pink grids represent the extracted Gkθ from each plane. The Gkθ extracted from each plane has a different safety distance depending on kθ, resulting in a total of 6 planes generated

[Fig. 4]

The result of generating Ckθ (right) from Gkθ (left). The yellow map in the left picture represents M, and the pink grid represents Gkθ. The right picture shows Ckθ, and the orientation changes depending on the current position of the UAV and the goal point

식 (3)~(5)에서 x_min과 y_min은 2차원 장애물 지도 내 x, y 축 최소 값(m)을 의미하며 res는 사전에 정의된 장애물 지도의 격자 해상도, W는 지도의 너비를 나타낸다$$ \left(W=\frac{\left(\left|x_{min}\right|+\left|x_{max}\right|\right)}{res}\right)$$. 또한 r_i와 c_i은 2차원 격자 지도 내 $$ {\mathbf{G}}_{k,i}^{\theta }$$ 포인트가 해당되는 행과 열을 의미하며 최종적으로 2차원 격자 지도 내 인덱스 순서 n에 따라 100 (Occupied)이 할당되어진다. 다음으로 우리는 $$ {\mathrm{C}}_k^{\theta }$$을 사용하여 유클리디언 거리(Euclidean distance) 기반 장애물 거리 비중 지도 $$ {\mathrm{D}}_k^{\theta }$$을 생성한다^[14]. 기존 A* 알고리즘^[15]은 주로 $$ {\mathrm{C}}_k^{\theta }$$만을 사용하여 경로를 생성하지만 최단 경로를 찾는 알고리즘의 특성상 장애물과 매우 근접한 경로가 생성되어 안정성 측면에서 제약이 있다. 하지만 제안하는 기법은 거리 비중 지도를 생성하여 장애물 과의 거리 또한 고려된 안전한 장애물 회피 경로를 생성할 수 있기 때문에 복잡한 실내 환경에서 신뢰성 있는 UAV 운용이 가능하다는 이점이 있다. $$ {\mathrm{C}}_k^{\theta }$$에 유클리디언 거리 기반 확률 기법을 적용한 $$ {\mathrm{D}}_k^{\theta }$$은 식 (6)과 같이 표현할 수 있으며 제안하는 3차원 장애물 지도 생성의 계층적 결과는 [Fig. 5]에 보여 진다.

$\[ {\mathrm{D}}_k^{\theta }=\mathit{E}\mathit{u}\mathit{c}\mathit{l}\mathit{i}\mathit{d}\mathit{e}\mathit{a}\mathit{n}\mathit{ }\mathit{D}\mathit{i}\mathit{s}\mathit{t}\mathit{a}\mathit{c}\mathit{n}\mathit{e}\mathit{ }\mathit{T}\mathit{r}\mathit{a}\mathit{n}\mathit{s}\mathit{f}\mathit{o}\mathit{r}\mathit{m}\left({\mathrm{C}}_k^{\theta }\right) \]$

(6)

[Fig. 5]

Hierarchical 3D costmap generation results. (a) Gkθ generated from 3D map points BM. (b) 2D grid map Ckθ generated from Gkθ. (c) Distance map Dkθ generated from Ckθ. (d) Dkθ generated for each Gkθ

2.2 3차원 경로 생성 및 Best path 선택 알고리즘

생성한 여러 개의 2차원 장애물 지도 내에서 장애물 회피 경로 생성은 A* 알고리즘을 통해 수행된다. 앞서 언급 했듯이 기존 A* 알고리즘은 최단 거리 경로를 생성하기 때문에 장애물과의 거리가 매우 가까워 무인 이동체 운용 시 장애물과의 충돌 가능성이 매우 크다. 따라서 우리는 안전한 자율 비행 UAV 운용을 위해 장애물과의 거리가 고려된 거리 비중 지도 기반 신뢰성 있는 회피 경로 생성 알고리즘을 제안한다.

거리 비중 지도가 고려된 제안하는 A* 알고리즘의 비용 함수(Cost function) F(n)은 다음과 같이 표현할 수 있으며 결과는 [Fig. 6]에 보여 진다.

$\[ F\left(n\right)=G\left[a\right]\left[b\right]+H\left[a\right]\left[b\right]-w_D\mathrm{*}{\mathrm{D}}_k^{\theta }\left[a\right]\left[b\right] \]$

(7)

[Fig. 6]

Result of the path generated by the proposed A* cost function that consider the distance-weighted map Dkθ. (a) Path generated by the conventional A* algorithm. (b) Path result generated by the proposed A* cost function. The proposed method enables the generation of safer paths compared to the conventional A* algorithm by considering the Dkθ

식 (7)에서 G[a][b]는 2차원 격자 장애물 지도 $$ {\mathrm{C}}_k^{\theta }$$의 a행 b열의 거리 비용(시작점부터 해당 위치까지의 거리)을 의미하며 H[a][b]는 목적지까지의 거리 비용(해당 위치로부터 목적지 까지의 최단거리 비용)을 의미한다. $$ {\mathrm{D}}_k^{\theta }\left[\mathrm{a}\right]\left[\mathrm{b}\right]$$는 거리 비중 지도의 a행 b열에 해당하는 거리 비중 값을 의미하며 장애물에 가까울수록 큰 값을 가지기 때문에 gain인 w_D에 곱해져 최종 비용 함수 내 음수 factor로 작용하게 된다. 우리는 $$ {\mathbf{G}}_k^{\theta }$$로부터 생성한 각각의 $$ {\mathrm{C}}_k^{\theta }$$과 $$ {\mathrm{D}}_k^{\theta }$$내에서 제안하는 경로 생성 알고리즘을 수행하며 각 $$ {\mathbf{G}}_k^{\theta }$$로부터 생성한 3차원 경로를 $$ {\mathit{L}}_k^{\theta }=\left\{L_{k,j}^{\theta }\right\}$$이라 할 때 결과는 [Fig. 7]에서 보여 진다.

[Fig. 7]

The result of Lkθ generated within each Gkθ. Lkθ is generated using Ckθ and Dkθ as well as the proposed cost function, and the safe distance and grid resolution are set differently depending on the roll angle. The yellow map points represent U, and the pink grid points represent Gkθ. The colored paths represent the resulting path generated in each plane

A* 알고리즘과 같은 격자 기반 경로 생성 알고리즘은 격자로 연결된 공간 내 경로를 탐색하는 알고리즘의 특성 상 jerky한 경로가 생성된다. 하지만 이러한 경우 UAV가 경로를 추종하며 비행할 때 공격적인 움직임이 야기되어 비행이 불안정해지는 단점이 있다. 이를 해결하기 위해 우리는 생성된 $$ {\mathit{L}}_k^{\theta }$$에 3차 spline 함수를 적용하여 경로 안정화(smoothing)를 수행하며 결과는 [Fig. 8]에 보여 진다. 각 $$ {\mathbf{G}}_k^{\theta }$$로부터 생성한 안정화된 $$ {\mathit{L}}_k^{\theta }$$ 결과는 [Fig. 9]에 보여 진다. 마지막으로 우리는 생성된 $$ {\mathit{L}}_k^{\theta }$$ 결과들 중 Best path를 선정한다. Best path 선정을 위해 사용한 제안하는 objective function은 다음과 같이 표현할 수 있다.

$\[ \begin{array}{c}{k}_{\text{best }}=\underset{k}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\sum _j\left(w_{\theta }\mathrm{s}\mathrm{i}\mathrm{n}\left(k\theta +{ϵ}_k\right)∥L_{k,j}^{\theta }-L_{k,j-1}^{\theta }∥\right.\hfill \\ \left.+w_g\left(k-k_{\text{prev}}\right)\right)\hfill \end{array} \]$

(8)

[Fig. 8]

Smoothed Lkθ using the 3rd order spline method. (a) Before applying the 3rd order spline method. (b) After applying the spline method. By applying the 3rd order spline method to Lkθ, we enabled the UAV to have stable control values when following the path

[Fig. 9]

The result of smoothed Lkθ generated within Gkθ. The 3rd order spline is applied to all Lkθ. The white map represents M, and the colored paths represent the smoothed Lkθ

식 (8)에서 w_θ, ϵ_k은 각각 roll angle에 따른 가중치, 평면에 따른 bias를 의미한다. w_g는 이전에 선택된 Best path group에 따른 가중치를 의미하며 이는 새로 Best path를 선택해야할 때 이전에 선택된 평면과 최대한 가까운 index의 평면을 선택하게 함으로서 UAV가 급격하게 비행하는 평면의 roll 각도를 변경하지 않도록 한다.

제안하는 objective function를 해석하면 다음과 같다. 첫번째 $$ w_{\theta }\mathrm{s}\mathrm{i}\mathrm{n}\left(k\theta +{ϵ}_k\right)$$은 roll angle term을 의미하며 각 평면의 회전된 roll angle의 기울기에 따라 비례하여 증가하기 때문에 UAV가 수평면 상에서 충분한 회피기동이 가능한 경우 가능한 수평면으로 비행하도록 한다. 두번째 $$ ∥L_{k,j}^r-L_{k,j-1}^r∥$$은 path length term으로 가장 최단 거리를 가지는 경로로 비행하도록 한다. 마지막으로 $$ w_g\left(k-k_{\text{prevs}}\right)$$는 group term으로 새로 Best path를 선정해야 하는 경우 이전에 선택되어진 평면으로부터 제일 가까운 index를 가지는 평면을 선택하도록 하여 UAV가 급격하게 비행하는 평면을 바꾸지 않도록 한다.

제안하는 objective function은 이와 같은 전략을 바탕으로 Best path를 선정하며 이는 UAV가 실제 환경에서 필드 테스트를 수행할 시 실용적이고 안전하게 비행할 수 있도록 설정되었다. 선정된 Best path를 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$라 할 때 그 결과는 [Fig. 10]에 보여 진다. 한번 선정된 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$은 새로 업데이트 된 U 내 포인트들과 충돌이 발생하거나, UAV가 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$을 따라 목적지까지 도착했을 때 새로 업데이트 되어진다.

[Fig. 10]

Best path Lkbest θ selection result according to the situation. (a) The horizontal path (k = 0) is selected as Lkbest θ, and the UAV flies into the minivan. (b) The diagonal path (k = 2) is selected as Lkbest θ, and the UAV flies diagonally over the minivan. The yellow map points represent M and the colored paths represent Lkθ. The white bold path represents the Lkbest θ

3. 실험결과

본 연구에서 제안하는 3차원 장애물 지도 생성 및 경로 계획 알고리즘을 검증하기 위해 우리는 실제 UAV에 장착되어 있는 온보드 컴퓨터 내 알고리즘을 탑재하여 필드 테스트를 수행하였다. 필드 테스트 수행 시 사용한 UAV는 자체 제작한 8인치 쿼드로터로 [Fig. 11] LiDAR 센서는 Ouster사의 OS1 32채널 모델을 사용하였고, 온보드 컴퓨터로는 Intel사의 i7-10710U CPU가 탑재된 NUC 모델을 사용하였다. 필드 테스트에서 우리는 장애물 지도 생성을 위해 θ = 30, S = 20을 적용하였다. 필드 테스트 장소로 우리는 경기도 일산 킨텍스 전시장 내 실내 비행장을 설치하여 실험을 진행하였다. 실험을 진행한 실내 비행장은 일반 벽, 수직으로만 회피할 수 있는 벽, 기둥, 좁은 통로, 철물 등으로 구성된 복합적인 환경이며 비행장 내 직각 부분들에 해당하는 지점 만 waypoint로 설정하였고 필드 테스트 결과는 [Fig. 12]에 보여 진다. [Fig. 12]에서 보여 지듯 제안하는 기법은 다양한 복합적인 장애물들로 구성되어 있는 환경에서 안전하고 신뢰성 있는 경로 생성 결과를 보여준다.

[Fig. 11]

The customized autonomous UAV platform used during field testing. To conduct testing in an indoor

[Fig. 12]

Autonomous UAV flight field test conducted in an indoor environment at KINTEX, Ilsan. The left image shows the UAV’s 1st Person View (FPV), while the right image represents Lkθ generated for 3D obstacle avoidance. (a) Wall avoidance in the horizontal direction. (b) Wall avoidance in the vertical direction. (c) Flight between narrow passages. (d) Diagonal flight for steel structure avoidance. The white bold path represents the Lkbest θ

첫번째 시나리오 [Fig. 12(a)]에서 UAV는 정면에 배치된 벽을 회피하기 위해 생성한 $$ {\mathit{L}}_k^{\theta }$$ 들 중 수평 방향 경로 (k = 0)인 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$를 선택하였다. 두번째 시나리오 [Fig. 12(b)]에서 UAV는 수직으로 배치된 벽을 회피하기 위해 $$ {\mathit{L}}_k^{\theta }$$ 들 중 대각선 경로 (k = 2)에 해당하는 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$를 선택하였으며 세번째 시나리오 [Fig. 12(c)]에서는 좁은 통로를 비행하기 위해 대각선 경로 (k = 5)에 해당하는 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$를 선택하였다. 마지막 시나리오 [Fig. 12(d)]도 마찬가지로 UAV는 철제 구조물을 회피하기 위해 대각선 경로 (k = 2)에 해당하는 $$ {\mathit{L}}_{k_{\text{best }}}^{\theta }$$를 선택하였다. 각 시나리오에서 UAV의 3rd person view는 [Fig. 13]에서 보여 지며 비행 실험장 내 UAV의 비행 경로는 [Fig. 14]에서 보여 진다.

[Fig. 13]

3rd person view of the UAV for each scenario. The UAV flies along the selected Lkbest θ, and when it reaches the destination, a new Lkbest θ is generated towards the new destination. Lkbest θ with a cubic spline method allows the UAV to follow a more stable path

[Fig. 14]

The trajectory of a UAV. The yellow map point indicates M and the white arrow indicates the UAV’s trajectory. As shown in the Top View, the UAV arrived at the destination avoiding various obstacles, and the Side View shows the altitude change in the region A and B

실내 비행장 내 취득한 맵 데이터를 사용하여 본 연구에서 제안하는 3차원 장애물 지도 생성 및 경로 생성 기법의 계산량을 기존 격자 기반 탐색 알고리즘인 3차원 A* 알고리즘^[16]과 비교하였다. 정확한 비교를 위해 격자 해상도(Grid resolution)은 0.05 m, 탐색 공간 S는 20 m로 설정하였다. 3차원 맵 포인트 개수에 따른 3차원 경로 생성 계산 시간 비교는 [Fig. 15]에 보여 진다. [Fig. 15]에서 보여지듯 제안하는 기법은 3차원 맵 포인트들의 개수가 증가할 때 기존 3차원 A*알고리즘에 비해 계산 시간 증가량이 작았으며 실험 조건 내 최대 4배이상 빠른 계산 시간을 보였다.

[Fig. 15]

Comparison of 3D path generation computation time according to the number of 3D map points. While the computation time of the conventional 3D A* algorithm increases exponentially according to the number of map points, the computation time of the proposed method is up to 4 times faster than the previous method through a novel 3D costmap generation method

마지막으로 더 나은 비교 분석을 위해 제안하는 기법의 성능을 기존 3차원 A* 알고리즘과 RRT* 알고리즘을 사용하여 시뮬레이션 환경 내 비교하였다. 비교를 위해 우리는 랜덤한 형태의 장애물들로 공간을 구성하였으며 시작점으로부터 약 150 m 떨어진 목적지에 도달하는데 걸린 계산 시간과 경로 생성 결과, 장애물과의 거리를 비교하였다. 총 4번의 시뮬레이션 환경 내 비교 결과는 [Fig. 16]에 보여 지며 정량적 비교는 [Table 1]에 보여 진다.

[Fig. 16]

Path generation results for four random scenarios within the simulation environment. The white path, blue path, and yellow path represent the results of Lkbest θ, RRT*, and A* respectively. The orange tree represents the tree generated by random samples from RRT* algorithm

[Fig. 16] 과 [Table 1]에서 보이듯이 RRT* 알고리즘의 경로 생성 결과는 탐색 공간 내 랜덤 샘플링 기법으로 인해 UAV가 추종하기에는 jerky한 결과를 보이며 경로 길이 또한 A* 알고리즘에 비해 큰 경향을 보였다. 또한 기존 3차원 A*알고리즘은 제안하는 기법과 비교해 보았을 때 계산 비용이 약 4배에서 경우에 따라 약 5배이상 큰 결과를 보였으며 장애물과의 거리는 제안하는 기법에 비해 작은 결과를 보인다. 이는 식 (7)에서 제안하는 거리 비중 지도가 고려된 A*의 비용함수가 총 경로 길이와 장애물과의 거리 사이 균형을 맞추는 것을 의미하며 이는 우리가 제안하는 3차원 장애물 지도 생성 및 경로 생성 방식이 복잡한 3차원 환경 내에서 실용적이고 신뢰성 있게 동작한다는 것을 보여준다.

[Table 1]

The performance comparison results in the simulation environment

4. 결 론

본 논문에서 우리는 새로운 3차원 장애물 지도 생성 및 장애물 회피 경로 생성 알고리즘에 대해 소개하였다. 제안하는 기법은 3차원 맵 포인트들을 roll 방향으로 회전시키며 평면에 해당하는 포인트들을 추출하고 이를 여러 2차원 장애물 지도로 생성하여 A* 알고리즘 기반 경로를 생성하는 방식이다. 생성된 경로들 중 우리는 제안하는 objective function을 사용하여 Bests path를 선정하였으며, 제안하는 목표 함수는 roll angle term, path length term, group term으로 이루어져 UAV가 최종적으로 추종할 경로의 안정성 및 실시간성을 증가시킬 수 있었다. 또한 제안하는 기법을 사용하여 실제 실내 비행장 내 자율 비행 실험을 수행하였으며, 다양한 장애물들이 복잡하게 배치되어 있는 환경 내에서도 UAV는 안전하고 신뢰성 있는 3차원 장애물 회피 경로 생성을 통해 최종 목적지까지 한차례의 충돌 없이 완벽하게 비행하였다. 추후 제안하는 기법이 탐사, 정찰, 구조 등 다양한 실내 자율 비행 미션에 적용되기를 기대한다.

Acknowledgments

This research was financially supported by the Institute of Civil Military Technology Cooperation funded by the Defense Acquisition Program Administration and Ministry of Trade, Industry and Energy of Korean government under grant No. UM22206RD2

References

• M. Petrlík, T. Báča, D. Heřt, M. Vrba, T. Krajník, and M. Saska, “A Robust UAV System for Operations in a Constrained Environment,” IEEE Robotics and Automation Letters, vol. 5, no. 2, pp. 2169-2176, Apr., 2020. [https://doi.org/10.1109/LRA.2020.2970980]
• M. Erdelj and E. Natalizio, “UAV-assisted disaster management: Applications and open issues,” International Conference on Computing, Networking and Communications (ICNC), Kauai, USA, 2016, pp. 1-5. [https://doi.org/10.1109/ICCNC.2016.7440563]
• Z. Xu, D. Deng, and K. Shimada, “Autonomous UAV Exploration of Dynamic Environments Via Incremental Sampling and Probabilistic Roadmap,” IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 2729-2736, Apr., 2021. [https://doi.org/10.1109/LRA.2021.3062008]
• B. Zhou, Y. Zhang, X. Chen, and S. Shen, “FUEL: Fast UAV Exploration Using Incremental Frontier Structure and Hierarchical Planning,” in IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 779-786, Apr., 2021. [https://doi.org/10.1109/LRA.2021.3051563]
• J. Tordesillas, B. T. Lopez, and J. P. How, “FASTER: Fast and Safe Trajectory Planner for Flights in Unknown Environments,” IEEE International Workshop on Intelligent Robots and Systems (IROS), Macau, China, 2019, pp. 1934-1940. [https://doi.org/10.1109/IROS40897.2019.8968021]
• X. Zhou, Z. Wang, H. Ye, C. Xu, and F. Gao, “EGO-Planner: An ESDF-Free Gradient-Based Local Planner for Quadrotors,” IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 478-485, Apr., 2021. [https://doi.org/10.1109/LRA.2020.3047728]
• P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, Jul., 1968. [https://doi.org/10.1109/TSSC.1968.300136]
• K. Naderi, J. Rajamäki, and P. Hämäläinen, “RT-RRT*: a real-time path planning algorithm based on RRT,” Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games, pp. 113-118, 2015. [https://doi.org/10.1145/2822013.2822036]
• J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic,” IEEE International Workshop on Intelligent Robots and Systems (IROS), Chicago, USA, 2014, pp. 2997-3004. [https://doi.org/10.1109/IROS.2014.6942976]
• J. Wang, T. Li, B. Li, and M. Q.-H. Meng, “GMR-RRT*: Sampling-Based Path Planning Using Gaussian Mixture Regression,” IEEE Transactions on Intelligent Vehicles, vol. 7, no. 3, pp. 690-700, Sept., 2022. [https://doi.org/10.1109/TIV.2022.3150748]
• C. Zammit and E.-J. Van Kampen, “Comparison between A* and RRT Algorithms for UAV Path Planning,” 2018 AIAA Guidance, Navigation, and Control Conference, Kissimmee, Florida, Jan., 2018. [https://doi.org/10.2514/6.2018-1846]
• A. G. H. Qahtan and AL-Baiati A. Emad, “Path-Planning Dynamic 3D Space Using Modified A* Algorithm,” IOP Conference Series.Materials Science and Engineering, vol. 928, 2020. DOI:10.1088/1757-899X/928/3/032016. [https://doi.org/10.1088/1757-899X/928/3/032016]
• B. Kim, C. Jung, D. H. Shim, and A. Agha–mohammadi, “Adaptive Keyframe Generation based LiDAR Inertial Odometry for Complex Underground Environments,” IEEE International Conference on Robotics and Automation (ICRA), London, United Kingdom, 2023. [https://doi.org/10.1109/ICRA48891.2023.10161207]
• L. Han, F. Gao, B. Zhou, and S. Shen, “FIESTA: Fast Incremental Euclidean Distance Fields for Online Motion Planning of Aerial Robots,” IEEE International Workshop on Intelligent Robots and Systems (IROS), Macau, China, 2019. [https://doi.org/10.1109/IROS40897.2019.8968199]
• D. Foead, A. Ghifari, M. B. Kusuma, N. Hanafiah, and E. Gunawan, “A systematic literature review of a* pathfinding,” Procedia Computer Science, vol. 179, pp. 507-514, 2021. [https://doi.org/10.1016/j.procs.2021.01.034]
• T. K. Nobes, D. D. Harabor, M. Wybrow, and S. D. C. Walsh, “The JPS pathfinding system in 3D,” Proceedings of the International Symposium on Combinatorial Search, 2022. [https://doi.org/10.1609/socs.v15i1.21762]