Planification en intelligence artificielle

La planification (Automated 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 manipule prend trois entrées (toutes codées dans un langage formel tel que STRIPS qui utilise des prédicats logiques) :

• une description de l'état initial d'un monde,
• une description d'un but à atteindre et
• un ensemble d'actions possibles (parfois appelés opérateurs)

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 1 Le problème de planification classique 2 Planification pratique 2.1 Le problème de planification non déterministe 2.2 Planification non linéaire 2.3 Planification hiérarchique 3 Voir aussi 3.1 Bibliographie 3.2 Articles connexes 3.3 Liens externes

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,
• la 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é.

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.

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 politique (ou stratégie) pour un Processus de décision markovien (MDP) ou (dans le cas général) un Processus de décision markovien partiellement observable (POMDP).

Planification non linéaire

La planification classique résout les sous-buts dans un ordre donné. Le problème est que cela amène parfois à détruire ce qui a déjà été construit. Ce phénomène est connu sous le nom d'anomalie de Sussman.

Supposons qu'un individu pieds nus doive se retrouver dans l'état ou il porte sa chaussure droite, sa chaussure gauche, sa chaussette droite et sa chaussette gauche. S'il cherche à réaliser les buts dans l'ordre de l'énoncé, il échouera.

Pour résoudre ce type de 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 (engagement au plus tard ou least commitment planning).

Dans l'exemple précédent, mettre la chaussure gauche doit se faire après avoir mis la chaussette gauche. Idem pour la droite. En revanche l'exécution du plan pour la gauche est indépendante de l'exécution pour la droite. Le plan global est donc partiellement ordonné.

Les planificateurs capable de gérer cette catégorie de problème sont dits à ordre partiel (POP, NOAH, etc).

Planification hiérarchique

Certains problèmes sont difficilement solubles 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 besoin (comme le fait ABSTRIPS par exemple).

Voir aussi

Bibliographie

• Algorithmique de la planification en IA, Pierre Régnier, Editions Cépaduès, ISBN 2-85428-658-8
• (en)Automated planning", 2004, Malik Ghallab, Dana nau et Paolo Traverso, Morgan Kaufman, ISBN 1-55860-856-7
• (en)Michael R. Genesereth and Nils J. Nilsson, Logical Foundations of Artificial Intelligence, 1987 [détail des éditions] , chap. 12 Planning, pp. 285-306

Articles connexes

• Planification de mouvement

Liens externes

Quelques planificateurs

• ALT-ALT (A little of this A little of that)
• BlackBox
• GPS (General Problem Solver)
• GRAPHPLAN
• IPP
• MIPS
• NOAH
• O-PLAN
• SHOP, SHOP2, JSHOP, JSHOP2
• SGP
• STAN
• TL-PLAN

Autres ressources

• 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.