Search

In this thesis, we focus on radio resource planning issues for low power wide area networks based on NB-IoT and LoRa technologies. In both cases, the average behavior of the network is considered by assuming the sensors and the collectors are distributed according to independent random Poisson Point Process marked by the channel randomness. For the NB-IoT, we elaborate a statistical dimensioning model that estimates the number of radio resources in the network depending on the tolerated delay access, the density of active nodes, the collectors, and the antenna configuration with single and multi-user transmission. For the LoRa network, we propose a multi-sub band allocation technique to mitigate the high level of interference induced by nodes that transmit with the same spreading factor. To dynamically allocate the spreading factor and the power, we present a Q-learning multi-agent approach to improve the energy efficiency., Cette thèse étudie le problème de planification des ressources pour les réseaux IoT longues portées basés sur les technologies NB-IoT et LoRa. Dans les deux cas, on suppose que les capteurs et les collecteurs sont distribués suivant des processus de points de Poisson spatial indépendants marqués par le caractère aléatoire du canal. Pour le NB-IoT, nous élaborons un modèle de dimensionnement statistique qui estime le nombre de ressources radio nécessaires en fonction du délai d’accès toléré, de la densité des nœuds actifs, des collecteurs et de la configuration de l’antenne. Pour le réseau LoRa, nous proposons une technique d’allocation de plusieurs sous-bandes pour atténuer le niveau élevé d’interférence induit par les nœuds qui transmettent avec le même facteur d’étalement. Pour allouer dynamiquement le facteur d’étalement et la puissance, nous présentons une approche d’apprentissage automatique avec multi-agents qui permet d’améliorer l’efficacité énergétique.

International audience; La résolution d'anaphores est une tâche fondamentale pour la plupart des applications du TALN. Cette tâche reste un problème difficile qui nécessite plusieurs sources de connaissances et des techniques d'apprentissage efficaces, notamment pour la langue arabe. Cet article présente une nouvelle approche de résolution d'anaphores pronominales dans les textes arabes en se basant sur une méthode d'Apprentissage par Renforcement AR qui utilise l'algorithme Q-learning. Le processus de résolution comporte une étape d'identification des pronoms et des antécédents candidats et une autre de résolution. L'algorithme Q-learning permet d'apprendre dans un environnement dynamique et incertain. Il cherche à optimiser pour chaque pronom anaphorique, une séquence de choix de critères pour évaluer les antécédents et sélectionner le meilleur. Le système de résolution est évalué sur des textes littéraires, des textes journalistiques et des manuels techniques. Le taux de précision atteint jusqu'à 77,14\%.

National audience; Nous nous intéressons aux techniques d'apprentissage par renforcement dans les systèmes multi-agents coopératifs. Nous présentons un nouvel algorithme pour agents indépendants qui permet d'apprendre l'action jointe optimale dans des jeux où la coordination est difficile. Nous motivons notre approche par le caractère décentralisé de cet algorithme qui ne nécessite aucune communication entre agents et des tables Q de taille indépendante du nombre d'agents. Des tests concluants sont de plus effectués sur des jeux coopératifs répétés, ainsi que sur un jeu de poursuite.

National audience; Cet article présente les résultats expérimentaux obtenus avec une architecture originale permettant un apprentissage générique dans le cadre de processus décisionnels de Markov factorisés observables dans le désordre (PDMFOD). L'article décrit tout d'abord le cadre formel des PDMFOD puis le fonctionnement de l'algorithme, notamment le principe de parallélisation et l'attribution dynamique des récompenses. L'architecture est ensuite appliquée à deux problèmes de navigation, l'un dans un labyrinthe et l'autre dans un trafic routier (New York Driving). Les tests montrent que l'architecture permet effectivement d'apprendre une politique de décisions performante et générique malgré le nombre élevé de dimensions des espaces d'états des deux systèmes.

International audience

The aim of this thesis is to propose an algorithmic approach, which allows to treat the problems of adaptive routing (AR) in telecommunication networks with irregular traffic. The analysis of the existing approaches has lead us to base our work on the Q-Routing (QR) algorithm. This algorithm uses a reinforcement learning technique which is based on Markov models. The efficiency of these routing approaches depends on information about the network load and the nature of data flows. This information must be sufficient and relevant and it has to reflect the real network load during the decision making phase. To overcome drawbacks of techniques using QR, we have proposed two AR algorithms. The first one, which is called Q-Neural Routing, is based on a stochastic neural model, used for parameter estimation and updating required for routing. In order to reduce the convergence time, a second approach is proposed: k-Shortest path Q-Routing. It is based on a multi-paths routing technique combined with the QR algorithm. In this case, the exploration space is limited to k-Best paths. The proposed algorithms are validated and compared to traditional approaches using the OPNET Simulator. Their efficiency, with respect to AR, is illustrated. In fact, these algorithms allow taking into account the network state in a better way than the classical approaches do., L'objectif de ce travail de thèse est de proposer des approches algorithmiques permettant de traiter la problématique du routage adaptatif (RA) dans un réseau de communication à trafic irrégulier. L'analyse des algorithmes existants nous a conduit à retenir comme base de travail l'algorithme Q-Routing (QR); celui-ci s'appuie sur la technique d'apprentissage par renforcement basée sur les modèles de Markov. L'efficacité de ce type de routage dépend fortement des informations sur la charge et la nature du trafic sur le réseau. Ces dernières doivent être à la fois, suffisantes, pertinentes et reflétant la charge réelle du réseau lors de la phase de prise de décision. Pour remédier aux inconvénients des techniques utilisant le QR, nous avons proposé deux algorithmes de RA. Le premier, appelé Q-Neural Routing, s'appuie sur un modèle neuronal stochastique pour estimer et mettre à jour les paramètres nécessaires au RA. Afin d'accélérer le temps de convergence, une deuxième approche est proposée : K-Shortest path Q-Routing. Elle est basée sur la technique de routage multi chemin combiné avec l'algorithme QR, l'espace d'exploration étant réduit aux k meilleurs chemins. Les deux algorithmes proposés sont validés et comparés aux approches traditionnelles en utilisant la plateforme de simulation OPNET, leur efficacité au niveau du RA est mise particulièrement en évidence. En effet, ceux-ci permettent une meilleure prise en compte de l'état du réseau contrairement aux approches classiques.

In the microrobotics field, the control of systems is difficult because the physical phenomena connected to the microscopic scale are complex. The reinforcement learning methods constitute an interesting approach because they allow to draw up a control policy without any knowledge of the system. With regard to the large dimensions of the state spaces of the studied systems, we developed a parallel approach which is inspired by the behaviour-based architectures and by the reinforcement learning. This architecture is based on parallel Q-Learning algorithms. It allows to reduce the system complexity and to speed up the learning process. On the gridworld example, the results are good but the learning time is too long to control a real system. Then, the Q-Learning algorithm was replaced by the Dyna-Q algorithm which we adapted to the control of no deterministic systems by using a chronological account of the last transitions. This architecture, called parallel Dyna-Q, allows to increase the convergence speed and also to find better control policies. The experiments done with the real manipulation system show that the learning is possible in real time without no need of simulations. The behaviours co-ordination function works well if the obstacles are separated from each others. If that is not case, it can create local maxima which trap temporarily the system in a cycle. So, we developed another co-ordination function which creates a more global model of the system from the model of transition built with the Dyna-Q algorithm. This new co-ordination function allows to go out of local maxima if the temporal pattern matching function used by the architecture is sturdy., En microrobotique, la commande des systèmes est délicate car les phénomènes physiques liés à l'échelle microscopique sont complexes. Les méthodes dites d'apprentissage par renforcement constituent une approche intéressante car elles permettent d'établir une stratégie de commande sans connaissance \emph(a priori) sur le système. Au vu des grandes dimensions des espaces d'états des systèmes étudiés, nous avons développé une approche parallèle qui s'inspire à la fois des architectures comportementales et de l'apprentissage par renforcement. Cette architecture, basée sur la parallélisation de l'algorithme du Q-Learning, permet de réduire la complexité du système et d'accélérer l'apprentissage. Sur une application simple de labyrinthe, les résultats obtenus sont bons mais le temps d'apprentissage est trop long pour envisager la commande d'un système réel. Le Q-Learning a alors été remplacé par l'algorithme du Dyna-Q que nous avons adapté à la commande de systèmes non déterministes en ajoutant un historique des dernières transitions. Cette architecture, baptisée Dyna-Q parallèle, permet non seulement d'améliorer la vitesse de convergence, mais aussi de trouver de meilleures stratégies de contrôle. Les expérimentations sur le système de manipulation montrent que l'apprentissage est alors possible en temps réel et sans utiliser de simulation. La fonction de coordination des comportements est efficace si les obstacles sont relativement éloignés les uns des autres. Si ce n'est pas le cas, cette fonction peut créer des maxima locaux qui entraînent temporairement le système dans un cycle. Nous avons donc élaboré une autre fonction de coordination qui synthétise un modèle plus global du système à partir du modèle de transition construit par le Dyna-Q. Cette nouvelle fonction de coordination permet de sortir très efficacement des maxima locaux à condition que la fonction de mise en correspondance utilisée par l'architecture soit robuste.

Nos travaux se concentrent sur l'apprentissage d'environnement qui est un moyen de rendre les systèmes autonomes plus adaptatifs. Dans un premier temps, nous avons employé une approche cognitive qui a débouché sur une nouvelle méthode pour la construction et la mise à jour d'un modèle géométrique du monde. Partant de deux modèles assez frustres du monde, notre algorithme introduit une méthodologie de fusion composée d'une suite d'opérations simples. Notre méthode aboutit à un modèle du monde comparable, en précision et en robustesse, aux modèles classiquement construits par un fitrage numérique de Kalman. Notre approche est cependant plus flexible - il suffit par exemple d'utiliser des modèles de base diffèrents - ce qui permet de concevoir des systèmes plus autonomes. Néanmoins, seul un traitement de plus en plus complexe et spécifique des informations manipulées par notre modèle peut encore augmenter son utilité et son adaptabilité, ce qui, finalement, nuit au caractère autonome d'un robot. Nous pensons que cette critique se généralise à l'approche classique de la robotique mobile. Nous nous sommes donc tournés, dans un deuxième temps, vers l'apprentissage de comportements. Pour cela, nous avons développé un nouvel algorithme d'apprentissage par renforcement pour des problèmes de décisions markoviens partiellement observés. Nous avons formalisé le cadre applicatif de notre algorithme, c'est-à-dire l'observabilité d'ordre fini du processus markovien, puis nous l'avons validé par des simulations. Ces simulations montrent en outre sa robustesse sur des problèmes sortant du cadre théorique de convergence. We have worked on learning world models, which can increase the adaptability of an autonomous system. We started with a cognitive approach and developed a new method for building and updating geometric models. Our algorithm is based on the fusion of two basic models of the environment. The world model thus obtained demonstrates the same level of quality, in term of precision and robustness, than models derived from classical modeling methods using Kalman filtering. Our algorithm seems more versatile - it can easily be extended to different basic models - which should bring more autonomy to a system. However, in order to improve the usefulness and adaptability of our algorithm we would have to use more complex and specific processes, which would eventually limit the system autonomy. We think that this limitation applies more generally to traditional mobile robotics. So we decided to try a behavior-based paradigm. We have proposed a new reinforcement learning algorithm for partially observed markov decision problems. We have defined the mathematical framework of our algorithm which can be applied to markov problems with a finite rank observable. We have validated our algorithm with simulations on various problems.These simulations show the robustness of our algorithm on problems lying outside its theoretical framework of convergence.

Les travaux décrits dans ce mémoire rapportent une trajectoire scientifique d’une dizaine d’années constamment guidée par le désir d’étudier et de développer des modèles de réseaux de neurones artificiels en prise directe avec le monde réel. La première partie de nos recherches s’est intéressée à l’apprentissage au sein de systèmes connexionnistes multi-réseaux. En droite ligne depuis le modèle de la Machine Séquentielle Connexionniste (MSC, développée durant la thèse de doctorat), qui met en jeu 2 réseaux multicouches, 6 MSCs sont mises en oeuvre qui permettent l’acquisition et le contrôle de la marche chez un robot hexapode. Le paradigme utilisé pour la distribution des informations nécessaires à chacun des modules connexionnistes est l’apprentissage par pénalité-récompense. Un robot hexapode a été construit qui valide les résulats préalablement obtenus en simulation. L’apprentissage par pénalité-récompense appartient à la classe des apprentissage par renforcement. La seconde partie de nos recherches s’est intéressée à étudier les interactions entre les réseaux de neurones artificiels et l’apprentissage par renforcement. Une implantation sur réseaux multicouches, puis sur cartes auto-organisatrices du Q-learning a été proposée. Nous obtenons ainsi des réductions de la taille mémoire requise et du nombre d’itérations d’apprentissage nécessaires qui autorisent une utilisation pratique. Nous avons ensuite développé des mécanismes de distribution de l’apprentissage par renforcement, soit au sein d’un seul robot doté de plusieurs comportements, soit au sein d’un groupe de robots dans une tâche impliquant la coopération. A la différence des courant de recherches actuels, qui pronent l’utilisation d’ a priori face à la combinatoire élevée de l’espace de recherche, nous proposons l’emploi d’ a posteriori , l’utilisation du “lazy learning” pour construire un modèle non explicite et le développement d’outils et méthodes d’aide à la conception des fonctions de renforcement. A moyen terme, l’objectif de nos recherches est d’automatiser la décomposition d’un comportement robotique complexe en une succession de comportements élémentaires. L’utilisation de marqueurs temporel et spatial est envisagée pour permettre le séquencement des cartes auto-organisatrices implantant les comportements élémentaires. Dans ce cas, la simple définition de l’objectif à atteindre suffirait alors à générer le comportement solution.

L’objet de cette thèse est l’étude des méthodes d'apprentissage par renforcement en vue de son application à la navigation d’un robot mobile autonome. Après une présentation des méthodes d’apprentissage développées depuis les débuts de la Cybernétique jusqu’à aujourd'hui en Intelligence Artificielle, nous présentons les fondements mathématiques de l'apprentissage par renforcement que sont la théorie des automates d’apprentissage et la Programmation Dynamique en temps réel. Les chapitres suivants sont consacrés au problème de la navigation d’un robot mobile autonome évoluant dans un environnement qui lui est inconnu. Pour répondre à ce problème, nous proposons d’utiliser différents algorithmes d’apprentissage par renforcement issus, soit des automates d'apprentissage, soit du Q-learning. Les performances de ces algorithmes sont ensuite comparées à partir d'expérimentations menées sur un système non-holonome. Enfin, le dernier chapitre propose une extension originale de ce type d’apprentissage dans le but de construire une carte représentant la topologie de l'environnement dans lequel le robot évolue. This thesis studies the application of reinforcement learning methods to the autonomous mobile robots navigation problem. After a presentation of the learning methods which have been developped from the begin- ning of cybernetics to the current state-of-the-art in artificial intelligence, we present the mathematical foundations of reinforcement learning, i.e. learning automata theory and real time dynamic programming. The following chapters are devoted to the problem of navigation for an autonomous mobile robot in an unknown environment. To solve this problem, several algorithms based on learning automata or on Q-learning are proposed. The performance of these algorithms are compared on the basis of simulation results for a robot with nonholonomic constraints. The last chapter presents an original extension of this kind of learning for the construction of a topological map of the robot’s environment.