中文摘要：

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

英文摘要：

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. AMOS 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^2） 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.