Voir la source de STRIPS

[[Fichier:SRI Shakey with callouts.jpg|thumb|Le robot [[Shakey le robot|Shakey]] de [[SRI International]] (ici en 1972) utilisait l'algorithme STRIPS.]]
'''STRIPS''' (ou ''{{lang|en|Stanford Research Institute problem solver}}'') est un [[Algorithmique|algorithme]] de [[Planification (intelligence artificielle)|planification]] classique conçu par {{lien|Richard Fikes}} et [[Nils John Nilsson]] en 1971. L'algorithme de STRIPS est assez simple, 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 {{lang|en|[[General Problem Solver]]}} de {{lien|trad=Alan Newell (English computer scientist)|fr=Alan Newell|texte=Newell}} et [[Herbert Simon|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…).

== Description de l'algorithme ==
=== 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.

=== Éléments de l'algorithme ===

Les composants de cet algorithme sont : 
* Les ''[[prédicat (programmation)|prédicats]]'' décrivant le monde, par exemple : <code>dansPiece(objet4,piece2)</code>
* Les ''états'' possibles du monde, chaque état est un ensemble de prédicats. 
* Les ''buts'' qui sont des [[Algèbre de Boole (logique)#Conjonction|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'ajouts et une liste de suppressions de prédicats.
* La ''pile de traitements'' contenant des actions à effectuer et des buts et sous-buts à réaliser

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

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

=== 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 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é.

== 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 appartient à Pile '''alors''' retourner ECHEC
     EnsembleOperateurs ← {o / o peut satisfaire le but But}
     '''pour''' chaque opérateur 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, État, Pile)
     NouvelEtat ← SatisfactionButs(Operateur, Preconditions, État, Pile)
     '''si''' NouvelEtat <> ECHEC '''alors'''
        '''faire''' Operateur.Action
        NouvelEtat ← NouvelEtat - Operateur.ListeSuppressions
        '''retourner''' NouvelEtat U Operateur.ListeAjouts
     '''sinon''' '''retourner''' ECHEC
  '''fin'''.

== 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é <code>porteFermee()</code> et
* « la clé se trouve dans la boîte aux lettres », noté <code>dansBoite()</code>.

Si le robot est dans le jardin et a pour but : <code>porteFermee()</code> <math>\wedge</math> <code>dansBoite()</code>, il a intérêt à s'occuper du sous-but <code>porteFermee()</code> avant le sous-but <code>dansBoite()</code> 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ésout pas toujours le problème, est d'ordonner les sous-buts a priori et d'une façon intelligente (cela fonctionne pour l'exemple précédent). Supposons à présent que les prédicats soient ordonnés ainsi : traiter <code>porteFermee()</code> avant <code>dansBoite()</code>.

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'').

== 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]].

{{Portail|Programmation informatique}}

[[Catégorie:Algorithme]]
[[Catégorie:Intelligence artificielle]]