---
title: "Conditional Planning in the Discrete Belief Space"
authors:
  - "Jussi Rintanen"
doi: ""
url: "https://ijcai.org/proceedings/2005/128"
pdf: "https://ijcai.org/proceedings/2005/0128.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "1260-1264"
track: ""
keywords:
---

# Conditional Planning in the Discrete Belief Space

Jussi Rintanen

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 1260-1264.

## Abstract

Probabilistic planning with observability restrictions, as formalized for example as partially observable Markov decision processes (POMDP), has a wide range of applications, but it is computationally extremely difficult. For POMDPs, the most general decision problems about existence of policies satisfying certain properties are undecidable. We consider a computationally easier form of planning that ignores exact probabilities, and give an algorithm for a class of planning problems with partial observability. We show that the basic backup step in the algorithm is NP-complete. Then we proceed to give an algorithm for the backup step, and demonstrate how it can be used as a basis of an efficient algorithm for constructing plans.