This paper presents part of the work developed so far within the scope of my PhD and suggests possible future research directions. My thesis tackles the problem of multi-robot coordination under uncertainty over the long-term. We present a preliminary approach that tackles multi-robot monitoring problems under uncertain task durations. We propose a methodology that takes advantage of a modeling formalism for robot teams: generalized stochastic Petri nets with rewards (GSPNR). A GSPNR allows for unified modeling of action selection and uncertainty on duration of action execution. At the same time, it allows for goal specification through the use of transition rewards and rewards per time unit. The proposed approach exploits the well-defined semantics provided by Markov reward automata in order to synthesize policies.