STRIPS
STRIPS (ou Stanford Research Institute problem solver) est un algorithme de planification classique conçu par Richard Fikes (en) 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 General Problem Solver de Newell (en) 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…).
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é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'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é
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() 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é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 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).