ITSAT: An Efficient SAT-Based Temporal Planner
ITSAT: An Efficient SAT-Based Temporal Planner
复制标题
ITSAT：基于 SAT 的高效时间规划器
DOI：
--
复制
发表时间：
2015
影响因子：
5
通讯作者：
Gholamreza Ghassem
中科院分区：
文献类型：
--
作者：
Masood Feyzbakhsh Rankooh;Gholamreza Ghassem
作为可满足性的规划被认为是处理多种规划问题的有效方法。然而，在时间规划方面，这种方法还不能与基于状态空间的方法相竞争。本文将ITSAT描述为一个有效的基于sat（基于满意度）的时间规划器，能够进行时间表达规划。ITSAT的新颖之处在于它处理给定问题的时间约束的方式，而不涉及在相应的可满足性问题中引入连续变量的困难。我们还展示了在基于sat的经典规划中，精心设计的预处理和编码模式如何显著提高基于sat的时间规划的效率。提出了互斥关系提取和动作压缩两种预处理方法。我们还展示了因果推理和时间推理的分离使我们能够采用基于并行执行语义概念的紧凑编码。虽然这样的编码在经典规划中已经被证明是相当有效的，但ITSAT是第一个利用这种编码类型的时间规划器。我们的实证结果表明，ITSAT不仅优于最先进的时间表达规划器，而且还与无法处理所需并发性的快速时间规划器竞争。
Planning as satisfiability is known as an efficient approach to deal with many types of planning problems. However, this approach has not been competitive with the state-space based methods in temporal planning. This paper describes ITSAT as an efficient SAT-based (satisfiability based) temporal planner capable of temporally expressive planning. The novelty of ITSAT lies in the way it handles temporal constraints of given problems without getting involved in the difficulties of introducing continuous variables into the corresponding satisfiability problems. We also show how, as in SAT-based classical planning, carefully devised preprocessing and encoding schemata can considerably improve the efficiency of SAT-based temporal planning. We present two preprocessing methods for mutex relation extraction and action compression. We also show that the separation of causal and temporal reasoning enables us to employ compact encodings that are based on the concept of parallel execution semantics. Although such encodings have been shown to be quite effective in classical planning, ITSAT is the first temporal planner utilizing this type of encoding. Our empirical results show that not only does ITSAT outperform the state-of-the-art temporally expressive planners, it is also competitive with the fast temporal planners that cannot handle required concurrency.
将推理在时间规划中的使用扩展为前向搜索
DOI：
--
发表时间：
2009
期刊：
--
影响因子：
--
作者：
Coles, A.J
通讯作者：
Coles, A.J