Further research on observation reduction in non-deterministic planning

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

doi:10.3724/SP.J.1001.2009.03453

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 journal › Article › peer-review

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(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 language	English
Pages (from-to)	1254-1268
Number of pages	14
Journal	Ruan Jian Xue Bao/Journal of Software
Volume	20
Issue number	5
DOIs	https://doi.org/10.3724/SP.J.1001.2009.03453
Publication status	Published - May 2009

Keywords

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

Access to Document

10.3724/SP.J.1001.2009.03453

Cite this

@article{4f376a9b798242abae58f0b1270478a9,

title = "Further research on observation reduction in non-deterministic planning",

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(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. {\textcopyright} by Institute of Software, the Chinese Academy of Sciences. All rights reserved.",

keywords = "AI (artificial intelligent) planning, Fault-tolerant, Minimal observation set, Non-deterministic planning, Observation reduction, Optimal observation set",

author = "Richard Preziosi and Rao, {Dong Ning} and Jiang, {Zhi Hua} and Jiang, {Yun Fei} and Zhu, {Hui Quan}",

year = "2009",

month = may,

doi = "10.3724/SP.J.1001.2009.03453",

language = "English",

volume = "20",

pages = "1254--1268",

journal = "Ruan Jian Xue Bao/Journal of Software",

issn = "1000-9825",

publisher = "Chinese Academy of Sciences",

number = "5",

}

TY - JOUR

T1 - Further research on observation reduction in non-deterministic planning

AU - Preziosi, Richard

AU - Rao, Dong Ning

AU - Jiang, Zhi Hua

AU - Jiang, Yun Fei

AU - Zhu, Hui Quan

PY - 2009/5

Y1 - 2009/5

N2 - 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.

AB - 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.

KW - AI (artificial intelligent) planning

KW - Fault-tolerant

KW - Minimal observation set

KW - Non-deterministic planning

KW - Observation reduction

KW - Optimal observation set

U2 - 10.3724/SP.J.1001.2009.03453

DO - 10.3724/SP.J.1001.2009.03453

M3 - Article

SN - 1000-9825

VL - 20

SP - 1254

EP - 1268

JO - Ruan Jian Xue Bao/Journal of Software

JF - Ruan Jian Xue Bao/Journal of Software

IS - 5

ER -

Further research on observation reduction in non-deterministic planning

Abstract

Keywords

Access to Document

Fingerprint

Cite this