Operator Counting Heuristics for Probabilistic Planning

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. In this paper, we present a generalization of the operator-counting family of heuristics to Stochastic Shortest Path problems (SSPs) that is able to represent the probability of the actions outcomes. Our experiments show that the equivalent of the net change heuristic in this generalized framework obtains significant run time and coverage improvements over other state-of-the-art heuristics in different planners.