Some recent works in conditional planning have proposed reachability
heuristics to improve planner scalability, but many lack a formal description
of the properties of their distance estimates. To place previous work in
context and extend work on heuristics for conditional planning, we provide a
formal basis for distance estimates between belief states. We give a definition
for the distance between belief states that relies on aggregating underlying
state distance measures. We give several techniques to aggregate state
distances and their associated properties. Many existing heuristics exhibit a
subset of the properties, but in order to provide a standardized comparison we
present several generalizations of planning graph heuristics that are used in a
single planner. We compliment our belief state distance estimate framework by
also investigating efficient planning graph data structures that incorporate
BDDs to compute the most effective heuristics.
We developed two planners to serve as test-beds for our investigation. The
first, CAltAlt, is a conformant regression planner that uses A* search. The
second, POND, is a conditional progression planner that uses AO* search. We
show the relative effectiveness of our heuristic techniques within these
planners. We also compare the performance of these planners with several state
of the art approaches in conditional planning.

提供了一种基于状态距离测量的置信状态距离估计框架，利用聚合状态距离度量的方法来定义置信状态之间的距离，实现了一些技术来聚合状态距离及其关联属性，提出了几种规划图启发式方法的广义形式，利用 BDD 来计算最有效的技巧，这些启发式方法在两个规划器上得到了有效应用。