主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
蒋志华,饶东宁,姜云飞,朱慧泉.利用规划命题关系图构建目标议程和宏动作.软件学报,2011,22(1):44-56
利用规划命题关系图构建目标议程和宏动作
Constructing Goal Agenda and Macro Actions Using Proposition Relation Graphs in Planning
投稿时间:2009-10-19  修订日期:2010-04-27
DOI:10.3724/SP.J.1001.2011.03861
中文关键词:  智能规划  放松式规划图  命题关系图  目标议程  宏动作
英文关键词:AI planning  relaxed planning graph  proposition relation graph  goal agenda  macro action
基金项目:国家自然科学基金(61003179, 60903178); 广东工业大学博士科研启动基金(093032); 中央高校基本科研业务费专 项资金(21610305)
作者单位E-mail
蒋志华 暨南大学 计算机系,广东 广州 510632  
饶东宁 广东工业大学 计算机学院,广东 广州 510006 raodn@gdut.edu.cn 
姜云飞 中山大学 信息科学与技术学院 软件研究所,广东 广州 510275  
朱慧泉 School of Computing, National University of Singapore, Singapore 670527, Singapore  
摘要点击次数: 5305
全文下载次数: 3894
中文摘要:
      对智能规划中的常用工具——放松式规划图(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 的结点数).
英文摘要:
      This paper focuses on graph properties of relaxed planning graph (RPG), a widely-used tool in automated planning. When proposition levels are extracted from RPG, and thus, used to build a proposition relation graph (PRG), it is found that PRG keeps primary planning properties in RPG. Preliminary research results include the following four aspects: The close pth out-neighborhoods (CON) of initial proposition set (IPS) is the relaxed reachable proposition set (R-RPS) in planning; the maximum distance from any proposition in initial state to any proposition in goal states is a reasonable estimation of the plan length; acyclic order in graph indicates that some orders that held corresponding propositions are necessary; contraction of in/out cut-vertex means construction of macro-action is currently being planned. The first and second results show PRG keeps planning properties in RPG, and the third and fourth results can be used in goal agenda building and macro-action construction. Three related algorithms are proposed: PRG in RPG finding algorithm, an O(mn2/4) (n is the number of propositions in RPG, m is the number of actions in RPG) algorithm; acyclic order reduction algorithm, an O(n+m) (n is the number of nodes in PRG, m is the number of edges in PRG) algorithm; macro action suggestion algorithm, an O(n2) (n is the number of nodes in PRG) algorithm.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利