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 -