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

Jul 16, 2026

Multi-robot persistent monitoring is investigated on weighted graphs where node weights represent monitoring priorities and edge weights represent travel distances. The objective is to minimize the worst-case weighted latency over all nodes across an infinite horizon, addressing shortcomings of standard worst-latency formulations that obscure transient weakness. A family of tail-performance objectives generalizes the classical metric, enabling theoretical guarantees, approximation via periodic solutions, and reductions to event-driven decision models.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages41

Reading Time1 h 43 min

Introduction

Problem formulation and tail-performance objectives

Tail Worst-case Latency-Optimizing MDP (TWLO-MDP)

Reinforcement-learning-based solutions

Benchmark M2Bench and experiments

Minimizing Worst-Case Weighted Latency for Multi-Robot Persistent Monitoring: Theory and RL-Based Solutions Journal Title XX(X):1–39 ©The Author(s) 2016 Reprints and permission: [sagepub.co.uk/journalsPermissions.nav](sagepub.co.uk/journalsPermissions.nav)[ ](sagepub.co.uk/journalsPermissions.nav)DOI: 10.1177/ToBeAssigned [www.sagepub.com/](www.sagepub.com/) SAGE arXiv :2605 .09633v2 [ cs .RO] 13 Jul 2026 Weizhen Wang1,2 , Ziheng Wang1 , Jianping He1,2 , Xinping Guan1,2 , and Xiaoming Duan1,2 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 time. 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-cost 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. Keywords Multi-robot monitoring, Markov decision process, reinforcement learning, benchmarking platform 1 Introduction Persistent monitoring is a key application area for many real-world robotic systems, with representative scenarios including urban crime surveillance (PalmaBorda et al. 2026), post-disaster area monitoring (Kumar et al. 2022), anomaly detection (Witwicki et al. 2017), ocean monitoring (Smith et al. 2011), and forest fire detection (Momeni et al. 2022) . In these applications, a team of robots is required to repeatedly visit a set of important locations so that abnormal events can be detected in a timely manner. This naturally leads to a graph-based multi-robot monitoring problem, where nodes represent locations of interest, edges represent feasible travel paths, and the robots must coordinate their long-term movements on the graph over an infinite time horizon. A central performance measure for this problem is latency, which quantifies how long each location remains unvisited. Since large latency at any important location may delay event detection, many studies adopt a worst-case perspective and seek coordinated multirobot trajectories that minimize the maximum latency across the graph over time. This problem has attracted significant attention over the past two decades (Machado et al. 2003 ; Chevaleyre 2004 ; Portugal and Rocha 2011 ; Huang et al. 2019 ; Basilico 2022) . Earlier studies formalized the worst-latency objective and established the computational hardness of the resulting optimization problems, including NP-hardness of exact optimization and APX-hardness of approximation in weighted variants (Chevaleyre 2004 ; Alamdari et al. 2014) . Subsequent work has developed a range of solution methods, incl

FAQs

What is the monitoring objective in the document?

The document targets joint multi-robot trajectories that minimize the worst-case weighted latency across all graph nodes over an infinite time horizon.

Why do the authors introduce tail-performance objectives instead of using the standard worst-case latency objective?

They note that the standard objective may not distinguish strategies with poor transient behavior even if long-run (asymptotic) performance is strong.

How do reinforcement learning methods connect to TWLO-MDP in the solutions?

The tail-performance objective is reformulated as an equivalent event-driven Markov decision process (TWLO-MDP), and reinforcement-learning-based solution methods are developed to solve this MDP formulation.

Jul 16, 2026

Upload by Ava Thompson