论文部分内容阅读
PDDL公理的研究与应用推理重新成为目前智能规划研究领域的热点。派生谓词是PDDL2.2语言的新特性之一,派生规划问题是最新的将逻辑推理融合到规划求解技术中的规划问题。如何推导动作前提中的派生谓词和处理动作效果对派生谓词的间接影响,是派生规划问题中的两个关键问题。
激活集是指使得派生谓词的实例在当前状态下成立的一组由基本谓词的实例所构成的集合。基于LPG-td规划系统的已有工作,本文定义了与状态无关的激活集(简称为SIAS)。SIAS完全由规则集推导出来,即当当前状态发生变化时,不需要在规则图上重新计算新的激活集。这使得在提取动作解的过程中,避免了对派生谓词的激活集的重复计算,从而减少了总的规划求解时间。本文提出了在规则图上计算与状态无关的激活集的SIAS-search算法,以及将与状态无关的激活集应用到启发式估值的DP-relax-plan算法。
基规则集是指用规划问题所包含的实体进行实例化的领域理论。规则图是基于基规则集建立的与或图,事实节点是与节点,规则节点是或节点。当规划问题所包含的实体个数增多,规则图的规模呈指数增长。在这样庞大的规则图上,即使计算与状态无关的激活集也是很耗费时间的。为此,尽量避免在规则图上计算激活集。根据派生谓词的语义,派生事实的激活集集合可以证明是该派生事实的一个析取范式。用这样的析取范式在基规则集中进行推导,使得基规则集包含更多的基本谓词,可以推导出其它的派生谓词的与状态无关的激活集。这个过程称为规则集的基化过程,它使得规则集发生等价变换而不改变原有规划问题的性质。基于这些改进方法,我们提出了求解派生谓词的激活集的总体框架,并且实现了一个规划系统LPGSIAS。实验结果表明,该系统能够更高效地求解派生规划问题。