Observation Reduction for Strong Plans

Wei Huang, Zhonghua Wen, Yunfei Jiang, Lihua Wu

Strong planning under full or partial observability has been addressed in the literature. But this research line is carried out under the hypothesis that the set of observation variables is fixed and compulsory. In most real world domains, however, observation variables are optional and many of them are useless in the execution of a plan; on the other side, information acquisition may require some kind of cost. So it is significant to find a minimal set of observation variables which are necessary for the execution of a plan, and to best of our knowledge, it is still an open problem. In this paper we present a first attempt to solve the problem, namely, we define an algorithm that finds an approximate minimal set of observation variables which are necessary for the execution of a strong plan under full observability (i.e. a state–action table); and transforms the plan into a strong plan under partial observability (i.e. a conditional plan branching on the observations built on these observation variables).