对不确定规划中观测约简的进-步研究

• 作者: 姜云飞 朱慧泉 蒋志华 饶东宁
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 智能规划 不确定规划 观测约简 最小观测集 最优观测集 容错
• 年，卷（期）: 2009,（5）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 1254-1268
• 页数: 15页
• 分类号: TPL8
• 字数: 11738字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2009.03453

摘要

从3个方面改进了不确定规划(non-deterministic planning,简称NDP)中的观测约简:-是如何找最小观测集合(minimal observation set,简称 MOS),二是如何在观测代价不均等时找最优观测集合(optimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cove简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2mm2)且不低于Q(2m-1)的算法,其中m是观测的个数逼过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	蒋志华	中山大学信息科学与技术学院软件研究所	25	122	7.0	9.0
3	姜云飞	中山大学信息科学与技术学院软件研究所	84	1013	18.0	28.0
6	饶东宁	中山大学信息科学与技术学院软件研究所	4	51	4.0	4.0