规划是指在给定的初始条件下,求得一个动作序列使得依次执行此动作序列可以达到规定的目标。规划是人工智能领域的经典问题之一,在过去十多年中,规划领域取得较大突破。现代规划系统无论在求解效率上还是在求解问题的规模上都有数量级的提高。多值规划是近五年来智能规划领域的研究热点,它掀起了继图规划之后的又一研究热潮。与以往的规划表示不同,多值规划采用一个多值变量来表示规划的多个命题组成的集合。知识表示的区别使得多值规划的动作模型区别于经典规划的动作模型。多值规划给规划求解模式带来了新颖的结构表示方法、求解策略和启发式函数。本文深入研究了多值规划框架下知识表示应用和启发式搜索等问题,主要研究结果和创新点如下:(1)将多值规划的知识表示应用于一致性规划。多值变量是通过规划任务中的常量来进行编码的。多值规划的多值变量表示比经典规划的布尔变量表示更紧凑,适合表示搜索空间很大的规划任务,有利于提高多种规划系统的求解速度。鉴于多值变量具有压缩状态编码的性质,本文通过将多值变量引入一致性规划,求解时空复杂度较高的一致性规划问题。一致性规划取消了一些经典规划中不现实的基本假设,考虑具有非确定性动作和部分描述的初始状态,使得一致性规划的状态空间规模较经典规划的状态空间的规模有指数倍增长。本文通过识别在一致性规划当中任意时间步不同时为真的命题集合,形式化定义了一致性规划中的常量,提出了一致性常量合成算法。该算法首先将所有受动作影响的谓词作为备选一致性常量,然后在初始状态和动作中验证备选常量是否符合一致性规划中常量的真值要求,修改未通过验证的备选常量,抛弃不能修改的备选常量,对修改后的备选常量再进行验证。定义了多值一致性规划任务及其动作模型,给出转换多值一致性规划任务的方法,把多值一致性规划任务与规划解重用启发式结合求解一致性规划。理论分析和实验表明本文提出的一致性常量合成算法能够合成出正确的一致性规划问题中的常量,生成多值一致性规划任务。与一致性规划通常采用的布尔编码相比,多值一致性状态编码能压缩大量存储空间。为验证多值一致性状态编码的应用效果,本文把多值一致性规划任务与规划解重用启发式结合进行求解。结合求解方法在GRID域性能优于一致性规划系统CFF,有较好的应用价值。(2)提出了动作路标提取方法。在不同的规划系统架构下,路标显示出加速规划解生成的优秀特性。路标在不同规划系统中承担的角色和发挥的作用是不同的,如前提排序、搜索方向建议、启发函数估计等。其中最具有代表性的应用方法是启发式函数。路标的种类很多,有命题路标、析取命题路标、合取命题路标、动作路标等。其中,动作路标作为启发式函数估计的应用效果显著。基于动作路标的启发式函数的性能主要取决于动作路标的质量和生成速度。本文提出了动作路标提取算法,该算法既不需要循环构建规划图,也不需要通过可达性测试来不断地验证动作路标的存在,通过建立两个提取规则从规划任务的命题路标关系图中提取动作路标。该算法能一次生成构建命题路标关系图,并提取全部动作路标。从理论上证明了提取规则的正确性。理论分析和对比实验表明本文提出的动作路标提取算法比基于放松规划图的动作路标验证算法具有更高的效率,且其复杂性不随问题规模快速增长。(3)构建了具有可纳性的基于命题路标的启发式函数。基于各种路标的启发式是当前启发式函数设计的趋势。命题路标是可直观提取的路标,是其他各类路标的基础。将当前状态下未到达命题路标的个数,作为当前状态下启发式函数的估计值是命题路标计数启发式的基本思想。命题路标计数启发式改善了规划成功率和规划解长度,但不能保证求解出最优解。原因在于未到达的命题路标数量有时大于真正需要执行的动作数量。本文深入分析了命题路标计数启发式函数不可纳的原因及各种基于命题路标启发式函数的优劣,定义了命题路标的对应动作,并提出使用未到达命题路标的对应动作数量作为加强命题路标计数启发式函数的估计值,从理论上给出加强命题路标计数启发式函数可纳性的证明。与目前有代表性的路标计数启发式的对比实验表明,加强路标计数启发式在求解动作带有强约束的问题时具有更好的性能。综上所述,本文针对多值规划领域的主要问题:知识表示应用,动作路标提取,启发式函数建立等进行了深入研究,利用多值规划知识表示的特性,把多值规划任务引入到一致性规划当中,应用多值一致性规划任务求解,取得了良好效果。针对多值规划特有的知识表示结构,给出了更加高效的动作路标提取方法。针对多值规划下的命题路标启发式,给出了具有可纳性的基于命题路标的启发式函数。本文的研究结果很有理论意义及应用价值,为多值规划研究提供了有益的借鉴和参考。