کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950689 1364299 2017 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Gathering of oblivious robots on infinite grids with minimum traveled distance
ترجمه فارسی عنوان
جمع آوری روبات های غیرفعال روی شبکه های بی نهایت با کمترین فاصله از راه دور
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A largely studied version of the gathering problem asks to move a set of robots initially placed at different vertices of an anonymous graph toward a common vertex, and to let them remain at such a vertex. Asynchronous robots move based on the so-called Look-Compute-Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move toward one of its neighbors (Compute), and then it performs the computed move (Move), eventually. So far, the main goal has been to detect the minimal assumptions that allow to accomplish the task, without taking care of any cost measure. In this paper, we are interested in optimal algorithms in terms of total number of moves. We consider infinite grids, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 254, Part 3, June 2017, Pages 377-391
نویسندگان
, ,