Gourt Home::Gourt :: Planification (intelligence artificielle)
La planification (AI planning) est une discipline de l'intelligence artificielle qui vise le développement d'algorithmes pour produire des plans (en d'autre termes, une planification), typiquement pour l'exécution par un robot ou tout autre agent. Les logiciels de planification qui incorporent ces algorithmes se nomment planificateurs. Un planificateur typique prend trois entrées: une description de l'état initial d'un monde, une description d'un but à atteindre, et un ensemble d'actions possibles (toutes codées dans un langage formel tel que STRIPS). Chaque action spécifie généralement des préconditions qui doivent être présentes dans l'état actuel pour qu'elle puisse être appliquée, et des postconditions (effets sur l'état actuel).
La difficulté du problème de planification dépend des hypothèses de simplification qu'on prend pour acquis, par exemple un temps atomique, un temps déterministe, une observabilité complète, etc.
Le problème de planification classique
Les planificateurs classiques prennent pour acquis que toutes ces hypothèses tiennent. Ils ont été étudiés en profondeur. Quelques techniques populaires sont la recherche avant dans un espace d'états, le recherche arrière dans un espace d'états, la recherche avant dans un espace de plans, graphplan, et la transformation vers un problème de satisfiabilité de propositions. L'algorithme A* est un exemple typique d'algorithme de planification classique, souvent employé dans les cours d'introduction pour sa simplicité.
Le problème de planification non déterministe
Si l'hypothèse du déterminisme est abandonnée et un modèle probabiliste de l'incertitude est adopté, alors ceci mène au problème de la génération de policy pour un problème de décision de Markov (MDP) ou (dans le cas général) un problème de décision de Markov partiellement observable (POMDP).
Bibliographie
- Algorithmique de la planification en IA, Pierre Régnier, Editions Cépaduès, ISBN 2-85428-658-8
- ''Automated planning", 2004, Malik Ghallab, Dana nau et Paolo Traverso, Morgan Kaufman, ISBN 1-55860-856-7
Liens externes
- Quelques planificateurs
Voir aussi
"Planification (intelligence artificielle)"