Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting
Abstract
We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-searchmachinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FF's techniques with a powerful machinery for weighted model counting in (weighted) CNFs, serving to elegantly define both the search space and the heuristic function. Our evaluation of Probabilistic-FF shows its fine scalability in a range of probabilistic domains, constituting a several orders of magnitude improvement over previous results in this area. We use a problematic case to point out the main open issue to be addressed by further research.
Cite
Text
Domshlak and Hoffmann. "Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting." Journal of Artificial Intelligence Research, 2007. doi:10.1613/JAIR.2289Markdown
[Domshlak and Hoffmann. "Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting." Journal of Artificial Intelligence Research, 2007.](https://mlanthology.org/jair/2007/domshlak2007jair-probabilistic/) doi:10.1613/JAIR.2289BibTeX
@article{domshlak2007jair-probabilistic,
title = {{Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting}},
author = {Domshlak, Carmel and Hoffmann, Jörg},
journal = {Journal of Artificial Intelligence Research},
year = {2007},
pages = {565-620},
doi = {10.1613/JAIR.2289},
volume = {30},
url = {https://mlanthology.org/jair/2007/domshlak2007jair-probabilistic/}
}