A Complete Set of Connectivity-aware Local Topology Manipulation Operations for Robot Swarms Koresh Khateri1 Karthik Soma Mahdi Pourgholi2 Mohsen Montazeri

2025-04-28 0 0 1.68MB 8 页 10玖币

侵权投诉

A Complete Set of Connectivity-aware Local Topology Manipulation

Operations for Robot Swarms

Koresh Khateri*1, Karthik Soma*, Mahdi Pourgholi2, Mohsen Montazeri,

Lorenzo Sabattini3and Giovanni Beltrame1

Abstract— The topology of a robotic swarm aﬀects the

convergence speed of consensus and the mobility of the robots.

In this paper, we prove the existence of a complete set of local

topology manipulation operations that allow the transformation

of a swarm topology. The set is complete in the sense that any

other possible set of manipulation operations can be performed

by a sequence of operations from our set. The operations

are local as they depend only on the ﬁrst and second hop

neighbors’ information to transform any initial spanning tree

of the network’s graph to any other connected tree with the

same number of nodes. The ﬂexibility provided by our method

is similar to global methods that require full knowledge of

the swarm network. We prove the existence of a sequence of

transformations for any tree-to-tree transformation, and derive

sequences of operations to form a line or star from any initial

spanning tree. Our work provides a theoretical and practical

framework for topological control of a swarm, establishing

global properties using only local information.

I. INTRODUCTION

According to Cayley’s formula [1], there are 𝑁𝑁−2pos-

sible labeled spanning trees for a swarm network with 𝑁

robots. Each of these determines diﬀerent properties (e.g.,

coverage area, consensus rate, and mobility) of the swarm.

In this paper, we investigate the possibility of transforming

any initial spanning tree of the swarm’s network, by only

using local operations, to any other connected tree spanning

all nodes of the system. This transformation is of importance

because a ﬁxed spanning tree restricts the relative movement

of a swarm.

In a ﬁxed topology, the mobility of the robots is con-

strained since initial neighbor robots have to remain neigh-

bors throughout the mission even though they might be

required at diﬀerent locations that are farther than the com-

munication range of the robots, whereas they could break

their connection and still be connected with a multi-hop path.

The existence of a communication path between any pair

of nodes in a robotic network deﬁnes the connectivity of that

network. Continuous connectivity (i.e., strict connectivity

from the start of the mission to the end) between the robots of

a swarm is essential in several applications [2], [3] Assuming

that communication is limited by distance, the existence of

a communication link between two robots depends on their

1École Polytechnique de Montréal, 2900 Boul Édouard-

Montpetit, Québec, CA (email: {koresh.khateri, karthik.soma,

giovanni.beltrame}@polymtl.ca)

2Shahid Beheshti University, Tehran, Iran

3University of Modena and Reggio Emilia, Reggio Emilia, Italy

*These authors contributed equally to this work

−5 0 5 10 15 20 25

X (m)

Y (m)

−2 0 2 4 6

X (m)

−3

−2

−1

Y (m)

−40 −30 −20 −10 0

X (m)

−40

−30

−20

−10

Y (m)

−5.0 −2.5 0.0 2.5 5.0 7.5 10.0

X (m)

−10.0

−7.5

−5.0

−2.5

0.0

2.5

5.0

7.5

Y (m)

−40 −30 −20 −10 0 10 20

X (m)

−50

−40

−30

−20

−10

Y (m)

−20 −10 0 10

X (m)

−15

−10

−5

Y (m)

Fig. 1: Trajectory visualizations for line and star formations

for 15, 30, and 60 robots, column-wise. Initial positions

and ﬁnal positions are represented by red and green colors,

respectively.

position. Therefore, robot mobility causes the topology to

dynamically change, potentially breaking links.

Connectivity maintenance is a supervisory control that

blocks disconnecting action from a primary controller that

pursues the primary goal of the swarm. In [4] a control bar-

rier function based controller minimally tweaks the primary

controller’s command such that connectivity is guaranteed.

We propose a set of operations to transform a spanning

tree topology into any other spanning tree topology using

only local, connectivity-aware operations which require data

from immediate and 2-hop neighbors. Then the primary

controller can use these operations to have more ﬂexibility

when topology manipulation is required. Note that data is

not propagated from farther neighbors using decentralized

averaging techniques like [5]. Although similar local manip-

ulation operations have been proposed in the literature [6],

[7], [8], [9], this is the ﬁrst local complete set without using

any global index of connectivity, to the best of the authors’

knowledge.

arXiv:2210.00037v2 [cs.RO] 4 Oct 2022

II. RELATED WORK

The communication topology of a swarm can be ﬁxed

or vary throughout its mission. When enforcing a ﬁxed

topology, also known as local connectivity maintenance,

every initially existing link between robots is maintained

(e.g. by the use of virtual potential functions or control

barrier functions) by enforcing an inter-robot distance that

is smaller than the robots’ communication range [10]. Local

connectivity maintenance is a simple approach that requires

minimal communication overhead and velocity constraints,

but it restricts the relative mobility of two initially neigh-

boring robots and makes it impossible to change the global

topological properties of the swarm (e.g. consensus rate or

coverage). With topology manipulation, the connectivity of

the network must be taken into account either continuously

from start to end [11], [12], [13] or it has to be re-established

intermittently [14], [15].

Preserving connectivity has been an active research area,

this subject is relevant in achieving almost all cooperative

tasks in multi-robot and multi-agent systems such as ﬂocking

[16], [17], search and rescue [18], [19] and formation control

[20], [21].

Published works on continuous connectivity maintenance

can be classiﬁed into three main approaches:

•Local connectivity maintenance [22], [23], [24], which

designs the control plans to avoid any disconnection of

initially existing communication links;

•Global connectivity maintenance [25], [26], [11], [4],

where the breaking of communication links is allowed,

as long as the overall communication topology remains

connected. Global connectivity maintenance is more

ﬂexible: it allows reconﬁguring the network’s graph to

any possible connected graph with the same number

of vertices. The criterion for allowing an edge discon-

nection is estimated or calculated based on a global

index which requires complete information over the

graph. In the decentralized version of this approach

interactions are local, such that iterative distributed

local averaging or consecutive local broadcast is used

to collect information in order to estimate this global

index.

•Connectivity-aware local topology manipulation opera-

tions: these methods are enhancing the local connec-

tivity maintenance method by performing local topol-

ogy manipulations while maintaining connectivity. A

node permutation method to locally swap neighbors

is proposed in [8]. A chained swarm relay method to

provide maximum coverage from a ground station is

investigated in [7]. A logical tree acts as a communica-

tion backbone in [9] where two topology manipulation

operations called outward and inward are utilized to add

robots to this backbone tree until they reach predeﬁned

targets. However, these methods do not provide the same

ﬂexibility compared to global connectivity maintenance

methods.

From the literature on theoretical distributed dynamic

networks, an approach [27] similar to our star formation

algorithm is proposed for reconﬁgurable robots. In [28] the

authors propose the use of rotation and slide operations

which are similar to our to be deﬁned leaﬁzation and leaf

transfer operations for reconﬁgurable robots arranged in 2-

dimensional grids. They have shown these two operations are

universal in a centralized mode as the operations can make

changes to the topology in the x and y axes respectively.

They also propose a line formation algorithm that unlike our

method requires global information.

In this paper, we investigate the possibility of deﬁning

connectivity-aware local topology manipulation operations

in such a way as to provide the same ﬂexibility as with

global methods. We demonstrate that there is a complete

set of operations that can manipulate the swarm’s topology

in any possible connected form.

The main reason for developing connectivity-aware local

topology manipulation operations is the fact that the de-

centralized estimation of global connectivity indices is not

scalable and it is very sensitive to noise [7], [10]. Despite

the ﬂexibility that a global method provides, the convergence

time needed to estimate a global index restricts the speed

of robots [10]. This phenomenon is caused by practical

constraints like ﬁnite bandwidth and/or communication de-

lays. The superiority of global methods in some works [29],

[11] is due to assuming continuous, inﬁnite bandwidth and

cost-less communication. It is worth noting that in a global

method communications are on (𝑁−1)−hop path, in the

worst case. Thus, it can have a signiﬁcant impact on a large-

scale network. However, in a local method communication

paths are one or two hops. Therefore, the communication

delay is insigniﬁcant and can be ignored. In a real-world

situation, there is a trade-oﬀ between graph ﬂexibility and

the maximum allowed speed of robots.

The algebraic connectivity which is the second smallest

eigenvalue 𝜆2of the Laplacian matrix 𝐿, associated with

the communication graph, is a connectivity index that is

employed to indicate the connectivity of the network. 𝜆2is

shown to be a concave function of the Laplacian matrix [30].

Therefore, optimization approaches to calculating the control

inputs had been proposed in order to maximize it [31], [32].

However, calculating the eigenvalues of a matrix requires full

knowledge of the matrix. A centralized approach to calculate

eigenvalues and eigenvectors is used in [32]. Power iteration

is used in designing a decentralized algorithm to estimate

algebraic connectivity in [33]. Based on this decentralized

estimator, several global connectivity maintenance methods

to apply control inputs such that 𝜆2is preserved positive

are proposed [11], [29], [34]. A connectivity maintenance

supervisor considering time delays using control barrier

functions to preserve 𝜆2more than a threshold is proposed

in [35].

Another approach to global connectivity maintenance is by

designing a controller such that only links with an alternative

𝑘−hop path are allowed to disconnect. The length of a path

in a graph with 𝑁nodes is less than 𝑁−1. Thus, global

connectivity of the network could be maintained with 𝑘=

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

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

10 玖币 0人已下载

立即下载

摘要：

ACompleteSetofConnectivity-awareLocalTopologyManipulationOperationsforRobotSwarmsKoreshKhateri*1,KarthikSoma*,MahdiPourgholi2,MohsenMontazeri,LorenzoSabattini3andGiovanniBeltrame1AbstractThetopologyofaroboticswarmaectstheconvergencespeedofconsensusandthemobilityoftherobots.Inthispaper,weprovetheex...

展开>> 收起<<

A Complete Set of Connectivity-aware Local Topology Manipulation Operations for Robot Swarms Koresh Khateri1 Karthik Soma Mahdi Pourgholi2 Mohsen Montazeri.pdf

共8页,预览2页

还剩页未读，继续阅读

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

A Complete Set of Connectivity-aware Local Topology Manipulation Operations for Robot Swarms Koresh Khateri1 Karthik Soma Mahdi Pourgholi2 Mohsen Montazeri

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: