Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Vendredi 13 Mars 2020 à 11:45

Reachability and Coverage for Connected Agent

par François Schwarzentruber (ENS, Rennes)

Motivated by the increasing appeal of robots in information-gathering missions, we study multi-agent path planning problems in which the agents must remain interconnected. We model an area by a topological graph specifying the movement and the connectivity constraints of the agents. In the first part of the talk, we study the theoretical complexity of the reachability and the coverage problems of a fleet of connected agents. We also introduce a new class called sight-moveable graphs which admit efficient algorithms. In the second part, we re-visit the conflict-based search algorithm known for multi-agent path finding, and define a variant where conflicts arise from disconnections rather than collisions. We give experimental results in which we compare our algorithms with the literature.

GREYC
Université de Caen Normandie
Campus Côte de Nacre
Boulevard du Maréchal Juin
Bâtiment Sciences 3
CS 14032
14032 CAEN cedex 5
TEL : +33 (0)2 31 56 74 86
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr