Improving heuristics for planning as search in belief space
Piergiorgio Bertoli, Alessandro Cimatti · 2002
Search in the space of beliefs has been proposed as a con-venient framework for tackling planning under uncertainty. Significant improvements have been recently achieved, espe-cially thanks to the use of symbolic model checking tech-niques such as Binary Decision Diagrams. However, the problem is extremely complex, and the heuristics available so far are unable to provide enough guidance for an informed search. In this paper we tackle the problem of defining effective heuristics for driving the search in belief space. The basic intuition is that the “degree of knowledge ” associated with the belief states reached by partial plans must be explicitly taken into account when deciding the search direction. We propose a way of ranking belief states depending on their de-gree of knowledge with respect to a given set of boolean func-tions. This allows us to define a planning algorithm based on the identification and solution of suitable “knowledge sub-goals”, that are used as intermediate steps during the search. The solution of knowledge subgoals is based on the identifi-cation of “knowledge acquisition conditions”, i.e. subsets of the state space from where it is possible to perform knowl-edge acquisition actions. We show the effectiveness of the proposed ideas by observing substantial improvements in the conformant planning algorithms of MBP.