nLab controllability and observability

Idea

In the context of control theory and automata theory, controllability and observability are dual concepts describing the capacities (1) to control the state of a system and (2) to detect the state of a system from observations. In automata theory, the alternative term reachability is frequently used in place of controllability.

Linear systems

A simple case is given by the example of finite-dimensional linear systems. Given a system of linear differential equations of the form

$$\begin{aligned} \dot{x} & = A x + B u \\ y & = C x \end{aligned}$$

where $x$ is the state vector, $u$ is the control vector and $y$ is the output vector, then controllability is based on the rank of the matrix $P$:

$$P \,=\, \big[ B, A B, A^2B, ..., A^{n-1}B \big] \mathrlap{\,,}$$

where $n$ is the dimension of the state vector space, full controllability corresponding to $rank P = n.$

Similarly observability is based on the rank of the matrix,

$$Q = \begin{bmatrix} C \\ C A \\ C A^2 \\ \vdots \\ C A^{n-1} \end{bmatrix}$$

full observability corresponding to $rank(Q) = n$

The dual system is given by

$$\begin{aligned} \dot{z} & = A^{\top}z + C^{\top}v \\ w & = B^{\top} z \mathrlap{\,.} \end{aligned}$$

Now controllability of the original system corresponds to observability of the dual, and vice versa.

Duality in this vein extends to many kinds of automata, nonlinear dynamical systems, hidden Markov models, etc. In (HK77), the authors write “duality between ‘controllability’ and ‘observability’ … is, mathematically, just the duality between vector fields and differential forms”, we may see the duality then as a concept with an attitude.

Separation principle

When a system is both fully controllable and observable, the so-called separation principle establishes that the design of a feedback controller and of a state observer are mutually independent. This facilitates the design of a closed-loop system with feedback from estimated states.

Petri nets

An incidence matrix, $C$, between places and transitions of a Petri net may be constructed such that the $(p, t)$ entry is the difference between incoming and outgoing $p$ arcs to $t$. One instance of the duality here is between so called $P$-invariants, $y^{\top} \cdot C = 0$ (number of tokens in all reachable markings satisfies some linear invariant) and $T$-invariants, $C \cdot x = 0$ (loop or firing sequences leaving the token count unchanged).

In (GARR), the authors discuss a duality which arises for a Petri net by switching its places and transitions, and reversing the directions of the arcs. This has the effect of replacing the incidence matrix, $C$, by the negative transpose, $-C^{\top}$. The $P$-invariants of a net are the $T$-invariants of the dual net, and vice versa.

Bialgebraic description

Often dualities of this form can be set in the framework of a bialgebra where a system‘s evolution and its outputs are described as $F(X) \to X \to G(X)$ for $X$ an object of a category $\mathcal{C}$ and two endofunctors, $F$ and $G$, on $\mathcal{C}$.

Suppose $F$ has an initial algebra, $\mu F$, and $G$ has a terminal coalgebra, $\nu G$, the unique map $r: \mu F \to X$ being an epimorphism corresponds to reachability/controllability, and the unique map $o:X \to \nu G$ being a monomorphism corresponds to observability.

There is generally a contravariant functor, $D$, which plays a dualizing role, and then natural transformations $F D \to D G$ and $D F \to G D$ allow us to see $D(X)$ also as a bialgebra, $F D(X) \to D G(X) \to D(X) \to D F(X) \to G D(X).$

One example of this is given in Set where $F(X) = 1 + A \times X$ and $G(X) = 2 \times X^A$. A bialgebra here is a finite state automaton with inputs given by $A$, and an initial state, $i:1 \to X$ and a final accepting costate $f: X \to 2$ with update function $u: A \times X \to X$, curried to $\hat{u}:X \to X^A$. The state space of $\mu F$ is $A^{\ast}$, the set of words on $A$, and the state space of $\nu G$ is $2^{A^{\ast}}$. The dual automaton has state space, $D(X) = 2^X$, $D$ being the contravariant power set functor. Here $D F(X) \cong G D(X)$.

Brzozowski’s double-reversal minimisation algorithm for deterministic finite automata may be seen through this lens as applying dualization then restricting to the reachable subpart twice.

In the finite linear case, the relevant bialgebra is $U \oplus X \to X \to Y \oplus X$. The initial algebra is $\bigoplus_{i \in \mathbb{N}} U$, and the terminal coalgebra is $\prod_{i \in \mathbb{N}} Y$. These are infinite-dimensional and correspond to finite sequences of elements of $U$ and streams of elements of $Y$. Dualization here is to the dual vector space.

Since a system may be seen as giving rise to a map from an initial algebra to a terminal coalgebra which factors through it, frequently this map may be rephrased as a pairing. E.g., for automata, a map from $A^{\ast}$ to $2^{A^{\ast}}$, may be rewritten as a pairing $A^{\ast} \times A^{\ast} \to 2$. Similarly, in the finite linear case, a map $\bigoplus_{i \in \mathbb{N}} U$ to $\prod_{i \in \mathbb{N}} Y$, may be rewritten as a pairing, $\bigoplus_{i \in \mathbb{N}} U \times \bigoplus_{i \in \mathbb{N}} Y^{\ast} \to \mathbb{R}$. In this way, these examples become instances of Chu duality theory.

References

The founding paper:

• R. E. Kalman: On the General Theory of Control Systems, Proceedings of the First International Congress on Automatic Control 1 1, Butterworth, London (1960) 481–493 [doi:10.1016/S1474-6670(17)70094-8]

An extension to nonlinear systems:

• R. Hermann and A. Krener, Nonlinear controllability and observability, IEEE Transactions on automatic control, vol. 22, no. 5, pp. 728–740, 1977 [doi:10.1109/TAC.1977.1101601].

In automata theory:

• Michael A. Arbib and Ernest G. Manes, Adjoint machines, state-behavior machines, and duality, Journal of Pure and Applied Algebra 6.3 (1975): 313-344 [doi:10.1016/0022-4049(75)90028-6].

On the bialgebraic formulation and automaton minimization:

• Filippo Bonchi, Marcello M. Bonsangue, Helle H. Hansen, Prakash Panangaden, Jan JMM Rutten, Alexandra Silva: Algebra-coalgebra duality in Brzozowski’s minimization algorithm ACM Transactions on Computational Logic (TOCL) 15 1 (2014) 1–29 [doi:10.1145/2490818, pdf]

• Nick Bezhanishvili, Marcello Bonsangue, Helle Hvid Hansen, Dexter Kozen, Clemens Kupke, Prakash Panangaden, Alexandra Silva, Minimisation in Logical Form [arXiv:2005.11551]

Duality for hidden Markov models:

• Jin Won Kim, Prashant G. Mehta, Duality for Nonlinear Filtering I: Observability [arXiv:2208.06586]; Duality for Nonlinear Filtering II: Optimal Control [arXiv:2208.06587]

Duality between output controllability and functional observability for networks:

• Arthur N. Montanari, Chao Duan, Adilson E. Motter, Duality between controllability and observability for target control and estimation in networks [arXiv:2401.16372]

Duality in forms of Petri net:

• J.L. García-Malacara, César Arzola, Antonio Ramírez-Treviño, C. Renato Vázquez, Duality of controllability and observability in proportional equal conflict timed continuous Petri Nets, Nonlinear Analysis: Hybrid Systems, Volume 52, 2024 [doi:10.1016/j.nahs.2023.101455].