Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting
arXiv:1111.0044 · doi:10.1613/jair.2289
Abstract
We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-search machinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FFs 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.
References in corpus (3)
Cited by in corpus (18)
- Hyper-optimized tensor network contraction
- Planning with Noisy Probabilistic Relational Rules
- Synthesizing Robust Plans under Incomplete Domain Models
- A Scalable Approximate Model Counter
- Sampling Techniques for Boolean Satisfiability
- Constrained Counting and Sampling: Bridging the Gap between Theory and Practice
- Automated Attack Planning
- On Hashing-Based Approaches to Approximate DNF-Counting
- Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
- Exploiting Database Management Systems and Treewidth for Counting
- Learning Branching Heuristics for Propositional Model Counting
- The Model Counting Competition 2020
- Counting Answer Sets via Dynamic Programming
- Probabilistic Planning by Probabilistic Programming
- Lifted Algorithms for Symmetric Weighted First-Order Model Sampling
- Exploiting Treewidth for Projected Model Counting and its Limits
- Phase Transition Behavior of Cardinality and XOR Constraints
- A New Probabilistic Algorithm for Approximate Model Counting