Landscape-Aware Bandit Hyper-Heuristics for Online Operator Selection in UAV Inspection Routing

기술 요약: UAV 검사 경로 최적화를 위한 지형 인식 밴딧 하이퍼-휴리스틱을 활용한 온라인 연산자 선택

1. 문제 정의

본 논문은 UAV 다지점 검사 경로 문제를 유클리드 외판원 문제 (TSP) 로 추상화하여 다룹니다. 이 맥락에서 UAV 는 제한된 비행 시간 내에 할당된 일련의 지점을 방문하고 기지로 복귀해야 합니다. 핵심 결정 변수는 이러한 지점들의 방문 순서이며, 고도 제어, 충돌 회피, 서비스 시간과 같은 하위 수준의 고려사항들은 다른 계획기에서 별도로 처리된다고 가정합니다.

도전 과제는 서로 다른 경로 지형 (예: 균일, 군집, 통로형, 격자형, 혼합 밀도) 과 탐색 과정의 서로 다른 단계가 서로 다른 최적화 전략을 요구한다는 점에 있습니다. 고전적인 휴리스틱은 종종 고정된 일정이나 무작위 연산자 선택에 의존하는데, 이는 개선이 더 이상 이루어지지 않는 연산자를 과도하게 사용하거나 현재 탐색 상태에 적합하지 않은 이동에 대한 평가를 낭비하는 등의 비효율성을 초래할 수 있습니다.

2. 방법론: LA-BHH

저자들은 오프라인 학습 없이 단일 최적화 실행 중 연산자 선택 정책을 학습하도록 설계된 경량 온라인 제어기인 LA-BHH(지형 인식 밴딧 하이퍼-휴리스틱) 를 제안합니다.

• 하이퍼-휴리스틱 프레임워크: LA-BHH 는 상위 수준에서 작동하며, 네 가지 저수준 연산자 (암) 로 구성된 포트폴리오 중에서 선택합니다:
  1. 2-opt: 엣지 교차를 제거하기 위해 경로 세그먼트를 반전시킵니다.
  2. Swap: 두 개의 검사 지점을 교환합니다.
  3. Relocate: 하나의 지점을 다른 위치로 이동시킵니다.
  4. Or-opt-2: 두 개의 지점 블록을 이동시킵니다.
• 맥락적 밴딧 제어기: 선택 메커니즘은 LinUCB(선형 상한 신뢰 구간) 알고리즘을 활용합니다.
  • 맥락 벡터 ($z_t$): 제어기는 다음을 포함하는 특징 벡터에 기반하여 결정을 내립니다:
    • 정적 지형 기술자: 정규화된 문제 크기, 평균 최단 이웃 거리, 분산, 좌표 이방성, 방사형 분산, 노드당 MST 가중치.
    • 동적 탐색 상태 특징: 예산 진행률, 초기 대비 현재/최적 경로 길이, 최근 개선 정도, 수용률, 정체 지표.
  • 학습 신호: 보상 ($r_t$) 은 선택된 연산자가 생성한 경로 길이의 클립된 상대적 개선량입니다. 이 보상은 선택된 암에 대한 릿지 회귀 통계량 ($A_a, b_a$) 을 업데이트하여 제어기가 실시간으로 신용 할당을 적응하도록 합니다.
• 정체 인식 복구: 특정 설계 기능은 탐색이 정체 (짧은 기간 동안 개선이 없음) 를 감지할 때 2-opt 이동으로의 선택을 편향시킵니다. 이는 새로운 이동 유형을 도입하지 않고 유클리드 복구에 대한 2-opt 의 알려진 유효성을 활용합니다.
• 수용 전략: 이 방법은 탐욕적 최선 개선 규칙을 사용합니다. 어닐링 스타일의 수용 방식은 제거 실험 (ablation) 으로 테스트되었으나, 강력한 최단 이웃 구조를 방해하여 이러한 특정 유클리드 인스턴스에서 성능을 저하시키는 것으로 밝혀졌습니다.

3. 주요 기여

• 경로를 위한 온라인 학습: 본 논문은 정적 인스턴스 특성과 동적 탐색 진행 상황 모두에 기반하여 연산자를 선택하도록 경량 온라인 제어기가 효과적으로 학습할 수 있음을 보여줌으로써, 대규모 오프라인 데이터셋이나 복잡한 신경 구조의 필요성을 제거합니다.
• 맥락적 신용 할당: 정적 지형 기술자와 온라인 탐색 상태 특징을 명시적으로 결합하여 연산자 선택을 안내함으로써, 이 맥락이 비맥락적 밴딧 선택 (UCB-HH) 이나 무작위 선택보다 우수함을 입증합니다.
• 정체 처리: 2-opt 복구 이동으로 제어기를 동적으로 편향시키는 정체 인식 게이트의 통합이 탐색 진행을 유지하는 데 중요한 구성 요소로 확인되었습니다.
• 제거 실험 분석: 연구는 특정 구성 요소 (맥락, 정적 특징, 동적 특징, 특정 연산자) 의 기여를 체계적으로 분리하여, 성능 향상이 2-opt 복구, 맥락적 신용 할당, 그리고 정체 인식 상태 사용 간의 상호작용에서 비롯됨을 명확히 합니다.

4. 실험 결과

이 방법은 다섯 가지 지형 계열 (균일, 군집, 통로, 격자-지터, 혼합 밀도) 과 세 가지 인스턴스 크기 (50, 100, 200 개 지점) 에 걸쳐 생성된 45 개의 유클리드 TSP 인스턴스에서 평가되었습니다.

• 성능 지표: LA-BHH 는 비교된 모든 방법 중 가장 우수한 평균 최종 갭(0.0223) 과 수렴 AUC(0.0389) 를 달성했습니다.
• 비교적 이득:
  • 비맥락적 UCB-HH 대비 최종 갭을 17.6% 감소시켰습니다.
  • Random-HH 대비 최종 갭을 22.6% 감소시켰습니다.
  • 최단 이웃 (NN) 구성 대비 최종 갭을 68.2% 감소시켰습니다.
• 견고성: LA-BHH 는 모든 지형 계열에서 고전적 베이스라인 (시뮬레이션 어닐링, 유전 알고리즘, 반복 로컬 서치 포함) 을 일관되게 능가하여 다양한 배치 시나리오에서 안정성을 입증했습니다.
• 연산자 사용: 분석 결과, 2-opt 가 (특히 정체 기간 동안) 지배적인 연산자였지만, 학습된 제어기는 2-opt 만으로는 해결할 수 없는 로컬 순서 오류를 수정하기 위해 swap, relocate, Or-opt-2 를 효과적으로 활용했습니다.

5. 중요성과 주장

본 논문은 LA-BHH 를 경로 최적화 분야에서 학습 지원 알고리즘 설계 (LEAD) 에 대한 실용적인 사례 연구로 위치시킵니다. 그 중요성은 몇 가지 소박하지만 실용적인 주장을 중심으로 제시됩니다:

• 해석 가능성과 효율성: 대규모 오프라인 모델과 달리 LA-BHH 는 단일 실행 중 학습하는 경량이고 검사 가능한 제어기이므로, 소수의 관련 인스턴스만 사용 가능한 시나리오에 적합합니다.
• 보조적 역할: 저자들은 LA-BHH 가 최첨단 TSP 솔버 (예: LKH) 를 대체하기 위한 것이 아님을 명시적으로 밝힙니다. 대신, 고정된 예산 하에서 적용할 재사용 가능한 탐색 연산자를 어떤 것으로 할지 결정하는 경로 순서화 계층으로 기능합니다.
• 확장성: 이 방법은 계산적으로 효율적 (CPU 전용, $O(Tn)$ 복잡도) 이며 50 에서 200 개 지점까지 잘 확장되어, 고전적 로컬 서치 베이스라인이 덜 신뢰할 수 있게 되는 영역에서도 경쟁력을 유지합니다.
• 미래 적용 가능성: 저자들은 이 프레임워크가 유클리드 거리를 통과성 그래프상의 최단 경로 거리로 대체하고 하위 수준 계획기를 통해 장애물을 처리함으로써 실제 UAV 검사로 확장될 수 있다고 제안하지만, 현재 실험은 현장 수집 데이터 대신 통제된 생성 인스턴스에 의존한다고 지적합니다.