Planification avec PSC

Durée estimée : 4 heures.

Objectifs de la série

Comment fonctionne un planificateur qui utilise un Problème de Satisfaction de Contraintes(PSC) pour trouver la solution.

É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 à deux 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 permet 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 PSC. Pour ce faire, vous allez procéder en deux étapes :

  1. Définition du problème de planification en termes de propositions et d’opérateurs ;
  2. 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 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.

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 d’eux (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.

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 trois 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 missionnaires.py

Ce fichier contient la routine qui définit les acteurs, operateurs, mutex et conditions de départ/fin du problème puis construit le problème de planification grâce à la classe Plan du fichier plan.py.

Vous trouverez une classe Operateur dans le fichier operateur.py

Une fois l’objet Plan construit, sa méthode resoudre utilise les outils de résolution de PSC développés les semaines précédentes pour résoudre le problème de planification.

Construction des propositions

Construisez les propositions du problème de planification. Une proposition est simplement représentée par une string. Stockez toutes les propositions dans une liste.

Construction des opérateurs

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

  • Le nom de l’opérateur à créer (similaire à la représentation des propositions).
  • La liste des préconditions (une liste de propositions).
  • La liste des postconditions (une liste de propositions).

Spécification des mutex de propositions

Définissez les mutex de propositions. Stocker les mutex dans une liste sous forme de tuples (prop1, prop2). Prop1 et prop2 sont 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 de la même manière que les mutex de propositions (liste de tuples) avec op1 et op2 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 avec deux listes de tuples (proposition, valeur).

Exercice 3 : Implémentation des fichiers axiomecadre.py, etat.py et plan.py

Ces fichiers 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 dans le module psc.

La classe ContrainteAxiomeCadre

Cette classe (dans axiomecadre.py) est une sous-classe de psc.Contrainte, et implémente une contrainte d’axiome de cadre pour un état Si donné et une proposition prop donnée :

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

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

  • var_pre est la variable prop(Si).
  • var_post est la variable prop(Si+1).
  • vars_ops est la liste des variables correspondant aux opérateurs qui ont prop comme postcondition.

La méthode est_valide

Il vous faut tout d’abord implémenter la méthode est_valide. 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(Si) = False, et qu’on désire propager aux variables d’opérateurs les conséquences de l’assignation prop(Si+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(Si+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 d’ores 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 est_valide, 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 six attributs :

  • vars_initiales : 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.
  • vars_finales : un dictionnaire de variables associées aux propositions à la fin de l’état (égales à celles du début de l’état suivant).
  • vars_operateurs : 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, Plan.nb_etats].
  • etat_prec: l’objet Etat qui précède l’objet courant dans le Plan.

Le constructeur vous est donné, et appelle les méthodes construire_vars_operateurs et construire_vars_propositions, qui remplissent les attributs vars_operateurs, et vars_initiales et vars_finales (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 Plan

La classe Plan 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 :

  • propositions, operateurs, mutex_propositions, mutex_operateurs, depart, but qui sont les listes construites dans missionnaires.py.
  • nb_etats : le nombre d’états dans le plan, c’est à dire, la longueur du plan.
  • etats: la liste des états du problème.
  • psc : l’instance de PSC qui représente le problème modélisé en PSC.

Les méthodes de classe

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

  • contruire_etats : construit tous les états de planification et les ajoute à la liste self.etats. Faites en sorte que la liste soit rangée par ordre croissant du numéro de l’état.
  • constuire_contraintes_propositions : construit les contraintes binaires d’exclusion mutuelle entre propositions.
  • construire_contraintes_operateurs : construit les contraintes binaires d’exclusion mutuelle entre opérateurs.
  • construire_contraintes_initiales et construire_contraintes_finales: ajoute les contraintes initiales sur les propositions de l’état 0, et les contraintes finales sur les propositions de l’état final.
  • constuire_contraintes_conditions: ajoute les contraintes de pré- et postconditions entre propositions et opérateurs.
  • construire_contraintes_axiomes_cadre: ajoute les contraintes d’axiomes de cadre, en utilisant la classe ContrainteAxiomeCadre.

Testez votre programme.