Catégorie : Informatique quantique

  • Algorithmes quantiques : quand la physique quantique défie la thèse de Church-Turing

    Frédéric Magniez  a tenu la Chaire annuelle Informatique et sciences numériques 2020-2021 du Collège de France. Il n’y avait pas eu à l’époque d’article sur binaire. Voilà qui corrige cette situation peu acceptable.
    Frédéric Magniez, mathématicien et informaticien, est directeur de l’Institut de recherche en informatique fondamentale (www.irif.fr) et directeur adjoint de la Fondation des sciences mathématiques de Paris. Ses travaux de recherche portent sur la conception et l’analyse d’algorithmes probabilistes pour le traitement des grandes masses de données, ainsi que sur le développement de l’informatique quantique et plus particulièrement les algorithmes, la cryptographie et ses interactions avec la physique.     Serge Abiteboul
    Frédéric Magniez, 2020. Crédits : Patrick Imbert, Collège de France

    Une prouesse inutile ?

    L’année 2021 sera sans aucun doute quantique ! Il y a à peine plus d’un an, Google réalisait un calcul sur un prototype de circuit quantique programmable. D’un point de vue technologique la prouesse était encore inimaginable il y a seulement quelques années. D’un point de vue de la puissance de calcul, la tâche demandée est certes très spécifique, mais nécessiterait plusieurs milliers d’années de calcul sur tout autre machine existante, aussi puissante soit-elle ! Un vrai tournant venait donc d’être engagé. Cette année, un consortium européen va lancer une plateforme de simulation et de programmation quantique rassemblant chercheurs et industriels issus de la physique et de l’informatique. Cette plateforme utilisera une technologie quantique fournie par la start-up française Pasqal. Enfin, l’État va lancer un plan national quantique qui va voir la création de plusieurs centres dédiés à la recherche sur les technologies quantiques, dont l’informatique.

    Le calcul effectué par Google fin 2019 revenait à lancer un gigantesque dé truqué ou faussé. Le calcul des probabilités de chaque face du dé est lié au circuit quantique programmé dans la machine de Google. La simulation d’un circuit quantique, même de petite taille (53 bits dans l’expérience de Google), est d’une telle complexité pour nos ordinateurs actuels qu’elle ne peut être réalisée en moins de plusieurs millénaires par ces derniers. En revanche, le lancé de ce dé est quasiment instantané sur le prototype quantique de Google, puisque ce dernier implémente directement ledit circuit quantique, et ce avec une précision satisfaisante, c’est-à-dire pour vérifier que le bon dé avait été lancé. Cette réalisation, même imparfaite, semble pour le moment impossible à réaliser autrement que quantiquement.

    Cette prouesse semble loin de toute application pratique. Néanmoins, elle valide un courant de pensée remontant aux années 1980, en particulier aux propos de Feynman, affirmant que notre interprétation et compréhension de ce qui est calculable devait évoluer. Elle remet en cause les fondements du calcul remontant à la thèse de Church-Turing. Cette thèse, qui a évolué au fil des années, tendait à affirmer que tout progrès technologique ne remettrait jamais en cause le modèle mathématique du calcul défini par Church et Turing en 1936. Ce modèle permet de discerner ce qui est calculable par une machine de ce qui ne l’est pas. Quelques décennies après, cette thèse avait été reformulée ainsi : tout modèle de calcul raisonnable peut être simulé efficacement par une machine de Turing probabiliste (i.e. ayant accès à une source d’aléa). La notion de complexité y avait donc été ajoutée, rendant la thèse plus ambitieuse mais aussi plus fragile.

    Les fondations – Enigma bis ?

    Cette thèse étendue de Church-Turing a donc été remise en question au tout début de l’informatique quantique, lorsque Deutsch définit en 1985 la notion de machine de Turing quantique, avec son lot de premiers algorithmes exponentiellement plus rapides que leurs équivalents déterministes (mais pas encore probabilistes). D’abord perçu comme une curiosité, ce modèle de calcul finit par susciter intérêt et questionnements dans la communauté scientifique. Finalement en 1993, Bernstein et Vazirani construisent mathématiquement une machine universelle quantique efficace, c’est-à-dire le premier
    compilateur quantique (l’existence d’une machine programmable) qui valide mathématiquement le modèle de calcul (mais pas sa réalisation physique). En même temps arrive l’évidence qu’un ordinateur quantique peut être exponentiellement plus rapide qu’un ordinateur classique, i.e. qu’une machine de Turing probabiliste. Cependant les problèmes résolus sont tous artificiels et semblent encore bien loin de toute application concrète.

    C’est Simon puis Shor qui arrivent avec la première application algorithmique, et pas des moindres, en 1994, soit seulement une année après l’acceptation par la communauté du concept même de calcul quantique. En effet, cette application permettait de déchiffrer la plupart des messages cryptés par les mécanismes dits à clé publique, et de réduire à néant les procédés cryptographiques les utilisant (monnaie électronique, CB, vote électronique, authentification, …). Heureusement, l’ordinateur quantique n’existe pas (encore) ! Pourtant cette découverte n’est pas sans rappeler les découvertes de Turing et la construction de la machine qui a permis de déchiffrer les messages allemands eux-mêmes chiffrés par la machine Enigma durant la deuxième guerre mondiale…

    Les algorithmes quantiques – Une nouvelle façon de penser

    Néanmoins, deux décennies plus tard, alors que la possibilité d’une construction future d’un ordinateur quantique commençait à être prise au sérieux, une compétition scientifique internationale a été lancée en 2016 afin de définir les nouveaux standards de chiffrement post-quantique, ouvrant la voie à une longue recherche puis standardisation toujours en cours. Une autre alternative repose pourtant dans l’utilisation relativement simple de fibre optique afin de communiquer en encodant l’information directement sur des photons. Il s’agit du protocole quantique d’échange de clé proposé par Bennett et Brassard en 1984, soit 10 années avant la découverte de l’algorithme de Shor. En quelque sorte l’attaque et la parade reposent sur la même technologie, à ceci près que le protocole en question a déjà été construit et testé sur de grandes distances, un satellite dédié à même été envoyé par la Chine en 2016. L’Europe n’est pas en reste avec des projets d’infrastructure de grande envergure dédiés au déploiement de solutions quantiques de chiffrement. Cependant ces solutions quantiques nécessitent des technologies spécifiques, alors que les solutions algorithmiques dites post-quantiques pourraient être déployées sur les structures et ordinateurs actuels.

    Depuis 1994, les applications (calcul scientifique, optimisation, recherche opérationnelle, simulation, apprentissage automatique, IA…) foisonnent dans tous les domaines où l’informatique joue un rôle crucial, et pour des tâches où nos ordinateurs actuels ne sont pas assez puissants. Mais surtout les outils développés (transformée de Fourier quantique, estimation de phase, amplification d’amplitude, estimateur quantique, marche quantique, …) progressent continuellement, impactant toutes les thématiques de l’informatique, en en créant de nouvelles (information quantique, complexité hamiltonienne, simulation quantique, …), ou encore en tissant de nouveaux liens de l’informatique vers d’autres disciplines dont la physique, la chimie et les mathématiques.

    Mais avant tout l’informatique quantique a introduit une nouvelle façon d’analyser, raisonner et démontrer. Les outils existants précédemment n’étant plus adaptés, il a fallu en créer de nouveaux. Apportant un nouveau regard mathématique à des questions anciennes, ces nouveaux outils ont permis de progresser sur des questions ouvertes depuis de nombreuses années. Cette démarche a été baptisée preuve ou méthode quantique. Une preuve quantique est un peu l’analogue des nombres complexes pour la trigonométrie ou encore l’électricité : un outil très puissant permettant de mener facilement des calculs difficiles, ou encore d’établir des preuves inaccessibles jusque là, y compris dans des domaines pour lesquels ils n’ont pas été construits initialement. La dernière démonstration en date est la réfutation d’une célèbre conjecture en mathématiques (conjecture de Connes) à l’aide d’un résultat en théorie de la complexité quantique.

    Vision et formations nécessaires

    Une fois tous ces algorithmes quantiques découverts, dont l’utilisation de certains serait à n’en pas douter révolutionnaire, la question de la possibilité de construire un ordinateur les exécutant fut donc de plus en plus pressante. L’importance d’un plan d’envergure a d’abord émané de tous les acteurs concernés, scientifiques comme industriels, avec une feuille de route et des jalons intermédiaires appropriés, puis fut largement soutenue par les politiques. Plusieurs plans ont vu le jour, dont un au niveau européen à travers le Quantum Flagship en 2018, et le Plan Quantique national en 2021. L’avantage industriel que pourrait procurer la construction d’un ordinateur quantique, même imparfait, a créé une frénésie stimulante qui touche tous les secteurs stratégiques (finance, industrie, santé, sécurité…). Les progrès technologiques de grands groupes industriels, tels que Google et IBM par exemple, ont été de véritables locomotives, laissant apparaître rapidement que le plus grand défi serait de trouver une application à ces premiers prototypes, certes révolutionnaires, mais très éloignés des machines nécessaires aux applications précédemment découvertes en algorithmique quantique. En effet, non seulement ces machines sont petites, mais elles ont un taux d’erreur encore trop grand. Pourtant elles sont capables d’effectuer des calculs impossibles à réaliser classiquement, mais des calculs sans impact industriel actuellement.

    Un véritable travail de fourmi s’est donc enclenché, mais, pour l’instant, avec une communauté encore trop petite. Les mêmes personnes ont actuellement en charge de comprendre et de maîtriser toutes les facettes du calcul quantique, de la modélisation à la réalisation expérimentale en passant par la solution algorithmique, son analyse, sa programmation et sa vérification, là où la chaine de production constitue habituellement un véritable écosystème de l’informatique. Il nous faut donc nouer de multiples partenariats, construire et enseigner dans de nouvelles formations, afin de saisir cet unique défi que pourrait constituer ce nouveau tournant technologique.

    C’est dans ce contexte que le Collège de France m’a donc invité à occuper pour un an sa chaire Informatique et sciences numériques, et à donner dans ce cadre un cours sur les algorithmes quantiques. Ce cours tâchera de répondre à une demande croissante d’information et de formation de nombreux publics. Le public ciblé va des esprits curieux de saisir les possibilités et les limites du calcul quantique, aux acteurs des sciences informatiques au sens large : informaticiens, mathématiciens du numérique et physiciens des technologies quantiques, qu’ils soient étudiants, chercheurs, développeurs, entrepreneurs ou encore futurs utilisateurs des algorithmes quantiques.

    En guise de conclusion, il convient de rappeler que c’est en France, en 1980, qu’a débuté la révolution quantique expérimentale lorsque l’expérience du groupe d’Alain Aspect (CNRS) a validé à Orsay les prédictions de la physique quantique, qui ne pouvaient s’expliquer par la physique classique seule. Puis le prix Nobel a été décerné en 2012 à Serge Haroche (Collège de France) pour ses travaux sur la manipulation de systèmes quantiques. Le versant informatique de cette révolution a, lui, débuté en 1994 conjointement aux travaux outre-Atlantique, grâce à la vision de Miklos Santha (CNRS). Alors étudiant de master, j’ai suivi le mouvement de son équipe, qui était basée aussi à Orsay. Rapidement, Miklos a su constituer un groupe qui essaime, fait des émules en France et attire des talents internationaux. A l’époque, le pari pouvait sembler risqué, mais dans les années 2000, les possibilités de recrutement au CNRS et à l’Université sont plus nombreuses, et plusieurs chercheurs sont recrutés afin de mieux comprendre les liens que tisse le traitement de l’information quantique entre informatique, mathématiques et physique.

    Frédéric Magniez, Directeur de recherche CNRS,  Directeur de l’IRIF
    Pour la leçon inaugurale de la chaire annuelle Informatique et sciences numériques du Collège de France – 1er avril 2021

    Pour aller plus loin

    • Pages de Frédéric Magniez sur le site internet du Collège de France :
      https://www.college-de-france.fr/site/frederic-magniez/index.htm
    • Article sur les travaux de Frédéric Magniez dans CNRS le journal
      https://lejournal.cnrs.fr/articles/une-informatique-a-reinventer-pour-le-calcul-quantique

  • Comment une machine joue-t-elle au Cluedo ?

    La science est un bien commun et nous devons y avoir accès directement, pouvoir comprendre les publications scientifiques de toutes les disciplines, avec des sources fiables, de manière accessible et abordable. C’est ce que nous offre Papier-Mâché et … qui de mieux que de commencer par se faire expliquer ici comment … notre cerveau ou une machine pourrait faire une enquête policière, un processus de perception active. Bonne lecture ! Thierry Viéville

    Cet article est repris de « Comment une machine joue-t-elle au Cluedo ? Un modèle d’Intelligence Artificielle pour la recherche d’information.» du site Papier-Mâché, qui offre aussi une version d’approfondissement.

    ©papiermachesciences.org

    Les bons joueurs de Cluedo sont efficaces dans leur recherche d’information : ils planifient leurs actions afin d’obtenir le plus d’information possible en un minimum de temps. On appelle ce processus perception active, et c’est une capacité que les humains maîtrisent très bien. Pour les machines, en revanche, c’est plus compliqué. Dans un article de 2015, Matthijs Spaan, Tiago Veiga et Pedro U. Lima ont proposé un modèle dotant les machines de capacités de perception active, avec des applications dans le domaine de la robotique autonome pour la surveillance ou le sauvetage de personnes.

    Perception active et planification sous incertitude. Kesako ?

    En tant qu’humain, lorsque que l’on marche dans la rue, on absorbe de l’information sur ce qui se passe autour de nous : le feu piéton au vert, le tram qui arrive en station ou le fait que le bâtiment où l’on va se trouve droit devant nous. Ces informations sont intégrées par notre cerveau presque inconsciemment pendant qu’il est occupé à planifier la prochaine action pour nous amener à notre but final : notre rendez-vous chez le docteur. Quand on souhaite remplacer l’humain par un robot, un ordinateur ou n’importe quelle entité artificielle (appelée agent artificiel, souvent abrégé en agent), et lui permettre de planifier une séquence d’actions, on tombe dans un sous-domaine de l’Intelligence Artificielle, qui s’appelle la Planification Automatique. Dans le monde de la planification automatique, la plupart des problèmes considérés suivent ce schéma : l’agent calcule un plan lui permettant d’accomplir sa mission, et l’information qu’il obtient lors de l’exécution de ce plan est au service de la mission. La recherche d’information est alors un moyen pour atteindre un but et non le but en lui-même. Cependant, il existe certains cas d’applications où la recherche d’information n’est pas seulement un moyen pour l’agent d’atteindre un but mais constitue le but en lui-même. C’est par exemple le cas dans des applications de surveillance et de patrouille, mais aussi de recherche et de sauvetage, où la vie de personnes dépend de la capacité des sauveteurs et sauveteuses (humain·e·s ou artificiel·le·s) à collecter de l’information vite et bien.

    Ce processus s’appelle la Recherche active d’information ou Perception Active. Le but ici est de collecter le plus d’information possible à propos de certains points d’intérêts. Pensez notamment à une partie de Cluedo, où il vous faut trouver le coupable, l’arme et le lieu du crime. Vous devez donc vous déplacer dans l’environnement et récolter de l’information afin d’éliminer, les uns après les autres, suspect·e·s, armes, et lieux potentiels.

    Résoudre une énigme est plus qu’une devinette : on doit interagir avec l’environnement et nos actions le modifient. ©wikipedia

    Pour un humain, la perception active est simple. On la pratique depuis qu’on est gamin·e, quand on joue à cache-cache ou quand on cherche nos clefs. Notre cerveau y est entraîné. Mais comme souvent dans le domaine de l’Intelligence Artificielle, ce qui est facile pour un humain peut être très compliqué pour un agent artificiel. La perception active se fonde sur un modèle de connaissances de l’agent : il faut que l’on soit capable de modéliser ce que l’agent va considérer comme une certitude, mais également ce qu’il doit vérifier.

    Dans cet article, les auteurs se placent dans le cadre de la planification séquentielle sous incertitude : on souhaite trouver la meilleure séquence d’actions possible afin d’atteindre un but donné, tout en sachant que l’on ne connaît pas tout de l’environnement. Dans le cas de votre rendez-vous chez le docteur, vous allez tenter de trouver la meilleure suite d’actions (quel tram prendre, tourner à droite à la seconde rue, etc.) pour arriver chez le docteur le plus rapidement possible. Pour ce faire, une solution possible est d’attribuer une valeur à certains états et certaines actions que l’on juge désirables. Par exemple, l’état « je suis chez mon docteur » aura une forte valeur positive car c’est l’état que l’on souhaite obtenir. En revanche, l’état « je suis immobile sur la ligne de tram » aura une très forte valeur négative car c’est particulièrement dangereux. On va donc récompenser notre agent lorsqu’il est dans état désirable ou effectue une action désirable, et le pénaliser s’il est dans un état ou effectue une action non désirable. Dans ce cas, ce qu’on appelle récompense ou pénalité correspond à cette valeur mathématique que l’on attribue aux différents états et actions et qu’on l’on donne à l’agent lorsqu’il se trouve dans cet état ou effectue cette action. Le but de l’agent (= la façon dont il est programmé) va être de maximiser sa récompense, immédiate et potentielle.

    Le problème, c’est que dans la vraie vie, on n’a pas accès à toute l’information tout le temps. Par exemple, peut-être que le tram est au prochain croisement ou peut-être qu’il est à l’autre bout de la ligne. Selon la situation, la valeur associée à l’action « se trouver sur la ligne de tram » peut donc changer. Ce qui est possible en revanche, c’est de collecter de l’information sur la position du tram, par exemple en regardant sur l’application dédiée sur mon téléphone. L’information que j’obtiendrai ainsi ne sera pas absolument exacte (l’application peut avoir un léger décalage ou seulement donner le prochain arrêt par exemple) mais elle me permettra d’effectuer un raisonnement complexe, comme « le tram est 3 arrêts plus loin, je peux rester un peu sur la ligne sans danger, mais plus j’attends plus c’est dangereux ».

    Il existe un modèle mathématique, basé sur la théorie des probabilités, qui permet de modéliser ce genre de problème, et qui s’appelle le Processus de Markov Partiellement Observable (POMDP de son petit nom, prononcez pom-dé-pé). Les POMDP permettent de modéliser tout ce qui peut se passer dans notre monde : les états possibles, les effets possibles des actions de l’agent ainsi que leur probabilité d’occurrence, et ce que l’agent reçoit comme information lorsqu’il effectue une action.

    À partir de là, il existe de nombreux algorithmes qui permettent à un agent de raisonner sur l’ensemble des situations, de considérer les différentes actions possibles et de choisir la meilleure suite d’actions à effectuer en fonction de ce qu’il sait, de ce qu’il a vu du monde et afin d’atteindre son but. Par exemple, pour mon Cluedo, si je sais que j’ai la carte Salon dans la main, je ne vais généralement pas me déplacer dans le salon car je sais que ça ne fait pas partie de la solution. Néanmoins, l’une des limitations de ce modèle est que les valeurs ne peuvent être attribuées qu’à des états et des actions (par exemple : arriver chez le docteur). Or dans le cas de la recherche active d’information, le comportement désirable est celui qui permet à notre agent d’en apprendre le plus possible sur le monde. Il n’est donc pas lié à un état ou une action particulière mais à son état de connaissance : on aimerait récompenser l’agent s’il sait que le crime a eu lieu dans le salon. Peu importe si notre agent se trouve dans la cuisine ou la salle à manger et comment il le sait. L’important, c’est qu’il le sache. C’est cette limitation que les auteurs de l’article tentent de dépasser.

    Actions d’engagement : le Colonel Moutarde dans la cuisine avec le chandelier

    Un point clé est de « formaliser´´ la situation pour la réduire à un problème symbolique où la solution correspond à une sélection parmi les quelques choix possibles. ©wikipedia CC BY-SA

    Pour modéliser cette récompense basée sur l’état de connaissance d’un agent, les auteurs présentent un nouveau modèle basé sur les POMDP, qu’ils appellent POMDP-IR (pour POMDP with Information Reward ou POMDP avec récompense d’information en français). Dans ce nouveau modèle, les auteurs introduisent ce qu’ils appellent des actions d’engagement. Pour comprendre ce qu’est une action d’engagement, repensez au Cluedo. À la fin de la partie, lorsque vous avez obtenu assez d’information sur les différentes pièces, armes et suspect·e·s, vous êtes suffisamment sûr·e de vous pour émettre une accusation : « c’est le Colonel Moutarde dans la cuisine avec le chandelier ». Cette accusation est une action d’engagement : si vous avez raison, vous serez récompensé·e (vous gagnez la partie). Si vous avez tort, vous serez pénalisé·e (vous sortez du jeu). De ce fait, vous vous assurez d’avoir suffisamment d’information avant d’émettre votre accusation. Et bien dans cet article, les auteurs ont créé des agents capables de jouer de Cluedo ! Grâce aux actions d’engagement, l’agent se focalise sur les actions qui lui permettent de récolter de l’information afin d’obtenir un état de connaissance suffisant avant de s’engager, et donc soit de recevoir une récompense (s’il a raison), soit d’être pénalisé (s’il a tort).

    Mais nos agents POMDP-IR ne sont pas que des joueurs de Cluedo et peuvent faire bien plus. En effet, un POMDP-IR permet de modéliser, en parallèle des actions d’engagement, n’importe quelle autre action qui serait modélisable dans un POMDP. À chaque action, l’agent peut alors décider simultanément d’une action « normale » et de s’engager ou non. De ce fait, le POMDP-IR permet de modéliser des problèmes multi-objectifs, où l’agent doit mettre en œuvre sa perception active tout en poursuivant une autre mission. On peut imaginer par exemple le cas de missions de sauvetage où l’agent doit retrouver des victimes et sécuriser l’environnement. Sécuriser l’environnement est la mission « classique » (au sens des POMDP, car il s’agit de modifier l’état de l’environnement par les actions de l’agent), alors que retrouver les victimes est une mission de perception active (modélisable par un POMDP-IR), car on attend de l’agent qu’il prenne des actions d’engagement du type « je sais qu’il y a un blessé au troisième étage ».

    Donc on peut maintenant récompenser un agent pour effectuer sa mission tout en ayant un état de connaissance suffisant. Mais, ça veut dire quoi suffisant ?

    Les auteurs nous disent : suffisant, ça dépend du contexte ! Évidemment, ce que vous considérez comme étant un état de connaissance suffisant dépend énormément de votre application. S’il s’agit d’indiquer à l’utilisateur·rice que le café est prêt, les erreurs ne sont pas bien graves. Par contre s’il s’agit de secourir des victimes, une erreur pourrait vous coûter cher. Les auteurs démontrent également qu’à vouloir être trop sûr, l’agent risque de se focaliser sur sa recherche d’information, quitte à délaisser toute autre mission qui pourrait lui être confiée. Dans le cas de notre agent de sauvetage par exemple, si l’on demande à l’agent d’être trop sûr d’où se trouvent les victimes, notre agent va passer son temps à vérifier et re-vérifier chaque pièce en négligeant de sécuriser l’environnement, risquant ainsi la vie de ses coéquipiers.

    Pourquoi ce modèle est-il intéressant ?

    Dans le monde de la recherche en Intelligence Artificielle, produire un nouveau modèle ne suffit pas, encore faut-il qu’il soit intéressant. Alors comment détermine-t-on qu’un modèle est intéressant ? Souvent grâce à deux questions :

    1. Ce modèle permet-il de modéliser un type de problème qu’on ne savait pas traiter jusque là ? Si oui, il permet d’accroître le nombre de problèmes qu’un agent artificiel peut traiter et il est donc intéressant.

    2. Si d’autres modèles permettent déjà de modéliser le même type de problème que ce nouveau modèle, ce nouveau modèle est-il meilleur que l’ensemble des autres modèles existant ?

      • Est-il plus simple à appliquer ?
      • Donne-t-il de meilleurs résultats ?

    Dans notre cas, le POMDP-IR introduit par Matthijs Spaan et ses collègues ne permet pas de modéliser de nouveaux problèmes car il existe déjà un autre modèle permettant de traiter le problème de la recherche active d’information. Ce modèle, appelé ρ-POMDP, a été proposé cinq ans plus tôt (en 2010) par Mauricio Araya-Lopez et ses collègues [1]. D’après ses auteurs, le POMDP-IR permet de meilleurs résultats que le ρ-POMDP, au sens où un agent qui suivrait un POMDP-IR aura une meilleure récompense finale (et donc sera a priori plus efficace dans sa tâche) qu’un agent qui suivrait un ρ-POMDP.

    Conclusion et discussion

    Le modèle développé par les auteurs dans cet article permet à un agent de raisonner sur ses connaissances afin d’agir au mieux pour acquérir de nouvelles connaissances tout en poursuivant d’autres buts. Ce modèle se base essentiellement sur la notion d’actions d’engagement, qui permettent de récompenser l’agent lorsque celui-ci obtient un bon niveau de connaissance sur le monde.

    L’une des difficultés majeures associées à ce modèle est de trouver le bon équilibre entre les différentes missions. C’est un aspect qui n’est pas du tout abordé dans l’article, mais qui est pourtant capital afin d’obtenir un comportement adéquat. En effet, dans le cas de notre agent de sauvetage, l’agent est récompensé s’il trouve les victimes correctement et s’engage sur leur position, mais également s’il sécurise au mieux l’environnement. La relation entre ces deux récompenses est tout aussi capitale que le degré de suffisant afin d’obtenir un agent qui effectue bien ses deux missions. Une récompense trop élevée pour la sécurisation de l’environnement par rapport à celle pour la recherche de victimes va inciter l’agent à prioriser la sécurisation et négliger la recherche des victimes, et inversement une récompense de sécurisation trop faible par rapport à la récompense de recherche de victime va inciter l’agent à négliger sa tâche de sécurisation. Ce problème n’est cependant pas propre au POMDP-IR, puisqu’il existe dans tout modèle la nécessité de trouver un compromis entre différents objectifs, ce qui implique malheureusement souvent une suite d’essais et d’erreurs afin de trouver la bonne configuration.

    Le problème de raisonner et planifier sur l’état de connaissance d’un agent est un sujet qui suscite énormément d’intérêt dans la communauté de recherche sur la planification automatique. Ce (relativement) nouveau domaine de recherche est appelé Planification Épistémique et verra probablement émerger de nombreux modèles dans le futur, ouvrant ainsi la voie à beaucoup de nouvelles applications.

    Note : l’autrice de ce papier-mâché est actuellement en collaboration avec les auteurs de la publication initiale. Cette collaboration a débuté après la publication dudit article, mais concerne un sujet similaire à celui abordé ici.

    [1] Araya-Lopez M., Buffet O., Thomas V., Charpillet F., A POMDP Extension with Belief-dependent Rewards. NIPS Proceedings, 2010. [Publication scientifique]

    Écriture : Jennifer Renoux
    Relecture scientifique : Cédric Buron et Vincent Thomas
    Relecture de forme : Aurélien Didier, Alexandre Fauquette et Christine Duthoit

    Temps de lecture : environ 11 minutes.
    Thématiques : Intelligence artificielle (Informatique et Sciences cognitives)

    Publication originale : Spaan M., et al., Decision-theoretic planning under uncertainty with information rewards for active cooperative perception. Autonomous Agents and Multi-Agent Systems, 2014. DOI : 10.1007/s10458-014-9279-8