UC San Diego

This thesis formulates versions of observability, reconstructibility, controllability, and reachability for stochastic linear and nonlinear systems. The concepts of observability and reconstructibility concern whether the measurements of a system suffice to construct a complete characterization of the system behavior while the concepts of controllability and reachability concern whether the actuation of the system suffices to cause the system to behave according to various user specifications. Thus, these concepts are fundamental to the design of control algorithms. In deterministic linear systems, linear algebraic conditions specify whether an unknown state can be exactly reconstructed from the measurements over a finite time interval, and whether there exists an input sequence over a finite time interval which can steer the state to a desired endpoint; thus, the concepts of observability, reconstructibility, controllability, and reachability are straightforwardly defined. The extension to linear stochastic systems is not obvious. While the deterministic matrix conditions have significance in applications such as Kalman filtering and linear-quadratic -optimal control, the presence of noise generally prevents exact reconstruction of the state via the measurements and exact placement of the state via the control inputs. This ambiguity in interpreting the matrix conditions has lead to a multitude of extensions in the literature. Nonlinear behavior introduces further difficulties; even in nonlinear deterministic systems, the generalization of the linear conditions is not immediate; for instance, whereas observability and reconstructibility does not depend on the control input in linear systems, this separation of control and estimation questions need not hold for nonlinear systems. Our purpose is to make precise the stochastic versions of observability, reconstructibility, controllability, and reachability; in the process, we obtain the expected matrix conditions for stochastic linear systems, which arise both in deterministic linear systems analysis and in Kalman filtering theory and linear -quadratic-optimal-control theory. Perhaps unexpectedly, we also obtain an analogous rank condition for the finite- state hidden Markov model. We show important roles of reconstructibility: in linear systems, it corresponds to minimality of the Kalman filter; in nonlinear systems, it is necessary for performance improvement via output feedback over open-loop control. The role of observability in the stability of optimal filters is discussed. Additionally, we demonstrate a connection between stochastic controllability/reachability and Granger causality and its generalizations from the statistics and econometrics literature. The ideas are explored via simulation of a finite-state hidden Markov model for the network congestion control problem