Probabilistic Planning Algorithms with Set-Valued Transitions

• Grant number: 08/04728-0
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: July 01, 2008
• End date: June 30, 2009
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: Leliane Nunes de Barros
• Grantee: Renato Schattan Pereira Coelho
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

The automation of the decision making process and planning in the field of ArtificialIntelligence are subjects of great interest in many areas, such as economy, decision analy-sis and logistic. Since problems in these areas usually involve uncertainty, it is common tomodel them as Markov decision processes (MDPs), a model that can represent problems where actions have probabilistic effects. However, in the field of probabilistic planning, the decision making problem considered is to find the shortest stochastic path from a set of initial states to a set of goal states (Shortest Stochastic Path - SSPs). This problem can be seen as an MDP with certain peculiarities that make it easier to solve. In this project we are interested in planning problems under uncertainty where the probabilities are not fully known. Lately it has been proposed a new model called Markov decision processes with set transitions (MDPST). This new model can represent problems with imprecise proba-bilities, such as probability intervals. In this project we want to adapt existent algorithms that solve SSPs, so that they can also solve problems modeled as MDPSTs.