Optimal Threshold-Based Control Policies for Persistent Monitoring on Graphs

Nan Zhou, Christos G. Cassandras, Xi Yu, Sean B. AnderssonarXiv 2018 · DOI · arXiv

Abstract

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.

Introduction

Persistent monitoring involves a team of agents visiting a set of targets to minimize overall state uncertainty. Unlike traditional coverage control, where targets are visited once, persistent monitoring requires continuous revisits because uncertainty grows over time. The primary challenge is the simultaneous optimization of the visit sequence and the dwell time at each node. This problem is generally NP-hard and computationally intractable for large-scale systems due to the continuous-variable nature of the decision space.

Threshold-Based Control Methodology

To address these complexities, the environment is modeled as a graph where nodes represent targets. The authors propose a distributed, threshold-based parametric controller. In this framework, an agent's movement is governed by two types of thresholds:

  1. Dwell Threshold ($\theta_{ii}$): An agent stays at node $i$ until the uncertainty level $R_i$ drops below $\theta_{ii}$.
  2. Transition Threshold ($\theta_{ij}$): An agent moves to a neighboring node $j$ only if the uncertainty $R_j$ exceeds $\theta_{ij}$.
The relationship between the graph topology and the threshold parameter matrix $\Theta$.

This approach transforms the trajectory optimization problem into a parameter optimization problem over the matrix $\Theta$. By adjusting these thresholds, the system can dynamically adapt to changing uncertainty rates across the graph.

Optimization via Infinitesimal Perturbation Analysis (IPA)

The system is modeled as a hybrid dynamic system with continuous uncertainty growth and discrete event-driven transitions. To optimize the threshold parameters $\Theta$ online, the authors employ Infinitesimal Perturbation Analysis (IPA). IPA calculates the gradient of the cost function with respect to the thresholds by observing how small perturbations in event times (like arrivals or departures) propagate through the system.

Illustration of perturbation generation at target events and its propagation through agent events in the IPA framework.

Because IPA is event-driven, its complexity scales with the number of events rather than the state-space size. This makes it significantly more efficient than traditional grid-based methods, allowing for real-time local optimization via gradient descent.

Key Insights

The "Reduce to Zero" Rule

A significant theoretical finding is that for a single agent, the optimal dwell threshold $\theta_{ii}$ is always zero. This implies that the most efficient strategy for a single agent is to remain at a node until its uncertainty is completely eliminated before moving to the next target. This result simplifies the control logic for single-agent systems significantly.

Multi-Agent Coordination

In multi-agent scenarios, the "reduce to zero" rule does not necessarily hold. Team dynamics may make it optimal for an agent to leave a node early if a teammate is better positioned to handle the remaining uncertainty. This highlights the importance of cooperative monitoring and the need for agents to consider the states of neighboring nodes.

Performance Evaluation

The IPA-based threshold policy was compared against a global optimum derived via Dynamic Programming (DP) on a 4-target graph scenario.

  • Computational Efficiency: DP required approximately 16 minutes per iteration and faced severe state-space explosion ($2.5 \times 10^9$ states). In contrast, the IPA approach converged to a solution in just 30 seconds total.
  • Optimality: Despite being a local optimization method, the IPA approach achieved a final cost ($J_{IPA} = 36.20$) remarkably close to the DP global optimum ($J_{DP} = 31.15$), demonstrating high performance with a fraction of the computational cost.

Conclusion and Future Work

This research provides a scalable, distributed framework for persistent monitoring on graphs. By leveraging IPA for real-time threshold optimization, the proposed method circumvents the "curse of dimensionality" associated with traditional trajectory planning. Future work will explore multi-step look-ahead policies to prevent agents from becoming trapped in local graph clusters, potentially improving global performance while maintaining the benefits of event-driven optimization.

Summary updated

Abstract

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.
BibTeX
@misc{zhou2018optimal,
  author = {Nan Zhou and Christos G. Cassandras and Xi Yu and Sean B. Andersson},
  title = {{Optimal Threshold-Based Control Policies for Persistent Monitoring on Graphs}},
  year = {2018},
  eprint = {1803.02798},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.02798},
}
Figure