Width and Complexity of Belief Tracking in Non-Deterministic Conformant and Contingent Planning
Abstract
It has been shown recently that the complexity of belief tracking in deterministic conformant and contingent planning is exponential in a width parameter that is often bounded and small. In this work, we introduce a new width notion that applies to non-deterministic conformant and contingent problems as well. We also develop a belief tracking algorithm for non-deterministic problems that is exponential in the problem width, analyze the width of non-deterministic benchmarks, compare the new notion to the previous one over deterministic problems, and present experimental results.
Cite
Text
Bonet and Geffner. "Width and Complexity of Belief Tracking in Non-Deterministic Conformant and Contingent Planning." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8365Markdown
[Bonet and Geffner. "Width and Complexity of Belief Tracking in Non-Deterministic Conformant and Contingent Planning." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/bonet2012aaai-width/) doi:10.1609/AAAI.V26I1.8365BibTeX
@inproceedings{bonet2012aaai-width,
title = {{Width and Complexity of Belief Tracking in Non-Deterministic Conformant and Contingent Planning}},
author = {Bonet, Blai and Geffner, Hector},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2012},
pages = {1756-1762},
doi = {10.1609/AAAI.V26I1.8365},
url = {https://mlanthology.org/aaai/2012/bonet2012aaai-width/}
}