OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Structured Possibilistic Planning Using Decision Diagrams

Drougard, Nicolas and Teichteil-Königsbuch, Florent and Farges, Jean-Loup and Dubois, Didier Structured Possibilistic Planning Using Decision Diagrams. (2014) In: Conference on Artificial Intelligence - AAAI 2014, 27 July 2014 - 31 July 2014 (Québec, Canada).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


Qualitative Possibilistic Mixed-Observable MDPs (π-MOMDPs), generalizing π-MDPs and π-POMDPs, are well-suited models to planning under uncertainty with mixed-observability when transition, observation and reward functions are not precisely known and can be qualitatively described. Functions defining the model as well as intermediate calculations are valued in a finite possibilistic scale L, which induces a finite belief state space under partial observability contrary to its probabilistic counterpart. In this paper, we propose the first study of factored π-MOMDP models in order to solve large structured planning problems under qualitative uncertainty, or considered as qualitative approximations of probabilistic problems. Building upon the SPUDD algorithm for solving factored (probabilistic) MDPs, we conceived a symbolic algorithm named PPUDD for solving factored π-MOMDPs. Whereas SPUDD’s decision diagrams’ leaves may be as large as the state space since their values are real numbers aggregated through additions and multiplications, PPUDD’s ones always remain in the finite scale L via min and max operations only. Our experiments show that PPUDD’s computation time is much lower than SPUDD, Symbolic-HSVI and APPL for possibilistic and probabilistic versions of the same benchmarks under either total or mixed observability, while still providing high-quality policies.

Item Type:Conference or Workshop Item (Paper)
Additional Information:Thanks to AAAI editor. The definitive version is available at http://www.aaai.org/ocs/index.php/AAAI/index/search/advancedResults
HAL Id:hal-01136897
Audience (conference):National conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Laboratory name:
Deposited On:27 Mar 2015 08:19

Repository Staff Only: item control page