Planning Graph Heuristics for Belief Space Search
Planning Graph Heuristics for Belief Space Search
复制标题
DOI：
10.1613/jair.1869
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
D. Bryce;S. Kambhampati;David E. Smith
中科院分区：
文献类型：
--
作者：
D. Bryce;S. Kambhampati;David E. Smith
最近的一些条件规划工作提出了可达性启发式方法来提高规划器的可扩展性，但许多工作缺乏对其距离估计属性的正式描述。为了将以前的工作置于上下文中并扩展条件规划启发式的工作，我们为信念状态之间的距离估计提供了正式的基础。我们给出了信念状态之间的距离的定义，该定义依赖于聚合底层状态距离度量。我们提供了几种聚合状态距离及其相关属性的技术。许多现有的启发式方法都展示了属性的子集，但为了提供标准化比较，我们提出了在单个规划器中使用的规划图启发式的几种概括。我们还通过研究有效的规划图数据结构来补充我们的信念状态距离估计框架，这些数据结构结合了 BDD 来计算最有效的启发式方法。我们开发了两个规划器作为我们调查的测试平台。第一个是 CAltAlt，是使用 A* 搜索的一致性回归规划器。第二个 POND 是一个使用 AO* 搜索的条件进展规划器。我们展示了我们的启发式技术在这些规划器中的相对有效性。我们还将这些规划器的性能与条件规划中的几种最先进的方法进行了比较。
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.