STRIPS

Un article de Wikipédia, l'encyclopédie libre.

STRIPS (ou STanford Research Institute Problem Solver) est un algorithme de Planification classique conçu par Richard Fikes et Nils Nilsson en 1971. L'algorithme de STRIPS est assez basique, mais il est intéressant comme exemple pédagogique. On nomme aussi par ce nom le langage de représentation des données utilisée par l'algorithme.

Avec le GPS (General Problem Solver) de Newell et Simon de 1961, il fait partie des premiers planificateurs utilisés en intelligence artificielle et été suivi de nombreux dérivés (GraphPlan, IPP, STAN, etc).

Sommaire

[modifier] Description de l'algorithme

[modifier] Principe général

L'algorithme de STRIPS fonctionne selon l'analyse des fins et des moyens (ou Mean Ends Analysis) énoncée par Aristote : on part des buts que l'on veut atteindre et on tente de trouver les moyens qui peuvent y conduire. Cela produit de nouveaux buts que l'on tente de résoudre et ainsi de suite jusqu'à ce que l'on tombe sur les hypothèses de départ. Le plan est alors obtenu en cheminant sens inverse. En pratique l'algorithme calcule la différence entre les états du monde qu'il considère. Il considère des actions capables de réduire ces différences et les combine pour construire le plan.

[modifier] Eléments de l'algorithme

Les composants de cet algorithme sont :

  • Les prédicats décrivant le monde, par exemple : dansPiece(objet4,piece2)
  • Les états possibles du monde, chaque état est un ensemble de prédicats.
  • Les buts qui sont des conjonctions de prédicats
  • Les actions (aussi appelées opérateurs) définies par leurs préconditions et leurs modifications sur l'état du monde.
    • Les préconditions sont une conjonction de prédicats. Chacun de ces prédicats doit être vérifié au moment où l'on exécute l'action.
    • Les modifications peuvent être représentées comme une liste d'ajout et une liste de suppression de prédicats.
  • La pile de traitements contenant des actions à effectuer et des buts et sous-buts à réaliser

[modifier] Fonctionnement

L'algorithme entretient une représentation du monde qui évolue pendant le déroulement de l'algorithme. Au cours de ce déroulement, l'algorithme peut décider d'effectuer une action qui modifiera l'état du monde.

L'algorithme consiste stocker dans une pile une suite de buts et d'actions à accomplir. Le but initial est positionné en bas de la pile, les sous-buts apparaissent au dessus, et les sous-sous-buts encore plus haut...

A chaque étape, on traite l'élément en haut de la pile.

Il se présente deux cas :

  • s'il s'agit d'un but :

Si le but est vérifié dans le monde courant, il est supprimé, sinon, l'algorithme choisit une action permettant d'obtenir ce but. L'action choisie est empilée, ainsi que les sous-buts à obtenir (ces sous-buts sont les prédicats contenus dans la précondition de l'action). On réitère alors l'algorithme pour traiter ces sous-buts.

Si plusieurs actions sont utilisables pour satisfaire un but, on choisit l'une d'entre elles, les autres seront essayées si l'algorithme échoue en utilisant la première. Ceci nécessite un backtracking (ou l'utilisation de la récursivité).

  • s'il s'agit d'une action :

on vérifie que la précondition est vérifiée. Si oui, on exécute l'action (ce qui met à jour le monde) on dépile l'action et on réitère l'algorithme. Sinon, l'algorithme effectue un backtrack jusqu'au dernier choix d'actions (cela implique qu'il dépile jusqu'à trouver une action pour laquelle il existe une alternative). Si aucune action alternative n'existe, ou si elles ont toutes été testées, l'algorithme échoue.

[modifier] Remarque inhérente au traitement d'une action

Si le haut de la pile est occupé par une action, c'est que tous les sous-buts issus de la précondition de cette action ont été traités. Le traitement d'un sous-but consiste à effectuer des actions qui transforment l'état du monde de manière a ce qu'il satisfasse le sous-but. Cependant il est possible que malgré ces traitements, l'état du monde ne satisfasse pas la précondition. En effet, le traitement d'un sous-but peut défaire un sous-but précédemment traité.

[modifier] Algorithme

Algorithme: Planification Linéaire en STRIPS

 SatisfactionButs( Buts, S, Pile)
    pour chaque But dans Buts faire
       NouvelEtat <- RealisationBut( But, S, Pile)
       si NouvelEtat = ECHEC alors retourner ECHEC
       si tous les buts dans Buts sont satisfaits dans l'état NouvelEtat alors retourner NouvelEtat
       sinon retourner ECHEC
 fin.

 RealisationBut (But, S, Pile)
    si But est marqué satisfait dans l'état S alors retourner S
    si But apartint à Pile alors retourner ECHEC
    EnsembleOperateurs <- {o / o peut satisfaire le but But}
    pour chaque operateur o dans EnsembleOperateurs faire
         NouvelEtat <- AppliquerOperateur( o, S, Pile U {But} )
         si NouvelEtat <> ECHEC alors
             Marquer le but But satisfait dans l'etat S
             retourner NouvelEtat
    retourner ECHEC
 fin

 AppliquerOperateur(Operateur, Etat, Pile)
    NouvelEtat <- SatisfactionButs(Operateur, Preconditions, Etat, Pile)
    si NouvelEtat <> ECHEC alors
       faire Operateur.Action
       NouvelEtat <- NouvelEtat - Operateur.ListeSuppressions
       retourner NouvelEtat U Operateur.ListeAjouts
    sinon retourner ECHEC
 fin.

[modifier] Limites

Le problème de STRIPS est la linéarité : cela signifie que les sous-buts sont traités les uns après les autres. Cela provoque des situations de blocage dans le cas où la réalisation du premier sous-but engendre une action rendant impossible le second sous-but.

Par exemple, supposons un problème avec une maison, un jardin avec une boîte aux lettres dans le jardin. Définissons ensuite deux prédicats :

  • "la porte de la maison est fermée", noté porteFermee() et
  • "La clé se trouve dans la boîte aux lettres", noté dansBoite().

Si le robot est dans le jardin et a pour but : porteFermee() \wedge dansBoite(), il a intérêt à s'occuper du sous-but porteFermee() avant le sous-but dansBoite() sinon il risque de glisser la clé dans la boîte aux lettres sans pouvoir fermer la porte par la suite.

La première solution, qui ne résoud pas toujours le problème, est d'ordonner les sous-buts a priori et d'une facon intelligente (cela fonctionne pour l'exemple précédent). Supposons à présent que les prédicats soient ordonnés ainsi : traiter porteFermee() avant dansBoite().

Si le robot est désormais dans la maison, il fermera la porte puis se trouvera bloqué au moment d'aller mettre la clé dans la boite aux lettres qui a le malheur de se trouver dans le jardin. Si on avait inversé les deux buts, on se serait retrouvé dans le cas de blocage expliqué précédemment.

La solution à ce problème est la planification non-linéaire. Là ou STRIPS force un ordre d'exécution, elle permet d'effectuer les actions et de les ordonner uniquement lorsque c'est nécessaire : on parle d'engagement au plus tard (Least Commitment Planning).

[modifier] Sources

Fikes, R. E. & N. J. Nilsson, "STRIPS: A New Approach to the Application of Theorem Proving", dans Artificial Intelligence, Vol. 2, 1971.

Elaine Rich, "Intelligence Artificielle", 1987.