Intelligence Artificielle : Logique et Contraintes


Bilan de la session 1 :

L'objectif de cette session a été de présenter le cadre général des problèmes de satisfaction de contraintes. Nous avons vu comment formaliser de tels problèmes, et étudié les principes de base des méthodes et algorithmes que l'on retrouve au coeur de la plupart des systèmes de résolution de contraintes.

Ces méthodes utilisent à la fois : Nous avons vu comment ces deux notions peuvent être intégrées dans le cadre d'algorithmes hybrides paramétrables et dont nous avons présenté différentes variantes.

Il vous appartient de bien apprendre le cours et de vous assurer que vous avez bien compris toutes les notions qui ont été présentées. Vous pouvez utiliser les 2 quizz qui vous ont été transmis pour vous auto-évaluer. Vous devez être capable de traiter des exercices similaires à ceux qui ont été abordés en TD de façon efficace. Pour cela, n'hésitez pas à réappliquer les différentes exercices sur les différents problèmes ou des variantes que vous pouvez créer à votre guise.

Session 2 :

Dans cette session nous allons aborder des aspects plus pratiques et notamment effectuer des travaux pratiques sur machine. Afin de pouvoir les effectuer dans de bonnes conditions il vous est demandé :

TD 6 (sur machine)

Archive à télécharger

Rappel : vous pouvez décompresser une archive au format .tgz l'aide la ligne de commande :
tar xzf nom_de_l'archive

TD 7 (sur machine)

Archive à télécharger et contenant des dossiers correspondant aux problèmes de la feuille de TD 7.

Vous pouvez placer cette archive directement dans le dossier opl créé lors du td6 et la décompresser avec la commande tar xzf archiveTD7.tgz, afin que les dossiers de ces nouveaux problèmes se retrouvent au même niveau que ceux du problème des billes et du carré latin.

Remarque : Chaque dossier contient un fichier .txt avec l'énoncé originel du problème. Pour ne pas perdre de temps n'hésitez pas à recopier si nécessaire les phrase décrivant les contraintes, pour les mettre en commentaires dans vos modèles.

TD 8 (sur machine)

Contrôle de la recherche

TD 9 (sur machine)

Optimisation sous contraintes

TD 10 (sur machine)

Archive à télécharger et contenant le dossier correspondant au problème de la feuille de TD 10.

TD 11 (sur machine)

Contraintes Globales (1)

Archive à télécharger et contenant le dossier correspondant au problème de la feuille de TD 11.

TD 12 (sur machine)

Contraintes Globales (2)

Archive à télécharger et contenant le dossier correspondant au problème de la feuille de TD 12.

Pour réviser

Enoncé du sujet d'examen sujet 2018


Devoir

Vous pouvez télécharger le sujet (v2) du devoir.

[2019/02/08] Vous pouvez à présent télécharger une archive vous indiquant la façon de structurer votre code de façon adéquate, et contenant les les librairies et données présentées dans le sujet du devoir.

[2019/02/12] L'énoncé a été mis à jour (correction de l'erreur concernant le 1er soin de Jean_DUPONT et de quelques typos).

[2019/03/11] Un serveur OSRM a été mis en place sur le réseau des machines du département. Il est accessible en interne via : http://osrm.dep-informatique.u-psud.fr:5000 (sur le port 5000).

A partir de l'extérieur (e.g. depuis chez vous) il est possible d'y accéder en vous connectant par ssh sur sur l'une des passerelles tp-sshX du département (c.f. https://www.dep-informatique.u-psud.fr/node/350)

[2019/03/13] La DI de l'université a ouvert le traffic vers le serveur OSRM interne. Vous pouvez donc directement y accéder à partir de votre machine personnelle depuis l'extérieur de l'université, sans avoir besoin de passer par ssh.

[2019/04/08] Précisions sur format demandé pour les résultats (voir ci-dessous)

[2019/04/09] Nouvelle version de l'archive avec des instances et le code fourni pour l'affichage et la sauvegarde.

Précisions sur le format adopté pour sauvegarder les résultats

Afin de simplifier la sauvegarde des résultats et d'homogénéiser la visualisation des solutions de vos modèles sur une carte on se propose de modéliser l'ensemble des informations relatives aux planning de l'infirmière (des infirmières) par : Une étape correspond correspond ici :

Code additionnel fourni :

Afin d'éviter toute ambiguité, la structure permettant de représenter une étape vous est donnée dans le fichier structuresResultat.mod.
tuple Etape {
	string infirmiere;	// la chaine correspondant au nom de l'infirmière
	int	etape;		// numéro d'étape pour le planning de l'infirmière (0 pour la premier passage au cabinet)
				// nb s'il y a plusieurs infirmières qui travaillent, chacune d'entre elle a une étape 0.
	string visite;		// Nom du Patient visité ou "cabinet" (pour première et la dernière étape d'un planning )
	string adresse; 	// Adresse (au format string) du patient ou du cabinet (telle que dans l'instance)
	float latitude; 	// Latitude de l'adresse 
	float longitude;	// Longitude de l'adresse 
	string description;	// codes de soins ou "Depart Bureau" ou "Transmissions"
	int debut;      	// horaire (en mn) du début de l'étape (entier compris entre 0 et 1439)
	int duree;      	// (durée de la visite en mn) ou  0 (pour la premire étape) ou durée des transmissions (en mn)
	int fin;      		// horaire de la fin de l'étape (en mn) du début des soins (entier compris entre 0 et 1439)
	int transit; 		// vers l'étape suivante (O si c'est la dernière étape)
}
Remarques :

Sauvegarde des résultats

On souhaite sauvegarder les résultats dans un fichier .res dont la syntaxe est similaire à celle des fichiers .dat, de façon à pouvoir relire par la suite ces données pour les vérifier automatiquement.

Une bonne nouvelle c'est que vous trouverez dans le fichier ../libs/results.js une fonction save_result(cost,steps,modelName) qui permet de sauvegarder directement le résulat au format demandé.
Vous n'avez donc pas à écrire de code pour cela.
Cette fonction à trois paramètres, correspondant respectivement au coût optimal (l'objectif de votre modèle), à l'ensemble d'étapes de vos plannings, et au nom du fichier de modèle ayant permi de produire cette solution.

En pratique, la seule chose que vous avez donc à faire consiste à :
  1. définir dans votre fichier de modèle une variable modelName que vous initialiserez avec le nom du fichier correspondnant au modèle :
    Exemple : string modelName = "visite1";
  2. définir dans la partie posttraitement une variable optimum que vous initialiserez avec la valeur de votre objectif (qui peut varier suivant les modèles)
    Exemple : int optimum = la valeur de votre objectif;
  3. définir dans la partie posttraitement une variable steps correspondant à un ensemble d'étapes (initialisée à l'ensemble vide au au départ)
    Exemple : {Etape} steps = {};
  4. ecrire un bloc de script qui, à partir de valeurs de vos variables de décisions et de celles initialisées lors du prétraitement, ajoute les différentes étapes des plannings dans l'ensemble steps
  5. appeler dans un bloc de script la fonction save_result(optimum,steps,modelName);
Les fichiers modèles de la nouvelle version de l'archive montre un exemple de structuration adéquate. Le code mutualise cette partie dans un fichier postProcessing.mod qui ne vous reste qu'à complèter. Remarque : Si vous inspectez les tuples créés dans le fichier résultat, vous pourrez noter que les attributs des tuples ne sont pas séparés par des virgules. Il en est de même des éléments constituant
Il est néanmoins possible de relire directement de tels fichiers, comme s'ils avaient la syntaxe Opl dans un fichier .dat, qui peut permettre ensuite de vérifier automatiquement les solutions.

Visualisation des solutions

Sous réserve d'avoir bien défini dans votre modèle les trois variables modelName, optimum et steps, vous pouvez également ajouter en fin de posttraitement la ligne
include "postProcessingMap.mod";
Ceci a pour effet de convertir les données décrivant les plannings construits et celles utiles à leur visualisation sur une carte OpenStreetMap dans la syntaxe javascript. Le fichier dataVis.js est généré dans le répertoire ../visualizaton. Il vous suffit alors d'ouvrir avec votre navigateur préféré le fichier map.html situé dans le répertoire ../visualizaton pour visualiser l'ensemble des plannings construit par votre modèle.

Exemple :

[Visualisation d'une solution sur une carte OpenStreetMap']

Mise à jour de l'archive

Vous pouvez télécharger une nouvelle version de l'archive, qui contient le code évoqué ci dessus ainsi que quelques instances que vous utiliser pour tester vos modèles.
Merci de signaler rapidement tout problème éventuel.
Attention à ne pas écraser le travail réalisé en décompressant cette nouvelle archive.
Procédez plutot en regardant ce qui a été modifié dans la nouvelle archive pour l'intégrer progressivement à votre travail.

Report de la date de rendu du devoir

La date limite pour le rendu du devoir est reportée au 10/05/2019 - 23h59

Questions posées sur le devoir




Utilisation de git pour ce cours

Lors du TD 6, il vous a été demandé :
  1. pour chacun d'entre vous, de vous créer un compte sur bitbucket.org
  2. pour chaque binôme, que l'un des membres du binôme crée une archive pour ce cours et donne accès à cette archive à l'autre membre du binome. (vous pouvez aussi créer une autre archive dans le seul but de vous entrainer avec les commandes de git).
  3. de faire chacun un clone de cette archive sous votre compte utilisateur.
A présent, vous allez pouvoir à chaque séance compléter cette archive en rajoutant au fur et à mesure de la résolution des différents problèmes abordés, les codes source correspondants. Pour cela, vous devrez apprendre à vous servir des commandes suivantes : D'autres commandes utiles : Quelques conseils :

Si vous faites attention à ne pas travailler à plusieurs simultanément sur des mêmes parties de projet, vous pouvez déjà gagner énormément en compétence en utilisant régulièrement ces commandes de base.

Naturellement, git permet de faire des choses plus avancées. Le site de référence concernant git est https://git-scm.com.

Vous trouverez une traduction francaise du livre "Pro Git" accessible en ligne à : https://git-scm.com/book/fr/v2.

Comment obtenir la suite IBM ILOG CPLEX Optimization Studio 12.8 (étudiants) ?

IBM a un certain nombre d'accords avec diverses institutions du monde académique et par ce biais, permet aux étudiant pouvant justifier de leur statut d'accéder à un certain nombre de ressources.

Cela nécessite un enregistrement préalable en tant qu'utilisateur étudiant, pour laquelle vous devrez utiliser votre adresse email @u-psud.fr.
Vous pourrez ensuite télécharger la suite en suivant le lien suivant :

https://ibm.onthehub.com/WebStore/OfferingDetails.aspx?o=733c3d21-0ce1-e711-80fa-000d3af41938&pmv=00000000-0000-0000-0000-000000000000
-->

Rédacteur de cette page (pour toute remarque) : Philippe Chatalic.