2017/07/21 by Huda Chuangpishit, Jurek Czyzowicz, Chuangpishit, Huda +5
Computer Science · Engineering · #Distributed #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Parallel #Robotic Path Planning Algorithms #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1707.06776
openalex publication_date 2017/07/21 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28
A set of mobile robots is placed at points of an infinite line. The robots\nare equipped with GPS devices and they may communicate their positions on the\nline to a central authority. The collection contains an unknown subset of\n"spies", i.e., byzantine robots, which are indistinguishable from the\nnon-faulty ones. The set of the non-faulty robots need to rendezvous in the\nshortest possible time in order to perform some task, while the byzantine\nrobots may try to delay their rendezvous for as long as possible. The problem\nfacing a central authority is to determine trajectories for all robots so as to\nminimize the time until the non-faulty robots have rendezvoused. The\ntrajectories must be determined without knowledge of which robots are faulty.\nOur goal is to minimize the competitive ratio between the time required to\nachieve the first rendezvous of the non-faulty robots and the time required for\nsuch a rendezvous to occur under the assumption that the faulty robots are\nknown at the start. We provide a bounded competitive ratio algorithm, where the\ncentral authority is informed only of the set of initial robot positions,\nwithout knowing which ones or how many of them are faulty. When an upper bound\non the number of byzantine robots is known to the central authority, we provide\nalgorithms with better competitive ratios. In some instances we are able to\nshow these algorithms are optimal.\n