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

饶东宁; 蒋志华; 姜云飞; 朱慧泉

引用本文:	饶东宁,蒋志华,姜云飞,朱慧泉.对不确定规划中观测约简的进一步研究.软件学报,2009,20(5):1254-1268

【打印本页】【下载PDF全文】【查看/发表评论】【EndNote】【RefMan】【BibTex】

←前一篇|后一篇→

过刊浏览高级检索

本文已被：浏览 6604次下载 7440次	码上扫一扫！
分享到：微信更多字体:加大+\|默认\|缩小-
对不确定规划中观测约简的进一步研究
饶东宁¹, 蒋志华^1,2, 姜云飞¹, 朱慧泉³
1.中山大学信息科学与技术学院软件研究所,广东广州 510275;2.暨南大学计算机系,广东广州 510632;3.School of Computing, National University of Singapore, Singapore

摘要:

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

关键词: 智能规划不确定规划观测约简最小观测集最优观测集容错

DOI：

分类号:

基金项目:Supported by the National Natural Science Foundation of China under Grant No.60773201 (国家自然科学基金)

Further Research on Observation Reduction in Non-Deterministic Planning

RAO Dong-Ning,JIANG Zhi-Hua,JIANG Yun-Fei,ZHU Hui-Quan

Abstract:

This paper improves the methods of observation reduction in non-deterministic planning (NDP) in three aspects: in finding MOS (minimal observation set); in finding out the optimal observation set (OOS) when observations have different costs; and in finding fault-tolerant OOS. A MOS problem is similar to a minimal set cover (MSC) problem, so it can be proved that finding MOS is NP-hard. Inspired by MSC methods, an O(2^mm²) but Ω(2^m?1) algorithm for MOS is presented, where m is the number of observations. By using integer programming (IP) technologies, OOS or fault tolerant OOS can be found out. Proofs are provided to show that these algorithms can guarantee finding optimal solutions.

Key words: AI (artificial intelligent) planning non-deterministic planning observation reduction minimal observation set optimal observation set fault-tolerant