Algorithm Design for Microrobots with Energy Constraints – ANCOR

Dans ce projet, nous concevons des algorithmes sensibles à l’énergie pour des tâches distribuées exécutées par une équipe de robots. Étant donné que chaque robot a une limite individuelle d’énergie disponible, nous devons trouver des moyens d’équilibrer le travail entre les robots afin
que chaque robot puisse accomplir sa tâche sans perdre toute son énergie. En fonction du scénario particulier, du placement des robots et de leurs réserves de puissance individuelles, l’algorithme doit faire des choix conscients sur le mouvement des robots et l’ordre dans lequel les robots
doivent être déployés. Les techniques développées au cours de ce projet peuvent être appliquées à une variété de tâches qui nécessitent une collaboration entre plusieurs micro-robots mobiles à énergie limitée.
Nous développons également un algorithme éco-énergétique pour des équipes de robots hétérogènes ayant des taux de consommation d’énergie distincts. Pour cela, nous subdivisons la tâche de livraison collaborative en trois sous-tâches, la collaboration, la planification individuelle
et la coordination : Tout d’abord, si plusieurs robots travaillent pour livrer le même colis, ils doivent collaborer, c’est-à-dire que nous devons trouver tous les lieux intermédiaires de dépôt et de retrait du colis. Deuxièmement, si un de robots travaille sur plusieurs packages, nous devons planifier dans quel ordre il souhaite aborder son sous-ensemble de colis. Enfin, nous devons coordonner quel robot travaille sur quel sous-ensemble de colis (s’ils le font sans collaboration, les sous-ensembles forment une partition, sinon les sous-ensembles ne sont pas nécessairement disjoints par paires). Même si ces trois sous-tâches sont entrelacées, nous étudions séparément les problèmes de collaboration, planification et coordination avec le but d’obtenir les meilleures approximations pour chacun de ces sous-tâches, qui sont ensuite combinées pour obtenir la solution approximative finale.

1. Problème de livraison collaborative :
Le but est de livrer une ou plusieurs colis d’un noeud désigné source à un autre noeud désigné destination, par un équipe de robots avec les contraints d’énergie individuelles. Nous avons trouver les résultats un peu surprenant que le problème est plus facile à résoudre dans le cas quand chaque robot doit retourner à son base en comparison du cas quand ils peuvent se terminer loin de sa base. Nous avons trouver les algorithmes à augmentation de ressources où on augment l’énergie de chaque robot par un petit facteur pour pouvoir résoudre la problème en temp polynomial.

2. Problème de formation de robots :
Nous étudions la tâche de rassemblement de k robots mobiles à énergie contraints dans un graphe quelconque. Comme la rassemblement des
robots sur un seul point devient impossible dans ce cas, nous étudions trois variantes de rassemblement approximative : Le but est de déplacer les robots et avoir une configuration qui minimise soit : (1) le rayon d’une balle contenant tous les robots, (2) la distance maximale entre deux robots quelconques, ou bien (3) la distance moyenne entre les robots.

3. Problème d’exploration en ligne :
Nous considérons le problème de l’exploration d’un réseau inconnu (Online Exploration), par k robots mobiles, qui commence d’un seul noeud du graphe, où chaque robot a une contrainte sur sa consommation d’énergie qui limite le nombre d’arêtes qu’il peut traverser. Étant donné qu’un seul robot peut ne pas explorer complètement le graphique, les robots doivent collaborer afin que chaque noeud soit visité par au moins un de robots. Nous considérons trois critères d’optimisation différents : (1) la taille de l’équipe, (2) le limite d’énergie par robot, et enfin, (3) le nombre de noeuds visités. En supposant que le limite d’énergie par robot est B, nous fournissons des algorithmes en ligne pour l’exploration d’arbres, avec ou sans retour à la base, optimisant le nombre de robots utilisés.

Le projet ANR ANCOR est un projet de recherche fondamentale coordonné par le Laboratoire d’Informatique et Système (LIS), Aix-Marseille Université et CNRS, situé à Marseille. C’est un projet bilateral Franco-Suisse avec l’institute d’informatique fondamentale de ETH Zurich en Suisse comme partenaire. Le projet a commencé en 1er Juillet 2015 et a duré 36 mois.
Il a bénéficié d’une aide ANR de 84.032,00 euros pour un coût global de l’ordre de 593.792,00 euros, pour la partie français du projet. Le partie Suisse a été financé par le SNF du Suisse, selon l’accord mutuel pour les projets bilatéraux. L’équipe française du projet à Marseille, était
composée de trois chercheurs permanents, d’un postdoctorant et d’une doctorante financé par les fonds externes.

Publications multi-partenaires :
Nous avons publié plusieurs articles scientifique et donner les exposés aux conferences nationaux et internationaux pour diffuser les résultats du projet au monde scientifique. Pour le problématique de livraison collaborative (Collaborative Delivery Problem), nous avons travailler avec notre partenaire, nous avons publié deux articles, un à SIROCCO 2016 et l’autre à STACS 2017, les conferences internationales à haut niveau dans notre domaine de recherche. Ces deux articles résoudre le problème pour les équipe de robots mobiles homogène (chaque robots est limité par un borne sur l’énergie) ou hétérogène (les robots ont les taux de consumption différents). La version plus longe du premiere article était accepté pour publication dans le journal Theoretical Computer Science. Nous avons aussi écrit deux autres articles sur les problématique de «Near-Gathering« et «Fixed Path Delivery« respectivement. Ces articles vont apparaitre dans le prochaine edition de la conference SIROCCO en 2019. Les versions longes de ces articles avec plus des détails vont publiées dans le journal Theoretical Computer Science prévus pour 2020.

Publications mono-partenaire :
Avec le postdoc (non-permanents du projet) et une thésard, nous avons publié deux articles, un à ALGOSENSORS (conference internationale) et l’autre à ALGOTEL 2017 (le seule conference francophone sur notre domaine) en 2017. Le premier article a étudié le problème de livraison
dans le scénario où les robots peuvent partager leur énergie. Le deuxième est sur la problème de l’exploration maximale dans le cas quand le nombre de robots et leurs budgets énergétiques sont fixés à l’avance. Avec notre collaborateur externe, nous avons publié deux articles dans les conferences internationales (SIROCCO 2015 et ICALP 2018) et un article sur le journal scientifique Theory of Computing Systems qui present les résultats sur les versions différents du problème de l’exploration en ligne.