Deterministic POMDPs Revisited

general frameworks for sequential decision making [19], yet the known algorithms scale very poorly. 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. However, we have seen that an important collection of problems that involve uncertainty and partial information have a common characteristic: they have actions with deterministic outcomes and the observations generated at each decision stage also behave deterministically. Indeed, these models have been used in recent proposals for planning with incomplete information [15, 16, 27], appear in works of more general scope [15, 20] and about causation [31], and are used for learning partially-observable action models [1].

Authors

• Blai Bonet

Keywords

No keywords are indexed for this paper.