Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

0 TPE 2004 BLEIBEL François DORKEL Aymeric Les algorithmes de l’intelligence ar

0 TPE 2004 BLEIBEL François DORKEL Aymeric Les algorithmes de l’intelligence artificielle Quels algorithmes permettent à un robot de se déplacer de manière autonome dans son environnement ? 1 Introduction L’intelligence artificielle est une compétence spécifique aux robots ou aux automatismes (« artificielle ») qui détermine sa faculté à imiter un comportement humain. Cette intelligence essaye d’imiter le fonctionnement d’un cerveau humain dans beaucoup de domaines, par exemple la parole ou le caractère, deux aspects spécifiques aux humains, mais aussi notamment la capacité du cerveau à reconnaître les objets ou personnes qui l’entourent. Elle a des applications tout d’abord dans l’informatique pure : une des utilisations de l’intelligence artificielle sert à l’apprentissage d’une voix par un ordinateur pour la reconnaissance vocale; les jeux vidéo utilisent aussi beaucoup une intelligence simulée pour donner au joueur l’impression de jouer avec des humains, donnant la capacité aux personnages contrôlés artificiellement de se « comporter » comme un humain, en adoptant un caractère, un langage ou encore des actions qui sont à l’origine de l’attitude du joueur envers eux, et qui imiteraient un dialogue ou un combat le plus réaliste possible. On peut aussi l’utiliser pour contrôler des chaînes de production mécanisées (industrie lourde ou robotique) : des machines « intelligentes » sont ainsi capables de deviner le moment où un défaut ou une fausse manoeuvre va survenir bien avant des capteurs traditionnels, soit par un apprentissage préalable ou soit en utilisant des algorithmes « classiques » (méthode la moins utilisée), le résultat source de réduction du temps d’arrêt de la production, faisant ainsi économiser du temps et de l’argent à l’entreprise qui les utilise. Dans ce TPE, notre but est de découvrir et examiner les différentes solutions qui permettent à un robot quelconque de se déplacer dans son environnement (une maison ? une pelouse) pour aller chercher une balle rouge. Il devra pour ce faire éviter les obstacles qui se présenteraient à lui, et pourquoi pas, optimiser son trajet histoire d’économiser de l’énergie en se déplaçant jusqu’à la balle. Ce robot doit faire preuve de deux aptitudes « humaines » ou les imiter pour réaliser son objectif. La première consiste à donner à un robot (ou personnage, dans une approche virtuelle) la capacité de se mouvoir « intelligemment » dans un environnement. Ici l’intelligence mise en œuvre aura pour but de se mouvoir d’un point à un autre en évitant les obstacles. On pourrait penser que c’est une intelligence assez « simple » ou en d’autres termes, évidente : nos trajets de tous les jours nous semblent simples; contourner des obstacles, ou aller chercher une chaise derrière une table ne relève pas du défi pour nous les humains. Mais dans le cadre d’un robot, avec pour seule « intelligence » un microprocesseur et des capteurs, c’est beaucoup plus ardu : il se pose alors le problème d’une détermination optimale (c'est-à-dire la plus courte) du trajet, ceci en n’ayant pas forcément la vision spatiale et immédiate de l’environnement que nous avons (c'est-à-dire sans forcément connaître la position des obstacles à l’avance : nous examinerons les deux cas), et même alors, les « points de passage » (du trajet) doivent être calculés de manière précise en minimisant la distance parcourue, mettant en œuvre des algorithmes aussi complexes que variés, dont les utilisations sont décrites dans la partie II. 2 La seconde aptitude humaine que nous allons étudier consiste à reconnaître les objets, c'est-à-dire leurs formes et/ou leurs couleurs. Les yeux qui nous permettent de reconnaître une balle quand nous en voyons une (en nous basant sur notre expérience et les informations de nos sens) ont leurs équivalents robotiques. Ces capteurs CCD ou autres caméras numériques embarqués sur notre robot couplées à un système de commande (le cerveau électronique du robot) lui permettent de reconnaître les caractéristiques (la forme et la couleur d’une balle rouge, par exemple) des objets. Le robot peut alors identifier certains objets et prendre des décisions en temps réel basées sur sa reconnaissance de l’environnement. Ces deux aptitudes sont les plus utilisées dans les applications modernes de l’intelligence artificielle : la première (détermination du trajet) sert dans les logiciels de cartes routières ou les ordinateurs de bord, afin de conseiller l’utilisateur sur la meilleure route à prendre. La seconde peut servir dans la reconnaissance des personnes (un robot - chien qui reconnaîtrait son maître par exemple) ou pour guider le déplacement d’un robot vers un objet, comme dans notre cas. Nous allons donc étudier les algorithmes et autres méthodes nécessaires pour réaliser notre objectif. Le robot doit reconnaître la balle et en déterminer sa position, pour pouvoir ensuite se déplacer jusqu’à elle. Ce TPE est donc divisé en trois parties. La première, Reconnaissance d’images traite des algorithmes, capteurs, et tout ce qui est nécessaire pour que le robot puisse reconnaître notre balle et en déterminer sa position. La seconde partie, intitulée Détermination Intelligente de Trajet, parle des algorithmes utilisés pour que le robot trouve (et optimise) son chemin en se déplaçant jusqu’à la balle. Enfin, la dernière partie, Les réseaux neuronaux, explique les mécanismes de fonctionnement d’une des plus récentes et plus compliquées découvertes de l’intelligence artificielle. 3 Sommaire I. Reconnaissance et localisation d’objets à partir d’images numérisées A. Codage et stockage de l’image 1) Acquisition et codage 2) Stockage : la matrice 3) Modifications de base B. Elimination du bruit 1) Principe de convolution 2) Filtres linéaires 3) Filtres non-linéaires C. Sélection D. Détermination de contours 1) Par convolution 2) Autres méthodes E. Reconnaissance de forme F. Localisation de la balle II. Détermination Intelligente de Trajet Introduction 1. La ligne droite 2. Depth First Search (DFS) 3. Breadth First Search (BFS) 4. Dijkstra 5. A* (A star) Comparatif et conclusion III. Les réseaux neuronaux 1. La théorie 2. Application à la reconnaissance d’images 3. Application à la Détermination Intelligente de Trajet 4 Reconnaissance et localisation d’objets à partir d’images numérisées Les systèmes robotisés utilisant des informations visuelles provenant de capteurs optiques, du type de ceux utilisés dans des caméras ou appareils photo, sont nombreux (ex : systèmes de contrôle industriel, robots d’exploration spatiale, …). Mais comment sont-ils capables d’interpréter ce qu’ils « voient » pour interagir avec leur environnement ? A partir d’un exemple, nous allons essayer d’illustrer différentes méthodes permettant à un robot de repérer un objet pour aller le ramasser, nous utiliserons pour cela une balle rouge. Mise en situation Nous disposons d’une image, provenant du capteur d’un robot (voir ci- dessous). Nous allons repérer la balle rouge qu’il devra ramasser, après en avoir déterminé la position. Pour simplifier le problème, nous définissons qu’un seul objet sphérique rouge (la balle) sera visible par le robot, et qu’il ne sera pas masqué à plus de 25% par un obstacle. Image provenant du capteur du robot 5 Processus permettant d’aboutir à une solution Localisation Comment trouver la position de la balle grâce au traitement de l'image Reconnaissance des formes Comment trouver la balle parmi tous les objets Distinction des contours Comment délimiter les différents objets visibles sur l'image Sélection des couleurs Comment simplifier l'image pour accélérer les calculs Suppression du bruit: Comment gommer les imperfections de l'image Codage et stockage de l'image: Comment coder et stocker l'image acquise 6 A. Codage et stockage de l’image 1) Acquisition et codage Dans la majorité des cas, le système réceptionne les données provenant d’un capteur CCD (Charge Coupled Device ou Dispositif à Transfert de Charges en français). Ce type de cellule photo-sensible est utilisé dans la plupart des appareils photos et caméras numériques. Il délivre les données de l’image sous la forme d’un tableau de pixels. Pour chaque pixel, les informations de luminosité et de couleur sont codées puis stockées dans une entité de taille définie. Dans la majorité des cas, on utilise des codes couleurs dits « 24 bits ». Une couleur est stockée sur 24 bits, soit 3 octets, comme le montre le schéma ci-dessous. On stocke l’intensité de chacune des composantes primaires (rouge, vert et bleu) sur un octet, soit 256 niveau de luminosité différents. Cela permet d’obtenir 2563, soit 16 777 216 nuances de couleurs distinctes. La dimension de la structure de stockage dépend de plusieurs facteurs. Elle est proportionnelle à la qualité du capteur et à la qualité requise. Une image en noir et blanc utilise des couleurs stocké sur 1 bit (2 états, noir et blanc), une image en niveaux de gris utilise des couleurs stockées sur 16 bits. Les images couleurs utilisent généralement des structures de stockages de 16, 24 ou 32 bits. Dans ce TPE, nous utiliserons des couleurs 24 bits, car elles sont très pratiques (1 octet, soit 256 états, par couleur primaire). 2) Stockage : la matrice En mathématique, une matrice est un tableau de valeurs. Nous allons donc considérer qu’une image peut être définie par trois matrices, une pour chaque couleur primaire (rouge, vert, bleu). Les valeurs initiales de celles-ci seront des entiers, compris entre 0 et 255. Pour obtenir la couleur d’un pixel d’abscisse x et d’ordonné y d’une matrice M, nous uploads/Philosophie/ ia-algo.pdf