Passions d’un développeur indépendant

Un nouveau blog sur Wefrag le blog de DraK.

Articles taggés avec ‘Course’

Bonjour à tous,

Si vous n’avez pas vu le 1er article, vous risquez de ne pas tout saisir.

Aujourd’hui, nous allons voir une application des algorithmes génétiques qui permet d’obtenir une IA de voiture sur un circuit en 2D. Pour ce faire, nous allons intégrer un réseau de neurones à notre algorithme.

Introduction baclée très rapide aux réseaux de neurones

Neurone

Un neurone a plusieurs entrées (autant que voulu) et une seule sortie. Les valeurs des entrées passent dans une fonction mathématique et le résultat donne la valeur de sortie du neurone. Cette fonction est paramétrable pour chaque neurone.

Généralement, cette fonction est une somme des entrées E pondérée par des poids P et à laquelle on soustrait un seuil S. Le résultat étant borné entre 0 et 1 par une fonction F.

Ce qui nous donne en formule : pour n entrées : F(E1 * P1 + … + En * Pn - S)

Nous choisissons d’utiliser cette fonction, les paramètres de chaque neurone seront donc tous les poids P ainsi que le seuil S.

Fonctionnement d'un neurone

Réseau de neurones

La version la plus simple consiste à faire des couches de neurones, en sachant que chaque couche reçoit en entrée de ses neurones les sorties des neurones de la couche précédente.

De plus, les neurones de la 1ère couche vont recevoir en entrée les informations concernant notre problème. Les neurones de la dernière couche nous donneront le résultat en sortie.

Fonctionnement d'un réseau de neurones

Exemple #2 : Voiture de course 2D

Voiture et neurones

La voiture possède 4 capteurs de route positionnés sur les roues permettant au programme d’éliminer la voiture si 2 de ses roues sont en dehors du circuit. Elle possède également 8 capteurs lasers qui donnent la distance avant la sortie de chaussée. Pour contrôler la voiture, nous disposons de 2 commandes : le moteur et le volant.

Capteurs de la voiture

Du coup, nous allons utiliser une seule couche de 2 neurones, un neurone pour contrôler le moteur (accélérer, freiner, voire marche arrière) et un autre pour contrôler le volant.

Chacun de nos 2 neurones va recevoir 9 valeurs en entrée : la vitesse actuelle de la voiture, car il y a de l’inertie dans la commande du moteur (accélération), et les 8 capteurs lasers.

Et là, vous vous posez une question : où est passé l’algorithme génétique ?

Algorithme génétique

L’ADN de l’algorithme génétique va correspondre dans notre cas au paramétrage du réseau de neurones.

L’ADN de chaque voiture sera donc une liste de 20 nombres réels ((9 poids + 1 seuil) * 2 neurones).

Nous allons ensuite voir la fonction d’évaluation !

Ce sera un championnat composé de 4 circuits différents. Chaque circuit est complété en faisant un seul tour.

Si la voiture sort du circuit (2 roues dehors), nous lui donnerons un nombre de points équivalant au pourcentage du circuit complété (exemple : 50 points pour 50% du circuit). Si la voiture boucle le circuit, nous lui donnerons 200 points + un bonus en fonction du temps (exemple : 100 points pour 30 secondes, 300 points pour 10 secondes, etc…). Pour ne pas attendre indéfiniment, nous imposons un temps maximum pour chaque circuit. Toutes les voitures encore sur le circuit à la fin du temps imparti seront considérées comme sortant de la piste.

Pour évaluer les individus à chaque génération, les 4 circuits se succéderont, le score d’une voiture sera la somme de ses scores sur les 4 circuits.

Les principes de l’algorithme génétique sont toujours présents : l’évaluation, la sélection, la reproduction et la mutation seront utilisées.

Le résultat est une IA qui apprend à conduire la voiture grâce aux capteurs. L’IA est encouragée à boucler le circuit rapidement, mais la sortie de route reste très punitive (elle passe de 300/400 points à moins de 100…). L’IA n’apprend pas le circuit, elle n’a d’ailleurs aucune mémoire de suite de virage ou quoi que ce soit. Elle apprend simplement à négocier les virages. Ou plutôt, elle apprend à négocier les combinaisons de valeurs que ses capteurs lui donnent.

Une fois que l’on a obtenu une IA qui gère bien les 4 circuits, nous arrêtons l’algorithme et nous sauvegardons l’ADN de notre champion pour pouvoir l’utiliser plus tard.

Mais nous n’en avons pas fini avec elle, nous allons lui soumettre un test particulier… Notre IA va devoir compléter un 5ème circuit inconnu et du 1er coup ! Plus besoin d’algorithme génétique, plus d’évolution possible ! Il nous suffit de charger notre ADN dans le réseau de neurones et de poser la voiture sur le nouveau circuit.

Va-t-elle réussir le test ?

Résultat

Vidéo de l’apprentissage au fil des générations + Bonus test sur le 5ème circuit :

YouTube Preview Image

Et voilà ! Nous venons de prouver qu’il est possible de conduire une voiture avec seulement 2 neurones :D

Nous avons obtenu une IA qui est capable de finir des circuits simples avec des virages assez serrés, mais elle sera surement perdue si elle rencontre une situation jamais vue (croisement de route, virage encore plus serré, route plus étroite, grande étendue, etc…).

Il est donc possible de créer une IA pour son propre jeu relativement facilement. Il suffit de créer quelques capteurs d’environnement (position de l’ennemi le plus proche, distance avant le prochain mur en face, etc…). De plus, si vous codez l’algorithme génétique et le réseau de neurones de manière générique, vous pouvez l’utiliser facilement partout.

Bonne fin de semaine à vous :)