Multitask-based Assisted Evolutionary Algorithm for Vehicle Routing Problems inComplex Logistics Distribution Scenarios
-
摘要: 在现代社会中, 复杂物流配送场景的车辆路径规划问题(Vehicle routing problem, VRP)一般带有时间窗约束且需要提供同时取送货的服务. 这种复杂物流配送场景的车辆路径规划问题是NP-难问题. 当其规模逐渐增大时, 一般的数学规划方法难以求解, 通常使用启发式方法在限定时间内求得较优解. 然而, 传统的启发式方法从原大规模问题直接开始搜索, 无法利用先前相关的优化知识, 导致收敛速度较慢. 因此, 提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm, MBEA), 通过使用迁移优化方法加快算法收敛速度, 其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题. 首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务, 然后使用进化多任务(Evolutional multitasking, EMT)方法用于生成原大规模问题和优化子任务的候选解. 由于优化子任务相对简单且与原大规模问题相似, 其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题, 从而加快其求解速度. 最后, 提出的算法在京东物流公司快递取送货数据集上进行验证, 其路径规划效果优于当前最新提出的路径规划算法.Abstract: In complex logistics, addressing the vehicle routing problem (VRP) with simultaneous pickup and delivery and time windows, an NP-hard problem, becomes increasingly challenging as the scale expands. Traditional heuristic methods, often unable to leverage prior optimization knowledge, result in slow convergence. To address this, we introduce a multitask-based evolutionary algorithm (MBEA), which assists the optimization of the original large-scale problem by constructing multiple simple and similar subtasks and utilizing transfer learning to accelerate convergence speed. First, a subset of orders is randomly selected from the original problem to construct various subtasks, and then a multitask evolutionary approach is applied to generate candidate solutions for the original problem and subtasks. Given that the subtasks are simpler yet similar to the original problem, useful routing traits can be shared through knowledge transfer among the tasks, thereby speeding up its evolutionary search. To validate MBEA＇s efficacy, empirical studies were conducted on a large-scale express dataset from Jingdong, and the results demonstrate that MBEA outperforms recently proposed vehicle routing algorithms.
-
随着人工智能和传感器技术的发展, 人体姿态估计(Human pose estimation, HPE)逐渐应用于各种不同的领域, 如人机交互、运动捕捉[1-2]、虚拟替身、康复训练[3]、自动驾驶、视频监控和运动表现分析等[4-6]. 然而, 受视觉遮挡等因素影响[7], 这将增加视觉人体姿态估计中腕、肘等人体部件误识别的风险, 从而导致量测不确定性的存在, 而多视觉融合方法是处理视觉遮挡下HPE的主流方法之一[8-11].
针对多视觉融合估计问题, 文献[8]提出一种面向人体关节点位置信息的可靠性判别方法, 通过调节加权观测融合中的量测融合权重, 以提高HPE的鲁棒性. 而在文献[12]中, 将多视觉下的融合估计问题转换为优化问题, 利用骨骼长度作为约束条件, 并基于关节点位置信息的可靠性, 来调整优化过程中的权重大小, 从而减小视觉遮挡时的人体骨架抖动. 然而, 在求目标函数的过程中, 该方法易受初始数据的影响. 针对基于多视角融合的HPE问题, 文献[9]首次提出信息加权一致性滤波器(Information weighted consensus filter, IWCF), 通过平均一致性(Average consensus)[13]来获得邻近节点的信息. 同时, 使用Metropolis权重来提高IWCF的收敛速度, 实验证明融合后的人体姿态信息可获得更高的动作识别精度. 之后, 针对多视觉HPE中各传感器节点估计误差引起的关节点波动问题, 文献[10]将IWCF与交互式多模型(Interacting multiple model-based, IMM)相结合, 获得混合恒定速度(Constant velocity, CV)、恒定加速度(Constant acceleration, CA)和Singer运动等多模型下的姿态估计, 从而减小视觉遮挡的影响以及提高估计的精度.
另一方面, 针对人体姿态量测存在的噪声问题, 卡尔曼滤波(Kalman filtering, KF)[14]是一种有效的去噪方法. 其不仅在目标跟踪领域应用广泛[15-17], 而且在人体姿态估计领域也发挥重要的作用[18-20]. 例如, 文献[19]利用卡尔曼滤波器提高人体姿态估计的准确性. 针对人体姿态量测噪声统计特性的难以精确描述问题, 文献[20]提出一种基于鲁棒卡尔曼滤波的HPE方法, 利用假设检验对视觉遮挡下的复杂噪声进行识别, 并引入自适应因子来对量测噪声协方差进行调整, 从而减小量测不确定性对滤波器性能的影响. 此外, 针对量测信息缺失的目标跟踪问题, 文献[21]同样利用假设检验对量测信息进行有效筛选, 并利用渐进滤波方法来处理量测信息缺失造成的误差增大问题, 从而提高滤波器的鲁棒性. 针对渐进滤波对量测不确定性补偿的问题, 文献[22-23]提出带自适应量测更新的渐进高斯滤波方法, 给出渐进量测更新的终止条件. 这不仅有利于计算效率, 而且提高了对量测不确定性的自适应能力. 然而, 针对视觉遮挡造成量测噪声的复杂性, 现有估计方法并未充分考虑到局部量测不确定性的差异. 同时, 基于假设检验的方法局限于单一维度对量测进行筛选, 没有充分考虑到先验信息和局部量测以及不同局部量测之间的相容性问题.
为此, 本文构建分布式的渐进贝叶斯滤波融合框架, 提出基于渐进高斯滤波融合的人体姿态估计方法. 针对量测信息包含的复杂噪声, 设计分层性能评估方法, 从空间维度到时间维度对量测进行分类处理. 为解决量测不确定性下的融合估计问题, 设计一种分层分类的融合估计方法. 特别地, 针对量测统计特性变化问题, 引入渐进滤波方法, 利用局部估计间的交互信息来引导渐进量测更新, 从而隐式地补偿量测不确定性. 最后, 仿真与实验结果表明, 相比于现有的方法, 提高了人体姿态估计的准确性和鲁棒性.
1. 问题描述
如图1所示, 考虑一类多视觉融合环境下的人体姿态估计系统, 其中, 视觉传感器为深度相机, 用于采集人体目标的深度信息. 本文将人体目标视为由头、躯干、臂、手、腿、足等部件相互连接构成的多刚体系统. 这样, 人体姿态估计问题可看作人体各关节点位置估计问题. 首先, 利用卷积神经网络(Convolutional neural network, CNN) 的方法[24]从图像中识别出人体各部件, 并计算出人体各关节点在各个相机坐标系下的3D位置; 其次, 通过棋盘格标定法可获得相机坐标系相对于世界坐标系(即, 棋盘格)的旋转矩阵$ {R^{{c_i}2w}} $和平移向量$ {\boldsymbol{t}}^{{c_i}2w} $, 从而将在不同相机坐标系下检测的3D关节点统一到世界坐标系. 同时, 对人体运动建模如下:
$$ {{\boldsymbol{x}}_k} = {F_k}{{\boldsymbol{x}}_{k - 1}} + {{\boldsymbol{w}}_k} $$ (1) 其中, $k=1, 2,\cdots$ 表示离散时间序列, ${{\boldsymbol{x}}_k} = [{{( {{{\boldsymbol{x}}_{k,1}}} )}^\text{T}} \;\; \cdots\;\; {{{( {{{\boldsymbol{x}}_{k,L}}} )}{}^{\rm{T}}}} ]{}^{\rm{T}}$表示$ {k} $时刻人体姿态的状态, $ {{\boldsymbol{x}}_{k,l}} $表示关节点$ l $状态, $ l = 1, \cdots , L $, $ {L} $为选取的人体关节数量; $ {F_k} = {\rm{diag}}\{ {{F_{k,1}}}\;\; \cdots \;\; {{F_{k,L}}}\} $表示状态转移矩阵; 过程噪声${{\boldsymbol{w}}_k} = {[ {{{( {{{\boldsymbol{w}}_{k,1}}} )}^\text{T}}}\;\; \cdots \;\; {{{( {{{\boldsymbol{w}}_{k,L}}} )}{}^\text{T}}} ]{}^\text{T}}$服从零均值高斯分布, 其方差为$ {\mathop{\rm{cov}}} ( {{{\boldsymbol{w}}_k}} ) = {Q_k} $. 最后, 在此基础上, 将融合运动模型和单视觉量测信息形成人体姿态的局部估计, 进而融合各局部估计形成人体姿态的全局估计. 注意到视觉遮挡程度的不同, 将给人体关节点的检测与测量带来不同程度的影响, 从而导致复杂的量测噪声.
因此, 对人体姿态量测建模如下:
$$ {\boldsymbol{z}}_k^i = H_k^i{{\boldsymbol{x}}_k} + {\boldsymbol{v}}_k^i + {\boldsymbol{\xi}}_k^i $$ (2) 其中, ${\boldsymbol{z}}_k^i = {[ {{{( {{\boldsymbol{z}}_{k,1}^i} )}{}^\text{T}} \;\cdots\; {{( {{\boldsymbol{z}}_{k,L}^i} )}{}^\text{T}}} ]^\text{T}}$表示传感器$ i $的量测值, $ i = 1, \cdots , N $, $ {N} $为传感器总数, ${\boldsymbol{z}}_{k,l}^i = [ {z_{x,l}^i} \;\;{z_{y,l}^i}\;\;{z_{z,l}^i} ]^\text{T}$ 表示关节点的位置量测信息, $z_{x,l}^i, z_{y,l}^i, z_{z,l}^i$分别为关节点$ l $在$ {x} $、$ {y} $和$ {z} $轴上的量测值. $H_k^i = [ {{{( {H_{k,1}^i} )}^\text{T}}} \;\; \cdots \;\;{{{( {H_{k,L}^i} )}{}^\text{T}}} ]{}^\text{T}$为量测矩阵; 量测噪声${\boldsymbol{v}}_k^i = {[ {{{( {{\boldsymbol{v}}_{k,1}^i} )}^\text{T}}}\;\; \cdots \;\;{{{( {{\boldsymbol{v}}_{k,L}^i} )}{}^\text{T}}} ]{}^\text{T}}$服从零均值高斯分布, 且其协方差为$ {\mathop{\rm{cov}}} ( {{\boldsymbol{v}}_k^i} ) = R_k^i $. $ {\boldsymbol{\xi}}_k^i = U_k^i {\boldsymbol{\alpha}}_k^i + b{\boldsymbol{\beta}}_k^i $用来描述不同遮挡程度影响下引起的量测噪声. 其中, $ U_k^i = \text{diag}\{{{\boldsymbol{u}}_{k,1}^i}\;\; \cdots \;\;{{\boldsymbol{u}}_{k,L}^i} \} $, $ {\boldsymbol{u}}_{k,l}^i $服从零均值且协方差为$ R_{k, + }^i $的高斯分布; $ b $为幅值较大的数值, $ {\boldsymbol{\alpha}}_k^i $和$ {\boldsymbol{\beta}}_k^i $为随机变量且分别服从参数为$ {y_1}\;( {0 < {y_1} < 1} ) $和$ {y_2}\;( {0 < {y_2} < 1} ) $的伯努利分布.
相应地, 针对量测信息包含的复杂噪声, 将对量测进行检测和分类处理, 从而剔除高程度视觉遮挡下的量测野值, 同时通过渐进滤波隐式地补偿低程度视觉遮挡下的量测.
注1. 针对视觉遮挡程度的不同, 本文将量测主要分为两类. 即: 1)低程度视觉遮挡下的量测, 例如, 人体双臂交叉引起的腕、肘等关节小面积视觉遮挡, 用$ U_k^i {\boldsymbol{\alpha}}_k^i $来描述该情形下的量测不确定性; 2)高程度视觉遮挡下的量测, 例如, 人体侧身时腕、肘等关节受背部大面积视觉遮挡, 用$ b{\boldsymbol{\beta}}_k^i $来描述这种情况下的量测野值.
2. 自适应渐进高斯滤波融合
不同程度的视觉遮挡将造成量测统计特性变化, 进而导致局部滤波器性能下降并最终影响融合结果. 因此, 分两步从空间维度和时间维度上分别对量测进行相容性检测来实现量测筛选和分类处理.
考虑多视觉传感器的坐标位置和感知范围不同, 可能导致量测具有不同的噪声特性与误差模型. 如图2所示, 首先, 在空间维度上检测不同量测间马氏距离的平方, 即
$$ \begin{split} \gamma \left( {{\boldsymbol{z}}_k^i, {\boldsymbol{z}}_k^j} \right) = {\left( {{\boldsymbol{z}}_k^i - {\boldsymbol{z}}_k^j} \right)^\text{T}}\Sigma _{zz}^{ - 1}\left( {{\boldsymbol{z}}_k^i - {\boldsymbol{z}}_k^j} \right) \end{split} $$ (3) 其中, $ \Sigma _{zz}^{ - 1} $表示$( {\boldsymbol{z}}_k^i - {\boldsymbol{z}}_k^j ) $的协方差矩阵. 若$ \gamma ({\boldsymbol{z}}_k^i,{\boldsymbol{z}}_k^j) $落在置信区间内, 即$ \gamma ({\boldsymbol{z}}_k^i,{\boldsymbol{z}}_k^j) < {\chi _n} $, 则表示量测相容, 即视为正常量测, 否则认为其中可能存在异常量测, 需进一步在时间维度上分析相容性, 即检测预测值与量测的马氏距离平方:
$$ \begin{split} \gamma ({\boldsymbol{z}}_k^j, H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f) = \, & {\left( {{\boldsymbol{z}}_k^j - H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f} \right)^\text{T}}\Sigma _{zx}^{ - 1} \;\times \\ &\left( {{\boldsymbol{z}}_k^j - H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f} \right) \end{split} $$ (4) 其中, $ \Sigma _{zx}^{ - 1} $表示$ ( {{\boldsymbol{z}}_k^j - H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f} ) $的协方差矩阵. 若$ \gamma ({\boldsymbol{z}}_k^j, H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f) $ 落在置信区间内, 即
$$\gamma ({\boldsymbol{z}}_k^j, H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f) < {\chi _a} $$ 则表示量测中存在额外干扰, 否则视为野值.
根据量测相容性的检测结果, 将量测${Z_k} = \{ {\boldsymbol{z}}_k^1, \cdots , {\boldsymbol{z}}_k^N \}$分为$ G_k^n $, $ G_k^a $, $ G_k^d $等3组. 正常量测集合表示为
$$ \begin{split} G_k^n = &\left\{{{\boldsymbol{z}}_k^j|\gamma ({\boldsymbol{z}}_k^j,{\boldsymbol{z}}_k^i) < {\chi _n},{\boldsymbol{z}}_k^j,{\boldsymbol{z}}_k^i \in {Z_k},}\right.\\ & \left.{{\boldsymbol{z}}_k^j \ne {\boldsymbol{z}}_k^i,j = 1,2, \cdots}\right\} \end{split} $$ (5) 低程度视觉遮挡下的量测集合表示为
$$ \begin{split} G_k^a =\, & \left\{ {{\boldsymbol{z}}_k^j|\gamma ({\boldsymbol{z}}_k^j,H_k^f\hat {{\boldsymbol{x}}}_{k|k - 1}^f) < {\chi _a},\gamma \left( {{\boldsymbol{z}}_k^j,{\boldsymbol{z}}_k^i} \right) \ge } \right. \\ &\left.{{\chi _n},{\boldsymbol{z}}_k^j,{\boldsymbol{z}}_k^i \in {Z_k},{\boldsymbol{z}}_k^j \ne {\boldsymbol{z}}_k^i,j = 1,2, \cdots} \right\} \end{split} $$ (6) 集合$ G_k^d = {Z_k} - G_k^n - G_k^a $表示高程度视觉遮挡下的量测野值. $ {\chi_n} $, $ {\chi_a} $为置信区间, $ \hat {{\boldsymbol{x}}}_{k|k - 1}^f $为全局状态预测. 量测分组后, 得到不同视觉遮挡下的量测$ {\boldsymbol{z}}_k^{{n_j}} $, $ {\boldsymbol{z}}_k^{{a_j}} $, $ {\boldsymbol{z}}_k^{{d_j}} $, 其中${\boldsymbol{z}}_k^{{n_j}} \in G_k^n,{\boldsymbol{z}}_k^{{a_j}} \in G_k^a,{\boldsymbol{z}}_k^{{d_j}} \in G_k^d$.
本文方法框图如图3所示, 首先, 通过分层性能评估对量测进行分层和分类; 其次, 在局部估计中, 将拒绝量测野值$ {\boldsymbol{z}}_k^{{d_j}} $, 以避免量测野值对系统滤波性能造成较大的负面影响. 特别地, 在量测$ {\boldsymbol{z}}_k^{{a_j}} $更新过程中, 将渐进地引入量测信息对当前局部状态进行补偿, 即通过多次量测迭代得到相应补偿下的后验状态, 并通过局部估计间的交互信息来引导渐进量测更新. 最后, 融合人体姿态的各局部估计形成全局估计. 为此, 构建分布式渐进贝叶斯滤波融合框架如下.
1)人体姿态全局估计
$$ p({{\boldsymbol{x}}_k}|{Z_{1:k - 1}}) = \int {p({{\boldsymbol{x}}_k}|{{\boldsymbol{x}}_{k - 1}})p({{\boldsymbol{x}}_{k - 1}}|{Z_{1:k - 1}})\text{d}{{\boldsymbol{x}}_{k - 1}}} $$ (7) $$ \begin{split} & p({{\boldsymbol{x}}_k}|{Z_{1:k}}) = p({{\boldsymbol{x}}_k}|{Z_{1:k - 1}})\;\times\\ & \quad \frac{{\prod\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {p\left( {{{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k}^{{n_j}}} \right)} \prod\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {p\left( {{{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k}^{{a_j}}} \right)} }}{{\prod\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {p\left( {{{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k - 1}^{{n_j}}} \right)} \prod\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {p\left( {{{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}} \right)} }} \end{split}$$ (8) 2)人体姿态局部估计
$$ p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k - 1}^i) = \int {p({{\boldsymbol{x}}_k}|{{\boldsymbol{x}}_{k - 1}})p({{\boldsymbol{x}}_{k - 1}}|{\boldsymbol{z}}_{1:k - 1}^i)\text{d}{{\boldsymbol{x}}_{k - 1}}} $$ (9) $$ p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k}^i) = \frac{{p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k - 1}^i)p({\boldsymbol{z}}_k^i|{{\boldsymbol{x}}_k})}}{{p({\boldsymbol{z}}_k^i|{\boldsymbol{z}}_{1:k - 1}^i)}} $$ (10) 对于量测$ {\boldsymbol{z}}_k^{{n_j}} \in G_k^n $, 采用卡尔曼滤波方法得到人体姿态局部估计; 而对$ {\boldsymbol{z}}_k^{{a_j}} \in G_k^a $, 则采用渐进高斯滤波(Progressive Gaussian filtering, PGF)方法对量测不确定性进行隐式补偿. 可将量测分解为多个伪量测的集成, 即
$$ \begin{align} &R_k^{{a_j}} = {\left[ {\sum\limits_{m = 1}^M {{{\left( {R_{k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}}} } \right]^{ - 1}} \end{align} $$ (11) $$ \begin{align} &{\boldsymbol{z}}_k^{{a_j}} = {\left[ {\sum\limits_{m = 1}^M {{{\left( {R_{k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}}} } \right]^{ - 1}}\sum\limits_{m = 1}^M {\left[ {{{\left( {R_{k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}}{\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}}} \right]} \end{align} $$ (12) 利用量测迭代更新, 渐进地引入量测信息. 其中$ {\lambda _m} $表示伪时间, 且满足
$$\left\{ \begin{aligned} &{\Delta _m} = {\lambda _m} - {\lambda _{m - 1}}\\ &{\Delta _m} > 0 \\ & \sum\limits_{m = 1}^M {{\Delta _m} = 1} \end{aligned}\right. $$ (13) 其中, $ {\lambda _0} = 0 $, $ m = 1, \cdots , M $, $ M $为总渐进步数, $ {\Delta _m} $表示渐进步长, ${\boldsymbol{z}}_{k, {\lambda _1}:{\lambda _M}}^{{a_j}} = \{ {{\boldsymbol{z}}_{k, {\lambda _1}}^{{a_j}}, \cdots, {\boldsymbol{z}}_{k, {\lambda _M}}^{{a_j}}} \}$表示整个渐进过程中的伪量测, $ {\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} $表示第$ m $步的伪量测. 在不考虑视觉遮挡所引起的量测不确定性时, $ p\left( {{\boldsymbol{z}}_k^{{a_j}}|{{\boldsymbol{x}}_k}} \right) $可以表示为
$$ \begin{split} & p\left( {{\boldsymbol{z}}_k^{{a_j}}|{{\boldsymbol{x}}_k}} \right) =\\ &\;\;\; \frac{1}{{\sqrt {2\pi \left| {R_k^{{a_j}}} \right|} }}\exp \Bigg[ { - \frac{1}{2}{{\left( {{\boldsymbol{z}}_k^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k}} \right)}^\text{T}}} \;\times \\ &\;\;\; {{{\left( {R_k^{{a_j}}} \right)}^{ - 1}}\left( {{\boldsymbol{z}}_k^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k}} \right)} \Bigg]= \\ &\;\;\; \frac{1}{{\sqrt {2\pi \left| {R_k^{{a_j}}} \right|} }}\prod\limits_{m = 1}^M {\frac{1}{{{{\left( {\sqrt {2\pi \left| {\frac{{R_k^{{a_j}}}}{{{\Delta _m}}}} \right|} } \right)}^{ - 1}}}}\frac{1}{{\sqrt {2\pi \left| {\frac{{R_k^{{a_j}}}}{{{\Delta _m}}}} \right|} }}} \;\times \\ &\;\;\; \exp \Bigg[ - \frac{1}{2}{\left( {{\boldsymbol{z}}_k^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k}} \right)^\text{T}}\times\Bigg. \\ &\;\;\; \Bigg.{\left( {\frac{{R_k^{{a_j}}}}{{{\Delta _m}}}} \right)^{ - 1}}\left( {{\boldsymbol{z}}_k^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k}} \right)\Bigg]\\[-15pt] \end{split} $$ (14) 因此, $p( {{\boldsymbol{z}}_k^{{a_j}}|{{\boldsymbol{x}}_k}} ) = c_k^{{a_j}}\prod\nolimits_{m = 1}^M {p( {{\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}}|{{\boldsymbol{x}}_k}} )},$ 其中,
$$ \begin{split} &p({\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}}|{{\boldsymbol{x}}_k}) = {\left(\sqrt {2\pi \left| {R_{k, {\lambda _m}}^{{a_j}}} \right|} \right)^{ - 1}}\;\times\\ & \qquad\exp \Bigg[ - \frac{1}{2}{({\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k})^\text{T}}\;\times \Bigg. \\ & \qquad \Bigg.{(R_{k, {\lambda _m}}^{{a_j}})^{ - 1}}({\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k})\Bigg] \end{split} $$ (15) $R_{k, {\lambda _m}}^{{a_j}} = \frac{{R_k^{{a_j}}}}{{{\Delta _m}}}$, $ {\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} = {\boldsymbol{z}}_k^{{a_j}} $, 归一化因子为
$$ \begin{split} c_k^{{a_j}} = {\left( {\sqrt {2\pi \left| {R_k^{{a_j}}} \right|} } \right)^{ - 1}}\prod\limits_{m = 1}^M {\sqrt {2\pi \left| {\frac{{R_k^{{a_j}}}}{{{\Delta _m}}}} \right|} } \end{split} $$ (16) 对于$ G_k^a $中的量测, 其局部后验分布可进一步描述为
$$ \begin{split} p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k}^{{a_j}}) = \frac{{p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}})\prod\limits_{m = 1}^M {p\left( {{\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}}|{{\boldsymbol{x}}_k}} \right)} }}{{{{\left( {c_k^{{a_j}}} \right)}^{ - 1}}p({\boldsymbol{z}}_k^{{a_j}}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}})}} \end{split} $$ (17) 同时, 在其渐进量测更新过程中, 引入$ G_k^n $中量测作为参照量来引导其渐进迭代, 令
$$ \begin{split} {\varphi _{{\lambda _m}}} =\, & \gamma \left( {{\boldsymbol{z}}_k^{{n_j}},H_k^{{a_j}}\hat {{\boldsymbol{x}}}_{k|k, {\lambda _m}}^{{a_j}}} \right)-\\ &\gamma \left( {{\boldsymbol{z}}_k^{{n_j}},H_k^{{a_j}}\hat {{\boldsymbol{x}}}_{k|k, {\lambda _{m - 1}}}^{{a_j}}} \right) \end{split} $$ (18) $ {\varphi _{{\lambda _m}}} $表示在渐进量测更新前后的估计值与参照量间马氏距离的差值, 当$ {\varphi _{{\lambda _m}}} \ge 0 $时停止$ p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k}^{{a_j}}) $中的渐进量测更新, 从而对量测不确定性隐式地补偿, 即通过$ {\varphi _{{\lambda _m}}} $值来判断是否继续引入伪量测$ {\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} $来渐进迭代和逐步修正状态估计, 而无需显式地将不确定性(如协方差矩阵)作为输入. 结合式(17)和式(18), 量测渐进更新过程中的后验概率密度函数(Probability density function, PDF)可以表示为
$$ \begin{split} &p\left({{\boldsymbol{x}}_k}, {\lambda _m}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}, {\boldsymbol{z}}_{k, {\lambda _1}:{\lambda _m}}^{{a_j}}\right) = \\ & \qquad {\eta _{k, {\lambda _m}}}p\left({{\boldsymbol{x}}_k}, {\lambda _1}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}, {\boldsymbol{z}}_{k, {\lambda _1}}^{{a_j}}\right)\times \\ & \qquad\prod\limits_{m = 2}^{{\varphi _{{\lambda _m}}} < 0} {p\left({\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}}|{{\boldsymbol{x}}_k}\right)} \end{split} $$ (19) 其中, $ {\eta _{k, {\lambda _m}}} $表示归一化因子.
注2. 在量测渐进更新过程中, $ {\varphi _{{\lambda _m}}} < 0 $表示估计值与参照量之间马氏距离的趋势减小, 即所修正的状态估计有效; 由式(14)可知, 渐进量测集成的等效协方差$ \bar R_k^{{a_j}} = {( {\Delta _1}+{\sum\nolimits_{m = 2}^{{\varphi _{{\lambda _m}}} < 0} {{\Delta _m}} } )^{ - 1}}R_k^{{a_j}} $, $ m = 2 $表示至少渐进一步(将简化为$ {\sum\nolimits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0}} $). 通过控制量测渐进更新的步长从而自适应调整其协方差, 将量测不确定性的补偿问题转换为对量测渐进更新的步长控制问题.
令$ k-1 $时刻的局部估计和全局估计均为高斯分布, 即$p({{\boldsymbol{x}}_{k - 1}}|{\boldsymbol{z}}_{1:k - 1}^i) = \text{N}( {{{\boldsymbol{x}}_{k - 1}};\hat {{\boldsymbol{x}}}_{k - 1|k - 1}^i, P_{k-1|k-1}^i} ),$ $ p({{\boldsymbol{x}}_{k - 1}}|{Z_{1:k - 1}}) = \text{N}( {{{\boldsymbol{x}}_{k - 1}};\hat {{\boldsymbol{x}}}_{k - 1|k - 1}^f, P_{k-1|k-1}^f} ) $, 由状态方程(1)可得$ p({{\boldsymbol{x}}_k}|{{\boldsymbol{x}}_{k - 1}}) $ = $\text{N}( {{{\boldsymbol{x}}_k};{F_k}{{\boldsymbol{x}}_{k - 1}}, {Q_k}} ),$ 则由$ k $时刻的状态预测分布易知
$$ \begin{split} p\left( {{{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k - 1}^i} \right) = \text{N}\left( {{{\boldsymbol{x}}_k};\hat {{\boldsymbol{x}}}_{k|k - 1}^i, P_{k|k - 1}^i} \right) \end{split} $$ (20) $$ \begin{split} p\left( {{{\boldsymbol{x}}_k}|{Z_{1:k - 1}}} \right) = \text{N}\left( {{{\boldsymbol{x}}_k};\hat {{\boldsymbol{x}}}_{k|k - 1}^f, P_{k|k - 1}^f} \right) \end{split} $$ (21) 其中,
$$ \begin{split} \hat {{\boldsymbol{x}}}_{k|k - 1}^i = {F_k}\hat {{\boldsymbol{x}}}_{k - 1|k - 1}^i \end{split} $$ (22) $$ \begin{split} P_{k|k - 1}^i = {F_k}P_{k - 1|k - 1}^iF_k^\text{T} + {Q_k} \end{split} $$ (23) $$ \begin{split} \hat {{\boldsymbol{x}}}_{k|k - 1}^f = {F_k}\hat {{\boldsymbol{x}}}_{k - 1|k - 1}^f \end{split} $$ (24) $$ \begin{split} P_{k|k - 1}^f = {F_k}P_{k - 1|k - 1}^fF_k^\text{T} + {Q_k} \end{split} $$ (25) 定理1. 考虑系统(1)和(2)中, 当$ G_k^n \ne \emptyset $, $ G_k^a \ne \emptyset $, 若先验概率密度函数给出如式(20)和式(21), 则可得到全局状态滤波融合估计, 即
$$ \begin{split} &{\left( {P_{k|k}^f} \right)^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k}^f = {\left( {P_{k|k - 1}^f} \right)^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^f\; + \\ &\;\;\sum\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {\left[ {{{\left( {P_{k|k}^{{n_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k}^{{n_j}} - {{\left( {P_{k|k - 1}^{{n_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}}} \right]}\;+\\ &\;\;\sum\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {\left[ {{{\left( {P_{k|k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k, {\lambda _m}}^{{a_j}} - {{\left( {P_{k|k - 1}^{{a_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^{{a_j}}} \right]} \end{split} $$ (26) $$ \begin{split} {\left( {P_{k|k}^f} \right)^{ - 1}} =\;& {\left( {P_{k|k - 1}^f} \right)^{ - 1}}\;+\\ & \sum\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {\left[ {{{\left( {P_{k|k}^{{n_j}}} \right)}^{ - 1}} - {{\left( {P_{k|k - 1}^{{n_j}}} \right)}^{ - 1}}} \right]}\;+\\ & \sum\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {\left[ {{{\left( {P_{k|k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}} - {{\left( {P_{k|k - 1}^{{a_j}}} \right)}^{ - 1}}} \right]} \end{split} $$ (27) 其中,
$$ \begin{split} \hat {{\boldsymbol{x}}}_{k|k}^{{n_j}} = \hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}} + K_k^{{n_j}}\left( {{\boldsymbol{z}}_k^{{n_j}} - H_k^{{n_j}}\hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}}} \right) \end{split} $$ (28) $$ \begin{split} P_{k|k}^{{n_j}} = \left( {{{I}} - K_k^{{n_j}}H_k^{{n_j}}} \right)P_{k|k - 1}^{{n_j}} \end{split} $$ (29) $$ \begin{split} K_k^{{n_j}} = P_{k|k}^{{n_j}}{\left( {H_k^{{n_j}}} \right)^\text{T}}{\left( {R_k^{{n_j}}} \right)^{ - 1}} \end{split} $$ (30) $$ \begin{split} &{\left( {P_{k|k,{\lambda _m}}^{{a_j}}} \right)^{ - 1}}\hat {\boldsymbol{x}}_{k|k,{\lambda _m}}^{{a_j}} = {\left( {P_{k|k - 1}^{{a_j}}} \right)^{ - 1}}\hat {\boldsymbol{x}}_{k|k - 1}^{{a_j}} \;+\\ &\qquad\;\;\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} {\left[ {{{\left( {H_k^{{a_j}}} \right)}^\text{T}}{{\left( {R_{k,{\lambda _m}}^{{a_j}}} \right)}^{ - 1}}{\boldsymbol{z}}_{k,{\lambda _m}}^{{a_j}}} \right]} \end{split} $$ (31) $$ \begin{split} &{\left( {P_{k|k, {\lambda _m}}^{{a_j}}} \right)^{ - 1}} = {\left( {P_{k|k - 1}^{{a_j}}} \right)^{ - 1}}\;+\\ &\qquad \;\;\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} {\left[ {{{\left( {H_k^{{a_j}}} \right)}^\text{T}}{{\left( {R_{k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}}H_k^{{a_j}}} \right]} \end{split} $$ (32) 式中, ${{I}}$表示单位矩阵.
证明. 见附录A.
最后, 带量测分类处理的渐进高斯滤波融合算法(Progressive Gaussian filtering fusion with classification, PGFFwC)给出如下:
算法1. PGFFwC算法
1) 初始化;
2) while
3) 由式(21)得$\hat {\boldsymbol{x}}_{k{{|}}k - 1}^f, P_{k|k - 1}^f$;
4) for $i = 1:N$ do
5) 基于式(3)和式(4), 对量测$ {\boldsymbol{z}}_k^{i}$分层分类处理得$ {\boldsymbol{z}}_k^{j}$;
6) if $ {\boldsymbol{z}}_k^{j} \in G_k^n$
7) 由式(28)和式(29)得到局部估计$\hat {\boldsymbol{x}}_{k|k}^{{n_j}}, P_{k|k}^{{n_j}}\,;$
8) end if
9) if $ {\boldsymbol{z}}_k^{j} \in G_k^a$
10) 渐进量测更新;
11) while${\varphi _{{\lambda _m}}} < 0$ and $m<M$
12) 由式(31)和式(32), 渐进量测更新得$\hat {\boldsymbol{x}}_{k|k, {\lambda _m}}^{{a_j}},$ $ P_{k|k, {\lambda _m}}^{{a_j}} $;
13) end while
14) end if
15) if $ {\boldsymbol{z}}_k^{j} \in G_k^d$
16) 剔除该量测野值;
17) end if
18) end for
19) 由式(26)和式(27)状态融合, 得到$\hat {\boldsymbol{x}}_{k|k}^f, P_{k|k}^f\,;$
20) end while
如定理1所示, 人体姿态估计性能改善表现在两方面: 1)通过量测分层性能评估, 对量测进行分类处理; 2)利用局部估计间的交互信息来引导渐进量测更新, 从而隐式地补偿量测不确定性. 此外, 当渐进滤波中截止条件尚未触发时, 定理1将等价于集中式融合. 特别地, 当量测信息均为同一种情形下时, 则具有如下的等价形式:
推论1. 当$ G_k^n = \emptyset $, $ G_k^a \ne \emptyset $时, 式(26)和式(27)可以表示为
$$ \begin{split} &{\left( {P_{k|k}^f} \right)^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k}^f = {\left( {P_{k|k - 1}^f} \right)^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^f\;{\rm{ + }}\\ &\qquad\sum\limits_{i = 1}^N {\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} {\left[ {{{\left( {H_k^i} \right)}^\text{T}}{{\left( {R_{k, {\lambda _m}}^i} \right)}^{ - 1}} {\boldsymbol{z}}_{k, {\lambda _m}}^i} \right]} } \end{split} $$ (33) $$ \begin{split} &{\left( {P_{k|k}^f} \right)^{ - 1}} = {\left( {P_{k|k - 1}^f} \right)^{ - 1}}\;+\\ &\qquad \sum\limits_{i = 1}^N {\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} {\left[ {{{\left( {H_k^i} \right)}^\text{T}}{{\left( {R_{k, {\lambda _m}}^i} \right)}^{ - 1}}H_k^i} \right]} } \end{split} $$ (34) 证明从略.
3. 仿真与实验
3.1 仿真验证
为验证本文方法的合理性与有效性, 设计由多个视觉传感器组成环境下的人体姿态估计仿真. 考虑存在不同程度视觉遮挡等因素, 采用式(2)的观测模型, 并假设人体关节目标的运动学模型如式(1), 状态转移矩阵参照文献[9, 19], 设置为${F_k} = {\rm{diag}}\left\{ {{F_0}}\;\;\cdots \;\;{{F_0}}\right\} ,$ 其中, ${F_0} = {\rm{diag}}\left\{ {{F_b}}\;\;{{F_b}}\;\;{{F_b}}\right\}$, ${F_b} = \left[ {\begin{aligned} & 1\;\;{\Delta t}\\& 0\;\;\;1 \end{aligned}} \right] ,$ 量测矩阵$ H_k^i = {\rm{diag}}\left\{ {H_0}\;\cdots \;{H_0}\right\} , $ 其中
$$ \begin{split} {H_0} = \left[ {\begin{array}{*{20}{l}} 1&0&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&0&1&0 \end{array}} \right] \end{split} $$ (35) $ {{\boldsymbol{x}}_{k,l}}={\left[{{x_{x,l}}}\;\;{{{\dot x}_{x,l}}}\;\;{{x_{y,l}}}\;\;{{{\dot x}_{y,l}}}\;\;{{x_{z,l}}}\;\;{{{\dot x}_{z,l}}} \right]^\text{T}} $, $ {x_{x,l}} $, $ {x_{y,l}} $, $ {x_{z,l}} $和$ {\dot {x}_{x,l}} $, $ {\dot {x}_{y,l}} $, $ {\dot {x}_{z,l}} $分别为人体关节点在$ x $, $ y $和$ z $轴上的位置和速度, 人体关节的总数量取为$ L $ = 17, 系统的采样时间$\Delta t =$ 0.03 s, 过程噪声$ {{\boldsymbol{w}}_k} $的协方差为$ {Q_k} = {\rm{diag}}\left\{{{Q_0}}\;\; \cdots\;\;{{Q_0}} \right\}$, 其中
$$ \begin{split} Q_0=\; &{\rm{diag}} \{0.09\;{\rm{cm}}^2, \;0.005\;{\rm{cm}}^2/{\rm{s}}^2, 0.09\;{\rm{cm}}^2,\;\\& 0.005 \;{\rm{cm}}^2/{\rm{s}}^2,\; 0.09\;{\rm{cm}}^2,\; 0.005 \;{\rm{cm}}^2/{\rm{s}}^2\} \end{split} $$ 人体骨架量测噪声$ {\boldsymbol{v}}_k^i $的协方差矩阵为$R_k^i =$${\rm{diag}}\left\{ {R_0} \cdots {R_0} \right\}$, 其中$R_0 =$ $ 5.0{I_{3 \times 3}} $$ {\rm{c}}{{\rm{m}}^{\rm{2}}} $, $ {I_{3 \times 3}} $表示3 × 3的单位阵. 设置不确定噪声$ {\boldsymbol{\xi}}_k^i $中低程度视觉遮挡干扰的协方差矩阵$ R_{k, + }^i $ = 5.0$ {I_{3 \times 3}} $$ {\rm{c}}{{\rm{m}}^{\rm{2}}} $, 出现的概率为$ {y_1} $ = 0.4; 高程度视觉遮挡下的野值设为幅值大小为40 cm的噪声, 即$ b= $40 cm, 出现的概率为$ {y_2}= $0.05. 以人体右臂腕关节点为例进行分析, 假设初始真实状态向量$ {{\boldsymbol{x}}_0} =$ [ 0 cm, 2.4 cm/s, 0 cm, 2.4 cm/s, 0 cm, 2.4 cm/s ]T, 关节点初始状态估计误差协方差为${P_0}= {I_{3 \times 3}}$, 状态估计初始值$ {\hat {{\boldsymbol{x}}}_{0|0}} $由高斯分布$ \text{N}\left( {{{\boldsymbol{x}}_0}, {P_0}} \right) $随机生成. PGF中渐进过程的总步数$ M $设为10步, 渐进步长$ \Delta _m $= 0.1, 量测评估机制中$ {\chi _n}= $ 15 cm, $ {\chi _a}= $ 30 cm.
便于仿真结果分析与比较, 定义位置误差指标为均方根误差(Root mean square error, RMSE), 其计算式为
$$ \begin{split}F_ {\rm{RMSE}} = \sqrt {\frac{1}{S}\sum\limits_{s = 1}^S {{{\left( {{H_k}{{\boldsymbol{x}}_k} - {H_k}{{\hat {{\boldsymbol{x}}}}_{k|k}}} \right)}^2}} } \end{split} $$ (36) 其中, $F_{\rm{RMSE}} $表示均方根误差, $ s = 1, \cdots , S $为仿真实验的序号, $ S $为蒙特卡罗仿真总次数, $ {\hat {{\boldsymbol{x}}}_{k|k}} $表示$ k $时刻的状态估计值, $ {{\boldsymbol{x}}_k} $表示$ k $时刻的状态真实值. 在局部滤波中采用带量测分类处理的渐进高斯滤波(PGF with classification, PGFwC) (即, PGFFwC中局部的滤波结果)、卡尔曼滤波、粒子滤波(Particle filtering, PF)、 鲁棒卡尔曼滤波(Robust Kalman filtering, RKF)[20]. 同时为进一步验证量测分层分类处理的作用, 加入不带量测分类处理的渐进高斯滤波方法(PGF without classification, PGFwoC) (即, 采用PGF方法无差别地处理量测数据)进行对比. 另外, 为验证PGFFwC的性能, 在融合算法中对比了集中式融合(Centralized fusion, CF)、协方差交叉(Covariance intersection, CI)融合、基于观测融合的自适应卡尔曼滤波(Adaptive measurement fusion-based Kalman filter, AMFKF)[25], 以及IWCF[9]的方法, 蒙特卡罗仿真结果如图4所示. 通过仿真结果可知, 无论在局部滤波还是在全局状态融合中, 本文所提方法的性能都更好. 同时, 通过图4可知, 带有量测分类处理的方法(PGFwC, PGFFwC)比未带量测分类处理的方法(PGFwoC, PGFFwoC)误差更小. 特别地, 包含量测分类处理的分布式状态融合方法(PGFFwC)提升的精度明显高于其他方法, 说明通过对量测进行分类处理后, 滤波器对量测不确定性的描述更准确, 从而在状态融合的过程中获得更高的精度.
3.2 实验验证
为进一步验证所提方法的有效性, 设计多视觉人体姿态估计实验, 实验平台如图5所示, 由两台微软公司的Azure Kinect DK相机[26-27], 一台Windows10操作系统的电脑和一个人体姿态估计对象组成. Azure Kinect DK视觉传感器包括彩色摄像头和深度摄像头, 采集到的彩色图像分辨率为1 920$ \times $1 080像素, 深度图像分辨率为512$ \times $512像素, 拍摄速度为30帧/s, 使用同步线缆硬件触发对两台相机进行同步数据采集, 并通过张正友相机标定法, 计算出从相机到主相机的旋转矩阵与平移向量, 以主相机坐标系作为世界坐标系. 在计算机上, 编写基于Visual Studio 2017的开发环境, 利用CNN的方法得到在深度相机空间下人体骨骼关节点的空间位置信息.
实验场景设置如下: 实验环境位于室内, 两台Azure Kinect DK呈约$ {45^ \circ } $角摆放, 人体目标位于两台相机前方1.5 m左右的位置进行挥臂运动, 用Azure Kinect DK来完成对人体关节点的捕捉, 整个过程会引入自遮挡以及由手持物遮挡造成的误识别. 这里需要补充说明的是, 人体关节点对应的实际人体位置并不明确, 即人体关节点的物理意义是不明确的. 故以高精度动作捕捉系统OptiTrack System[28] (精度0.5 mm) 来获取人体关节点的真实轨迹, 如图5所示, 该定位系统由12个Prime 13相机组成, 能够实时捕捉运动目标的位姿, 以追踪到的光学标记点的位置为真值, 即视为真实人体关节点位置进行对比.
在实验中, 采用的对比方法与仿真一致, 局部滤波分别采用PF, KF, RKF, PGFwC和PGFwoC的方法对比, 全局融合分别采用CF, CI, AMFKF, IWCF, PGFFwC和PGFFwoC的方法对比. 捕捉对象为人体右臂, 其中包括肩关节、肘关节和腕关节. 以人体右臂腕关节点为例分析, 滤波参数与仿真设置的一致, 图6表示该关节点在运动过程中, 不同方法处理下的累积位置误差分析图. 进一步, 表1所示为腕关节点、肘关节点以及肩关节点的位置误差均值, 从中可看出, PGFFwC方法下得到的误差更低. 由此说明该方法能有效提高人体姿态估计的精度和鲁棒性. 另外, 从3组关节点误差均值的整体对比中, 可看出腕关节点的误差相对更大, 肩关节点的误差相对更小, 表明机动性更强的关节点存在的误差也更大.
图 6 不同滤波融合方法下的累积位置误差Fig. 6 Cumulative position error under different filtering fusion methods表 1 累积误差均值统计(mm)Table 1 Cumulative error mean statistics (mm)实验方法 腕关节 肘关节 肩关节 观测融合 166.44 124.44 96.56 CF 157.55 118.00 95.00 AMFKF 147.81 113.85 93.08 CI 127.63 117.85 99.62 IWCF 153.12 113.21 92.53 PGFFwoC 151.77 114.12 92.83 PGFFwC 119.47 108.98 84.11 4. 结束语
为处理视觉遮挡下人体姿态估计性能下降问题, 提出基于渐进高斯滤波融合的姿态估计方法. 首先, 采用CNN的方法从深度图像中识别并得出人体各关节点在相机坐标系下的3D位置, 并将其转换到世界坐标系下; 其次, 在多视觉骨架数据融合中, 构建分布式的渐进贝叶斯滤波融合框架并提出基于渐进高斯滤波融合的人体姿态估计方法. 针对量测信息中包含的复杂噪声, 分别从空间、时间维度对量测进行相容性分析与分类处理. 同时, 引入渐进量测更新与引导机制, 隐式地补偿量测不确定性.
附录 A. 定理1的证明
证明. 因为$ p({\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}}|{{\boldsymbol{x}}_k}) $, $ p({{\boldsymbol{x}}_k}|{\boldsymbol{z}}_{1:k{\rm{ - }}1}^{{a_j}}) $为高斯分布, 易知$ p({{\boldsymbol{x}}_k}, {\lambda _m}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}, {\boldsymbol{z}}_{k, {\lambda _1}:{\lambda _m}}^{{a_j}}) $, $ p({{\boldsymbol{x}}_k}|{Z_{1:k}}) $也为高斯分布. 令
$$ \begin{split} &o({\boldsymbol{x}}_k) = \\ &\quad-\frac{1}{2}{\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^f} \right)^\text{T}}{\left( {P_{k|k - 1}^f} \right)^{ - 1}}\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^f} \right)-\\ &\quad\frac{1}{2}\sum\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {\left[ {{{\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k}^{{n_j}}} \right)}^\text{T}}{{\left( {P_{k|k}^{{n_j}}} \right)}^{ - 1}}\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k}^{{n_j}}} \right)} \right]}\;- \\ &\quad\frac{1}{2}\sum\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {\left[ {{{\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k,{\lambda _m}}^{{a_j}}} \right)}^\text{T}}{{\left( {P_{k|k,{\lambda _m}}^{{a_j}}} \right)}^{ - 1}}\left( {{{\boldsymbol{x}}_k} \;- } \right.} \right.} \\ &\;\;\left. {\left. {\hat {{\boldsymbol{x}}}_{k|k,{\lambda _m}}^{{a_j}}} \right)} \right] + \frac{1}{2}\sum\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {\left[ {{{\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}}} \right)}^\text{T}}{{\left( {P_{k|k}^{{n_j}}} \right)}^{ - 1}}} \right.} \times \\ \end{split} $$ $$\begin{split}&\quad\left. {\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}}} \right)} \right] + \frac{1}{2}\sum\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {\left[ {{{\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^{{a_j}}} \right)}^\text{T}}} \right.} \times\\&\quad \left. {{{\left( {P_{k|k,{\lambda _m}}^{{a_j}}} \right)}^{ - 1}}\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^{{a_j}}} \right)} \right]\end{split} \tag{A1} $$ 根据后验概率密度函数(8), 可得最大后验估计为
$$ \begin{split} \hat {{\boldsymbol{x}}}_{k|k}^f = &\arg \max p({{\boldsymbol{x}}_k}|{Z_{1:k}}) = \\ &\arg \mathop {\max }\limits_{{{\boldsymbol{x}}_k}} o\left( {{{\boldsymbol{x}}_k}} \right) \end{split} \tag{A2}$$ 求解$ \frac{{\partial o\left( {{{\boldsymbol{x}}_k}} \right)}}{{\partial {{\boldsymbol{x}}_k}}} = 0 $, 得全局状态估计为
$$ \begin{split} &{\left( {P_{k|k}^f} \right)^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k}^f = {\left( {P_{k|k - 1}^f} \right)^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^f\;+ \\ &\qquad\sum\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {\left[ {{{\left( {P_{k|k}^{{n_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k}^{{n_j}} - {{\left( {P_{k|k - 1}^{{n_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}}} \right]} \;+ \\ &\qquad\sum\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {\left[ {{{\left( {P_{k|k,{\lambda _m}}^{{a_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k,{\lambda _m}}^{{a_j}}} \right.}\; - \\ &\qquad\left. { {{\left( {P_{k|k - 1}^{{a_j}}} \right)}^{ - 1}}\hat {{\boldsymbol{x}}}_{k|k - 1}^{{a_j}}} \right] \end{split}\tag{A3} $$ $$ \begin{split} &{\left( {P_{k|k}^f} \right)^{ - 1}} = {\left( {P_{k|k - 1}^f} \right)^{ - 1}}\; +\\ & \qquad\sum\limits_{{\boldsymbol{z}}_k^{{n_j}} \in G_k^n} {\left[ {{{\left( {P_{k|k}^{{n_j}}} \right)}^{ - 1}}} \right.} \left. { - \;{{\left( {P_{k|k - 1}^{{n_j}}} \right)}^{ - 1}}} \right] +\\ &\qquad\sum\limits_{{\boldsymbol{z}}_k^{{a_j}} \in G_k^a} {\left[ {{{\left( {P_{k|k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}} - {{\left( {P_{k|k - 1}^{{a_j}}} \right)}^{ - 1}}} \right]} \end{split} \tag{A4}$$ 其中, 由于量测$ {\boldsymbol{z}}_k^{{n_j}} \in G_k^n $中不含额外噪声干扰与野值, 局部状态估计$ \hat {{\boldsymbol{x}}}_{k|k}^{{n_j}} $即可用卡尔曼滤波得到
$$ {\hat{\boldsymbol{x}}_{k|k}^{{n_j}}} = \hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}} + K_k^{{n_j}}\left( {{\boldsymbol{z}}_k^{{n_j}} - H_k^{{n_j}}\hat {{\boldsymbol{x}}}_{k|k - 1}^{{n_j}}} \right) \tag{A5}$$ $$ P_{k|k}^{{n_j}} = \left( {I - K_k^{{n_j}}H_k^{{n_j}}} \right)P_{k|k - 1}^{{n_j}} \tag{A6}$$ $$ K_k^{{n_j}} = P_{k|k}^{{n_j}}{\left( {H_k^{{n_j}}} \right)^\text{T}}{\left( {R_k^{{n_j}}} \right)^{ - 1}}\tag{A7} $$ 对于${\boldsymbol{z}}_k^{{a_j}} \in G_k^a\, ,$ 在其局部状态更新中, 通过PDF式(19), 可求得最大后验状态估计
$$ \begin{split} \hat {{\boldsymbol{x}}}_{k|k}^{{a_j}} = \arg \max p({{\boldsymbol{x}}_k}, {\lambda _m}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}, {\boldsymbol{z}}_{k, {\lambda _1}:{\lambda _m}}^{{a_j}}) \end{split} $$ 根据高斯分布的连乘性质, $p({{\boldsymbol{x}}_k}, {\lambda _m}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}, {\boldsymbol{z}}_{k, {\lambda _1}:{\lambda _m}}^{{a_j}} )$也为高斯分布, 求得
$$ \begin{split} &\hat {{\boldsymbol{x}}}_{k|k, {\lambda _m}}^{{a_j}} = \arg \mathop { \max }\limits_{{{\boldsymbol{x}}_k}} p({{\boldsymbol{x}}_k}, {\lambda _m}|{\boldsymbol{z}}_{1:k - 1}^{{a_j}}, {\boldsymbol{z}}_{k, {\lambda _1}:{\lambda _m}}^{{a_j}}) = \\ &\quad\arg \mathop {\max }\limits_{{{\boldsymbol{x}}_k}} \exp \left\{ - \frac{1}{2}{\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^{{a_j}}} \right)^\text{T}}{\left( {P_{k|k - 1}^{{a_j}}} \right)^{ - 1}}\;\times\right. \end{split} $$ $$ \begin{split} & \quad\left( {{{\boldsymbol{x}}_k} - \hat {{\boldsymbol{x}}}_{k|k - 1}^{{a_j}}} \right) - \frac{1}{2}\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} \left[{{\left( {{\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k}} \right)}^\text{T}} \;\times \right.\\ &\left.\left.\quad{\left( {R_{k, {\lambda _m}}^{{a_j}}} \right)^{ - 1}}\left( {{\boldsymbol{z}}_{k, {\lambda _m}}^{{a_j}} - H_k^{{a_j}}{{\boldsymbol{x}}_k}} \right)\right]\right\} \end{split}\tag{A8} $$ 解法与式(A1) ~ (A4)类似, 得
$$ \begin{split} &{\left( {P_{k|k,{\lambda _m}}^{{a_j}}} \right)^{ - 1}}\hat {\boldsymbol{x}}_{k|k,{\lambda _m}}^{{a_j}} = {\left( {P_{k|k - 1}^{{a_j}}} \right)^{ - 1}}\hat {\boldsymbol{x}}_{k|k - 1}^{{a_j}} \;+\\ & \qquad\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} {\left[ {{{\left( {H_k^{{a_j}}} \right)}^\text{T}}{{\left( {R_{k,{\lambda _m}}^{{a_j}}} \right)}^{ - 1}}{\boldsymbol{z}}_{k,{\lambda _m}}^{{a_j}}} \right]} \end{split}\tag{A9} $$ $$ \begin{split} &{\left( {P_{k|k, {\lambda _m}}^{{a_j}}} \right)^{ - 1}} = {\left( {P_{k|k - 1}^{{a_j}}} \right)^{ - 1}}\;+\\ &\qquad\sum\limits_{m = 1}^{{\varphi _{{\lambda _m}}} < 0} {\left[ {{{\left( {H_k^{{a_j}}} \right)}^\text{T}}{{\left( {R_{k, {\lambda _m}}^{{a_j}}} \right)}^{ - 1}}H_k^{{a_j}}} \right]} \end{split}\tag{A10}$$ □ -
图 8 本文提出的方法和对比算法的平均搜索收敛轨迹
Fig. 8 Averaged search convergence traces of the proposed method and the compared algorithms
表 1 京东数据集的特性
Table 1 Properties of Jingdong dataset
问题 |V| C J $ {u_1} $ $ {u _2} $ F201 ~ F204 200 2.5 500 300 0.014 F401 ~ F404 400 2.5 500 300 0.014 F601 ~ F604 600 2.5 500 300 0.014 F801 ~ F804 800 2.5 500 300 0.014 F1001 ~ F1004 1 000 2.5 500 300 0.014 
下载: 导出CSV
表 2 MBEA算法参数设置
Table 2 Parameter settings in MBEA
参数 含义 值 Evaluation 算法总评价次数 18 000 TE 每阶段的评价次数 3 600 N 种群大小 36 Nre 阶段数 5 Nbe 保留个体的数量 18 k 子任务个数 1 lower 子任务维度最低占比 0.7
下载: 导出CSV
表 3 MBEA和5种对比算法在京东数据集对比实验结果
Table 3 Comparative experimental results of MBEA and five compared algorithms on Jingdong dataset
问题 MBEA EMA MATE CCMO GVNS VNSME NV TD TC 运行
时间 (s)NV TD TC 运行
时间 (s)NV TD TC 运行
时间 (s)NV TD TC 运行
时间 (s)NV TD TC 运行
时间 (s)NV TD TC 运行
时间 (s)F201 43 53 851 66 751 3 291 45 54 918 68 418 4 252 42 53 997 66 597 8 712 51 66 099 81 399 2 976 52 84 808 100 408 81 50 60 494 75 494 3 F202 44 53 155 66 355 3 270 47 56 288 70 388 4 340 43 53 649 66 609 14 194 52 63 782 79 382 2 839 53 67 756 83 656 252 49 59 728 74 428 2 F203 43 54 899 67 679 3 356 46 59 009 72 809 5 416 42 54 544 67 024 13 635 49 67 608 82 308 2 881 51 83 079 98 379 103 51 65 951 81 251 2 F204 43 53 311 66 211 2 983 46 56 456 70 256 3 986 43 54 398 67 238 9 929 48 62 329 76 729 2 970 52 74 571 90 171 300 51 60 415 75 715 2 F401 81 99 380 123 620 11 538 93 120 041 147 941 2 567 84 109 863 135 123 16 852 94 124 412 152 612 8 580 98 144 757 174 157 1 229 96 112 942 141 742 15 F402 84 103 091 128 351 13 338 101 122 636 152 936 2 535 87 113 871 139 971 10 742 100 130 655 160 655 7 923 101 160 822 191 122 268 98 117 970 147 370 12 F403 80 98 175 122 055 12 119 95 122 289 150 789 2 731 84 109 212 134 412 10 154 97 123 599 152 699 8 364 98 160 018 189 418 420 93 111 171 139 071 15 F404 83 99 809 124 649 12 656 95 116 269 144 769 2 694 86 110 555 136 295 13 709 100 127 209 157 209 8 154 101 136 483 166 783 651 94 110 775 138 975 17 F601 118 149 868 185 148 15 779 153 202 915 248 816 2 663 126 174 424 212 344 17 795 148 192 176 236 576 15 623 144 240 941 284 141 702 138 171 997 213 397 41 F602 121 153 129 189 429 19 571 164 204 772 253 972 2 656 129 177 851 216 551 18 839 146 199 278 243 078 15 505 141 227 723 270 023 1 624 143 175 068 217 968 49 F603 120 153 681 189 741 16 090 151 202 985 248 285 2 922 128 176 806 215 146 17 636 151 198 996 244 296 15 032 143 219 879 262 779 395 142 171 057 213 657 37 F604 122 153 477 190 137 18 569 157 204 541 251 641 2 886 128 176 943 215 403 18 789 154 196 028 242 228 15 201 145 204 293 247 793 757 141 172 956 215 256 33 F801 159 175 009 222 709 11 565 200 244 506 304 506 3 679 164 196 076 245 156 20 421 200 234 549 294 549 25 467 189 278 179 334 879 1 654 178 189 502 242 902 82 F802 157 173 598 220 577 13 077 210 226 736 289 736 3 657 164 194 325 243 465 20 835 199 236 794 296 494 25 879 184 271 798 326 998 1 153 179 192 243 245 943 107 F803 159 173 474 221 173 14 682 206 240 358 302 158 3 355 165 195 539 244 919 24 212 201 236 025 296 325 25 387 186 231 297 287 097 1 130 180 188 245 242 245 71 F804 156 171 956 218 756 12 743 213 227 247 291 147 3 324 161 191 853 240 033 21 884 198 226 353 285 753 25 707 181 231 743 286 043 1 490 174 186 214 238 414 81 F1001 212 265 385 329 044 9 698 275 363 035 445 535 3 874 222 293 298 359 838 25 957 279 364 136 447 836 34 957 239 391 293 462 993 1 236 232 278 192 347 792 154 F1002 211 264 034 327 213 8 655 279 356 200 439 900 3 858 225 291 180 358 740 27 482 284 354 899 440 099 34 582 240 352 092 424 092 2 847 234 278 465 348 665 126 F1003 212 265 409 329 008 8 910 275 358 768 441 268 3 917 227 295 806 363 786 26 217 283 359 276 444 176 33 748 243 408 770 481 670 554 231 274 553 343 853 126 F1004 212 262 117 325 656 10 331 285 362 496 447 996 3 914 223 289 035 355 815 26 180 289 360 481 447 181 33 515 234 348 460 418 660 890 233 276 896 346 796 123 最佳/
全部18/20 0/20 2/20 0/20 0/20 0/20
下载: 导出CSV
表 4 RBX和OX的消融实验结果
Table 4 Ablation experiment results of RBX and OX
问题 RBX OX RBX + OX F201 66 517 67 966 66 751 F202 66 365 67 744 66 355 F203 68 948 71 718 67 679 F204 66 970 69 372 66 211 F401 124 851 148 685 123 620 F402 128 798 146 954 128 351 F403 123 550 149 781 122 055 F404 125 247 155 403 124 649 F601 187 048 246 299 185 148 F602 192 623 253 252 189 429 F603 193 915 247 466 189 741 F604 193 410 245 400 190 137 F801 224 758 298 889 222 709 F802 228 345 296 430 220 577 F803 226 138 302 783 221 173 F804 220 988 294 788 218 756 F1001 342 544 442 939 329 044 F1002 339 143 440 007 327 213 F1003 341 946 446 173 329 008 F1004 336 077 445 518 325 656 最佳/全部 1/20 0/20 19/20
下载: 导出CSV
表 5 MBEA中参数lower的敏感性分析
Table 5 Sensitivity analysis of lower in MBEA
问题 TC (0.7) TC (0.5) TC (0.6) TC (0.8) TC (0.9) F201 66 751 66 664 66 926 66 895 66 971 F202 66 355 66 587 66 597 66 677 66 751 F203 67 679 68 206 67 919 68 027 67 783 F204 66 211 66 215 65 920 66 209 66 150 F401 123 620 123 826 123 103 122 861 122 672 F402 128 351 127 154 127 696 127 771 127 986 F403 122 055 122 428 122 703 122 343 122 270 F404 124 649 124 771 125 365 125 138 124 936 F601 185 148 185 831 186 163 185 579 186 371 F602 189 429 190 317 190 661 190 363 190 731 F603 189 741 189 160 189 740 189 986 189 683 F604 190 137 189 300 189 128 189 743 188 712 F801 222 709 221 057 221 905 221 221 220 910 F802 220 577 221 957 220 655 219 998 220 951 F803 221 173 222 172 222 227 221 495 221 377 F804 218 756 218 002 216 628 217 680 218 297 F1001 329 044 330 379 330 059 330 929 329 632 F1002 327 213 327 346 327 565 326 923 327 199 F1003 329 008 329 596 326 035 328 369 327 482 F1004 325 656 325 790 325 812 326 352 327 106 最佳/全部 9/20 3/20 3/20 2/20 3/20
下载: 导出CSV
表 6 MBEA中参数k的敏感性分析
Table 6 Sensitivity analysis of parameter k in MBEA
问题 TC (1) TC (0) TC (2) TC (3) F201 66 751 67 985 66 298 66 731 F202 66 355 67 920 67 002 67 111 F203 67 679 68 180 67 917 67 680 F204 66 211 66 621 66 524 65 730 F401 123 620 124 871 124 825 123 839 F402 128 351 127 377 128 292 127 603 F403 122 055 123 494 122 305 121 883 F404 124 649 126 338 124 959 125 486 F601 185 148 187 055 185 004 187 381 F602 189 429 192 343 192 178 189 516 F603 189 741 190 448 190 047 190 610 F604 190 137 191 208 189 940 189 096 F801 222 709 223 158 223 670 224 248 F802 220 577 222 758 223 576 225 523 F803 221 173 222 456 223 684 223 939 F804 218 756 218 393 217 485 220 373 F1001 329 044 330 374 331 387 332 643 F1002 327 213 329 829 329 525 326 603 F1003 329 008 331 877 330 099 329 200 F1004 325 656 330 725 326 082 331 858 最佳/全部 12/20 1/20 3/20 4/20
下载: 导出CSV
-
[1] Hu M, Liu W D, Peng K, Ma X Q, Cheng W Q, Liu J C, et al. Joint routing and scheduling for vehicle-assisted multidrone surveillance. IEEE Internet of Things Journal, 2019, 6(2): 1781-1790 doi: 10.1109/JIOT.2018.2878602 [2] 杨培颖, 唐加福, 于洋, 裴金翔. 面向最小碳排放量的接送机场服务的车辆路径与调度. 自动化学报, 2013, 39(4): 424-432 doi: 10.1016/S1874-1029(13)60042-7Yang Pei-Ying, Tang Jia-Fu, Yu Yang, Pei Jin-Xiang. Minimizing carbon emissions for vehicle routing and scheduling in picking up and delivering customers to airport service. Acta Automatica Sinica, 2013, 39(4): 424-432 doi: 10.1016/S1874-1029(13)60042-7 [3] 韩月起, 张凯, 宾洋, 秦闯, 徐云霄, 李小川, 等. 基于凸近似的避障原理及无人驾驶车辆路径规划模型预测算法. 自动化学报, 2020, 46(1): 153-167Han Yue-Qi, Zhang Kai, Bin Yang, Qin Chuang, Xu Yun-Xiao, Li Xiao-Chuan, et al. Convex approximation based avoidance theory and path planning MPC for driver-less vehicles. Acta Automatica Sinica, 2020, 46(1): 153-167 [4] 徐杨, 陆丽萍, 褚端峰, 黄子超. 无人车辆轨迹规划与跟踪控制的统一建模方法. 自动化学报, 2019, 45(4): 799-807Xu Yang, Lu Li-Ping, Chu Duan-Feng, Huang Zi-Chao. Unified modeling of trajectory planning and tracking for unmanned vehicle. Acta Automatica Sinica, 2019, 45(4): 799-807 [5] 吴伟, 刘洋, 刘威, 吴国弘, 马万经. 自动驾驶环境下交叉口车辆路径规划与最优控制模型. 自动化学报, 2020, 46(9): 1971-1985Wu Wei, Liu Yang, Liu Wei, Wu Guo-Hong, Ma Wan-Jing. A novel autonomous vehicle trajectory planning and control model for connected-and-autonomous intersections. Acta Automatica Sinica, 2020, 46(9): 1971-1985 [6] Abbatecola L, Fanti M P, Pedroncelli G, Ukovich W. A distributed cluster-based approach for pick-up services. IEEE Transactions on Automation Science and Engineering, 2019, 16(2): 960-971 doi: 10.1109/TASE.2018.2879875 [7] 王素欣, 高利, 崔小光, 曹宏美. 多需求点车辆调度模型及其群体智能混合求解. 自动化学报, 2008, 34(1): 102-104Wang Su-Xin, Gao Li, Cui Xiao-Guang, Cao Hong-Mei. Study on multi-requirement points vehicle scheduling model and its swarm mix algorithm. Acta Automatica Sinica, 2008, 34(1): 102-104 [8] 曾正洋, 许维胜, 徐志宇. 开放式两级车辆路径问题建模与多起始点变邻域下降法求解. 计算机科学, 2014, 41(10): 232-237Zeng Zheng-Yang, Xu Wei-Sheng, Xu Zhi-Yu. Modeling and multi-start variable neighborhood descent solution of two-echelon open vehicle routing problem. Computer Science, 2014, 41(10): 232-237 [9] Kheirkhah A, Navidi H, Bidgoli M M. An improved benders decomposition algorithm for an arc interdiction vehicle routing problem. IEEE Transactions on Engineering Management, 2016, 63(2): 259-273 doi: 10.1109/TEM.2016.2542849 [10] 胡蓉, 李洋, 钱斌, 金怀平, 向凤红. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题. 自动化学报, 2022, 48(12): 3006-3023Hu Rong, Li Yang, Qian Bin, Jin Huai-Ping, Xiang Feng-Hong. An enhanced ant colony optimization combined with clustering decomposition for solving complex green vehicle routing problem. Acta Automatica Sinica, 2022, 48(12): 3006-3023 [11] Xiao J H, Zhang T, Du J G, Zhang X Y. An evolutionary multiobjective route grouping-based heuristic algorithm for large-scale capacitated vehicle routing problems. IEEE Transactions on Cybernetics, 2021, 51(8): 4173-4186 doi: 10.1109/TCYB.2019.2950626 [12] Lin C H, Choy K L, Ho G T S, Chung S H, Lam H Y. Survey of green vehicle routing problem: Past and future trends. Expert Systems With Applications, 2014, 41(4): 1118-1138 doi: 10.1016/j.eswa.2013.07.107 [13] Kassem S, Chen M Y. Solving reverse logistics vehicle routing problems with time windows. The International Journal of Advanced Manufacturing Technology, 2013, 68(1-4): 57-68 doi: 10.1007/s00170-012-4708-9 [14] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 1989, 23(5): 377-386 doi: 10.1016/0191-2607(89)90085-X [15] Dethloff J. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 2001, 23(1): 79-96 doi: 10.1007/PL00013346 [16] Berbeglia G, Cordeau J F, Laporte G. Dynamic pickup and delivery problems. European Journal of Operational Research, 2010, 202(1): 8-15 doi: 10.1016/j.ejor.2009.04.024 [17] Wang H F, Chen Y Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers and Industrial Engineering, 2012, 62(1): 84-95 doi: 10.1016/j.cie.2011.08.018 [18] Eksioglu B, Vural A V, Reisman A. The vehicle routing problem: A taxonomic review. Computers and Industrial Engineering, 2009, 57(4): 1472-1483 doi: 10.1016/j.cie.2009.05.009 [19] 范厚明, 刘鹏程, 刘浩, 侯登凯. 多中心联合配送模式下集货需求随机的VRPSDP问题. 自动化学报, 2021, 47(7): 1646-1660Fan Hou-Ming, Liu Peng-Cheng, Liu Hao, Hou Deng-Kai. The multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution. Acta Automatica Sinica, 2021, 47(7): 1646-1660 [20] 陈萍, 黄厚宽, 董兴业. 求解卸装一体化的车辆路径问题的混合启发式算法. 计算机学报, 2008, 31(4): 565-73Chen Ping, Huang Hou-Kuan, Dong Xing-Ye. A hybrid heuristic algorithm for the vehicle routing problem with simultaneous delivery and pickup. Chinese Journal of Computers, 2008, 31(4): 565-573 [21] Gupta A, Heng C K, Ong Y S, Tan P S, Zhang A N. A generic framework for multi-criteria decision support in eco-friendly urban logistics systems. Expert Systems with Applications, 2017, 71: 288-300 doi: 10.1016/j.eswa.2016.09.033 [22] Wang J H, Weng T Y, Zhang Q F. A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows. IEEE Transactions on Cybernetics, 2019, 49(7): 2467-2478 doi: 10.1109/TCYB.2018.2821180 [23] Wang C, Mu D, Zhao F, Sutherland J W. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Computers & Industrial Engineering, 2015, 83: 111-122 [24] Mingyong L, Erbao C. An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 2010, 23(2): 188-195 doi: 10.1016/j.engappai.2009.09.001 [25] 黄务兰, 张涛. 基于改进全局人工鱼群算法的VRPSPDTW研究. 计算机工程与应用, 2016, 52(21): 21-29Huang Wu-Lan, Zhang Tao. Vehicle routing problem with simultaneous pick-up and delivery and time-windows based on improved global artificial fish swarm algorithm. Computer Engineering and Applications, 2016, 52(21): 21-29 [26] Shi Y, Zhou Y J, Boudouh T, Grunder O. A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup-delivery and time window. Engineering Applications of Artificial Intelligence, 2020, 95: Article No. 103901 [27] Hof J, Schneider M. An adaptive large neighborhood search with path relinking for a class of vehicle-routing problems with simultaneous pickup and delivery. Networks, 2019, 74(3): 207-250 doi: 10.1002/net.21879 [28] Iqbal M, Xue B, Al-Sahaf H, Zhang M J. Cross-domain reuse of extracted knowledge in genetic programming for image classification. IEEE Transactions on Evolutionary Computation, 2017, 21(4): 569-587 doi: 10.1109/TEVC.2017.2657556 [29] Di S, Zhang H G, Li C G, Mei X, Prokhorov D, Ling H B. Cross-domain traffic scene understanding: A dense correspondence-based transfer learning approach. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(3): 745-757 doi: 10.1109/TITS.2017.2702012 [30] Chalmers E, Contreras E B, Robertson B, Luczak A, Gruber A. Learning to predict consequences as a method of knowledge transfer in reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(6): 2259-2270 doi: 10.1109/TNNLS.2017.2690910 [31] Gupta A, Ong Y S, Feng L. Multifactorial evolution: Toward evolutionary multitasking. IEEE Transactions on Evolutionary Computation, 2016, 20(3): 343-357 doi: 10.1109/TEVC.2015.2458037 [32] Gupta A, Ong Y S, Feng L, Tan K C. Multiobjective multifactorial optimization in evolutionary multitasking. IEEE Transactions on Cybernetics, 2017, 47(7): 1652-1665 doi: 10.1109/TCYB.2016.2554622 [33] Bali K K, Ong Y S, Gupta A, Tan P S. Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2020, 24(1): 69-83 doi: 10.1109/TEVC.2019.2906927 [34] Hao X X, Qu R, Liu J. A unified framework of graph-based evolutionary multitasking hyper-heuristic. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 35-47 doi: 10.1109/TEVC.2020.2991717 [35] Feng L, Zhou L, Gupta A, Zhong J H, Zhu Z X, Tan K C, et al. Solving generalized vehicle routing problem with occasional drivers via evolutionary multitasking. IEEE Transactions on Cybernetics, 2021, 51(6): 3171-3184 doi: 10.1109/TCYB.2019.2955599 [36] Feng L, Huang Y X, Zhou L, Zhong J H, Gupta A, Tang K, et al. Explicit evolutionary multitasking for combinatorial optimization: A case study on capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 2021, 51(6): 3143-3156 doi: 10.1109/TCYB.2019.2962865 [37] Feng L, Zhou L, Zhong J H, Gupta A, Ong Y S, Tan K C, et al. Evolutionary multitasking via explicit autoencoding. IEEE Transactions on Cybernetics, 2019, 49(9): 3457-3470 doi: 10.1109/TCYB.2018.2845361 [38] Feng L, Huang Y X, Tsang I W, Gupta A, Tang K, Tan K C, et al. Towards faster vehicle routing by transferring knowledge from customer representation. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(2): 952-965 doi: 10.1109/TITS.2020.3018903 [39] Shang Q X, Huang Y X, Wang Y, Li M, Feng L. Solving vehicle routing problem by memetic search with evolutionary multitasking. Memetic Computing, 2022, 14(1): 31-44. doi: 10.1007/s12293-021-00352-7 [40] Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 2016, 99: 300-313 [41] Huang M F, Hu X P. Large scale vehicle routing problem: An overview of algorithms and an intelligent procedure. International Journal of Innovative Computing, Information and Control, 2012, 8(8): 5809-5819 [42] Shin K, Han S Y. A centroid-based heuristic algorithm for the capacitated vehicle routing problem. Computing and Informatics, 2011, 30(4): 721-732 [43] Angelelli E, Mansini R. The vehicle routing problem with time windows and simultaneous pick-up and delivery. Quantitative Approaches to Distribution Logistics and Supply Chain Management. Berlin: Springer, 2002. 249−267 [44] Dell'Amico M, Righini G, Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science, 2006, 40(2): 235-247 doi: 10.1287/trsc.1050.0118 [45] Rieck J, Zimmermann J. Exact solutions to the symmetric and asymmetric vehicle routing problem with simultaneous delivery and pick-up. Business Research, 2013, 6(1): 77-92 doi: 10.1007/BF03342743 [46] Subramanian A, Uchoa E, Pessoa A A, Ochi L S. Branch-cut-and-price for the vehicle routing problem with simul-taneous pickup and delivery. Optimization Letters, 2013, 7(7): 1569-1581 doi: 10.1007/s11590-012-0570-9 [47] Cao W J, Yang W S. A survey of vehicle routing problem. MATEC Web of Conferences, 2017, 100: Article No. 01006 [48] Elshaer R, Awad H. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers and Industrial Engineering, 2020, 140: Article No. 106242 [49] Yu V F, Redi A A N P, Hidayat Y A, Wibowo O J. A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 2017, 53: 119-132 doi: 10.1016/j.asoc.2016.12.027 [50] Schermer D, Moeini M, Wendt O. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, 2019, 109: 134-158 [51] Ribeiro G M, Laporte G. An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 2012, 39(3): 728-735 [52] Avci M, Topaloglu S. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with sim-ultaneous pickup and delivery. Expert Systems with Applications, 2016, 53: 160-171 doi: 10.1016/j.eswa.2016.01.038 [53] Zhou Y, Kong L J, Cai Y Q, Wu Z Y, Liu S P, Hong J M, et al. A decomposition-based local search for large-scale many-objective vehicle routing problems with simultaneous delivery and pickup and time windows. IEEE Systems Journal, 2020, 14(4): 5253-5264 doi: 10.1109/JSYST.2019.2959664 [54] Baker B M, Ayechew M A. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 2003, 30(5): 787-800 [55] Mohammed M A, Abd Ghani M K, Hamed R I, Mostafa S A, Ahmad M S, Ibrahim D A. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science, 2017, 21: 255-262 doi: 10.1016/j.jocs.2017.04.003 [56] Sabar N R, Bhaskar A, Chung E, Turky A, Song A. An adaptive memetic approach for heterogeneous vehicle routing problems with two-dimensional loading constraints. Swarm and Evolutionary Computation, 2020, 58: Article No. 100730 [57] Ouaddi K, Mhada F, Benadada Y. Memetic algorithm for multi-tours dynamic vehicle routing problem with overtime (MDVRPOT). International Journal of Industrial Engineering Computations, 2020, 11(4): 643-662 [58] Zhang X Y, Duan H B. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Applied Soft Computing, 2015, 26: 270-284 doi: 10.1016/j.asoc.2014.09.046 [59] Venkatesan S R, Logendran D, Chandramohan D. Optimization of capacitated vehicle routing problem using PSO. International Journal of Engineering Science and Technology, 2011, 3(10): 7469-7477 [60] Yu B, Yang Z Z, Yao B Z. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009, 196(1): 171-176 doi: 10.1016/j.ejor.2008.02.028 [61] Lee C Y, Lee Z J, Lin S W, Ying K C. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 2010, 32(1): 88-95 doi: 10.1007/s10489-008-0136-9 [62] Liu S C, Tang K, Yao X. Memetic search for vehicle routing with simultaneous pickup-delivery and time windows. Swarm and Evolutionary Computation, 2021, 66: Article No. 100927 [63] Ma Y F, Li Z M, Yan F, Feng C Y. A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers. Soft Computing, 2019, 23(15): 6697-6714 doi: 10.1007/s00500-019-03754-5 [64] Wang J H, Zhou Y, Wang Y, Zhang J, Chen C L P, Zheng Z B. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: Formulation, instances, and algorithms. IEEE Transactions on Cybernetics, 2016, 46(3): 582-594 doi: 10.1109/TCYB.2015.2409837 [65] Lagos C, Guerrero G, Cabrera E, Moltedo A, Johnson F, Paredes F. An improved particle swarm optimization algorithm for the VRP with simultaneous pickup and delivery and time windows. IEEE Latin America Transactions, 2018, 16(6): 1732-1740 doi: 10.1109/TLA.2018.8444393 [66] Potvin J Y, Bengio S. The vehicle routing problem with time windows Part Ⅱ: Genetic search. INFORMS Journal on Computing, 1996, 8(2): 165-172 doi: 10.1287/ijoc.8.2.165 [67] Oliver I M, Smith D J, Holland J R C. A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Cambridge, USA: L. Erlbaum Associates Inc., 1987. [68] Tian Y, Zhang T, Xiao J H, Zhang X Y, Jin Y C. A coevolutionary framework for constrained multiobjective opti-mization problems. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 102-116 doi: 10.1109/TEVC.2020.3004012 [69] Fleszar K, Osman I H, Hindi K S. A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 2009, 195(3): 803-809 doi: 10.1016/j.ejor.2007.06.064 [70] Cai J C, Zhu Q L, Lin Q Z. Variable neighborhood search for a new practical dynamic pickup and delivery problem. Swarm and Evolutionary Computation, 2022, 75: Article No. 101182 期刊类型引用(3)
1. 朱荣花，刘永超. 物流管理系统中基于改进遗传算法的车辆路径选择研究. 自动化与仪器仪表. 2025(02): 198-202 . 
百度学术2. 谭信，李寿荣，王翔，李婷. 基于改进NSGA-Ⅲ算法的车辆路径自动化规划分析. 自动化与仪器仪表. 2025(02): 243-246+251 . 百度学术3. 赵佳伟，陈雪峰，冯亮，候亚庆，朱泽轩，Ong Yew-Soon. 优化场景视角下的进化多任务优化综述. 计算机应用. 2024(05): 1325-1337 . 百度学术其他类型引用(2)
-
下载:
计量
- 文章访问数: 859
- HTML全文浏览量: 254
- PDF下载量: 291
- 被引次数: 5
