  In this paper we present a method for automatically planning robust optimal
paths for a group of robots that satisfy a common high level mission
specification. Each robot's motion in the environment is modeled as a weighted
transition system, and the mission is given as a Linear Temporal Logic (LTL)
formula over a set of propositions satisfied by the regions of the environment.
In addition, an optimizing proposition must repeatedly be satisfied. The goal
is to minimize the maximum time between satisfying instances of the optimizing
proposition while ensuring that the LTL formula is satisfied even with
uncertainty in the robots' traveling times. We characterize a class of LTL
formulas that are robust to robot timing errors, for which we generate optimal
paths if no timing errors are present, and we present bounds on the deviation
from the optimal values in the presence of errors. We implement and
experimentally evaluate our method considering a persistent monitoring task in
a road network environment.
