Distributed Differentially Private Control Synthesis for Multi-Agent Systems with Metric Temporal Logic Speciﬁcations Nasim Baharisangari and Zhe Xu

2025-04-27 0 0 603.28KB 9 页 10玖币

侵权投诉

Distributed Differentially Private Control Synthesis for Multi-Agent

Systems with Metric Temporal Logic Speciﬁcations

Nasim Baharisangari and Zhe Xu

Abstract— In this paper, we propose a distributed differ-

entially private receding horizon control (RHC) approach for

multi-agent systems (MAS) with metric temporal logic (MTL)

speciﬁcations. In the MAS considered in this paper, each agent

privatizes its sensitive information from other agents using a

differential privacy mechanism. In other words, each agent adds

privacy noise (e.g., Gaussian noise) to its output to maintain its

privacy and communicates its noisy output with its neighboring

agents. We deﬁne two types of MTL speciﬁcations for the

MAS: agent-level speciﬁcations and system-level speciﬁcations.

Agents should collaborate to satisfy the system-level MTL

speciﬁcations with a minimum probability while each agent

must satisfy its own agent-level MTL speciﬁcations at the same

time. In the proposed distributed RHC approach, each agent

communicates with its neighboring agents to acquire their noisy

outputs and calculates an estimate of the system-level trajectory.

Then each agent synthesizes its own control inputs such that

the system-level speciﬁcations are satisﬁed with a minimum

probability while the agent-level speciﬁcations are also satisﬁed.

In the proposed optimization formulation of RHC, we directly

incorporate Kalman ﬁlter equations to calculate the estimates

of the system-level trajectory, and we use mixed-integer linear

programming (MILP) to encode the MTL speciﬁcations as

optimization constraints. Finally, we implement the proposed

distributed RHC approach in a case study.

I. INTRODUCTION

In multi-agent systems (MAS), it is common that agents

collaborate to accomplish different types of system-level

tasks through communication with each other, where the

communication occurs among the agents that are neighbors

[1]. Distributed control of an MAS, in comparison with

centralized control has the advantages of scalability and

fast computing [2] [3] [4] [5]. Furthermore, the central-

ized control can be computationally expensive, and if the

central control unit fails, then the whole system may fail.

In comparison, distributed control has a better potential in

fault tolerance [6]. Distributed control has been used in

many applications such as mobile robots [7] and autonomous

underwater vehicles (AUVs) [8].

In an MAS, it is possible that while the agents are coop-

erating to satisfy system-level tasks through communication,

each agent should protect its sensitive information (e.g.,

actual position state) from its neighboring agents [9]. In such

situations, differential privacy can be employed to protect the

privacy of the agents in an MAS. Differential privacy ensures

that an adversary is not able to deduce an agent’s sensitive

information while allowing decision making on system level

[10] [11] [12]. For dynamical systems (e.g., multi-agent

Nasim Baharisangari and Zhe Xu are with the School for Engineering of

Matter, Transport and Energy, Arizona State University, Tempe, AZ 85287.

{nbaharis, xzhe1}@asu.edu (Corresponding author: Zhe Xu)

systems), differential privacy protects the privacy of each

agent by adding differential privacy noise (e.g., Gaussian

noise) to the trajectories containing sensitive information

such that an adversary is not able to deduce the privatized

trajectories [9].

Metric temporal logic (MTL) can be used to deﬁne differ-

ent complicated tasks for an MAS due to being expressive

and human-interpretable [13] [14]. MTL is one type of

temporal logics which is deﬁned over real-valued data in

discrete time domain [15]. In addition, MTL is amenable to

formal analysis, and these advantages make MTL a good

candidate to deﬁne complicated tasks, such as collision

avoidance [16], in the form of MTL formulas [17] [18] [19].

In the MAS considered in this paper, the agents collaborate

with each other to satisfy system-level tasks while protecting

their privacy and satisfying their own agent-level tasks at the

same time, where the tasks are deﬁned in the form of MTL

formulas and each agent incorporates differential privacy

to privatize its trajectory containing sensitive information.

For satisfying the system-level tasks, each agent calculates

an estimate of the system-level trajectory. First, each agent

communicates with its neighboring agents to acquire their

noisy outputs. Then, each agent employs Kalman ﬁlter to

compute the estimates of the states of its neighboring agents

and use the estimated information to estimate the system

trajectory. In the next step, each agent uses receding horizon

control (RHC) to synthesize control inputs for satisfying the

system-level tasks and the agent-level tasks.

Contributions: We summarize our contributions as follows.

(a) We propose a distributed differentially private receding

horizon control (RHC) formulation for an MAS which is

considered a stochastic dynamic system with MTL speciﬁca-

tions. (b) In the proposed approach, we directly incorporate

Kalman ﬁlter equations in the optimization formulation of

RHC to account for the uncertainties stemming from differ-

ential privacy. In the proposed optimization formulation, we

employ a one-step ahead predication of the noisy outputs to

be used in the Kalman ﬁlter equations. (c) In the proposed

distributed RHC, by assigning individual tasks in addition to

system-level tasks, we utilize a higher portion of the capacity

of each agent in accomplishing different tasks.

II. PRELIMINARIES

In this section, we explain the notations, deﬁnitions, and

concepts that we use in this paper. Table I shows the

important notations that we use in this section and the

following sections.

arXiv:2210.01759v1 [eess.SY] 4 Oct 2022

A. System Dynamics and Features of Multi-Agent Systems

In this paper, an MAS consisting of Zagents moves in

a bounded environment S⊆R∣D∣, where Zdenotes the set

of the agents in the MAS, Zdenotes the cardinality of Z,

and D={d1, d2, ..., d∣D∣}with Dbeing the cardinality of

the set D. We represent the system dynamics of this MAS

in the ﬁnite discrete time domain T={1,2, ..., τ}(where

τ∈N={1,2, ...}) with Eq. (1).

s[t]=As[t−1]+Bu[t−1],(1)

where s[t]=[(s1[t])T,(s2[t])T, ..., (s∣Z∣[t])T]Tis the

vector of the states of the agents in the MAS at time

step tand si[t]=[si,d1[t], si,d2[t], ..., si,d∣D∣[t]]T(where

i∈Z) denotes the state of agent iat time step t;u[t−

1]=[(u1[t−1])T,(u2[t−1])T, ..., (u∣Z∣[t−1])T]Tis the

vector of the control inputs at time step t−1and ui[t−1]=

[ui,d1[t−1], ui,d2[t−1], ..., ui,d∣D∣[t−1]]Tis the control input

vector of agent iat time step t−1, and Aand Bare Z×Z

diagonal time-invariant matrices. The dynamics equation of

agent ican be expressed as si[t]=Ai∗si[t−1]+Bi∗ui[t−

1], where si[t]∈Sand ui[t−1]∈U={uu∞≤umax}for

all i∈Zand for all t∈T, and Ai∗and Bi∗refer to the i-th

row of matrix Aand B, respectively.

Deﬁnition 1. We deﬁne the system-level trajectory ηas a

function η∶T→Sto denote evolution of the average of

the states of all the agents in the MAS within a ﬁnite time

horizon deﬁned in the discrete time domain Tand we deﬁne

η[t]∶=1

∣Z∣

∑

i=1

si[t]. We also deﬁne the agent-level trajectory

sias a function si∶T→Sto denote the evolution of the

state of each agent iwithin a ﬁnite time horizon deﬁned in

the discrete time domain T.

In this paper, we represent the topology of the MAS with

an undirected graph Gthat is time-invariant.

Deﬁnition 2. We denote an undirected graph by G=(C,E),

where C={c1, c2, ..., cnC}is a ﬁnite set of nodes, E=

{e1,2, e1,3, ..., e1,nE, e2,3, ..., enE−1,nE}is a ﬁnite set of edges,

and nC, nE∈N={1,2, ...}. In the set of edges E,ei,l

represents the edge that connects the nodes ciand cl.

Each node ciof the undirected graph Grepresents an agent

in the MAS. Each edge ei,l connecting the nodes iand l

represents the fact that agnets iand lare neighbors, i.e.,

agent iand lcommunicate with each other. Hereafter, we

denote the set of the neighboring agents of agent iwith Zi.

Also, we denote the adjacency matrix of the graph Gwith

B. Differential Privacy

In this subsection, we review the theoretical framework of

differential privacy that we use in this paper [20] [21] [9]. To

apply differential privacy to protect the sensitive information

of each agent, we use the “input perturbation” approach, i.e.,

each agent adds noise to its state and then shares its noisy

output with its neighboring agents. Before formalizing the

deﬁnition of differential privacy, we explain the preliminary

deﬁnitions and notations related to differential privacy.

For a trajectory κi=si[0], si[1], ..., si[t], ..., where

si[t]=κi[t]∈R∣D∣for all t, we use the `pnorm as

κi`p∶=∞

∑

t=1si[t]p

p

, where .pis the ordinary p-norm

on Rd(d∈N∪{0}), and we deﬁne the set `d

p∶={κisi[t]∈

Rd,κ`p<∞}. Then, we deﬁne the truncation operator PQ

over trajectories κias follows: PQ(κi)=si[t]if t≤Q; and

P(κi)=0, otherwise. Now, we deﬁne the set ˜

`∣D∣

2as the set

of sequences of vectors in R∣D∣whose ﬁnite truncations are

all in `∣D∣

2(p=2and d=D). In other words, κi∈˜

`∣D∣

2if

and only if PQ(κi)∈`∣D∣

2for all Q∈N.

Deﬁnition 3. (Adjacency) For a ﬁxed adjacency parameter

νi, the adjacency relation Aνi, for all κi, κ′

i∈˜

`∣D∣

2, is deﬁned

as Eq. (2).

Aνi(κi, κ′

i)=









1,if κi−κ′

i`2≤νi

0,otherwise.(2)

In other words, two trajectories generated by agent iare

adjacent if the `2distance between the two is less or equal

to νi. Differential privacy is expected to make agent i’s true

trajectory, denoted by κi, indistinguishable from all other

trajectories contained in an `2-ball of radius νicentred at

the true trajectory κi.

We use a probability space (Ω,F,P)in order to state a

formal deﬁnition for differential privacy for dynamical sys-

tems which speciﬁes the probabilistic guarantees of privacy.

For the formal deﬁnition of differential privacy mechanism

that we explain shortly, we assume that the outputs of the

mechanism is in ˜

2and uses a σ-algebra over ˜

2which is

denoted by Θq

2and the construction of Θq

2is explained in

[22].

Deﬁnition 4. ((i, δi)-Differential Privacy for Agent i)With

i>0and δi∈(0,1

2)for agent i, a mechanism M∶˜

`∣D∣

2×

Ω→˜

2is (i, δi)-differentially private if for all adjacent

trajectories κi, κ′

i∈˜

`∣D∣

2and for all S∈Θq

2, we have the

following (Eq. (3)).

P[M(κi)∈S]≤eiP[M(κ′

i)∈S]+δi(3)

At each time step t, each agent ioutputs the value Ci∗yi[t],

where Ci∗is the i-th row of the Z×Ztime-invariant

diagonal matrix C. At time step t, for protecting the privacy

of agent i, noise must be added to its output yi[t]so an

adversary can not infer agent i’s trajectory κi[t]from its

output yi[t]. Calibrating the level of noise is done using

“sensitivity” of an agent’s output.

Deﬁnition 5. (Sensitivity for Input Perturbation Privacy)

The `2-norm sensitivity of agent i’s output map is the

greatest distance between two output trajectories ϑi=

yi[0], yi[1], ..., yi[t], ... and ϑ′

i=yi[0], yi[1], ..., yi[t], ...

deﬁned as Eq. (4) for κi, κ′

i∈˜

`∣D∣

∆`2ϑi∶=sup

κi,κ′

iCi∗κi−Ci∗κ′

i`2(4)

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

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

10 玖币 0人已下载

立即下载

摘要：

DistributedDifferentiallyPrivateControlSynthesisforMulti-AgentSystemswithMetricTemporalLogicSpecicationsNasimBaharisangariandZheXuAbstractInthispaper,weproposeadistributeddiffer-entiallyprivaterecedinghorizoncontrol(RHC)approachformulti-agentsystems(MAS)withmetrictemporallogic(MTL)specications.In...

展开>> 收起<<

Distributed Differentially Private Control Synthesis for Multi-Agent Systems with Metric Temporal Logic Speciﬁcations Nasim Baharisangari and Zhe Xu.pdf

共9页,预览2页

还剩页未读，继续阅读

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

Distributed Differentially Private Control Synthesis for Multi-Agent Systems with Metric Temporal Logic Speciﬁcations Nasim Baharisangari and Zhe Xu

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: