| Texto completo | |
| Autor(es): |
Fernandez, Milton Condori
;
de Barros, Leliane Nunes
;
Delgado, Karina Valdivia
;
IEEE
Número total de Autores: 4
|
| Tipo de documento: | Artigo Científico |
| Fonte: | 2018 7TH BRAZILIAN CONFERENCE ON INTELLIGENT SYSTEMS (BRACIS); v. N/A, p. 6-pg., 2018-01-01. |
| Resumo | |
The most efficient approach to solve probabilistic planning problems is based on stochastic shortest path (SSP) and uses heuristic search to find a policy that minimizes the expected accumulated cost to the goal (MINCOST criterion). However, this approach can solve problems with dead ends (states from which it is not possible to reach the goal) only if an efficient dead end detection heuristic is used. Another solution would be to plan in two phases: maximizing the probability to reach the goal (MAXPROB) and then minimizing the expected cost (MINCOST). While there exist several heuristics to solve MINCOST, there are not known efficient heuristics to solve MAXPROB. A recent work proposes the first heuristic that takes into account the probabilities, called h(pom), which solves a relaxed version of an SSP as a linear program in the dual space. However, to solve large problems with dead ends, h(pom) must be augmented with a dead end detection heuristic (e.g., h(pom) & h(max)). In this work, we propose two new heuristics based on hpom. The first, h(pom)(pe)(s), estimates the minimal cost to reach the goal from state s, including new variables and constraints for dead ends states and adding an expected penalty for reaching them. The second, h(ppom)(s), estimates the maximum probability to reach the goal from s, and is used to solve MAXPROB problems by ignoring action costs. We claim that h(ppom)(s) is the first heuristic for MAXPROB. Empirical results show that h(pom)(pe) can solve larger planning instances when compared to h(pom)&h(max). (AU) | |
| Processo FAPESP: | 15/01587-0 - Armazenagem, modelagem e análise de sistemas dinâmicos para aplicações em e-Science |
| Beneficiário: | João Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Programa eScience e Data Science - Temático |