基于因果图的一致性规划研究

智能规划是人工智能研究的一个重要领域，实现高效的规划求解是智能规划追求的主要目标之一。一致性规划作为一种不确定规划，是指初态和状态转换中的信息都是不完备的规划任务，在初始状态和动作效果都不确定的情况下，在没有感知动作的帮助下，生成规划任务的解。本项目拟针对一致性规划中的两个主要问题：紧凑的信念表示方式和获得有效的启发式信息进行研究，并将基于多值表示的因果图分解规划求解方案引入到一致性规划中，扩展一致性规划的表示能力，为一致性规划的求解提供高效的计算理论与方法。主要研究内容包括PPDDL一致性规划任务的有限域转换方法、基于路标的启发式搜索策略、基于因果图的一致性规划求解方法等，以实现高效的一致性规划问题的求解。

智能规划是人工智能的一个重要分支，一致性规划作为一种不确定规划，是指初态和状态转换中的信息都是不完备的规划任务。纯粹的一致性规划问题很少存在于实际情况中，而是作为可观察规划的特例来求解这类规划问题。大部分当前的一致性规划器都是基于信念空间的，本项目针对一致性规划中的两个主要问题：紧凑的信念表示方式和获得有效的启发式信息进行研究，主要目的在于扩展一致性规划的表示能力，为一致性规划的求解提供高效的计算理论与方法。.本项目将经典规划中的FDR转化方法扩展到一致性规划问题中，提出了CPT-FDR转化方法。分别扩展了PPDDL表示的一致性规划任务和有限域表示的一致性规划任务的定义，扩展了非确定效果、变数、信念操作等相关语义。实验效果表明生成的CPT-FDR与PPDDL任务相比，节省了存储空间，有效地减小了信念状态空间；能成功地转化大部分的标准一致性规划域问题。.为了去除一致性规划状态空间中的冗余，本项目研究了有限域转换算法的四个阶段，以积木问题为例说明状态变量的生成过程。最后提出压缩状态空间方法。分析有限域状态变量中被编码的文字，将冗余文字分为三种：无效文字、负文字和无用文字。实例化原子算法用于去除无效文字，有用文字算法和oneof算法用于转换负文字，域值约简算法用于去除无用文字。这些算法都是通过减少状态变量编码的文字个数来达到减少状态空间的目的。实验效果表明我们提出的算法无论在时间还是空间性能方面都有效地压缩一致性规划领域状态空间。.GBFS在启发式搜索中表现出良好的性能，但容易陷入局部最优状态。针对这一问题，本项目通过增加选择节点的多样性和动态选取参考节点的方法，提出一种改进算法IBFS，该算法在LAMA规划器上通过利用路标作为伪启发式指导搜索，采用2008国际规划大赛标准问题和领域进行实验，结果表明，该算法能够有效地减少扩展的状态节点数，并降低搜索开销。