\qquad
文中主要研究具有区域约束的机器人网络执行静态最优覆盖。给定密度函数描述事件发生的概率，执行函数(
p
e
r
f
o
r
m
a
n
c
e
f
u
n
c
t
i
o
n
performance\ function
performance function)代表到定位点的代价。目标是通过合理放置传感器使最小化探测代价。此外，由于平衡负载约束，预先设定给每个机器人的分配的区域。
一般性泰森分区(Generalized Voronoi Partitions)
\qquad
对于凸多边形
Q
⊂
R
d
Q\subset\mathbb{R}^d
Q⊂Rd和
P
=
(
p
1
,
p
2
,
.
.
.
,
p
n
)
∈
Q
n
P=(p_{1},p_{2},...,p_{n})\in Q^{n}
P=(p1,p2,...,pn)∈Qn，泰森分区为
V
(
P
)
=
{
V
1
(
P
)
,
.
.
.
,
V
n
(
P
)
}
\mathcal{V}(P)=\{V_{1}(P),...,V_{n}(P)\}
V(P)={V1(P),...,Vn(P)}，定义
D
e
l
a
u
n
a
y
g
r
a
p
h
\color{#F00}{Delaunay\ graph}
Delaunay graph，对于相邻端点
p
i
和
p
j
p_{i}和p_{j}
pi和pj如果
V
i
(
P
)
∩
V
j
(
P
)
≠
ϕ
V_{i}(P)\cap V_{j}(P)\neq\phi
Vi(P)∩Vj(P)̸=ϕ，给定性能函数
f
:
R
→
R
f:\mathbb{R}\rightarrow\mathbb{R}
f:R→R严格递增，给定权重
ω
=
(
ω
1
,
.
.
.
,
ω
n
)
∈
R
n
\omega=(\omega_{1},...,\omega_{n})\in\mathbb{R}^{n}
ω=(ω1,...,ωn)∈Rn，得出一般性泰森分区公式为：
V
i
f
(
P
,
ω
)
=
{
q
∈
Q
∣
f
(
∣
∣
q
−
p
i
∣
∣
)
−
ω
i
≥
f
(
∣
∣
q
−
p
j
∣
∣
)
−
ω
j
,
i
≠
j
}
V_{i}^{f}(P,\omega)=\{q\in Q|f(||q-p_{i}||)-\omega_{i}\ge f(||q-p_{j}||)-\omega_{j},i\ne j\}
Vif(P,ω)={q∈Q∣f(∣∣q−pi∣∣)−ωi≥f(∣∣q−pj∣∣)−ωj,i̸=j}一般的，一般化泰森分区既不是凸区域也不是星形。
区域约束下的定位最优问题
\qquad
考虑区域约束条件多中心最优化问题，即在多中心最优问题(
m
i
n
i
m
i
z
e
H
(
p
1
,
.
.
.
,
p
n
,
W
1
,
.
.
.
,
W
n
)
minimize\ \mathcal{H}(p_{1},...,p_{n},W_{1},...,W_{n})
minimize H(p1,...,pn,W1,...,Wn))中增加可行域条件约束(
a
i
a_{i}
ai)。给定可行域集
{
a
1
,
.
.
.
,
a
n
}
⊂
R
>
0
\{a_{1},...,a_{n}\}\subset\mathbb{R}_{>0}
{a1,...,an}⊂R>0满足
∑
i
=
1
n
a
i
=
∫
Q
ϕ
(
q
)
d
q
=
a
r
e
a
ϕ
(
Q
)
\sum_{i=1}^{n}a_{i}=\int_{Q}\phi(q)dq=area_{\phi}(Q)
∑i=1nai=∫Qϕ(q)dq=areaϕ(Q)。即：
m
i
n
i
m
i
z
e
H
(
p
1
,
.
.
.
,
p
n
,
W
1
,
.
.
.
,
W
n
)
s
u
b
j
e
c
t
t
o
∫
W
i
ϕ
(
q
)
d
q
=
a
i
,
i
∈
{
1
,
.
.
.
,
n
}
minimize\quad\mathcal{H}(p_{1},...,p_{n},W_{1},...,W_{n})\\ subject\ to\quad \int_{W_{i}}\phi(q)dq=a_{i},i\in\{1,...,n\}
minimizeH(p1,...,pn,W1,...,Wn)subject to∫Wiϕ(q)dq=ai,i∈{1,...,n}等分域情形为
a
i
=
1
/
n
∫
Q
ϕ
(
q
)
d
q
f
o
r
i
∈
{
1
,
.
.
.
,
n
}
a_{i}=1/n\int_{Q}\phi(q)dq\ for\ i\in\{1,...,n\}
ai=1/n∫Qϕ(q)dq for i∈{1,...,n}。
基于一般化泰森分区的权重-区域映射
\qquad
定义权重-区域映射为
M
:
U
⊂
R
n
→
R
n
\mathcal{M}:U\subset\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}
M:U⊂Rn→Rn：
M
(
ω
)
=
(
∫
V
1
f
(
P
,
ω
)
ϕ
(
q
)
d
q
,
.
.
.
,
∫
V
n
f
(
P
,
ω
)
ϕ
(
q
)
d
q
)
\mathcal{M}(\omega)=(\int_{V_{1}^{f}(P,\omega)}\phi(q)dq,...,\int_{V_{n}^{f}(P,\omega)}\phi(q)dq)
M(ω)=(∫V1f(P,ω)ϕ(q)dq,...,∫Vnf(P,ω)ϕ(q)dq)其中，
P
=
{
p
1
,
.
.
.
,
p
n
}
P=\{p_{1},...,p_{n}\}
P={p1,...,pn}。令
M
\mathcal{M}
M为梯度，
∇
F
=
−
M
\nabla F=-\mathcal{M}
∇F=−M(
？
？
？
\color{#F00}{？？？}
？？？)，其中
F
:
R
n
→
R
F:\mathbb{R}^{n}\rightarrow\mathbb{R}
F:Rn→R
F
(
ω
)
=
∑
j
=
1
n
∫
V
j
f
(
P
,
ω
)
(
f
(
∣
∣
q
−
p
j
∣
∣
)
−
ω
j
)
ϕ
(
q
)
d
q
F(\omega)=\sum_{j=1}^{n}\int_{V_{j}^{f}(P,\omega)}(f(||q-p_{j}||)-\omega_{j})\phi(q)dq
F(ω)=j=1∑n∫Vjf(P,ω)(f(∣∣q−pj∣∣)−ωj)ϕ(q)dq
\qquad
若通过配置权值
ω
i
\omega_{i}
ωi使得
M
(
ω
i
)
=
a
i
\mathcal{M}(\omega_{i})=a_{i}
M(ωi)=ai，几乎不能直接求解映射的解析解，使用的方法为：定义函数
g
(
ω
1
,
.
.
.
,
ω
n
)
=
M
(
ω
1
,
.
.
.
,
ω
n
)
−
(
a
1
,
.
.
.
,
a
n
)
g(\omega_{1},...,\omega_{n})=\mathcal{M}(\omega_{1},...,\omega_{n})-(a_{1},...,a_{n})
g(ω1,...,ωn)=M(ω1,...,ωn)−(a1,...,an)，其原函数为：
F
:
R
n
→
R
n
,
F
=
−
F
(
ω
)
−
∑
i
=
1
n
ω
i
a
i
\mathcal{F}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n},\mathcal{F}=-F(\omega)-\sum_{i=1}^{n}\omega_{i}a_{i}
F:Rn→Rn,F=−F(ω)−∑i=1nωiai。寻找
ω
∈
U
\omega\in U
ω∈U，使得：
∇
F
(
ω
)
=
g
(
ω
)
=
0
(
v
e
c
t
o
r
)
n
\nabla\mathcal{F}(\omega)=g(\omega)=0(vector)_{n}
∇F(ω)=g(ω)=0(vector)n
\qquad
所寻找的
ω
\omega
ω即优化函数
F
\mathcal{F}
F(多中心最优化问题
？
？
？
\color{#F00}{？？？}
？？？)又使得泰森区域满足约束条件。
使
用
雅
克
比
(
J
a
c
o
b
i
)
迭
代
算
法
配
置
权
重
。
\color{#F00}{使用雅克比(Jacobi)迭代算法配置权重。}
使用雅克比(Jacobi)迭代算法配置权重。
\qquad
雅克比算法(生成线性方程的
J
O
R
JOR
JOR算法)
x
(
t
+
1
)
=
x
(
t
)
−
γ
[
D
(
x
(
t
)
)
]
−
1
∇
F
(
x
(
t
)
)
x(t+1)=x(t)-\gamma[D(x(t))]^{-1}\nabla F(x(t))
x(t+1)=x(t)−γ[D(x(t))]−1∇F(x(t))
\qquad
其中，
γ
\gamma
γ是步长，
D
(
x
)
D(x)
D(x)是对角矩阵，其第i个对角元素为
∇
i
i
2
F
(
x
)
\nabla_{ii}^{2}F(x)
∇ii2F(x)，假设其对角元素都是非零元素。
\qquad
应用雅克比算法迭代权值为：
ω
k
+
1
=
ω
k
−
γ
d
i
a
g
(
∂
g
1
∂
ω
1
(
ω
k
)
,
.
.
.
,
∂
g
n
∂
ω
n
(
ω
k
)
)
−
1
g
(
ω
k
)
\omega_{k+1}=\omega_{k}-\gamma diag(\frac{\partial g_{1}}{\partial \omega_{1}}(\omega_{k}),...,\frac{\partial g_{n}}{\partial \omega_{n}}(\omega_{k}))^{-1}g(\omega_{k})
ωk+1=ωk−γdiag(∂ω1∂g1(ωk),...,∂ωn∂gn(ωk))−1g(ωk)
\qquad
使
用
质
量
守
恒
(
c
o
n
s
e
r
v
a
t
i
o
n
−
o
f
−
m
a
s
s
)
定
理
\color{#F00}{使用质量守恒(conservation-of-mass)定理}
使用质量守恒(conservation−of−mass)定理求解：
∂
g
i
∂
ω
j
=
∫
∂
V
i
ϕ
n
i
∂
q
∂
ω
j
d
q
\frac{\partial g_{i}}{\partial \omega_{j}}=\int_{\partial V_{i}}\phi\ n_{i}\frac{\partial q}{\partial\omega_{j}}dq
∂ωj∂gi=∫∂Viϕ ni∂ωj∂qdq
