L’équipe BISCUIT (Bio-Inspired Situated Cellular and Unconventional Information Technology) rassemble des chercheurs intéressés par l’informatique non conventionnelle, considérant en particulier les modèles d’intelligence artificielle bio-inspirés, tout en s’attachant à « faire réellement quelque chose avec des Populations de calcul Spatialisées et Décentralisées (SDP) », plutôt que de modéliser avec précision les structures du cerveau. Cette équipe souhaite étudier de nouveaux paradigmes computationnels pour s’attaquer à des problèmes difficiles comme la robotique autonome, le calcul cognitif situé, etc. La pertinence de ces paradigmes non conventionnels vient de l’idée que le cerveau est plus performant que la technologie humaine pour contrôler des agents autonomes (les animaux par exemple). De plus, même si cela prête à controverse (Jones, 2000), lorsque des architectures du système nerveux plus récentes dans l’évolution, comme le cortex, sont prises en compte, il apparaı̂t que la génétique code le développement anatomique de systèmes assez homogènes, systèmes qui sont ensuite adaptés, par apprentissage, lorsque l’animal interagit avec le monde (Miller et al., 2001; Ballard, 1986; Stavrinou et al., 2007). Lorsqu’ils sont considérés comme des solutions biologiques à des problèmes de robotique, les cerveaux montrent que calculer en rassemblant une grande population de petits circuits élémentaires de calcul (par exemple les micro-colonnes dans le cortex (Mountcastle, 1997)) est un moyen robuste et efficace de contrôler les agents artificiels. Mais, la reproduction des modes et capacités de calcul des cerveaux n’étant pas encore atteinte, les chercheurs en informatique ne comprennent pas totalement ces phénomènes.
Parmi toutes les caractéristiques qui peuvent être transférées de la biologie à l’informatique, ce doctorat souhaite mettre l’accent sur l’auto-organisation, à la suite de la démarche fondatrice de Kohonen (Kohonen, 1997). Kohonen s’est inspiré de la biologie du cortex pour son modèle de cartes auto-organisatrices (SOM), modèle qui est aujourd’hui un algorithme d’apprentissage artificiel éprouvé pour l’apprentissage non supervisé. Les travaux antérieurs des membres de l’équipe portent également sur l’auto-organisation, en insistant sur une approche plus spécifiquement SPD (Ménard, 2006; Alecu, 2011; Lefort, 2012; Khouzam, 2014), approche qui n’est pas centrale dans les SOMs classiques. L’idée est de considérer les modules SPD auto-organisateurs comme des blocs élémentaires de calcul pour les architectures multi-cartes (Ménard and Frezza-Buet, 2005). La manière dont plusieurs modules d’auto-organisation doivent être connectés reste un problème crucial de cette approche, sachant qu’ils peuvent également être connectés à eux-mêmes. Ils deviennent alors en mesure de traiter des séquences de données, donc la nature temporelle de l’information (Khouzam and Frezza-Buet, 2013). Nos travaux antérieurs ont montré deux limitations principales. Ils n’ont été appliqués qu’à des problèmes jouets de « preuve de concept » et ils nécessitent une grande quantité de calculs parallèles (Gustedt et al., 2010), puisque les mécanismes intrinsèques reposent sur des populations à grande échelle d’unités de calcul élémentaires. Cela restreint fortement la possibilité d’explorer des architectures composées de nombreux modules SPD et d’espérer une utilisation temps-réel, en robotique autonome par exemple. Plus récemment, une thèse qui se termine dans l’équipe a ouvert la voie sur ces questions, au niveau d’une approche intermédiaire qui définit une méthodologie de construction d’architectures complexes. Il s’agit, à base d’une adaptation des SOMs, de définir des briques élémentaires et leurs échanges pour permettre un passage à l’échelle. Ces briques auto-organisatrices forment un système dynamique dont la relaxation vers des bassins d’attraction constitue l’établissement d’un consensus (Gonnier et al., 2021; Gonnier et al., 2020). Cette méthodologie, pour le moment prometteuse, reste toutefois à stabiliser, à expérimenter sur des problèmes temporels et à décliner au delà des approches jouets qui ont guidé ses validations.
C’est l’objet de la thèse proposée.
Nous proposons de décliner la partie expérimentale de cette thèse dans un contexte robotique. Ce doctorat n’est pas une contribution directe à la robotique, puisque le but est d’aborder le calcul SPD plutôt que de fournir à un robot des capacités qui dépassent celles de l’état de l’art. Néanmoins, un défi pour cette thèse sera d’utiliser un véritable robot comme plate-forme de validation. Pour ce faire, la smartroom de CentralSupélec sera disponible : les applications aux drones (Quadricoptères Parrots), pour lesquels nous avons de premiers résulats (Gonnier et al., 2021), ou aux robots roulants ( Kheperas, turtlebots) peuvent être facilement accessibles, en utilisant ROS.
Comme nous l’avons déjà écrit, les modules d’auto-organisation ont déjà été abordés au sein de l’équipe, en se concentrant sur le calcul de populations à grains fins. Un virage récent a été pris vers des architectures plus mésoscopiques à base de SOMs adaptées à la prise en charge d’un consensus pour diriger les processus d’auto-organisation. Il reste toutefois aujourd’hui à construire des architectures multi-cartes avec de nombreux composants et à analyser leur comportement dynamique. Des approches multicartes de l’auto-organisation ont été proposées dans la littérature (Johnsson et al., 2009), ainsi que des approches récurrentes pour le traitement temporel (Voegtlin, 2002; Hagenbuchner et al., 2001), mais le nombre de modules impliqués reste faible : dans les contributions où il est supérieur à un, il reste toujours inférieur à trois. Le type de calculs que peuvent réaliser des architectures auto-organisatrices composées d’un grand nombre de modules reste à investiguer, même après la définition de la méthodologie posée par les travaux en cours dans l’équipe.
Le doctorant ou la doctorante sera accueilli(e) au Loria, laboratoire bi-localisé à Nancy et Metz (campus de CentralSupelec). Il ou elle travaillera sur les deux sites, à sa convenance, sous la supervision de Hervé Frezza-Buet et Yann Boniface. Une collaboration scientifique avec les autres membres de l’équipe est attendue, ainsi que des discussions scientifiques plus générales et des collaborations avec d’autres membres du laboratoire. La durée prévue du doctorat est de trois ans.
Des références à la biologie devant être prises en compte, un goût pour l’innovation et les approches pluridisciplinaires est attendu. De bonnes compétences en programmation sont également requises, les outils que nous mettons à disposition pour l’étude étant écrits dans les langages C++ et Python en particulier.
L’équipe fournira un ensemble d’outils de programmation, de plates-formes robotiques et tout le soutien humain nécessaire pour les aspects techniques, ce qui permettra au doctorant ou à la doctorante de se concentrer sur les questions scientifiques. Voir par exemple la suite cxsom (https://github.com/HerveFrezza-Buet/cxsom).
Equipe MOCQUA
Encadrants : Nazim Fatès – nazim.fates@loria.fr
Sylvain Contassot-Vivier – sylvain.contessotvivier@loria.fr
PDF : Etude du problème de la réduction de dettes mutuellles entre entreprises
Localisation : Inria Nancy Grand Est, LORIA
La réduction des dettes mutuelles entre entreprises est un enjeu macroéconomique majeur, tout particulièrement pressant dans les phases descendantes du cycle économique, où les liquidités peuvent manquer à certaines entreprises et conduire à des faillites en chaîne (effet domino). L’idée du projet est de nous intéresser aux réseaux de paiement entre entreprises pour réduire la dette qu’ils contiennent. Nous modélisons le problème par un graphe dont les sommets représentent des entreprises et les arcs représentent des factures émises pendant un laps de temps donné (par exemple un mois). Comme ces factures sont généralement payées avec un certain délai (trois mois en moyenne en zone euro) les dettes qu’elles représentent peuvent être réduites par compensation multilatérale, c’est-à-dire que l’on supprime les dettes communes d’un ensemble d’acteurs et que l’on compense les restes dus à l’aide d’un acteur extérieur. Cela est particulièrement clair dans le cas où ces dettes forment un cycle et mais ces compensations multilatérales peuvent également être appliquées dans le cas de chaînes, de structures arborescentes, etc. Ce système vise donc à diminuer le besoin de liquidités des entreprises et pourrait avoir des effets bénéfiques sur les échanges à l’intérieur d’un groupe d’acteurs économiques fortement reliés. Nous souhaitons concevoir des algorithmes innovants pour réaliser une réduction de dettes mutuelles sur graphes de paiement réels fournis par un opérateur de facturation électronique. Nous disposons de jeux de données qui regroupent plusieurs millions d’échanges réalisés par des entreprises en Italie en 2019 et 2020.
L’originalité de notre approche est de travailler avec un financement intégral des factures : à chaque application de l’algorithme, les factures sélectionnées sont totalement supprimées et les entreprises qui ont un bilan négatif reçoivent un financement de la part d’un acteur extérieur.
Le but est donc de choisir le bon ensemble de factures à financer, de manière à maximiser la dette globale supprimée tout en minimisant l’apport extérieur. D’un point de vue algorithmique, le problème est NP-complet; obtenir des solutions optimales est donc hors d’atteinte pour des graphes de grande taille. Notre but est donc de concevoir des méthodes approchées pour traiter des graphes de plusieurs centaines de milliers de sommets et d’appliquer ces méthodes dans des économies réelles. Nous cherchons également à traiter la dimension temporelle du problème, c’est-à-dire l’application des cycles financement-remboursement sur une longue période.
Le travail de recherche consistera donc principalement à analyser la structure des graphes réels et à rechercher des heuristiques de réduction de dettes. Les travaux peuvent se décomposer comme suit :
– analyser la structure des graphes réels, notamment la présence de communautés, c’est-à-dire d’acteurs fortement reliés entre eux,
– générer des jeux de données pseudo-aléatoires semblables aux graphes réels de manière à pouvoir travailler sur des graphes de taille arbitraire,
– inventer et mettre en oeuvre différents algorithmes de réduction de dette et évaluer leurs performances (temps de calcul, propriétés des solutions, robustesse aux changements topologiques, etc.).
Nous souhaiterions donc recruter une personne ayant une aisance en informatique, en mathématiques discrètes, et un esprit d’ouverture vers les problèmes de nature économique, lesquels peuvent rapidement devenir complexes étant donné le nombre de contraintes que l’on peut vouloir prendre en compte pour une application réelle de ces méthodes.
– Massimo Amato, Nazim Fatès, Lucio Gobbi. The economics and algorithmics of an integral settlement procedure on B2B networks, rapport technique,
– Marie Vela-Mena. Heuristic methods for mutual debt reduction on B2B networks, Mémoire de stage de L3,
– Arthur Rousseau. Génération de graphes pour la compensation de dettes mutuelles entre entreprises, Mémoire de stage de L3,
Equipe :
BISCUIT, Loria
Encadrement :
Hervé Frezza-Buet (HDR), Alain Dutech (HDR)
Herve.Frezza-Buet@centralesupelec.fr & Alain.Dutech@loria.fr
Tous les détails dans le PDF à télécharger.
L’équipe BISCUIT [1] , est une équipe du laboratoire Loria [2] quirassemble des chercheurs intéressés par de nouveaux paradigmes informatiques. Il s’agit d’une informatique où les calculs sont adaptatifs, distribués et décentralisés, réalisés par une foule d’unités de calcul simples qui communiquent principalement avec leurs proches voisins. Ces propriétés sont compatibles avec la mise en œuvre de principes d’auto-organisation non-supervisés, mais guidés, pour s’attaquer à des problèmes difficiles comme le calcul cognitif situé, la robotique autonome, l’allocation adaptative de ressources de calcul, etc.
Le cerveau est une preuve de l’efficacité et des capacités d’adaptation que l’on peut atteindre en s’appuyant sur ce genre de principes. Sa structure, relativement homogène mais déjà partiellement spécifiée dans le code génétique, va se développer, s’organiser, se spécialiser et se modulariser grâce aux interactions entre l’homme, ou plus généralement l’animal, et son monde. Cette théorie de l’émergence de la cognition (McClelland, 2010) est séduisante, mais ses phénomènes sous-jacents sont encore mal compris. D’ailleurs, les progrès récents en matière d’apprentissage profond ne font malheureusement pas progresser la connaissance dans cette direction.
C’est dans cette optique que nous voulons explorer ce qui nous semble être une composante essentielle, et très rarement abordée, de l’émergence du comportement. Les agents artificiels que nous considérons évoluent dans des espaces sensorimoteurs continus, aussi bien au niveau temporel que spatial. À l’inverse, les processus cognitifs les plus élémentaires s’appuient des moments où sont prises des décisions. Dans le décours continu du temps, ces moments sont des points où une reconnaissance émerge des signaux perçus, où une action est déclenchée. L’agent, selon ce principe, est cognitif dans la mesure où il interagit avec son environnement par scansion, en construisant les événements nécessaires à son couplage avec le monde
extérieur. Palper du regard une scène, pour reprendre l’expression de Merleau-Ponty, y détecter un objet particulier, décider de le saisir, sont autant de production d’événements où perception et action se confondent. Se pose alors la question de savoir comment se crée ce concept d’événement, comment le monde passe d’un continuum en perpétuelle évolution à une suite d’événements discrets qui s’enchaı̂nent. Comment se construit un rapport
au monde compatible avec le raisonnement ? Comment passe-t-on d’un agent purement réactif à un agent qui prend une décision ?
L’équipe BISCUIT s’attache à « faire réellement quelque chose avec des populations de calcul spatialisées et Décentralisées (SDP) [3] », plutôt
que de modéliser avec précision les structures du cerveau. Le sujet de thèse de doctorat proposé est un pas de plus dans cette direction.
Références
[1]. Bio-Inspired Situated Cellular and Unconventional Information
Technology, http://biscuit.loria.fr/
[2]. www.loria.fr
[3]. Spatialized and Decentralized Population
En intelligence artificielle, la planification d’actions consiste à trouver quelles actions un agent doit effectuer pour atteindre un objectif donné. Ce sujet de thèse se concentre plus spécifiquement sur la planification probabiliste, pour laquelle les résultats des actions peuvent être incertains, et l’état courant du système n’est que partiellement connu, avec des observations éventuellement bruitées [6]. Lorsqu’un humain interagit avec un système de planification, il peut avoir différentes attentes concernant la stratégie construite par planification ou avoir des demandes particulières. Par exemple,
Dans les deux cas, le système de planification doit pouvoir être le plus transparent possible pour l’humain, soit en lui fournissant des éléments rendant compte de la stratégie proposée (cas 1), soit en proposant au robot une stratégie qui laissera le moins d’incertitudes à l’interprétation possible (cas 2). Dans tous les cas, pour pouvoir construire la meilleure réponse possible, il peut être important de tenir compte du point de vue de l’humain : ce qu’il sait ou pourrait savoir de la dynamique, de la situation actuelle, des objectifs.
De manière plus générale, diverses questions peuvent se poser concernant l’information dont dispose soit l’humain, soit même l’agent. Ces questions abordent différentes thématiques, que ce soit l’explicabilité (donner des éléments de réponses pour expliquer la stratégie construite), l’interprétabilité (construire une stratégie la plus lisible pour l’humain lors de son exécution) ou la confidentialité et le respect de la vie privée (construire une stratégie qui masque les intentions du robot pour un observateur extérieur ou qui dévoile le moins possible des données personnelles que l’humain souhaiterait garder confidentielles).
La littérature a typiquement abordé de telles questions indépendamment les unes des autres. Récemment, Chakkraborti et al. [2, 3] ont proposé une étude et des définitions formelles de ces différentes problématiques dans le cadre de la planification automatique en générale et la théorie de l’information. De manière similaire, nous souhaitons, dans cette thèse, adopter un point de vue unifié, en faisant le choix de quantifier les incertitudes mises en jeu de manière bayésienne, et voir quels outils proposer pour répondre à ces questions dans le cadre de modèles de décision markoviens [6]. Des modèles particuliers permettent déjà de raisonner par exemple sur l’information dont dispose l’agent lui-même (comme les ρ-POMDP [1, 5] que nous avons proposé par le passé) ou encore sur l’interaction collaborative ou compétitive avec d’autres agents (POSG [8, 4] et I-POMDP [7]).
L’objectif de cette thèse est de proposer une méthode systématique pour décrire, formaliser et résoudre tout problème combinant une tâche de planification et une volonté de contrôler ou d’optimiser certaines informations détenues par l’un ou l’autre acteur, humain ou agent.
Nous sommes à la recherche de candidats avec un intérêt marqué pour l’intelligence artificielle et la planification. Le candidat devra être à l’aise avec le cadre des probabilités ainsi qu’avoir de très bonnes compétences en programmation.
[1] M. Araya-López, O. Buffet, V. Thomas et F. Charpillet. “A POMDP Extension with Belief-dependent Rewards”. In : NIPS-10. 2010.
[2] T. Chakraborti, A. Kulkarni, S. Sreedharan, D. E. Smith et S. Kambhampati. “Explicability ? Legibility ? Predictability ? Transparency ? Privacy ? Security ? The Emerging Landscape of Interpretable Agent Behavior”. In : ICAPS-19. 2021. URL : https://ojs.aaai.org/index.php/ICAPS/article/view/3463.
[3] T. Chakraborti, S. Sreedharan et S. Kambhampati. “The Emerging Landscape of Explainable Automated Planning & Decision Making”. In : IJCAI-20. 2020. DOI : 10.24963/ijcai.2020/669.
[4] A. Delage, O. Buffet et J. Dibangoye. “HSVI fo zs-POSGs using Concavity, Convexity and Lipschitz Properties”. In : CoRR/arXiv (2021). URL : https://arxiv.org/abs/2110.14529.
[5] M. Fehr, O. Buffet, V. Thomas et J. Dibangoye. “rho-POMDPs have Lipschitz-Continuous epsilon-Optimal Value Functions”. In : NIPS-18. 2018.
[6] F. Garcia et al. Markov Decision Processes and Artificial Intelligence. Sous la dir. d’O. Sigaud et O. Buffet. ISBN : 978-1-84821-167-4. ISTE – Wiley, 2010, p. 480.
[7] P. Gmytrasiewicz et P. Doshi. “Interactive POMDPs : Properties and Preliminary Results”. In : AAMAS-04. 2004.
[8] E. A. Hansen, D. Bernstein et S. Zilberstein. “Dynamic Programming for Partially Observable Stochastic Games”. In : AAAI-04. San Jose, CA, 2004.
