智能规划(AI planning)传统人工智能最古老的研究领域之一。近年来,以启发式搜索,命题自动推理为代表的新规划技术的出现大大改进了传统规划方法的效率,使得智能规划重新成为人工智能的研究热点之一。在过去十多年间,删除放宽和landmark等启发式函数设计方法吸引了国内外研究者的关注,并有了众多的研究成果。但大多数研究都是针对满足规划和非可纳启发式函数展开的,本文围绕如何设计高效准确的可纳启发式函数以提高最优规划的效率来展开研究。本文的研究内容主要有三个方面,首先,研究了存在多个可纳启发式函数的情况下,如何利用惰性启发式函数评估来减少A*算法计算代价较大的启发式函数的计算时间。其次,研究了利用MAXSAT编码来计算最优删除放宽启发式函数h+,试图通过通用的命题推理技术来计算规划问题的启发式函数。最后对多值landmark规划方法进行了研究,通过将landmark扩展成多值landmark,使得可以对基数约束进行建模,从而可以设计出比删除放宽更准确的可纳启发式函数。具体来说,研究内容如下：1.在给定一个可纳启发式函数的情况下,传统的A*算法扩展的节点数是所有搜索算法中最少的。但在存在两个或多个可纳启发式函数时,单纯对启发式函数取最大值的方法效率低下。本文提出了针对A*算法的惰性启发式函数评估技术,在不增加扩展节点数的情况下,减少了计算代价较高的启发式函数的计算时间,从而提高了搜索过程的效率,使得在A*算法中利用计算代价较大的启发式函数成为可能。2.针对现有最优删除放宽规划近似方法的不足,我们提出了一种新的MAXSAT编码方法,利用约束生成的方法产生一系列渐进逼近h+的下界,并最终计算出h+的精确值。同时基于一种特殊的MAXSAT解法,指出了MAXSAT编码的不可满足核是放宽规划任务的动作1andmark,该联系使我们可以利用LM-cut等其他规划方法产生的landmark来加速我们MAXSAT实例的计算,并保证MAXSAT所计算的启发式函数在准确性上优于LM-cut函数。3.针对传统landmark建模基数约束的不足,提出了基于多值landmark的规划方法,从理论上证明了多值landmark相比传统landmark和删除放宽等方法能更准确的近似最优启发式函数h*。同时,本文定义了规则转移命题的概念,给出了该类命题和多值landmark之间的联系,基于该联系设计了基于线性规划的多值1mdmark启发式函数hLPML,hLPML满足可纳性。在标准规划问题集上的实验表明相比传统的landmark启发式函数,hLPML的准确性更高,且在相同时间内能解决更多的规划任务。