Delivery to Safety with Two Cooperating Robots Jared Coleman2 Evangelos Kranakis3 Danny Krizanc4 and Oscar_2

2025-05-06 0 0 550.91KB 27 页 10玖币

侵权投诉

Delivery to Safety with Two Cooperating

Robots?

Jared Coleman2, Evangelos Kranakis3, Danny Krizanc4, and Oscar

Morales-Ponce1

1Department of Computer Engineering and Computer Science, California State

University, Long Beach, Long Beach, CA. Oscar.MoralesPonce@csulb.edu

2Department of Computer Science, University of Southern California, Los Angeles,

CA, USA. jaredcol@usc.edu

3School of Computer Science, Carleton University, Ottawa, Ontario, Canada.

kranakis@scs.carleton.ca

Department of Mathematics & Computer Science, Wesleyan University, Middletown

CT, USA. dkrizanc@wesleyan.edu

Abstract.

Two cooperating, autonomous mobile robots with arbitrary

nonzero max speeds are placed at arbitrary initial positions in the plane.

A remotely detonated bomb is discovered at some source location and

must be moved to a safe distance away from its initial location as quickly

as possible. In the Bomb Squad problem, the robots cooperate by com-

municating face-to-face in order to pick up the bomb from the source

and carry it away to the boundary of a disk centered at the source in the

shortest possible time. The goal is to specify trajectories which deﬁne

the robots’ paths from start to ﬁnish and their meeting points which

enable face-to-face collaboration by exchanging information and passing

the bomb from robot to robot.

We design algorithms reﬂecting the robots’ knowledge about orientation

and each other’s speed and location. In the oﬄine case, we design an

optimal algorithm. For the limited knowledge cases, we provide online

algorithms which consider robots’ level of agreement on orientation as

per

OneAxis

and

NoAxis

models, and knowledge of the boundary as per

Visible, Discoverable,

and

Invisible

. In all cases, we provide upper

and lower bounds for the competitive ratios of the online problems.

Keywords:

Boundary

Mobile Robots

Delivery

Cooperative

Com-

petitive Ratio

1 Introduction

A remotely detonated bomb is located at the center of some critical zone. Since the

time of detonation is unknown, the bomb must be removed as quickly as possible

from the critical zone by two autonomous mobile robots. How can these robots,

each with their own speeds and initial location, collaborate to carry the bomb

?Research supported in part by NSERC Discovery grant

arXiv:2210.04080v2 [cs.DC] 11 Oct 2022

2 J. Coleman et al.

out of the critical zone as quickly as possible? We assume the bomb is initially

located at a point

(the source) and must be transported at least distance

(called the critical distance) away from the source. The critical distance deﬁnes

a disk centered at

of radius

. Each robot has its own maximum speed and

the bomb can be passed from robot to robot in a face-to-face communication

exchange. We refer to this as the Bomb Squad problem. The perimeter of the disk

centered at

and radius

is also called the boundary and encloses the critical

zone which must be rid of the bomb.

In the sequel, we study various versions of the Bomb Squad problem which

depend on what knowledge the collaborating robots have regarding the location

of the other robot and the boundary. We are interested in designing both oﬄine

(full knowledge) and online (limited knowledge) algorithms that describe the

trajectories and collaboration of the participating robots.

1.1 Model, Notation, and Preliminaries

There are two autonomous mobile robots,

and

, with maximum speeds

and

initially placed in the plane distances

and

from the source, respectively.

We use the standard mobility model for the robots. At any time, they may stop

and start, change direction/speed, and carry the bomb when they decide to do so.

A robot trajectory is a continuous function

: [0

, T

]

→R2

such that

(

) is the

location of the robot at time

and

is the duration of a robot’s trajectory. If the

robot’s speed cannot exceed

then

(

)

−f

(

)

k2≤v|t−t0|

, for all 0

≤t, t0≤T

where k·k2denotes the Euclidean norm in the plane R2.

Robots may collect information as they traverse their trajectories. Moreover,

they may exchange information only when they are collocated (also known as

F2F model). When collocated, they may compare their speeds and decide which

robot is faster. They can recognize the bomb initially placed at location

and

can carry it around and pass it from robot to robot without their speed being

aﬀected.

We assume robots have a common unit of distance. We consider both the

oﬄine and online settings. In the oﬄine setting, all information regarding the

robots (their initial positions and speeds) is available and an algorithm provides

robot trajectories and a sequence of robot meetings that relay the bomb from

the source to the boundary in optimal time.

In the online setting, a robot has limited knowledge of the other robot’s

location and the critical distance. We consider both

OneAxis

and

NoAxis

(or

Disoriented

) models (see [

]). In the

OneAxis

model robots agree on a single

axis and direction (i.e. North). In the

NoAxis

model, we say robots are disoriented

and do not agree on any axis or direction. With respect to knowledge of the

critical distance, we consider three models:

1. VisibleBoundary

: the boundary is always visible and thus the critical dis-

tance Dis known by all robots.

2. DiscoverableBoundary

: the boundary (and thus the critical distance) is

not known ahead of time but is “discoverable”. Robots can discover the

Delivery to Safety with Two Cooperating Robots 3

boundary (and the critical distance) by visiting any point on the boundary

or by encountering another robot which has already discovered it.

3. InvisibleBoundary

: the boundary is completely invisible and robots have no

knowledge of whether or not they’ve already visited a point on the boundary.

Each of these models has intuitive inspiration from the bomb-squad scenario. The

VisibleBoundary

model considers the situation where a safe distance is known

ahead of time, while the

DiscoverableBoundary

model considers a situation

where a boundary — physical (i.e. a fence or a wall) or abstract (i.e. a border,

patrol line, maximum communication distance) — must be discovered by the

robots. Finally, the

InvisibleBoundary

model considers the situation where a

safe distance is not known by the robots (i.e. they don’t know the detonation

radius of the bomb). In this case, the goal is to deliver the bomb to an unknown

radius as quickly as possible. Interestingly, each of these models yields unique

algorithms with diﬀerent competitive ratios.

In all of our algorithms, both robots start at the same time from arbitrary

locations in the plane. The delivery time

(

) of an algorithm

solving the

Bomb Squad problem is the time it takes the algorithm

to deliver the bomb

to the boundary for an instance

of the problem (a source location

, critical

distance

, and robots’ initial positions and maximum speeds). If

Topt

(

) is the

optimal time of an oﬄine algorithm for the same instance

, then the competitive

ratio of an online algorithm

is deﬁned by the ratio

CRA

supITA

(

)

/Topt

(

is a class of algorithms solving an online version of the Bomb Squad problem,

then its competitive ratio is deﬁned by

CRA

infA∈A CRA

. Usually, the

subscripts will be omitted since the online version of the problem will be easily

understood from the context.

In proving upper bounds on the competitive ratio, if the faster robot cannot

arrive at

before the slow robot then we may restrict our attention to the case

where the slow robot starts at the source. We state this useful claim as a lemma.

Lemma 1.1.

Consider any online algorithm solving an online version of the

Bomb Squad problem. Assume that the faster robot cannot arrive at

before the

slow robot does. If

is an upper bound on the competitive ratio of the algorithm

for all instances in which the slow robot starts at the source, then

is also an

upper bound on the competitive ratio for that algorithm.

Proof.

Consider any online algorithm

solving the given optimization problem.

Recall that the robots can communicate only F2F. Let

be the time it takes the

slow robot to move from its starting position to the source

. The hypothesis of

the lemma implies after time

has passed the faster robot cannot arrive at the

source. Therefore algorithm

is split into two parts: the ﬁrst part takes time

and the second part is an algorithm

that assumes that the slow robot started

at S. Now observe that

CRA=TA

TOpt

=t+TAt

t+TOptt≤TAt

TOptt≤c,

where

Optt

is the optimal algorithm after time

has passed and the slow robot

starts at S.

4 J. Coleman et al.

1.2 Related work

The Bomb Squad problem is closely related to the message delivery problem

with a set of robots. In that problem, the source and destination are predeﬁned

and robots jointly work to deliver the message. Two diﬀerent objective functions

have been studied. The ﬁrst assumes that the robots have limited battery and

consequently the objective function is to minimize the maximum movement

(minmax). The second is to minimize the time to deliver the message. Anaya

et al. [

] study a more general minmax problem where the message must be

delivered to many destinations. The authors show that the decision problem is

NP-hard and provide a 2 approximation algorithm.

Chalopin et al. [

] study the minmax problem on a line and show that the

decision problem is NP-Complete for instances where all input values are integers.

The authors also provide an algorithm for delivering the message that runs in

(

d2·n1+4 log d

) time where

is the distance between the source and destination

for the general case. Coleman et al. [

] study the broadcast and unicast versions

of the problem on a line and present optimal oﬄine algorithms and online

algorithms with optimal constant competitive ratio. In [

] Czyzowicz et al. study

the problem in a weighted graph and show that the problem is NP-Complete.

They also show that by allowing robots to exchange energy, the problem can be

solved in polynomial time. Carvalho et al. [

] also study the problem in weighted

graphs. They provide an oﬄine algorithm that runs in

(

kn log n

) time

where

is the number of robots,

is the number of nodes, and

the number of

edges.

More recently, Coleman et al. [

] studied the point-to-point delivery problem

on the plane and gave an optimal oﬄine algorithm for two robots as well as

approximation oﬄine algorithms and online algorithms with constant competitive

ratio. The delivery problem diﬀers signiﬁcantly from the problem studied in

our current paper, where the goal is to reach any point on a given boundary

(namely the perimeter of a disk centered at the source) as opposed to a speciﬁc

destination.

The delivery problem studied in our paper focuses on the knowledge the

robots have about each other as well as the environment. To this end we design

algorithms for the

OneAxis

and

NoAxis

models. In particular, in the latter model

and based on the knowledge the robots have in Subsection 4.3 one has to design a

search algorithm that makes the robots perform a “zigzag” procedure in order to

collect appropriate information and pass the bomb to the faster robot, if feasible,

that will eventually deliver the bomb to the boundary. This has similarities to the

well-known linear search algorithms proposed by Baeza-Yates et al. [

], Beck [

]

and Bellman [

], Ahlswede et al. [

], as well as Alpern et al. [

]. However, search

in the previously given research works is based only on one robot while in our

case we have two collaborating robots with incomplete information about the

environment.

Delivery to Safety with Two Cooperating Robots 5

1.3 Outline and results of the paper

In this paper, we design and analyze algorithms for the Bomb Squad problem

with two cooperating robots. In the oﬄine case, we design an optimal algorithm

that assumes robots have knowledge of their own and each other’s location but

does not require knowledge of each other’s speed. For the online case Table 1

Table 1.

Upper and lower bounds on the competitive ratio of online algorithms for

two cooperating robots in the

OneAxis

and

NoAxis

models for

Visible, Discoverable

and Invisible Boundary:

Axis Model Boundary Model Upper Bound Lower Bound Section

OneAxis All 1

75 + 4√2≈1.5224 1.48102 3

NoAxis Visible 1 + √2 1 + √2 4.1

NoAxis Discoverable 15

43 4.2

NoAxis Invisible 7+√17

22 + √5 4.3

displays upper and lower bounds on the competitive ratio for the

OneAxis

and

NoAxis

models, and for

Visible, Discoverable

, and

Invisible

Boundary as

well as the speciﬁc (sub)section where the results are proved. Section 2 presents

an optimal oﬄine algorithm, Section 3 presents an online algorithm for the

OneAxis

model, while Section 4 includes the results of the three Subsections for

the

NoAxis

model. There are many interesting open problems and in Section 5

we summarize the results and discuss potential extensions and alternatives.

2 Optimal Oﬄine Algorithm

Our problem may be solved optimally using Algorithm 1.

Algorithm 1 Oﬄine Delivery Algorithm for Two Robots

1: move toward S

2: if arrived at Sthen

3: pick up the bomb

4: move in direction of other robot

5: else if encountered other robot with bomb and other robot is slower then

6: take the bomb from other robot

7: move away from Stoward boundary

Theorem 2.1.

For any two robots

r1, r2

such that

v1≤v2

, the oﬄine Algo-

rithm 1 is optimal in that it delivers the bomb to the perimeter of the circle

centered at Swith radius Din minimum time

min d1+D

,d2+D

,D−d2

+ 2d1+d2

v1+v2(1)

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

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

10 玖币 0人已下载

立即下载

摘要：

DeliverytoSafetywithTwoCooperatingRobots?JaredColeman2,EvangelosKranakis3,DannyKrizanc4,andOscarMorales-Ponce11DepartmentofComputerEngineeringandComputerScience,CaliforniaStateUniversity,LongBeach,LongBeach,CA.Oscar.MoralesPonce@csulb.edu2DepartmentofComputerScience,UniversityofSouthernCalifornia,Lo...

展开>> 收起<<

Delivery to Safety with Two Cooperating Robots Jared Coleman2 Evangelos Kranakis3 Danny Krizanc4 and Oscar_2.pdf

共27页,预览5页

还剩页未读，继续阅读

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

Delivery to Safety with Two Cooperating Robots Jared Coleman2 Evangelos Kranakis3 Danny Krizanc4 and Oscar_2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: