基于聚类趋向性原理的气味源自主搜索及定位方法

摘要

本发明公开了一种基于聚类趋向性原理的气味源自主搜索及定位方法，本发明包括构建气体正向扩散模型和传感器探测模型；对气味源的搜索过程进行建模，划分为源项估计、行动决策和执行行动；利用粒子滤波逼近表示源项估计的后验概率密度函数，将源项估计的更新转化为粒子滤波的更新；利用基于密度的聚类算法对投影在二维平面上的粒子进行聚类；利用聚类簇信息为移动机器人的行动设计聚类趋向性行动策略。本发明采用了基于聚类趋向性原理，利用基于密度的聚类算法提取源项估计中的簇信息，并基于这些信息来指导移动机器人的行动，本发明无需复杂的奖励函数来进行决策，因此计算量要远小于认知搜索策略，在实际场景中的实用性更好。

说明书

技术领域

面向气体泄漏源的移动机器人自主搜索及定位技术，具体涉及一种基于聚类趋向性原理的气味源自主搜索及定位方法，可用于有害气体源定位，气态危化品泄漏源自主搜索等多场景、多种类气味源的自主搜索和定位任务。

背景技术

在人类社会的生产生活中，有许多需要对未知气味源进行搜索和准确定位的任务。例如搜索天然气泄漏口以避免更严重事故的发生；在突发的气态危化品泄漏事故中快速搜索和定位泄漏源，使得应急处置工作得到及时开展等。现有方法一般利用携带传感器的移动机器人进行搜索，并采用相应的自主搜索算法来指导它们进行感知和搜索行为，该方法被统称为寻源方法。

自上世纪80年代以来，研究人员就开始研究各种自主搜索算法。一般来说，自主搜索算法可分为三种：基于梯度的算法，基于仿生学原理的算法和基于概率和映射的算法。基于梯度的算法和基于仿生学原理的算法原理较为简单，所需计算量较小，但它们都依赖于浓度梯度。然而在现实中，由于湍流效应的影响，稳定的气体羽流会被分割为间断的，零星的气团。在这样的情况下，上述两种自主搜索算法将会严重失效。

基于概率和映射的算法利用概率密度函数来估计源位置等源项参数，并利用移动传感器不断收集相关信息来更新概率密度函数，从而获得更准确的估计。该种方法可以对湍流条件下的气体扩散模式进行建模，从而能够在该条件下进行准确的寻源。Infotaxis算法是一种典型的基于概率和映射的算法，该算法采取基于信息熵的奖励函数来平衡利用和开发问题，并指导移动传感器在每一步都选择移动到信息增益最大的临近位置。有研究者进一步将寻源过程建模为部分可观马尔科夫决策过程，并利用粒子滤波改进原本基于网格的Infotaxis算法，同时将这类利用信息熵作为奖励函数的自主搜索算法统称为认知搜索策略。Entrotaxis算法采用了Infotaxis算法的序贯蒙特卡洛框架，并根据最大熵采样原则设计了计算效率更高的奖励函数。该奖励函数用来计算未来探测值的不确定程度，从而指导移动传感器在每一步中都前往不确定程度最大的相邻位置，以收集到更多的源项信息。

认知搜索策略在每一步都需要较为复杂的计算来支撑决策，从而导致整体的寻源时间增长。而在实际的寻源应用中，寻源速度往往和寻源准确率一样重要。因此，认知搜索策略在实际应用中将受到严重的限制。然而该种方法所采用的基于粒子滤波的序贯蒙特卡洛框架可以将收集到的间断的、零星的源项信息融合为对于源项参数的估计，这使得认知搜索算法能在湍流效应中保持较好的搜索性能。

发明内容

本发明要解决的技术问题：针对现有技术的上述问题，提供一种基于聚类趋向性原理的气味源自主搜索及定位方法，本发明采用基于聚类趋向性原理的方法，利用基于密度的聚类算法提取源项估计中的簇信息，并基于这些信息来指导移动机器人的行动，本发明无需复杂的奖励函数来进行决策，因此计算量要远小于认知搜索策略，在实际场景中的实用性更好。

为了解决上述技术问题，本发明采用的技术方案为：

一种基于聚类趋向性原理的气味源自主搜索及定位方法，包括：

1)构建气体正向扩散模型和传感器探测模型；

2)对气味源的搜索过程进行建模，划分为源项估计、行动决策和执行行动三个部分；

3)利用粒子滤波逼近用于表示源项估计的后验概率密度函数，并将气味源的搜索过程中的源项估计的更新转化为粒子滤波的更新；

4)利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类，得到聚类簇信息；

5)利用得到的聚类簇信息为移动机器人的行动设计聚类趋向性行动策略。

可选地，步骤1)构建得到的气体正向扩散模型的函数表达式为：

上式中，R(r|θ

步骤1)构建得到的传感器探测模型的函数表达式为：

上式中，P(d(r)|θ

可选地，步骤2)中对气味源的搜索过程进行建模的步骤包括：

2.1)源项估计：依据关于气味源的先验信息构建初始的源项估计，初始的源项估计采用概率密度函数P(θ

2.2)行动决策：根据初始的源项估计，按照预设的行动策略得到行动指令；

2.3)执行行动：移动机器人执行完行动指令并移动到新的位置，移动机器人收集新的信息；根据新的信息，基于贝叶斯后验概率公式对源项估计进行更新，得到新的源项估计P(θ

可选地，步骤3)包括：

3.1)基于粒子滤波的源项估计表示：对后验概率密度函数P(θ

上式中，δ(·)表示狄利克雷函数；

3.2)基于粒子滤波的源项估计更新：引入重要性函数q(θ

上式中，

3.3)重采样步骤：在保持粒子总数不变的情况下，将权重大的粒子按权重加以复制来代替无效粒子，达到删除小权重粒子、复制大权重粒子的目的；

3.4)马尔科夫链蒙特卡洛步骤：采用基于马尔科夫链蒙特卡洛方法的Metropolis-Hastings采样算法来增加粒子多样性。

可选地，步骤4)中利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类的步骤包括：利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子，将粒子滤波中粒子分布较为密集的区域聚类识别为聚类簇，且聚类的参数为Eps邻域，其中Eps邻域的定义函数表达式为：

N

上式中，N

可选地，步骤5)中的详细步骤包括：

5.1)针对得到的聚类簇进行有效簇判断：若某聚类簇中含有的粒子占总粒子数的比例超过阈值，则判定该聚类簇为有效簇；

5.2)选定目标簇：若在某个寻源阶段，若场景中存在有效簇，则最大有效簇所在区域即为是目标簇；若场景中不存在有效簇，则会将整个粒子簇作为目标簇；

5.3)移动机器人会采取固定步长向目标簇的均值点移动，一旦到达均值点，会采取方形搜索探查整个目标簇，直到下一个目标簇的出现或是寻源终止。

此外，本发明还提供一种基于聚类趋向性原理的气味源自主搜索及定位系统，包括：

模型构建程序单元，用于构建气体正向扩散模型和传感器探测模型；

搜索过程建模程序单元，用于对气味源的搜索过程进行建模，划分为源项估计、行动决策和执行行动三个部分；

粒子滤波更新程序单元，用于利用粒子滤波逼近用于表示源项估计的后验概率密度函数，并将气味源的搜索过程中的源项估计的更新转化为粒子滤波的更新；

密度聚类程序单元，用于利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类，得到聚类簇信息；

行动策略设计程序单元，用于利用得到的聚类簇信息为移动机器人的行动设计聚类趋向性行动策略。

此外，本发明还提供一种基于聚类趋向性原理的气味源自主搜索及定位系统，包括计算机设备，该计算机设备包括相互连接的微处理器和存储器，所述微处理器被编程或配置以执行所述基于聚类趋向性原理的气味源自主搜索及定位方法的步骤。

此外，本发明还提供一种基于聚类趋向性原理的气味源自主搜索及定位系统，包括计算机设备，该计算机设备包括相互连接的微处理器和存储器，所述存储器中存储有被编程或配置以执行所述基于聚类趋向性原理的气味源自主搜索及定位方法的计算机程序。

此外，本发明还提供一种计算机可读存储介质，该计算机可读存储介质中存储有被编程或配置以执行所述基于聚类趋向性原理的气味源自主搜索及定位方法的计算机程序。

和现有技术相比，本发明具有下述优点：本发明包括构建气体正向扩散模型和传感器探测模型；对气味源的搜索过程进行建模，划分为源项估计、行动决策和执行行动三个部分；利用粒子滤波逼近用于表示源项估计的后验概率密度函数，并将气味源的搜索过程中的源项估计的更新转化为粒子滤波的更新；利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类，得到聚类簇信息；利用得到的聚类簇信息为移动机器人的行动设计聚类趋向性行动策略。本发明采用了基于聚类趋向性原理的方法，利用基于密度的聚类算法提取源项估计中的簇信息，并基于这些信息来指导移动机器人的行动，本发明无需复杂的奖励函数来进行决策，因此计算量要远小于认知搜索策略，在实际场景中的实用性更好。

附图说明

图1为本发明实施例方法的基本流程示意图。

图2为本发明实施例方法步骤2)中的自主寻源过程。

图3为本发明实施例方法步骤3)中的粒子滤波更新过程。

图4为本发明实施例方法步骤4)中的基于密度的聚类算法流程图。

图5为本发明实施例方法步骤5)中的最大有效簇示意图。

图6为本发明实施例方法步骤5)中的方形搜索示意图。

图7为本发明实施例方法步骤5)中的基于聚类信息进行行动决策流程图。

具体实施方式

下文以搜索有害气体泄漏源搜索与定位任务为例，对本实施例的基于聚类趋向性原理的气味源自主搜索及定位方法进行详细说明。需要说明的是，本实施例仅仅是以有害气体泄漏源搜索与定位任务为例进行说明，毫无疑问地，本实施例还可以应用到其它各种需要对气味源进行搜索与定位的场景，在此不再赘述。

如图1所示，本实施例基于聚类趋向性原理的气味源自主搜索及定位方法包括：

1)构建气体正向扩散模型和传感器探测模型；

2)对气味源的搜索过程进行建模，划分为源项估计、行动决策和执行行动三个部分；

3)利用粒子滤波逼近用于表示源项估计的后验概率密度函数，并将气味源的搜索过程中的源项估计的更新转化为粒子滤波的更新；

4)利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类，得到聚类簇信息；

5)利用得到的聚类簇信息为移动机器人的行动设计聚类趋向性行动策略。

本实施例中步骤1)中具体为依据对流扩散模型构建气体正向扩散模型，并考虑湍流因素和传感器测量误差影响下的传感器探测模型。

步骤1)构建得到的气体正向扩散模型的函数表达式为：

上式中，R(r|θ

若搜索场景中存在一个未知的气味源，其坐标为θ

步骤1)构建得到的传感器探测模型的函数表达式为：

上式中，P(d(r)|θ

如图2所示，本实施例中步骤2)中对气味源的搜索过程进行建模的步骤包括：

2.1)源项估计：依据关于气味源的先验信息构建初始的源项估计，初始的源项估计采用概率密度函数P(θ

2.2)行动决策：根据初始的源项估计，按照预设的行动策略得到行动指令；

2.3)执行行动：移动机器人执行完行动指令并移动到新的位置，移动机器人收集新的信息；根据新的信息，基于贝叶斯后验概率公式对源项估计进行更新，得到新的源项估计P(θ

如图3所示，本实施例中步骤3)包括：

3.1)基于粒子滤波的源项估计表示：由于在步骤2)中的基于后验概率密度函数的源项估计是非线性的，很难求得解析解，因此采用粒子滤波来近似表示源项估计。本实施例中，对后验概率密度函数P(θ

上式中，δ(·)表示狄利克雷函数；

3.2)基于粒子滤波的源项估计更新：由于后验概率密度函数P(θ

上式中，

上式中，

3.3)重采样步骤：在保持粒子总数不变的情况下，将权重大的粒子按权重加以复制来代替无效粒子，达到删除小权重粒子、复制大权重粒子的目的；

在粒子滤波中，普遍存在粒子退化的问题，即经过若干次迭代后，除少部分粒子权值较大，大多数粒子权值小到可以忽略不计，并且粒子权值的方差随时间增大。把粒子权重可以小到忽略不计的粒子称为无效粒子，随着无效粒子数目的增加，大量计算耗费在对估计后验概率密度函数几乎不起作用的粒子上，使得粒子滤波估计性能下降。重采样也称再采样，其目的在于减少无效粒子的数目。在保持粒子总数不变的情况下，将权重大的粒子按权重加以复制，来代替无效粒子。简而言之就是删除小权重粒子，复制大权重粒子。重采样的基本过程就是对现有粒子集近似的随机离散型概率分布列重新采样得到新的样本集，并且新的样本集中每个粒子的权值相等。

3.4)马尔科夫链蒙特卡洛步骤：采用基于马尔科夫链蒙特卡洛方法的Metropolis-Hastings采样算法来增加粒子多样性。

在进行重采样步骤后又会引发一个新的问题。重采样导致粒子多样性丢失，在若干次迭代后，所有粒子可能都变为了某几个粒子的复制。此外，由于一开始所有粒子对源项参数的点估计都可能存在误差，而通过更新粒子滤波无法减小或消除这种误差。因此，需要通过增加粒子多样性来解决此问题，本实施例在重采样后，采用基于马尔科夫链蒙特卡洛方法的Metropolis-Hastings采样算法来增加粒子多样性。

如图4所示，本实施例步骤4)中利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类的步骤包括：利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子，将粒子滤波中粒子分布较为密集的区域聚类识别为聚类簇，且聚类的参数为Eps邻域，其中Eps邻域的定义函数表达式为：

N

上式中，N

基于密度的聚类算法用一组关于“邻域”的参数来描述样本分布的紧密程度，该算法主要术语定义如下：

Eps邻域：给定一个样本p∈D，则p的Eps邻域N

核心点、边界点：对于样本p，给定一个整数MinPts，若p的Eps邻域内包含了至少MinPts个样本，即|N

密度直达：对于样本p、q，若q为核心点，且p落入了q的Eps邻域，则称样本p是从样本q出发密度直达的。密度直达不具有对称性，即样本q不一定是从样本p出发密度直达的。

密度可达：当存在一个样本链p

密度相连：若存在样本o∈D，使得样本p和q都是从样本o出发密度可达的，则称样本p和q是密度相连的。密度相连具有对称性。

簇和噪声点：对于样本集D，簇C是D的一个非空子集，是由密度可达关系导出的最大的密度相连样本集合，即满足下列条件：

条件1：对于所有p,q∈D，若p∈C并且q是从p出发密度可达的，则q∈C。

条件2：对于所有p,q∈C，p和q是密度相连的。

对于不属于任何簇的样本，则定义该样本为噪声点。

图4为本发明实施例方法步骤4)中的基于密度的聚类算法流程图。步骤4)中利用基于密度的聚类算法，可以将粒子滤波中粒子分布较为密集的区域识别为聚类簇，基于这类聚类簇的信息，可以支撑移动机器人的行动决策。

本实施例步骤5)中的详细步骤包括：

5.1)针对得到的聚类簇进行有效簇判断：若某聚类簇中含有的粒子占总粒子数的比例超过阈值，则判定该聚类簇为有效簇；

在每一个时间步中，机器人都会选择一个目标簇进行趋近和探查，因此，本方法被称为聚类趋向性方法。对于给定的一组表示当前源项估计的粒子，采用基于密度的聚类算法对该组粒子进行聚类，所有簇中包含粒子最多的簇称为最大簇。通常情况下，最大簇区域可被认为是泄漏源最可能存在的区域，并作为目标簇。然而在某些情况下，最大簇所包含的粒子数量占总粒子数的比例非常小，所提供的信息不足以表明泄漏源位于该区域。例如在寻源的最初阶段，收集到的信息并没有使粒子滤波有明显的收敛现象，此时的簇可能只是由多个随机散布的粒子构成的。因此定义有效簇的概念：某簇中含有的粒子占总粒子数的比例超过阈值，则称该簇为有效簇。有效簇的概念是为了减小误判的可能性，即在没有一定的把握的情况下，不盲目的进行探索，而是继续收集信息来增加源项估计的准确性。有效簇中包含粒子最多的簇被称为最大有效簇，其示意图见图5。

5.2)选定目标簇：若在某个寻源阶段，若场景中存在有效簇，则最大有效簇所在区域即为是目标簇；若场景中不存在有效簇，则会将整个粒子簇作为目标簇；

若在某个寻源阶段，存在有效簇，则最大有效簇所在区域即为是目标簇；若场景中不存在有效簇，则会将整个粒子簇作为目标簇。

5.3)移动机器人会采取固定步长向目标簇的均值点移动，一旦到达均值点，会采取方形搜索探查整个目标簇，直到下一个目标簇的出现或是寻源终止。

一旦选定目标簇。移动机器人会采取固定步长向目标簇的均值点移动，一旦到达均值点，会采取方形搜索探查整个目标簇，直到下一个目标簇的出现或是寻源终止。方形搜索模型如图6所示，完整的聚类趋向性行动策略流程如图7所示。

综上所述，本实施例基于聚类趋向性原理的气味源自主搜索及定位方法步骤1)中，为了充分利用气味源释放到空气中的相关信息和风场等环境信息，需要首先对气体的正向扩散模式进行建模。本步骤可参考一些现有的和较为成熟的扩散模型。例如常用的半经验型高斯模型，基于对流扩散方程导出的对流扩散模型，还有基于流体力学分析方法的流体力学模型。考虑到一般的源搜索任务具有十分严苛的时间要求，在建立模型时，需要考虑计算精确度与计算效率的权衡。步骤2)中，采用寻源方法进行自主搜索气味源的过程一般被建模为一个序贯决策过程：自主寻源算法在每一步都会引导移动机器人采取一个动作，例如移动到当前位置的相邻位置。移动机器人利用传感器在新的位置上进行探测，并提取探测值中的信息，辅助下一步的移动决策。重复此过程，移动机器人最终可移动到气味源附件，并执行源确认。由于在此过程中气味源实际位置是未知的，需要在整个过程中同时进行源项信息(源位置)的估计。步骤3)中，基于贝叶斯框架，可以将每一步收集到信息整合到源项估计中。为了更加灵活的表示估计，可采用粒子滤波来表示源项估计的迭代更新。粒子滤波采用一组带权重的粒子来近似表示概率密度函数，即源项估计。每个粒子都表示了源项参数的一个点估计，其权重代表了该点估计为真实值的可能性。而源项估计的更新可以被转化为粒子权重的更新。为了保持粒子多样性和避免粒子退化，还可在更新过程中加入重采样步骤和马尔科夫链蒙特卡洛步骤。步骤4)中，基于粒子滤波中每个粒子的点估计，可以将粒子投影到搜索区域所在的二维平面，则整个粒子集会在二维平面上呈现一定的空间分布。在当前源项估计下，粒子越密集的地方，则表示泄漏源位于该位置的可能性越大。利用基于密度的聚类算法够把具有足够高密度的区域划分为簇，并可在有噪声的数据集中发现任意形状的聚类簇。步骤5)中，根据步骤4)中提取出的聚类簇相关信息，可以辅助移动机器人进行行动决策。例如某个局部区域所包含的粒子的疏密程度反映了实际源项参数落入该区域的可能性，因此可以通过寻找粒子密度最高的区域来确定泄漏源最可能存在的位置。然而这种移动方式可能存在着诸多问题，需要为机器人的行动决策制定更加高效的策略。因此，本实施例基于聚类趋向性原理的气味源自主搜索及定位方法提取粒子滤波粒子分布的信息，和基于该信息设计的聚类趋向性行动策略。本实施例基于聚类趋向性原理的气味源自主搜索及定位方法可以实现对未知气味源的快速准确搜索与定位。本实施例基于聚类趋向性原理的气味源自主搜索及定位方法相比于以往的方法，搜索性能更好，计算效率更高，因此具有更强的实用价值。本实施例基于聚类趋向性原理的气味源自主搜索及定位方法具有实用性强，应用前景广，效率高，搜索速度快等优点。

此外，本实施例还提供一种基于聚类趋向性原理的气味源自主搜索及定位系统，包括：

模型构建程序单元，用于构建气体正向扩散模型和传感器探测模型；

搜索过程建模程序单元，用于对气味源的搜索过程进行建模，划分为源项估计、行动决策和执行行动三个部分；

粒子滤波更新程序单元，用于利用粒子滤波逼近用于表示源项估计的后验概率密度函数，并将气味源的搜索过程中的源项估计的更新转化为粒子滤波的更新；

密度聚类程序单元，用于利用基于密度的聚类算法对投影在二维平面上的粒子滤波中的粒子进行聚类，得到聚类簇信息；

行动策略设计程序单元，用于利用得到的聚类簇信息为移动机器人的行动设计聚类趋向性行动策略。

此外，本实施例还提供一种基于聚类趋向性原理的气味源自主搜索及定位系统，包括计算机设备，该计算机设备包括相互连接的微处理器和存储器，所述微处理器被编程或配置以执行前述基于聚类趋向性原理的气味源自主搜索及定位方法的步骤。

此外，本实施例还提供一种基于聚类趋向性原理的气味源自主搜索及定位系统，包括计算机设备，该计算机设备包括相互连接的微处理器和存储器，所述存储器中存储有被编程或配置以执行前述基于聚类趋向性原理的气味源自主搜索及定位方法的计算机程序。

此外，本实施例还提供一种计算机可读存储介质，该计算机可读存储介质中存储有被编程或配置以执行前述基于聚类趋向性原理的气味源自主搜索及定位方法的计算机程序。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可读存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

以上所述仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。