arXiv:1904.08962

Constrained Restless Bandits for Dynamic Scheduling in Cyber-Physical Systems

Kesav Kaza, Rahul Meshram, Varun Mehta, S. N. Merchant

제출 2019-04-18

원문 초록

This paper studies a class of constrained restless multi-armed bandits (CRMAB). The constraints are in the form of time varying set of actions (set of available arms). This variation can be either stochastic or semi-deterministic. Given a set of arms, a fixed number of them can be chosen to be played in each decision interval. The play of each arm yields a state dependent reward. The current states of arms are partially observable through binary feedback signals from arms that are played. The current availability of arms is fully observable. The objective is to maximize long term cumulative reward. The uncertainty about future availability of arms along with partial state information makes this objective challenging. Applications for CRMAB can be found in resource allocation in cyber-physical systems involving components with time varying availability. First, this optimization problem is analyzed using Whittle's index policy. To this end, a constrained restless single-armed bandit is studied. It is shown to admit a threshold-type optimal policy and is also indexable. An algorithm to compute Whittle's index is presented. An alternate solution method with lower complexity is also presented in the form of an online rollout policy. A detailed discussion on the complexity of both these schemes is also presented, which suggests that online rollout policy with short look ahead is simpler to implement than Whittle's index computation. Further, upper bounds on the value function are derived in order to estimate the degree of sub-optimality of various solutions. The simulation study compares the performance of Whittle's index, online rollout, myopic and modified Whittle's index policies.

함께 살펴볼 논문

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

arXiv:2609.23058v2cs.AI공통 태그 Decision Making, Scheduling

LazyAgent: 수요 기반 구체화 및 에이전트 프로그램의 물리적 최적화

LazyAgent: Demand-Driven Materialization and Physical Optimization of Agentic Programs

행동에 앞서 계획을 세우는 에이전트 런타임은 각 단계가 준비되는 즉시 실행한다. 이러한 런타임도 그 벤치마크도 준비된 단계와 요청이 필요로 하는 단계를 구별하지 않으며, 그 차이는 크다. 154개의 프로덕션 워크플로에 대한 303개 요청에서, 목표가 달성되면 멈추는 즉시 실행(eager) 런타임은 CPU의 62.2%를 요청이 전혀 필요로 하지 않은 작업에 소비한다. LazyAgent는 우리가 아는 한 에이전트 런타임을 위한 수요 기반 실행의 최초의 완전한 정식화이다. 그 규칙은 준비된 단계를 현재 요청이 필요로 할 때만 실행하고, 계획이 바뀌어도 그 답을 정확하게 유지하는 것이다. 프로그램에서 도출된 수요 집합이 모델 호출 없이 한 번의 순회로 이를 결정하므로, LazyAgent는 요청 밖에서는 아무것도 소비하지 않는다. 수요가 정확하게 정의되기 때문에 그 동작이 증명되며, 빌더는 어떤 실행 이전에도 수요가 어디에서 절감해야 하고 어디에서 동률이어야 하는지 알 수 있다. 계획이 실행되기 전에 비용이 알려지므로, LazyAgent는 쿼리 옵티마이저로서 후보 워크플로 중에서 선택할 수 있다. 해당 즉시 실행 런타임과 비교한 실측에서, LazyAgent는 최첨단 LLM이 패치를 작성하는 릴리스 게이트에서 컨테이너 시간을 51.7%와 52.1% 절감하고, 동일한 품질의 DataSciBench 계획에서 토큰을 12.8%, 실제 LangGraph 애플리케이션에서 비용을 24.0% 절감하며, 손실은 없다. LLM이 실제 코드 실패 후 재계획할 때는 해결 가능한 모든 목표를 목표당 토큰 11.7% 적게 사용하여 해결한다. 프로덕션 워크플로에서는 CPU를 42.0% 절감하고, 요청이 전체 그래프를 필요로 하는 경우에는 정확히 동률이며, 오버헤드는 최대 0.43%이다. 동일한 집합이 모든 물리적 연산을 조정하는데, 프로젝션은 공유 CI 단계의 80-89%를 절감하는 반면 동일한 즉시 실행 대조군은 0.0%를 절감한다. 공개 에이전트 벤치마크는 즉시 실행 런타임과 같은 방식으로 설계되어 있어 이 차이를 보여줄 수 없다. 우리는 이들의 과제로 테스트 프로그램을 구성하였으며, 업계에 에이전트 워크플로가 얼마나 효율적으로 실행되는지를 측정하는 벤치마크를 구축할 것을 촉구한다.

arXiv:2609.37085v2cs.DC공통 태그 Decision Making, Scheduling

ARGOS: 컴퓨팅 연속체에서의 서비스 오케스트레이션을 위한 강화학습 기반 다차원 탄력성

ARGOS: Reinforcement Learning-Driven Multidimensional Elasticity for Service Orchestration in the Computing Continuum

컴퓨팅 연속체(Computing Continuum)의 데이터 집약적 서비스는 용량이 제한적이고 불균등한 이기종 노드 전반에서 분석 품질, 자원 사용량, 비용 간의 균형을 유지해야 합니다. 자원 스케일링이 용량 한계에 도달하면 수요 변화와 클러스터 압박을 클라이언트가 정의한 품질 범위를 위반하지 않으면서 흡수해야 하므로 이러한 균형을 맞추기가 특히 어려워집니다. 기존 오케스트레이터는 주로 자원, 배치 또는 복제본을 조정하는 반면, 커버리지, 샘플, 최신성과 같은 분석 요구사항은 고정된 상태로 유지합니다. 본 논문에서는 용량 인식 승인 제어(capacity-aware admission)의 지원을 받아 분석 품질 및 클러스터 압박에 대한 요청별 마르코프 결정 과정(MDP)으로 다차원 탄력성을 정형화하는 엔드투엔드 컨트롤러인 ARGOS(Adaptive Reinforcement Learning-Driven Governance for Orchestrated Services)를 제시합니다. ARGOS는 이기종 클러스터에서 통제된 워크로드와 시간에 따라 변하는 다중 테넌트 유입 환경을 바탕으로 평가되었습니다. 통제된 시나리오 전반에서 심층 강화학습 정책은 비학습 기반 베이스라인을 일관되게 능가하며 독립적으로 튜닝된 최적 고정 참조 모델에 근접했습니다. 별도의 실제 환경 평가에서는 현실적이고 포화된 유입 조건에서 정적 중간값 대비 성능 향상을 보였으며, 기록된 CPU 또는 메모리 위반은 없었으나 커버리지 위반은 일부 남아 있었습니다. 이러한 결과는 자원 스케일링만으로는 불충분할 때 심층 강화학습이 다차원 탄력성을 위한 적응형 메커니즘으로 유효함을 뒷받침합니다.

arXiv:2610.03296v1cs.AI공통 태그 Scheduling, Multi-Armed Bandits

JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.

arXiv:2610.01364v1cs.MA공통 태그 Decision Making, Scheduling

스킬 기반 스마트 제조를 위한 LLM 기반 다중 에이전트 제어

LLM-Driven Multi-Agent Control for Skill-Based Smart Manufacturing

공장은 높은 수준의 제품 맞춤화를 갖춘 소량 생산 체제로 전환되고 있으며, 이에 따라 유연하고 재구성 가능한 자동화 시스템의 빈번한 재프로그래밍이 요구됩니다. 대규모 언어 모델(LLM) 기반 에이전트(agent)는 상호보완적인 두 가지 역할로 배치될 수 있습니다. 오프라인에서는 결정론적 생산 시퀀스를 생성하여 프로그래밍 노력을 줄이고, 온라인에서는 실제 기계를 운영하며 정적 프로그램이 예측할 수 없는 런타임 오류를 처리합니다. 본 논문에서는 각 공장 모듈을 전용 LLM 기반 에이전트 및 OPC UA 메서드 호출을 통해 모듈의 스킬을 노출하는 MCP 툴 서버와 결합하고, 에이전트들이 MQTT를 통해 조율하며 공장 상태의 실시간 업데이트를 바탕으로 그라운딩(grounding)되는 솔루션을 제안합니다. 실제 6개 모듈 육각형 공장의 시뮬레이션 환경에서 무음 하드웨어 결함 감지를 포함하여 복잡성이 증가하는 9가지 생산 과제를 대상으로 세 가지 에이전트 아키텍처(오케스트레이터, 피어투피어, 모놀리식)를 비교합니다. 모놀리식 및 피어투피어 아키텍처는 모두 가장 높은 평균 해결률(93%)을 달성한 반면, 오케스트레이터는 차단된 구간 주변으로 플레이트 경로를 자율적으로 재지정함으로써 10회 실행 모두에서 무음 컨베이어 벨트 결함을 유일하게 해결했습니다. 모든 아키텍처는 명시적인 장애 처리 로직 없이도 창발적(emergent) 결함 진단 동작을 보이며, 표준화된 MCP 툴링, MQTT 기반 에이전트 간 통신, 실시간 상태 주입이 LLM으로 프로그래밍되는 스마트 제조를 위한 실용적이고 재현 가능한 기반임을 입증합니다.

arXiv:2609.28064v1cs.AI공통 태그 Decision Making, Scheduling

SlackDrive: 적응형 주행 추론을 위한 런타임 슬랙 회수

SlackDrive: Reclaiming Runtime Slack for Adaptive Driving Inference

주행 world-action 모델은 다중모달 추론과 미래 예측을 결합해 계획(planning)을 개선하지만, 커지는 추론 비용은 차량 제어의 실시간 지연(latency) 요구와 점점 더 충돌한다. 기존 가속 방법은 배포 전에 선택된 정책으로 토큰, 레이어, 또는 샘플링 단계를 줄이지만, 공유 온보드 컴퓨트에서 오프라인 프로파일링과 정적 스케줄링 이후 잔여 런타임 변동은 대부분 활용하지 못한다. 우리는 허용 가능한 최대 컴퓨트 예산이 잔여 런타임 상태에 따라 체계적으로 달라지며, 최근 실현 지연(latency)이 가용 컴퓨트 슬랙(slack)에 대한 직접적인 신호를 제공함을 관찰한다. 이 관찰에 기반해, 우리는 실현 지연을 재사용하여 모델 실행 전 각 제어 단계의 컴퓨트 예산을 고르는 추론 전(pre-inference) 컴퓨트 할당기 SlackDrive를 제안한다. SlackDrive는 작은 이산 예산 집합에 대한 지연과 계획(planning) 유틸리티를 한 번 프로파일링하고, 완료된 forward로부터 온라인 컴퓨트 상태를 추정하며, 허용 가능한 지연(latency) envelope 안에 남을 것으로 예측되는 최고 유틸리티 예산을 선택해 주행 백본과 그 컴퓨트 액추에이터는 유지한 채 기존 프로파일링 및 리소스 스케줄링을 보완한다. NAVSIM v2에서 DriveDreamer-Policy와 함께 평가할 때 SlackDrive는 엄격한 지연 체제 하에서 최강 기준선 대비 지연 제약 EPDMS를 21.7% 개선했으며, 전체 예산 모델과 사전 구성된 토큰 가지치기 기준선은 런타임 경합 하에서 허용 가능한 지연 envelope를 초과했다.

arXiv:2607.23678v1cs.AI공통 태그 Decision Making, Scheduling

집중이 전부다: 다중 에이전트 그래프 시스템을 위한 적응형 목표 인식 어텐션 오케스트레이션

Focus Is All You Need: Adaptive Goal-aware Attention Orchestration for Multi-Agent Graph Systems

대규모 언어 모델(LLM)은 추론, 계획, 도구 사용을 위한 자율 에이전트를 가능하게 한다. 최근 시스템들은 이러한 에이전트를 전문화되고 상호 연결된 노드의 그래프로 점점 더 조직하고 있다. 그래프 기반 오케스트레이션은 유연한 분해와 조정을 지원하지만, 핵심 과제인 어텐션 할당(attention allocation)을 야기한다. 워크플로가 커질수록 기존 접근법은 종종 그래프 구성 요소를 균일하게 실행하여, 관련 없거나 영향이 낮은 작업에 자원을 낭비한다. 우리는 어텐션 오케스트레이션(Attention Orchestration)을 제안한다. 이는 트랜스포머 스타일의 어텐션을 토큰 표현에서 워크플로 수준의 에이전트 조정으로 확장하는 패러다임이다. 우리의 프레임워크인 적응형 목표 인식 어텐션 오케스트레이션(AGAO)은 사용자 목표, 그래프 의존성, 계산 제약을 기반으로 에이전트 중요도를 동적으로 추정한다. AGAO는 세 가지 구성 요소를 결합한다: (1) 목표 인식 어텐션(goal-aware attention), 사용자 목표와 에이전트 역량 간의 의미적 관련성을 측정; (2) 토폴로지 인식 어텐션(topology-aware attention), 에이전트 그래프의 구조적 의존성을 모델링; (3) 자원 인식 어텐션(resource-aware attention), 이종 에이전트 간 예산과 실행 우선순위를 할당. 이러한 메커니즘들이 함께 정적 에이전트 그래프를 목표에 핵심적인 추론 경로에 계산을 집중하는 적응형 시스템으로 변환한다. 다양한 다중 에이전트 워크로드에 걸친 실험은 AGAO가 기존 그래프 기반 실행 전략과 비교하여 불필요한 계산, 지연 시간, 토큰 소비를 줄이면서 작업 효과를 향상시킴을 보여준다. 우리의 연구는 확장 가능하고 지능적인 다중 에이전트 시스템을 위한 방향으로서 어텐션 엔지니어링(Attention Engineering)을 정립한다. Code: https://github.com/MingzhouFan97/AGAO.

토론

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