Further research on observation reduction in non-deterministic planning

Richard Preziosi, Dong Ning Rao, Zhi Hua Jiang, Yun Fei Jiang, Hui Quan Zhu

    Research output: Contribution to journalArticlepeer-review


    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(2mm2) but Ω(2m-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. © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
    Original languageEnglish
    Pages (from-to)1254-1268
    Number of pages14
    JournalRuan Jian Xue Bao/Journal of Software
    Issue number5
    Publication statusPublished - May 2009


    • AI (artificial intelligent) planning
    • Fault-tolerant
    • Minimal observation set
    • Non-deterministic planning
    • Observation reduction
    • Optimal observation set


    Dive into the research topics of 'Further research on observation reduction in non-deterministic planning'. Together they form a unique fingerprint.

    Cite this