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/4 - 2010  - pp.465-484  - doi:10.3166/ria.24.465-484
TITRE
Transformation de problèmes de planification optimale

TITLE
Transformation of optimal planning problems

RÉSUMÉ
La planification de coût optimal, dont le but est de minimiser la somme des coûts des actions, est un challenge pour l'IA en raison de sa complexité. Un programme linéaire obtenu par une relaxation qui ignore les contraintes d'ordonnancement des actions peut être utilisé pour déterminer une borne inférieure au coût d'un plan-solution. Nous montrons que le dual de ce programme linéaire fournit une transformation du problème en un problème de planification de coût optimal équivalent dans lequel le coût de l'action qui atteint le but est exactement égal à cette borne inférieure. Cette transformation est une technique universelle dans le sens où elle peut être appliquée comme une technique de prétraitement et peut donc être combinée avec d'autres techniques qui ont été développées pour la planification optimale.


ABSTRACT
Cost-optimal planning, in which the aim is to minimize the sum of costs of actions, is a challenging problem due to its computational complexity. A linear program derived from a relaxation which ignores the constraints on the ordering of actions can be used to obtain a lower bound on the cost of a solution-plan. We show that the dual of this linear program provides a transformation of the problem into an equivalent optimal planning problem in which the cost of the goal-achieving action is exactly equal to this lower bound. This transformation is of universal utility since it can be applied as a preprocessing technique and can thus be combined with any of the diverse techniques which have been developed for optimal planning.


AUTEUR(S)
Martin C. COOPER, Marie DE ROQUEMAUREL, Pierre RÉGNIER

MOTS-CLÉS
planification, optimisation, programmation linéaire, théorème fondamental de dualité.

KEYWORDS
planning, optimization, linear programming, fundamental duality theorem.

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  (230 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

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

 English version >> 
Lavoisier