Considérations générales sur la planification multirobot

TAXONOMIE

Quot homines, tot sententiae. (Autant d’hommes, autant d’opinions.) — Térence

La détection, la localisation et le suivi de cibles sont au cœur de nombreuses applications en robotique, tant dans des contextes antagonistes que coopératifs. Ces problèmes ont fait l’objet de nombreux travaux dans différentes communautés de recherche, principalement sous les termes de problèmes de « poursuite-évasion». Sous ce terme évocateur se cachent en fait une grande variété de scénarios : mono- ou multirobot, considérant une ou plusieurs cibles, dans le but de les détecter, de les capturer ou simplement de les suivre.

Par ailleurs, on trouve dans la littérature de nombreux problèmes similaires sous des noms différents, comme la surveillance, la fouille (search) ou le pistage (tracking), chacun utilisant un champ lexical spécifique. Ceci s’explique en partie par les différentes applications considérées (industrielles, civiles ou militaires), et en partie par les différentes communautés abordant ces problèmes depuis différents points de vue (planification symbolique ou géométrique, commande, capteurs, théorie des jeux, allocation de tâches , etc.).

Face à l’étendue des problèmes de robotique relatifs à la notion de cible, on dénombre un grand nombre de contributions et un large éventail d’approches. Plusieurs études proposent une vue d’ensemble sur quelques problèmes spécifiques, en rassemblant les travaux qui leur sont relatifs . Elles forment de bons points d’entrée pour le lecteur désireux d’approfondir ses connaissances sur un problème précis ou sur le point de vue d’une communauté. Dans ce chapitre, notre objectif est d’aller au-delà des frontières entre ces communautés et au-delà des spécificités des problèmes rencontrés, afin d’élargir le champ des études déjà existantes. La détection et le suivi de cibles, qui forment les deux grandes catégories de scénarios relatifs aux cibles, ont a priori peu de choses en commun et sont abordés séparément, comme deux phases distinctes. Pourtant, en pratique, ces scénarios sont généralement entremêlés et sont joués par les mêmes équipes de robots : c’est pourquoi nous considérons qu’il est pertinent de les analyser et de les traiter de pair.

La surveillance automatique, le nettoyage de zones sécurisées, la patrouille de frontière, le suivi ou la poursuite de cible sont autant de scénarios typiques et relatifs aux cibles en robotique mobile. Dans la plupart des cas, l’environnement est globalement connu : les tâches d’exploration ne sont pas abordées dans cette analyse. Les cibles considérées peuvent être mobiles ou fixes, mais notre étude se concentre principalement sur les cibles mobiles, présentant plus de difficultés .

Détection de cibles

La détection de cibles consiste à trouver – « détecter » – une cible dans un environnement donné. Il peut y avoir une ou plusieurs cibles, et le nombre de capteurs (robots) disponibles n’est pas un critère à ce niveau. Ceux-ci peuvent en outre balayer activement l’environnement grâce à leur mobilité ou bien rester à une position fixe et surveiller passivement l’environnement. On désigne cette dernière classe de problèmes par l’expression couverture de zones : les problèmes rassemblés dans cette catégorie se concentrent sur le placement des capteurs, ce qui implique souvent de partitionner l’environnement puis de distribuer les capteurs selon cette partition.

Lorsque la mission exploite explicitement la mobilité des capteurs, la planification des déplacements se retrouve au cœur des stratégies proposées. On parle alors de recherche de cibles. De tels problèmes peuvent être résolus localement ou globalement. Suivant les modèles utilisés et les hypothèses de départ, les stratégies formulées fournissent des garanties dans le pire cas (capture), des garanties probabilistes (fouille) ou aucune garantie (chasse). La recherche de cible peut être cyclique (patrouille), bien que cela ne présente pas d’intérêt dans le cas d’une capture ou d’une chasse. On notera que, pour chaque problème de recherche de cible, on peut définir une variante nécessitant d’entourer la cible pour éviter qu’elle ne s’échappe, plutôt que de simplement la détecter avec les capteurs ou de « l’attraper » en l’atteignant.

couverture de zones

L’objectif d’une couverture de zones est de déterminer les positions optimales d’un ensemble de capteurs fixes afin de surveiller une zone définie. La forme traditionnelle de la couverture de zones est le célèbre problème des gardiens de musée (the Art Gallery problem), pour lequel il existe de nombreux travaux et résultats . Certaines variantes de la couverture de zones considèrent des capteurs mobiles, mais les stratégies obtenues se concentrent toujours sur le positionnement des capteurs – « où placer les capteurs ? » – plutôt que sur les déplacements de ces capteurs – « comment atteindre les positions retenues ? ».

capture

L’optimalité et la complétude sont des caractéristiques essentielles du problème de capture : le but est de « nettoyer » une zone connue et délimitée tout en fournissant des garanties au pire cas, ce qui signifie que toute cible se trouvant dans la zone définie sera trouvée quelles que soient ses capacités . Pour cela, l’équipe poursuivante essaie d’encercler les cibles présentes. Aucune hypothèse sur ces dernières n’est formulée :

leurs positions ne sont pas estimées et les cibles peuvent même avoir des capacités extraordinaires comme une vitesse infinie. Les problèmes de capture sont aussi désignés sous d’autres termes, parmi lesquels « poursuite / évasion » (pursuit-evasion), « sécuriser » (search and secure) ou encore le jeu « des gendarmes et des voleurs » (cops and robbers games).

Les travaux dans cette classe de problème sont souvent basés sur des résultats mathématiques solides, et l’on peut distinguer deux principales approches [10, 41] : poser le problème comme étant celui d’un « nettoyage de graphe » (graph clearing), ou l’aborder d’un point de vue purement géométrique, dans un environnement plan et polygonal. Une variante courante consiste à trouver le nombre minimal d’agents nécessaires pour obtenir des garanties au pire cas.

Fouille

La principale différence entre les problèmes de capture et les problèmes de fouille porte sur les garanties au pire cas, absentes pour les seconds. En effet, ces derniers sont caractérisés par des considérations probabilistes, et fournissent des garanties en accord [163]. Ce type de considérations est principalement motivé par un manque de ressources – manque de robots ou de temps – qui ne permet pas de gérer les pires cas. Cela peut également être motivé par la recherche d’un compromis entre l’efficacité et la probabilité d’apparition de certaines situations particulières et difficiles. Les solutions aux problèmes de fouille exploitent les probabilités de distributions connues ou estimées a priori, définies sur les modèles d’environnement – la position estimée des cibles par exemple. La plupart des auteurs tentent de borner la probabilité de détection des cibles. Celles-ci peuvent être antagonistes ou non, ce dernier cas étant plus simple à gérer car induisant une complexité algorithmique bien plus faible. Ce modèle de cible est celui utilisé dans les scénarios de « secours » (search and rescue), pour lesquels l’urgence de la situation empêche de mener une recherche exhaustive des victimes dans la zone et impose donc des priorités, ce que gèrent très bien les modèles probabilistes.

PATROUILLE

Lors que la recherche active de cible – avec capteurs mobiles – se répète dans le temps, on emploie le terme de problèmes de patrouille. La patrouille est comme une version cyclique de la fouille, qui implique une analyse statistique des performances au cours du temps. Elle considère notamment le temps écoulé entre deux observations ou « visites » d’une même position. C’est un domaine de recherche plutôt récent, qui s’est réellement développé au cours de la dernière décennie [137].

Chasse

Enfin, il existe des situations pour lesquelles aucune garantie n’existe quant à la détection ou la capture des cibles. Nous désignons cette classe de problèmes comme étant des problèmes de chasse. Cette absence de garantie vient d’un manque de ressources – robots ou temps – mais aussi d’un manque d’informations, en l’absence desquelles on ne peut fournir ni exploiter de modèles probabilistes sur la position des cibles.

Table des matières

INTRODUCTION
I considérations générales sur la planification multirobot
1 état de l’art : taxonomie
1.1 Motivations
1.2 Taxonomie
1.2.1 Détection de cibles
1.2.2 Pistage de cibles
1.3 État de l’art
2 détection de cibles
2.1 Couverture de zones – Gardiens de musée
2.2 Capture – Nettoyage de graphes contaminés
2.3 Fouille probabiliste
2.4 Patrouille
2.5 Chasse
3 p istage de c ibles
3.1 Localisation des cibles
3.2 Suivi
3.3 Observation – CMOMMT
4 analyse et synthèse de l’état de l’art
4.1 Approches récurrentes
4.1.1 Théorie et Pratique
4.1.2 De la décentralisation
4.1.3 Le besoin de coopération
4.1.4 Environnements incertains et dynamiques
4.1.5 Planification et Optimisation
4.2 Modèles principalement exploités
4.2.1 Modèles de l’environnement
4.2.2 Modèles des agents
4.3 Résultats et validations expérimentales
Bilan
II contributions algorithmiques
5 modèles
5.1 Impact des modèles
5.2 Modèles et planification
5.3 Organisation des modèles et données associées
5.3.1 Une gestion commune
5.3.2 Différents niveaux d’abstraction
5.3.3 Géolocalisation
5.4 Intégration
5.4.1 La librairie Gladys
5.4.2 Fonctions d’accès aux données
5.4.3 Gestion des états
5.5 Bilan
6 patrouille de zones sécurisées : formalisme
et théorie
6.1 Contexte et approche
6.2 Modélisation du problème
6.3 Échantillonnage et instanciation
6.3.1 Échantillonnage orienté positions
6.3.2 Échantillonnage orienté perceptions
6.3.3 Échantillonnage multiple perceptions-positions
6.4 Résolution par parcours de graphe
6.4.1 Algorithme de patrouille
6.4.2 Terminaison, correction et complexité
6.5 Optimisation en nombres entiers
6.5.1 Formulation TOP orientée positions
6.5.2 Formulation TOP orientée perceptions
6.5.3 Formulation « Sightseeing Problem »
6.5.4 Élimination des sous-tours
6.6 Discussion sur les formulations IP
6.6.1 Exploitation des modèles
6.6.2 Résoudre le problème d’optimisation
6.6.3 Fonctions objectifs alternatives
6.6.4 Contraintes de communication
6.6.5 Patrouilles cycliques et considérations sur le long terme
7 résultats expérimentaux
7.1 Intégration
7.1.1 Intégration des modèles
7.1.2 Solveur IP
7.2 Résultats préliminaires
7.2.1 Complexité des formulations IP
7.2.2 Performances face à la complexité
7.3 Les schémas de patrouille
7.3.1 Environnement « Parking du LAAS »
7.3.2 Environnement « Caylus »
7.3.3 Environnement « Manhattan »
7.3.4 Environnement « Plaine »
7.4 Influence de l’échantillonnage
7.5 Cycles et performances sur le long terme
7.5.1 Métriques
7.5.2 Oisiveté
7.5.3 Non-prédictibilité
7.6 Communication
7.7 Bilan et perspectives
8 patrou illes décentral isées
8.1 Décentralisation et résolution IP
8.2 Le besoin de coordination
8.3 Aspects long terme
8.3.1 Oisiveté
8.3.2 Non-prédictibilité
8.3.3 Formulations SP
8.3.4 Aspects « très long terme »
8.4 Communications
8.5 Bilan et perspectives
9 suivi de cible
9.1 Contexte
9.2 Approche : un suivi monorobot avec support multirobot
9.2.1 Formalisme
9.2.2 Modèles réalistes
9.3 Évaluer le besoin de renforts
9.3.1 Évaluer les échecs
9.3.2 Stratégie locale de suivi
9.3.3 Arbre d’états et graphe cyclique de suivi
9.4 Résultats expérimentaux
9.4.1 Simulations ad hoc
9.4.2 Simulations réalistes
9.5 Suivi et renforts
9.6 Bilan et perspectives
Discussion
III annexes
CONCLUSION

Lire le rapport complet