STRIPS
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
STRIPS est un algorithme de planification basique intéressant pour comme exemple pédagogique.
Sommaire |
[modifier] Description de l'algorithme
Les composants de cet algorithme sont :
- Les Prédicats décrivant le monde. ex: DansPiece(objet4,piece2)
- L'Etat du monde qui est un ensemble de Prédicats
- Les Buts qui sont des conjonctions de Prédicats
- Les Actions 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
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.
Il est à noter que si plusieurs actions sont utilisables pour satisfaire le 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'algotithme effectue un backtrack jusqu'au dernier choix d'actions (cela implique d'il dépile la Pile jusqu'à trouver une Action 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 taritement 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édement 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 retournes 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] Défauts
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 probleme avec une maison, un jardin, une boite aux lettres dans le jardin.
si le robot est dans le jardin et a pour buts : "la porte de la maison est fermée" (Maison_Fermee) et "La cle se strouve dans la boite aux lettres" (Dans_Boite), il a intéret à s'occupper du predicat Porte_Fermee avant le prédicat Dans_Boite.
La première solution, qui ne résoud pas toujours le probleme, est d'ordonner les buts a priori et d'une facon intelligente. (cela fonctionne pou l'exemple précédent)
Supposons à présent que les predicats soient ordonnés ainsi : traiter Maison_Fermée avant Dans_Boite.
Si le robot est desormais dans la maison, il fermera la porte puis se trouvera bloqué au moment d'aller mettre la porte 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.
[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.
