Agents intelligents et formulation de problèmes

Un système intelligent peut être jugé d'après ce qu'il fait ou d'après sa manière de penser. Il peut aussi être jugé par rapport à la performance humaine ou à une norme de rationalité. Ces deux choix donnent quatre conceptions de l'IA.

Choisir la référence

La modélisation cognitive relève de la conception qui consiste à penser comme un humain. Un programme qui résout une énigme et obtient la bonne réponse finale peut néanmoins être un mauvais modèle de la pensée humaine si les humains suivent d'autres étapes. Les expériences psychologiques, l'introspection et l'imagerie cérébrale aident à vérifier le modèle. Newell et Simon ont utilisé des traces de raisonnement humain pour développer le General Problem Solver.

L'approche des lois de la pensée utilise la logique. À partir de « Tous les humains sont mortels » et de « Socrate est un humain », elle déduit « Socrate est mortel ». Les décisions réelles font aussi intervenir des prémisses incertaines et un choix d'action. Les probabilités traitent l'incertitude ; une politique d'action relie les conclusions au comportement.

Ce que vérifie le test de Turing

Le jeu de l'imitation de Turing, proposé en 1950, repose sur des échanges écrits avec un humain et une machine cachés. La machine réussit lorsque l'interrogateur ne peut pas les distinguer de manière fiable. Le traitement du langage, la représentation des connaissances, le raisonnement et l'apprentissage contribuent à cette tâche. Le test de Turing total ajoute l'interaction physique : la vision pour voir les objets, la robotique pour les manipuler et la reconnaissance de la parole pour les échanges oraux.

Une conversation convaincante établit l'existence d'un comportement conversationnel semblable à celui d'un humain. La question de savoir si elle établit une compréhension est différente. ELIZA, lancé en 1966, pouvait transformer l'énoncé d'un utilisateur en question : « Je me sens seul » pouvait susciter « Pourquoi te sens-tu seul ? » De telles réponses peuvent suggérer une compréhension sans modèle de la situation de la personne qui parle. L'imitation peut aussi récompenser les erreurs humaines ou les réponses évasives.

La Chambre chinoise de Searle, en 1980, rend cette distinction plus nette. Une personne suit un manuel de règles pour fournir des réponses en chinois sans comprendre le chinois. Searle soutient que l'exécution de règles ne suffit pas à produire la compréhension. La réponse du système situe toute compréhension éventuelle dans le système complet, y compris les règles et la pièce. Le débat philosophique reste ouvert. L'IA faible concerne la capacité d'agir intelligemment ; l'IA forte affirme l'existence d'une pensée et d'une compréhension réelles.

Bien agir avec des ressources limitées

L'approche de l'agent rationnel, le modèle standard de l'IA, juge les actions d'après leurs conséquences attendues. Un réflexe rapide peut être rationnel ; un long raisonnement logique est inutile lorsqu'un retrait immédiat évite une brûlure. Les agents pratiques disposent d'un temps et de ressources de calcul limités : la rationalité limitée consiste donc à faire aussi bien que ces ressources le permettent.

Le choix de l'objectif importe aussi. Une machine récompensée uniquement pour la fermeture de demandes d'assistance peut les fermer sans résoudre les problèmes. C'est un échec de l'alignement sur les valeurs humaines : la mesure optimisée ne correspond pas à ce à quoi les humains accordent de la valeur. Une conception proposée maintient la machine dans l'incertitude quant à l'objectif véritable et attentive aux indications humaines.

L'IA spécialisée traite des tâches particulières. L'intelligence artificielle générale apprendrait et accomplirait avec souplesse un large éventail de tâches au niveau humain. Une grande aisance conversationnelle et l'excellence dans un jeu répondent à des questions différentes de celle de savoir si un système possède cette capacité générale ; il n'existe pas de test de l'intelligence artificielle générale faisant consensus.

L'IA combine des idées issues de disciplines qui ont abordé différentes parties d'une même question : comment un système peut-il représenter le monde, apprendre à le connaître et choisir des actions utiles ?

Les idées antérieures au domaine

La philosophie a apporté la logique et les théories de l'esprit. Les mathématiques ont fourni les probabilités, le raisonnement formel et les limites du calcul. L'économie a contribué par l'utilité et la théorie de la décision. La psychologie et les neurosciences ont proposé des conceptions du traitement de l'information et des neurones. L'ingénierie informatique a fourni le matériel ; la linguistique a apporté la structure du langage. L'automatique et la cybernétique ont étudié la rétroaction, comme lorsqu'un thermostat corrige un écart de température. L'approche par les agents réunit ces contributions.

Des premiers modèles aux premières limites

McCulloch et Pitts ont décrit des neurones artificiels calculant des fonctions logiques en 1943. Turing a proposé le jeu de l'imitation en 1950. McCarthy, Minsky, Rochester et Shannon ont soumis la proposition de Dartmouth en 1955 ; l'atelier tenu en 1956 a établi l'IA comme domaine. Son ambition était de décrire l'apprentissage et l'intelligence assez précisément pour que des machines puissent les simuler.

Parmi les premiers succès figurent le Logic Theorist et le General Problem Solver de Newell et Simon, le programme de jeu de dames apprenant de Samuel, le langage Lisp de McCarthy en 1958 et le perceptron de Rosenblatt en 1958. Ces programmes ont montré des capacités de raisonnement ou d'apprentissage dans des cadres restreints. Les prédictions optimistes ont dépassé les progrès : la prévision d'un champion du monde d'échecs dans les dix ans a mis environ quarante ans à se réaliser.

Trois obstacles sont apparus clairement. Les programmes manquaient de connaissances du domaine, les espaces de recherche grandissaient trop vite et certaines représentations étaient trop limitées. L'explosion combinatoire signifie que l'ajout de quelques choix peut multiplier énormément les possibilités. L'analyse de Minsky et Papert en 1969 a montré les limites des perceptrons à une couche, notamment leur incapacité à représenter XOR. Elle n'a pas établi l'impossibilité des réseaux multicouches. Le rapport ALPAC de 1966 a réduit le soutien américain à la traduction automatique ; le rapport Lighthill de 1973 a contribué aux réductions de financement au Royaume-Uni. La baisse des financements au milieu des années 1970 est devenue le premier hiver de l'IA.

Connaissances, incertitude et apprentissage

Les systèmes experts encodaient les connaissances de spécialistes sous forme de règles « si-alors ». DENDRAL étudiait les structures moléculaires, MYCIN aidait au diagnostic des infections du sang et R1/XCON configurait des commandes d'ordinateurs, ce qui économisait des millions de dollars américains par an. La croissance commerciale du début des années 1980 a mis en évidence le coût d'acquisition et de maintenance des règles. Les systèmes étaient fragiles hors de leur domaine ; le marché des machines Lisp s'est effondré en 1987 et un deuxième hiver a suivi. La recherche s'est poursuivie pendant les deux hivers.

À partir du milieu des années 1980, plusieurs axes ont progressé ensemble. Rumelhart, Hinton et Williams ont popularisé la rétropropagation du gradient en 1986. Le livre de Pearl paru en 1988 a contribué à établir les réseaux bayésiens pour traiter l'incertitude. Les modèles de Markov cachés sont devenus essentiels à la reconnaissance de la parole. Des jeux de données et des références partagés ont rendu les comparaisons plus systématiques.

De grands jeux de données et du matériel plus rapide ont soutenu la vague suivante. Le réseau profond d'AlexNet, entraîné sur des processeurs graphiques, a remporté ImageNet en 2012. AlphaGo a battu Lee Sedol 4 à 1 en 2016. Les Transformers sont apparus en 2017 ; le lancement de ChatGPT en novembre 2022 a fait découvrir l'IA conversationnelle à un large public.

Comparer deux étapes marquantes des jeux

Le go offre généralement environ 250 coups autorisés contre environ 35 aux échecs. Le guidage appris a aidé à sélectionner des suites prometteuses sans tout explorer. Les deux systèmes utilisaient la recherche : l'apprentissage a élargi les méthodes de l'IA sans remplacer le reste du domaine. L'effet IA désigne la tendance à cesser de qualifier d'IA une capacité maîtrisée une fois qu'elle devient familière.

L'IA rassemble des méthodes de perception, de raisonnement, d'apprentissage et d'action. Pour les comparer utilement, demande-toi comment un système représente les connaissances, d'où elles viennent et ce qui se passe lorsque ses hypothèses ne sont plus valables.

Comparer les principales approches

Un calculateur d'itinéraire symbolique peut établir l'itinéraire le moins coûteux sur sa carte. Sa garantie concerne cette carte et ce modèle de coût. Les connaissances sont souvent rédigées par des experts, ce qui crée un goulet d'étranglement de l'acquisition des connaissances, mais des règles symboliques peuvent aussi être apprises. Un arbre de décision appris, par exemple, peut produire des règles lisibles.

Les méthodes probabilistes représentent explicitement l'incertitude. Un robot dont les mesures de distance sont bruitées peut combiner des observations sur plusieurs positions possibles. Les réseaux bayésiens et les modèles de Markov organisent ce raisonnement ; les modèles de décision relient les probabilités aux choix. L'incertitude est représentée et gérée, mais elle ne disparaît pas simplement parce qu'une probabilité lui est attribuée.

Les méthodes fondées sur l'apprentissage utilisent des exemples ou l'expérience pour améliorer les performances. Les réseaux de neurones sont des modèles connexionnistes ; l'apprentissage profond utilise plusieurs couches. Les grands réseaux profonds peuvent nécessiter beaucoup de données et de calcul et être difficiles à interpréter. Des modèles appris plus petits peuvent être lisibles. Dans les systèmes appris, les biais d'entraînement et les entrées inhabituelles peuvent nuire aux performances.

Combiner les méthodes selon les besoins de la tâche

Dans les années 1980, la robotique fondée sur le comportement de Rodney Brooks mettait l'accent sur des comportements réactifs simples. Le calcul évolutionnaire effectue une recherche en faisant varier des solutions candidates et en sélectionnant les meilleures. Les systèmes hybrides combinent des méthodes : AlphaGo associe une évaluation apprise à la recherche ; un véhicule autonome peut combiner vision apprise, suivi probabiliste, planification d'itinéraire et règles de sécurité explicites. La recherche en IA neurosymbolique combine apprentissage neuronal et raisonnement symbolique.

Imagine un robot d'entrepôt qui lit les étiquettes des colis, estime sa position et choisit un itinéraire. La reconnaissance des étiquettes bénéficie de l'apprentissage, les estimations incertaines de la position font appel aux probabilités et le choix de l'itinéraire fait appel à la recherche. La tâche physique relie ces méthodes sans en faire une seule technique interchangeable.

Juger ce qu'une capacité établit

Les systèmes d'IA planifient des itinéraires, traduisent des textes, reconnaissent la parole, aident à analyser des images médicales et pilotent des robots d'entrepôt. Des services de taxis sans conducteur transportent des passagers dans plusieurs villes. AlphaFold 2 a démontré de grandes capacités de prédiction de la structure des protéines ; Hassabis et Jumper ont partagé la moitié du prix Nobel de chimie 2024 pour la prédiction de la structure des protéines.

Ce sont des réussites importantes dans ces tâches. Pour évaluer une affirmation plus large, identifie l'objectif, les perceptions, les actions disponibles et l'environnement. Un programme champion d'échecs vise la victoire, perçoit l'échiquier et choisit des coups autorisés dans un jeu discret et déterministe. La conduite exige de percevoir des dangers cachés et de contrôler un véhicule physique en temps voulu. Gagner aux échecs apporte une preuve de performance aux échecs, pas de compétence en conduite.

Les systèmes actuels peuvent échouer hors de conditions familières, produire des erreurs avec assurance ou reproduire des schémas biaisés. Les systèmes physiques peuvent subir des défaillances de sécurité ; les autres risques comprennent la surveillance, la désinformation et les perturbations de l'emploi. Les avantages comprennent les découvertes scientifiques, l'aide au diagnostic et l'automatisation des travaux dangereux. Les réseaux de neurones sont des modèles mathématiques inspirés des neurones ; cette inspiration ne dit pas à elle seule à quel point leur raisonnement ressemble à celui d'un cerveau.

Un robot et un filtre antipourriel reçoivent tous deux des informations et modifient quelque chose à l'extérieur d'eux-mêmes. Le modèle de l'agent décrit cette boucle sans exiger de corps ni affirmer l'existence d'une intelligence semblable à celle d'un humain.

Distinguer les composantes de la boucle

Les capteurs obtiennent des informations ; une perception est l'information transmise à un instant donné. Les actionneurs fournissent des moyens d'agir sur l'environnement. Une caméra est un capteur, son image courante est une perception, un moteur de roue est un actionneur et avancer est une action.

Pour un agent logiciel, les messages entrants, le contenu des fichiers ou les frappes au clavier fournissent des perceptions. Écrire un fichier, déplacer un message ou afficher une réponse modifie son environnement numérique. Un agent incarné est aussi soumis à une dynamique physique : la masse, la vitesse, les frottements, les limites de la batterie et l'usure influencent son comportement.

La séquence de perceptions est l'historique complet des perceptions. Deux agents qui reçoivent la même mesure courante peuvent agir différemment parce que leurs mesures antérieures diffèrent. Un robot d'entrepôt qui a vu une allée bloquée il y a un instant possède une information dont un robot qui vient de démarrer ne dispose pas.

Comportement et implémentation

La fonction décrit ce que l'agent ferait pour chaque historique d'entrées, y compris ceux qu'il n'a jamais rencontrés. Le programme reçoit la perception courante à chaque appel. Tout historique nécessaire doit être conservé en mémoire. Agent = architecture + programme : le même code sur une plateforme dotée de capteurs ou d'actions différents peut se comporter très différemment.

Étudier un aspirateur à deux cases

Les cases A et B peuvent chacune être propres ou sales. L'aspirateur perçoit sa propre position et l'état de propreté de sa case courante. Il peut effectuer Gauche, Droite, Aspirer ou NeRienFaire. Une perception courante comme « [A, Sale] » ne fournit aucune information sur B.

Un programme simple peut utiliser ces règles :

if current_square_is_dirty:
    return "Suck"
if location == "A":
    return "Right"
return "Left"

En partant de A sale, il aspire. Sa perception suivante est « [A, Propre] », donc il va à droite. Sur B sale, il aspire à nouveau. Une fois les deux cases propres, ces règles le font continuer à se déplacer, car elles ne stockent aucune information indiquant que les deux cases ont été nettoyées. L'effet de ce déplacement sur la performance dépend de la règle de notation.

Pourquoi ne pas énumérer tous les historiques d'entrées ?

Il existe quatre perceptions courantes : A ou B croisé avec propre ou sale. Une table indexée par les historiques de longueur 1 à 3 nécessite :

Pour les longueurs de 1 à 10, elle nécessite 1 398 100 entrées. Un historique plus long constitue une clé différente dans la table, même lorsque sa dernière perception répète une perception antérieure. Les caméras rendent le nombre d'entrées possibles encore bien plus grand. Un programme compact exploite des régularités, comme nettoyer chaque fois que de la saleté est détectée, au lieu de stocker chaque cas.

Qualifier un thermostat d'agent décrit sa relation entre capteur et action. Cela n'implique pas un raisonnement sophistiqué. L'approche par les agents devient particulièrement utile lorsque le choix des actions fait intervenir la perception, l'inférence, l'apprentissage ou la planification, et lorsque les informations disponibles pour le programme doivent être explicitées.

Un bon comportement nécessite un critère explicite. Une mesure de performance évalue la séquence d'états de l'environnement produite par l'agent, ce qui permet de comparer deux programmes d'après leurs conséquences.

Récompenser le résultat souhaité

Un aspirateur récompensé pour la saleté ramassée pourrait la déverser et la ramasser à nouveau. Récompenser un sol propre traduit mieux le résultat souhaité. Le concepteur ou l'utilisateur fixe la mesure ; laisser un agent redéfinir librement la réussite lui permettrait de s'attribuer un score parfait.

Une mesure peut combiner propreté, énergie et bruit. Ces choix comptent : un sol maintenu propre en silence diffère d'un sol dont la même propreté moyenne est obtenue par des interventions bruyantes et perturbatrices. La définition de la réussite précède le choix d'un algorithme.

Calculer un score au fil du temps

Les deux cases sont sales au départ et l'aspirateur se trouve en A. Après chacune des 10 actions, attribue un point par case propre. Les cases propres le restent.

1. L'agent 1 effectue Aspirer, Droite, Aspirer, puis NeRienFaire sept fois. Les nombres de cases propres après les trois premières actions sont 1, 1 et 2. Son total est $1+1+2+7\times 2=18$.
2. L'agent 2 effectue Droite, Aspirer, Gauche, Aspirer, puis NeRienFaire six fois. Son total est $0+1+1+2+6\times 2=16$.
3. L'agent 3 commence comme l'agent 1 mais continue à se déplacer pendant ses sept dernières actions. Son score de propreté est aussi de 18.

Retire maintenant un point par déplacement. L'agent 1 se déplace une fois et obtient 17. L'agent 3 se déplace huit fois et obtient 10. Avec la nouvelle mesure, il est avantageux de s'arrêter dès que l'agent sait que les deux cases sont propres.

Juger une décision avant d'en voir le résultat

Un agent rationnel choisit l'action censée maximiser sa mesure de performance, compte tenu de sa séquence de perceptions et de ses connaissances intégrées. Quatre éléments déterminent ce jugement : la mesure, les connaissances préalables, les actions disponibles et l'historique des perceptions.

La rationalité diffère de l'omniscience, qui consisterait à connaître à l'avance le résultat réel. Une personne à vélo consulte une prévision annonçant 5 % de risque de pluie. Transporter une veste encombrante est une gêne certaine qui, pour cette personne, l'emporte sur ce risque d'être mouillée. La laisser chez soi peut être rationnel même s'il pleut ensuite. Un mauvais résultat ne change pas les informations disponibles au moment de la décision.

La collecte d'informations peut elle-même être une action rationnelle. Regarder avant de traverser une route coûte peu et améliore la décision suivante. Dans un cadre inconnu, l'exploration peut révéler les effets des actions, au prix d'une partie de la récompense immédiate pour faire de meilleurs choix par la suite.

Laisser l'expérience améliorer le comportement

L'autonomie augmente lorsqu'un agent s'appuie sur sa propre expérience plutôt que sur les seules hypothèses de son concepteur. Un aspirateur doté d'un plan fixe peut heurter à plusieurs reprises un canapé déplacé. La mise à jour du plan à partir de nouvelles mesures lui permet de s'adapter. Des connaissances préalables utiles l'aident à démarrer ; l'apprentissage permet d'adapter ces connaissances à l'environnement.

Un score élevé n'a de sens que si la mesure rend compte du résultat visé. Fermer rapidement des tickets d'assistance tout en laissant les problèmes non résolus est un échec de la mesure, même si le système optimise efficacement ce score.

Avant de concevoir un agent, précise ce que signifie la réussite et ce que l'agent peut percevoir et modifier. PEAS organise l'environnement de tâche en mesure de performance, environnement, actionneurs et capteurs.

Commencer par la réussite

P décrit les résultats qui peuvent être évalués. E décrit le cadre et les entités qui influencent ces résultats. A énumère les moyens d'agir ; S énumère les moyens d'obtenir des informations. L'environnement de tâche est le problème que l'agent doit résoudre, et non l'algorithme utilisé pour le résoudre.

Pour un taxi autonome, « bien conduire » est trop vague. Une composante P utile comprend des trajets sûrs, légaux, confortables et effectués dans les délais, les gains et les effets sur les autres usagers de la route. Ces objectifs peuvent entrer en conflit. Les contraintes de sécurité peuvent être des exigences fixes, la vitesse n'étant optimisée que parmi les choix sûrs.

Compléter la description du taxi

Un écran destiné aux passagers est un actionneur parce qu'il modifie ce que les passagers voient. Un écran tactile peut aussi fournir des informations de capteur lorsqu'un passager choisit une destination. Classe chaque rôle selon le sens de l'information ou de l'action, et non selon le nom courant du dispositif.

Appliquer PEAS au-delà de la conduite

Un assistant de diagnostic médical vise la santé des patients, des diagnostics exacts, des examens utiles et peu d'actes inutiles. Son environnement comprend les patients, les soignants, les laboratoires et l'hôpital. Ses sorties comprennent des questions, des demandes d'examens, des suggestions de diagnostics et des orientations vers d'autres professionnels. Ses entrées comprennent les symptômes rapportés, les constatations, les dossiers et les résultats d'examens.

Un robot de préparation de commandes en entrepôt vise un certain nombre d'articles corrects prélevés par heure, sans dommage ni blessure. Les rayonnages, les bacs, les convoyeurs et les personnes constituent son environnement. Les roues, un bras et une pince sont des actionneurs. Les caméras, les lecteurs de codes-barres, les capteurs d'angle des articulations et les capteurs de force fournissent des informations. Le robot doit mesurer la force si sa mesure pénalise les marchandises écrasées : voir le bon article ne suffit pas à détecter une force de préhension excessive.

Pour un filtre antipourriel, P met en balance les pourriels bloqués et les courriels légitimes bloqués à tort. E comprend la boîte de réception et les expéditeurs. A permet de distribuer un message ou de le déplacer dans les pourriels. S fournit le texte des messages, les en-têtes et les signalements de l'utilisateur. Bloquer davantage de pourriels en bloquant tous les messages sacrifierait la distribution des messages légitimes.

Vérifier la cohérence des composantes

Rédige d'abord P, puis E, A et S. Pour chaque résultat souhaité, détermine comment les actionneurs l'influencent. Pour chaque information nécessaire au choix d'une action, identifie un capteur ou une connaissance préalable qui la fournit. Un objectif de confort nécessite des éléments comme des mesures d'accélération ou les avis des passagers. Si aucun des deux n'existe, le système conçu ne peut pas juger cet aspect du trajet de manière fiable.

Distingue les instruments, les observations et les choix. Une caméra est un capteur ; une image est une perception. Une pince est un actionneur ; « saisir l'article 37 » est une action. L'algorithme d'itinéraire appartient à l'agent, tandis que le réseau routier appartient à E. Les capteurs choisis déterminent aussi quelle quantité d'informations utiles est accessible à l'agent.

Les catégories d'environnement décrivent des exigences distinctes pour un agent. Une tâche peut être totalement observable tout en étant incertaine, ou avoir des règles connues tout en comportant des informations cachées. Classe chaque dimension indépendamment.

Informations, autres agents et résultats

Un environnement est totalement observable lorsque les capteurs révèlent tous les faits utiles au choix d'une action. Il est partiellement observable lorsque des faits utiles sont cachés ou que les mesures sont bruitées. Un agent sans capteur fait face à un environnement non observable. Un échiquier est visible ; le poker cache les cartes des adversaires.

Une tâche multiagent comprend d'autres entités dont les choix guidés par un objectif influencent le résultat et dépendent de notre comportement. Les échecs sont compétitifs ; des robots qui portent une table coopèrent. Les conducteurs coopèrent pour éviter les collisions et peuvent rivaliser pour des places de stationnement. Un arbre tombé est un obstacle, pas un autre agent. Le recours au hasard peut aider en compétition en rendant les choix plus difficiles à prévoir.

Dans un environnement déterministe, l'état et l'action déterminent l'état suivant. Un modèle non déterministe énumère les issues possibles ; un modèle stochastique leur attribue des probabilités. Les échecs sont considérés par convention comme déterministes, car l'incertitude sur le choix de l'adversaire relève de la dimension multiagent. Des informations cachées peuvent rendre une dynamique déterministe incertaine aux yeux d'un agent.

Dépendance et passage du temps

Une tâche statique peut être séquentielle. Inscrire une réponse dans une grille de mots croisés contraint les réponses suivantes, même si la grille ne change pas pendant que la personne réfléchit. Épisodique signifie que les décisions concernent des épisodes indépendants, et non simplement que les actions ont lieu à des moments distincts.

Valeurs et connaissances

Les états ou actions discrets présentent des possibilités distinctes. Les grandeurs continues varient sur une plage, comme la vitesse d'une voiture ou son angle de braquage. Classe séparément les états, le temps, les perceptions et les actions : les images numériques contiennent des valeurs discrètes mais représentent souvent une luminosité et une position variant de façon continue. Les échecs avec pendule combinent des coups discrets et un temps qui s'écoule de façon continue.

Dans un environnement connu, les effets des actions ou les probabilités des résultats sont spécifiés. Dans un environnement inconnu, l'agent doit les apprendre. Ces catégories concernent le modèle, et non ce que les capteurs montrent à l'instant présent. Le solitaire a des règles connues et des cartes cachées. Un nouveau jeu peut montrer son état complet tout en laissant inconnus les effets de ses boutons.

Appliquer chaque question à la tâche

Demande-toi, dans l'ordre : quels faits utiles sont cachés ? Qui d'autre choisit des actions ? L'état suivant est-il déterminé ? Les décisions influencent-elles les suivantes ? Qu'est-ce qui change pendant que l'agent réfléchit ? Quelles grandeurs sont discrètes ou continues ? Les effets des actions sont-ils connus ?

La conduite d'un taxi combine observabilité partielle, plusieurs agents, résultats stochastiques, décisions séquentielles, monde dynamique et grandeurs continues. Une grande partie de la dynamique du véhicule est connue, mais un véhicule inconnu peut nécessiter un apprentissage. La combinaison la plus difficile comprend aussi une dynamique inconnue. Ne déduis pas les sept catégories d'une seule caractéristique difficile : le go, totalement observable, possède malgré tout un espace d'états énorme.

Un classement devient utile lorsqu'il modifie la manière de construire l'agent. Un état caché peut nécessiter une estimation ; des résultats incertains appellent la prise en compte de plusieurs futurs possibles ; un monde changeant limite le temps de délibération.

Comparer des tâches familières

Ces descriptions de jeux supposent que leurs règles habituelles sont connues. Une pendule change le classement relatif au temps sans cacher les pièces ni modifier les règles des coups. Les dés changent l'incertitude des transitions sans cacher le plateau visible.

Classer les tâches physiques et de diagnostic

Un taxi possède des angles morts et ne peut pas observer directement les intentions des autres conducteurs. Les autres usagers de la route poursuivent des objectifs et la circulation change pendant que l'agent réfléchit. Une sortie manquée influence les choix ultérieurs. Les positions, les vitesses et les angles de braquage varient de façon continue ; des événements imprévus rendent les résultats stochastiques. Cette combinaison exige de la perception, de la prédiction, un contrôle en temps voulu et de la planification.

Un assistant de diagnostic médical dispose d'observations incomplètes sur les états internes. Les résultats des examens sont imparfaits, les traitements ont des résultats incertains et un examen détermine la décision suivante. L'état du patient peut changer pendant la délibération ; de nombreuses mesures sont continues. Un modèle courant considère le patient comme faisant partie d'un environnement à un seul agent, l'assistant prenant des décisions pour améliorer la santé. Ce choix diffère d'une modélisation dans laquelle plusieurs soignants prennent des décisions en interaction.

Une caméra d'inspection juge les pièces finies indépendamment les unes des autres. Un défaut interne caché rend la tâche partiellement observable, mais les pièces précédentes ne sont pas nécessairement utiles pour juger la pièce courante. Si un convoyeur en mouvement change la position de la pièce pendant que la caméra délibère, la tâche est dynamique. Si une image figée reste inchangée et que seul le délai réduit le score, elle est semi-dynamique. Une échéance ne suffit pas à déterminer laquelle de ces situations s'applique.

Traduire les propriétés en choix de conception

Lorsque les mesures antérieures révèlent quelque chose sur l'état courant caché, utilise une mémoire et un modèle du monde. Un taxi peut se souvenir d'une voiture entrée dans son angle mort. Dans une classification d'images indépendantes, la mémoire des éléments précédents peut ne rien apporter d'utile ; l'observabilité partielle ne suffit pas à elle seule à établir le besoin d'un historique.

Les tâches stochastiques exigent de comparer des résultats incertains. Les tâches compétitives exigent d'anticiper les adversaires, parfois en recourant au hasard. Les tâches séquentielles exigent de considérer les conséquences. Les tâches dynamiques exigent des décisions assez rapides pour rester utiles. Des effets inconnus exigent l'apprentissage et l'exploration. Les grandeurs continues exigent des représentations et des méthodes adaptées à des plages de valeurs.

La recherche classique convient aux modèles à un seul agent qui sont connus, déterministes, totalement observables et discrets. La recherche adversariale traite les jeux compétitifs. L'inférence probabiliste estime l'état caché ; les processus de décision aident à faire des choix séquentiels incertains ; l'apprentissage par renforcement traite l'apprentissage par interaction. L'apprentissage supervisé convient à de nombreuses tâches de classification indépendantes. Un système réel peut combiner plusieurs de ces méthodes parce que son environnement combine plusieurs exigences.

Les programmes d'agent diffèrent par les informations qu'ils utilisent pour choisir une action. Une table peut décrire directement le comportement ; les conceptions pratiques exploitent des règles et des modèles pour éviter d'énumérer tous les historiques.

Comparer trois conceptions

Un programme tabulaire peut en principe implémenter une fonction d'agent. Avec quatre perceptions possibles, les historiques de longueur allant jusqu'à 10 nécessitent déjà 1 398 100 entrées. Une règle comme « si la case est sale, aspirer » couvre de nombreux historiques avec un seul morceau de code.

Comprendre pourquoi un réflexe peut boucler

Un agent réflexe simple associe la situation courante à une règle condition-action, puis agit. Un détecteur de feux stop peut déclencher rapidement le freinage. Pour une tâche dont la réponse correcte peut être déterminée à partir de la mesure courante, cette méthode est efficace. L'observabilité totale fournit les informations utiles sur l'état, mais les règles doivent encore choisir des actions appropriées.

Retirons le capteur de position de l'aspirateur. Il ne voit plus que « Propre » ou « Sale ». En partant de A propre, une règle « si la case est propre, aller à Gauche » le fait heurter le mur. La mesure suivante est toujours « Propre », donc il répète l'action indéfiniment. La même mesure apparaît en B propre, où aller à Gauche serait judicieux. L'information manquante rend les deux situations impossibles à distinguer.

Choisir Gauche ou Droite au hasard peut permettre de sortir de la boucle : depuis A, chaque tentative atteint B avec une probabilité d'un demi. Le nombre moyen de tentatives est de 2. Cela supprime la boucle déterministe mais n'indique pas à l'agent où il se trouve ni quelle case reste sale.

Mettre à jour une estimation interne

Un agent réflexe avec modèle conserve un état interne issu des perceptions antérieures. Il met à jour cet état à l'aide de la dernière action et de la nouvelle perception, puis applique des règles à l'estimation actualisée.

Deux modèles jouent des rôles différents :

• Un modèle de transition décrit comment le monde change, y compris les effets des actions.
• Un modèle d'observation décrit comment les états du monde produisent des observations.

Pour un taxi, voir une voiture dans un rétroviseur constitue une observation récente. Prédire où la voiture se déplace relève du modèle de transition. Relier une image de caméra à la position de la voiture relève du modèle d'observation. Le taxi peut conserver la voiture dans son estimation interne après son entrée dans un angle mort.

Un aspirateur peut se souvenir que A a été nettoyée. Après avoir nettoyé B, son état indique que les deux cases sont propres et sa règle peut choisir NeRienFaire. Selon le score de propreté sur dix actions avec une pénalité d'un point par déplacement, s'arrêter donne 17 points ; continuer à errer en donne 10.

Contrôle réactif et délibératif

Les conceptions réflexes sont réactives : les règles choisissent les actions sans simuler de séquences futures. Les conceptions fondées sur les buts et sur l'utilité sont délibératives : elles prédisent les conséquences. Les systèmes peuvent superposer un freinage d'urgence rapide et une planification d'itinéraire plus lente. « Avec modèle » ne signifie pas en soi « fondé sur les buts » : mémoriser des faits non visibles et se demander quel avenir permet d'atteindre une destination sont des opérations différentes. En observabilité partielle, l'état interne est une estimation que de nouvelles observations peuvent réviser.

Garder une représentation du monde en mémoire aide à prendre de meilleures décisions, mais n'indique pas quel avenir est souhaitable. Les agents fondés sur les buts et sur l'utilité rendent cette préférence explicite.

D'une destination à un plan

Un agent fondé sur les buts prédit les résultats des actions et se demande si elles mènent à une situation souhaitée. À une intersection, un taxi peut tourner à gauche, à droite ou aller tout droit sans danger. La destination du passager détermine quelle direction est utile. Changer de destination modifie le but, ce qui permet de trouver un nouvel itinéraire avec la même carte et les mêmes mécanismes de raisonnement.

Un but est un test oui/non : atteint ou non atteint. La recherche et la planification trouvent des séquences d'actions qui satisfont ce test. Des connaissances explicites rendent l'agent souple : une nouvelle destination change le but, tandis qu'une capacité de freinage réduite sous la pluie change le modèle utilisé pour prédire les résultats.

Un agent fondé sur l'utilité attribue des nombres au caractère souhaitable des résultats. Plusieurs itinéraires peuvent atteindre la même destination mais différer en durée, en sécurité ou en confort. L'utilité exprime ces préférences et ces compromis. Sa fonction d'utilité interne doit concorder avec la mesure de performance externe pour que la maximisation de l'utilité serve l'objectif visé.

Une utilité binaire de 1 pour la réussite et de 0 pour l'échec peut représenter un but en situation d'incertitude. Une utilité plus détaillée peut distinguer les résultats qui constituent une réussite ou attribuer des valeurs différentes aux différents échecs.

Calculer l'espérance d'utilité

Pour chaque résultat possible, multiplie sa probabilité par son utilité, puis additionne les produits :

Ici, le modèle probabiliste décrit les états résultant d'une action et la fonction d'utilité évalue ces résultats. Le choix rationnel fondé sur l'utilité est celui dont l'espérance d'utilité est la plus élevée.

Étudier le choix d'un trajet pour prendre un train

Un train part dans 40 minutes. Le trajet A dure à coup sûr 30 minutes. Le trajet B dure 20 minutes avec une probabilité de 0,8 ou 50 minutes avec une probabilité de 0,2.

Si l'objectif est de minimiser la durée de trajet attendue :

Le trajet B a la durée attendue la plus faible. Mais la personne souhaite prendre le train. Fixons l'utilité à 1 pour une arrivée avant le départ et à 0 si elle manque le train. Avec A, elle le prend toujours ; avec B, elle ne le prend que lorsque le trajet dure 20 minutes :

A est maintenant préférable. Le modèle probabiliste n'a pas changé. C'est l'évaluation des résultats qui a changé. Une durée moyenne de trajet de 26 minutes ne signifie pas que chaque trajet dure 26 minutes.

Tenir compte du calcul

L'utilité peut représenter le temps, la santé, le confort ou d'autres résultats auxquels on accorde de la valeur ; elle ne représente pas nécessairement de l'argent. Prédire exactement tous les futurs possibles coûte généralement trop cher en calcul, si bien que les agents pratiques utilisent des approximations. Anticiper prend aussi du temps. Une réponse réflexe est utile lorsqu'une action immédiate suffit, tandis que la délibération justifie son coût lorsque les conséquences futures distinguent les choix.

L'apprentissage peut améliorer un programme réflexe, fondé sur les buts ou fondé sur l'utilité. C'est une manière de construire et d'adapter un agent, et non une catégorie concurrente de choix des actions.

Suivre la boucle d'apprentissage

Le critique a besoin d'un critère externe car une perception seule ne dit pas si un résultat est bon. Voir une position d'échec et mat n'est pas la même chose que savoir que gagner est récompensé. L'agent ne doit pas pouvoir redéfinir son critère afin de faire passer un mauvais comportement pour une réussite.

Prenons un drone de livraison. L'élément de performance effectue un trajet. À cause d'un vent contraire, il ne reste que 8 % de batterie à l'atterrissage, sous le seuil de sécurité fixe de 15 %. Le critique signale cet écart. L'élément d'apprentissage révise le modèle énergétique pour prévoir une consommation plus élevée en cas de vent contraire similaire. Les vols futurs pourront transporter des charges plus légères ou emprunter des trajets plus courts. Le générateur de problèmes suggère un vol d'essai plus lent pour savoir si une vitesse de croisière réduite économise de l'énergie.

L'exploration peut réduire la récompense immédiate tout en améliorant les choix ultérieurs. L'apprentissage peut modifier les règles, les modèles de transition, les modèles d'observation ou une estimation interne de l'utilité. Une estimation actualisée de l'utilité doit toujours servir le critère de performance externe ; modifier ce que l'agent a appris sur les préférences est différent de l'autoriser à redéfinir la réussite.

Choisir comment représenter les états

Une représentation atomique traite un état comme un élément indivisible, tel qu'un nom de ville. L'algorithme peut comparer les états sans examiner leurs attributs internes. C'est une approche courante dans les modèles élémentaires de recherche et de jeu.

Une représentation factorisée décrit un état à l'aide de variables ayant des valeurs. Un véhicule peut avoir une position, un niveau de carburant et un indicateur d'alerte d'huile. Deux états peuvent partager une valeur de carburant tout en ayant des positions différentes, ce qui permet aux règles de se référer à leurs propriétés communes. La planification, les modèles de contraintes, les réseaux bayésiens et une grande partie de l'apprentissage automatique utilisent ce type de structure.

Une représentation structurée décrit des objets et leurs relations. « Le camion est derrière le portail » distingue un camion, un portail et la relation entre eux. La logique du premier ordre et la compréhension du langage utilisent de telles représentations pour exprimer qui a fait quoi à qui.

Compter les combinaisons sans les énumérer

Supposons qu'un état factorisé possède trois variables oui/non et une autre variable à 10 valeurs. Le nombre d'affectations possibles est :

Une description compacte par variables représente 80 possibilités atomiques. Des contraintes peuvent réduire le nombre d'affectations possibles ou accessibles. Des représentations plus expressives peuvent décrire des régularités de façon concise, mais elles exigent un raisonnement plus complexe. Atomique ne signifie pas dépourvu d'intelligence : traiter les villes comme des noms est efficace lorsque seules les liaisons routières importent. Les objets et leurs relations justifient leur complexité lorsque la tâche exige de réutiliser des connaissances sur leurs rôles.

Un agent résolveur de problèmes distingue le choix de ce qu'il faut accomplir de celui de la manière d'y parvenir. Il formule un but, formule un problème, cherche une solution dans son modèle et exécute les actions choisies.

Spécifier précisément le modèle

Certains cours combinent les actions, les résultats et les coûts dans une fonction successeur qui renvoie des triplets action-état-coût. Les mêmes informations sont présentes. Ces composantes décrivent le problème ; l'algorithme de recherche décide quelles possibilités examiner.

Un chemin est une séquence d'actions. Son coût est la somme des coûts des actions. Une solution mène de l'état initial à un état but ; une solution optimale a le coût le plus faible parmi les solutions. Lorsque les coûts sont positifs et inégaux, un chemin comportant moins d'actions peut malgré tout coûter plus cher.

Comparer les itinéraires selon leur coût

Voici les longueurs des routes en kilomètres : Alden-Brook 40, Alden-Cove 25, Brook-Cove 10, Brook-Elm 30, Cove-Dale 35 et Dale-Elm 20. Les routes peuvent être empruntées dans les deux sens. L'état est la ville courante ; le départ est à Alden et le test de but vérifie si l'on est à Elm. Les actions applicables suivent les routes depuis la ville courante, et chaque action a pour coût la longueur de la route.

Les chemins solutions simples sont :

• Alden → Brook → Elm : 70 km.
• Alden → Cove → Brook → Elm : 65 km.
• Alden → Cove → Dale → Elm : 80 km.
• Alden → Brook → Cove → Dale → Elm : 105 km.

L'itinéraire à trois routes passant par Cove et Brook est meilleur que celui à deux routes passant par Brook. Les longueurs des routes étant positives, ajouter un cycle ne peut pas réduire la distance.

Formuler le monde de l'aspirateur

Un état enregistre la position de l'aspirateur et l'état de propreté de chaque case : deux positions croisées avec deux indicateurs de saleté indépendants donnent 8 états. Les actions sont Gauche, Droite et Aspirer. Aspirer nettoie la case courante. Gauche en A et Droite en B ne changent pas la position. Le test de but vérifie si les deux cases sont propres ; chaque action coûte 1.

En partant de A avec les deux cases sales, Aspirer, Droite, Aspirer atteint le but au coût de 3. Deux actions de nettoyage et au moins un déplacement sont nécessaires : ce plan est donc optimal. Un modèle peut omettre les déplacements aux bords dans ACTIONS ou les inclure comme actions sans effet ; ACTIONS et RESULT doivent appliquer la même convention.

Distinguer les états des chemins

Le graphe de l'espace d'états possède un sommet par état et des arcs orientés pour les actions. Une route à double sens fournit deux arcs orientés. Un arbre de recherche représente les chemins depuis le départ : deux chemins différents peuvent se terminer au même état, créant des nœuds différents dans l'arbre. Un graphe peut être généré au besoin à l'aide d'ACTIONS et de RESULT sans stocker tous les états à l'avance.

Dans un modèle totalement observable, déterministe et connu, un plan fixe peut être exécuté en boucle ouverte sans nouvelle perception. Lorsque l'exécution peut s'écarter des prévisions, un contrôle en boucle fermée surveille les perceptions et modifie le plan ou suit des branches correspondant aux différentes issues. L'état but seul indique une destination ; la séquence d'actions explique comment l'atteindre.

Un état du monde contient tous les détails de l'environnement. Un état de recherche conserve ce dont la planification a besoin.

Vérifier ce qu'il faut mémoriser

Inclus assez d'informations pour déterminer les actions applicables, les résultats des transitions, le statut du but et les coûts des actions à partir de l'état courant. Si deux situations exigent des réponses différentes à l'une de ces questions, garde-les distinctes.

Pour atteindre une sortie sur une grille fixe, la position peut suffire. Pour ramasser des colis, la seule position ne permet pas de savoir quels articles restent. Pour se déplacer avec une batterie limitée, la seule position ne permet pas de savoir si l'action suivante est possible. La couleur des murs peut être omise lorsqu'elle ne change aucune de ces décisions.

Une abstraction est valide lorsque chaque solution abstraite peut être développée en une solution réelle. Elle est utile lorsque ses actions sont plus simples à effectuer que la résolution du problème initial. Remplacer les détails de conduite par « conduire de Cove à Brook » n'aide que si ce trajet abstrait peut réellement être effectué.

Construire le dénombrement variable par variable

Un robot se déplace sur une grille de 5 × 6 contenant 8 colis à des emplacements fixes.

1. Pour atteindre la sortie, stocke la case : $5\times 6=30$ possibilités.
2. Pour ramasser tous les colis, ajoute huit indicateurs ramassé/non ramassé : $30\times 2^8=7680$ affectations.
3. Si la charge de la batterie importe, ajoute 11 niveaux, de 0 à 10 : $7680\times 11=84480$ affectations.

Multiplie les tailles des domaines lorsque toutes les combinaisons sont autorisées. Cela donne le nombre de configurations représentées ; le nombre de configurations accessibles depuis l'état initial peut être plus petit. Le taquin à 8 cases mobiles possède $9!=362880$ dispositions, mais seules 181 440 sont accessibles depuis une disposition donnée. Pour le taquin à 15 cases mobiles, le nombre correspondant d'états accessibles est de 10 461 394 944 000, soit environ 1,05 × 10¹³.

Un aspirateur sur n cases possède une position et n indicateurs de saleté, ce qui donne $n{2}^n$ états. Deux cases donnent 8 états ; dix en donnent 10 240. Ajouter une variable binaire multiplie le nombre par deux, ce qui explique la croissance exponentielle.

Changer la formulation, pas la tâche

La tâche des huit reines consiste à placer huit reines qui ne s'attaquent pas. Une formulation à états complets commence avec huit reines et les déplace. Une formulation incrémentale commence avec un échiquier vide et ajoute des reines.

Autoriser chaque nouvelle reine sur n'importe quelle case vide produit environ 1,8 × 10¹⁴ séquences ordonnées de huit placements. De nombreux ordres créent le même échiquier. Le dénombrement des échiquiers distincts comportant de zéro à huit reines donne 5 130 659 561 états. Ce sont des quantités différentes : les séquences indiquent comment un échiquier a été construit ; les états décrivent l'échiquier.

Plaçons plutôt une reine uniquement dans la colonne vide la plus à gauche et uniquement sur une case non attaquée. Cette formulation comporte 2 057 états, dont 92 solutions, soit environ 2,5 millions de fois moins d'états distincts que la version incrémentale sans restriction. Elle empêche de nombreux choix voués à l'échec avant que la recherche ne les explore.

Conserver l'historique nécessaire sous une forme compacte

Une tournée qui doit passer par toutes les villes nécessite l'ensemble des villes visitées ainsi que la ville courante. Elle ne nécessite généralement pas l'ordre exact de tous les déplacements antérieurs, sauf si cet ordre influence les actions autorisées ou leur coût. Stocker un historique inutile fait apparaître des situations équivalentes comme différentes et empêche de réutiliser le travail effectué. Le nombre d'états donne une indication sur la difficulté ; la structure du graphe et la méthode utilisée pour l'explorer comptent aussi.

Une bonne formulation précise l'objectif, les déplacements autorisés et le coût pour qu'une méthode de recherche puisse les utiliser. Les petites énigmes rendent ces choix visibles ; les tâches pratiques ajoutent des délais, de l'incertitude ou des contraintes que l'état doit conserver.

Suivre une séquence de formulation

1. Énonce un but mesurable lié à la mesure de performance.
2. Choisis les variables d'état minimales et suffisantes ainsi que l'état initial.
3. Définis les actions applicables et leurs résultats.
4. Écris le test de but.
5. Attribue des coûts aux actions avec leurs unités.
6. Vérifie l'abstraction et estime le nombre d'états.

Pour le taquin à 8 cases mobiles, stocke les positions des huit tuiles et de la case vide. Déplace la case vide vers une case adjacente et échange-la avec la tuile qui s'y trouve. Un coin permet 2 déplacements, un bord 3 et le centre 4. Le test de but compare la disposition à une cible spécifiée. Des coûts d'action unitaires rendent le coût du chemin égal au nombre de déplacements.

Modéliser deux cruches d'eau

Utilise des cruches non graduées de 4 et de 3 litres, un robinet et une évacuation. Commence avec les cruches vides. Stocke les quantités sous forme de couple ordonné : d'abord la cruche de 4 litres, puis celle de 3 litres. Les opérations autorisées consistent à remplir, vider et verser jusqu'à ce que la cruche source soit vide ou la cruche de destination pleine. Chaque opération coûte 1.

À partir de (3 ; 3), verse la petite cruche dans la grande. La source contient 3 litres, mais la destination ne peut recevoir que 1 litre. Transfère la plus petite quantité :

Le résultat est (4 ; 2). Le versement ne partage pas l'eau arbitrairement ; la règle d'arrêt détermine la quantité transférée. En partant de cruches vides, les quantités entières en litres restent entières. La représentation comporte 20 combinaisons entières, dont 14 accessibles depuis (0 ; 0).

Laisser le test de but déterminer la réussite

Pour « l'une ou l'autre cruche contient 2 litres », un plan parmi les plus courts prend quatre actions :

(0 ; 0) → remplir la petite → (0 ; 3) → verser dans la grande → (3 ; 0) → remplir la petite → (3 ; 3) → verser dans la grande → (4 ; 2).

Pour « la cruche de 4 litres contient 2 litres », (4 ; 2) ne satisfait pas le test. Un plan parmi les plus courts prend six actions :

(0 ; 0) → remplir la grande → (4 ; 0) → verser dans la petite → (1 ; 3) → vider la petite → (1 ; 0) → verser dans la petite → (0 ; 1) → remplir la grande → (4 ; 1) → verser dans la petite → (2 ; 3).

Modifier quelques mots du but change l'état final considéré comme une réussite. Conserver un ordre fixe dans l'état évite de confondre les quantités des deux cruches.

Ajouter les informations nécessaires aux tâches réelles

Un calculateur d'itinéraires aériens a besoin de l'aéroport et de l'heure courants. Les vols suivants autorisés doivent partir assez tard pour permettre la correspondance. La classe tarifaire ou les tronçons précédents doivent aussi figurer dans l'état lorsqu'ils influencent les possibilités ou les prix futurs. La seule distance ne peut pas représenter un objectif qui combine tarifs, attente, durée du vol et aspects pratiques ; un modèle de coût doit définir les compromis.

Un problème de tournée doit mémoriser les lieux visités. Le problème du voyageur de commerce cherche une tournée de longueur minimale qui passe une fois par chaque ville et revient au départ ; il est NP-difficile et aucune méthode exacte et efficace n'est connue pour tous les grands cas. La navigation d'un robot peut nécessiter une position continue et des angles d'articulation. La disposition des composants dans un circuit VLSI traite le placement des composants et des connexions ; l'ordonnancement des opérations d'assemblage doit conserver les pièces déjà installées car un choix précoce peut bloquer une étape ultérieure.

Avant la recherche, teste une action ordinaire et un cas limite. Une cruche de destination pleine ne doit plus accepter d'eau ; un vol déjà parti ne doit pas apparaître comme une correspondance disponible. Ces vérifications révèlent tôt les informations manquantes dans l'état ou les incohérences des règles d'action.