Algorithms and architecture to control the exploration of an area by a fleet of autonomous submarines
Algorithmes et architecture pour le contrôle de l’exploration d’une zone par une flotte de sous-marins autonomes
Résumé
Since the 80s, progresses in all the functions necessary for the autonomy of underwater robots have allowed the development of operational solutions, mainly for data collection missions.The deployment of these robots in fleets could allow to take advantage of the full potential of these advances. Research in this domain has however not yet reached a sufficient level of maturity. One of the reasons is that the underwater context imposes extremely strong constraints on communications, which implies major difficulties in establishing cooperation strategies.Nevertheless, cooperating multi-robot systems capable of evolving underwater are needed for complex missions. This is the case of mine hunting missions, which consist in detecting and locating mines. These missions are dynamic by nature because it is necessary to identify the detected suspicious objects. The robots must therefore react to new targets and distribute them within the fleet. However, there may be more than one way to achieve an objective, and specific constraints may be imposed by the operator. These elements induce complex dependencies on the tasks to achieve.The distribution of these objectives within the system defines ``Multi-Robot Allocation Task Problems (MRTA)'' to be solved before and during the mission. Given the specificities of the mission, such as communication constraints and complex dependencies that may link tasks, solving an MRTA problem is difficult.The solution to an MRTA problem defines a plan to be executed by the robots. The execution of this plan is, however, not deterministic. So each robot must supervise the plan execution in order to detect deviations, which must be repaired to not compromise the mission.The implementation of decision, supervision, and repair algorithms that are able to meet these challenges is at the heart of our work. We propose to base these algorithms on methods mixing auction-based allocation and hierarchical planning.Auctions allow to decentralize the decision in order to cope with communication constraints.However, with these methods, it is often difficult to obtain solutions in reasonable time and quality when the tasks involve complex dependencies. We address this challenge by exploiting hierarchical planning within our auction scheme. Finally, we leverage the rich structures used by the decision algorithm to allow robots to supervise and repair their plans.The resulting architecture, called HaucTioN, was implemented and evaluated in a simulation environment reproducing the main characteristics of the mission, including communication losses and the presence of hazards.
Depuis les années 80, les progrès dans l'ensemble des fonctions nécessaires à l'autonomie des robots sous-marins ont permis le développement de solutions opérationnelles, principalement pour des missions de recueil de données.Le déploiement en flotte de ces robots pourrait permettre de tirer le plein potentiel de ces progrès, mais les recherches dans ce secteur n'ont pas encore atteint un niveau de maturité suffisant. Une des raisons est que le contexte sous-marin impose des contraintes extrêmement fortes sur les communications, ce qui implique de grandes difficultés à l'établissement de stratégies de coopération.Un réel besoin pour des systèmes multirobots complexes, capables d’évoluer sous l’eau en coopération existe cependant, c’est le cas du contexte opérationnel entourant la chasse aux mines, qui consiste à détecter et localiser des mines. Cette mission, qui est initialement une mission de couverture, est par nature dynamique, car il faut identifier les objets suspects détectés. Les robots doivent donc réagir aux nouveaux objectifs et les répartir au sein de la flotte. Il peut cependant exister plus d’une manière de réaliser un objectif, et des contraintes spécifiques peuvent être imposées par l’opérateur. Ces éléments induisent des dépendances complexes entre les tâches à exécuter.Les répartitions de ces objectifs au sein du système définissent des problèmes d’allocation de tâches multirobots (« Multi-Robot Allocation Task » ou MRTA) devant être résolus avant et pendant la mission. Au regard des spécificités de la mission, telles que les contraintes de communication et les dépendances complexes pouvant lier les tâches, la résolution d’un problème de MRTA est difficile.La solution d’un problème de MRTA définit un plan qui doit être exécuté par les robots.L’exécution de ce plan n’est cependant pas déterministe, chaque robot doit donc superviser l’exécution de son plan afin d’en détecter les divergences. Au même titre que l’intégration de nouveaux objectifs, ces divergences sont des aléas qu’il faut réparer afin de ne pas compromettre la mission.La mise en place d’algorithmes de décision, de supervision, et de réparation, aptes à répondre à ces défis est au cœur de nos travaux. Nous proposons de faire reposer ces algorithmes sur des méthodes entremêlant allocation par enchères et planification hiérarchique.Grâce aux enchères nous décentralisons la décision pour faire face aux contraintes de communication, cependant, il est souvent difficile avec ces méthodes d’obtenir des solutions en temps et qualité raisonnables lorsque les tâches comprennent des dépendances complexes. Nous relevons ce défi en exploitant la planification hiérarchique au sein de notre schéma d’enchère. Enfin, nous tirons profit des structures riches utilisées par l’algorithme de décision pour permettre aux robots de superviser et réparer leurs plans.L’architecture résultante, appelée HaucTioN, a été implémentée et évaluée dans un environnement de simulation reproduisant les principales caractéristiques de la mission, notamment les pertes de communication et la présence d’aléas.
Domaines
Robotique [cs.RO]
Origine : Version validée par le jury (STAR)