Files in this item
Files  Description  Format 

application/pdf Kun_Deng.pdf (3MB)  (no description provided) 
Description
Title:  Model reduction of Markov chains with applications to building systems 
Author(s):  Deng, Kun 
Director of Research:  Mehta, Prashant G. 
Doctoral Committee Chair(s):  Mehta, Prashant G. 
Doctoral Committee Member(s):  Meyn, Sean P.; Beck, Carolyn L.; Dullerud, Geir E.; Salapaka, Srinivasa M. 
Department / Program:  Mechanical Sci & Engineering 
Discipline:  Mechanical Engineering 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Model Reduction
Markov Chain Hidden Markov Model Building System Information Theory Control System 
Abstract:  Markov chain serves as an important modeling framework in applied science and engineering. e.g., Markov Chain Monte Carlo methods and Markov Decision Processes. A fundamental problem of Markov chain models is that the dimension of the problem could be very large in practice. This causes immense difficulties in manipulation and analysis of Markov chain models. Hence, the model reduction of Markov chains is an important problem that is relevant to many applications. In the first part of this thesis, the model reduction problem of Markov chains is studied and investigated. An information theoretic method is proposed to reduce Markov chains via the aggregation of states. The KullbackLeibler (KL) divergence rate, a commonly used pseudo metric in statistics and information theory, is employed to measure the differences between two Markov chains. The proposed framework reveals a connection to the spectral properties of Markov chains. In particular, the significance of the second eigenvector is explained in information theoretic terms for the first time. This result leads to a practical recursive modelreduction algorithm based on spectral analysis, and a limited set of error bounds for the model reduction of Markov chains. Besides using the spectral method, a simulationbased method is also proposed to perform state aggregation of the Markov chain. The main idea is to recast the model reduction problem as an infinitehorizon average cost optimal control problem. An optimal policy corresponds to an optimal aggregation of the state space. The optimal control problem is simplified in an approximate dynamic programming (ADP) approach. A relaxation of the policy space is performed, and based on this a parameterization of the set of optimal policies is introduced. This makes possible a stochastic approximation approach to compute the best policy within a given parameterized class. Convergence of stochastic approximation approach is established using the ODE method. The aggregationbased model reduction method of Markov chains is extended to hidden Markov models (HMM), which is a special Markov chain model with unobserved state process. Similarly, the state space is aggregated or partitioned to reduce the complexity of the HMM. The optimal aggregation is obtained by minimizing the KL divergence rate between the laws of the observation process. The optimal aggregated HMM is given as a function of the partition function of the state space. The optimal partition is obtained by using a recursive stochastic approximation learning algorithm, which can be implemented through a single sample path of the HMM. Convergence of the algorithm is established using ergodicity of the filtering process and standard stochastic approximation arguments. In the second part of this thesis, the modeling and control problems of building systems are investigated. Firstly, A nonlinear resistorcapacitor (RC) network model of a multizone building is established to capture the building thermal dynamics. Then an aggregationbased model reduction method is proposed to preserve the structure of the buildingthermal model, that is, the reduced building thermal model is still a nonlinear RCnetwork. This is achieved by obtaining supernodes via aggregation, and determining the supercapacitance for each supernode and super resistance for each edge between two adjacent supernodes. The aggregationbased approach proposed here is based on model reduction method of Markov chains that was described in the first part of this thesis. The main idea is to connect the linear portion of the multizone thermal model to a continuoustime Markov chain, and extend the model reduction framework for Markov chains to the nonlinear fullorder building thermal model. A decentralized optimal control strategy is also proposed for a multizone building in the second part, where model complexity is mitigated by using a two pronged approach. First, we use the aggregationbased model reduction technique introduced in this part to construct a reducedorder model of the multizone building’s thermal dynamics. Second, we use the meanfield intuition from statistical mechanics so that the effect of other zones on a particular zone is captured though a meanfield model. Then the whole model does not have to be used in computing the controls over short time scales. A local optimal zonal control law is designed based on the local model of thermal dynamics, and its interaction with the building via the meanfield. The methodology is shown to yield distributed control laws that can be easily implemented on largescale problems. In the third part of this thesis, the modeling, analysis, and control of occupancy evolution in a large building are studied. The main concern is efficient evacuation of a building in the event of emergency. Complexity arises due to building topology, uncertainty regarding the distribution of occupants, and the uncertain behavior of occupants. The relaxation techniques borrowed from queueing theory is employed to address complexity issues. These techniques are used to model occupancy evolution during evacuation, obtain lower bounds on evacuation time, and construct control policies to instruct occupants in order to efficiently evacuate the building. The control solutions are based on recent generalizations of the MaxWeight policy for decentralized routing. These results are illustrated with the aid of simulations using realistic building models. 
Issue Date:  20130203 
URI:  http://hdl.handle.net/2142/42225 
Rights Information:  Copyright 2012 Kun Deng 
Date Available in IDEALS:  20130203 
Date Deposited:  201212 
This item appears in the following Collection(s)

Dissertations and Theses  Mechanical Science and Engineering

Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois