摘要
We consider a strong variant of the crash fault-tolerant gathering problem called stand-up indulgent gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (that is, they are myopic), and emit a visible color from a fixed set (that is, they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: \(M_{init}\), which denotes the number of nodes between two border nodes, and \(O_{init}\), which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if \(M_{init}\) or \(O_{init}\) is odd, SUIG can be solved in the fully synchronous model.
摘要译文
We consider a strong variant of the crash fault-tolerant gathering problem called stand-up indulgent gathering (SUIG), by robots endowed with limited visibility sensors and lights on line-shaped networks. In this problem, a group of mobile robots must eventually gather at a single location, not known beforehand, regardless of the occurrence of crashes. Differently from previous work that considered unlimited visibility, we assume that robots can observe nodes only within a certain fixed distance (that is, they are myopic), and emit a visible color from a fixed set (that is, they are luminous), without multiplicity detection. We consider algorithms depending on two parameters related to the initial configuration: \(M_{init}\), which denotes the number of nodes between two border nodes, and \(O_{init}\), which denotes the number of nodes hosting robots. Then, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if \(M_{init}\) or \(O_{init}\) is odd, SUIG can be solved in the fully synchronous model.
Quentin Bramas & Anissa Lamani[1];Hirotsugu Kakugawa[2];Sayaka Kamei[3];Fukuhito Ooshita[4];Masahiro Shibata[5];Sébastien Tixeuil[6];Leonard Barolli [7]. Stand-Up Indulgent Gathering on Lines for Myopic Luminous Robots. Advanced Information Networking and Applications Proceedings of the 38th International Conference on Advanced Information Networking and Applications (AINA-2024), Volume 2[M].DE: Springer, 2024: 110-121