Joint Cluster Head Selection and Trajectory Planning in UAV-Aided IoT Networks by Reinforcement Learning with Sequential Model
원문 초록
Employing unmanned aerial vehicles (UAVs) has attracted growing interests and emerged as the state-of-the-art technology for data collection in Internet-of-Things (IoT) networks. In this paper, with the objective of minimizing the total energy consumption of the UAV-IoT system, we formulate the problem of jointly designing the UAV's trajectory and selecting cluster heads in the IoT network as a constrained combinatorial optimization problem which is classified as NP-hard and challenging to solve. We propose a novel deep reinforcement learning (DRL) with a sequential model strategy that can effectively learn the policy represented by a sequence-to-sequence neural network for the UAV's trajectory design in an unsupervised manner. Through extensive simulations, the obtained results show that the proposed DRL method can find the UAV's trajectory that requires much less energy consumption when compared to other baseline algorithms and achieves close-to-optimal performance. In addition, simulation results show that the trained model by our proposed DRL algorithm has an excellent generalization ability to larger problem sizes without the need to retrain the model.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝
Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling
잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.
학습과 탐색을 통한 조합 최적화에서 인간형 해법 이해
Understanding Human-like Solutions in Combinatorial Optimization via Learning and Search
인간은 고급 컴퓨터 알고리즘에게도 계산적으로 어려운 조합 최적화 문제에 대해 종종 좋은 해를 찾는다. 유클리드 여행 판매원 문제(TSP)에서 사람들은 시간과 계산에 심각한 제약이 있음에도 불구하고 거의 최적인 경로(tour)를 빠르게 생성한다. 경로를 인간형으로 만드는 요인은 무엇이며, 이러한 해를 어떻게 학습할 수 있을까? 본 연구에서는 유클리드 TSP에서 인간의 수행을 대규모 행동 및 계산 조사를 통해 이러한 질문에 답한다. 우리는 TSP 인스턴스의 넓은 공간을 샘플링하고, 인간의 해를 수집했으며, 유효한 경로에 대한 확률 분포를 정의하는 어텐션 기반 포인팅 메커니즘을 갖춘 순환 신경망인 Pointer Networks에 기반한 신경 정책과 이를 비교했다. 우리는 강화학습(RL), 최적 경로로부터의 지도학습, 인간 경로로부터의 지도학습, 그리고 최적 경로 지도학습 사전학습 후 RL 미세조정을 포함한 여러 목적 함수로 이러한 네트워크를 학습시켰다. 인간의 경로는 최적 경로와 동일하지는 않았지만, 거의 최적인 기하학적 분지(basin)를 차지했다: 최적 해와 많은 구조적 특성을 공유하면서도 체계적인 인간 특유의 편차를 유지했다. 인간 경로에 대한 최상의 설명은 최적 경로의 직접적 모방이 아니라, 최적 경로로 사전학습하고 RL로 미세조정한 뒤 $\text{Best-of-}N$ 샘플링을 통해 디코딩한 모델이었다. 이러한 결과는 인간형 해가 구조화된 지도학습, RL, 테스트 시점 탐색의 결합으로부터 창발할 수 있음을 시사하며, 많은 현대 인공지능 시스템의 기반이 되는 계산 원리와 공명한다.
심층 강화학습을 활용한 라스트마일 픽업 통합 주문 배차 및 경로 최적화
Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning
최근 몇 년간 라스트마일 픽업 운영의 복잡성이 증가하면서 물류 플랫폼에서 빠르고 정확한 의사결정에 대한 필요성이 커졌다. 이 과제는 근본적으로 두 가지 핵심적이고 긴밀히 결합된 의사결정 과정, 즉 주문 배차와 경로 최적화에 의해 촉발된다. 이들을 개별적으로 해결하면 상호 의존성을 간과하게 되며, 완전한 end-to-end 학습은 희소 보상(sparse reward)으로 인해 대규모이고 가변적인 규모의 인스턴스에서 불안정하고 비용이 많이 든다. 이 문제를 해결하기 위해, 학습된 경로 오라클(routing oracle)과 실시간 배차 휴리스틱을 결합하는 통합 최적화 프레임워크를 제안한다. 경로 최적화 하위 문제에 대해서는 Look-Ahead Courier-Personalized 디코더를 갖춘 Dynamic-Residual Graph Attention Network 인코더를 개발한다. 배차 하위 문제에 대해서는 경로 오라클이 지도하는 국소 탐색(local search) 기반 배차 휴리스틱을 개발하며, 오라클은 실시간 확장성을 유지하면서 후보 배송 기사를 선택하기 위한 근최적 해를 제공한다. Cainiao Logistics의 실제 데이터셋을 활용한 광범위한 실험을 통해 오프라인 평가와 온라인 롤링 호라이즌(rolling-horizon) 시뮬레이션을 포함하여 접근법의 성능을 검증했다. 실험 결과, 제안 방법은 해 품질과 해결 시간 측면에서 다른 벤치마크를 능가하며, 실시간 대규모 라스트마일 픽업 문제 해결에 물류 기업을 효과적으로 지원할 수 있음을 보여준다.
PPVC 모듈 공장의 유연 작업장 스케줄링을 위한 시간 지연 인식 심층 강화학습
Time-Lag-Aware Deep Reinforcement Learning for Flexible Job-Shop Scheduling in PPVC Module Factories
조립식 완성형 체적 건설(PPVC, Prefabricated Prefinished Volumetric Construction)은 대부분의 건축 작업을 모듈 공장으로 이전하며, 해당 공장의 생산 현장은 유연 작업장(flexible job shop) 형태로 운영된다. 주요한 복잡성이 결정적으로 작용하는데, 콘크리트 양생, 방수 침수 시험, 도장 건조로 인해 발생하는 장시간의 작업 후 시간 지연이 그것이다. 이 기간 동안 모듈은 대기 상태에 묶여 있지만 작업 스테이션은 유휴 상태를 유지한다. 공식 국가 조립식 건설 지침서에 기반한 벤치마크 인스턴스에서, 이러한 지연은 최적 기준 최대완료시간(makespan)조차 평균 약 67% 증가시키며, 의사결정 시점에 이를 무시하고 사후 실행 가능성으로 복구하는 방식은 모든 디스패칭 규칙(dispatching rule)보다 성능이 낮다. 우리는 최첨단 이중 어텐션(dual-attention) 심층 강화학습 솔버를 세 가지 최소 침습적이고 개별적으로 절제(ablation) 가능한 확장을 통해 적응시켰다: 허용 가능한 보상 경계를 갖는 시간 지연 인식 동역학, 두 개의 예측적 지연 특징 채널, 그리고 활성 마스킹된 작업 및 스테이션 유형 임베딩. 모든 확장을 비활성화하면 구현이 원래 솔버를 정확히 재현하므로, 모든 성능 향상은 해당 적응에 귀인된다. 우리는 지침서 기반의 공개 벤치마크 생성기를 공개한다. 보류 인스턴스에서 학습된 정책은 솔버 없이 동작하는 스케줄러 중 가장 강력하며, 제약 프로그래밍(constraint programming) 기준 대비 약 4% 이내의 성능을 달성하고 모든 디스패칭 규칙과 유전 알고리즘 메타휴리스틱을 능가한다. 그 우위는 용량 경합 상황에서 더욱 두드러지며, 크기가 혼합된 단일 정책이 학습된 공장 규모 범위 전체에서 이 우위를 유지한다. 이 방법은 루프 내에 솔버, 모델, 또는 라이선스가 필요 없으며 중단 발생 후 수 초 내에 재계획이 가능하다. 정밀 솔버를 배포할 수 있는 경우 해당 솔버가 품질의 상한선으로 남으며, 우리는 이 경계를 명시적으로 제시한다.
MPFlow: 심층 그래프 강화학습으로 라이트닝 네트워크의 예산 제약 최대 유량 최적화 학습
MPFlow: Learning Budgeted Max-Flow Optimization on the Lightning Network with Deep Graph Reinforcement Learning
본 연구는 비트코인 라이트닝 네트워크(LN)에서의 유동성 배치 문제를 다룬다: 고정된 예산이 주어졌을 때, 라우팅 용량을 최대화하기 위해 노드가 어떤 채널을 개설해야 하는가? 우리는 이를 그래프 상의 예산 제약 조합 최적화 문제로 정식화하여, 라우팅 용량의 이론적 척도인 $s$--$t$ 최대 유량(max-flow)을 최대화하는 $k$개의 엣지 추가를 선택하고, 이를 그래프 강화학습으로 해결한다. 우리의 경량 에이전트는 메시지 패싱 정책 네트워크와 근위 정책 최적화(PPO, Proximal Policy Optimization), 그리고 액션 마스킹을 결합하며, 허브 제외 커리큘럼 하에서 학습된다: 네트워크의 상위 허브를 학습 서브그래프에서 제거함으로써, 정책이 허브 연결이 아닌 용량 인식 배치를 학습하도록 유도한다. 실제 라이트닝 네트워크 스냅샷에 대한 광범위한 실험에서, 본 방법은 여러 시드와 미관측 그래프에 걸쳐 최대 유량 목표에서 강력한 휴리스틱 기준선을 일관되게 능가한다. 해당 에이전트는 피어 추천을 위해 프로덕션 환경에 배포되어 4,640건의 채널 개설 결정을 실행하였으며, 30개의 관리 노드에 걸쳐 누적 1,600만 달러 이상에 해당하는 267.3 BTC를 배분하였다.
Deep RL-based Trajectory Planning for AoI Minimization in UAV-assisted IoT
토론
이 논문과 연결된 포럼 글이 아직 없습니다.