A Real-Time System for Scheduling and Managing UAV Delivery in Urban Areas

논문 기술 요약: 도시 지역 UAV 배송을 위한 실시간 스케줄링 및 관리 시스템

1. 문제 정의 (Problem)

도시 물류 수요의 증가로 인해 무인 항공기 (UAV) 배송이 교통 체증 완화 및 물류 비용 절감의 핵심 솔루션으로 부상하고 있습니다. 그러나 UAV 배송 네트워크의 잠재력을 완전히 발휘하기 위해서는 효율적인 스웜 (군집) 스케줄링과 관리가 필수적입니다. 기존 연구는 주로 경로 최적화, 충돌 회피, 에너지 효율 등 알고리즘적 측면에 집중해 왔으나, 실제 환경 적용에는 다음과 같은 한계가 존재합니다:

• 이론과 실행의 괴리: 많은 스케줄링 알고리즘이 하위 실행 인프라 (Ground Execution Infrastructure) 와의 통합을 간과하거나, 비현실적인 단순화된 모델을 사용합니다.
• 실시간성 부족: 많은 알고리즘이 오프라인용 (Offline) 으로 설계되어 계산 시간이 길어 실시간 스케줄링 요구사항을 충족하지 못합니다.
• 상태 인식 부재: 스케줄링 계층이 하위 시스템의 정확한 상태 (예: UAV 의 실제 위치, 배터리 상태, 지상 작업자의 가용성) 를 인지하지 못해, 스케줄링 지시가 실행 명령으로 정확히 변환되지 않거나 오류가 발생할 수 있습니다.

이러한 문제를 해결하기 위해 **스케줄링 알고리즘과 실행 시스템 사이의 간극을 메우는 실시간 관리 시스템 (Middleware)**의 필요성이 대두되었습니다.

2. 방법론 (Methodology)

이 논문은 "공항 - 하역 스테이션 (Airport-Unloading Station)" 모델을 기반으로 한 실시간 스케줄링 및 관리 시스템을 제안합니다.

• 시스템 아키텍처 (Middleware):

  • 마스터 관리 노드 (Master Management Node): 상위 스케줄링 레이어와 하위 실행 레이어를 연결하는 핵심 노드입니다. AGV 와 UAV 의 상태 정보를 집계하여 스케줄러에 제공하고, 스케줄링 결과를 실행 노드에 배포합니다.
  • AGV 관리 노드 & UAV 관리 노드: 각각의 차량 (AGV, UAV) 을 독립적인 멀티스레드 및 유한 상태 머신 (FSM) 으로 관리합니다. 이는 고장 격리 (Fault Isolation), 실시간 응답성, 확장성을 보장합니다.
  • 유한 상태 머신 (FSM) 설계:
    • UAV FSM: 준비 (Ready), AGV 탑승 (On Car), 이륙 대기 (Waiting Go), 비행 중 (Flying Go/Back), 하역 대기 (Waiting Back) 등 6 가지 상태와 명령/조건을 정의하여 자율적인 임무 수행을 관리합니다.
    • AGV FSM: UAV 를 공항의 이륙/착륙 구역 (AW) 과 지상 작업 구역 (GW) 사이에서 운송하고, 화물 적재 및 배터리 교체 등을 보조하는 4 가지 상태 (기다림, 작업 중 등) 를 정의합니다.

• 스케줄링 전략 (Scheduling Schemes):
  지상 교통 (AGV) 과 공중 교통 (UAV) 을 조정하기 위해 두 가지 스케줄러를 도입했습니다.

  1. 지상 교통 스케줄러 (Ground Traffic Scheduler): AGV 의 이동 경로를 관리하며, 세 가지 시나리오를 지원합니다.
     • One-Cycle: 모든 AGV 가 단일 루프를 순환.
     • Two-Cycle: 두 개의 루프가 하나의 이륙 지점을 공유 (각 루프당 3 대의 AGV).
     • Three-Cycle: 세 개의 독립된 루프 (각 루프당 2 대의 AGV).
     • 이 설계는 조립 라인처럼 작동하여 UAV 의 대기 시간을 최소화하고 항공 - 지상 작업 간의 효율적인 이양을 보장합니다.
  2. 공중 교통 스케줄러 (Air Traffic Scheduler): UAV 의 이륙 및 귀환 승인, 경로 할당을 담당합니다.
     • 이륙 승인: 하역 스테이션 도착 시간 간격 ($t_{gap}$) 을 유지하여 충돌을 방지합니다.
     • 귀환 승인: UAV 가 착륙하기 전에 AGV 가 착륙 지점에 도착할 수 있는지 확인하여 안전성을 확보합니다.

3. 주요 기여 (Key Contributions)

1. 실시간 관리 시스템 설계: 도시 배송 요구 사항에 맞춘 스케줄링 관리 시스템을 설계하여, 고수준 알고리즘을 실제 실행 가능한 명령어로 변환하는 미들웨어 역할을 수행합니다.
2. 협업 스케줄링 솔루션 구현: AGV, UAV, 지상 작업자 간의 협력을 최적화하는 세 가지 스케줄링 방안 (One/Two/Three-Cycle) 을 구현하고 비교 분석했습니다.
3. 실증적 검증: 다양한 UAV 수와 스케줄링 전략에 대한 실험을 통해 시스템의 타당성과 상업적 적용 가능성을 입증했습니다.

4. 실험 결과 (Results)

• 실험 환경: Docker 기반의 모의 실험 플랫폼 (AGV 제어, UAV 제어, 시나리오, 스케줄링 모듈) 을 구축하여 Intel Core i7 CPU 환경에서 테스트했습니다.
• 성능 지표: 배송 건수, 점수 (시간 준수도에 따른 점수), AGV 및 지상 작업자의 바쁨 비율 (Busy Ratio) 을 측정했습니다.
• 주요 발견:
  • UAV 수 증가 효과: UAV 수가 증가할수록 배송 건수와 점수가 증가했으나, 효율성 향상에는 한계가 존재했습니다.
  • 최적의 스케줄링 방식: Two-Cycle 방식이 가장 높은 점수와 배송 효율을 보였습니다. 이는 지상 작업자의 활용도를 높이는 동시에 AGV 의 이동 거리를 불필요하게 늘리지 않는 균형 잡힌 구조 때문입니다.
  • 비효율적인 방식: Three-Cycle 방식은 AGV 가 이동하는 시간이过长하여 전체 효율이 낮았고, One-Cycle 방식은 대기 시간이 길어 AGV 활용도가 낮았습니다.
  • 자원 활용도: 지상 작업자의 바쁨 비율이 높을수록 배송 점수가 높게 나타났으며, 이는 화물 적재 효율이 전체 시스템 성능에 결정적임을 시사합니다.

5. 의의 및 결론 (Significance & Conclusion)

이 연구는 UAV 배송 시스템의 이론적 알고리즘과 실제 물리적 실행 사이의 간극을 성공적으로 메웠습니다. 제안된 시스템은 다음과 같은 의의를 가집니다:

• 실용성: 단순한 시뮬레이션을 넘어, 실제 도시 환경에서 발생할 수 있는 지상 - 공중 협업의 복잡성을 고려한 실용적인 솔루션을 제공합니다.
• 확장성: 모듈화된 아키텍처와 FSM 기반 제어를 통해 UAV 수의 증가나 새로운 차량 추가에 유연하게 대응할 수 있습니다.
• 상업적 가치: Meituan 등 실제 기업들의 UAV 배송 상용화를 위한 기술적 기반을 제공하며, 효율적인 자원 배분 (AGV, 지상 인력, UAV) 을 통해 물류 비용을 절감하고 배송 속도를 높이는 방안을 제시합니다.

결론적으로, 본 논문은 단순한 경로 최적화를 넘어 시스템 전체의 실시간 관리 및 협업 프로세스를 통합함으로써 도시 UAV 배송의 상용화를 위한 핵심 기술적 토대를 마련했습니다.