ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 24/2 - 2010  - pp.131-158  - doi:10.3166/ria.24.131-158
TITRE
Résolution exacte et approchée de problèmes de décision markoviens formulés en logique propositionnelle

TITLE
Exact and approximate solving of Markov decision processes using propositional logic

RÉSUMÉ
Nous présentons une méthode factorisée de résolution de processus de décision markoviens formulés en logique propositionnelle. Nous montrons que la complexité de la résolution de tels problèmes dépend directement de celles des opérations logiques mises en oeuvre telles que le test de satisfaisabilité. Afin de réduire cette complexité, nous proposons une méthode d'approximation des problèmes dans des classes de formules permettant de réaliser de manière efficace ces opérations. En utilisant ces approximations, nous mesurons expérimentalement la capacité de différentes classes de formules à représenter la structure des problèmes, ainsi que les gains en temps de résolution.


ABSTRACT
In this paper we present a method for solving factored Markov Decision Processes described using propositional logic. We show that the complexity of solving such problems directly depends on that of the logical operations used, such as satisfiability testing. In order to reduce this complexity, we propose a problem approximation method into classes of formulas which are tractable for these operations. Using such approximations, we experimentally measure the capability of various classes of formulas to represent the structure of problems as well as the benefits in terms of resolution time.


AUTEUR(S)
Boris LESNER, Bruno ZANUTTINI

MOTS-CLÉS
décision et planification, processus de décision markoviens, logique propositionnelle, approximation de connaissances.

KEYWORDS
decision-theoretic planning, Markov decision processes, propositional logic, knowledge approximation.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 7.5 €
• Non abonné : 15.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (366 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier