Width and complexity of belief tracking in non-deterministic conformant and contingent planning

Bonet, Blai; Geffner, Héctor

Width and complexity of belief tracking in non-deterministic conformant and contingent planning

Citation

Bonet B, Geffner H. Width and complexity of belief tracking in non-deterministic conformant and contingent planning. In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence; 2012 Jul 22-26. Toronto, Canada. [Menlo Park, California]:AAAI; 2012. p. 1756-62

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.