Lab 9 : 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 -------- - :download:`libPSC.py <../../exercises/hw9/libPSC.py>` - :download:`PSC.py <../../exercises/hw9/PSC.py>` - :download:`libPlan.py ` - :download:`missionnairesTemplate.py <../../exercises/hw9/missionnairesTemplate.py>` - :download:`planificateurTemplate.py <../../exercises/hw9/planificateurTemplate.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. .. admonition:: Remarque :class: note 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. .. admonition:: Remarque :class: note 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. .. note:: 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. .. note:: 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. .. admonition:: Remarque :class: note 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. .. note:: 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 :py:class:`.Operateur` et :py:class:`.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 :py:func:`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 :py:class:`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 :py:func:`libPlan.ProblemeDePlanification.ajouteOperateur()`. Spécification des mutex de propositions ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Définissez les mutex de propositions à l'aide de la méthode :py:func:`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 :py:func:`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 :py:func:`libPlan.ProblemeDePlanification.ajouteConditionInitiale()` et :py:func:`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 :py:class:`.ContrainteAxiomeCadre` ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Cette classe est une sous-classe de libPSC.Contrainte, et implémente une contrainte d'axiome de cadre pour un état S\ :sub:`i` donné et une proposition prop donnée : Si prop(S\ :sub:`i`) = False et prop(S\ :sub:`i+1`) = True, alors pour au moins un opérateur op qui a prop comme postcondition, on a op(S\ :sub:`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\ :sub:`i`) ; - ``varPost`` est la variable prop(S\ :sub:`i+1`) ; - ``varsOp`` est la liste des variables correspondant aux opérateurs qui ont prop comme postcondition. La méthode :py:func:`~planificateur.ContrainteAxiomeCadre.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 :py:func:`~planificateur.ContrainteAxiomeCadre.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\ :sub:`i`) = False, et qu'on désire propager aux variables d'opérateurs les conséquences de l'assignation prop(S\ :sub:`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\ :sub:`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 :py:class:`.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 :py:func:`~planificateur.Etat.construitVariablesOperateurs` et :py:func:`~planificateur.Etat.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. .. note:: 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 :py:class:`.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 : - :py:func:`~planificateur.PlanificateurPSC.contruitEtats` : 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. - :py:func:`~planificateur.PlanificateurPSC.implementeMutexDePropositions` : construit les contraintes binaires d'exclusion mutuelle entre propositions. Indication : utilisez les méthodes :py:func:`~planificateur.Etat.retourneVarInitiale` et :py:func:`~planificateur.Etat.retourneVarFinale`, qui retournent les variables associées à une proposition passée en paramètre. - :py:func:`~planificateur.PlanificateurPSC.implementeMutexDOperateurs` : construit les contraintes binaires d'exclusion mutuelle entre opérateurs. Indication : utilisez la méthode :py:func:`~planificateur.Etat.retourneVarOperateur`, qui retourne la variable associée à un opérateur passé en paramètre. - :py:func:`~planificateur.PlanificateurPSC.implementeConditionsInitialesEtFinales`: ajoute les contraintes initiales sur les propositions de l’état 0, et les contraintes finales sur les propositions de l'état final. - :py:func:`~planificateur.PlanificateurPSC.implementePreEtPostconditions`: ajoute les contraintes de pré- et postconditions entre propositions et opérateurs. - :py:func:`~planificateur.PlanificateurPSC.implementeAxiomesDeCadre`: ajoute les contraintes d'axiomes de cadre, en utilisant la classe :py:class:`.ContrainteAxiomeCadre`. Testez votre programme. Vous pouvez appeler la fonction :py:func:`~planificateur.PlanificateurPSC.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