Gathering few fat mobile robots in the plane

Jurek Czyzowicz; Leszek Ga̧sieniec; Andrzej Pelc

doi:10.1016/j.tcs.2008.10.005

Gathering few fat mobile robots in the plane

Jurek Czyzowicz, Leszek Ga̧sieniec, Andrzej Pelc

Research output: Contribution to journal › Article › peer-review

99 Scopus citations

Abstract

Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.

Original language	English (US)
Pages (from-to)	481-499
Number of pages	19
Journal	Theoretical Computer Science
Volume	410
Issue number	6-7
DOIs	https://doi.org/10.1016/j.tcs.2008.10.005
State	Published - Feb 28 2009
Externally published	Yes

Keywords

Algorithm
Asynchronous
Gathering
Robot

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/j.tcs.2008.10.005

Cite this

@article{7df5dec2de784a8683e31524fcd466f4,

title = "Gathering few fat mobile robots in the plane",

abstract = "Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.",

keywords = "Algorithm, Asynchronous, Gathering, Robot",

author = "Jurek Czyzowicz and Leszek G{\c a}sieniec and Andrzej Pelc",

note = "Funding Information: The first and third author{\textquoteright}s research was partially supported by NSERC discovery grant. The third author{\textquoteright}s research was partially supported by the Research Chair in Distributed Computing at the Universit{\'e} du Qu{\'e}bec en Outaouais.",

year = "2009",

month = feb,

day = "28",

doi = "10.1016/j.tcs.2008.10.005",

language = "English (US)",

volume = "410",

pages = "481--499",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "6-7",

}

TY - JOUR

T1 - Gathering few fat mobile robots in the plane

AU - Czyzowicz, Jurek

AU - Ga̧sieniec, Leszek

AU - Pelc, Andrzej

N1 - Funding Information: The first and third author’s research was partially supported by NSERC discovery grant. The third author’s research was partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais.

PY - 2009/2/28

Y1 - 2009/2/28

N2 - Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.

AB - Autonomous identical robots represented by unit discs move deterministically in the plane. They do not have any common coordinate system, do not communicate, do not have memory of the past and are totally asynchronous. Gathering such robots means forming a configuration for which the union of all discs representing them is connected. We solve the gathering problem for at most four robots. This is the first algorithmic result on gathering robots represented by two-dimensional figures rather than points in the plain: we call such robots fat.

KW - Algorithm

KW - Asynchronous

KW - Gathering

KW - Robot

UR - http://www.scopus.com/inward/record.url?scp=58549096685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58549096685&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2008.10.005

DO - 10.1016/j.tcs.2008.10.005

M3 - Article

AN - SCOPUS:58549096685

SN - 0304-3975

VL - 410

SP - 481

EP - 499

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 6-7

ER -

Gathering few fat mobile robots in the plane

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this