ECAI 2004 Conference Paper

[full paper]

Utilizing Structured Representations in Conformant Probabilistic Planning

Nathanael Hyafil, Fahiem Bacchus

A CSP based algorithm for the conformant probabilistic planning problem (CPP) has been presented by Hyafil & Bacchus. Although their algorithm displayed some interesting potential when compared with traditional POMDP algorithms, it was developed using a ``flat'' representation. In this work we revisit this algorithm and develop a version that utilizes a structured representation. The structured representation can be exponentially more efficient than the flat representation when dealing with the structured problems that are typical in AI. Our new structured version of their algorithm allows us to make the main contribution of this work, which is to demonstrate that the CSP approach to CPP can in fact be much more effective than traditional POMDP algorithms for an interesting range of problems. This is contrary to previously presented results, and makes the application of CSP techniques to decision theoretic planning a more promising area for future work.

Keywords: probabilistic planning, decision theoretic planning, Constraint Satisfaction Problems, structured representations

Citation: Nathanael Hyafil, Fahiem Bacchus: Utilizing Structured Representations in Conformant Probabilistic Planning. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.1033-1034.