Maximum independent set formation on a finite grid by myopic robots

作     者：Das, Raja Sharma, Avisek Sau, Buddhadeb 

作者机构：Jadavpur Univ Dept Math Kolkata India 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (Theor Comput Sci)

年 卷 期：2025年第1031卷

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Council of Scientific & Industrial Research (CSIR) [09/096 (1031) /2020-EMR-I] University Grants Commission (UGC) Science and Engineering Research Board (SERB) [MTR/2021/000835] 

主　　题：Myopic robot Maximum independent set Finite grid Autonomous robots Robot with lights Distributed algorithms 

摘      要：This work deals with the Maximum Independent Set (MAXIS) formation problem in a finite rectangular grid by autonomous robots. Suppose we are given a set of identical robots, where each robot is placed on a node of a finite rectangular grid G such that no two robots are on the same node. The MAXIS formation problem asks to design an algorithm and each robot will move autonomously after executing the algorithm and terminate at a node such that after a finite time the set of nodes occupied by the robots is a maximum independent set of G. We assume that robots are anonymous and they execute the same distributed algorithm. Previous works solved this problem using one or several door nodes through which the robots enter the grid or the graph one by one and occupy the required nodes. In this work, we propose a deterministic algorithm that solves the MAXIS formation problem in a more generalized scenario, i.e., when the total number of required robots to form a MAXIS are arbitrarily placed on the grid. The proposed algorithm works under a semi-synchronous scheduler using robots with only two hop visibility range and only three colors.