权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Research on an Integrated System for Fast SAT Planning

快速SAT规划综合系统研究

基本信息

批准号：
12680384
负责人：
INOUE Katsumi
金额：
$ 2.05万
依托单位：
Kobe University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

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.

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