Stochastic Multi-Robot Monitoring on Graphs under Markovian Mobility
We study a stochastic multi-robot monitoring problem on a connected graph G = (V, E), where each robot moves according to a Markov chain on G and monitors the closed neighborhood of its current vertex. The performance of r robots is evaluated in steady state via two objectives: average-case coverage (the expected number of covered vertices) and worst-case coverage (the minimum coverage probability over all vertices). We consider three models: independent homogeneous strategies, where all robots share the same stationary distribution; independent heterogeneous strategies, where robots use different stationary distributions; and centralized strategies, allowing arbitrary correlations between robot locations.
For the heterogeneous model, we prove that maximizing average coverage is NP-hard even for two robots, and that replicating an easy-to-compute optimal homogeneous strategy yields a (1 ? (1 ? 1/r)^r)-approximation for both objective functions in the heterogeneous setting; moreover, no polynomial-time algorithm can achieve a ratio better than 1 ? 1/e unless P = NP.
Centralized strategies can exploit correlations to reduce redundancy. We develop a hierarchy of approximation factors: for any positive integer r’ ? r, writing r = h r’ + b with 0 ? b < r’, block coordination yields a [1 ? (1 ? r’/r)^h (1 ? b/r)]-approximation for both objectives. We also establish NP-hardness and a tight 1 ? 1/e inapproximability bound. Moreover, we prove diminishing-returns properties with respect to the number of robots: a non-increasing-ratio property holds for the average-case objective in all settings, but not for the heterogeneous worst-case objective. These results provide a unified complexity and approximation landscape for stochastic graph monitoring and quantify the benefit of heterogeneity and coordination in steady-state multi-robot monitoring.
Joint work with Walid Ben-Ameur and Tijani Chahed.
arXiv:2608.20618