  We study a subclass of POMDPs, called Deterministic POMDPs, that is
characterized by deterministic actions and observations. These models do not
provide the same generality of POMDPs yet they capture a number of interesting
and challenging problems, and permit more efficient algorithms. Indeed, some of
the recent work in planning is built around such assumptions mainly by the
quest of amenable models more expressive than the classical deterministic
models. We provide results about the fundamental properties of Deterministic
POMDPs, their relation with AND/OR search problems and algorithms, and their
computational complexity.
