期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2006
卷号：26
页码：35-99
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：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
