Technical Report No. 205 - Abstract

Jussi Rintanen
Conditional Planning in the Discrete Belief Space

We address the non-probabilistic conditional planning problem with partial observability. Although backward search (dynamic programming) is the leading algorithm for probabilistic forms of conditional planning and for conditional planning with full observability, recent works on the non-probabilistic partially observable problem have concentrated on forward search. To show the high competitiveness of the backward approach and the benefits of dynamic programming type backups in the non-probabilistic problem we propose a new framework for non-probabilistic conditional planning with partial observability: we present a compact problem representation, an optimal algorithm for computing dynamic-programming type backup steps with this representation, and describe an efficient implementation of the framework.