Algorithmes et complexités génériques pour différents cadres de décision séquentielle dans l'incertain
De nombreux cadres existent pour la représentation et la résolution de problèmes de décision séquentielle dans l'incertain. Récemment, un formalisme unifiant une partie importante de ces cadres, qu'ils soient probabilistes ou possibilistes, a été proposé sous le nom de formalisme PFU (pour Plausibilité, Faisabilité, Utilité). Cet article introduit des algorithmes génériques définis dans le cadre PFU et qui conséquemment sont directement applicables à tous les cadres couverts. Il est montré qu'une approche unifiée peut être définie quelle que soit la représentation de l'incertain utilisée. La complexité théorique des algorithmes introduits est également étudiée en fonction d'un paramètre appelé largeur induite contrainte.
Recently, a generic algebraic framework called PFU (for Plausibilities-FeasibilitiesUtilities) has been introduced in order to represent generic forms of sequential decision making under uncertainties. The PFU framework covers various existing probabilistic or possibilistic formalisms. This article introduces generic algorithms defined in the PFU framework which are therefore applicable for various decision models. Theoretical complexity results are also provided based on a parameter called the constrained induced-width.
C.PRALET, T.SCHIEX, G.VERFAILLIE
cadre PFU, algorithmes génériques, élimination de variable, largeur induite.
PFU framework, generic algorithms, variable elimination, induced-width.
Français
|
