Deterministic POMDPs Revisited
This work addresses the need for more efficient algorithms in planning by focusing on a less general but more tractable model, which is incremental as it builds on existing POMDP research.
The paper tackles the problem of analyzing Deterministic POMDPs, a subclass with deterministic actions and observations, by providing results on their fundamental properties, relation to AND/OR search problems, and computational complexity, but does not report concrete numerical results.
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.