Guidage coopératif utilisant la règle des plus proches voisins

À l’origine, cette règle est une méthode de classification, c’est-à-dire qu’elle est utilisée pour répartir des objets dans des classes en fonction de leurs propriétés. Elle consiste à déterminer la classe des objets d’après celle, connue, des objets voisins. Les objets devant être classés peuvent être de tout type : des images, des courriers électroniques, des meubles, etc. La classification considérée peut être constituée de catégories (par exemple carré, rond, triangle, etc), de valeurs entières (par exemple nombre d’occurrences d’un mot), de valeurs réelles (par exemple poids). Afin de juger quels sont les objets voisins de l’objet à classifier, une distance entre ceux-ci doit être définie à partir de leurs caractéristiques connues. Cette distance peut être la distance euclidienne, de Mahalanobis ([Dev+96]) ou encore une distance définie spécifiquement pour l’occasion. Les objets voisins utilisés afin d’établir la classification de nouveaux objets sont tirés d’un ensemble pré-existant, leur classification doit être définie à la main ou par une autre méthode.

Appliquée au guidage de véhicules, la règle des plus proches voisins consiste à déterminer la commande de chaque véhicule en fonction de l’état (par exemple la position, la vitesse, l’orientation, etc) des véhicules voisins. Le critère déterminant si deux véhicules sont voisins est alors souvent fondé sur la distance euclidienne les séparant. Le premier auteur à considérer la règle des plus proches voisins afin de guider des véhicules semble être Reynolds dans [Rey87], [Rey99]. Son objectif est de simuler le comportement de déplacement en groupe d’animaux tels que certains oiseaux et poissons pour les besoins de l’animation par ordinateur. À cet effet, Reynolds propose que la commande des véhicules soit élaborée en suivant trois règles : séparation, alignement et cohésion. Ces règles servent respectivement à éviter les collisions, aligner les directions des véhicules entre eux et maintenir le groupe uni. Chaque règle prend en compte l’ensemble des véhicules de la flotte et produit une consigne d’accélération. Chaque véhicule doit donc arbitrer entre ces trois accélérations afin de déterminer sa commande. Par la suite, d’autres auteurs ont étudié le comportement, notamment la convergence des directions de groupes importants de véhicules soumis à la règle des plus proches voisins : [Vic+95] [TT98] [JLM02] [Mor05]. Dans ces études, la commande de direction des véhicules est obtenue en faisant la moyenne des directions des véhicules voisins tandis que le module de vitesse des véhicules est constant. Ainsi, parmi les règles de Reynolds, seule celle d’alignement est considérée. Dans [IT10], Inada obtient la commande de direction des véhicules en effectuant la moyenne des contributions des véhicules voisins. Ces contributions peuvent être l’éloignement, l’imitation ou le rapprochement du véhicule en fonction de la distance le séparant des autres véhicules. De cette manière, les trois règles de Reynolds sont utilisées, quoique de manière différente, et les véhicules se regroupent pour former une flotte en évitant les collisions.

Utilisation de la règle des plus proches voisins pour créer et maintenir une flotte de véhicules autonomes de manière coopérative

Rappelons que le principe de fonctionnement de la règle des plus proches voisins est que la commande courante de chaque véhicule est élaborée en fonction de l’état des véhicules voisins. Ce principe entraine que les actions de chaque véhicule influent sur les actions des autres. Ainsi, la règle des plus proches voisins conduit mécaniquement à la coopération des véhicules telle que nous l’avons définie en introduction. Il est ainsi aisé de comprendre l’intérêt de la règle des plus proches voisins dans le cadre du guidage coopératif d’un groupe de véhicules. De plus, comme la commande de chaque véhicule dépend uniquement de l’état de ses voisins, la règle des plus proches voisins est, naturellement, une commande distribuée.

Travaux ayant inspiré l’approche développée

La première approche : Travaux de Reynolds pour les films d’animation

Dans [Rey87] puis [Rey99], Reynolds propose un modèle d’interaction entre véhicules permettant de reproduire le mouvement en trois dimensions de groupes d’animaux tels que les oiseaux, les poissons, etc. Son objectif est que ces mouvements soient suffisamment réalistes pour sembler naturels au spectateur d’un film d’animation. Son étude emploie la technique des systèmes de particules. Dans le domaine de l’animation par ordinateur, cette technique est utilisée lorsqu’un phénomène est trop complexe pour être simulé en utilisant un seul objet. Le phénomène est alors divisé en un ensemble de particules, modélisant chacune une partie élémentaire du phénomène complet ([Ree83]). Dans les travaux de Reynolds, chaque véhicule est représenté par une particule en interaction avec les particules voisines. La commande en accélération appliquée à chaque particule dépend de ces interactions ainsi que d’une consigne globale permettant de contrôler la flotte de particules.

Modèle de véhicule
Le modèle de véhicule utilisé par Reynolds diffère du modèle puisque d’une part, les véhicules se déplacent dans les trois dimensions de l’espace simulé, et d’autre part, la commande des véhicules consiste en un vecteur accélération. Le modèle exact de véhicule n’est pas explicitement donné. Il est décrit de la façon suivante : le mouvement des véhicules consiste en des portions de lignes droites, intercalées de rotations afin d’aligner l’orientation du véhicule avec la direction de son déplacement. Ce modèle conserve la quantité de mouvement de chaque véhicule et inclut un frottement fluide afin que, même en conservant une commande en accélération constante, la vitesse des véhicules reste bornée. Enfin, par souci de réalisme, l’accélération est également bornée.

Stratégie de guidage
La loi de guidage développée par Reynolds se compose de plusieurs parties. Dans un premier temps, trois règles, définissant trois requêtes d’accélération, décrivent les interactions entre les véhicules. Chaque véhicule arbitre ensuite entre ces différentes requêtes afin de déterminer sa commande. Dans un second temps, la flotte peut être contrôlée en fournissant à tout ou partie des véhicules un point de passage à atteindre ou une direction à suivre. Enfin, les collisions avec les obstacles externes sont évitées en déviant les véhicules en danger vers une zone libre.

Règles décrivant les interactions entre véhicules
D’après Reynolds, le comportement naturel des animaux au sein d’un groupe se compose de deux volontés opposées et équilibrées : celle de rester proche des autres membres du groupe, ainsi que celle d’éviter les collisions. Reynolds exprime ces deux objectifs sous la forme de trois règles, listées ici par ordre de priorité décroissante.
1. Séparation : éviter les collisions avec les membres proches du groupe ;
2. Alignement : tenter d’égaler le vecteur vitesse des membres proches du groupe;
3. Cohésion : tenter de rester près des membres proches du groupe.

Analyse de l’approche de Reynolds
Introduite dans l’objectif de simuler le comportement des groupes d’animaux, la loi de guidage distribuée développée par Reynolds présente plusieurs intérêts. Premièrement, comme la prise en compte des véhicules voisins suffit au succès de la stratégie de commande, il est envisageable de l’utiliser sur des flottes de grande taille. En effet, chaque véhicule n’aura à prendre en compte que les véhicules de son voisinage et non toute la flotte, évitant ainsi que la quantité de calcul n’augmente de manière proportionnelle au nombre de véhicules. Deuxièmement, la coopération est assurée lors du calcul de la commande en prenant en compte les autres véhicules. Il n’est donc pas nécessaire de prévoir une procédure supplémentaire assurant cette tâche.

Cependant, la procédure de calcul de la commande présente un problème. Celui-ci réside dans la méthode d’arbitrage entre les différentes requêtes d’accélération. Tout d’abord, cette méthode nécessite de choisir le quota d’accélération avec soin: s’il est trop faible, les requêtes de priorité inférieure seront rarement satisfaites tandis que s’il est trop important, il y aura conflit entre les requêtes. De plus, même en choisissant ce quota soigneusement, il est difficile de différencier une requête d’évitement urgente, mais de faible amplitude, d’une requête d’attraction de forte amplitude.

Approche de Vicsek : étude de l’apparition spontanée de mouvement collectif

Dans [Vic+95], Vicsek étudie, en deux dimensions, la convergence des directions des véhicules soumis à un modèle d’interaction du type règle des plus proches voisins. Son objectif est d’étudier l’apparition spontanée de mouvement ordonné au sein de systèmes de type colonie de bactéries. Les véhicules employés se déplacent à vitesse constante dans un plan. La direction du vecteur vitesse de chaque véhicule est déterminée en calculant la moyenne des directions des véhicules voisins additionnée d’un bruit uniforme. Ce modèle peut être vu comme un cas particulier de celui que décrit Reynolds où seule la règle d’alignement est appliquée et où est ajouté du bruit. Vicsek s’intéresse, de manière empirique, aux conditions permettant à la direction des véhicules de converger vers une valeur commune. Il observe que la probabilité que les directions des véhicules convergent augmente lorsque la densité de véhicules dans le plan augmente et que l’amplitude du bruit diminue.

Étude des conditions de convergence
Vicsek étudie l’influence de la densité ρ de véhicules dans le plan, ainsi que de la plage de variation du bruit ηb sur la convergence ou non des directions de déplacement des véhicules vers une valeur commune. Cette étude est effectuée à partir de résultats de simulations mettant en scène un nombre de véhicules important N, évoluant au sein d’une cellule carrée de taille L. Vicsek met en place des conditions périodiques aux limites. Cela signifie que lorsque le déplacement d’un véhicule le fait sortir de la cellule, il y rentre par la frontière opposée en conservant le même mouvement. Ceci permet de simuler un milieu infini en utilisant un nombre fini de véhicules et une cellule de taille finie. Le rayon de voisinage d v voi est utilisé comme unité de longueur et la durée d’une itération comme unité de temps afin de définir la vitesse des véhicules. Les observations effectuées par Vicsek ne sont valables que pour une plage de vitesse spécifique au delà de laquelle le système ne représente plus le type de phénomène étudié (i.e. colonie de bactérie, volée d’oiseaux).

Analyse de l’approche de Vicsek
La présence de conditions périodiques aux limites dans les simulations a une grande importance dans les comportements observés. En effet, des véhicules qui auraient été perdus ont de nouvelles chances de rejoindre les autres après être réapparus de l’autre côté de la cellule. Ces conditions périodiques aux limites ne sont en revanche pas réalistes dans le cadre de la commande d’une flotte de véhicules. Contrairement aux travaux de Reynolds, l’évitement de collision, le regroupement et la transmission de consignes au groupe ne sont pas envisagés. Vicsek observe que lorsque la densité de véhicules est importante, la direction de ceux-ci converge vers une valeur commune. Cette étude reste empirique et la convergence, si elle est observée dans les simulations, n’est pas démontrée.

Approche de Jadbabaie : étude théorique de la convergence des directions des véhicules

Dans [JLM02], Jadbabaie effectue une étude théorique d’un modèle d’interaction proche de celui que décrit Vicsek mais en l’absence de bruit, ainsi que de plusieurs modèles d’interaction dérivés. Il fournit la preuve que les directions des véhicules soumis à ces modèles d’interaction convergent sous une condition. Cette condition, pouvant être résumée en « interagir suffisamment souvent », est en accord avec les observations de Vicsek concernant la forte densité de particules requise. En effet, une densité importante entraine naturellement davantage de véhicules dans la zone de voisinage et davantage d’interactions entre les véhicules.

Convergence des directions des véhicules

Grâce à la forme explicite de uθ (k), Jadbabaie démontre que la direction des véhicules converge vers une valeur commune si les véhicules interagissent « suffisamment souvent ». Cette démonstration utilise plusieurs propriétés de la matrice Fσ(k) , qui découlent de sa définition (1.13).

Propriétés de Fσ(k) Par construction, la matrice Fσ(k) possède les propriétés suivantes :
– Fσ(k) est une matrice stochastique (cf Annexe B).
– Tous les éléments de la diagonale de Fσ(k) sont strictement positifs.
– Lorsque σ (k) est connexe (cf. Annexe A), Fσ(k) est une matrice primitive, donc ergodique .

Table des matières

Introduction
1 Contexte
2 Notions utiles
2.1 Notion de véhicule autonome
2.2 Notion de coopération
3 Principales approches développées dans littérature
3.1 Coopération implicite ou explicite
3.2 Coopération permanente ou ponctuelle
3.3 Élaboration régulée ou réactive de la commande
3.4 Élaboration centralisée ou distribuée de la commande
3.5 Hiérarchisation des véhicules
3.6 Répartition des tâches
3.7 Bilan des approches existantes
4 Objectifs et contenu de la thèse
I Guidage coopératif utilisant la règle des plus proches voisins
1 Création et maintien d’une flotte par la règle des plus proches voisins
1.1 Description du problème
1.2 Travaux ayant inspiré l’approche développée
1.2.1 Travaux de Reynolds
1.2.2 Travaux de Vicsek
1.2.3 Approche de Jadbabaie
1.3 Moyenne de plusieurs angles
1.3.1 Limites de la moyenne vectorielle
1.3.2 Limites de la moyenne arithmétique
1.3.3 Exemples numériques
1.3.4 Choix d’un mode de calcul
1.4 Étude des limitations de la loi de guidage initiale
1.4.1 Les conditions périodiques aux limites
1.4.2 Convergence des directions des véhicules
1.4.3 Collisions entre véhicules
1.4.4 Comportement en présence d’un véhicule leader
1.4.5 Bilan sur la loi de guidage initiale
1.5 Loi de guidage coopératif proposée
1.5.1 Modèle des véhicules
1.5.2 Stratégie de guidage
1.5.3 Évitement de collision – Fonctions d’espacement
1.5.4 Cohésion du groupe de véhicules – Fonctions d’espacement
1.5.5 Notion de voisinage – Fonctions d’influence
1.5.6 Commande du module de vitesse des véhicules
1.5.7 Limitation de la vitesse angulaire des véhicules
1.5.8 Récapitulatif de la loi de guidage proposée
1.6 Conclusion
2 Utilisation d’agents virtuels pour transmettre des consignes à la flotte
2.1 Définition des agents virtuels
2.2 Les différents usages d’un agent virtuel
2.2.1 Désigner la cible des véhicules
2.2.2 Signaler une direction à prendre, une vitesse souhaitée
2.2.3 Signaler un obstacle
2.2.4 Signaler la direction à suivre pour éviter un obstacle
2.3 Combiner différents types d’agents virtuels
2.4 La gestion des agents virtuels
2.4.1 Gestion figée
2.4.2 Gestion centralisée
2.4.3 Gestion coopérative
2.4.4 Bilan
2.5 Conclusion
II Guidage coopératif utilisant la commande prédictive
3 Guidage coopératif prédictif 2D de véhicules de type avion
3.1 Description du problème
3.2 Le problème de commande prédictive
3.2.1 Rappels sur la commande prédictive
3.2.2 Commande prédictive distribuée de N véhicules
3.3 Travaux ayant inspiré la démarche proposée
3.3.1 Modèle
3.3.2 Stratégie de guidage
3.3.3 Forces et faiblesses de l’approche de Frew
3.3.4 Différences entre l’étude de Frew et l’approche proposée
3.4 Fonction objectif proposée
3.4.1 Composantes de la fonction objectif
3.4.2 Importance relative des différents termes de la fonction objectif
3.5 Recherche de la séquence de commandes optimale
3.5.1 Procédure de recherche de la séquence de commandes
3.5.2 Réduction de la charge de calcul
3.5.3 Composition du jeu de séquences de commandes candidates
3.6 Simulations numériques
3.6.1 Présentation de la mission des véhicules
3.6.2 Analyse d’une simulation de la mission
3.6.3 Analyse des performances de la loi de guidage
3.7 Conclusion
4 Extension pour l’exploration d’une zone
4.1 Description du problème
4.2 Modification de la fonction objectif
4.2.1 Prise en charge de deux points de passage par chaque véhicule
4.2.2 Modification du critère J
m,f inal
4.2.3 Utilisation de la vitesse prédite à la place de la vitesse nominale
4.3 Répartition des points de passage entre les véhicules
4.3.1 Aperçu général de la procédure de répartition proposée
4.3.2 Coûts d’attribution des points de passages
4.3.3 Examen des points de passage
4.3.4 Choix du point de passage pris en charge
4.3.5 Illustration du fonctionnement de la méthode de répartition
4.4 Simulations numériques
4.4.1 Exploration par 4 véhicules
4.4.2 Exploration par 1 véhicule
4.4.3 Exploration par 4 véhicules initialement séparés
4.5 Conclusion et perspectives
5 Guidage coopératif prédictif 3D de véhicules de type hélicoptère
5.1 Description du problème
5.2 Pilotage des hélicoptères quadrirotor
5.2.1 Décomposition partielle
5.2.2 Linéarisation par retour d’état
5.2.3 Utilisation du module de pilotage
5.3 Loi de guidage prédictive
5.3.1 Modèle de prédiction
5.3.2 Adaptation de la fonction objectif
5.3.3 Adaptations de la procédure de recherche
5.4 Simulations numériques
5.4.1 Présentation de la mission et des paramètres
5.4.2 Analyse d’une simulation de la mission
5.4.3 Évaluation des performances de la loi de guidage
5.5 Conclusion et perspectives
Conclusions

Lire le rapport complet