Optimal Persistent Monitoring of Mobile Targets in One Dimension Jonas Hall1 Sean Andersson12 Christos G. Cassandras13 Abstract This work shows the existence of opti-

2025-04-29 0 0 1.95MB 8 页 10玖币

侵权投诉

Optimal Persistent Monitoring of Mobile Targets in One Dimension

Jonas Hall1, Sean Andersson1,2, Christos G. Cassandras1,3

Abstract— This work shows the existence of opti-

mal control laws for persistent monitoring of mobile

targets in a one-dimensional mission space and derives

explicit solutions. The underlying performance metric

consists of minimizing the total uncertainty accumu-

lated over a ﬁnite mission time. We ﬁrst demon-

strate that the corresponding optimal control problem

can be reduced to a ﬁnite-dimensional optimization

problem, and then establish existence of an optimal

solution. Motivated by this result, we construct a

parametric reformulation for which an event based

gradient descent method is utilized with the goal of

deriving (locally optimal) solutions. We additionally

provide a more practical parameterization that has

attractive properties such as simplicity, ﬂexibility,

and robustness. Both parameterizations are validated

through simulation.

I. Introduction

In persistent monitoring problems, a team of au-

tonomous agents is tasked to monitor a given envi-

ronment. The problem is closely related to coverage

control [1], the key diﬀerence being that the environment

is assumed to change dynamically, so that all points of

interest must be revisited persistently. The problem has

received a lot of attention over the last decade due to

its broad applicability across a range of applications,

including environmental monitoring [2], data harvest-

ing [3], and particle tracking [4]. Persistent monitoring

problems are notoriously diﬃcult to solve because of

highly non-convex and non-smooth costs and dynamics

along with the computational complexity due to the

problem’s combinatorial nature.

In this paper we consider the persistent monitoring

problem applied to a ﬁnite number of targets in a

one-dimensional connected mission space, similar to the

formulations in [5], [6]. One-dimensional mission spaces

are common in applications that involve rivers, roads in

a transportation network, or power lines, to name a few.

Unlike previous work, however, in addition to an internal

state describing a measure of uncertainty, we allow the

targets themselves to be mobile in the mission space. The

control objective considered is the minimization of the

overall uncertainty over a ﬁnite mission time. The uncer-

tainty dynamics considered in this work can be viewed

This work was supported in part by NSF under grants ECCS-

1931600, DMS-1664644, CNS-1645681, CNS-2149511, by AFOSR

under FA9550-19-1-0158, by ARPA-E under DE-AR0001282, by

NIH under 1R01GM117039-01A1, and by the MathWorks.

1Division of Systems Engineering, Boston University, USA

2Division of Mechanical Engineering, Boston University, USA

3Department of Electrical and Computer Engineering

{hallj, sanderss, cgc}@bu.edu

as a ﬂow model with constant input ﬂow, whereas the

output ﬂow depends on the target-agent distance. This

model is commonly used in the literature [5], [7], though

other dynamics have been discussed as well. For example,

in [8], the authors consider internal states with arbitrary

linear time-invariant dynamics, with a control applied

only when an agent is monitoring the target. In other

applications, such as environmental monitoring tasks, the

internal state is modeled as a Gaussian random ﬁeld [9].

Similarly, the literature contains various performance

metrics, e.g., that of maximizing the number of observed

events [2], minimizing the inter-observation time [10], or

minimizing estimation errors [9].

The persistent monitoring problem is often split into

a higher and lower level. The higher level consists of

path planning and scheduling target visiting sequences.

Lan and Schwager proposed the use of rapidly-exploring

random cycles in order to ﬁnd an optimal periodic trajec-

tory [9]. Other formulations abstract the mission space to

a graph, where each node represents a region of interest

and the edges capture the travel times [10], [11]. The

graph-based formulation was further generalized in [12],

in which targets were grouped into clusters and only a

single target within each cluster must be visited. Due to

the combinatorial nature of the scheduling task, the use

of mixed-integer optimization is natural [13], and its sim-

ilarity to the Traveling Salesman Problem has motivated

solving the higher level scheduler with such methods [14].

On the lower level, the problem consists of optimizing

the agents’ motion control, either along a given path, or

in order to realize a given schedule. For example, in [5]

and [15], the authors optimize agent velocities along a

given path, while in [16] a conﬁguration-based solution

is sought such that each point on a given path is revisited

with a constant frequency.

The contribution of this paper consists of advances

in the one-dimensional persistent monitoring problem of

mobile targets. In particular, we prove that the con-

sidered inﬁnite-dimensional Optimal Control Problem

(OCP) can be reduced to an optimization problem of

ﬁnite dimension, and that the OCP always admits a

solution. Though similar results can be found for static

targets, we provide novel (to the best of the authors’

knowledge) results for mobile targets. Additionally, we

provide two parametric reformulations and utilize the

Inﬁnitesimal Perturbation Analysis (IPA) method [17]

in order to compute gradients and solve the parametric

optimization problem locally.

The remainder of this paper is structured as follows.

arXiv:2210.01294v1 [math.OC] 4 Oct 2022

Sec. II introduces the problem in detail and establishes

the OCP (4). In Sec. III, we show how the problem can

be reduced to a ﬁnite-dimensional optimization problem.

Two parametric formulations are provided and compared

in Sec. IV. By applying the IPA calculus, we describe how

perturbations of the parameters aﬀect the cost function

in Sec. V. We also compare the parameterizations in

numerical experiments in Sec. VI. Sec. VII concludes the

paper and outlines ideas for future work.

II. Problem Formulation

Our problem formulation builds upon the foundation

of [6], [7], extending it to include mobile targets. Let S=

Rbe the work space in which we consider the persistent

monitoring problem over a ﬁnite time interval [0, T ].

We introduce a set of mobile agents A={1,2, . . . , N},

and denote the position of agent j∈ A by sj(t)∈ S.

We assume that the agents follow ﬁrst-order dynamics

˙sj(t) = uj(t), where each ujbelongs to the admissible

control set U={[0, T ]→[−1,1]}, and the initial

position sj(0) ∈ S is given. In addition to the agents,

there is a set of mobile targets T={1,2, . . . , M}, and

we denote by ϑi(t) and ˙

ϑi(t) the position and velocity of

i∈ T at t∈[0, T ]. The monitoring function of agent j

for target iis given by

pij (ϑi(t), sj(t)) = max 0,1−|ϑi(t)−sj(t)|

rj,(1)

where rj>0 is the sensing range of agent j. The joint

monitoring function of target ifrom all agents is then

P(ϑi(t), s(t)) = 1 −Y

j∈A

(1 −pij (ϑi(t), sj(t))) .(2)

The question remains of what is being monitored. We

associate each target with an internal state Ri(t)≥0

describing a measure of uncertainty. This state is as-

sumed to grow with a constant rate of Ai>0 when

not monitored, and to change with a dynamic rate of

Ai−BiP(ϑi(t), s(t)) for a given Bi> Aiotherwise.

To ensure that the uncertainty remains nonnegative, we

limit the uncertainty reduction for targets in the set

Z(t) = {i∈ T | Ri(t) = 0 and Ai< BiP(ϑi(t), s(t))}.

Thus, the uncertainty dynamics are captured by

fRi(t) = (0,if i∈ Z(t),

Ai−BiP(ϑi(t), s(t)),otherwise.(3)

The goal of the persistent monitoring problem is to

minimize the overall uncertainty, i.e., we seek a control

policy which solves the OCP

minimize

u∈ UNJ(u) = 1

TZT

i∈T

Ri(t)dt (4a)

subject to ˙s(t) = u(t),˙

R(t) = fR(t).(4b)

Note that the function (3) depends on time only

through s(t), R(t), and ϑ(t). However, to keep notation

simple, we neglect the explicit dependence on the states,

noting only that it is a function of time. This convention

will be used throughout the paper.

Remark 1: The choice of the monitoring function is

not restricted to (1). Any monitoring function can be

chosen, as long as it a) has compact support, and b) is

monotonically increasing with the distance between its

arguments. Similarly, the results in this paper directly ex-

tend to other joint monitoring functions, as long as they

are monotonically increasing with each of the individual

monitoring functions, e.g., maxj∈A pij (ϑi(t), sj(t)).

III. Optimal Control Characterization

As in previous work [6], a standard Hamiltonian anal-

ysis can be applied to (4) to reveal that the optimal

control can be expressed in a parametric form. To better

understand the structure of the problem, however, here

we show the existence of such a parametric reformulation

directly. In order to prove the main result in Thm 1

below, we ﬁrst show that any control law can be adapted

to one of the form given in (5) without increasing the

cost. Applying this result repeatedly shows that any

control can be replaced by one which can be partitioned

into a ﬁnite number of intervals during which the control

is either a) constant and maximal, or b) equal to the

velocity of a target. From this we conclude that there

exists a compact parameter space, with which we can

ultimately show the existence of a parametrically repre-

sented optimal control. These theoretical results rely on

the following assumptions for the motions of the targets.

Assumption 1: For all t∈[0, T ], i, i16=i2∈ T , we

assume that (i) target velocities are no larger than the

maximal speed of the agents, i.e., their absolute velocities

are bounded by one, and (ii) agents never sense two

targets at the same time, i.e., there exists ∆min >0 such

that |ϑi1(t)−ϑi2(t)| ≥ 2 maxj∈A{rj}+ ∆min.

The ﬁrst assumption is fundamental, whereas the

second one is of a technical nature, without which it

becomes increasingly diﬃcult to characterize the optimal

control. However, in Sec. VI we show that the considered

parameterizations are adaptable to simultaneous sensing

scenarios. Similarly, if a target’s velocity exceeds the

target control bounds, then the given parameterization

with bounded controls provides a heuristic for the more

general case. Our ﬁrst lemma provides a characterization

of the optimal control over a ﬁxed interval. Before we

begin, let us denote by ‘sgn’ the sign function that maps

all negative real numbers to negative one, zero to zero,

and all positive real numbers to one.

Lemma 1: Let (u, s) be any feasible control-trajectory

pair. Consider an interval (t1, t2) over which the agent

j∈ A only ever senses one target i∈ T . Then, there

exist ˇ

t, ˆ

t∈[t1, t2] such that the modiﬁed control law

j(t) = 









uj(t),if t /∈(t1, t2),

sgn (ϑi(t1)−sj(t1)) ,if t∈(t1,ˇ

t),

ϑi(t),if t∈(ˇ

t, ˆ

t),

sgn (sj(t2)−ϑi(t2)) ,if t∈(ˆ

t, t2),

(5)

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

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

10 玖币 0人已下载

立即下载

摘要：

OptimalPersistentMonitoringofMobileTargetsinOneDimensionJonasHall1,SeanAndersson1;2,ChristosG.Cassandras1;3Abstract|Thisworkshowstheexistenceofopti-malcontrollawsforpersistentmonitoringofmobiletargetsinaone-dimensionalmissionspaceandderivesexplicitsolutions.Theunderlyingperformancemetricconsistsofmi...

展开>> 收起<<

Optimal Persistent Monitoring of Mobile Targets in One Dimension Jonas Hall1 Sean Andersson12 Christos G. Cassandras13 Abstract This work shows the existence of opti-.pdf

共8页,预览2页

还剩页未读，继续阅读

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

Optimal Persistent Monitoring of Mobile Targets in One Dimension Jonas Hall1 Sean Andersson12 Christos G. Cassandras13 Abstract This work shows the existence of opti-

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: