利用规划命题关系图构建目标议程和宏动作

对智能规划中的常用工具——放松式规划图(relaxedplanninggraph,简称rpg)的图论性质进行了深入研究.将rpg中的命题层抽取出来,得到一个不包含任何动作的命题关系图(propositionrelationgraph,简称prg),发现prg仍具有rpg的主要规划性质.初步研究结果包括以下4个方面:初始命题集(initialpropositionset,简称ips)的闭出邻集(closeout-neighborhoods,简称con)是放松式规划可达命题集(relaxedreachablepropositionset,简称r-rps);初始状态命题到目标状态命题的最大距离是规划解长度的合理估计;无圈序指出了对应命题被实现的顺序要求;出度或入度为1的结点收缩对应规划中构造的宏动作.上述结果中,前两者说明prg保留rpg的主要规划性质,后两者可用于建立目标议程或宏动作提取等领域.还提出与上述结论相关的3种算法:从rpg中得到prg的算法(复杂性为o(mn2),其中,n为rpg的命题数,m为rpg的动作数);约简无圈序算法(复杂性为o(n+m),其中,n为prg的结点数,m为prg的边数);宏动作建议算法(复杂性为o(n2),n为prg的结点数).