Skip to main content
Engineering LibreTexts

22.2: The Reachability Problem

  • Page ID
    24361
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    In previous lectures we have examined solutions of state-space models, the stability of undriven models, some properties of interconnections, and input-output stability. We now turn to a more detailed examination of how inputs affect states, for the \(n^{th}\)-order DT system

    \[x(i+1)=A x(i)+B u(i)\label{22.1}\]

    (The discussion of reachability in the DT case is generally simpler than in the CT case that we will consider next Chapter, but some structural subtleties that are hidden in the CT case become more apparent in the DT case. For the most part, however, DT results parallel CT results quite closely.)

    Recall that

    \[\begin{aligned}
    x(k) &=A^{k} x(0)+\sum_{i=0}^{k-1} A^{k-i-1} B u(i) \\
    &=A^{k} x(0)+\left[A^{k-1} B\left|A^{k-2} B\right| \cdots \mid B\right] \\
    &=A^{k} x(0)+R_{k} \mathcal{U}_{k}
    \end{aligned}\label{22.2}\]

    where the definition of \(R_{k}\) and \(U_{k}\) should be clear from the equation that precedes them. Now consider whether and how we may choose the input sequence \(u(i), i \in[0, k-1]\), so as to move the system from \(x(0) = 0\) to a desired target state \(x(k) = d\) at a given time \(k\). If there is such an input, we say that the state \(d\) is reachable in \(k\) steps. It is evident from (22.2) that | assuming there are no constraints placed on the input - the set \(\mathbb{R}_{k}\) of states reachable from the origin in \(k\) steps, or the \(k\)-reachable set, is precisely the range of \(R_{k}\), i.e.

    \[\mathbb{R}_{k}=R a\left(R_{k}\right)\label{22.3}\]

    The \(k\)-reachable set is therefore a subspace, and may be referred to as the \(k\)-reachable subspace. We call the matrix \(R_{k}\) the \(k\)-step reachability matrix.

    Theorem \(\PageIndex{22.1}\)

    For \(k \leq n \leq \ell\),

    \[R a\left(R_{k}\right) \subseteq R a\left(R_{n}\right)=R a\left(R_{\ell}\right)\label{22.4}\]

    so the set of states reachable from the origin in some (finite) number of steps by appropriate choice of control is precisely the subspace of states reachable in \(n\) steps.

    Proof

    The fact that \(R a\left(R_{k}\right) \subseteq R a\left(R_{n}\right)\) for \(k \leq n\) follows trivially from the fact that the columns of \(R_{k}\) are in- cluded among those of \(R_{n}\). To show that \(R a\left(R_{n}\right)=R a\left(R_{\ell}\right)\) for \(\ell \geq n\), note from the Cayley-Hamilton theorem that \(A^{i}\) for \(i \geq n\) can be written as a linear combination of \(A^{n-1}, \cdots, A, I\), so all the columns of \(R_{\ell}\) for \(\ell \geq n\) are linear combinations of the columns of \(R_{n}\). Thus (22.4) is proved, and the rest of the statement of the theorem follows directly.

    In view of Theorem 22.1, the subspace of states reachable in \(n\) steps, i.e. \(Ra(Rn)\), is referred to as the reachable subspace, and will be denoted simply by \(\mathbb{R}\); any reachable target state, i.e. any state in \(\mathbb{R}\), is reachable in \(n\) steps (or less). The system is termed a reachable system if all of \(\mathbb{R}^{n}\) is reachable, i.e. if \(rank(R_{n}) = n\). The matrix

    \[R_{n}=\left[A^{n-1} B\left|A^{n-2} B\right| \cdots \mid B\right]\label{22.5}\)

    is termed the reachability matrix (often written with its block entries ordered oppositely to the order that we have used here, but this is not significant).

    Example \(\PageIndex{22.1}\)

    Consider the single-input system

    \[\left[\begin{array}{l}
    x_{1}(k+1) \\
    x_{2}(k+1)
    \end{array}\right]=\left[\begin{array}{ll}
    1 & 0 \\
    0 & 1
    \end{array}\right]\left[\begin{array}{l}
    x_{1}(k) \\
    x_{2}(k)
    \end{array}\right]+\left[\begin{array}{l}
    1 \\
    1
    \end{array}\right] u\tag{k}\]

    The reachable subspace is evidently (from symmetry) the line \(x_{1}=x_{2}\). This system is not reachable.

    The following alternative characterization of \(\mathbb{R}_{k}\) is useful, particularly because its CT version will play an important role in our development of the CT reachability story. Let us first define the k-step reachability Gramian \(\mathcal{P}_{k}\) by

    \[\mathcal{P}_{k}=R_{k} R_{k}^{T}=\sum_{i=0}^{k-1} A^{i} B B^{T}\left(A^{T}\right)^{i}\label{22.6}\]

    This matrix is therefore symmetric and positive semi-definite. We then have the following result.

    Lemma \(\PageIndex{22.1}\)

    \[R a\left(\mathcal{P}_{k}\right)=R a\left(R_{k}\right)=\mathbb{R}_{k}\label{22.7}\]

    Proof

    It is easy to see that \(R a\left(\mathcal{P}_{k}\right) \subset R a\left(R_{k}\right)\). For the reverse inclusion, we can equivalently show that

    \[R a^{\perp}\left(\mathcal{P}_{k}\right) \subset R a^{\perp}\left(R_{k}\right)\nonumber\]

    For this, note that

    \[\begin{aligned}
    q^{T} \mathcal{P}_{k}=0 & \Longrightarrow q^{T} \mathcal{P}_{k} q=0 \\
    & \Longleftrightarrow\left\langle R_{k}^{T} q, R_{k}^{T} q\right\rangle=0 \\
    & \Longleftrightarrow q^{T} R_{k}=0
    \end{aligned}\nonumber\]

    so any vector in \(R a^{\perp}\left(\mathcal{P}_{k}\right)\) is also in \(R a^{\perp}\left(R_{k}\right)\).

    Thus the reachable subspace can equivalently be computed as \(Ra(P_{ell})\) for any \(\ell \geq n\). If the system is stable, then \(P_{\infty} := P\) is well defined, and is easily shown to satisfy the Lyapunov equation

    \[A P \Lambda^{T} \quad P=B B^{T}\label{22.8}\]

    We leave you to show that (22.8) has a (unique) positive definite (and hence full rank) solution \(P\) if and only if the system \((A, B)\) is reachable.

    Reachability from an Arbitrary Initial State

    Note from (22.2) that getting from a nonzero starting state \(x(0) = s\) to a target state \(x(k) = d\) requires us to find a \(\mathcal{U}_{k}\) for which

    \[d-A^{k} s=R_{k} \mathcal{U}_{k}\label{22.9}\]

    For arbitrary \(d\), \(s\), the requisite condition is the same as that for reachability from the origin. Thus we can get from an arbitrary initial state to an arbitrary final state if and only if the system is reachable (from the origin); and we can make the transition in \(n\) steps or less, when the transition is possible.

    Controllability versus Reachability

    Now consider what is called the controllability problem, namely that of bringing an arbitrary initial state \(x(0)\) to the origin in a finite number of steps. From (22.2) we see that this requires solving

    \[-A^{k} x(0)=R_{k} \mathcal{U}_{k}\label{22.10}\]

    If \(A\) is invertible and \(x(0)\) is arbitrary, then the left side of (22.10) is arbitrary, so the condition for controllability of \(x(0)\) to the origin in a finite number of steps is precisely that rank\( (R_{k} ) = n\) for some \(k\), i.e. just the reachability condition that \(rank(R_{n}) = n\).

    If, on the other hand, \(A\) is singular (i.e. has eigenvalues at 0), then the left side of (22.10) will be confined to a subspace of the state space, even when \(x(0)\) is unrestricted. The range of \(A_{k}\) for a singular \(A\) may decrease initially, but \(Ra(A^{k} ) = Ra(A^{n} )\) for \(k \geq n\) (since by stage \(n\) the Jordan blocks associated with the zero eigenvalues of \(A\) are all guaranteed to have been \zeroed out" in \(A^{n}\) ). Meanwhile, as we have seen, the range of \(R_{k}\) may increase initially, but \(Ra(R_{k} ) = Ra(R_{n})\) for \(k \geq n\).

    It follows from these facts and (22.10) that an arbitrary initial state is controllable to 0 in finite time, i.e. the system is controllable, iff

    \[R a\left(A^{n}\right) \subset R a\left(R_{n}\right)\label{22.11}\]

    For invertible \(A\), we recover our earlier condition. (The distinction between reachability and controllability is not seen in the CT case, because the state transition matrix there is \(e^{At}\) rather than \(A^{k}\) , and is always invertible.)


    This page titled 22.2: The Reachability Problem is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mohammed Dahleh, Munther A. Dahleh, and George Verghese (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.