Upload
vuquynh
View
223
Download
1
Embed Size (px)
Citation preview
Intelligence artificielle et Rechercheoperationnelle
M1 SIRPhilippe Muller
et Matthieu Serrurier,Marie-Christine Lagasquie
2015-2016
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Introduction
structure du cours
intervenants
introduction au contenu
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Trois parties
resolution de problemes combinatoires
systemes de contraintes
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Trois intervenants
resolution de problemes combinatoires : Matthieu Serrurier
systemes de contraintes : Philippe Muller
un renfort en TP : Marie-Christine Lagasquie
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Ce qu’on verra...
Toujours deux versants
modelisation de problemes
resolution de problemes
→ “systemes decisionnels”
et mise en pratique en TP
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Domaines vises
problemes mal poses ou mal definis
domaines en friche
problemes complexes ou tres larges
problemes pour lesquels on ne connaıt pas d’algorithmes“efficaces” (rapides) ou ne donnant pas de “bonnes” solutions.
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Une methodologie commune
1 modelisation d’un domaine ou d’un probleme particulier
2 representation
3 resolution (algorithmique, raisonnement, optimisation,apprentissage)
4 evolution
L’etape (3) necessite des recherches dans des ensembles depossibilites tres grands → “recherche operationnelle”.
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Humains, robots, machines, etc : “systemes decisionnels”
une notion commune : la notion d’agent rationnel
recoit de l’information d’un environnement (perception)
agit sur l’environnement (action)
en fonction de l’information recue et traitee (decision)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Caracteristiques de l’agent rationnel
perception : necessite representation de l’environnement
action : representation des actions possibles
decision : processus
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple chercher son chemin
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Un exemple : chercher son chemin
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Un exemple : chercher son chemin
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple trouver son chemin
representation : graphe / grille
actions : deplacements ds une direction
decision : arriver au but + optimiser : quelles procedures ?
→ analogue a trouver une solution parmi un ensemble de possibles
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Resolution de problemes
Exemple simplet :Un berger veut transporter d’un cote d’une riviere a l’autre :
une chevre, un chou, un loup
laisses seuls, la chevre mange le chou
laisses seuls, le loup mange la chevre
son bateau ne peut prendre a bord que deux choses en plus delui-meme
comment s’y prendre pour eviter le carnage ?
representation des donnees ?
actions possibles ?
qu’est-ce qu’une resolution ?
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Resolution d’un probleme ”combinatoire”
A peine moins simplet : les missionaires et les cannibales
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Les cannibales (suite)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Les cannibales (suite)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Les cannibales (suite)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Planification
”monde des cubes” : idealisation d’un probleme general
nombre d’etats possibles ?augmente tres (trop rapidement)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple reel : installation de relais satellites
[stage M2 SIR / 2013 — Astrium]
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Petit Exemple
on dispose de deux recipients initialement vides, pouvantrespectivement contenir 3 litres et 4 litres d’eau.
on peut remplir completement un recipient au robinet, le vidercompletement dans l’evier, ou bien vider un recipient dansl’autre jusqu’a remplir le deuxieme ou bien vider un recipientdans l’autre jusqu’a vider le premier.
on veut arriver a avoir 2 litres d’eau exactement dans lerecipient de 4 litres.
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple : Die Hard
(3L,4L)(0,0)(3,0) remplir 3(0,3) vider 3 dans 4(3,3) remplir 3(2,4) remplir 4 avec 3(2,0) vider 4(0,2) vider 3 dans 4
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exercice : ordonnancement
modeliser le probleme d’ordonnancement suivant :on a 4 taches a realiser de durees 5, 1, 3, 4
— les taches 2 et 3 ne peuvent etre faites en parallele (memesressources necessaires),— la 3 doit etre faite avant la 4.peut-on avoir toutes les taches commencees finies avant t=7 ?
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple avec optimisation : Pandemie
Une epidemie de maladie infectieuse a ete observee dans un certainnombre N d’endroits. Un ensemble de M equipes de medecinsdoivent aller enqueter pour identifier la maladie, ce qui leur prendun certain temps tij qui depend de l’endroit j et de l’equipe i .Chaque equipe peut enqueter au maximum a 2 endroits, mais doitalors se deplacer de l’endroit j1 a l’endroit j2, ce qui prend untemps dj1j2 .Peut-on trouver une solution prenant moins de 20 unites de temps ?Bonus : quel est le minimum qu’on puisse trouver ?
Eq / Lieu 1 2 3 4
1 10 12 14 52 6 10 10 43 12 12 16 6
Lieu 1 / 2 1 2 3 4
1 6 6 82 7 83 5
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Problemes combinatoires classiques
sac a dos ; ex : (12 4 5 7 3 18) dans 20 litres
demenagement
voyageur de commerce
coloriage de graphes
etc
versions ”idealisees” de nombreux problemes reelsexplosion du nombre de possibilites
probleme de resolution vs. probleme d’optimisation
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Systemes de contraintes
processus de recherche de solutions dans un cadre plusspecifique
uniquement des ”faits” : variables avec domaines restreints +relations entre variables
recherche d’instances des variables satisfaisant les relations(”contraintes”)
applications : partout (emploi du temps, occupation de salles,logistique, etc)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Systemes de contraintes
des variables {V1,V2,V3, ...}des domaines de valeurs : V1 ∈ D1,V2 ∈ D2, ...
des contraintes entre variables : ex V1 6= V2, V3 ≤ V4
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple
5 personnes de 5 metiers differents dans 5 maisons de couleursdifferentes, avec un animal domestique et une boisson prefereedistincte.
L’anglais habite dans la maison rouge.
L’espagnol a un chien.
Le japonais est peintre.
L’italien boit du the.
Le norvegien habite la premiere maison.
L’habitant de la maison verte boit du cafe.
La maison blanche est juste apres la verte.
Le sculpteur eleve des escargots.
Le diplomate habite la maison jaune.
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple (suite)
On boit du lait dans la 3e maison.
La maison du norvegien est a cote de la bleue.
Le violoniste boit du jus de fruit.
Le renard est dans la maison voisine du docteur. (plus simple :apres)
Le cheval est la maison voisine de celle du diplomate. (plussimple : apres)
(indice) Le zebre est dans la maison verte.
Une des personnes boit de l’eau.
Qui habite ou ?
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Modelisation
quelles variables ?
quels domaines ?
representation
resolution ”a la main”
resolution : variante des algorithmes de recherche (cf cours 1)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Variables et domaines
maison, couleur, metier, pays, boisson, animal ?
1 maisons ∈ {1, 2, 3, 4, 5} (dans l’ordre)
2 il y a une valeur seulement de metier, animal, etc par maison
3 toutes les variables peuvent etre associees a une valeur demaison : 1, 2, 3, 4, 5
4 donc 5 variables par proprietes = 25 variables, chacune dedomaine {1, 2, 3, 4, 5}
5 pas de variables pour la maison
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Demarrage
contrainte generale : chien6= chat, chat6= cheval, etc sur les 5familles de variables
L’anglais habite dans la maison rouge.rouge=anglais
L’espagnol a un chien.espagnol=chien
Le japonais est peintre.japonais=peintre
L’italien boit du the.italien=the
Le norvegien habite la premiere maison.norvegien=1
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
L’habitant de la maison verte boit du cafe.vert=cafe
La maison verte est juste apres la blanche.vert=blanche+1
Le sculpteur eleve des escargots.sculpteur=escargot
Le diplomate habite la maison jaune.jaune=diplomate
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Suite
On boit du lait dans la 3e maison.lait=3
La maison du norvegien est a cote de la bleue.|norvegien − bleue| = 1
Le violoniste boit du jus de fruit.violoniste=jus
Le renard est dans la maison apres celle du docteur.renard=docteur+1
Le cheval est la maison apres celle du diplomate.cheval=diplomate+1
Le zebre est dans la maison blanche.zebre=blanche
Une des personnes boit de l’eau.
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Resolution
1 recherche arborescente dans les valeurs possibles
2 propagation des contraintes
ex : domaine de norvegien=1 → on remplace partout dans lesautres
1 1 devient impossible pour espagnol, italien, etc
2 bleu ∈ {0, 2} ∩ D(bleu) = {2}
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
animal chien = 4, renard = 1, cheval = 2, escargot = 3,zebre = 5,
color bleu = 2, vert = 5, rouge = 3, blanc = 4, jaune = 1,
drink cafe = 5, jus = 4, lait = 3, the = 2, eau = 1,
nationality angl = 3, ital = 2, jap = 5, norv = 1, espagnol = 4,
profession diplomate = 1, docteur = 2, peintre = 5, sculpteur= 3, violiniste = 4
ici : uniquement par propagation de contraintes
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exercices : ordonnancement
modeliser le probleme d’ordonnancement suivant :on a 4 taches a realiser de durees 5, 1, 3, 4
— les taches 2 et 3 ne peuvent etre faites en parallele (memesressources necessaires),— la 3 doit etre faite avant la 4.peut-on avoir toutes les taches commencees finies avant t=7 ?
reprendre comme un probleme de satisfaction de contraintes
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Adaptation
1 representation et raisonnement pas toujours suffisant
2 evolutivite d’un systeme
3 adaptation au changement
4 peut-on faire de l’”apprentissage” automatiquement ?(→ en M2)
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Exemple : diagnostic
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Apprendre les regles
Cas Previsions Temperature Humidite Vent SportE1 Soleil Chaude Elevee Faible NONE2 Soleil Chaude Elevee Fort NONE3 Couvert Chaude Elevee Faible OUIE4 Pluie Douce Elevee Faible OUIE5 Pluie Froide Normale Faible OUIE6 Pluie Froide Normale Fort NONE7 Couvert Froide Normale Fort OUIE8 Soleil Douce Elevee Faible NONE9 Soleil Froide Normale Faible OUIE10 Pluie Douce Normale Faible OUIE11 Soleil Douce Normale Fort OUIE12 Couvert Douce Elevee Fort OUIE13 Couvert Chaude Normale Faible OUIE14 Pluie Douce Elevee Fort NON
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle
Apprendre les regles
Sport ?
prevision meteo
humidite
NON
forte
OUI
normale
soleil
OUI
couvert
vent
NON
fort
OUI
faible
pluie
M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle