TY - JOUR

T1 - Team assembling problem for asynchronous heterogeneous mobile robots

AU - Liu, Zhiqiang

AU - Yamauchi, Yukiko

AU - Kijima, Shuji

AU - Yamashita, Masafumi

N1 - Funding Information:
This work was supported by Grant-in-Aid for Scientific Research on Innovative Areas “Molecular Robotics” (No. JP24104003) of MEXT, Japan and JSPS KAKENHI Grant Numbers JP15K15938, JP15H00821, JP25700002, JP15K11987, and JP15H02666.
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2018/4/18

Y1 - 2018/4/18

N2 - We investigate the team assembling problem for a swarm of heterogeneous mobile robots which requires the robots to autonomously partition themselves into teams satisfying a given specification A=(a1,a2,…,ak), where ai is the number of robots with color (i.e., robot type) i in one team. A robot, which is represented by a point in the two-dimensional Euclidean space, is asynchronous, oblivious, and anonymous in the sense that robots with the same color are indistinguishable and all robots execute the same algorithm to determine their moves. It has neither any access to the global coordinate system nor any explicit communication medium. We show that GCD(a1,a2,…,ak)=1 is a necessary and sufficient condition for the robots to have an algorithm to solve the team assembling problem in a self-stabilizing manner, i.e., starting from any arbitrary initial configuration, the robots form teams according to the specification.

AB - We investigate the team assembling problem for a swarm of heterogeneous mobile robots which requires the robots to autonomously partition themselves into teams satisfying a given specification A=(a1,a2,…,ak), where ai is the number of robots with color (i.e., robot type) i in one team. A robot, which is represented by a point in the two-dimensional Euclidean space, is asynchronous, oblivious, and anonymous in the sense that robots with the same color are indistinguishable and all robots execute the same algorithm to determine their moves. It has neither any access to the global coordinate system nor any explicit communication medium. We show that GCD(a1,a2,…,ak)=1 is a necessary and sufficient condition for the robots to have an algorithm to solve the team assembling problem in a self-stabilizing manner, i.e., starting from any arbitrary initial configuration, the robots form teams according to the specification.

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

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

U2 - 10.1016/j.tcs.2018.01.009

DO - 10.1016/j.tcs.2018.01.009

M3 - Article

AN - SCOPUS:85043520791

SN - 0304-3975

VL - 721

SP - 27

EP - 41

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -