Herdability of Linear Systems Based on Sign Patterns and Graph Structures

Sebastian F. Ruf, Magnus Egerstedt, Jeff S. ShammaarXiv 2019 · arXiv

Introduction: Beyond Classical Controllability

In classical control theory, controllability is the standard metric for system performance, asking whether a system can be driven from any initial state to any target point in the state space. However, many real-world applications—ranging from social network influence to biological quorum sensing—do not require such precise "point-to-point" control. Instead, the objective is often to drive a collective state above a specific threshold.

This paper introduces the concept of herdability, a set-based reachability condition. A system is considered herdable if its state can be driven above a non-negative threshold, regardless of its starting point. This framework shifts the focus from individual placement to collective behavior, much like a shepherd ensuring a herd enters a pen rather than positioning each sheep at a specific coordinate.

Methodology: Algebraic and Structural Approaches

The authors analyze continuous-time, Linear Time-Invariant (LTI) systems defined by $\dot{x} = Ax + Bu$. Their approach integrates linear algebra with structural graph theory to characterize herdability.

Algebraic Characterization

A fundamental result of the paper is that a system is herdable if and only if there exists a strictly positive vector within the range of the controllability matrix $C$. This provides a concrete mathematical test for the property.

Qualitative Systems Analysis and Sign Patterns

In many practical models, exact system parameters are unknown. To address this, the researchers focus on sign herdability. This property depends solely on the "sign pattern"—the positive or negative nature of interactions—rather than exact numerical weights. By representing the system as a signed, directed graph, they can determine if the structure itself guarantees herdability.

Figure 1: Signed and weighted directed graphs used to analyze sign herdability.

Key Insights: The Role of Graph Structure

The research highlights several critical links between a system's underlying graph and its herdability:

  • Structural Balance: A key finding is the connection between structural balance (where all semi-cycles in a graph are positive) and the sign pattern of the controllability matrix. In structurally balanced graphs, paths do not "cancel each other out," preserving the ability to push the system state in a desired direction.
  • Positive Systems: For systems where states and inputs remain non-negative, herdability simplifies significantly, becoming equivalent to basic input connectability.
  • Symmetry: Unlike traditional controllability, where symmetry often introduces uncontrollable modes, herdability is more robust and can be maintained even in certain symmetric configurations.

Main Results

The paper establishes several formal conditions for herdability:

  1. Necessary Condition: Any completely herdable system must be input connectable, meaning every state node must be reachable from at least one input.
  2. Out-branching Characterization: For systems structured as a "rooted out-branching"—a tree-like structure originating from the input—the authors provide a formula to determine the maximum number of nodes that can be simultaneously herded based on path lengths.
Figure 5: An out-branching structure used to characterize herdability in tree-like networks.
  1. Sign Herdability Conditions: The authors identify specific graph-theoretic conditions under which the sign pattern alone is sufficient to guarantee herdability, offering a robust tool for analyzing systems with uncertain parameters.

Conclusion and Future Directions

While the paper provides a strong theoretical foundation, it also notes that determining herdability for general graphs with complex cycles can be computationally intensive (NP-hard). The algorithm's time complexity can grow exponentially with the number of state nodes in non-acyclic systems.

Future research directions include developing efficient approximation algorithms for large-scale networks and extending the theory to "output herdability," where only a subset of observed variables needs to meet the threshold. This work opens new avenues for controlling complex systems in fields like synthetic biology and opinion dynamics.

Summary updated

Abstract

We consider the notion of herdability, a set-based reachability condition, which asks whether the state of a system can be controlled to be element-wise larger than a non-negative threshold. First a number of foundational results on herdability of a continuous time, linear time invariant system are presented. These show that the herdability of a linear system can be determined based on certain matrices, such as the controllability matrix, which arise in the study of controllability of linear systems. Second, the relationship between the sign pattern of the underlying graph structure of a system and the herdability properties of the system is investigated. In doing so the notion of sign herdability is introduced which captures classes of systems whose sign pattern determines their herdability. We identify a set of conditions, first on the sign pattern of the controllability matrix and then on the underlying graph structure, that ensure that the system is sign herdable.
BibTeX
@misc{ruf2019herdability,
  author = {Sebastian F. Ruf and Magnus Egerstedt and Jeff S. Shamma},
  title = {{Herdability of Linear Systems Based on Sign Patterns and Graph Structures}},
  year = {2019},
  eprint = {1904.08778},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.08778},
}
Figure