⚡ electrical engineering

Obstacle-aware multi-UAV scheduling for plant-protection operations using an enhanced walrus optimizer

본 논문은 무인 항공기(UAV)의 식물 보호 작업을 위한 작업 할당과 방문 순서를 공동으로 최적화하기 위해 무작위 차분 변이, 렌즈 이미지 반대 학습, 그리고 이산 근방 탐색을 통합한 개선된 바다코끼리 최적화 알고리즘(CRWO)을 제안하며, 이를 통해 함대 작업 부하의 균형을 효과적으로 맞추고 지속 시간 제약 조건 하에서 장애물 인지 경로 타당성을 보장한다.

원저자: zhe sun, anchan liao, yunrui bi, zhixin sun

게시일 2026-09-02

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: zhe sun, anchan liao, yunrui bi, zhixin sun

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

현대적인 과수원의 고요한 줄 사이로, 새로운 종류의 일꾼이 하늘로 날아올랐습니다. 바로 무인 항공기, 즉 드론입니다. 과거의 크고 덜컹거리는 트랙터와 달리, 이 기계들은 나무 사이를 누빌 수 있을 만큼 민첩하며, 주의가 필요한 병든 잎이나 영양분이 부족한 가지만을 정밀하게 겨냥할 수 있습니다. 이러한 전면적인 살포에서 표적형 관리로의 전환은 화학 물질을 절약하고 환경을 보호할 것을 약속합니다. 하지만 단 한 대의 드론만으로는 전체 작업을 수행할 수 없습니다. 배터리는 소모되고, 액체 농약을 담는 탱크는 금방 채워집니다. 넓은 밭을 보호하기 위해서는 드론 함대가 함께 협력하여, 번갈아 가며 비행하여 특정 지점에 살포하고, 중앙 기지로 돌아와 다시 채운 뒤 다시 비행해야 합니다. 문제는 어떤 드론이 어느 나무로 갈지, 어떤 순서로 갈지, 그리고 각 드론이 몇 번의 왕복을 할지를 결정하는 데 있습니다. 만약 계획이 부실하다면, 어떤 드론은 지쳐버리고 다른 드론은 놀게 되거나, 더 나아가 드론이 지도상으로는 짧아 보이지만 실제로는 나무에 막혀 있거나 금지 구역인 경로로 보내져 충돌하거나 귀중한 에너지를 낭비하게 될 수도 있습니다.

난징 정보통신대학교와 난징 이공대학교의 연구진은 이러한 드론 함대를 조율하는 새로운 방법을 개발함으로써 이 복잡한 스케줄링 문제를 해결했습니다. 그들은 단순히 나무 사이의 직선거리를 보는 것이 아니라, 나뭇가지, 건물, 제한 구역과 같은 장애물을 피하기 위해 드론이 실제로 비행해야 하는 안전한 경로를 계산하는 시스템을 만들었습니다. 최적의 드로 함대 일정을 찾기 위해, 그들은 바다코끼리의 행동에서 영감을 얻은 새로운 컴퓨터 알고리즘을 설계했습니다. 야생에서 바다코끼리는 새로운 먹이 활동지를 탐색하는 필요성과 무리 근처에 머무는 안전함 사이의 균형을 맞추며 집단으로 이동합니다. 연구진은 이러한 사회적 행동을 수학적 규칙으로 변환하여, 컴퓨터가 수백만 개의 가능한 비행 계획을 검색하여 모든 드론이 균등하고 안전하게 작동할 수 있는 계획을 찾도록 도왔습니다.

연구팀은 자신들이 '강화된 바다코끼리 최적화 알고리즘(enhanced walrus optimizer)'이라 부르는 이 새로운 알고리-즘을 유사한 문제에 사용되는 여러 기존 방식과 비교 테스트했습니다. 그들은 기복이 있는 지형, 다양한 높이의 나무, 그리고 드론이 들어갈 수 없는 비행 금지 구역을 포함한 현실적인 과수원 환경을 시뮬레이션했습니다. 이러한 시뮬레이션에서 새로운 알고리즘은 다른 방식들을 지속적으로 능가했습니다. 이 알고리즘은 함대가 비행해야 하는 총 거리를 작지만 유의미한 수준으로 줄였을 뿐만 아니라, 가장 큰 성과는 작업량의 균형을 맞춘 데 있었습니다. 최상의 결과에서, 가장 바쁜 드론과 가장 한가한 드론 사이의 비행 거리 차이는 차순위 방식과 비교했을 때 거의 절반 가까이 줄어들었습니다. 이는 실제 상황에서 드론들이 대략 비슷한 시기에 마모될 것임을 의미하며, 지친 기계를 교체하지 않고도 함대가 더 오래 운영될 수 있음을 뜻합니다.

이 성공의 핵심적인 부분은 연구진이 과수원의 현실을 어떻게 다루었느냐에 있었습니다. 많은 계획 시스템은 드론이 한 나무에서 다음 나무로 직선으로 비행할 수 있다고 가정합니다. 연구진은 이러한 가정이 위험하다는 것을 보여주었습니다. 장애물을 돌아가기 위해 필요한 실제 우회 경로를 매핑하는 검증된 경로 탐색 기술을 사용함으로써, 그들은 알고리즘이 생성한 일정이 물리적으로 비행 가능한 경로임을 보장했습니다. 또한 그들은 3차원 요소를 계획에 추가하여, 드론이 지면과 나무 캐노피 위로 안전한 높이를 유지하고, 항공기에 위험할 수 있는 급격한 상승이나 하강을 하지 않도록 했습니다. 시스템에 의해 생성된 모든 비행 경로는 드론의 배터리 제한 및 안전 규칙 내에 있는지 확인되었습니다.

이 연구는 나무와 장애물이 움직이지 않는 정적인 환경에서 이 방식이 잘 작동함을 확인해 줍니다. 연구진은 이 방법이 특히 한 대의 드론이 과도하게 업무를 수행하고 다른 드론은 쉬게 되는 현상, 즉 전체 작업을 늦출 수 있는 흔한 문제를 방지하는 데 탁-월하다는 것을 발견했습니다. 이 시스템은 아직 움직이는 장애물이나 변화하는 날씨를 처리하지 못하며 모든 드론이 동일하다고 가정하지만, 자동화된 농업의 미래를 위한 견고한 토대를 제공합니다. 과수원을 평면 지도가 아닌 복잡한 3차원 공간으로 취급하고, 함대 관리를 위해 자연에서 영감을 받은 스마트한 알고리즘을 사용함으로써, 연구진은 이 로봇 일꾼들을 안전하고 효율적이며 균형 있게 유지할 수 있는 실질적인 방법을 제시했습니다. 그 결과, 이 스케줄링 방식은 혼란스러운 비행의 조합을 조율되고 신뢰할 수 있는 운영 체제로 바꾸어 놓았으며, 기계에 과부하를 주지 않으면서도 과수원을 보호할 수 있도록 보장합니다.

기술 요약: 향상된 월러스 최적화 알고리즘을 이용한 장애물 인지형 다중 UAV 식물 보호 작업 스케줄링

문제 정의
본 논문은 복잡한 지형과 장애물이 존재하는 과수원 환경에서 협력형 식물 보호 무인 항공기(UAV)의 스케줄링 문제를 다룬다. 기존의 경로 계획(coverage path planning)과 달리, 본 연구는 이산적인 질병 발생 구역 또는 영양 결핍 지점을 대상으로 하는 **표적 처리(targeted treatment)**에 초점을 맞춘다. 핵심 문제는 다음과 같은 제약 조건이 있는 단일 기지, 다중 UAV, 다회 출격(multi-sortie) 스케줄링 과업이다:

지속 시간 및 페이로드: 배터리 가동 범위와 농약 적재 용량의 제한으로 인해 중앙 기지로의 반복적인 귀환이 필요함.
장애물 회피: 나무, 건물, 비행 금지 구역의 존재로 인해 유클리드(직선) 거리가 경로 계획에 부적합함.
작업 부하 균형: 특정 UAV에 과부하가 걸리는 것을 방지하기 위해 동질적인 함대(fleet) 간에 작업을 균등하게 분배해야 함.
3D 실행 가능성: 지형 이격 거리, 상승각 제한, 캐노피 상단의 특정 작업 고도를 준수하는 실행 가능한 경로를 생성해야 함.

기존 방법들은 직선 거리를 기준으로 스케줄을 평가하는데, 이는 장애물이 도입될 경우 실행 불가능하거나 비효율적인 경로를 초래할 수 있다. 또한, 이러한 2.5차원 제약 조건 하에서 작업 할당, 방문 순서, 경로 실현을 동시에 최적화하는 연구는 드물다.

방법론
저자들은 결정론적 경로 실현 계층과 메타휴리스틱 스케줄링 최적화 계층을 결리한 2단계 프레임워크를 제안한다.

스케줄링 모델:
- 목적 함수: 총 이동 거리, 최대 누적 UAV별 거리(makespan), 그리고 UAV 간 경로 길이의 표준 편차(작업 부하 균형)를 최소화하는 다중 목적 함수를 사용한다.
- 에지 비용(Edge Costs): 유클리드 거리 대신, 정적 점유 그래프(static occupancy graph) 상의 A 탐색*을 통해 에지 비용( $c_{ij}$ )을 도출한다. 이를 통해 스케줄링 알고리즘이 장애물 및 비행 금지 구역을 우회하는 수평적 우회 경로를 고려하도록 보장한다.
- 제약 조건: 페이로드 제한, 최대 출격 길이, 단일 기지 귀환 제약을 강제한다. 디코더는 용량 또는 범위 제한에 도달할 때까지 작업을 패킹하여 출격을 구성한다.
경로 실현 (2.5차원):
- 수평 방향: A* 알고리즘이 스케줄에 기반하여 작업 간 충돌 없는 경로를 재구성한다.
- 수직 방향: 2.5D 고도 모델이 고도 프로파일을 할당한다. UAV는 지형으로부터 일정 순항 고도( $H_c$ )를 유지하며, 작업 지점의 나무 캐노피 상단에서 최소 작업 고도( $H_{min}$ )까지 부드럽게 하강하고, 최대 상승각( $20^\circ$ )을 준수한다.
- 실행 가능성 검사: 실현된 3D 공간 거리는 스케줄링 이후에 계산되며, UAV의 지속 시간 한계와 대조하여 검증된다.
향상된 월러스 최적화 알고리즘 (CRWO):
저자들은 표준 월러스 최적화(WO)를 세 가지 특정 전략을 통해 향상시켜 NP-난해(NP-hard) 조합 스케줄링 문제를 해결한다:
- 무작위 차분 변이(Random Differential Mutation): 역사적 최적해와 무작위 개체 간의 차이를 사용하여 섭동(perturbation)을 유도함으로써 탐색(exploration)과 이용(exploitation)의 균형을 맞춘다.
- 렌즈 이미징 반대 학습(Lens-Imaging Opposition-Based Learning): 탐색 공간 전체에 대해 대칭적인 후보 해를 생성하여 지역 최적해(local optima) 탈출을 돕는다.
- 이산 근방 탐색(Discrete Neighbourhood Search): 엘리트 해에 적용되어 작업 재할당 및 방문 우선순위를 정교화한다.
- 인코딩: 작업의 UAV 할당과 방문 우선순위를 모두 인코딩하는 이중 랜덤 키(dual-random-key) 표현법을 사용하여, 연속 최적화 연산자가 이산 문제를 해결할 수 있도록 한다.

주요 기여

장애물 인지형 정식화: 에지 비용을 유클리드 거리가 아닌 A*를 통해 사전 계산하는 스케줄링 모델을 정식화하여, 최적화 목표가 실행 가능한 경로 비용과 일치하도록 보장하였다.
CRWO 알고리즘: 고차원, 제약 조건이 있는 다중 UAV 스케줄링에 특화된 향상된 메타휴리스틱(CRWO)을 개발하였으며, 표준 WO, PSO, GWO 등을 능가하는 성능을 입증하였다.
2.5D 실현 프레임워크: 2D 스케줄링 탐색과 3D 경로 실현을 분리하는 순차적 접근 방으로, 전체 3D 역학을 최적화 과정에 포함시켜 복잡하게 만들지 않으면서도 지형 이격 및 상승각 제약을 만족하는 경로를 생성한다.
포괄적 평가: 저, 중, 고 장애물 밀도 시나리오에서 8개의 알고리즘을 대상으로 엄격한 벤치마킹을 수행하였으며, 특정 CRWO 구성 요소의 기여도를 격리하기 위한 절제 연구(ablation studies)를 포함하였다.

실험 결과
실험은 50개의 작업과 6대의 UAV가 있는 800m × 800m 규모의 과수원 맵에서 수행되었다.

베이스라인 대비 성능: 중간 장애물 시나리오에서 CRWO는 가장 강력한 베이스라인인 PSO보다 평균 목적 함수 값을 3.71%, 최대 누적 UAV별 공간 거리를 3.70% 감소시켰으며, UAV 간 경로 길이의 표준 편차를 47.62% 줄였다.
작업 부하 균형: CRWO는 모든 장애물 밀도에서 일관되게 가장 낮은 작업 변동성(표준 편차)을 달로, 우수한 함대 활용 능력을 보여주었다.
실행 가능성: 실현된 모든 출격은 지속 시간, 장애물 회피, 지형 이격(최소 5.52m), 상승각( $\le 20^\circ$ ) 제약을 모두 만족하였다.
A vs. 유클리드:* A* 에지 비용을 사용하는 것이 유클리드 스케줄링에 비해 총 누적 거리를 크게 줄이지는 못했으나, 작업 부하 균형 측면에서는 유의미한 개선을 보였다(쌍을 이룬 실행에서 경로 길이 표준 편차를 50.43m에서 23.11m로 감소).
절제 연구(Ablation): 차분 변이, 반대 학습, 이산 근방 탐색의 결합이 최종 성능을 달성하는 데 필수적임을 확인하였다. 이 중 하나라도 제거하면 결과가 저하되었다.

의의 및 주장
본 논문은 CRWO가 장애물 회피와 함대 균형이 중요한 정적, 단일 기지 식물 보호 작전에서 실용적인 스케줄링 방법을 제공한다고 주장한다. 저자들은 이 방법이 단순한 최단 경로 알고리즘이라기보다 "균형 잡힌 스케줄러"임을 강조한다. 즉, 이 방법의 주요 가치는 작업량을 균등하게 분배하고, 복잡한 3D 결합 없이도 안전 제약 조건을 준수하도록 보장하는 데 있다.

저자들은 현재 프레임워크가 정적 지도, 결정론적 수요, 동질적 함대로 제한된다는 점을 인정하며 신중한 태도를 유지한다. 또한, 이 방법이 전역 최적해를 보장하지는 않으며, 동적 재할당, 이종 함대, 비행 조건의 불확실성을 다루기 위해서는 향후 연구가 필요하다고 명시하였다. 결론적으로, 총 이동 거리의 이득은 미미할 수 있으나, 작업 부하 균형과 안전 준수 측면에서의 상당한 개선은 CRWO가 표적 과수원 보호를 위한 유효한 솔루션임을 입증한다.

유사한 논문