Minimizing Worst-Case Weighted Latency for Multi-Robot Persistent Monitoring: Theory and RL-Based Solutions

• URL: http://arxiv.org/abs/2605.09633v1
• Date: Sun, 10 May 2026 16:22:48 GMT
• Title: Minimizing Worst-Case Weighted Latency for Multi-Robot Persistent Monitoring: Theory and RL-Based Solutions
• Abstract summary: We study multi-robot persistent monitoring on weighted graphs, where node weights encode monitoring priorities and edge weights encode travel.<n>The goal is to design joint robot trajectories that minimize the worst-case latency across all nodes over an infinite time horizon.
• Score: 19.90961049459541
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study multi-robot persistent monitoring on weighted graphs, where node weights encode monitoring priorities and edge weights encode travel distances. The goal is to design joint robot trajectories that minimize the worst-case weighted latency across all nodes over an infinite time horizon. The widely adopted worst-case latency objective evaluates team performance over the entire time horizon and therefore may fail to distinguish strategies with poor transient behavior but strong asymptotic performance. To address this limitation, we propose a family of tail-performance objectives that generalize the standard objective and study the resulting functional optimization problems. We establish several key theoretical properties, including the existence of optimal strategies, relationships among the proposed objectives and their corresponding optimization problems, approximation by periodic solutions to arbitrary accuracy, and reductions to event-driven decision models with discretized waiting times. Building on these results, we construct an equivalent event-driven Markov decision process (MDP), called the Tail Worst-case Latency-Optimizing Markov Decision Process (TWLO-MDP), which reformulates the tail-performance objective as a standard average-reward criterion. We then develop reinforcement-learning-based solution methods for the TWLO-MDP and introduce the multi-robot monitoring benchmark (M2Bench), a unified platform that supports the evaluation and comparison of heuristic and learning-based monitoring algorithms. Experiments on synthetic and realistic monitoring scenarios show that our methods effectively reduce the worst-case weighted latency and outperform representative baselines.

Related papers

• Multi-Objective Structured Pruning of LLMs for Latency and Model Size Optimization [2.3012967702331313]
  Large Language Models (LLMs) have achieved widespread adoption because of their strong reasoning and query-response capabilities.<n> deploying them in embedded and edge computing environments remains challenging because of strict latency, memory, and energy constraints.<n>We propose a hardware-aware, multi-objective structured pruning framework to address these limitations.
  arXiv  Detail & Related papers  (2026-06-08T09:38:13Z)
• Multi-scale Coarse-to-fine Modeling for Test-time Human Motion Control [51.92884966472683]
  MSCoT is a multi-scale, coarse-to-fine model for test-time human motion synthesis and control.<n> MSCoT discretizes motion into a multi-scale hierarchical representation and predicts the entire token sequence at each temporal scale.
  arXiv  Detail & Related papers  (2026-05-14T15:09:49Z)
• Barrier-enforced multi-objective optimization for direct point and sharp interval forecasting [1.0966260566122237]
  This paper proposes a multi-step probabilistic forecasting framework using a single neural-network based model to generate simultaneous point and interval forecasts.<n>Our approach ensures non-crossing prediction intervals (PIs) through a model structure design that strictly satisfy a target coverage probability (PICP)<n>Results demonstrate that our proposed loss consistently outperforms those in current literature by achieving target coverage with the narrowest PI widths.
  arXiv  Detail & Related papers  (2026-04-20T16:43:12Z)
• Fault-Tolerant Design and Multi-Objective Model Checking for Real-Time Deep Reinforcement Learning Systems [7.759578639008443]
  Deep reinforcement learning (DRL) has emerged as a powerful paradigm for solving complex decision-making problems.<n>DRL-based systems still face significant dependability challenges due to the simulation-to-reality gap, out-of-distribution observations, and the critical impact of latency.<n>We propose a formal framework for designing and analysing real-time switching mechanisms between DRL agents and alternative controllers.
  arXiv  Detail & Related papers  (2026-03-24T12:08:06Z)
• Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time [52.230936493691985]
  We propose SITAlign, an inference framework that addresses the multifaceted nature of alignment by maximizing a primary objective while satisfying threshold-based constraints on secondary criteria.<n>We provide theoretical insights by deriving sub-optimality bounds of our satisficing based inference alignment approach.
  arXiv  Detail & Related papers  (2025-05-29T17:56:05Z)
• The Larger the Merrier? Efficient Large AI Model Inference in Wireless Edge Networks [56.37880529653111]
  The demand for large computation model (LAIM) services is driving a paradigm shift from traditional cloud-based inference to edge-based inference for low-latency, privacy-preserving applications.<n>In this paper, we investigate the LAIM-inference scheme, where a pre-trained LAIM is pruned and partitioned into on-device and on-server sub-models for deployment.
  arXiv  Detail & Related papers  (2025-05-14T08:18:55Z)
• Learning Dynamic Representations via An Optimally-Weighted Maximum Mean Discrepancy Optimization Framework for Continual Learning [16.10753846850319]
  Continual learning allows models to persistently acquire and retain information.<n> catastrophic forgetting can severely impair model performance.<n>We introduce a novel framework termed Optimally-Weighted Mean Discrepancy (OWMMD), which imposes penalties on representation alterations.
  arXiv  Detail & Related papers  (2025-01-21T13:33:45Z)
• Q-VLM: Post-training Quantization for Large Vision-Language Models [73.19871905102545]
  We propose a post-training quantization framework of large vision-language models (LVLMs) for efficient multi-modal inference.<n>We mine the cross-layer dependency that significantly influences discretization errors of the entire vision-language model, and embed this dependency into optimal quantization strategy.<n> Experimental results demonstrate that our method compresses the memory by 2.78x and increase generate speed by 1.44x about 13B LLaVA model without performance degradation.
  arXiv  Detail & Related papers  (2024-10-10T17:02:48Z)
• Reinforcement Learning with a Terminator [80.34572413850186]
  We learn the parameters of the TerMDP and leverage the structure of the estimation problem to provide state-wise confidence bounds. We use these to construct a provably-efficient algorithm, which accounts for termination, and bound its regret.
  arXiv  Detail & Related papers  (2022-05-30T18:40:28Z)
• Revisiting State Augmentation methods for Reinforcement Learning with Stochastic Delays [10.484851004093919]
  This paper formally describes the notion of Markov Decision Processes (MDPs) with delays. We show that delayed MDPs can be transformed into equivalent standard MDPs (without delays) with significantly simplified cost structure. We employ this equivalence to derive a model-free Delay-Resolved RL framework and show that even a simple RL algorithm built upon this framework achieves near-optimal rewards in environments with delays in actions and observations.
  arXiv  Detail & Related papers  (2021-08-17T10:45:55Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Trajectory Optimization for Nonlinear Multi-Agent Systems using Decentralized Learning Model Predictive Control [5.2647625557619815]
  We present a decentralized minimum-time trajectory optimization scheme based on learning model predictive control for multi-agent systems with nonlinear decoupled dynamics and coupled state constraints. Our framework results in a decentralized controller, which requires no communication between agents over each iteration of task execution, and guarantees persistent feasibility, finite-time closed-loop convergence, and non-decreasing performance of the global system over task iterations.
  arXiv  Detail & Related papers  (2020-04-02T23:04:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.