42
Intelligence artificielle et Recherche op´ erationnelle M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine Lagasquie 2015-2016 M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine Lagasquie Intelligence artificielle et Recherche op´ erationnelle

Intelligence artificielle et Recherche opérationnellePhilippe.Muller/Cours/M1_CSP/introia_1516.pdf · Exercice : ordonnancement mod eliser le probl eme d’ordonnancement suivant

  • 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

Decision sur un nouveau cas ?

si Soleil+Temperature chaude+Humidite normale+Vent fort ?

prevision meteo

humidite

OUI

normale

soleil

M1 SIR Philippe Muller et Matthieu Serrurier, Marie-Christine LagasquieIntelligence artificielle et Recherche operationnelle