Planning with incomplete information as heuristic search in belief space

TLDR

Planning as heuristic search has proven effective for classical planning, and incomplete‑information planning can be framed as belief‑space search over sets or probability distributions of states. This paper explicitly formulates heuristic‑search planning for incomplete information, tests it across multiple domains, and extends it to sensing tasks where standard search algorithms fail. The authors implement a belief‑space heuristic‑search planner, evaluate it on several domains, and adapt it to handle sensing actions beyond conventional search. The resulting planner is competitive with recent conformant and contingent planners such as CGP, SGP, and CMBP, while also supporting probabilistic actions, sensing, varied action costs, and epistemic goals.

Abstract

The formulation of planning as heuristic search with heuristics derived from problem representations has turned out to be a fruitful approach for classical planning. In this paper, we pursue a similar idea in the context planning with incomplete information. Planning with incomplete information can be formulated as a problem of search in belief space, where belief states can be either sets of states or more generally probability distribution over states. While the formulation (as the formulation of classical planning as heuristic search) is not particularly novel, the contribution of this paper is to make it explicit, to test it over a number of domains, and to extend it to tasks like planning with sensing where the standard search algorithms do not apply. The resulting planner appears to be competitive with the most recent conformant and contingent planners (e.g., CGP, SGP, and CMBP) while at the same time is more general as it can handle probabilistic actions and sensing, different action costs, and epistemic goals.