| 对不确定规划中观测约简的进一步研究 |
| |
| 引用本文： | 饶东宁,蒋志华,姜云飞,朱慧泉.对不确定规划中观测约简的进一步研究[J].软件学报,2009,20(5):1254-1268. |
| |
| 作者姓名： | 饶东宁 蒋志华 姜云飞 朱慧泉 |
| |
| 作者单位： | 中山大学 信息科学与技术学院 软件研究所,广东 广州 510275;中山大学 信息科学与技术学院 软件研究所,广东 广州 510275;暨南大学 计算机系,广东 广州 510632;中山大学 信息科学与技术学院 软件研究所,广东 广州 510275;School of Computing, National University of Singapore, Singapore |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant No.60773201 (国家自然科学基金) |
| |
| 摘 要： | 从3个方面改进了不确定规划(non-deterministic planning,简称NDP)中的观测约简:一是如何找最小观测集合(minimal observation set,简称MOS),二是如何在观测代价不均等时找最优观测集合(optimal observation set,简称OOS),三是如何找到容错的OOS.通过MOS问题和图论中的最小覆盖集问题(minimal set cover,简称MSC)的类似性,可证MOS是NP难的问题,还可参考MSC算法得出时间复杂性不超过O(2mm2)且不低于Ω(2m?1)的算法,其中m是观测的个数.通过使用整数规划(integer programming,简称IP)技术,可找到OOS以及容错的OOS.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.
|
| 关 键 词： | 智能规划 不确定规划 观测约简 最小观测集 最优观测集 容错 |
| 收稿时间： | 2008/4/28 0:00:00 |
| 修稿时间： | 2008/8/28 0:00:00 |
Further Research on Observation Reduction in Non-Deterministic Planning |
| |
| RAO Dong-Ning,JIANG Zhi-Hu,JIANG Yun-Fei and ZHU Hui-Quan.Further Research on Observation Reduction in Non-Deterministic Planning[J].Journal of Software,2009,20(5):1254-1268. |
| |
| Authors: | RAO Dong-Ning JIANG Zhi-Hu JIANG Yun-Fei and ZHU Hui-Quan |
| |
| Abstract: | |
| |
| Keywords: | AI (artificial intelligent) planning non-deterministic planning observation reduction minimal observation set optimal observation set fault-tolerant |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
