arXiv:2203.15030

Solving Disjunctive Temporal Networks with Uncertainty under Restricted Time-Based Controllability using Tree Search and Graph Neural Networks

Kevin Osanlou, Jeremy Frank, Andrei Bursuc, Tristan Cazenave, Eric Jacopin, Christophe Guettier, J. Benton

제출 2022-03-28

원문 초록

Planning under uncertainty is an area of interest in artificial intelligence. We present a novel approach based on tree search and graph machine learning for the scheduling problem known as Disjunctive Temporal Networks with Uncertainty (DTNU). Dynamic Controllability (DC) of DTNUs seeks a reactive scheduling strategy to satisfy temporal constraints in response to uncontrollable action durations. We introduce new semantics for reactive scheduling: Time-based Dynamic Controllability (TDC) and a restricted subset of TDC, R-TDC. We design a tree search algorithm to determine whether or not a DTNU is R-TDC. Moreover, we leverage a graph neural network as a heuristic for tree search guidance. Finally, we conduct experiments on a known benchmark on which we show R-TDC to retain significant completeness with regard to DC, while being faster to prove. This results in the tree search processing fifty percent more DTNU problems in R-TDC than the state-of-the-art DC solver does in DC with the same time budget. We also observe that graph neural network search guidance leads to substantial performance gains on benchmarks of more complex DTNUs, with up to eleven times more problems solved than the baseline tree search.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2610.15730v1cs.LG공통 태그 Scheduling, Graph Neural Network

시간적 그래프 신경망을 위한 의존성 인식 다중 GPU 학습 프레임워크

A Dependency-Aware Multi-GPU Training Framework for Temporal Graph Neural Networks

시간적 그래프 신경망(TGNN)은 많은 동적 그래프 학습 작업에서 우수한 성능을 달성한다. 이러한 모델은 노드 상태 벡터(즉, 메모리)를 사용하여 그래프 변화(즉, 이벤트)를 포착하고 기록한 뒤, 이 메모리를 활용하여 예측을 돕는다. 그러나 이러한 메모리 중심 설계는 다중 GPU 학습을 어렵게 만드는데, 이는 이후 이벤트에 대한 예측이 종종 이전 이벤트의 메모리 업데이트에 의존하기 때문이다. 모델 품질을 유지하기 위해 기존의 다중 GPU TGNN 학습 기법들은 모든 이벤트 의존성을 엄격하게 보존하는데, 이는 병렬성을 제한하고 비용이 큰 GPU 간 메모리 동기화를 야기한다. 본 연구에서는 이러한 의존성 중 다수를 학습 품질을 저해하지 않으면서도 더 유연하게 처리할 수 있다는 점을 관찰하였다. 구체적으로, (a) TGNN 학습의 의존성은 시간 및 그래프 토폴로지 측면에서 높은 지역성(locality)을 가지며, (b) 큰 배치 내에서 놓치는 단거리 의존성은 대개 저비용으로 복구할 수 있고, (c) 많은 메모리 업데이트는 즉시 필요하지 않다. 이러한 관찰을 바탕으로, 우리는 세 가지 기법을 통해 다중 GPU TGNN 학습을 가속화하는 DepBloom을 제안한다: (1) 불필요한 GPU 간 동기화를 줄이고 병렬성을 향상시키는 시간적으로 제한된 공간 분할(temporally bounded spatial partitioning); (2) 확대된 배치 내에서 놓친 단거리 시간적 의존성을 복구하는 배치 내 메모리 보정(intra-batch memory refinement); (3) 다중 GPU 파이프라인 실행 중 긴급한 메모리 업데이트를 우선 처리하고 비핵심 작업을 지연시키는 critical-path 최적화(critical-path optimization). 대표적인 모델들과 다양한 데이터셋에 대한 실험 결과, DepBloom은 최신 기법(state-of-the-art methods) 대비 평균 2.84배, 최대 5.16배의 속도 향상을 달성하면서도 동등하거나 더 나은 모델 정확도를 유지함을 보여준다.

arXiv:2609.28085v1cs.LG공통 태그 Scheduling, Graph Neural Network

잡 샵 스케줄링을 위한 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시간 절약했다.

arXiv:2607.22356v1cs.LG공통 태그 Scheduling, Graph Neural Network

심층 강화학습을 활용한 라스트마일 픽업 통합 주문 배차 및 경로 최적화

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) 시뮬레이션을 포함하여 접근법의 성능을 검증했다. 실험 결과, 제안 방법은 해 품질과 해결 시간 측면에서 다른 벤치마크를 능가하며, 실시간 대규모 라스트마일 픽업 문제 해결에 물류 기업을 효과적으로 지원할 수 있음을 보여준다.

arXiv:2607.19985v1cs.AI공통 태그 Scheduling, Graph Neural Network

메모리 기반 조율: 동적 제조 환경에서 다중 에이전트 적응을 위한 그래프 구조 경험 재사용

Coordinating from Memory: Graph-Structured Experience Reuse for Multi-Agent Adaptation in Dynamic Manufacturing

동적 제조 환경에서는 기계 고장, 긴급 작업 도착, 처리 시간 변동과 같은 빈번한 운영 교란 하에서 다중 에이전트 시스템이 효과적으로 조율해야 한다. 기존 다중 에이전트 강화학습 접근법은 각 교란 에피소드를 독립적으로 처리하여, 향후 적응을 가속할 수 있는 귀중한 조율 경험을 버린다. 본 논문에서는 동적 제조 환경에서의 다중 에이전트 조율을 위한 그래프 구조 경험 메모리(GSEM) 프레임워크를 제안한다. 이 프레임워크는 작업 종속성, 기계 상태, 에이전트 간 협업 패턴을 포착하는 이종 관계 그래프로 역사적 조율 에피소드를 인코딩한다. 새로운 교란이 발생하면 그래프 신경망 기반 검색 메커니즘이 구조적으로 유사한 과거 에피소드를 식별하여, 처음부터 학습하는 대신 경험 기반 정책 적응을 가능하게 한다. 세 가지 교란 유형을 포함하는 동적 유연 작업장 스케줄링 벤치마크에서의 실험 결과, GSEM은 가장 강력한 메모리 증강 기준선 대비 makespan을 4.1%-10.0% 줄이고 적응 시간을 33%-38% 단축했으며, 교란 빈도가 높을수록 이 우위가 커진다. 소거 연구와 교차 교란 전이 실험은 그래프 구조 인코딩과 유사도 기반 검색의 필요성을 추가로 검증하고, 학습된 조율 패턴의 교차 교란 일반화 가능성을 입증한다.

arXiv:2607.08454v1cs.NI공통 태그 Scheduling, Graph Neural Network

백홀 지연 환경에서 강인한 협력 빔포밍을 위한 시공간적 스케줄링 예측

Spatio-Temporal Scheduling Prediction Under Backhaul Delay for Resilient Coordinated Beamforming

분산 5G 네트워크에서의 협력 빔포밍(Coordinated Beamforming)은 셀 간 스케줄링 정보의 적시 교환에 의존하지만, 백홀 지연으로 인해 이 정보가 오래될 수 있다. 단 하나의 전송 시간 구간(TTI) 지연만으로도 CBF-SLNR 성능이 비협력 기준선 이하로 떨어질 수 있는데, 이는 프리코더가 더 이상 활성화되지 않은 사용자를 향한 간섭을 억제하기 때문이다. 따라서 오래된 정보에 기반한 협력은 전혀 협력하지 않는 것보다 오히려 더 나쁜 결과를 초래한다. 이를 해결하기 위해, 본 논문은 스펙트럴 시간적 그래프 신경망(StemGNN, Spectral Temporal Graph Neural Network)이 지연된 과거 관측값으로부터 미래 단말(UE) 스케줄링 상태를 예측하고, 그 예측값이 CBF-SLNR 프리코더의 오래된 입력을 대체하는 2단계 예측 프레임워크를 제안한다. Quadriga Urban Micro (UMi) 채널과 비례 공정 스케줄러를 사용하는, 기지국당 64개의 안테나와 60개의 UE를 갖춘 3-셀 대규모 MIMO(massive MIMO) 다운링크에서 평가한 결과, StemGNN은 평균 스케줄링 예측 정확도 87.57%를 달성하여 모든 평가 지평에서 LSTM, GRU, Simple RNN, 마르코프 체인 기준선을 능가하였으며, UE 간 구조적 의존성이 시간적 자기상관보다 지배적인 긴 지평에서 LSTM 대비 최대 7.71% 향상을 보였다. 협력 빔포밍에 통합되었을 때, 예측값은 1 TTI 백홀 지연으로 인한 합산 전송률 손실의 57~73%를 복구하고, 예측 없는 기준선 대비 합산 전송률을 9.58~14.35% 향상시키며, 셀 경계 사용자에 대한 Lag-1 공정성 손실의 최대 83%를 회복한다. 또한 처리량 이득이 감소하는 높은 지연 값에서도 공정성 향상이 지속된다. 이러한 결과는 백홀 지연을 시공간적 예측 문제로 접근하는 것이 지연 제약 네트워크에서 강인한 셀 간 협력을 위한 효과적인 방법임을 보여준다.

arXiv:2608.23986v4math.OC공통 태그 Scheduling

지능의 그림자 가격: LLM 추론에서의 품질 저하와 재시도 피드백

The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference

대규모 언어 모델 제공자는 연산 자원이 제약되어 있으며, 혼잡에 대한 일반적인 대응은 서비스를 저하시키는 것이다. 즉, 질의를 더 작은 모델로 라우팅하거나, 추론 예산을 줄이거나, 컨텍스트 윈도를 단축한다. 만족스럽지 못한 답을 받은 사용자는 재시도하여 시스템이 바쁜 동안 부하를 늘리거나, 이탈하여 잠재적으로 고객 이탈로 이어진다. 우리는 추론 서비스를 서비스 품질이 제공자의 의사결정인 제어 문제로 모델링한다. 재시도를 서비스율에 포함한 2국면 유체 근사는 닫힌 형태의 궤적과 교차 시간을 제공하므로, 품질 등급에 대한 동적 계획법에 시뮬레이션이 필요하지 않다. 우리는 더 약한 등급이 작업당 에너지는 덜 쓰지만 작업당 용량은 더 쓰는 영역을 규명하고, 유체 모델에서 그러한 등급으로의 반응적 스로틀링이 큐가 해소되지 못하게 할 수 있음을 보인다. 이질적인 고객이 있는 경우 이 문제는 재시도로 부풀려진 용량 계수를 갖는 수송 문제가 되며, 최적 라우팅은 $c\mu$ 유형의 지수를 따르고, 용량 제약의 쌍대는 클래스와 시간별로 질의 하나를 더 처리하는 한계 비용을 제공한다. 우리는 공개 벤치마크 데이터로 보정한 다섯 가지 사례에서 이 방법을 예시한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.