Projets_Etudiants

h1. Véhicule autonome

+Objectif+

Le but de notre projet est de trouver les paramètres optimaux permettant à une voiture automatisée de faire le tour d’un circuit le plus rapidement possible.

+Déroulement du travail+

Notre projet de première année d’élève ingénieur de l’ISIMA s’est déroulé dans les locaux de Polytech Clermont-Ferrand sous la tutelle de M. Jacques Laffont, professeur à Polytech. 

Un code source écrit en langage C, sous un environnement Codeblocks a été mis à notre disposition. Ce code permet de lancer une voiture en fonction de différents paramètres (que l’utilisateur doit régler) sur un circuit.

Nous avons dû créer un programme en langage C, à partir de ce qui nous a été remis, permettant de trouver les paramètres optimaux recherchés.

+Présentation de la démarche mise en œuvre pour résoudre le problème+

Notre première approche fut d’abord de faire tourner le programme afin de mieux comprendre le problème et s’approprier le code qui nous a été donné. 

Nous avons ensuite adapté ce code et ainsi créé un programme qui lance plusieurs fois la voiture en changeant les paramètres. Nous pouvions ainsi déterminer les paramètres recherchés en lançant le logiciel. Il aurait alors fallu faire tourner le programme pendant plusieurs jours (chaque tour prenant environ une minute, avec 4 paramètres à changer chacun d’eux pouvant prendre plusieurs dizaines de valeurs différentes).

L’étape suivante fut d’écrire les résultats et les paramètres de chaque tour fait par la voiture dans un fichier. On a ainsi pu acquérir une base de données qui nous a été utile pour la suite. En effet, lorsqu’on lance un véhicule, on peut savoir si ces paramètres n’ont pas déjà été testés (ce qui évite le cas échéant de devoir recommencer le test). On gagne ainsi du temps et on peut relancer le programme à différent moments sans perdre les résultats obtenus précédemment.

La dernière étape de notre travail fut d’appliquer un algorithme s’inspirant de celui du recuit simulé pour déterminer les paramètres optimaux recherchés. 

Ce rapport détaille tout le travail qui a été effectué et reprend donc toutes les étapes qui ont été expliquées précédemment. 

+Prise en main et premiers essais+

La première difficulté fut de trouver un ordinateur sur lequel nous pouvions travailler.

Ceux de l’ISIMA et ceux du binôme ne convenaient pas pour diverses raisons. L’accès aux ordinateurs de Polytech, permis par notre tuteur de projet M. Laffont et l’acquisition d’un nouvel ordinateur par l’un des membres du binôme nous a permis de commencer le travail dans de bonnes conditions.

Nous avons fait tourner le programme en modifiant les quatre paramètres à modifier dans le but d’optimiser le temps de parcours du véhicule : 

-	la vitesse

-	la distance au mur

-	le coefficient de correction de l’angle

-	l’angle

Nous avons alors lancé quelques véhicules sur le simulateur avec des paramètres différents pour voir quelle influence à chaque paramètre sur la voiture. Nous en avons ainsi déduit les limites de chaque paramètre. Par exemple si on lance une voiture avec une distance au mur inférieur à 5 m ou supérieure à 9 m, assez rapidement la voiture rencontrera un mur et sera bloquée dans son avancée sur le parcours.

Nous avons ensuite fait une dichotomie sur le coefficient de correction de l’angle avec tous les autres paramètres fixes. Nous avons alors obtenu le tableau de résultats suivant :

Correction de l’angle	Temps

15	

30	

45                      103,39

47,5	

50	                103,38

60	

75	

Lorsque nous avons trouvé le coefficient de correction de l’angle qui nous donnait la vitesse la plus faible, nous avons ensuite fait une dichotomie sur la distance au mur :

Distance au mur	Temps

5	 

5,5	        103,38

6	 

7,5	 

8,75	        101,03

8,875	         99,05

9	        101,46

Nous avons alors refait une dichotomie sur la correction de l’angle pour nous assurer que la valeur obtenue précédemment (50) était bien celle qui nous donnait la vitesse la plus faible. Nous avons alors obtenu le même résultat de 50 pour le coefficient de correction de l’angle.

Pour ces paramètres de distance au mur (8,875 m) et de coefficient de correction d’angle (50) obtenus grâce à la dichotomie, nous avons alors augmenté la vitesse jusqu’à la vitesse maximum pour laquelle la voiture ne va pas directement dans le mur ou ne se retourne pas dès le départ:

Vitesse	Temps

25	79,25

30	66,06

35	56,64

40	49,6

45	44,11

50	39,77

55	36,22

60	33,21

62,5	32,22

64	31,27

64,5	31,22

65	Ne démarre pas bien

+Constitution d'une base de donnée et interet+

Le but était de créer une base de données contenant tous les essais effectués par la voiture. Ces données servent de base à l’algorithme de recuit simulé que nous avons mis en œuvre plus tard.

Afin de pouvoir exploiter nos résultats, il fallait donc les mémoriser dans un fichier texte. Nous avons alors créé une fonction écriture qui permet de sauvegarder les tests faits par le simulateur.

Comme il est inutile que le simulateur fasse tourner deux fois une voiture avec les mêmes paramètres, nous avons écrit la fonction recherche qui cherche dans le fichier « résultats.txt » si une voiture a déjà été lancée avec des paramètres identiques. Cela permet d’éviter de lancer plusieurs fois une voiture avec les mêmes paramètres.

Afin d’acquérir une base de donnée la plus importante possible, nous avons laissé

tourner notre programme durant tout un week-end sur six ordinateurs, ce qui nous a permis de constater qu’au-delà d’un certain temps, le simulateur ne chronomètre plus la vitesse de parcours du véhicule.

Nous avons ensuite écrit une nouvelle fonction de recherche dans un fichier ce qui nous a permis de savoir dans chaque fichier résultat.txt quelle est la plus faible vitesse de parcours et pour quels paramètres elle a été obtenue.

Vitesse (km/h)	Temps (s)

5	         323,04

10	         161,56

15	         107,73

20	          80,82

30	          53,93

40	          40,48

50	          40,46

+Le recuit simulé+

L’objectif était de rechercher un maximum en appliquant un algorithme de recuit simulé à la voiture. Pour cela, nous avons dû faire des recherches sur cet algorithme afin de le comprendre, puis nous avons cherché à le coder d’abord sur une fonction basique à une dimension. Nous l’avons ensuite appliqué à la voiture. Enfin nous l’avons fait tourner.

Principe :

Le recuit simulé est un algorithme basé sur une heuristique permettant la recherche de solutions à un problème donné. Il permet notamment d'éviter les minima locaux mais nécessite un réglage minutieux des paramètres.

Pour appliquer cet algorithme, on doit avoir des paramètres correspondant à cette fonction. On combine ensuite ces paramètres entre eux, nous obtenons ainsi un nouveau paramètre que l’on applique à la fonction que l’on cherche à minimiser. Ensuite en fonction du résultat, on garde ou non ce paramètre.

Application à une fonction à une dimension : 

Le test de l’algorithme correspondant à la fonction x^4+12x^2+3x retourne la bonne valeur : 0,1866

Application à la voiture : 

L’algorithme précédent a été modifié pour pouvoir être appliqué à la voiture. 

Explication du programme contenant les modifications : 

-	Le programme prend 64 valeurs au hasard dans le fichier servant de base de données et les met dans un autre fichier intermédiaire nommé « recuit.txt » sur lequel 

        on appliquera l’algorithme

-	L’algorithme prend 2 lignes de ce fichier et combine les paramètres entre eux pour en fabriquer un autre

-	Si ces paramètres ont déjà été testés, le programme récupère juste la valeur du temps et réécrit ou non et à la bonne place dans le fichier « recuit.txt » en

        fonction de cette valeur.

-	Si ces paramètres n’ont pas été testés, le programme lance la voiture avec ces paramètres, ajoute le résultat trouvé au fichier résultats.txt contenant tous les

        résultats obtenus depuis le début et comme précédemment traite ce nouveau résultat selon l’algorithme

Le programme est fonctionnel, mais il faudrait malgré tout le faire tourner plusieurs

heures sans discontinuité avant d’obtenir un résultats, chose que nous n’avons pas eu le temps de faire.

+Conclusion+

Ce projet qui était notre premier choix ne correspondait pas à ce que nous pensions. Néanmoins, malgré quelques difficultés techniques nous ayant empêché de démarrer rapidement le projet, nous avons passé de nombreuses heures dessus afin de franchir une à une toutes les étapes nécessaires pour résoudre le problème. Il nous aura manqué un peu de temps afin de pouvoir réellement arriver à une solution optimale.

De plus l’algorithme utilisé, qui n’est qu’un algorithme modifié du recuit simulé peut rester bloquer dans un minimum local, ce qui est un obstacle dans la recherche de paramètre optimaux. La prochaine étape consisterait à régler ce problème.

En conséquence malgré un engagement important de notre part, et suite à quelques difficultés techniques, il nous aura manqué un peu de temps pour arriver à bout de ce projet.