Conditional Planning in the Discrete Belief Space

Rintanen, Jussi

Conditional Planning in the Discrete Belief Space

Download BibTeX Cite

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.

Jussi Rintanen. 2005. Conditional Planning in the Discrete Belief Space. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05. IJCAI, 1260–1264. https://ijcai.org/proceedings/2005/128

@inproceedings{ijcai2005p128,
  title     = {Conditional Planning in the Discrete Belief Space},
  author    = {Rintanen, Jussi},
  booktitle = {Proceedings of the Nineteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-05}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  pages     = {1260--1264},
  year      = {2005},
  url       = {https://ijcai.org/proceedings/2005/128},
}

TY  - CPAPER
TI  - Conditional Planning in the Discrete Belief Space
AU  - Rintanen, Jussi
T2  - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2005
SP  - 1260
EP  - 1264
UR  - https://ijcai.org/proceedings/2005/128
ER  -