Bounded Aggregation Techniques to Solve Large Markov Models
Daly, David M.
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/80902
Description
Title
Bounded Aggregation Techniques to Solve Large Markov Models
Author(s)
Daly, David M.
Issue Date
2005
Doctoral Committee Chair(s)
Sanders, William H.
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
"Markovian modeling of systems is a promising technique used to gauge the performance, dependability, and performability of systems. It can be used to aid design decisions by evaluating a range of design options for a range of environments, and it can be used to increase understanding of operational systems. Unfortunately, Markovian modeling is limited by the ""state-space explosion,"" or the exponential growth of the state space of a Markovian model as detail is added to the model. It is our thesis that aggregation techniques can be used to solve, at an acceptable level of accuracy, Markovian models that are more than an order of magnitude more complex than models solvable by current techniques, and that the aggregation techniques can be automated in many cases. We prove that claim by extending existing aggregation techniques to develop a new partial order that we apply to the solution of large models. In the partial order, if one state is larger than another state then all of the reward variables will be greater for all instants and intervals of time if the model starts in the first state instead of the second state. We show how the partial order can be computed, how it can be used to generate aggregates and compare aggregates to an original model, and how it can be applied to compositionally defined models. We then use the developed aggregation techniques to solve models that would be infeasible to solve otherwise."
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
