摘要:对智能规划中的常用工具——放松式规划图(relaxed planning graph,简称RPG)的图论性质进行了深入研究.将RPG 中的命题层抽取出来,得到一个不包含任何动作的命题关系图(proposition relation graph,简称PRG),发现PRG 仍具有RPG 的主要规划性质.初步研究结果包括以下4 个方面:初始命题集(initial proposition set,简称IPS)的闭出邻集(close out-neighborhoods,简称CON)是放松式规划可达命题集(relaxed reachable proposition set,简称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 的结点数).