Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) ParSys
Collaborative delivery by robots that can share energy
Evangelos Bampas

02 May 2018, 10h30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Algorithmique distribuée

Résumé :
We consider the problem of delivery of a packet from a source node to a destination node in a graph, by a team of mobile robots that have very low battery capacity (two units of energy, with one unit spent each time an agent traverses an edge). The robots can collaborate to deliver the packet by exchanging energy or the packet itself whenever two of them are co-located. We study two variants of the problem: In the fixed placement variant, the robots are initially placed at some given nodes of the graph and the question is whether delivery is feasible. We prove that this problem is NP-complete. In the free placement variant, the initial positions of the robots are not fixed but a subset of nodes H of the graph is given as input together with an integer k, and the question is whether there exists a placement of k robots at nodes in H such that delivery is possible. We prove that this problem can be solved in polynomial time, by actually computing the minimum initial energy and the placement of robots at nodes in H that allows them to carry out the delivery.

(joint work with Shantanu Das, Dariusz Dereniowski, and Christina Karousatou)

Pour en savoir plus : https://parsys.lri.fr/seminar.html
Séminaires
Programming computing media
Combinatoire
Friday 20 March 2020 - 14h30
Salle : 445 - PCRI-N
Frédéric Gruau .............................................

Forum dev-LRI
Wednesday 05 February 2020 - 14h00
Salle : 455 - PCRI-N
Erik Bray .............................................

Quantum at LRI
Calcul quantique
Tuesday 04 February 2020 - 09h00
Salle : 465 - PCRI-N
.............................................

Progressive Data Analysis: a new computation parad
Gestion de données du Web
Friday 24 January 2020 - 14h00
Salle : 435 - PCRI-N
Jean-Daniel Fekete .............................................

Jeux d’instructions : des extensions SIMD aux exte
Architectures parallèles
Tuesday 21 January 2020 - 10h30
Salle : 465 - PCRI-N
Daniel Etiemble .............................................