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

• 作者: 姜云飞 朱慧泉 蒋志华 饶东宁
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 智能规划 放松式规划图 命题关系图 目标议程 宏动作
• 年，卷（期）: 2011,（1）
• 页码范围: 44-56
• 分类号: TP181
• 字数: 10288字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2011.03861

摘要

对智能规划中的常用工具--放松式规划图(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的结点数).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	饶东宁	广东工业大学计算机学院	26	89	5.0	8.0
2	蒋志华	暨南大学计算机系	25	122	7.0	9.0
3	姜云飞		8	107	5.0	8.0