Compact Representations of Markov Decision Processes and Their Application to Printer Management
Resumo
Many planning problems can be framed as Markov decision processes (MDPs). In this paper we discuss situations where regularities in states and variables lead to compact MDPs, particularly when variables have many categories and strong interrelation. We develop techniques that generate optimal policies by exploiting regularities in MDPs. We illustrate these ideas with a real problem on management of printing clusters.
Referências
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Boutilier, C., Dean, T., and Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, pages 1–94.
C. Boutilier, N. Friedman, M. G. and Koller, D. (1996). Context-specific independence in bayesian networks. Uncertainty in Artificial Intelligence, pages 115 – 123.
D. Koller, A. P. (1998). Probabilistic frame-based systems. American Association for Artificial Intelligence, pages 580 – 587.
Glesner, S. and Koller, D. (1995). Constructing flexible dynamic belief networks from first-order probalistic knowledge bases. ECSQARU, pages 217–226.
Guestrin, C., Koller, D., Parr, R., and Venkataraman, S. (2003). Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19:399–468.
Littman, M. L., Dean, T. L., and Kaelbling, L. P. (1995). On the complexity of solving Markov decision problems. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, pages 294–402, Montreal, Canada. AUAI.
Littman, M. L. and Younes, H. L. S. (2004). PPDDL1.0: An extension to PDDL for expressing planning domains with probabilistic effects. International Planning Competition.
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Los Angeles, California.
Puterman, M. L. (1994). Markov Decision Process. J. Wiley & Sons, New York. R. Sharma, P. P. (2005). Probabilistic reasoning with hierarchically structured variables. International Joint Conference on Artificial Intelligence.
Boutilier, C., Dean, T., and Hanks, S. (1999). Decision-theoretic planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, pages 1–94.
C. Boutilier, N. Friedman, M. G. and Koller, D. (1996). Context-specific independence in bayesian networks. Uncertainty in Artificial Intelligence, pages 115 – 123.
D. Koller, A. P. (1998). Probabilistic frame-based systems. American Association for Artificial Intelligence, pages 580 – 587.
Glesner, S. and Koller, D. (1995). Constructing flexible dynamic belief networks from first-order probalistic knowledge bases. ECSQARU, pages 217–226.
Guestrin, C., Koller, D., Parr, R., and Venkataraman, S. (2003). Efficient solution algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19:399–468.
Littman, M. L., Dean, T. L., and Kaelbling, L. P. (1995). On the complexity of solving Markov decision problems. In Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, pages 294–402, Montreal, Canada. AUAI.
Littman, M. L. and Younes, H. L. S. (2004). PPDDL1.0: An extension to PDDL for expressing planning domains with probabilistic effects. International Planning Competition.
Pearl, J. (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, Los Angeles, California.
Puterman, M. L. (1994). Markov Decision Process. J. Wiley & Sons, New York. R. Sharma, P. P. (2005). Probabilistic reasoning with hierarchically structured variables. International Joint Conference on Artificial Intelligence.
Publicado
30/06/2007
Como Citar
TORRES, João Vitor; COZMAN, Fabio Gagliardi; RODRIGUES, André.
Compact Representations of Markov Decision Processes and Their Application to Printer Management. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 6. , 2007, Rio de Janeiro/RJ.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 1072-1081.
ISSN 2763-9061.
