Problématique

La coordination locale entre agents ou robots permet de gérer, en temps réel, l’évitement de collision et plus généralement le déploiement dans un environnement contraint. Au sein d’une flotte de robots, la coordination locale permet de distribuer le contrôle et la prise de décision, en bénéficiant d’un fort degré de robustesse (due à la décentralisation) et d’adaptation (reconfiguration locale rapide de la flotte). En contrepartie, ces comportements locaux peuvent entraîner des décisions contradictoires, pouvant mener à une distorsion de la flotte, entraînant par exemple la déconnexion de la flotte en sous-groupes. De nombreuses applications nécessitent que la communication soit possible en continue au travers de la flotte (pour des partages d’informations, de diffusion de contraintes, d’ordres du monitoring au sol, etc.). Cela revient à garantir la connectivité du réseau d’agents. Cette connectivité permanente a néanmoins un fort impact sur la liberté de déplacement des agents [6]. Le problème se complexifie dès lors que l’environnement contient des obstacles, contraignant plus fortement les déplacements et les liens de communication.

L’objectif de la thèse est d’étudier des modèles de coordination spatiale décentralisés, assurant le déploiement d’une flotte d’agents avec maintien de la connectivité, en environnements contraints 2D et 3D (type urbains).

 

Approche et travaux de la thèse

Cette thèse s’inscrit dans le domaine de l’IA distribuée, et plus particulièrement des techniques de l’intelligence en essaim, formalisées dans le cadre des systèmes multi-agents décentralisés (eg. [2]). Elle s’appuie aussi sur les techniques d’optimisation sous contraintes distribuées (type DCOP1), et sur les protocoles de communication sans fil.

L’approche envisagée, pour répondre au problème de coordination sous contrainte de connectivité, est de combiner la coordination à base de forces (flocking) avec la propagation de contraintes sur la qualité des liens de communication mesurée en temps réel. Le modèle du « Flocking », introduit par Reynolds [1], a inspiré plusieurs contrôleurs décentralisés pour la navigation en formation ou en essaim, eg. [2, 5]. Ce modèle repose sur trois forces locales : force de cohésion (regroupement), force de séparation (évitement de collisions), et force d’alignement (direction commune). Ces modèles sont très efficaces en environnements ouverts (c-à-d. sans obstacles) [2,3,5], mais ils peuvent se dégrader très vite en environnements présentant des obstacles. Il est donc nécessaire de prendre en compte 1) la topologie de l’environnement (perçue par les agents) et 2) la qualité des liens de communication, incluant les pertes.

Il a été montré que la propagation des ondes radio est instable dans le temps, et non homogène dans l’espace [9], ce qui ne permet pas de construire des solutions sûres et efficaces a priori. Ainsi on visera à définir un modèle de coordination intégrant les contraintes de liaison, de façon dynamique, selon les mesures de la qualité des liens de communication réalisées en continue. Il s’agira aussi d’explorer l’idée de générer des forces (virtuelles) lors de la perte de liaisons pour garantir une reconnexion rapide.

Deux propriétés seront étudiées et optimisées :

  • Déploiement maximal en distance sans perte de liaisons

  • Déploiement avec réparation lors d’une perte de liaison.

La validité et l’efficacité des modèles construits durant la thèse sera évaluée en simulation, en environnements encombrés 2D, puis 3D. Il s’agira d’optimiser les paramètres de combinaison des forces, et d’évaluer la robustesse aux pertes de connectivité (simulation de bruits, de pertes). Nous exploiterons le simulateur multi-drones développé dans CHROMA et DANTE, reposant sur les outils GAZEBO (simulation 2D/3D de robots et drones) et NS3 (simulateur de référence pour les communications sans fil), cf. https://team.inria.fr/chroma/en/software/ .

Deux scénarios seront particulièrement étudiés en environnement inconnu et contraint : 1) le déploiement maximal en distance (ou couverture) d’une flotte de n agents depuis une source fixe, 2) la couverture maximale par une flotte de n agents se déplaçant d’une source vers une destination connue. Par couverture, on entend ici la surface (2D) ou l’enveloppe (3D) totale vue lors de la mission (problème de l’exploration multi-robot [7,8]).

Une fois montré l’efficacité des modèles en simulation, nous viserons à démontrer leur validité expérimentale avec des drones réels. Pour cela nous implémenterons le modèle de coordination sur la plate-forme de drones quadri-rotors de l’équipe CHROMA (drones IntelAero). Les expérimentations seront menées sur le campus de la Doua à Lyon, avec le support d’un ingénieur.

1 Problème d’Optimisation sous Contraintes Distribuées

 

Références

[1] C. Reynolds, "Flocks, herds and schools: A distributed behavioral model.". ACM SIGGRAPH Computer Graphics. 21. pp. 25–34, 1987.

[2] R. Olfati-Saber, “Flocking for Multi-Agent Dynamic Systems: Algorithms and Theory”, IEEE Transactions on Automatic Control, Vol. 51, NO 3, March 2006.

[3] L. Reynaud and I. Guérin Lassous, Design of a force-based controlled mobility on aerial vehicles for pest management”, Mobile Networks and Applications (Springer), January 2017.

[4] R. Grünblatt, I. Guérin-Lassous, O. Simonin, Study of the Intel WiFi Rate Adaptation Algorithm, CoRes-AlgoTel, 2019, under submission.

[5] H. G. Tanner, A. Jadbabaie, G. J. Pappas, Flocking in Fixed and Switching Networks, IEEE Transactions on Automatic Control, Vol 52, No 5, pp 863-868, May 2007.

[6] M. Zavlanos, M. Egerstedt, G. Pappas, Graph Theoretic Connectivity Control of Mobile Robot Networks, Proceedings of the IEEE, March 2011.

[7] A. Renzaglia, J. Dibangoye, V. Le Doze, O. Simonin, “Combining Stochastic Optimization and Frontiers for Aerial Multi-Robot Exploration of 3D Terrains”, 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems, to appear in Proc. IROS 2019.

[8] A. Renzaglia, J. Dibangoye, V. Le Doze, O. Simonin, “Multi-UAV Visual Coverage of Partially Known 3D Surfaces: Voronoi-based Initialization to Improve Local Optimizers”. CoRR abs/1901.10272 (2019), submit to IEEE SMC 2019.

[9] J.-L. Lu, F. Valois, Performance evaluation of 802.11 WLAN in a real indoor environment, IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, pp. 140-147, 2006.

 

 

 


Mots-clés
décision distribuée; Drones; multi-robots; simulation multi-agents
Établissement
CITI - CENTRE D'INNOVATION EN TELECOMMUNICATIONS ET INTEGRATION DE SERVICES
69621 VILLEURBANNE  
Équipe de recherche
CHROMA : Cooperative and Human-aware Robot Navigation in Dynamic Environments
Directeur
Olivier SIMONIN, Prof, INSA Lyon, Labo. CITI, équipe Inria CHROMA
Co-encadrants
Isabelle Guerin-Lassous, Prof, Univ. Lyon 1, Labo LIP, équipe Inria DANTE
Site Web
https://team.inria.fr/chroma/en/
Date de début souhaitée
01/10/2019
Langues obligatoires
Français
Prérequis

Le/la candidat/e disposera d’un niveau Master 2 ou équivalent, en informatique, IA ou robotique. Une expérience en modélisation/simulation de systèmes distribués ou en expérimentation robotique/réseaux sera un plus.

Informations de contact

Contacter par courrier électronique Olivier Simonin (olivier.simonin@insa-lyon.fr) ou Isabelle Guerin-Lassous (isabelle.guerin-lassous@ens-lyon.fr)