Lab 7 : Planification avec PSC

Durée estimée : 4 heures.

Objectifs de la série

Comment fonctionne un planificateur qui utilise un PSC pour trouver la solution.

Fichiers squelettes

libPSC.pyPSC.pylibPlan.pymissionnairesTemplate.pyplanificateurTemplate.py

Énoncé

Dans cette série, vous allez devoir planifier la traversée de cannibales et de missionnaires entre les deux rives d’une rivière. Pour ce faire, vous disposez d’un bateau à 2 places qui doit être piloté par un missionnaire. Dans cet exercice, nous supposons qu’il y a deux missionnaires M1 et M2, deux cannibales C1 et C2, et un seul bateau B.

Cette série se compose de deux parties : dans la première partie, correspondant à l'exercice 1, vous allez concevoir sur papier un modèle PSC qui permette de représenter le problème de planification donné et de le résoudre en utilisant un solveur PSC. Dans la seconde partie, vous implémenterez ce modèle en Python, et vous le résoudrez en utilisant le solveur PSC implémenté au cours des séances d'exercices précédentes.

Afin de vous permettre d'avancer dans cette série, la solution de la première partie sera mise en ligne au bout d'une heure. Nous vous invitons cependant très vivement à travailler sérieusement sur cette première partie de modélisation pendant la première heure de la séance. La modélisation d'un problème de planification sous forme d'un PSC est un exercice fondamental typique qui pourrait tomber à l'examen théorique final.

Remarque : Il n'est pas nécessaire de lire l'énoncé de la deuxième partie (Exercices 2 et 3) pour faire la première. Au contraire, vous pourriez éprouver une certaine difficulté à comprendre cet énoncé sans avoir d'abord lu la solution de la première partie, étant donné qu'il y fait référence.

La solution de l'exercice 2 (l'implémentation de missionnaires.py) vous sera aussi donnée en fin de semaine, pour que vous puissiez vous atteler à l'exercice 3 au début de la deuxième séance d'exercices.

Exercice 1 : Modélisation sur papier

Avant de commencer à coder, vous allez devoir modéliser le problème de planification en un Problème de Satisfaction de Contraintes. Pour ce faire, vous allez procéder en deux étapes :

Définition du problème de planification en termes de propositions et d'opérateurs ;
Définition d'un PSC correspondant, en termes de variables et de contraintes sur ces variables.

Remarque : Vous pouvez vous inspirer du chapitre 10.6 du livre.

Définition du problème de planification

Un problème de planification peut être défini par trois éléments :

un ensemble de propositions, qui permettent de décrire complètement l'état du monde à un moment donné (certaines de ces propositions peuvent être mutuellement exclusives, et il faut alors expliciter des contraintes d'exclusion) ;
deux ensembles d'instanciations partielles de ces propositions, qui décrivent respectivement l'état initial et l'état final à atteindre ;
un ensemble d'opérateurs, qui permettent de faire évoluer l'état du monde depuis un état vers un autre.

Proposez une définition d'un problème de planification qui corresponde à la description informelle du problème donnée en introduction, et rappelée ci-dessous :

Deux missionnaires M1 et M2, deux cannibales C1 et C2, et un bateau B se trouvent sur la rive gauche d'un fleuve. L'objectif est de faire passer le fleuve à tout le monde, sachant que le bateau B n'a que deux places, et ne peut être piloté que par un missionnaire.

Rappelons que des propositions sont, par définition, des affirmations sur l'état d'une partie du monde, et peuvent être vraies ou fausses. Les opérateurs, quant à eux, sont définis comme des actions qui nécessitent certaines propositions (les préconditions) d'êtres vraies ou fausses pour pouvoir être exécutées, et qui ont pour conséquence d'imposer à certaines propositions (les postconditions) d'être vraies ou fausses.

Indication 1 : Privilégiez un modèle simple, qui ne contienne pas trop d'opérateurs inutiles. Par exemple, il est inutile d'introduire des opérateurs pour décrire le fait qu'un missionnaire ou un cannibale embarque sur le bateau ou débarque.

Indication 2 : Pour chaque acteur, vous pourrez utiliser une proposition pour indiquer s'il se trouve ou non sur la rive gauche, et une autre proposition indiquant s'il se trouve ou non sur la rive droite.

Définition d'un PSC correspondant

Par définition, un PSC est décrit par :

un ensemble de variables, prenant des valeurs dans des domaines définis ;
un ensemble de contraintes sur ces variables, qui définissent les combinaisons de valeurs admissibles.

Proposez un modèle PSC pour le problème de planification. Les variables doivent décrire complètement les propositions et les opérateurs à chaque état. Les contraintes, quant à elles, doivent exprimer les propriétés et limitations du problème de planification. Par exemple, un bateau ne peut contenir que deux acteurs au maximum, et l'un deux (le pilote) doit être un missionnaire. Ou encore, le bateau doit initialement être à gauche pour pouvoir faire la traversée de gauche à droite.

Remarque : Afin de reformuler le problème de planification sous la forme d'un PSC, vous allez devoir faire une hypothèse sur le nombre d'états (i.e. le nombre d'applications successives d'opérateurs) nécessaire pour l'existence d'un plan solution.

Indication : Le solveur PSC que vous avez implémenté dans les labos précédents ne connaît que les contraintes unaires ou binaires, pas les contraintes n-aires portant sur au moins 3 variables. Votre modèle PSC pourra cependant contenir des contraintes n-aires (par exemple, les contraintes correspondant aux axiomes de cadre). Il vous suffira d'étendre les capacités du solveur PSC pour qu'il supporte ces contraintes n-aires ; les exercices suivants détaillent la procédure à suivre.

Exercice 2 : Implémentation du fichier missionnairesTemplate.py

Ce fichier contient la routine qui définit et construit le problème de planification grâce aux classes fournies dans le fichier libPlan.py, puis utilise les classes et algorithmes du fichier planificateurTemplate.py (dont vous allez implémenter une partie dans l'exercice 3) afin de résoudre le problème en le transformant en un PSC. L'instruction print(probleme) dans le fichier des missionnaires devrait vous permettre de déboguer votre code au fur et à mesure que vous implémentez les différentes étapes de la routine, détaillées ci-après.

Le fichier libPlan.py contient les classes Operateur et ProblemeDePlanification, qui sont seulement des conteneurs pour définir respectivement des opérateurs et un problème de planification (les propositions seront simplement représentées par des Strings). Une fois défini le problème de planification, la construction du modèle PSC correspondant s'effectuera dans les méthodes du fichier planificateurTemplate.py.

Construction des propositions

Construisez les propositions du problème de planification, et ajoutez-les au problème en utilisant la méthode libPlan.ProblemeDePlanification.ajouteProposition(). Cette méthode prend comme paramètre une proposition, qui sera tout simplement représentée par son nom, sous la forme d'un String.

Construction des opérateurs

Construisez à présent les opérateurs du problème, qui seront représentés par la classe libPlan.Operateur. Le constructeur de cette classe prend comme arguments trois paramètres :

le nom de l'opérateur à créer
la liste des préconditions
la liste des postconditions

Ajoutez ensuite ces opérateurs au problème à l'aide de la méthode libPlan.ProblemeDePlanification.ajouteOperateur().

Spécification des mutex de propositions

Définissez les mutex de propositions à l'aide de la méthode libPlan.ProblemeDePlanification.ajouteMutexDePropositions(). Cette méthode prend en paramètres deux propositions qui ne doivent pas être vraies en même temps.

Spécification des mutex d'opérateurs

Définissez les mutex d'opérateurs à l'aide de la méthode libPlan.ProblemeDePlanification.ajouteMutexDOperateurs(). Cette méthode prend en paramètres deux opérateurs qui ne doivent pas être exécutés en même temps.

Déclaration des contraintes initiales et finales

Spécifiez maintenant les contraintes initiales et finales du problème de planification, en utilisant les méthodes libPlan.ProblemeDePlanification.ajouteConditionInitiale() et libPlan.ProblemeDePlanification.ajouteConditionFinale(). Ces méthodes prennent en paramètres une proposition, et une valeur booléenne que doit prendre la proposition à l'état initial (resp. final).

Exercice 3 : Implémentation du fichier planificateurTemplate.py

Ce fichier contient les classes et les algorithmes qui vont permettre de modéliser un problème de planification en un Problème de Satisfaction de Contraintes, afin de résoudre ce PSC pour trouver un plan valide. Le solveur PSC utilisé sera celui obtenu au cours des séances d'exercices précédentes, et qui vous est à nouveau fourni sous la forme des fichiers libPSC.py et PSC.py.

La classe ContrainteAxiomeCadre

Cette classe est une sous-classe de libPSC.Contrainte, et implémente une contrainte d'axiome de cadre pour un état S_i donné et une proposition prop donnée :

Si prop(S_i) = False et prop(S_i+1) = True, alors pour au moins un opérateur op qui a prop comme postcondition, on a op(S_i) = True.

Cette contrainte est une contrainte n-aire qui porte sur plus de deux variables ; ces variables sont les attributs de la classe :

varPre est la variable prop(S_i) ;
varPost est la variable prop(S_i+1) ;
varsOp est la liste des variables correspondant aux opérateurs qui ont prop comme postcondition.

La méthode estValide

Il vous faut tout d'abord implémenter la méthode estValide. Notez que contrairement au cas des contraintes unaires et binaires, cette méthode peut être appelée alors que toutes les variables de la contrainte ne sont pas encore instanciées (i.e. leur valeur est None). Traitez donc d'abord ce cas, et faites l'hypothèse de "présomption de validité" : la contrainte est présumée valide tant qu'on n'a pas encore pu prouver qu'elle était violée (i.e. tant qu'au moins une de ses variables n'est pas encore instanciée).

La méthode propage

Implémentez ensuite la méthode propage. Cette méthode est appelée juste après qu'une valeur ait été choisie pour une variable de la contrainte, et tente de propager les conséquences de ce choix aux variables non encore instanciées de la contrainte pour réduire leurs labels. En effet, il est possible qu'une assignation de valeur à une variable rende incompatibles certaines valeurs des labels des variables non encore instanciées. Cette méthode doit retourner True si et seulement si aucune inconsistance n'a été découverte.

Imaginons par exemple que la seule variable déjà instanciée est prop(S_i) = False, et qu'on désire propager aux variables d'opérateurs les conséquences de l'assignation prop(S_i+1) = False. Clairement, la contrainte sera alors toujours vérifiée, et la méthode retournera True, sans avoir pu découvrir aucune valeur incompatible dans les labels des variables d'opérateurs. Inversement, si on fait l'assignation prop(S_i+1) = True, on peut en déduire qu'au moins un des labels des variables d'opérateurs doit contenir la valeur True. Si ce n'est pas le cas, cette assignation est inconsistante. Si seulement une des variables d'opérateurs a un label qui contient True, alors on peut dores et déjà conclure que seule la valeur True est possible pour cette variable, et on peut retirer la valeur False de son label.

Comme vous le soupçonnez peut-être déjà sur la base de cet exemple, dans le cas général l'implémentation d'un algorithme performant de propagation pour une contrainte n-aire peut s'avérer être un problème difficile, surtout si l'on veut découvrir le plus tôt possible les inconsistances et réduire au maximum les labels des variables non encore instanciées, afin d'accélérer la recherche. Dans cet exercice nous vous proposons d'en implémenter une version simple, peu performante, mais suffisante pour résoudre le problème simple de planification qui nous occupe. Cette implémentation "paresseuse" consiste à ne tenter de réduire les labels et détecter des inconsistances que s'il ne reste plus qu'une seule variable de la contrainte qui n'est pas encore instanciée. Si c'est le cas, vérifiez simplement les valeurs du label de cette variable une par une, pour retirer du label celles qui ne respectent pas la contrainte, et retournez True si et seulement si le label résultant n'est pas vide. Dans le cas contraire où au moins deux variables de la contraintes ne sont pas encore instanciées, utilisez la même hypothèse de "présomption de validité" que pour la méthode estValide, et retournez systématiquement True sans même tenter de réduire les labels de ces variables. Comme exercice optionnel, vous pourrez plus tard implémenter un algorithme de propagation plus performant, que vous comparerez avec ce premier algorithme simple sur des problèmes de planification plus complexes.

Remarque sur la méthode reviser

Notez que l'implémentation de la fonction reviser qui vous est fournie retourne simplement False, c'est à dire qu'elle n'essaie pas de réduire les domaines des variables en appliquant la consistance des arcs. La raison pour cela est que la consistance des arcs n'est pas définie pour des contraintes n-aires. Pour les contraintes n-aires, on parle de consistance des arcs généralisée (Generalized Arc Consistency, ou GAC) : pour chaque valeur du domaine de chaque variable, il doit exister une combinaison de valeurs pour toutes les autres variables qui satisfasse la contrainte. Pour l'exemple simple de planification qui nous occupe, il n'est pas nécessaire d'implémenter GAC, de la même façon qu'il n'est pas nécessaire d'implémenter une méthode de propagation très performante.

La classe Etat

Un état contient quatre attributs :

varInitiales : une liste de variables correspondant aux propositions au début de l'état (égales à celles à la fin de l'état précédent). Cette "liste" est en fait un dictionnaire qui associe des propositions à leurs variables respectives.
varFinales : un dictionnaire de variables associées aux propositions à la fin de l'état (égales à celles du début de l'état suivant).
varOperateurs : un dictionnaire de variables associées aux opérateurs pour cet état
no_etat : le numéro de l’état, inclus dans l’intervalle [0, PlanificateurPSC.nb_etats].

Le constructeur vous est donné, et appelle les méthodes construitVariablesOperateurs() et construitVariablesPropositions(), qui remplissent les attributs varOperateurs, et varInitiales et varFinales (respectivement). La première de ces méthodes est déjà implémentée ; vous allez devoir coder la seconde, en vous inspirant de la première.

Indication : Nommez les variables à l'aide du numéro de l'état au début duquel la variable se trouve. N'oubliez pas que les variables finales d'un état doivent être les mêmes que les variables initiales de l'état suivant.

La classe PlanificateurPSC

La classe PlanificateurPSC est la classe centrale du planificateur et qui transforme un problème de planification en un PSC pour trouver un plan valide. La classe contient les attributs suivants :

nb_etats : le nombre d’états dans le plan, c'est à dire, la longueur du plan.
probleme : l'instance de ProblemeDePlanification qui représente le problème à modéliser par un PSC

Les méthodes de classe

Vous allez maintenant implémenter les méthodes de la classe PlanificateurPSC. Les méthodes à implémenter sont les suivantes :

construitEtats : construit tous les états de planification et les ajoute à la liste globale ETATS. Faites en sorte que la liste globale ETATS ainsi construite soit rangée par ordre croissant du numéro de l'état.
implementeMutexDePropositions : construit les contraintes binaires d'exclusion mutuelle entre propositions. Indication : utilisez les méthodes Etat.retourneVarInitiale() et Etat.retourneVarFinale(), qui retournent les variables associées à une proposition passée en paramètre.
implementeMutexDOperateurs : construit les contraintes binaires d'exclusion mutuelle entre opérateurs. Indication : utilisez la méthode Etat.retourneVarOperateur(), qui retourne la variable associée à un opérateur passé en paramètre.
implementeConditionsInitialesEtFinales : ajoute les contraintes initiales sur les propositions de l’état 0, et les contraintes finales sur les propositions de l'état final.
implementePreEtPostconditions : ajoute les contraintes de pré- et postconditions entre propositions et opérateurs.
implementeAxiomesDeCadre : ajoute les contraintes d'axiomes de cadre, en utilisant la classe ContrainteAxiomeCadre.

Testez votre programme. Vous pouvez appeler la fonction affichePSC pour détecter des éventuelles erreurs dans votre PSC.

Copyright LIA - 2007. Author: vincent.schickel-zuber@epfl.ch - Created on 19 March 2007 - Last update on 05 April 2011 by Florent Garcin