摘要
One of the fundamental problems of distributed systems that has been extensively studied is the exploration of different network topologies. In exploration, each node of the graph network has to be visited by at least one robot within a finite time. Existing literature typically assumes on various networks like lines, rings, tori, arbitrary networks, and rectangular grids. To the best of our knowledge, no existing work has addressed the exploration problem considering triangular grid. In this work the exploration problem is considered on rectangle enclosed triangular grid (RETG) with myopic robots, where the visibility of the robot is limited to a specific distance, denoted as ϕ, since infinite visibility becomes impractical for a very large network. The robots are luminous and work under FSYNC scheduler. Firstly the cases where the perpetual RETG exploration is not possible are discussed in three impossibility results. Then two algorithms are provided to solve the exploration problem on RETG. The first algorithm requires two robots without common chirality, ϕ = 1, and three colors of light. The second algorithm requires two robots with common chirality, ϕ = 2, and two colors of light. Using luminous robots to decrease both visibility and the number of robots is a nice trade-off from the implementation’s point of view as increasing visibility is more expensive than using robots with a light having finite colors.
摘要译文
One of the fundamental problems of distributed systems that has been extensively studied is the exploration of different network topologies. In exploration, each node of the graph network has to be visited by at least one robot within a finite time. Existing literature typically assumes on various networks like lines, rings, tori, arbitrary networks, and rectangular grids. To the best of our knowledge, no existing work has addressed the exploration problem considering triangular grid. In this work the exploration problem is considered on rectangle enclosed triangular grid (RETG) with myopic robots, where the visibility of the robot is limited to a specific distance, denoted as ϕ, since infinite visibility becomes impractical for a very large network. The robots are luminous and work under FSYNC scheduler. Firstly the cases where the perpetual RETG exploration is not possible are discussed in three impossibility results. Then two algorithms are provided to solve the exploration problem on RETG. The first algorithm requires two robots without common chirality, ϕ = 1, and three colors of light. The second algorithm requires two robots with common chirality, ϕ = 2, and two colors of light. Using luminous robots to decrease both visibility and the number of robots is a nice trade-off from the implementation’s point of view as increasing visibility is more expensive than using robots with a light having finite colors.
Raja Das[1];Pritam Goswami[2];Brati Mondal[1];Buddhadeb Sau[1]. Rectangle Enclosed Triangular Grid Exploration with Myopic Luminous Robots[C]//ICDCN '25: Proceedings of the 26th International Conference on Distributed Computing and Networking, Hyderabad India, January 4 - 7, 2025, IN: ACM, 2025: 249 - 253