Revisiting Goal Probability Analysis in Probabilistic Planning. Steinmetz, M., Hoffmann, J., & Buffet, O. In
Revisiting Goal Probability Analysis in Probabilistic Planning [link]Paper  abstract   bibtex   1 download  
Maximizing goal probability is an important objective in probabilistic planning. But there has been little work towards optimal solvers, presumably due to a lack of heuristic estimators of goal probability, and due to the difficulties entailed by the $0$-reward cycles arising in this setting. Yet, there are relevant probabilistic planning problems, like planning with a limited action-cost budget, whose state spaces are acyclic; and there are relevant weaker objectives, like achieving at least a given goal probability threshold, that allow early termination based on maintaining a pessimistic bound in addition to the usual optimistic bound. We explore the space of algorithmic opportunities arising from these observations. We consider three different objectives, and design suitable termination criteria, search algorithm variants, dead-end pruning methods, and node selection strategies. Our evaluation on more than 1000 benchmark instances from the IPPC, resource-constrained planning, and simulated penetration testing shows the substantial benefits of heuristic search and early termination.
@inproceedings {icaps16-127,
    track    = {​Main Track},
    title    = {Revisiting Goal Probability Analysis in Probabilistic Planning},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13005},
    author   = {Marcel Steinmetz and  Joerg Hoffmann and  Olivier Buffet},
    abstract = {Maximizing goal probability is an important objective in probabilistic planning. But there has been little work towards optimal solvers, presumably due to a lack of heuristic estimators of goal probability, and due to the difficulties entailed by the $0$-reward cycles arising in this setting. Yet, there are relevant probabilistic planning problems, like planning with a limited action-cost budget, whose state spaces are acyclic; and there are relevant weaker objectives, like achieving at least a given goal probability threshold, that allow early termination based on maintaining a pessimistic bound in addition to the usual optimistic bound. We explore the space of algorithmic opportunities arising from these observations. We consider three different objectives, and design suitable termination criteria, search algorithm variants, dead-end pruning methods, and node selection strategies. Our evaluation on more than 1000 benchmark instances from the IPPC, resource-constrained planning, and simulated penetration testing shows the substantial benefits of heuristic search and early termination.},
    keywords = {Classical planning,Probabilistic planning; MDPs and POMDPs,Search techniques}
}
Downloads: 1