检索结果-内蒙古大学图书馆

arbitrary pattern formation by opaque fat robots on infinite grid

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2022年第5期37卷 542-570页

作者： Kundu, Manash Kumar Goswami, Pritam Ghosh, Satakshi Sau, Buddhadeb Gayeshpur Govt Polytech Dept Sci & Humanities Kalyani 741234 W Bengal India Jadavpur Univ Dept Math Kolkata 700032 W Bengal India

arbitrary pattern formation (APF) by a swarm of mobile robots is a widely studied problem in the literature. Many works regarding APF have been proposed on plane and infinite grid by point robots. But in practical application, it is impossible to design point robots. In Bose et al. [arbitrary pattern formation on infinite grid by asynchronous oblivious robots. Theor Comput Sci. 2020;815:213-227], the robots are assumed opaque fat robots but the environment is plane. To the best of our knowledge, no work till now ever considered the APF problem assuming opaque fat robots on infinite grid where movements are restricted. In this paper, we have provided a collisionless distributed algorithm and solved APF using 9 colours.

关键词： Distributed algorithm arbitrary pattern formation opaque fat robots luminous robots asynchronous infinite grid

来源：评论

学校读者我要写书评

暂无评论

Move-optimal arbitrary pattern formation by mobile robots on rectangular grid using near-optimal spatial area

引用

THEORETICAL COMPUTER SCIENCE 2025年 1038卷

作者： Sharma, Avisek Ghosh, Satakshi Goswami, Pritam Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata 700032 West Bengal India Int Inst Informat Technol IIIT Bhubaneswar Dept Basic Sci & Humanities Bhubaneswar 751003 Odisha India Sister Nivedita Univ Dept Comp Sci & Engn Kolkata 700156 West Bengal India

arbitrary pattern formation (APF) is a well-studied problem in swarm robotics. To the best of our knowledge, the problem has been considered in two different settings: one in a euclidean plane and another in an infinite grid. This work deals with the problem in an infinite rectangular grid setting. The previous works in literature dealing with the APF problem in an infinite grid had a fundamental issue. These deterministic algorithms use a lot of spatial area in the grid to solve the problem, mainly to maintain the asymmetry of the configuration and avoid any collision. These solution techniques cannot be useful if there is a spatial constraint in the application field. In this work, we consider luminous robots (each robot equipped with a light that can take three colors) to avoid symmetry, but we carefully designed a deterministic algorithm that solves the APF problem using the minimal required spatial area in the grid if the initial pattern is asymmetric. The robots are autonomous, identical, and anonymous, and they operate in Look-Compute-Move cycles under a fully-asynchronous scheduler. The APF algorithm proposed in [1] by Bose et al. can be modified using luminous robots so that it uses minimal spatial area, but that algorithm is not move-optimal. The algorithm proposed in this paper not only uses minimal spatial area but is also asymptotically move-optimal.

关键词： Distributed algorithms arbitrary pattern formation Rectangular grid Robot with lights Optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

arbitrary pattern formation by asynchronous opaque robots with lights

引用

THEORETICAL COMPUTER SCIENCE 2021年 849卷 138-158页

作者： Bose, Kaustav Kundu, Manash Kumar Adhikary, Ranendu Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India Gayeshpur Govt Polytech Kalyani W Bengal India

The arbitrary pattern formation problem asks for a distributed algorithm that moves a set of autonomous mobile robots to form any arbitrary pattern given as input. The robots are assumed to be autonomous, anonymous and identical. They operate in Look-Compute Move cycles under an asynchronous scheduler. The robots do not have access to any global coordinate system. The movement of the robots is assumed to be rigid, which means that each robot is able to reach its desired destination without interruption. The existing literature that investigates this problem, considers robots with unobstructed visibility. This work considers the problem in the more realistic obstructed visibility model, where the view of a robot can be obstructed by the presence of other robots. The robots are assumed to be punctiform and equipped with visible lights that can assume a constant number of predefined colors. We have studied the problem in two settings based on the level of consistency among the local coordinate systems of the robots: two axis agreement (they agree on the direction and orientation of both coordinate axes) and one axis agreement (they agree on the direction and orientation of only one coordinate axis). In both settings, we have provided a full characterization of initial configurations from where any arbitrary pattern can be formed. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Distributed algorithm arbitrary pattern formation Leader election Autonomous robots Opaque robots Luminous robots Obstructed visibility Asynchronous scheduler Look-compute-move cycle

来源：评论

学校读者我要写书评

暂无评论

arbitrary pattern formation on infinite grid by asynchronous oblivious robots

引用

THEORETICAL COMPUTER SCIENCE 2020年 815卷 213-227页

作者： Bose, Kaustav Adhikary, Ranendu Kundu, Manash Kumar Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India

The arbitrary pattern formation problem asks to design a distributed algorithm that allows a set of autonomous mobile robots to form any specific but arbitrary geometric pattern given as input. The problem has been extensively studied in the literature in continuous domains. This paper investigates a discrete version of the problem where the robots are operating on a two dimensional infinite grid. The robots are assumed to be autonomous, identical, anonymous and oblivious. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not have access to any common global coordinate system. However, the grid allows the robots to have a partial agreement on coordinate system as they can align the axes of their local coordinate systems along the grid lines. In this setting, we have shown that a set of robots can form any pattern, if their starting configuration is asymmetric. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Distributed algorithm Autonomous robot arbitrary pattern formation Grid Asynchronous Look-compute-move cycle

来源：评论

学校读者我要写书评

暂无评论

arbitrary pattern formation by Opaque Fat Robots with Lights 6th

Arbitrary Pattern Formation by Opaque Fat Robots with Lights

引用

6th International Conference on Algorithms and Discrete Applied Mathematics

作者： Bose, Kaustav Adhikary, Ranendu Kundu, Manash Kumar Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India Gayeshpur Govt Polytech Kalyani W Bengal India

ISBN: (纸本)9783030392185;9783030392192

arbitrary pattern formation is a widely studied problem in autonomous robot systems. The problem asks to design a distributed algorithm that moves a team of autonomous, anonymous and identical mobile robots to form any arbitrary pattern given as input. The majority of the existing literature investigates this problem for robots with unobstructed visibility. In a few recent works, the problem has been studied in the obstructed visibility model, where the view of a robot can be obstructed by the presence of other robots. However, in these works, the robots have been modelled as dimensionless points in the plane. In this paper, we have considered the problem in the more realistic setting where the robots have a physical extent. In particular, the robots are modelled as opaque disks. Furthermore, the robots operate under a fully asynchronous scheduler. They do not have access to any global coordinate system, but agree on the direction and orientation of one coordinate axis. Each robot is equipped with an externally visible light which can assume a constant number of predefined colors. In this setting, we have given a complete characterization of initial configurations from where any arbitrary pattern can be formed by a deterministic distributed algorithm.

关键词： Distributed algorithm arbitrary pattern formation Leader election Opaque fat robots Luminous robots Asynchronous scheduler

来源：评论

学校读者我要写书评

暂无评论

arbitrary pattern formation by Asynchronous Opaque Robots with Lights 26th

Arbitrary Pattern Formation by Asynchronous Opaque Robots wi...

引用

26th International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Bose, Kaustav Kundu, Manash Kumar Adhikary, Ranendu Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India

ISBN: (纸本)9783030249212;9783030249229

The arbitrary pattern formation problem asks for a distributed algorithm that moves a set of autonomous mobile robots to form any arbitrary pattern given as input. The robots are assumed to be autonomous, anonymous and identical. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not have access to any global coordinate system. The existing literature that investigates this problem, considers robots with unobstructed visibility. This work considers the problem in the more realistic obstructed visibility model, where the view of a robot can be obstructed by the presence of other robots. The robots are assumed to be punctiform and equipped with visible lights that can assume a constant number of predefined colors. We have studied the problem in two settings based on the level of consistency among the local coordinate systems of the robots: two axis agreement (they agree on the direction and orientation of both coordinate axes) and one axis agreement (they agree on the direction and orientation of only one coordinate axis). In both settings, we have provided a full characterization of initial configurations from where any arbitrary pattern can be formed.

关键词： Distributed algorithm arbitrary pattern formation Leader election Autonomous robots Opaque robots Luminous robots Obstructed visibility Asynchronous scheduler Look-compute-move cycle

来源：评论

学校读者我要写书评

暂无评论

arbitrary pattern formation on Infinite Grid by Asynchronous Oblivious Robots 13th

Arbitrary Pattern Formation on Infinite Grid by Asynchronous...

引用

13th International Conference on Algorithms and Computation (WALCOM)

作者： Bose, Kaustav Adhikary, Ranendu Kundu, Manash Kumar Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India

ISBN: (纸本)9783030105648;9783030105631

The arbitrary pattern formation problem asks to design a distributed algorithm that allows a set of autonomous mobile robots to form any specific but arbitrary geometric pattern given as input. The problem has been extensively studied in literature in continuous domains. This paper investigates a discrete version of the problem where the robots are operating on a two dimensional infinite grid. The robots are assumed to be autonomous, identical, anonymous and oblivious. They operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not agree on any common global coordinate system or chirality. We have shown that a set of robots can form any arbitrary pattern, if their starting configuration is asymmetric.

关键词： Distributed algorithm Autonomous robots arbitrary pattern formation Grid Asynchronous Look-Compute-Move cycle

来源：评论

学校读者我要写书评

暂无评论

Move optimal and time optimal arbitrary pattern formations by asynchronous robots on infinite grid

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2023年第1期38卷 35-57页

作者： Ghosh, Satakshi Goswami, Pritam Sharma, Avisek Sau, Buddhadeb Jadavpur Univ Dept Math Kolkata India

The arbitrary pattern formation (APF) is widely studied in distributed computing for swarm robots. This paper deals with the APF problem in an infinite grid under an asynchronous scheduler. In [Bose K, Adhikary R, Kundu MK, et al. arbitrary pattern formation on infinite grid by asynchronous oblivious robots. Theor Comput Sci. 2020;815:213-227], the authors proposed an algorithm for APF problem in OBLOT model under an asynchronous scheduler, but the proposed algorithm was neither time optimal nor move optimal. This work provides two algorithms that solve APF problem in an asynchronous scheduler. The first algorithm is move optimal considering OBLOT model and the second algorithm is move and time optimal considering the LUMI model, where each robot has one light having three distinct colours.

关键词： Distributed computing autonomous robots arbitrary pattern formation robots with lights asynchronous look-compute-move cycle grid

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：