Research on an Integrated System for Fast SAT Planning

SAT规划是一种快速规划方法，它将规划问题转化为可满足性问题，并利用快速求解器对可满足性问题进行求解，从而提取出计划。在本研究中，我们开发了一个集成的动作语言处理系统AMP，用于对动作语言描述的领域描述进行快速的SAT规划。我们已经开发了几种算法来将动作语言中描述的领域描述转换为SAT问题。特别是，我们考虑了一种将涉及不确定性行为的规划问题转换为SAT问题的算法。我们在AMP中实现了几个规划引擎。使用规划图作为数据结构，我们开发了向前/向后/混合图扩展算法，以尽可能快地执行规划。我们还设计了我们的系统，为SAT计划提供多个SAT求解器。根据问题的特点，一些SAT解题者比其他人表现得更好。我们已经考虑了加速规划的学习算法。给定在执行动作序列后描述流畅值的观察结果，学习算法推导出动作及其效果之间的因果关系。AMP已经在Java中实现，并且能够绘制用于交互使用的规划图。大型基准问题的实验结果表明，AMP的性能可与世界上最快的规划器之一相媲美。然而，与以前的系统不同，AMP可以直接用动作语言解释描述，并且不仅可以有效地回答计划查询，还可以有效地生成模型。

SAT planning is a fast planning method which converts a planning problem into a satisfiability (SAT) problem and extracts a plan by solving the SAT problem using a fast SAT solver. In this research, we have developed an integrated action language processing system AMP to perform fast SAT planning on domain descriptions described in action languages : The contributions of the research can be summerized as follows.1. We have developed several algorithms to convert domain descriptions described in action languages into SAT problems. In particular, we have considered an algorithm which transforms planning problems involving nondeterministic actions into SAT problems.2. We have implemented several planning engines in AMP. Using planning graphs as data structures, we have developed forward/backward/mixed graph expansion algorithms to perform planning as fast as possible. We have also designed our system to have multiple SAT solvers for SAT planning. Depending on the feature of a problem, some SAT solvers perform better than others.3. We have considered learning algorithms for speed-up planning. Given observations that describe fluent values after performing action sequences, learning algorithms induce causal relationships between actions and their effects.4. AMP has been implemented in Java, and has an ability to draw planning graphs for interactive uses. Experimental results with big benchmark problems show that the performance of AMP is comparable to one of the fastest planner in the world. Unlike previous systems, however, AMP can interpret a description in an action language directly, and can answer queries for not only planning but model generation efficiently.