Finding minimal observation set for finite (belief) state set in non-deterministic planning
Zhihua Jiang · 2008
Non-deterministic planning (NDP) is one of the most significant and challenging planning problems, recently works involving planning under sensing were presented. But in most real world domains, information acquisition may require some kind of cost, so it is significant to find a minimal set of observation variables which are necessary for planning. A new frontier in the research line of non-deterministic planning (NDP) is to reduce the observations, and several papers have been presented in IJCAI-07. This paper can be seen as an extension of these previous works, we present method to reduce observations for any state set or belief state set. Unlike previous works, our approach can find the minimal observation set. This work can be used before planning, or during planning, or after planning (with strong solutions as papers in IJCAI-07, or strong cyclic planning), wherever the (belief) state set can be limit to a finite one.