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

摘要：

从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.可以证明,上述算法能够保证找到解,并且能够保证解的最优性.

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

所属期刊栏目：20

分类号：TPL8

资助基金：the National Natural Science Foundation of China under Grant No.60773201

在线出版日期：2009-06-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1254-1268