  We consider the optimal multi-agent persistent monitoring problem defined by
a team of cooperating agents visiting a set of nodes (targets) on a graph with
the objective of minimizing a measure of overall node state uncertainty. The
solution to this problem involves agent trajectories defined both by the
sequence of nodes to be visited by each agent and the amount of time spent at
each node. Since such optimal trajectories are generally intractable, we
propose a class of distributed threshold-based parametric controllers through
which agent transitions from one node to the next are controlled by threshold
parameters on the node uncertainty states. The resulting behavior of the
agent-target system can be described by a hybrid dynamic system. This enables
the use of Infinitesimal Perturbation Analysis (IPA) to determine on line
(locally) optimal threshold parameters through gradient descent methods and
thus obtain optimal controllers within this family of threshold-based policies.
We further show that in a single-agent case the IPA gradient is monotonic,
which implies a simple structure whereby an agent visiting a node should reduce
the uncertainty state to zero before moving to the next node. Simulation
examples are included to illustrate our results and compare them to optimal
solutions derived through dynamic programming when this is possible.
