협소 공간에서의 다중 비행로봇 명령 포메이션 시퀀스 생성 기법

I. 서론

비행로봇 기술의 발전에 따라 비행로봇의 활용 범위는 확장되고 있다. 특히 다수의 비행로봇이 협력하여 임무를 수행하는 포메이션 제어 기술은 집단 비행의 효율성과 안정성을 향상시키는 핵심 기술로 주목받고 있다. 다중 로봇이 일정한 포메이션을 유지하며 임무 경로를 따라 이동하기 위해서는, 각 로봇이 동일한 환경 정보를 공유하고 충돌 없이 이동할 수 있는 경로를 효율적으로 생성하는 것이 중요하다. 이러한 요구를 충족하기 위해 다양한 포메이션 제어 및 협조 제어 연구가 수행되었으며, 이를 통해 포메이션의 안정성과 임무 수행 효율성을 확보하기 위한 다양한 접근이 제안되었다. 정상 및 장애 상황에서 다중 로봇의 포메이션 제어 전략을 고찰한 연구[1], 임무 영역을 공간적으로 분할하여 효율적인 경로 계획을 수행한 다중 로봇 탐색 연구[2]가 그 대표적인 예이다. 이와 더불어, 탐색 및 감시를 위한 다중 비행로봇의 협조 경로 계획[3], 작업 할당과 경로 계획을 통합한 MAPF (Multi-Agent Path Finding) 기반 다중 로봇 제어 프레임워크[4], 농업 환경에서의 협조 이동을 위한 작업 영역 최적화 연구[5]등 응용 중심의 연구도 활발히 이루어졌다. 또한 다중 비행로봇 시스템의 장애 허용 포메이션 제어 연구[6]에서는 일부 구성원의 손실 상황에서도 안정적인 형상 유지가 가능함을 확인하였다. 포메이션 제어 성능 향상을 위해 PSO (Particle Swarm Optimization) [7]와 BAT (Bat Algorithm) [8]과 같은 진화형 최적화, LFT (Local Formation Transformation) [9]이나 Swarm Morphing [10]을 이용한 포메이션 변형 기법이 제안되었으며, 그래프 기반 분산 제어[11] 및 MPC (Model Predictive Control) [12]를 적용하여 충돌 회피와 형상 유지를 동시에 달성하려는 연구도 진행되고 있다.

이와 같은 연구 흐름을 기반으로, 참고문헌 [13]에서는 좁은 통로가 포함된 복잡한 실내 환경에서 다중 모바일 로봇의 실시간 대형 전환을 수행하기 위한 그래프 탐색 기반 포메이션 계획 방법을 제안하였다. 해당 방법은 2차원 Occupancy Grid 상에서 다양한 yaw 회전각과 스케일별 포메이션 후보를 생성하고, A* 탐색을 통해 구간별 포메이션 전환 시퀀스를 결정하여 안정적인 대형 전환을 실현하였다. 또한 MPC 제어를 적용해 각 로봇이 전환된 포메이션을 추종하도록 함으로써 협소 공간에서도 포메이션 유지가 가능함을 확인하였다.

그리고 다중 비행로봇의 고수준 행동을 그래프 구조로 모델링하여 시퀀스를 계획하려는 연구도 진행되었다. LTL (Local Temporal Logic) 기반 군집 임무 계획 연구에서는 요구되는 임무 조건을 상태전이 모델로 변환하여 UAV의 고수준 행동 시퀀스를 생성한다[14].

다중 비행로봇 시스템의 포메이션 경로 계획 문제는 전역 경로를 따라 이동하는 동안 각 시점의 비행로봇 배치를 결정하고, 환경 제약 내에서 안정적인 포메이션 전환 시퀀스를 생성하는 것을 목표로 한다. 그러나 기존 방법[13]의 접근은 2차원 평면에 한정되어 3차원 공간으로 확장하기 어렵고, yaw와 스케일의 모든 조합을 사전에 생성해야 하므로 협소 구간에서 후보 수가 급증하여 탐색 효율이 저하되는 한계를 가진다. 이러한 한계는 복잡한 3차원 환경에서 포메이션의 축소·확장 및 회전 이동을 제한하며, 각 구간에서 생성되는 후보가 많을수록 그래프 규모가 급격히 증가해 연산 부하가 비선형적으로 커진다. 특히 yaw 회전각과 스케일의 전체 조합을 사전 생성하는 기존 방법은 장애물 밀집 환경에서 반복적인 충돌 검증을 유발하여 탐색시간이 과도하게 증가한다. 이로 인해 3차원 확장성과 탐색 효율 간의 상충관계가 발생하며, 이는 실시간 적용을 어렵게 만든다.

본 논문은 이러한 한계를 해결하기 위해 3차원 환경에서 다중 비행로봇의 안정적인 포메이션 전환을 지원하는 명령 포메이션 시퀀스 생성 기법을 제안한다. 제안 기법은 공간 제약과 탐색 비효율을 개선함으로써 협소한 통로나 입체 장애물이 존재하는 환경에서도 효율적이고 안정적인 명령 포메이션 시퀀스 생성을 가능하게 한다.

II. 그래프 기반 명령 포메이션 시퀀스 생성

본 장에서는 다중 비행로봇 군집의 이동을 포메이션 단위의 상태 전이 문제로 정의하고, 3차원 공간으로 확장한 그래프 기반 명령 포메이션 시퀀스 생성 알고리즘을 제안한다. 제안 방법은 참고문헌 [13]의 기존 2차원 평면 탐색 구조를 3차원 공간으로 확장하여 그림 1과 같은 협소 공간에서 군집 비행로봇의 충돌 회피를 위한 명령 포메이션 시퀀스 생성을 하기 위해 3차원 포메이션 그래프의 노드를 선별적으로 생성하고 이로 인한 그래프 탐색시간의 감소를 목적으로 한다.

Fig. 1.

Example of formation control for multiple flying robots in a confined indoor environment.

제안된 명령 포메이션 시퀀스 생성의 전체 흐름은 그림 2와 같다. 먼저 전역 경로의 노드를 일정 간격으로 균등화하고, 각 노드마다 맵 장애물과 충돌하지 않고 포메이션을 이루는 비행로봇 간 안전거리를 유지가능한 공간 배치와 스케일을 갖는 각 패턴별 포메이션 후보를 생성한다. 이후 인접 노드 간의 전이비용을 계산하여 그래프 형태의 연결망을 구성하고, 탐색 알고리즘을 적용하여 누적 비용이 최소인 포메이션 시퀀스를 도출한다. 이 과정에서 각 포메이션 후보는 인접 노드 간 패턴 변화를 최소화하며, 탐색 결과로 얻어진 시퀀스는 포메이션 단위의 연속적인 이동 궤적으로 표현된다. 이 방법은 경로의 노드 간격 균등화, 포메이션 후보 생성, 전이비용 계산, 탐색 및 시퀀스 결정의 네 단계로 구성된다.

Fig. 2.

Graph-based formation sequence generation flowchart.

본 연구에서는 전역 경로를 따라 이동하는 과정에서 각 경로의 노드마다 적용 가능한 포메이션 상태들을 정의하고, 이들 상태 간의 전이를 이동 거리, 목표 패턴 접근성, 회전 안정성, 패턴 전환 여부를 반영한 비용으로 평가함으로써 포메이션 시퀀스 생성 문제를 그래프 탐색 문제로 구성한다. 이러한 정의를 바탕으로, 전역 경로 전체에서 누적 비용이 최소가 되는 포메이션 상태들의 조합을 탐색 알고리즘을 통해 선택하고 이는 최종 포메이션 시퀀스가 된다.

2. 포메이션 후보 생성

전역경로의 노드 𝑘에서 포메이션 후보는 전역 경로가 정의되는 전역 좌표계(Global frame)와 포메이션 패턴이 정의되는 포메이션 기준 좌표계(formation frame)를 구분하여 표현된다. 여기서 포메이션 기준 좌표계는 개별 비행 로봇의 body-fixed frame과 구분되는 가상의 좌표계로서 포메이션 전체의 상대 배치를 정의하기 위해 도입된다. 각 포메이션 후보는 기준위치 𝑐^(𝑘) = [𝑥^(𝑘), 𝑦^(𝑘), 𝑧^(𝑘)]^𝑇, 스케일 𝑠^(𝑘) > 0, 패턴의 회전 상태 𝑟^(𝑘) = (𝜓^(𝑘), 𝜃^(𝑘), 𝜙^(𝑘))로 정의된다. 여기서 𝑟^(𝑘)는 포메이션의 회전 상태를 나타내는 3차원 벡터이며, 𝜓^(𝑘), 𝜃^(𝑘), 𝜙^(𝑘)는 각각 yaw, pitch, roll 각도를 의미한다. 포메이션 기준 좌표계는 전역 경로의 𝑘번째 노드인 포메이션 기준점 𝑐^(𝑘)에 고정된 좌표계로서, 포메이션 패턴 내 𝑖번째 비행로봇의 상대 위치 𝑜_𝑖는 포메이션 기준 좌표계에서 정의된다.

$\[ o_i={[x_i,y_i,z_i]}^T(i=1,\dots ,N) \]$

(1)

식 (1)에서 𝑥_𝑖, 𝑦_𝑖, 𝑧_𝑖는 각 비행로봇의 상대 위치를 나타내고, 𝑁은 비행로봇의 수를 의미한다. 포메이션 패턴 F={A, B, C}은 개별 비행로봇의 전역 좌표계 위치와 무관하게 비행로봇 간의 상대적인 배치 형상을 정의한 것이다. 그림 3과 같이 이 A, B, C의 패턴은 𝑥_𝑖, 𝑦_𝑖, 𝑧_𝑖 간격의 조합으로 결정된다.

Fig. 3.

Examples of formation patterns.

포메이션 후보 패턴의 각 비행로봇 𝑖의 전역 좌표계 위치 $$ p_i^{\left(k\right)}$$는 yaw, pitch, roll 회전과 스케일, 평행이동을 결합하여 다음과 같이 계산된다.

$\[ p_i^{\left(k\right)}=c^{\left(k\right)}+s^{\left(k\right)}{R}_z\left({\psi }^{\left(k\right)}\right)R_y\left({\theta }^{\left(k\right)}\right)R_x\left({\varphi }^{\left(k\right)}\right)o_i \]$

(2)

그림 4는 식 (2)에 사용된 좌표계와 변수들의 관계를 나타낸다. 식 (2)에 포함된 회전 행렬 𝑅_𝑧(𝜓^(𝑘))𝑅_𝑦(𝜃^(𝑘))𝑅_𝑥(𝜙^(𝑘))는 포메이션 기준 좌표계에서 정의된 상대 위치 𝑜_𝑖에 대해 포메이션의 yaw, pitch, roll 회전을 적용하는 역할을 한다.

Fig. 4.

Conceptual illustration of formation reference frame and UAV position computation in the global frame.

포메이션은 경로의 진행 방향에 맞춰 yaw와 pitch 회전으로 정렬되며, roll 각도 𝜙^(𝑘)는 전역경로로부터 직접 계산되지 않고, 각 노드 𝑘마다 후보 집합 𝜙 = {−90°, −45°, 0°, 45°, 90°}중 선택되어 생성된다. 이를 통해, 그림 5와 같이 포메이션을 하나의 강체로 간주하여 입체적 회전을 적용함으로써 각 전역경로 노드에서 3차원 자세가 정의된다.

Fig. 5.

Rotation of a formation pattern.

이후 스케일 𝑠^(𝑘)를 적용하고, 기준점 𝑐^(𝑘)에 대한 평행이동을 수행함으로써, 전역 경로 상에서 각 비행로봇의 전역 좌표계 위치 $$ p_i^{\left(k\right)}$$가 계산된다.

포메이션의 스케일 𝑠^(𝑘)은 비행로봇 간 충돌을 방지하고 환경의 여유 공간을 반영하기 위해, 각 전역경로 노드에서 장애물까지의 거리 정보를 기반으로 결정한다. 본 연구에서는 맵 환경을 OctoMap 기반의 3차원 점유 격자로 표현하며, 장애물은 점유 상태로 표시된 voxel들의 집합으로 정의된다. 각 voxel은 공간 내에서 일정 크기를 갖는 셀을 의미하며, 해당 voxel의 중심 좌표를 장애물 위치를 대표하는 점으로 사용한다. 기준위치 𝑐^(𝑘)와 각 점유 voxel 중심 좌표 간의 유클리드 거리를 계산한 후, voxel의 반경에 해당하는 값을 보정함으로써 기준위치로부터 장애물 표면까지의 최소 거리를 산출한다. 이를 통해 계산된 최근접 거리 𝑑^(𝑘)는 기준위치 𝑐^(𝑘)와 가장 가까운 장애물 표면 사이의 거리로 정의된다. 최근접 거리 계산은 다수의 voxel에 대해 효율적으로 수행하기 위해 KD-tree 기반 최근접 이웃 탐색을 이용하여 구현하였다. 이렇게 얻은 𝑑^(𝑘)와 기준 포메이션 반경 𝑟₀을 바탕으로 𝑠^(𝑘)를 다음과 같이 산출한다.

(3)

식 (3)에서 d_s는 최소 안전 거리이며, s_min은 포메이션을 구성하는 기체 간 거리가 최소 안전 거리보다 좁아지지 않도록 보장하는 최소 축소 한계 값이다. 이 값은 기준 포메이션 반경 r₀과 최소 안전 거리 d_s의 비율로 정의되며, 다음과 같이 계산된다.

$\[ s_{min}=\frac{{\mathrm{d}}_s}{r_0} \]$

(4)

식 (4)는 포메이션이 축소될 수 있는 최소 비율을 나타내며, 각 구간의 장애물 분포에 따라 포메이션 크기가 조정된다. 좁은 통로에서는 d^(k)가 작아져 포메이션이 축소되고, 반대로 개방된 공간에서는 s^(k)가 최대 1.0까지 증가하여 공간 활용 효율을 높인다.

회전 변환과 스케일 조정이 적용된 각 포메이션 후보는 그래프 구성 이전 단계에서 유효성을 검증하는 과정을 거친다. 우선, 포메이션 내부에서 각 비행로봇 간의 간격이 최소 안전 거리 이하로 좁아지는 후보는 제거된다. 이러한 내부 충돌 검증은 포메이션을 구성하는 모든 비행로봇 쌍 (i,j)에 대해 다음의 거리 제약을 통해 수행된다.

$\[ \Vert p_i^{\left(k\right)}-p_j^{\left(k\right)}\Vert \ge d_m, \forall \mathrm{i}\ne j \]$

(5)

식 (5)에서 d_m은 비행로봇 간 최소 안전 거리로, 포메이션 내부 충돌을 방지하기 위한 기준값이다. 다음으로, 각 비행로봇이 장애물과의 최소 안전 거리를 확보하는지를 확인한다. 기준위치 c^(k) 주변의 장애물 점유 영역으로부터 각 로봇의 최근접 거리 $$ D\left(p_i^{\left(k\right)}\right)$$ 를 계산하고, 아래의 조건을 만족하지 않는 후보는 제거된다.

$\[ D\left(p_i^{\left(k\right)}\right)\ge {\mathrm{d}}_s, \forall \mathrm{i}=1,\dots ,N \]$

(6)

식 (6)에서 d_s는 비행로봇–장애물 간 최소 안전 거리이며, $$ D\left(p_i^{\left(k\right)}\right)$$는 비행로봇 i 의 위치 $$ p_i^{\left(k\right)}$$로부터 가장 가까운 장애물까지의 유클리드 거리를 반환하는 함수이다. 이 두 단계의 검증을 통해 내부 및 외부 충돌 검사를 통과한 후보만 그래프 노드로 정의된다. 결과적으로, 이러한 사전 필터링 과정은 그래프의 불필요한 구성 노드 수를 줄인다. 검증을 통과하여 생성된 그래프 노드 후보는 그림 6과 같이 노드 k에서 하나의 상태로 정의되며, 다음과 같이 표현된다.

$\[ P_F^{\left(k\right)}=\{p_i^{\left(k\right)}\mid i=1,2,\dots ,N\} \]$

(7)

Fig. 6.

Formation node graph example.

식 (7)에서 $$ p_F^{\left(k\right)}$$는 노드 k에서 특정 패턴으로 구성된 포메이션 후보의 위치 집합을 의미한다. 각 후보 상태는 패턴 종류 F , 스케일 s^(k) , 그리고 자세 조합 (ψ^(k), θ^(k),ϕ^(k))에 의해 결정된다. 이러한 포메이션 후보들은 그래프 탐색 단계에서 전이비용 계산 및 시퀀스 결정의 입력으로 사용된다. 따라서, 탐색 효율이 향상된 간결한 포메이션 상태 그래프가 형성된다.

3. 포메이션 전이 비용

인접한 두 전역 경로 노드 간 포메이션 전환은 전이비용으로 평가되며, 이는 패턴을 유지하면서 목표 포메이션으로 자연스럽게 수렴하도록 유도한다. 전이비용 J는 인접 노드 포메이션 간의 상대 위치 변화, 목표 포메이션과의 거리, 패턴 전환 여부, 그리고 포메이션의 회전 변화를 함께 고려하여 다음과 같이 정의된다.

$\[ J=W_1{G}_1+W_2{G}_{goal }+W_3{\Delta }_{pattern }+W_4{\Delta }_{space } \]$

(8)

식 (8)에서 W₁, W₂, W₃, W₄는 각 항의 영향도를 조정하는 가중치 계수이다. G₁은 인접한 두 노드 간 비행로봇의 이동 거리를 최소화하기 위한 항이며, G_goal은 현재 포메이션이 목표 포메이션에 얼마나 근접해 있는지를 나타낸다.

Δ_pattern 은 인접 노드 간 패턴이 변경될 때 발생하는 전환 비용을 의미하고, Δ_space는 포메이션의 pitch 및 roll 변화량을 반영하여 공간 방향의 급격한 회전 변화를 억제한다. 식 (8)에서 G₁은 다음의 최소 매칭 문제로 계산된다.

$\[ G_1=\underset{\pi }{\min } \stackrel{N}{\sum _{i=1}} \Vert P_i^{\left(u\right)}-P_{\pi \left(i\right)}^{\left(v\right)}\Vert \]$

(9)

식 (9)에서 π는 이전 노드 u와 다음 노드 v간 구성 비행로봇 대응 관계를 나타내는 일대일 매칭으로, 각 비행로봇이 최소 이동 거리로 이전 노드의 각 비행로봇이 다음 노드의 대응 위치로 최소 이동 거리로 배치되도록 한다. 이 과정을 통해 전체 이동 경로의 연속성이 유지되며, 최적 매칭은 헝가리안 알고리즘(Hungarian Algorithm) [15]을 이용하여 계산된다. 이 알고리즘은 모든 구성 비행로봇 간 일대일 대응을 유지하면서 총 이동 거리를 최소화한다. 또한 식 (8)에서 G_goal을 다음과 같이 정의한다.

$\[ G_{goal}=\underset{\pi }{\min } \stackrel{N}{\sum _{i=1}} \Vert P_i^{\left(v\right)}-D_{\pi \left(i\right)}\Vert \]$

(10)

식 (10)에서 𝐷_𝜋(𝑖)는 목표 포메이션의 구성원 좌표를 의미한다. 이 항은 현재 포메이션이 목표 패턴에 얼마나 근접한지를 정량적으로 평가하며, 남은 구간에서의 목표 접근 정도를 예측 비용으로 반영한다. Δ_pattern은 빈번한 패턴 전환을 방지하기 위한 이진 항으로, 인접 노드 간 포메이션 패턴이 달라질 경우 1 , 동일할 경우 0으로 설정된다. Δ_space는 인접 노드 간 pitch 및 roll 변화량으로 정의되며, 공간 방향의 급격한 회전이나 포메이션의 회전 급변화를 억제한다. 이를 통해 탐색 과정에서 불필요한 패턴 전환이나 급격한 방향 변화가 억제되고, 인접 노드간 포메이션의 이동이 부드럽게 유지된다.

본 연구의 비용함수 𝐽는 이동 거리 항 𝐺₁ , 목표 패턴 정렬 항 𝐺_{𝑔𝑜𝑎𝑙} , 패턴 전환 항 Δ_{𝑝𝑎𝑡𝑡𝑒𝑟𝑛} , 그리고 공간 방향 변화 항 Δ_{𝑠𝑝𝑎𝑐𝑒} 로 구성되며, 각 항목은 서로 다른 물리적 단위(거리, 이진 값, 각도)를 가진다. 이러한 차이를 고려하여 항 간 공정한 비교를 보장하기 위해 모든 항을 0–1 범위로 정규화하여 사용하였다.

먼저 𝐺₁과 𝐺_{𝑔𝑜𝑎𝑙}은 포메이션 구성 비행 로봇이 인접 노드에서 이동할 수 있는 최대 거리 상한값 𝑑_max = 6.5 m로 나누어 정규화하였다. 𝑑_max는 전역 경로의 노드 간 간격(𝛿_𝑑 = 0.8 m )과 패턴A에서 발생 가능한 최대 반경(≈ 2.83 m )을 고려하여 산출하였다.

$\[ {\tilde{G}}_1=min(\frac{G_1}{{\mathrm{d}}_{max}},1.0), {\tilde{G}}_{goal }=min(\frac{G_{goal }}{{\mathrm{d}}_{max}},1.0) \]$

(11)

공간 방향 변화 항 Δ_{𝑠𝑝𝑎𝑐𝑒}는 pitch 및 roll 변화량의 크기를 이용하며, 각 회전 성분은 허용 가능한 최대 회전각 90° 을 기준으로 정규화하였다.

$\[ {\tilde{\Delta }}_{space }=min(\frac{\mid \Delta pitch \mid }{\pi /2},1.0)+min(\frac{\mid \Delta roll \mid }{\pi /2},1.0) \]$

(12)

Δ_{𝑝𝑎𝑡𝑡𝑒𝑟𝑛}은 이미 0 또는 1로 정의되므로 정규화는 적용하지 않았다. 이와 같은 정규화 과정을 통해 비용 항목들은 동일 스케일에서 비교 가능하며, 가중치 𝑊₁ ∼ 𝑊₄는 단위 차이에 영향을 받지 않고 상대적 중요도만 반영하도록 조정된다.

정규화된 비용 항을 기반으로 가중치 𝑊₁ –𝑊₄는 이동 거리 최소화, 목표 패턴 접근성, 회전 안정성, 패턴 전환 빈도 사이의 균형을 고려하여 설정하였다. 가중치 선정 시에는 이동 거리 최소화를 우선 목표로 두어 𝑊₁ > 𝑊₂ > 𝑊₃, 𝑊₄의 기본 원칙을 유지하였다. 이 원칙을 유지한 상태에서, 여러 가중치 조합에 대해 동일한 시나리오에서 실험을 수행하고, 패턴 전환 수, 최소 여유 거리, 탐색 시간을 성능 지표로 비교하였다.

표 1에 제시된 다섯 가지 가중치 조합 중 Case 4는 패턴 전환 수가 가장 적고 최소 여유 거리가 가장 크며 탐색 시간이 가장 짧아, 전반적인 안정성과 효율성 측면에서 가장 우수한 성능을 나타내었다. 이에 따라 본 연구에서는 (𝑊₁, 𝑊₂, 𝑊₃, 𝑊₄) = (1.0, 0.8, 0.3, 0.2)를 최종 가중치로 설정하였다.

Table 1.

Comparison of search performance by weight combination.

III. 시뮬레이션

본 연구에서는 제안된 3차원 명령 포메이션 생성 알고리즘의 성능을 검증하기 위해, 동일한 환경에서 기존 2차원 탐색 방법과 비교 실험을 수행하였다. 두 방법 모두 동일한 전역 경로와 장애물 구성을 사용하였으며, 복잡한 환경의 장애물 정보는 OctoMap [16]을 이용해 3차원 점유 격자 형태로 변환하였다. 시뮬레이션은 ROS Noetic [17] 환경에서 수행되었고, 명령 포메이션 시퀀스의 시각화는 3D Matplotlib을 사용하여 생성되었다. 각 노드에서 선택된 포메이션의 위치 · 자세 정보를 3차원 좌표계에 투영하여 그래프 탐색 결과를 확인하였다.

실험은 기존 방법[13]을 재현하여, 제안 방법과의 성능을 비교하기 위해 수행되었다. 기존 방법은 전역 경로 상에서 yaw 회전과 스케일 조합을 사전 생성하고, 2차원 평면에서 포메이션 전환 시퀀스를 탐색하는 구조를 따른다. 반면, 제안 방법은 3차원 회전과 스케일을 통합적으로 고려하여 공간 제약을 반영한 조건 기반 포메이션 후보를 생성한다. 두 방법은 동일한 환경 조건에서 그래프 생성시간, 탐색시간, 생성 노드 수, 평균 여유 거리를 기준으로 성능을 비교하였다.

시뮬레이션 환경은 그림 7과 같이 장애물의 분포와 통로 폭에 따라 세 구간으로 구성하였다. 구간 1은 3차원 장애물이 존재하는 영역으로, 기울기 변화에 따른 공간 배치 유연성과 안정성을 평가하였다. 구간 2는 문틈과 직각 복도로 이루어진 협소 구간으로, 포메이션 축소 및 패턴 전환 능력을 검증하였다. 구간 3은 복합적인 장애물 회피와 복도 통과가 동시에 요구되는 영역으로, 제안된 방법의 종합적 적응성을 평가하였다.

Fig. 7.

Map segmented into sections by obstacles.

표 2는 각 구간에서 기존 방법[13]과 제안 방법의 성능을 비교한 결과를 나타낸다. 그래프 생성시간은 모든 구간에서 단축되었으며, 구간 1은 12.083s에서 9.480s로 21.6% 감소, 구간 2는 8.173s에서 7.464s로 8.7% 감소, 구간 3은 10.991s에서 9.432s로 14.2% 감소하였다. 전체 그래프 생성시간은 31.247 s에서 26.376 s로 15.6% 단축되었다. 이는 제안 방법이 포메이션 후보 생성 과정에서 비효율적인 후보를 사전에 배제하여 그래프 규모를 축소했기 때문이다.

Table 2.

Performance comparison between the baseline and the proposed method.

그래프 탐색시간 또한 모든 구간에서 단축되었다. 구간 1은 0.117s에서 0.082s로 29.9%, 구간 2는 0.020s에서 0.015s로 25.0%, 구간 3은 0.019s에서 0.014s로 26.3% 감소하였다. 전체 탐색시간은 기존 0.156 s 대비 제안 0.111 s로 28.8% 단축되었다. 이러한 효율 향상은 탐색 공간을 단순 확장하지 않고, 유효 후보만을 대상으로 비용 함수를 계산하는 구조적 최적화의 결과이다. 표 2에 나타난 바와 같이, 전 구간에서 탐색 시간은 0.1 s 이하로 유지되었으며, 그래프 생성 시간을 포함한 전체 포메이션 시퀀스 생성은 수 초 이내에 완료되었다.

생성 노드 수는 구간 1에서 557개에서 392개로 29.6%, 구간 2에서 202개에서 152개로 24.7%, 구간 3에서 252개에서 221개로 12.3% 감소하였다. 특히 구간 1의 큰 감소폭은 3차원 회전과 스케일 조합을 통합적으로 고려함으로써 불필요한 평면 조합이 제거된 결과이다.

평균 여유 거리는 포메이션 내 각 비행로봇과 장애물 간의 최근접 거리에서 안전 거리를 제외한 여유 거리의 평균으로, 모든 구간에서 증가하였다. 구간 1은 1.02m에서 1.18m로 15.7%, 구간 2는 0.20m에서 0.28m로 40.0 %, 구간 3은 0.35m에서 0.41m로 17.1% 증가하였다. 이는 좁은 복도나 복합 구간에서도 포메이션이 충돌 위험을 최소화하며 여유 거리를 확보했음을 의미한다.

그림 8, 9, 10은 각각 구간 1, 2, 3에서 제안 방법을 적용하여 생성된 포메이션 시퀀스를 나타낸다. 각 구간의 시작 포메이션은 원, 종료 포메이션은 삼각형으로 표시하였으며, 다섯 대의 비행로봇은 서로 다른 색상으로 구분하였다. 시각화 결과, 모든 구간에서 포메이션의 위치와 자세 변화가 전역 경로의 진행 방향과 일관성을 유지하며 연속적으로 전개되었다. 이상의 시뮬레이션 결과를 종합하면 제안된 방법은 기존 방법 [13] 대비 생성과 탐색 전 과정에서 일관된 이점을 보이며 협소 공간에서 더 높은 계산 효율과 안전 여유를 동시에 달성했음을 확인하였다.

Fig. 8.

3D formation sequence in section 1.

Fig. 9.

3D formation sequence in section 2.

Fig. 10.

3D formation sequence in section 3.

IV. 결론

본 논문에서는 협소하고 복잡한 3차원 환경에서 다중 비행로봇의 포메이션 이동을 효율적으로 계획하기 위한 명령 포메이션 시퀀스 생성 알고리즘을 제안하였다. 제안된 방법은 포메이션의 기울기와 스케일 변화를 통합적으로 반영하고 조건 기반 후보 선별로 비효율 상태를 사전에 제거하여 그래프 규모와 탐색 복잡도를 낮췄다. 그 결과 생성과 탐색 단계의 지연이 줄고 포메이션 전개가 경로 진행 방향과 일관되게 유지되었으며 평균 여유 거리가 확보되어 공간 활용성이 향상되었다. 따라서 협소한 3차원 환경에서도 명령 포메이션 시퀀스를 안정적으로 산출하는 유효한 접근임을 확인하였다.

본 연구는 정적 환경에서 수행되었으며, 동적 장애물, 통신 지연, 비행체의 동역학 제약은 고려하지 않았다. 또한 본 연구의 포메이션 추종 명령은 position 기반으로 구성되어 있어 전역 경로 노드 간 간격이 큰 구간에서는 일부 이산화된 궤적이 시각적으로 나타날 수 있다. 향후 velocity 기반 혹은 smooth trajectory 기반 명령 생성 방식으로 확장한다면 이러한 현상을 완화하고 보다 연속적인 비행 경로를 구현할 수 있을 것으로 기대된다.

REFERENCES

• M. A. Kamel, X. Yu, and Y. Zhang, “Formation control and coordination of multiple unmanned ground vehicles in normal and faulty situations: A review,” Annual Reviews in Control, vol. 49, pp. 128–144, 2020. [https://doi.org/10.1016/j.arcontrol.2020.02.001]
• S.-W. Choi, S.-H. Lee, S.-B. Woo, T.-H. Kim, and D. Kim, “Space partitioning and path planning for mission area exploration using multiple UGVs,” Journal of Institute of Control, Robotics and Systems (in Korean), vol. 30, no. 3, pp. 197–205, Mar. 2024. [https://doi.org/10.5302/J.ICROS.2024.23.0178]
• S. Lee, W. Chung, M. Kim, S.-P. Lee, C.-H. Lee, S. Kim, and H. Son, “Path planning for search and surveillance of multiple UAVs,” Journal of Korea Robotics Society (in Korean), vol. 18, no. 1, pp. 1–9, 2023. [https://doi.org/10.7746/jkros.2023.18.1.001]
• D. Shin, J. Ryu, and C. Park, “A task allocation and path planning framework for fleet management based on MAPF,” Journal of Korea Robotics Society (in Korean), vol. 17, no. 4, pp. 309–318, 2022. [https://doi.org/10.7746/jkros.2022.17.4.407]
• C. Kim and H. Son, “Optimization of work area division for agricultural multi-robot systems,” Journal of Institute of Control, Robotics and Systems (in Korean)., vol. 30, no. 1, pp. 35–42, 2024.
• M. A. Kamel, X. Yu, and Y. Zhang, “Fault-tolerant formation control for multi-UAV systems,” Annual Reviews in Control, vol. 50, pp. 215–228, 2021.
• T. Hoang, H. Kim, and J. Park, “Angle-encoded particle swarm optimization for UAV formation path planning,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1721–1728, Oct. 2018. [https://doi.org/10.1109/IROS.2018.8593930]
• D. Roy, M. Maitra, and S. Bhattacharya, “Adaptive formation switching of a multi-robot system in an unknown occluded environment using BAT algorithm,” International Journal of Intelligent Robotics and Applications, vol. 4, no. 4, pp. 465–489, 2020. [https://doi.org/10.1007/s41315-020-00150-3]
• A. Wasik, J. N. Pereira, R. Ventura, P. U. Lima, and A. Martinoli, “Graph-based distributed control for adaptive multi-robot patrolling through local formation transformation,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1721–1728, Nov. 2016. [https://doi.org/10.1109/IROS.2016.7759276]
• J. N. Yasin, M.-H. Haghbayan, M. M. Yasin, and J. Plosila, “Swarm formation morphing for congestion-aware collision avoidance,” Heliyon, vol. 7, no. 8, 2021. [https://doi.org/10.1016/j.heliyon.2021.e07840]
• A. Wasik, J. N. Pereira, and R. Ventura, “Distributed formation control based on local graph interactions,” Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3164–3171, Nov. 2016.
• S.-C. Park and S.-M. Lee, “Distributed model predictive formation control of UGV swarm guaranteeing collision avoidance,” IEMEK J. Embedded Syst. Appl., vol. 17, no. 2, pp. 115–121, 2022.
• S.-M. Lee and J.-U. Lee, “Multi-robot formation planning in maze-like environments consisting of narrow passages using graph search,” IEEE Access, vol. 12, pp. 52345–52359, Nov. 2024. [https://doi.org/10.1109/ACCESS.2024.3497177]
• M. Guo and D. V. Dimarogonas, “Multi-agent plan reconfiguration under local LTL specifications,” The International Journal of Robotics Research, vol. 34, no. 2, pp. 218–235, 2015. [https://doi.org/10.1177/0278364914546174]
• H. W. Kuhn, “The Hungarian method for the assignment problem,” Naval Research Logistics Quarterly, vol. 2, no. 1–2, pp. 83–97, 1955. [https://doi.org/10.1002/nav.3800020109]
• A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard, “OctoMap: An efficient probabilistic 3D mapping framework based on octrees,” Autonomous Robots, vol. 34, no. 3, pp. 189–206, 2013. [https://doi.org/10.1007/s10514-012-9321-0]
• https://wiki.ros.org/noetic