A unified approach for different tasks on rings in robot-based computing systemsReportar como inadecuado

A unified approach for different tasks on rings in robot-based computing systems - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués 2 UNIVAQ - University of L-Aquila Italy 3 DMI - Dipartimento di Matematica e Informatica Perugia 4 Facultad de Ingeniería y Ciencias Santiago

Abstract : A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems in the field: the exclusive perpetual exploration, the exclusive perpetual graph searching and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing all edges of the network infinitely often; and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the famous CORDA distributed computing model where the robots cannot communicate but can perceive the positions of other robots. More precisely, each robot is equipped with visibility sensors and motion actuators, and it operates in Look-Compute-Move asynchronous cycles. Moreover, robots are anonymous, oblivious, uniform and have no common sense of orientation. For the first two problems, the exclusivity constraint must also be satisfied, i.e., a node can be occupied by at most one robot. In this setting, we devise algorithms that, starting from any exclusive rigid i.e. aperiodic and asymmetric configuration, solve the three above mentioned problems in anonymous ring-topologies. Besides being a unified approach for three different tasks, the given algorithms solve some open problems. Moreover, we provide some impossibility results for the perpetual graph searching problem.

Autor: Gianlorenzo D-Angelo - Gabriele Di Stefano - Alfredo Navarra - Nicolas Nisse - Karol Suchan -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados