Les voitures autonomes peuvent-elles penser ?
La Navigation Autonome
Cet article fait suite aux articles :
- l’IA…Et le véhicule fut autonome
- La fusion de capteurs
- Les voitures autonomes et la localisationNous nous situons désormais à l’étape Path Planning dans laquelle notre voiture utilise sa connaissance de l’environnement et de sa position pour planifier des trajectoires.
Dans l’étape de Planning, nous devons prendre des décisions. Ce sujet est un des plus difficiles, il s’agit là d’implémenter le cerveau d’un véhicule autonome.
Cette image est un problème moral populaire où nous devons choisir qui sacrifier si nous n’avons plus de freins. Bien que peu probable, ce sujet permet de se demander comment une voiture autonome ferait si elle doit décider seule.
Prédictions
La première étape consiste à prédire ce que chacun de ces élément fera. Un piéton est susceptible de se déplacer tandis qu’un panneau restera immobile.
Nous pouvons utiliser deux approches :
- Pour chaque situation possible (insertion d’autoroute, intersection, …), modéliser toutes les trajectoires possibles pour un véhicule.
- Faire appel au Machine Learning pour, suivant les observations actuelles, établir une similarité avec les données d’entraînement et ainsi corréler cela à une trajectoire.
- L’approche par modélisation
Lorsque l’on modélise une trajectoire, nous devons imaginer tous les choix possibles pour la voiture que nous trackons. Prenons le cas où nous nous insérons sur une autoroute.
Le véhicule détecté peut faire plusieurs choses :
- Rester dans sa voie, ce qui signifie :
- Accélérer,
- Décélérer, pour nous laisser passer devant lui,
- Rester à vitesse constante, et donc nous ignorer - Changer de voie, ce qui faciliterait notre insertion.
Nous avons donc quatre situations possibles à définir pour une insertion d’autoroute. Nos capteurs fonctionnent en temps réel et il est donc possible de décider si un véhicule change de vitesse ou de voie simplement en calculant sa position et sa vitesse à chaque instant.
Dans notre cas, nous tenons à jour quatre scénarios possibles, et avons donc une distribution multimodale. Cela signifie que chaque scénario a une probabilité qui évolue suivant nos observations.
Cette technique à l’avantage d’implémenter la faisabilité d’une trajectoire, et donc d’éliminer les choix impossibles. Elle se concentre uniquement sur ce qu’il est possible de faire et non sur ce qui a déjà été fait.
2. L’approche par Machine Learning
Cette approche est très différente. Comme chaque algorithme de Machine Learning, nous définissons deux étapes, une phase d’entraînement et une phase de prédiction.
La phase d’entraînement regroupe des données massives sur l’historique des véhicules et apprend à partir de ces données. Nous pouvons avoir des centaines de véhicules ayant réalisé des centaines de comportements différents dans une intersection.
Nous réalisons de l’apprentissage non-supervisé. Des algorithmes de clustering nous aident à définir, pour l’observation actuelle, de quel groupe de trajectoire le véhicule se rapproche. Pour rappel, le clustering est une technique où nous définissons un nombre de clusters (de trajectoires) et où nous demandons à un algorithme d’indiquer quelles données se ressemblent.
Chaque cluster est en réalité une trajectoire type qu’un véhicule peut suivre. L’avantage de cette technique est de reposer sur des données et donc sur les scénarios passés. Plus nous roulons et récoltons de données, plus nous serons précis dans l’estimation des comportements.
Ces deux approches sont très différentes et reflètent en réalité la réalité de l’industrie des véhicules autonomes. Alors que certains s’appuient sur des cas déterministes par de la prédiction mathématique, d’autres s’appuie sur les statistiques en faisant appel à de l’intelligence artificielle. Ce choix des entreprises est plus largement étendu à bon nombre de problématiques comme la Perception au LiDAR contre la perception à la caméra ou autres.
Prise de Décision
Une fois que nous avons une estimation du futur de l’environnement, nous pouvons prendre une décision. Comment freiner si un piéton est détecté ? Comment accélérer ou changer de voie ?
La première chose à faire est de classifier l’environnement. Si nous sommes sur une autoroute, nos choix seront différents que dans un parking. Plusieurs critères entrent en compte lorsque l’on génère une trajectoire, notamment la sécurité, sa faisabilité, son efficacité et sa légalité. D’autres variables peuvent également entrer en compte comme le confort du passager.
Finite-State Machine
La première méthode de prise de décision que l’on peut utiliser est une machine à état fini. Le principe est de définir, suivant les situations, les états possible d’une voiture. Sur une autoroute, l’état d’une voiture peut être de rester dans une voie, de changer de file à gauche, ou de changer de file à droite. Suivant les conditions de circulation, nous changeons d’état pour, par exemple, dépasser un véhicule.
Le choix des états est généralement réalisé à l’aide de fonctions de coûts. Pour chaque scénario possible, nous calculons des coûts indépendants (distance aux obstacles, légalité, …), et les additionnons à la fin. Le scénario qui a le coût le plus faible l’emporte.
Ici, c’est à nous de définir ce qui à de l’importance. Nous ne pouvons réaliser une trajectoire non faisable ou dangereuse.
Coût_Total = Coût_Faisabilité * 5+ Coût_Sécurité*4 + Coût_Légalité * 3+ Coût_Confort*2 + Coût_Vitesse * 1
Dans la fonction de coûts associé à la vitesse, nous ne voulons pas que notre véhicule soit trop lent, ni qu’il dépasse la vitesse maximum autorisée. Nous définissons donc un coût décroissant suivant la vitesse puis maximum après la vitesse limite.
La prise de décisions est un sujet très délicat lorsque l’on parle de conduite autonome. Nous devons prendre en compte la situation actuelle et décider de tout ce qu’il est possible de faire à partir de ce point. Ensuite, nous devons peser le pour et le contre de chaque possibilité et finalement choisir la meilleure solution.
Génération de trajectoires
L’étape finale est la génération de trajectoires. Dans cette étape, il est nécessaire d’utiliser un repère différent du repère cartésien. Pour cause, le repère cartésien prend en compte la dimension (x;y) mais n’a pas de sens si l’on souhaite se repérer par rapport à la route. Le repère de Frenet contient deux axes, un axe s indiquant l’avancée par rapport à la voie et un axe d indiquant la distance au centre de la voie. Ce repère est celui sur lequel nous nous basons pour estimer si notre trajectoire dévie du centre de la voie ou si un véhicule est devant ou derrière nous.
Lorsque nous prenons la décision de dépasser un véhicule, l’algorithme génère plusieurs trajectoires pour une décision et choisit la meilleure selon les critères de faisabilité, sécurité, légalité, efficacité, confort, …
Dans ce cas de dépassement, les trajectoires rouges/oranges sont dangereuses, les jaunes sont acceptables mais incomplètes, la verte est la plus efficace et sure.
Pour générer cette trajectoire, nous créons un polynôme de niveau cinq qui passe par des points de chemins. Les points de chemin sont des point qu’on situe sur le trajet et qui contiennent 3 dimensions :
S : La distance longitudinale
D : La distance latérale
T : L’instant auquel on doit passer par ce point; donnant la vitesse
Une trajectoire est une courbe qui passe par tous ces points. Ces points sont positionnés dans l’espace et dans le temps. Ils nous indique quand passer à tel endroit et à quelle vitesse. Si l’on souhaite freiner à un passage piéton, nous créons des points jusqu’au passage piéton et fixons les vitesse des points en décroissance jusqu’à la zone d’arrêt.
Planificateurs
Nous venons d’étudier la génération de trajectoires à bas niveau. Qu’en est-il a plus haut niveau ? Comment décider de quelle rue prendre ?
Nous avons plusieurs familles d’algorithmes permettant de planifier un chemin d’un point de départ à un point d’arrivée. Dans ces algorithmes, nous considérons le monde comme étant une grille contenant des obstacles, un point de départ, et un point d’arrivée.
Parmi les différentes familles, nous nous concentrerons sur deux dans cet article.
- Les algorithmes Sampling-Based
- Les algorithmes d’apprentissage par renforcement
— Algorithmes Sampling-Based
Ils sont très populaires puisque très efficaces au niveau du temps de calcul. Nous avons deux types d’algorithmes : Discrets et Continus.
- Dans le planificateur discret, nous considérons le monde comme étant une grille. On peut citer les algorithmes de parcours en largeur, Dijkstra, A*… qui permettent de trouver le plus court chemin très rapidement et sans nécessairement explorer toute la carte.
Dans un algorithme de Dijkstra, nous explorons un grand nombre de possibilités et choisissons le chemin qui contient le moins d’étapes pour arriver à une destination.
A*
Dans l’algorithme très populaire A* (A-étoile), nous explorons seulement une partie de la carte en utilisant une fonction heuristique. A chaque point de la carte, nous indiquons la distance à l’objectif. Plutôt que d’explorer systématiquement tous les chemins, nous choisissons uniquement les chemins qui nous rapprochent de l’objectif.
A* est une variante de l’algorithme de Dijkstra qui cherche a trouver le meilleur chemin vers une destination spécifique en réalisant la quantité de travail minimale. Cet algorithme est donc très efficace dans une voiture autonome. Cette animation montre A* en action.
- Dans un planificateur continu, nous ne rendons pas le monde discret. Des algorithmes comme Hybrid A*, RRT (Rapidly-exploring Random Tree) permettent d’implémenter cela.
Hybrid A*
Hybrid A* cherche à se rapprocher de la réalité du monde continu en décomposant le mouvement. Au lieu de de rendre de case en case, nous essayons plusieurs déplacement courts et choisissons toujours celui qui nous rapproche de l’objectif. Cela signifie que l’algorithme est à la fois continu et discret. Les trajectoires générées peuvent également être plus fluides puisqu’elles prennent en compte la réalité du monde et donc des angles maximums, des équations de trajectoires, …
— Apprentissage par renforcement
Une approche de plus en plus populaire est l’apprentissage par renforcement. Cette technique de Machine Learning consiste à apprendre à partir de l’expérience. Si nous souhaitons tourner à droite, nous demandons à la voiture de faire un choix au hasard, s’il est bon, elle reçoit une récompense positive, si non, une négative. Au fil de l’entraînement, la voiture est capable d’apprendre ce qui a causé une récompense positive, et de le reproduire. Cette technologie est celle qui aujourd’hui se rapproche le plus de l’apprentissage humain.
Grâce à l’apprentissage par renforcement, nous avons appris à marcher, à courir, à battre le champion du monde de Go…
Il est possible d’intégrer cette technologie dans la robotique et notamment dans les véhicules autonomes. Le système de planification des véhicules autonomes de MobilEye fonctionne avec de l’apprentissage par renforcement. La récente démo de Wayve montre parfaitement l’utilisation de ce concept.
Résultats
Dans le cadre de mon Nanodegree sur les véhicules autonomes, j’ai réalisé un projet sur la conduite sur autoroute. Je devais développer un algorithme capable de conduire 7,5 km au milieu d’autres véhicules sur une autoroute. L’automate fini est capable de dépasser un véhicule lent ou de ralentir si le dépassement n’est pas possible.
Conclusion
La navigation autonome est un sujet passionnant. Nous conduisons avec notre intuition et nos yeux en respectant le code de la route. Pour reproduire cela dans un ordinateur, il faut passer par toutes les étapes que nous avons réalisé. Nous devons voir, nous positionner, prédire les comportements des autres véhicules, et enfin prendre une décision en intégrant des contraintes comme le code de la route ou encore le confort des passagers. Derrière chaque machine, un humain dicte les actions à réaliser suivant les situations. La machine ne fait que reproduire ce qu’on lui apprend. Ce sujet laisse place à un nombre très important de travaux de recherches et d’expérimentations. Il permet d’atteindre le niveau 5 d’autonomie et de démocratiser définitivement les véhicules sans chauffeur.
Jeremy Cohen.
Next : Les contrôleurs et l’intégration finale !
Références
Projet GitHub de Path Planning
- Implémentation C++ d’un système de navigation sur autoroute : highway-driving
