Pathfinding et algorithmes génétiques

Par Franck Deroche et Frédéric Devilliers

Sommaire

Introduction

Un article de l'ECNiouzes de Juin semble vouloir remettre en cause la théorie de l'évolution de Darwin, arguant de la forte improbabilité de voir apparaître par hasard des fonctions évoluées chez les êtres vivants. Cependant, le calcul de probabilité utilisé est faussée, puisqu'il présume que l'ensemble des mutations doivent se produire simultanément, sur un unique individu.

L'informatique actuelle permettant, par le biais d'algorithmes génétiques, de simuler aisément, en les accelérant, les différents processus intervenant dans la théorie, nous avons décidé d'écrire un programme ludique dans lequel une population de chemins se reproduiraient, et où l'on pourrait observer le résultat du passage du temps sur les générations successives.

Contexte

Le pathfinding, ou dans la langue de Molière la recherche de chemins est un domaine en plein essor, utilisé par des industries très différentes. Entre autres, on trouve des applications très serieuses en robotique, où l'on cherche un chemin dans l'espace articulaire ( c'est-à-dire l'espace dans lequel les axes représentent les différents degrés de libertés du robot ) pour passer d'une configuration à l'autre, mais aussi une utilisation massive dans l'industrie du jeu video, où il est particulierement utilisé dans le déplacement des différentes unités dans les jeux de stratégie.

C'est un domaine où la recherche est encore active puisque si la résolution systématique est possible dans les cas où la dimension de l'espace de travail est faible ( 2 ou 3 ), elle devient nettement plus complexe lorsque l'on s'attaque à des espaces de dimension 6 ( cas de la majorité des robots industriels ).

Réferences