Non-Submodular Maximization via the Greedy Algorithm and the Effects of Limited Information in Multi-Agent Execution Benjamin Biggs

2025-05-02 0 0 431.34KB 8 页 10玖币

侵权投诉

Non-Submodular Maximization via the Greedy Algorithm and the

Effects of Limited Information in Multi-Agent Execution

Benjamin Biggs

Virginia Tech

babiggs@vt.edu

James McMahon

US Naval Research Laboratory

Acoustics Division, Code 7130

james.mcmahon@nrl.navy.mil

Philip Baldoni

US Naval Research Laboratory

Acoustics Division, Code 7130

philip.baldoni@nrl.navy.mil

Daniel J. Stilwell

Virginia Tech

stilwell@vt.edu

Abstract—We provide theoretical bounds on the worst case

performance of the greedy algorithm in seeking to maximize

a normalized, monotone, but not necessarily submodular ob-

jective function under a simple partition matroid constraint.

We also provide worst case bounds on the performance of

the greedy algorithm in the case that limited information is

available at each planning step. We speciﬁcally consider limited

information as a result of unreliable communications during

distributed execution of the greedy algorithm. We utilize notions

of curvature for normalized, monotone set functions to develop

the bounds provided in this work. To demonstrate the value

of the bounds provided in this work, we analyze a variant of

the beneﬁt of search objective function and show, using real-

world data collected by an autonomous underwater vehicle,

that theoretical approximation guarantees are achieved despite

non-submodularity of the objective function.

I. INTRODUCTION

In general, the problem of planning search paths that

seek to maximize a general objective function is NP-hard.

One simple method of addressing the general infeasibility of

planning optimal paths for a team of search agents is to utilize

the greedy algorithm [1] wherein an ordering is assigned to

the set of search agents and each agent plans a path for

itself while accounting for the paths of preceding agents.

We seek to provide theoretical approximation guarantees

for the greedy algorithm in seeking to maximize a non-

submodular objective function where planning at each step of

the greedy algorithm is potentially suboptimal. Furthermore,

we consider the effect of unreliable communications during

distributed execution of the greedy algorithm which limits the

information available to search agents and seek to provide

approximation guarantees for the greedy algorithm with

limited information as well.

The greedy algorithm has received signiﬁcant attention

because of its practical simplicity. In addition to its ease

of implementation, the greedy algorithm has been shown

to yield results with high-quality approximation guarantees

under a wide variety of constraints on the possible solutions

that the greedy algorithm may produce.

*This work was supported by the Ofﬁce of Naval Research via grants

N00014-18-1-2627, and N00014-19-1-2194. The work of J. McMahon and

P. Baldoni is supported by the Ofﬁce of Naval Research through the NRL

Base Program.

James McMahon and Phillip Baldoni are with the US Naval Research

Laboratory, Code 7130, Washington D.C., USA

Benjamin Biggs and Daniel Stilwell are with the Bradley Department of

Electrical and Computer Engineering, Virginia Tech, Blacksburg, VA, USA

It is shown in [2] that the greedy algorithm yields an

optimal solution given a modular objective function. The well

known 1/2lower bound is presented in [3] for the case of a

normalized, monotone, submodular objective function under

a general matroid constraint. The authors of [1] introduce a

notion of curvature for normalized, monotone, submodular

objective functions and use this curvature αc∈[0,1] to

provide an approximation guarantee of 1/(1 + αc)that is

equivalent to the bounds presented in [2] and [3] at the limits

of the curvature term (when αc= 0 or αc= 1) thus unifying

the results of [2] and [3]. It is shown in [4] that under a

uniform matroid constraint, the greedy algorithm yields an

improved bound of (1 −e−1)≈0.63 given a submodular

objective function. In [1], curvature is again used to further

improve this bound to (1 −e−αc)/αc.

The bounds of [3] and [4] have motivated the frequent use

of submodular objective functions such as mutual information

which is known to be submodular assuming measurements

are conditionally independent [5]. Further consideration of

approximation guarantees for the greedy algorithm in seeking

to maximize a non-submodular objective function has begun

only recently. We refer the reader to [6] for a more thorough

discussion of distinct types of non-submodular functions

and recent advancements. Important applications with corre-

sponding non-submodular objective functions include exper-

imental design, dictionary selection, and subset selection [6].

The work of [7] addresses visibility optimization in social

media. In this work, we address robotic search.

Contributions: In the ﬁrst contribution of this work, which

appears in Theorem 1, we provide suboptimality guarantees

for the greedy algorithm under a simple partition matroid

constraint where the objective function is normalized and

monotone, but not necessarily submodular. We discuss how

our novel bound generalizes and extends bounds provided in

earlier works with the additional consideration of generalized

curvature. In the second contribution of our work, which

appears in Theorem 2, we provide suboptimality guarantees

for the greedy algorithm with limited information extending

the work of [8], [9]. Our extensions include the consideration

of normalized, monotone, but not necessarily submodular

objective functions. Additionally, in each case we consider

that the greedy selection step is executed with bounded

suboptimality as in [10]. Finally, we illustrate the efﬁcacy of

arXiv:2210.09868v1 [eess.SY] 18 Oct 2022

our contributions with respect to a robotic search application.

Most closely related to the ﬁrst contribution of this work

are the results presented in [11] and [7] which show that

under a general matroid constraint the greedy algorithm

yields a constant approximation factor (1 −β)/(1 + (1 −β))

for normalized, monotone, but not necessarily submodular

objective functions where βis equivalent to the inverse gener-

alized curvature given in Deﬁnition 5 of our work. Our work

extends the bounds of [11], [7] by further considering the

generalized curvature given in Deﬁnition 4. Our contribution

given as Theorem 1 has a form very similar to that of the

bound presented in [12]. In contrast to [12] where the authors

consider the sum of submodular and supermodular func-

tions and utilize notions of curvature with respect to these

functions, we consider a general non-submodular objective

function. This is signiﬁcant because a decomposition of a

normalized monotone set function into a sum of submodular

and supermodular functions is not guaranteed to exist as

shown in Lemma 3.2 of [12]. Additionally, we consider that

the greedy selection step is potentially suboptimal as in [10]

further distinguishing our contribution.

Most closely related to the second contribution of this

work are the results in [8] and [9] where a generalized

greedy algorithm is presented that does not require complete

information regarding preceding decisions. Notably, the gen-

eralized greedy algorithm in [9] enjoys a worst-case approxi-

mation guarantee of 1/(1 + k∗(G)) under a partition matroid

constraint assuming a normalized, monotone, submodular

objective function. The term k∗(G)represents the fractional

clique cover number of the underlying communication graph

Gand is discussed in detail in [9]. We extend the work of

[9] by considering the curvature of the objective function

which is assumed to be normalized and monotone, but not

necessarily submodular.

Paper Overview: This paper is organized as follows.

Mathematical preliminaries are presented and discussed in

Section II. Properties of the objective function including

notions of curvature are presented in Section III. The primary

contributions of this work are presented in Section IV. The

beneﬁt of search objective function is presented in Section

V and properties of the objective function are analyzed in

Section VI. Conclusions are presented in Section VII. Proofs

are presented in the appendices.

II. MATHEMATICAL PRELIMINARIES

Let Vbe a ﬁnite ground set and let f: 2V7→ Rbe a set

function where 2Vdenotes the power set of V. Generally,

calligraphic font is used to denote sets. Exceptions should be

clear from context. We consider a team of Nagents given

as A={1, . . . , N}. In executing the greedy algorithm, each

agent iwill select an element xifrom the ground set Vin

an effort to maximize the objective function f.

When analyzing suboptimality of the greedy algorithm,

one often encounters matroids which are used to represent

constraints on the solutions produced by the greedy algo-

rithm. A matroid is deﬁned as follows.

Deﬁnition 1 (Matroid [13, Deﬁnition 39.1] ): Consider a

ﬁnite ground set V, and a non-empty collection of subsets of

V, denoted by I. Then, the pair (V,I)is called a matroid if

and only if the following conditions hold:

i ) for any set X ⊆ V such that X ∈ I, and for any set

Z ⊆ X , it holds Z ∈ I;

ii ) for any sets X,Z ⊆ V such that X,Z ∈ I and |X | <

|Z|, it holds that there exists an element z∈ Z \ X

such that X ∪ {z}∈I.

Matroids are used to represent abstract dependence. The set

Icontains all independent sets of V. A set x∈ I is called

maximal if there exists no v∈ V such that x∪ {v} ∈ I.

For example, any subset of the columns of a matrix are

either linearly independent or dependent. A matroid may

be constructed by allowing the columns of the matrix to

form the ground set Vand every combination of linearly

independent columns to form I. An excellent discussion

of matroids and their history is provided in [13]. Most

importantly for our purposes, matroids provide a construct to

represent constraints in planning. Two notable special types

of matroids are uniform matroids [1], [4], [14] and partition

matroids [9], [10], [15], [16], [17].

To analyze suboptimality bounds for the greedy algorithm,

we utilize the marginal reward.

Deﬁnition 2 (Marginal Reward): Given any sets S,Q⊆V

the marginal contribution of Sgiven Qis

∆(S|Q),f(S ∪ Q)−f(Q).(1)

We adopt notation for the marginal reward from [8] and [9]. It

may be useful to consider the marginal reward as the discrete

derivative of fas discussed in [15].

Note that given an arbitrarily ordered set S ⊆ V, the

reward attained by Smay be represented as the sum of the

marginal rewards for the elements of S. For example, given

S={s1, . . . , sM}, we have

f(S) =

i=1

∆({si}| ∪i−1

j=1 {sj})(2)

where ∪i−1

j=1{sj}is the empty set when i= 1. For conve-

nience, we use the subscript notation s1:i−1=∪i−1

j=1{sj}

to denote a subset of an ordered set. We also often use a

comma in place of the union operator, e.g. ∆(S|Q,Z) =

∆(S|Q ∪Z). Lastly, when representing a single element in a

set, we often drop the curly brace notation, e.g. ∆({si}|Q) =

∆(si|Q).

By (2), given sets S,Q⊆Vwith |S| =MSand |Q| =

MQand arbitrary orderings S={s1, . . . , sMS}and Q=

{q1, . . . , qMQ}we have

f(S,Q) = f(S) +

i=1

∆(qi|q1:i−1,S)(3)

f(S,Q) = f(Q) +

i=1

∆(si|s1:i−1,Q).(4)

For the case of informative path planning, let Xirepresents

the set of paths available to agent iand let V=∪i∈AXi. We

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

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

10 玖币 0人已下载

立即下载

摘要：

Non-SubmodularMaximizationviatheGreedyAlgorithmandtheEffectsofLimitedInformationinMulti-AgentExecutionBenjaminBiggsVirginiaTechbabiggs@vt.eduJamesMcMahonUSNavalResearchLaboratoryAcousticsDivision,Code7130james.mcmahon@nrl.navy.milPhilipBaldoniUSNavalResearchLaboratoryAcousticsDivision,Code7130philip...

展开>> 收起<<

Non-Submodular Maximization via the Greedy Algorithm and the Effects of Limited Information in Multi-Agent Execution Benjamin Biggs.pdf

共8页,预览2页

还剩页未读，继续阅读

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

Non-Submodular Maximization via the Greedy Algorithm and the Effects of Limited Information in Multi-Agent Execution Benjamin Biggs

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: