Planification en intelligence artificielle

Planification en intelligence artificielle

Planification (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

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

Liens externes

Quelques planificateurs
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.
Ce document provient de « Planification (intelligence artificielle) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Planification en intelligence artificielle de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Planification (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… …   Wikipédia en Français

  • Intelligence Artificielle — Pour les articles homonymes, voir A.I. Intelligence artificielle (film),IA. Le robot humanoïde ASIMO …   Wikipédia en Français

  • Intelligence artificielle — Pour les articles homonymes, voir A.I. Intelligence artificielle (film), IA. Le robot humanoïde ASIMO L intelligence artificielle est la …   Wikipédia en Français

  • Planification — sous forme d un diagramme de Gantt. La planification est l organisation dans le temps de la réalisation d objectifs : dans un domaine ; avec des objectifs ; avec des moyens ; et sur une durée (et des étapes) précise(s). La… …   Wikipédia en Français

  • INTELLIGENCE — De tous les concepts que la psychologie a hérités de la tradition philosophique et religieuse, celui d’intelligence est sans doute le plus marqué par ses antécédents culturels. L’intelligence représente la fonction par laquelle l’homme a essayé… …   Encyclopédie Universelle

  • Planification motrice — La planification motrice est un processus cognitif permettant d’élaborer un mouvement volontaire et de l’organiser en séquences avant de l’exécuter [1]. Pour ce faire, avant chaque mouvement, le cerveau établit un plan moteur composé d’images… …   Wikipédia en Français

  • Modèles de l'intelligence collective des sociétés — Des communautés intelligentes qui s’auto organisent, sans chef, qui réagissent instantanément à un message, peuvent communiquer et débattre entre elles : voilà actuellement le modèle standard de l’« intelligence collective » des… …   Wikipédia en Français

  • Emploi du temps — Planification Planning sous forme d un diagramme de Gantt. La planification est la mise en oeuvre d objectifs dans le temps dans un domaine, avec des objectifs, avec des moyens et sur une durée (et des étapes) précise(s). La caractéristique du… …   Wikipédia en Français

  • Plan (économie) — Planification Planning sous forme d un diagramme de Gantt. La planification est la mise en oeuvre d objectifs dans le temps dans un domaine, avec des objectifs, avec des moyens et sur une durée (et des étapes) précise(s). La caractéristique du… …   Wikipédia en Français

  • I.A. — Intelligence artificielle Pour les articles homonymes, voir A.I. Intelligence artificielle (film),IA. Le robot humanoïde ASIMO …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”