Generalizing GraphPlan by Formulating Planning as a CSP
Generalizing GraphPlan by Formulating Planning as a CSP
复制标题
通过将规划制定为 CSP 来推广 GraphPlan
DOI：
--
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
F. Bacchus
中科院分区：
文献类型：
--
作者：
Adriana Lopez;F. Bacchus
我们研究的编码规划问题的CSPs更密切的方法。首先，我们提出了一个简单的CSP编码规划问题，然后一组转换，可用于消除变量和添加新的约束的编码。我们表明，我们的转换发现额外的结构在规划问题，结构，包含的结构发现的GRAPHOTOGRAPHIC规划图。我们使用标准的CSP算法解决CSP编码规划问题。实证证据验证这种方法来解决规划问题的有效性，并表明，即使是一个原型的实施是更有效的比标准的GRAPHOLOGY。我们的原型甚至具有更优化的基于规划图的实现的竞争力。我们还证明，这种方法比规划图更容易应用于更复杂的规划类型。特别是，我们表明，该方法可以很容易地扩展到规划资源。
We examine the approach of encoding planning problems as CSPs more closely. First we present a simple CSP encoding for planning problems and then a set of transformations that can be used to eliminate variables and add new constraints to the encoding. We show that our transformations uncover additional structure in the planning problem, structure that subsumes the structure uncovered by GRAPHPLAN planning graphs. We solve the CSP encoded planning problem by using standard CSP algorithms. Empirical evidence is presented to validate the effectiveness of this approach to solving planning problems, and to show that even a prototype implementation is more effective than standard GRAPHPLAN. Our prototype is even competitive with far more optimized planning graph based implementations. We also demonstrate that this approach can be more easily lifted to more complex types of planning than can planning graphs. In particular, we show that the approach can be easily extended to planning with resources.