Oblivious Robots Performing Different Tasks on Grid Without Knowing their Team Members Satakshi Ghosh10000 000317474037 Avisek Sharma10000 00018940392X

2025-05-02 0 0 607.04KB 18 页 10玖币

侵权投诉

Oblivious Robots Performing Diﬀerent Tasks on

Grid Without Knowing their Team Members⋆

Satakshi Ghosh1[0000−0003−1747−4037], Avisek Sharma1[0000−0001−8940−392X],

Pritam Goswami1[0000−0002−0546−3894], and Buddhadeb

Sau1[0000−0001−7008−6135]

Jadavpur University, Kolkata, 700032

{satakshighosh.math.rs,aviseks.math.rs,pritamgoswami.math.rs,

buddhadeb.sau}@jadavpuruniversity.in

Abstract. Two fundamental problems of distributed computing are

Gathering and Arbitrary pattern formation (Apf). These two tasks are

diﬀerent in nature as in gathering robots meet at a point but in Apf

robots form a ﬁxed pattern in distinct positions.

In most of the current literature on swarm robot algorithms, it is assumed

that all robots in the system perform one single task together. Two

teams of oblivious robots deployed in the same system and diﬀerent

teams of robots performing two diﬀerent works simultaneously where no

robot knows the team of another robot is a new concept in the literature

introduced by Bhagat et al. [ICDCN’2020].

In this work, a swarm of silent and oblivious robots are deployed on an

inﬁnite grid under an asynchronous scheduler. The robots do not have

access to any global coordinates. Some of the robots are given input

of an arbitrary but unique pattern. The set of robots with the given

pattern is assigned the task of forming the given pattern on the grid.

The remaining robots are assigned with the task of gathering to a vertex

of the grid (not ﬁxed from earlier and not any point where a robot that

is forming a pattern terminates). Each robot knows to which team it

belongs, but can not recognize the team of another robot. Considering

weak multiplicity detection, a distributed algorithm is presented in this

paper which leads the robots with the input pattern into forming it and

other robots into gathering on a vertex of the grid on which no other

robot forming the pattern, terminates.

Keywords: Robots ·Gathering ·Arbitrary pattern formation ·Inﬁnite

grid

1 Introduction

In swarm robotics, robots solving some tasks with minimum capabilities is the

main focus of interest. In the last two decades, there has been huge research

interest in robots working with coordination problems. It is not always easy to

⋆The preliminary version of this paper appeared in the conference ICARA 2023

arXiv:2210.00567v2 [cs.DC] 27 Aug 2024

2 S. Ghosh et al.

use robots with strong capability in real-life applications, as the making of these

robots is not at all cost-eﬀective. If a swarm of robots with minimum capabil-

ities can do the same task then it is eﬀective to use swarm robots rather than

using robots with many capabilities, as the making of these robots in the swarm

is very much cheaper than making robots with many capabilities. Also, it is

very easy to design a robot of a swarm due to the fact that they have mini-

mum capabilities. Depending on these capabilities there are generally four types

of robot models. These models are OBLOT ,FST A,FCOM and LUMI. In

each of these models, robots are assumed to be autonomous (i.e the robots do

not have any central control), identical (i.e the robots are physically indistin-

guishable), and anonymous (i.e the robots do not have any unique identiﬁers).

Furthermore in the OBLOT model, the robots are silent (i.e there is no means

of communication between the robots) and oblivious (i.e the robots do not have

any persistent memory to remember their previous state), in FST A model the

robots are silent but not oblivious, in FCOM model the robots are oblivious

but not silent and in LUMI model robots are neither silent nor oblivious. The

robots after getting activated operate in a Look-Compute-Move (Lcm) cycle.

In the Look phase a robot takes input from its surroundings and then with that

input runs the algorithm in Compute phase to get a destination point as an

output. The robot then goes to that destination point by moving in the Move

phase. The activation of the robots is controlled by a scheduler. There are mainly

three types of schedulers considered in the literature. In a synchronous scheduler,

time is divided into global rounds. In a fully synchronous (FSync) scheduler,

each robot is activated in all the rounds and executes Lcm cycle simultaneously.

In a semi-synchronous (SSync) scheduler all robots may not get activated in

each round. But the robots that are activated in the same round execute the

Lcm cycle simultaneously. Lastly in the asynchronous (ASync) scheduler, there

is no common notion of time, a robot can be activated at any time. There is no

concept of global rounds. So there is no assumption regarding synchronization.

The Gathering and Arbitrary pattern formation are two vastly studied prob-

lems by researchers in the ﬁeld of swarm robot algorithms. These are one of

the fundamental tasks which can be done by autonomous robots in diﬀerent

settings. In the gathering problem, nnumber of robots initially positioned ar-

bitrarily meets at a point not ﬁxed from earlier within ﬁnite time. It is not

always easy to meet at a point with very weak robots in the distributed system.

Similarly, the Arbitrary pattern formation problem is such that robots have to

form a given pattern that is given as input to the robots within a ﬁnite time.

In literature, there are several works that have considered either gathering or

arbitrary pattern formation problem separately. But none of those works con-

sider robots deployed in the same environment working on two diﬀerent tasks.

The environment of robot swarm needs periodic maintenance for making the

environment robust from faults and some other factors. So if the same robot

swarm deployed in the environment can do the maintenance apart from doing

the speciﬁc task assigned to them, it would be more cost-eﬀective. From this

motivation and practical interest, in [2] authors ﬁrst studied the problem where

Performing diﬀerent tasks by robots 3

two teams of oblivious robots work on two diﬀerent tasks, namely gathering

and circle formation on a plane. Here the crucial part is that a robot knows

to which team it belongs, but it can not recognize another robot’s team. The

novelty of the problem would have gone away a bit if the robots are luminous

and gathering team robots put a color on a light to indicate which team they

belong to. But the main motivation of this problem is to extend the work for

more than two diﬀerent tasks and for assigning diﬀerent colors for diﬀerent tasks

would make the number of colors unbounded. For this reason, it is convenient

to solve the problem with the least possible capabilities for the robot swarm.

Also OBLOT model is more self-stabilized and fault tolerant. For these reasons,

in our work, we also consider robots to be oblivious. Now it is challenging to

design a distributed algorithm by which two diﬀerent teams of oblivious robots

can do two diﬀerent tasks simultaneously on a discrete domain because, in any

discrete graph, the movements of robots become restricted. So avoiding collision

becomes a great challenge.

In our work, we have provided a collision-less distributed algorithm following

which two teams of oblivious robots with weak multiplication detection ability

can do two diﬀerent tasks namely gathering and arbitrary pattern formation

simultaneously on an inﬁnite grid under the asynchronous scheduler. Here we

assume that the initial conﬁguration is asymmetric.

2 Earlier Works

Arbitrary pattern formation and gathering of robots are two hugely studied

problems in the distributed system. In literature, there are many works on these

two problems in various settings. Arbitrary pattern formation on a plane was

ﬁrst studied by Suzuki and Yamashita [13]. For the grid network, the arbitrary

pattern formation was ﬁrst studied in [3] in the OBLOT model with full visibil-

ity. But in this paper, the algorithm is not move optimal. So in [9] authors have

shown on an inﬁnite grid a move optimal Apf algorithm under OBLOT model

and a time optimal Apf algorithm under LUMI model. Later in [4] authors

studied the Apf on a regular tessellation graph. In an inﬁnite grid, the arbitrary

pattern formation problem was studied in [11] with opaque robots and in [12]

with fat robots. Similarly, for gathering there are many works in an inﬁnite grid.

In [7], authors have shown that the gathering is possible on a grid without mul-

tiplicity detection. There are many other works ([8,1,5,6]) where authors have

solved gathering on an inﬁnite rectangular grid with various assumptions. In [10]

authors solved the gathering of robots on an inﬁnite triangular grid in Ssync

scheduler under one axis agreement and with one-hop visibility. But in all these

works they only consider that all robots perform one individual task. But in [2]

authors ﬁrst showed that two speciﬁc but diﬀerent tasks can be done by robots

simultaneously on a plane. They showed that gathering and circle formation can

be done by oblivious robots in a plane simultaneously with two diﬀerent teams

of robots using one-axis agreement.

4 S. Ghosh et al.

So here we are interested to show that two diﬀerent tasks namely gather-

ing and the arbitrary pattern formation of oblivious robots can be done on an

inﬁnite grid simultaneously under an asynchronous scheduler without any axis

agreement. This paper ﬁrst time deals with this problem under a discrete envi-

ronment. In [4], authors considered multiplicity points in the target pattern that

needs to be formed. So their work is also capable of forming an arbitrary pattern

along with an additional multiplicity point. But by following their algorithm a

robot on team gathering might end up forming a pattern and also a robot on

team arbitrary pattern formation might end up on the multiplicity point, which

is not the required solution to our problem. The algorithm proposed in paper [9]

uses similar technique to select head and tail robots and also the forming of the

ﬁxed pattern. But in [9] the robots have no multiplicity detection capability and

throughout the algorithm, no multiplicity points will form. So from the existing

previous algorithms (as in [9,4]), two diﬀerent tasks are not trivially solved by

robots as a robot does not know in which team another robot belongs.

3 Model and Problem Statement

Robots Robots are anonymous, identical, and oblivious, i.e. they have no memory

of their past rounds. They can not communicate with each other. There are two

teams between the robots. One is TApf and the other team is Tg. A robot ronly

knows that in which team it belongs to between this two. But a robot can not

identify to which team another robot belongs. All robots are initially in distinct

positions on the grid. The robots can see the entire grid and all other robots’

positions which means they have global visibility. This implies the robots are

transparent and hence the visibility of a robot can not be obstructed by another

robot. Robots have no access to any common global coordinate system. They

have no common notion of chirality or direction. A robot has its local view and

it can calculate the positions of other robots with respect to its local coordinate

system with the origin at its own position. There is no agreement on the grid

about which line is xor y-axis and also about the positive or negative direction

of the axes. As the robots can see the entire grid, they will set the axes of their

local coordinate systems along the grid lines. Also, robots have weak multiplicity

detection capability, which means a robot can detect a multiplicity point but

cannot count the number of robots present at a multiplicity point.

Look-Compute-Move cycles An active robot operates according to the Look-

Compute-Move cycle. In each cycle a robot takes a snapshot of the positions

of the other robots according to its own local coordinate system (Look); based

on this snapshot, it executes a deterministic algorithm to determine whether to

stay put or to move to an adjacent grid point (Compute); and based on the

algorithm the robot either remain stationary or makes a move to an adjacent

grid point (Move). When the robots are oblivious they have no memory of past

conﬁgurations and previous actions. After completing each Look-Compute-

Move cycle, the contents in each robot’s local memory are deleted.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ObliviousRobotsPerformingDifferentTasksonGridWithoutKnowingtheirTeamMembers⋆SatakshiGhosh1[0000−0003−1747−4037],AvisekSharma1[0000−0001−8940−392X],PritamGoswami1[0000−0002−0546−3894],andBuddhadebSau1[0000−0001−7008−6135]JadavpurUniversity,Kolkata,700032{satakshighosh.math.rs,aviseks.math.rs,pritamgo...

展开>> 收起<<

Oblivious Robots Performing Different Tasks on Grid Without Knowing their Team Members Satakshi Ghosh10000 000317474037 Avisek Sharma10000 00018940392X.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Oblivious Robots Performing Different Tasks on Grid Without Knowing their Team Members Satakshi Ghosh10000 000317474037 Avisek Sharma10000 00018940392X

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: