Chapitre 2 - Agents intelligents

Exercice 2.1

Quelques définitions...

Agent

Elément qui reçoit des informations de son environnement, les traite, et agit dans cet environnement. L'histoire ne dit pas si le comportement est rationnel, tout dépend de la qualité des signaux reçus, de la pertinence des traitements, de l'efficacité des actions.

Mais grosse maille, l'idée est là: INPUT -> PROCESS -> OUTPUT

Cela ne veut pas nécessairement dire qu'on peut modéliser un agent intelligent par un fonction en BASIC 1.0, ne me faites pas dire ce que je n'ai pas dit.

Fonction agent

Le rôle que remplit l'agent, son comportement modélisé dans son environnement.

Programme agent

Le sous-ensemble de l'agent (de la fonction agent?) qui se contente de traiter les infos reçues et d'en déduire les actions à mener. La case "PROCESS" dans ma description au lance-pierre de l'agent.

Rationalité

Capacité à prendre la "bonne" décision. La notion de bien et de mal n'est ici pas mystique mais doit être adaptée au contexte. Elle correspond en général à un critère d'efficacité. Mais entre faire "au plus vite", "au plus simple", ou "au moins cher", on n'obtient pas forcément les mêmes solutions. Le tout est de savoir ce qu'on cherche. A partir de là, on adopter - ou plutôt l'agent peut adopter - un comportement rationnel pour atteindre le but.

Autonomie

Capacité à se démerder tout seul. Comprendre ici, sans intervention d'agents extérieurs, en particulier un humain.

Agent réflexe

Agent dont le programme agent est une fonction (au sens informatique usuel) qui ne dépend que des paramètres de l'environnement à l'instant "t". Pas de notion d'état (stateless), pas de boucle (feedback), rien. Le cas de "base". Comportement sans surprise.

Agent fondé sur un modèle

Agent dont le programme peut faire appel à toutes sortes d'artifices techniques (en particulier la mémorisation des actions et des états précédents) mais dont les principes de fonctionnement sont connus. Typiquement le domaine fonctionnel a été analysé, on a conclu que tel et tel algorithmes étaient pertinents, on spécifie on code et c'est terminé. Suppose qu'on connaît bien le domaine. Et qu'il est possible de le connaître...

Agent fondé sur des buts

Ici l'agent essaye d'atteindre un "but" donné, sans nécessairement connaître le pourquoi du comment il faut faire pour l'atteindre.

Agent fondé sur l'utilité

A mon sens, c'est une variante de l'agent fondé sur le but, le but étant de maximiser une fonction "utilité". La notion d'heuristique n'est pas loin non?

Agent capable d'apprentissage

La réponse est dans la question: agent capable de modifier son comportement, de faire évoluer son programme agent en fonction des expériences précédentes.

Exercice 2.2

Différence entre fonction de performance et fonction d'utilité

A mon sens la fonction de performance est un indicateur global de bon fonctionnement de l'agent, qu'on utilise pour vérifier s'il est correct ou pas. Elle porte sur le but.

La fonction d'utilité, elle, est un artifice interne pour obtenir le bon comportement. Elle porte sur les moyens.

Imaginons un pilote automatique de bateau qui doit amener un rafiot de l'autre côté de l'Atlantique. La fonction de performance est simple: "dis papa c'est loin l'Amérique?". La fonction utilité, elle, contient des infos de navigation et va par exemple être de la forme "suis-je bien cap à l'Ouest, et est-ce qu'on avance?".

Exercice 2.3

Plusieurs programmes agents pour une fonction donnée?

J'aurais tendance à sortir l'argument cher à Larry Wall: TIMTOWTDI.

Oui, plusieurs programmes pour une fonction donnée, c'est possible, d'autant que les fonctions "intéressantes" en IA sont éminement sous-spécifiées. Sinon, vraisemblablement, on n'aurait pas besoin de l'IA pour traiter la question, un simple programme implémentant les spécifications très précises et détaillées (!) fournies en entrée suffirait.

Exemple d'implémentations multiples: fonctionnement d'un lampadaire, qui doit s'allumer quand il fait noir. 1er programme -> allume entre t1 et t2, t1 et t2 variant sur l'année pour s'adapter au changement d'heure du lever et du coucher de soleil. 2ème programme -> déclenchement à partir d'un détecteur de luminosité. 3ème programme -> se base sur un "top" d'EDF. 4ème programme -> mélange des trois précédents. On pourrait me rétorquer que les programmes sont différents parce que les entrées et les sorties, donc la perception de l'environnement (donc, du point de vue du programme, l'environnement lui-même) sont différents dans chaque cas. Dans la réalité il n'existe jamais d'environnement modélisable de façon canonique, il y a toujours interprétation, choix, compromis. La fonction intéressante, c'est allumer le lampadaire quand il faut. L'usager sera plus ou moins content selon la solution choisie, ce qui veut simplement dire que les programmes sont plus ou moins performants, mais ils remplissent tous la même fonction.

Fonctions agents impossibles à implémenter?

Un point de vue est de faire son vrai-faux petit malin et de déterrer le théorème d'incomplétude de Gödel, affirmant ainsique oui, certaines fonctions agents sont impossibles à implémenter.

Ce serait vrai si on imposait que la performance soit parfaite.

Si on accepte une performance dégradée, voire aléatoire, on peut implémenter n'importe quoi, y compris prédire l'avenir. C'est ce que fait un système expert en météorologie, ni plus ni moins. Nous mêmes, humains, sommes des agents intelligents qui estimons être capable de "plancher" sur n'importe quel sujet, mais avec - c'est parfois regrettable - plus ou moins de succès.

Un autre moyen d'être capable de "tout coder" tout en restant parfait est de disposer de ressources matérielles illimitées, quitte à augmenter le nombre d'atomes dans l'univers. Pas simple 8-)

Un programme agent -> une fonction agent?

Sur une machine physique donnée, un programme ne pourra représenter qu'au maximum une fonction agent. A moins de changer la signification des entrées-sorties, ou de considérer une fonction composite "lire et écrire" comme deux fonctions "lire" et "écrire".

Mais plusieurs programmes peuvent correspondre à une seule fonction.

Combien de fonctions implémentables avec n-bits de stockage?

En théorie 2^n.

Dans la pratique, largement moins, la plupart des séquences de bits n'ayant pas de sens.

Exercice 2.4

Rationnalité de la fonction aspirateur

Difficile de ne pas tomber dans le raisonnement circulaire...

Mais bon, l'idée d'une démonstration propre serait de montrer par A+B que le choix:

1. aspirer quand c'est sale
2. aller voir ailleurs quand c'est propre

est plus efficace que l'inverse:

1. aller voir ailleurs quand c'est sale
2. aspirer quand c'est propre

Logiquement la fonction de performance qui cherche à minimiser le nombre d'opérations (le temps?) pour arriver à "propre partout" est le mieux satisfaite quand on fait les choix évidents à court terme. Ce n'est pas forcément le cas général.

Comment gérer les mouvements inutiles?

Oui certes, avec notre agent simpliste, l'aspirateur risque de faire du gauche droite gauche droite ad vitam eternam si c'est propre partout.

Dont acte, pour prendre ça en compte il faut stocker en interne l'historique des actions et/ou des états, et prendre la décision de se déplacer quand on n'a rien fait ou que la situation n'a pas changé depuis "suffisamment longtemps".

Pour savoir comment qualifier le "suffisamment longtemps" il faudrait avoir une idée statistique de combien de temps met une case à se salir. Ou bien concevoir un système à apprentissage.

Cas où les cases peuvent devenir sales, géographie inconnue

Ah mince j'avais mal lu l'énoncé... Je pensais acquis que les cases pouvaient devenir sales. Zut. Pas le courage de revoir mes réponses aux questions précédentes, en plus, c'est plus rigolo de traiter le cas compliqué.

Pour ce qui est de la géographie inconnue, clairement il faut introduire des techniques (ce n'est pas exclusif) du type:

• mémorisation du parcours pour être certain ou au moins maximiser les chances de passer "partout"
• choix aléatoire d'actions pour éviter les boucles infinies
• apprentissage afin de calibrer le ratio aspiration/déplacement

D'une manière générale, à partir du moment où la géographie est inconnue, il est impossible de construire une table exhaustive des situations et des actions idéales correspondantes, or donc n'importe quelle technique d'IA est pertinente, c'est un problème ouvert.

Exercice 2.5

Description PEAS (performance - environnement - effecteurs - capteurs) de quelques systèmes choisis.

Robot joueur de foot

• performance: score de l'équipe
• environnement: ballon, durée de jeu restant, coéquipiers, adversaires, arbitre, météo
• capteurs: capteur visuel, capteur auditif (messages équipiers & arbitre), capteur sensitif (toucher de ballon)
• effecteurs: pieds bioniques, tête

Acheteur de livres sur le web

• performance: livres pas chers, livres intéressants, livres non seulement commandés mais aussi et surtout livrés (vendeur fiable)
• environnement: humain qui lira les livres,serveurs web des marchands en ligne, mail
• capteurs: interpréteur des demandes de l'humain,analyseur de pages web, lecteur de mail
• effecteurs: requêteur http(s), envoi de mail

Robot martien

• performance: nombre de photos effectuées, surface parcourue
• environnement: sol, station terrestre
• capteurs: capteur sensitifs pour le sol, camera, thermomètre, altimètre, boussole?, accéléromètre
• effecteurs: appareil photo pour prises de vues, moteur et roues, radio pour envoyer des infos à la terre

Assistant mathématicien

• performance: temps mis à trouver une solution et une réponse vrai ou faux
• environnement: mathématicien, base de données sur les théorèmes existants
• capteurs: interpréteur de fichiers au format ad hoc
• effecteurs: indicateur d'état "je bosse/c'est foutu/j'ai trouvé", générateur de fichier décrivant la solution (démonstration) trouvée s'il y en a une

Exercice 2.6

Les environnements de l'exercice précédent sont-ils:

• entièrement / partiellement observables?
• déterministes / stochastiques?
• épisodiques / séquentiels?
• statiques / dynamiques?
• discrets / continus?
• mono / multi agents?

Robot joueur de foot

• partiellement observable
• stochastique
• séquentiel
• dynamique
• continu
• multi agents

Acheteur de livres sur le web

• totalement observable (on suppose qu'on se limite à N vendeurs connus)
• déterministe (soyons optimistes!)
• épisodique (chaque achat de livre est indépendant)
• dynamique (évolution permanente des stocks, c'est du vécu)
• discret
• mono agent (humain et serveurs vus comme du magma dans l'environnement)

Robot martien

• partiellement observable
• stochastique
• séquentiel
• statique (on suppose qu'il n'y a pas de martiens, on néglige les changements de climat, de luminosité)
• continu
• mono agent

Assistant mathématicien

• totalement observable
• déterministe
• épisodique
• statique
• discret
• mono agent

Exercice 2.7

A partir de maintenant, ça parle aspirateur.

Programmation d'un simulateur de l'environnement de l'aspirateur.

J'ai écrit quelques lignes de code Guile mais très vite, désintérêt total, ça doit être le fait d'avoir passé des heures, des jours, des semaines, des mois, des années à programmer des jeux vidéos qui me rend ce type de tâche assez rébarbative et pas très... fun.

Exercice 2.8

Programmation de l'aspirateur lui-même.

Conséquence directe de l'exercice précédent, plus de courage pour implémenter l'aspirateur. J'ai toujours eu horreur des aspirateurs. J'imagine que ça doit pas être bien plus compliqué que la prorgammation d'un "agent combattant" de Liquid War. Non?

Exercice 2.9

Avec une pénalisation d'un point par mouvement:

  * a) l'agent réflexe pur a du mal à être optimal car pour avoir le meilleur comportement il faut prendre en compte le nombre de coups, ne pas ré-aspirer un truc déjà aspiré par exemple. Pour cela il faut garder en mémoire ce qu'on a fait avant -> on passe en mode "statefull", donc pas de réflexe pur, mais un mode de fonctionnement qui prend en compte le passé, les états/actions antérieures;
  * b) je pense qu'en gardant un historique des différents états, on doit arriver à  produire un agent réflexe correct, en imaginant qu'il n'aspire pas deux fois la même case (on suppose ici que tout ne se resalit pas dans son dos...);
  * c) si on avait dans les percepts l'intégralité des cases, l'agent réflexe pur "stateless" optimal est possible, on peut imaginer lui faire aspirer la case sale la plus proche de manière systématique.

Exercice 2.10

On rajoute des frontières et des obstacles (ça ressemble de plus en plus à un jeu vidéo bien connu ce truc...):

  * a) difficile de faire un agent réflexe optimal, il a de fortes chances de tourner en rond, de rester bloqué dans des impasses...
  * b) j'imagine qu'en randomisant le comportement l'agent réflexe va bien finir par tout aspirer, au bout de combien de temps, on se le demande, mais c'est une autre question
  * c) pour piéger un robot stupide qui se déplace au hasard, rien de tel que deux zones bien vastes séparées par un petit goulet: le robot idiot reste toujours du même côté... On piège aussi le petit malin qui "laisse le mur à droite" avec des zones concentriques (murs disjoints).
  * d) si on sait par où on est passé (stateful), il est plus facile de sortir de l'impasse, c'est clair.

Exercice 2.11

Avec un capteur de chocs au lieu de l'indicateur de position:

  * on peut imaginer calculer en interne sa position mais est-ce là l'esprit de l'exercice? On peut plutôt partir sur des principes simples type changement de direction à l'obstacle, avec un peu de randomisation quand même.
  * si le capteur tombe en panne, il faut impérativement provoquer à intervalle régulier des changements de comportement, de direction, pour éviter de bloquer pendant 1000 ans sur un mur.

Exercice 2.12

Avec un environnement stochastique (non déterministe):

  * a) si l'aspiration est susceptible de mal se passer: procédure de contrôle, on vérifie après avoir aspiré. Si le détecteur de poussière donne des réponses érronés (donc si même le contrôle est faux) ça va marcher moins bien, on risque de croire avoir aspiré et laisser des cases sales. Le programme est moins efficace, soit on décide d'aspirer systématiquement, donc ne pas croire le capteur, soit on laisse des cases sales...
  * b) si les cases se salissent au hasard, on peut imaginer "qu'au bout d'un certain temps" on revient visiter des cases réputées propres, surtout ne pas s'excrimer à avoir un résultat parfait dans une petite zone quand le reste est réellement très salle (ne pas se concentrer sur le problème des "jeunes enfants")