1 Cooperative Coverage with a Leader and a Wingmate in Communication-Constrained

2025-04-28 1 0 1MB 10 页 10玖币

侵权投诉

Cooperative Coverage with a Leader and a

Wingmate in Communication-Constrained

Environments

Sai Krishna Kanth Hari, Sivakumar Rathinam, Swaroop Darbha, David W. Casbeer

Abstract—We consider a mission framework in which two

unmanned vehicles (UVs), a leader and a wingmate, are re-

quired to provide cooperative coverage of an environment while

being within a short communication range. This framework

ﬁnds applications in underwater and/or military domains, where

certain constraints are imposed on communication by either

the application or the environment. An important objective of

missions within this framework is to minimize the total travel and

communication costs of the leader-wingmate duo. In this paper,

we propose and formulate the problem of ﬁnding routes for the

UVs that minimize the sum of their travel and communication

costs as a network optimization problem of the form of a

binary program (BP). The BP is computationally expensive,

with the time required to compute optimal solutions increasing

rapidly with the problem size. To address this challenge, here,

we propose two algorithms, an approximation algorithm and a

heuristic algorithm, to solve large-scale instances of the problem

swiftly. We demonstrate the effectiveness and the scalability of

these algorithms through an analysis of extensive numerical

simulations performed over 500 instances, with the number of

targets in the instances ranging from 6 to 100.

Index Terms—Cooperative Coverage, Path Planning, Coordi-

nation of Multiple Unmanned Vehicles, Communication Con-

straints, Leader Follower, Underwater Vehicles, Network Opti-

mization, Approximation Algorithm, Heuristic Algorithm

I. INTRODUCTION

We consider a mission framework in which two unmanned

vehicles (UVs), a leader and a wingmate, are required to

provide cooperative coverage of an environment while being

within a short communication range. This framework ﬁnds

applications in underwater and/or military domains, where

certain constraints are imposed on communication by either

the application or the environment. For example, consider

a military application in which UAVs must monitor an en-

vironment without being detected. Then, communication us-

ing directional antennas is preferred over transmitting omni-

directional signals, to reduce the chances of being detected.

Alternatively, consider underwater applications such as ocean

exploration or mine sweeping. Here, standard terrestrial modes

of communication are ineffective due to high attenuation rate

Sai Krishna Kanth Hari is with the Applied Mathematics and Plasma

Physics Division, Los Alamos National Laboratory, NM, 87544 (email:

hskkanth@gmail.com).

Sivakumar Rathinam and Swaroop Darbha are with the Department of

Mechanical Engineering, Texas A&M University, College Station, TX 77843.

David W. Casbeer is with the Autonomous Control Branch, Air Force

Research Laboratory, Wright-Patterson A.F.B., OH 45433.

Distribution Statement A: Approved for Public Release; Distribution is

Unlimited. PA# AFRL-2022-4269 and LA-UR-22-30345

of electromagnetic signals, and acoustic mode of communi-

cation, which is traditionally used underwater, is undesirable

due to a low data transfer date and high latency owing to

slow speed of sound in water. As an alternative, the usage

of optical signals with a low ﬁeld of view is preferred for

communication, as it offers high data rates and low latency.

In these applications, an unmanned vehicle is accompanied

by at least one other vehicle, to either protect and help each

other or simply add redundancy to the mission. The vehicles

are required to regularly communicate with each other to plan

for any unexpected challenges presented by the environment.

However, while communicating, the vehicles are required to

stay close to each other for multiple reasons. Firstly, staying

close to each other reduces the chances of the UVs and their

communicating signals being detected in military applications.

Secondly, in underwater applications, staying close helps in

keeping the optical signals in the low attenuation range. Lastly,

staying close reduces the distance required to be traveled by

the communicating signals and leads to a reduction of power

consumption associated with communication; consequently,

mission-critical tasks such as collecting data through sensors

and performing necessary on-board computations will have

more on-board power available. Therefore, we consider a

problem in which the objective is to route the vehicles such

that the combined cost of traveling and communicating is

minimized.

In this work, we assume that exactly two UVs are uti-

lized to accomplish the mission. The UVs are required to

provide a coverage of the environment by collecting data

from representative targets and cover each other by staying

close and communicating regularly. Such an assumption is

apt for missions in which stealthiness is key and swarming

the environment with UVs is undesirable. For convenience of

algorithmic development, we assume that the number of targets

in the environment is even, say 2m, and the travel times for the

UVs between the targets obey the triangle inequality. Then, we

propose the following mission implementation framework. At

the beginning of the mission, each UV is assigned a distinct set

of mtargets to visit and is speciﬁed the sequence in which the

targets must be visited. Then, the UVs coordinate their speeds

such that they reach their respective targets in the speciﬁed

sequences at the same time. Upon reaching the targets, the

UVs quickly exchange information using directional antennas

and immediately switch off their communication. Then, they

move on to visit the next target in their assigned sequence

and repeat the same process of communication until all the

arXiv:2210.02628v1 [cs.RO] 6 Oct 2022

targets are exhausted, and they return to their initial location.

To realize this framework of coordination and communication,

the following problem is of interest:

Determine the sets of targets assigned to each UV and the

sequence (feasible routes) in which the targets in the assigned

set must be visited by each UV such that the sum of the travel

and communication costs is minimized.

Solving this problem is the focus of this work. In this

paper, we assume that the cost of communication between

UVs present at two targets is nearly equal to the cost incurred

by the UVs to travel between the targets, and the travel cost

between two targets is proportional to the Euclidean distance

between the targets.

II. PROBLEM FORMULATION

We formulate the problem as a network optimization prob-

lem of the form of a Binary Program (BP). The targets

to be monitored and the travel and communication paths

between them are represented by a simple undirected graph

G= (V, E, c);Vis the set of vertices representing the

targets to be monitored, Eis the set of edges representing

the travel and communication paths between the targets, c(.),

the edge weights, represent the non-negative cost incurred by

the UVs to travel and communicate between the targets. Then,

a solution to the problem is a connected graph in which all the

vertices have a degree 3; the graph must contain edges that

translate to connected paths for each UV to its assigned set of

targets and communication links that accord the sequence in

which the targets are visited by the UVs.

The mathematical description of the BP that is used to

compute such a solution with the minimum travel and com-

munication costs is presented below.

A. Data

2m- Number of targets in the environment

c(i, j)- Travel/communication cost between targets iand j,

where (i, j)∈E

B. Variables

We use sets of binary variables to capture the vehicle’s

target assignment, and travel and communication paths. First,

the set of binary variables vi,∀i∈V, is used to indicate if

a target is assigned to the 1st UV, i.e., UV-1, or the 2nd UV,

i.e., UV-2.

vi=(1,if target iis assigned to UV-1;

0,otherwise.

Then, we use the set of variables xi,j to indicate whether

UV-1 is required to traverse a path (i, j)between targets i

and j, where i, j ∈V.

xi,j =(1,if edge (i, j)∈Eis traversed by UV-1;

0,otherwise.

Similarly, we use the set of variables yi,j to indicate

whether UV-2 is required to traverse a path (i, j)between

targets iand j, where i, j ∈V.

yi,j =(1,if edge (i, j)∈Eis traversed by UV-2;

0,otherwise.

Next, the set of variables zi,j is used to indicate whether

an edge (i, j), where (i, j)∈E, is utilized by the UVs for

communication at any point of time in the mission.

zi,j =(1,if edge (i, j)is used for communication;

0,otherwise.

Finally, we utilize the sets of variables ξi,j,l and ηi,k,l,

∀i, j ∈V, and l, k ∈V\ {i, j}, to ensure that the

communication links are chosen based on the sequence in

which the targets are visited by the UVs.

ξi,j,l =(1,if xi,j = 1 and zj,l = 1;

0,otherwise.

ηi,k,l=(1,if zi,k = 1 and yk,l = 1;

0,otherwise.

C. Constraints

Using these binary variables, the problem requirements can

be represented as mathematical constraints as follows.

1) Target Assignment: Each UV must be assigned exactly

mtargets. This is represented by Equation (1).

i∈V

vi=m(1)

2) Feasible Tours/Sequences: A UV can traverse between

two targets (along an edge with the targets as the endpoints)

only if both the targets are assigned to the UV. Constraints

(2)–(3) ensure that an edge, (i, j)∈E, is assigned to UV-1’s

tour only if targets iand jare both assigned to UV-1, and

constraints (4)–(5) ensure that an edge (i, j)is assigned to

UV-2’s tour only if both iand jare assigned to UV-2.

xi,j ≤vi,∀(i, j)∈E(2)

xi,j ≤vj,∀(i, j)∈E(3)

yi,j ≤1−vi,∀(i, j)∈E(4)

yi,j ≤1−vj,∀(i, j)∈E(5)

The purpose of constraints (6)–(7) is similar to that of (2)–

(5), as they ensure that a UV can only travel to targets that

are assigned to it.

i∈V\{j}

xi,j =vj,∀j∈V(6)

i∈V\{j}

yi,j = 1 −vj,∀j∈V(7)

Constraints (8) and (9) ensure that a UV arriving at a target

must also depart from the target.

i∈V\{j}

xi,j =X

l∈V\{j}

xj,l,∀j∈V(8)

i∈V\{j}

yi,j =X

l∈V\{j}

yj,l,∀j∈V(9)

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

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

10 玖币 0人已下载

立即下载

摘要：

1CooperativeCoveragewithaLeaderandaWingmateinCommunication-ConstrainedEnvironmentsSaiKrishnaKanthHari,SivakumarRathinam,SwaroopDarbha,DavidW.CasbeerAbstractWeconsideramissionframeworkinwhichtwounmannedvehicles(UVs),aleaderandawingmate,arere-quiredtoprovidecooperativecoverageofanenvironmentwhilebein...

展开>> 收起<<

1 Cooperative Coverage with a Leader and a Wingmate in Communication-Constrained.pdf

共10页,预览2页

还剩页未读，继续阅读

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

1 Cooperative Coverage with a Leader and a Wingmate in Communication-Constrained

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: