Markov decision processes with imprecise probabilities and relational representations: foundations and algorithms.

Author(s)

Ricardo Shirota Filho

• Document type: Doctoral Thesis
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Escola Politécnica (EP/BC)
• Defense date: 2012-05-03

Examining board members

Fabio Gagliardi Cozman; Leliane Nunes de Barros; Jaime Shinsuke Ide; Kate Cerqueira Revoredo; Renata Wassermann

• Advisor: Fabio Gagliardi Cozman

Abstract

This work is devoted to the theoretical and algorithmic development of Markov Decision Processes with Imprecise Probabilities and relational representations. In the literature, this configuration is important within artificial intelligence planning, where the use of relational representations allow compact representations and imprecise probabilities result in a more general form of uncertainty. There are three main contributions. First, we present a brief discussion of the foundations of decision making with imprecise probabilities, pointing towards key questions that remain unanswered. These results have direct influence upon the model discussed within this text, that is, Markov Decision Processes with Imprecise Probabilities. Second, we propose three algorithms for Markov Decision Processes with Imprecise Probabilities based on mathematical programming. And third, we develop ideas proposed by Trevizan, Cozman e de Barros (2008) on the use of variants of Real-Time Dynamic Programming to solve problems of probabilistic planning described by an extension of the Probabilistic Planning Domain Definition Language (PPDDL). (AU)