Planification (intelligence artificielle)
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
 |
Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant. |
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.
Sommaire |
[modifier] 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é.
[modifier] Planification pratique
En pratique, on ne vérife que très rarement les hypothèses de la planification classique. C'est pourquoi bon nombre d'extensions ont vu le jour.
[modifier] 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 Processus de décision markovien (MDP) ou (dans le cas général) un Processus de décision markovien partiellement observable (POMDP).
[modifier] Planification non linéaire
La planification classique résoud les sous-buts dans un ordre donné. Le problème est que cela amène parfois à détruire ce qui a déja été construit. Ce phénomène est connu sous le nom d'anomalie de Sussman. Pour résoudre le problème, on peut passer à des plans partiellement ordonnés dans lesquels l'ordre entre les actions n'est fixé que lorsque c'est nécessaire. Les planificateurs capable de gérer cette catégorie de problème sont dits à ordre partiel (POP, NOAH, etc).
[modifier] Planification hiérarchique
Certains problèmes sont difficilement résolvables en l'état du fait de leur complexité. On peut gagner en efficacité en effectuant une abstraction des détails et en changeant la granularité des opérateurs de planification. On peut par exemple commencer à planifier à haut niveau puis descendre dans le détail au besoins (comme le fait ABSTRIPS par exemple).
[modifier] 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
[modifier] Liens externes
- Quelques planificateurs
[modifier] Voir aussi
- AIPS Conférences internationales sur les Systèmes de Planification en Intelligence Artificielle au cours de laquelle se déroulent des compétitions de planificateurs.
- PDDL (Planning Domain Description Language) qui est un langage utilisé pour décrire des domaines et des problèmes de planification. Utilisé en compétition, il est modulaire et supporté (en partie) par bon nombre de planificateurs.
