Modèles et algorithmes pour systèmes multi-robots hétérogènes

Modèles et algorithmes pour systèmes multi-robots
hétérogènes

Intégration des modèles 

Nous détaillons ici l’intégration des modèles utilisés par nos algorithmes de planification de patrouille, pour laquelle nous avons mis en œuvre nos idées développées au chapitre 5. À l’heure actuelle, nos algorithmes de planification de patrouille n’utilisent pas directement la librairie Gladys mais sont construits autour d’un équivalent écrit en Python et exploitant les mêmes données de base, et en particulier les cartes au format GeoTIFF exploitant GDAL et les modèles des robots et de mission au format json – voir aussi l’annexe A à ce sujet. Cela nous a permis un premier prototypage rapide dont nous montrons les résultats ici et qui est tout à fait compatible avec l’exploitation future de la librairie Gladys. En particulier, on exploite les données d’entrée suivantes : — descriptif de la mission (json) ; — descriptif de chaque robot impliqué dans la mission (json) ; — cartes d’accessibilité, une par robot (GeoTIFF) ; — cartes de visibilité, une par robot (GeoTIFF) ; — carte d’utilité, une pour la mission (GeoTIFF), décrivant l’utilité initiale de chaque position objectif et son importance, et représentant son évolution au cours du temps, entre deux instances. Le descriptif de la mission précise notamment les fichiers utilisés (dont les cartes), les positions de départ des protagonistes et les paramètres de la mission – ici la durée T d’un cycle). Chaque robot utilise un modèle de déplacement basé sur sa carte d’accessibilité, sa taille et sa vitesse nominale, un modèle de visibilité basé sur sa carte de visibilité, la hauteur de son capteur, le type de capteur, sa portée et sa qualité – les paramètres sont utilisés pour définir la fonction de perception décrite plus loin – et un modèle de communication fonction de la distance. Ces modèles sont facilement extensibles. Actuellement, nous considérons des robots ayant un angle de vue à 360° et nous ne prenons pas en compte leur orientation. Cela peut s’avérer problématique dans certains cas – voir à ce sujet le chapitre 9 – mais reste suffisant pour nos algorithmes de patrouille et les résultats présentés ici. Ce n’est pas une perte de généralité, mais il est important de considérer que la prise en comte de l’orientation du robot impacte fortement l’étape d’échantillonnage et la complexité du problème instancié. Par ailleurs, P r et Q sont basés sur des ensembles de positions 2D, disposées selon une grille cartésienne – des rasters GDAL au format GeoTIFF. Ces grilles sont géoréférencées, et différent d’un robot à l’autre – par la taille du robot et par ses capacités d’accès – comme illustré à la figure  32. À partir du tableau 1, explicitons les fonctions de base utilisées ici : percept ion φ r pq =    1 si dist(p, q) = 0 0 si dist(p, q) > sensor range min .

 Solveur IP

 Nous avons utilisé le solveur IP GLPK. Nous détaillons ce choix et le fonctionnement de ce solveur dans l’annexe B. Plus spécifiquement, la section 7.2 utilise directement les binaires de la librairie (lp_solve) tandis À propos de que les autres résultats expérimentaux ont été obtenus à travers la librairie PyMathProg, voir http:// pymprog.sf.net/ PyMathProg∗ fournissant une API Python à GLPK à travers PyGLPK. Cette API a été retenue pour sa simplicité et sa lisibilité. En outre, il est très important de noter que GLPK est un solveur déterministe. Cela permet de garantir la reproductibilité des résultats pour une instance donnée Il est courant de – l’échantillonnage restant lui stochastique. laisser tourner un solveur IP pendant plusieurs heures pour évaluer ses capacités et obtenir le meilleur résultat possible ; nous trouvons ces temps de calculs trop longs pour notre application qui vise la replanification en cours de mission, c’est pourquoi nous nous limitons à quelques minutes de calculs seulement. Dans le présent chapitre, tous les résultats sont issus d’une résolution centralisée : le solveur utilise l’ensemble des données disponibles pour élaborer en même temps les plans de chaque robot, ce qui permet une coordination optimale entre les robots, au contraire du chapitre 8 qui étudie une approche séquentielle et décentralisée du problème. Le solveur GLPK, de par son fonctionnement, est capable d’évaluer sa résolution du problème IP qui lui est donné. En particulier, il est capable d’indiquer si des solutions existent ou non, et lorsqu’il en a renvoyé une il indique si elle est optimale ou non. Si la solution est sous-optimale, il peut fournir des bornes sur son optimalité, bien que celles-ci se révèlent assez larges en pratique. En outre, il est possible de fixer une limite de temps au bout de laquelle le solveur s’arrête et renvoie la meilleure solution trouvée jusque-là, généralement sous-optimale. Nous faisons un usage systématique de cette fonction, avec une limitation du temps de calcul à cinq minutes, ce qui pour nous correspond à un « maximum acceptable∗ » en cours de mission pour planifier le prochain chemin.  Il n’est pas facile d’évaluer a priori quelles sont les capacités du solveur face à un nouveau problème IP car ses performances dépendent du nombre de variables et de contraintes mais aussi de sa capacité à exploiter les liens entre elles, c’est-à-dire en quelque sorte de la « topologie » du problème. Or, si nos problèmes TOP et SP sont proches du classique TSP, ils sont différents dans leur complexité – plus grande – et dans les variables – il y a des variables et des relations supplémentaires. Afin d’évaluer grossièrement les capacités de notre solveur, nous avons dans un premier temps lancé de nombreuses instances afin de définir quels étaient les jeux de paramètres acceptables pour le solveur. Ceci est présenté dans la section 7.2 ; les sections suivantes évaluent alors plus en détails les performances de notre approche dans ces bornes.