IFT3330 ? Intelligence artificielle Filipe Langlais ? 2233 felipe@iro ...
Le principe de cette philosophie repose sur le principe régulateur binaire de l'
univers ..... desquels l'acheteur ne doit pas exiger, quel que soit leur désir de le
faire. ... Prix qui serait déterminé par le jeu naturel entre l'offre et la demande (
textes 1, 2, 3, ..... Cette analyse monétaire, mettant l'accent sur les quantités de
métaux ...
part of the document
IFT3330 Intelligence artificielle
Filipe Langlais 2233 felipe@iro.umontreal.ca
HYPERLINK "http://www.iro.umontreal.ca/~felipe/IFT3330-Automne2006/" http://www.iro.umontreal.ca/~felipe/IFT3330-Automne2006/
Cours 1, mardi 5 septembre 2006
TPs (15% - 15% - 15%)
Intra: 20%
Final: 35%
Agent: Unité interagissant (humain ou robot...)
[Possède une fonction]
Senseur: Permet d'obtenir de l'information de l'environnement.
Actuateur: Permet d'agir
pp.19-21
Rationnel? ( Fait le mieux possible selon une mesure de performance (métrique).
p.26: ex.: Jeu d'échecs sans temps (dynamique) ou avec temps limite (semi-dynamique)
p.27: static: au sens de variable persistente accessible à chaque exécution de la fonction... (mémoire)
Cours 2, mercredi 6 septembre 2006
Static: On a tout le temps voulu pour répondre (le monde est gelé)
Déterministe: On a toutes les informations.
états: villes
état initial: A
état final ( but = {ensemble d'états qui répondent au problème}
Successeur: successeur.fn[etat] ( {}
Ici: A a pour successeur C et D
Exemple de l'aspirateur:
États: 2 positions pour l'aspirateur x 22 pour la poussière... (énumérable au besoin)
État initial: (peu importe)
Successeur: succ(etat) ( noop
if dirty asp ( Un algorythme déterminant les possibilités
if propre ........
But: Tout est propre
Problème du '8' (p.3.19
)
États: toutes les config possibles... O(n!)
Successeur: 4 paires d'actions-état ...
Arbre de recherche:
arbre dont les noeuds sont les différents états...
nota: ne pas confondre les noeuds ds l'arbre avec les états... Les noeuds servent à la fonction de recherche ...
Noeud n:
state(n) est l'état associé au noeud n.
parent(n) est le noeud d'où l'on vient. (Utile, mais pas toujours!)
action(n) est l'action qui a permis de passer du parent au noeud actuel
path-cost(n) ou g(n) est le coût total du chemin parcourru. (Cumulatif)
depth(n) est la frofondeur du noeud dans notre arbre.
Frange (fringe): Ensemble des noeuds non encore étendus. (Une file/Queue)
Empty?(q)
First(q) retourne le 1er noeud dans q (peut être une queue ou une pile...)
Remove_First(q) retourne et retire ...
Insert(node,q)
Insert_All(nodes,q)
Cours 3, mardi 12 septembre 2006
Chapître 3 AIMA.
Recherches aveugles. Espace d'états.
Problème
INIT état initial
GOAL vérifie si un état est solution
SUCCESSOR_FN etat ( {} /e = succ(etat)
Frange
REMOVE_FIRST
EMPTY?
INSERT
INSERT_ALL
Node n
PARENT %node
PATH_COST %coût du chemin depuis l'état initial n
STEP_COST %coût d'une action
ACTION
STATE
function Tree_search (problème, frange)
frange ( Make_node( INIT(problème), frange)
loop do
if (empty(frange) return ECHEC
node ( remove_first(frange)
if (GOAL(problem, STATE(node))) return Solution(node)
frabge ( insert_all(EXPAND(problème,node),frange)
fonction EXPAND(problème, node) return ensemble de nodes
succ ( empty
foreach(action, etatsuivant) Îð Successor_fn(probleme, STATE(node))
s ( PATH_COST(node)+STEP_COST(STATE(node),action,etat-suivant)
add(succ, MAKE_NODE(node-parent, etat-suivant, action, s, DEPHT(node)+1)
return succ
STEP_COST(depart,action,arrivee) = 1 (pour le moment)
Recherche par largeur d'abord:
tree_search(probleme, fifo()) en java: Problem p = nre Problem();
Fifo q = new Fifo();
tree_search(p,q);
(Problem est une Interface qui force l'implémentation, par exemple, des méthode définie ci-haut. On utilisera alors une classe du type Aspirateur() qui hérite de Problem)
Note: Un algo de recherche est complet s'il trouve une solution dès lors qu'il en existe au moins une.
Un algo est optimal si la solution trouvée est toujours la meilleur selon la fonction de coût définie.
Complexité maximale (de l'algo): Temps: Nombre de noeuds visités.
Mémoire: Nombre de noeuds que l'on doit stocker en mémoire.
(nombre maximal de noeuds dans la frange)
Facteur de branchement: b Nombre maximum de successeur à un noeud.
Profondeur la plus petite d'une solution: d (la racine est de profondeur 0)
Profondeur maximale: m (de l'arbre de recherche)
Donc, largeur d'abord (pire des cas):
Complet? oui (sauf si b est infini)
Optimal? oui (parce que la fonction de coût est unitaire)
Complexité temporel? O(bd+1)
Complexité espace?
Uniform_cost_search: meilleur d'abord g(n) [le coût d'un chemin entre deux villes]
tree_search(problem, priority_queue()); REMOVE_FIRST retourne le noeud n de plus faible coût g(n)
complet? oui ((>0)
optimal? oui
Profondeur d'abord:
tree_search(problème, Stack())
complet? non (risque de tourner en rond (rien faire))
optimal? non
temps? O(bm) (voir infinie) ( ARK
espace? O(b(m)
Profondeur d'abord limité: (Soit l une limite)
Si un noeud est une profondeur l, l'état associé n'a pas de successeur.
complet? non (si la sol est sous la limite)
optimal? non
temps? O(bl)
espace? O(b(l)
Profondeur limité itérative:
for l(0 à (
if (prof_limitée(probleme, l))
succès
temps? O(bd) ( mieux que d+1 par rapport à largeur c surprenant, mais même si c
espace? O(b(d) lourd, c intéressant.
Cours 4, mercredi 13 septembre
function graph_search(problem, frange) retourne Solution ou Échec (va éviter le bouclage)
frange ( make_node (INIT(problem))
close ( ( % ensemble de tous els états déjà étendus
loop
if (EMPTY?(marge)) et Échec
node (REMOVE_FIRST(frange)
if (GOAL(STATE(node))
return SOLUTION(node)
if (STATE(node) ( close)
close ( close ( STATE(node)
marge ( INSERT_ALL(EXPAND(problem,node), frange)
Pour le jeu du cavalier:
SUCC(grille, i, j) retourne {(i',j')}
Grille:
SEARCH(Grille, i, j, nb)
if (nb > n2) sol(grille) % On a trouvé une solution
else
((i',j') ( Succ(Grille, i, j)
Grille[I',j'] = nb ( on ajoute la trace des cavaliers sur la même grille
SEARCH(Grille, i', j', nb+1)
Grille[I',j'] = 0 ( on rétabli à la sortie de cette branche...
meilleur d'abord: g(n) g(n): ma fonction à optimiser
h(n) greedy search h(n): une heuristique d'un expert...
f(n)=h(n)+g(n) A*
(exemple des villes vers Bukarest)
h(n): DONC: graph_search avec file de priorité (score)
heuristique:
h:E((
h(n) = 0 pour tout n sol
Définition: h est une fonction admissible ssi h(n)=0 pour tout noeud n, STATE(n) est une solution
h(n) est toujours une valeur inférieure au coût réel d'aller de n à un but donné.
- Le vol d'oiseau ne peut être qu'admissible pcq y'a pas mieux que la ligne droite.
Un théorème dit que si h est admissible, alors la solution trouvée par A* (avec TreeSearch) sera toujours optimale.
Démo 1, mercredi 13 septembre 2006
Marc Parisien
HYPERLINK "mailto:dift3330@iro.umontreal.ca" dift3330@iro.umontreal.ca
Dispo: Vendredi 9h à 12h au 3174AA
I) Théorique:
Missionnaire et cannibales...
Contrainte:
#M < #C laissés seuls ( pas de successeur.
Opérations possibles:
Bouger 1M
Bouger 1C
Bouger 2M
Bouger 2C
Bouger 1M+1C
Cours 5, mardi 19 septembre 2006
Codage: voir acétates...
main: new TreeSearch(new ProblemAspirateur(), new FIFO());
stateMC {
int M1, C1;
bool bateau;
}
Successeurs: 1M 1C / 2M / 2C / 1M / 1C
Note: A* est optimal si h est admissible avec TreeSearch, pas avec Graph-Search.
Théorème: Si h est consistante, alors A* avec GraphSearch est optimal.
Définition: h est consistante si (n, (n' ( Succ(n), alors h(n)d"c(n(n')+b(n')
g(n')-g(n)
Propriété: si h est consistant, alors elle est admissible
ex.: Heuristiques: (recette magique(h consistente)
h: Le nombre de pièces à la mauvaise place.
ici: 7
h1: Le nombre de cases (minimum) à se déplacer pour chaque pièce
ici: 3+2+2+2+2+2+4=17
(avec solution à 14 déplacements) (24 déplacements)
Statistiques: A* + h1 ( 539 >9000
A* + h2 ( 113 1641
Profondeur ( 3 000 000 54 000 000 000
Cours 6, mercredi 20 spetembre 2006
RÉSUMÉ:
Définitions: h admissible: h(n) d" b(n) (n {
