太阳城集团

  • / 8
  • 下载费用:30 金币  

一种基于树分解的智能搜捕方法.pdf

摘要
申请专利号:

CN201611047818.4

申请日:

2016.11.25

公开号:

CN106779169A

公开日:

2017.05.31

当前法律状态:

实审

有效性:

审中

法律详情: 实质审查的生效IPC(主分类):G06Q 10/04申请日:20161125|||公开
IPC分类号: G06Q10/04(2012.01)I; G06N5/00 主分类号: G06Q10/04
申请人: 中国人民解放军63880部队
发明人: 米士超; 白永强; 鲁刚; 杜嘉薇; 郭荣华
地址: 471003 河南省洛阳市涧西区周山路17号085信箱11号
优先权:
专利代理机构: 北京中海智圣知识产权代理有限公司 11282 代理人: 胡静
PDF完整版下载: PDF下载
法律状态
申请(专利)号:

太阳城集团CN201611047818.4

授权太阳城集团号:

|||

法律状态太阳城集团日:

2017.06.23|||2017.05.31

法律状态类型:

实质审查的生效|||公开

摘要

太阳城集团本发明公开了基于树分解的智能搜捕方法,包括以下步骤:(1)获取目标环境,根据搜捕者的感知能力将监测环境转换为拓扑图;(2)环境拓扑图的树分解;(3)求解拓扑图树宽;(4)求解基于树分解的搜捕算法;(5)求解搜捕者数量最小上界;本发明的优点是提出了以最小搜捕者数量及追捕的有效性为优化目标的移动传感网搜捕的技术方案,本发明基于树分解的方法对环境进行搜素,避免了搜索过程中入侵者的重复侵入,能提高搜索效率并减少了搜捕过程中的能量开销。

权利要求书

1.一种基于树分解的智能搜捕方法,其特征在于,包括以下步骤:
(1)获取目标环境,根据搜捕者的感知能力将监测环境转换为拓扑图;
(2)环境拓扑图的树分解;
(3)求解拓扑图树宽;
(4)求解基于树分解的搜捕算法;
(5)求解搜捕者数量最小上界。
2.根据权利要求1所述的一种基于树分解的智能搜捕方法,其特征在于,所述步骤(1)
中,获取目标环境,根据搜捕者的感知能力和移动速度将环境离散化为有限图,根据智能体
的感知能力将环境离散化为单元,使得每个搜捕者能够监测环境离散化后的每一个单元,
若入侵者进入此单元,搜捕者能够及时对其进行捕获,用顶点代替单元,相邻的单元之间插
入一条边,目标环境离散化为图G=(V,E)表示,其中图G为无向连通,V表示顶点集,|V|表示
顶点的个数,E表示边集。
3.根据权利要求1所述的一种基于树分解的智能搜捕方法,其特征在于,所述步骤(2)
中,在图G=(V,E)中选取路径L,且L中包含顶点集V中的两个端点,对图G按如下方式进行树
分解:
图G=(V,E)的一个树分解为(TL,X),X={Xi|i∈I},其中I是V的一个子集族,TL是指以I
为顶点集的树,TL中的节点是X的子集,路径L为图G中端点v1到vK的连接路径,路径L中包含K
个节点v1,v2,...,vK,并且满足:
(31)∪Xi=V;
(32)对于任意的i∈L,Xi至少包含一个vi,1≤i≤K;
(33)对于任意一条边(u,v)∈E,存在一个i∈L使得
(34)对于树的节点Xi,Xj以及Xk,如果树节点Xk是树节点Xi到Xj路径上的一个树节点,则
图G中存在一个节点属于Xi∩Xj,且有
分解后的每一个树的子节点Xi,j包含路径L上的至少一个图的节点i,j表示图G中的任
一顶点,J是V的一个子集族。
4.根据权利要求1所述的一种基于树分解的智能搜捕方法,其特征在于,所述步骤(3)
中,依据步骤(2)对图G求得的树分解(TL,X),求取树的宽度为
5.根据权利要求1所述的一种基于树分解的智能搜捕方法,其特征在于,所述步骤(4)
中,对于图G的最优树分解为(TL,X),最优树分解中的树节点Xi,j,j=1,2,...,mi并包含相应
的vi;若树节点中包含vi和vi',且i'>i,则该节点记为Xi,j;则图G的最优树分解中对于任意
一个树节点Xi,j,至多需要[tw(G)/2]+1个搜捕者就能对其进行监视和安全防护;令Xi,j中搜
捕者数量为q,b1,b2,...,bq-1表示Xi,j/vi中的顶点;下面是对树节点Xi,j的搜索方法;首先,
将树节点Xi,j根据下面的规则重新构造为一个类二叉树的形状;具体包括以下步骤:
(51)令vi为树中的第0层顶点;
(52)将vi的相邻顶点定义为第1层顶点;
(53)依此类推,将第h层顶点的相邻顶点定义为第h+1层顶点;
(54)若顶点j的相邻顶点为j1,j2,...,jk,且j1,j2,...,jk分别属于不同的层l1,l2,...,
lk,则定义顶点j为第min{l1,l2,...,lk}+1层的顶点;
根据以上定义,偶数层的顶点数量为N;若N≤q/2,则考虑偶数层的顶点,若N>q/2,则
考虑奇数层的顶点;下面证明N个搜捕者能对Xi进行监测以及安全防护;首先,令搜捕者P1停
留在顶点vi处,剩余的N-1个搜捕者对Xi进行搜寻,直到这些搜捕者停留在Xi的偶数层,搜寻
过程中,搜捕者到达某一偶数层时,则这些搜捕者停在该层的顶点上,其余搜捕者继续搜
寻,直到Xi,j中所有的偶数层顶点都有搜捕者停留并监视;由于N≤q/2又根据树宽[tw(G)/
2]的定义,因此[tw(G)/2]+1个搜捕者即能对节点Xi,j进行搜寻和监视;用这种方法,入侵者
在有限步数后就会被限定到X/Xi,j的范围内;
搜捕者从顶点v1开始沿着路径L进行搜索;为了对相邻的树节点进行搜索和监视,搜捕
者按照下面的运动策略进行从Xi,1到Xi,2的移动;具体包括以下步骤:
(a)对于监视Xi,1∩Xi,j或者Xi,1∩Xi',j的搜捕者,j=2,...,mi,i'>i,令其继续保持在
相同的边不动;
(b)对于监视bh'bh,bh'bh∈E,bh'∈Xi,1∩Xi,2且bh∈Xi,1\Xi,2的搜捕者,令其沿着边bh'bh
移动到顶点bh',然后监视边bh'bh”,其中bh”∈Xi,2\Xi,1;
(c)对于其它的搜捕者,令它们监视Xi,2\Xi,1中未被监视的边;
按照上述方式,[tw(G)/2]+1+ni,1个搜捕者即能够搜索和监视Xi,1∪Xi,2,其中ni,1=|
Yi,1|且Yi,1=∑jXi,1∩(∪i'>iXi',j);重复上面的步骤,能够得出个搜
捕者能够搜索和监视其中ni,j=|Yi,j|且Yi,j=∑jXi,j∩(∪i'>iXi',j);
在所有的树节点Xi,j,j=1,2,...,mi都被搜索和监视后,令保持对
的监视;然后令搜捕者P1移动到vi+1进行监视;对于其它搜捕者的移动
策略,需要考虑以下两种情况:
(a)若存在2≤j'≤mi使得则令搜捕者通过vi监视Xi,j'∩
(∪i'>iXi',j)\{vi,vi-1};
(b)若则令[tw(G)/2]+1个搜捕者按照上面的方式
并沿着Xi,1到Xi+1,1的最短路径搜索并监视Xi+1,1。
6.根据权利要求1所述的一种基于树分解的智能搜捕方法,其特征在于,所述步骤(5)中,依
据基于树分解的搜捕算法,得出网络中所需搜捕者数量的最小上界
[.]为floor函数,mi表示包含vi的树节点中图顶点的个数,ni,j=|∑j'Xi,j∩(∪i'>iXi',j')|。

说明书

一种基于树分解的智能搜捕方法

技术领域

本发明涉及一种基于树分解的智能搜捕方法,属于智能协同控制技术领域。

背景技术

图搜索算法的研究是智能协同控制领域的一个重要分支,搜索算法的性能通过算
法的复杂度、有效性来衡量。多智能体搜捕方法中最短路径搜捕策略、最短太阳城集团搜捕策略、
博弈搜捕策略等的方法主要侧重于搜捕策略的最大效率,而忽视了所需搜捕者的数量以及
搜捕的成功率,其算法的复杂度也较大。而本发明所定义的搜捕方法中的搜捕者数量既能
保证搜捕的成功,又减少了搜捕的损耗。图搜索算法的求解思想能用于应急环境救援、室内
环境安防、战场环境探测,因此基于树分解的多智能体搜索方法既能为监测环境的入侵搜
索提供理论基石,也能为监测环境安全防护提供解决方案。

监测环境入侵搜索的理论基石图搜索是解决监测环境入侵搜索最常用的方法,根
据多智能体的感知范围、移动速度以及监测环境的特点对监测环境进行拓扑刻画,获取其
拓扑结构,并利用图论的方法对网络进行搜索,能够最有效率的实现对整个环境的搜索,并
以最快的速度定位入侵者。

监测环境安全防护的解决方案在保证搜索成功的情况下,使用最少的多智能体对
环境进行安全防护,利用树分解的方法,将图中的环变为树中的节点,防止了图搜索过程中
的重污染,保证了对整个环境的有效防护。

入侵者位置、速度不可知的情况下,基于搜捕策略的搜捕者数量的研究是非常有
难度、有挑战性的,当前公开发表的文献中,尚未看到相关研究成果。

发明内容

本发明的目的在于提供一种能够克服上述技术问题的基于树分解的智能搜捕方
法,本发明提出了以最小搜捕者数量及追捕的有效性为优化目标的移动传感网搜捕的技术
方案,本发明基于树分解的方法对环境进行搜素,避免了搜索过程中入侵者的重复侵入,能
提高搜索效率并减少了搜捕过程中的能量开销。首先给出以下定义:

定义1搜捕者数量:指在某一环境中存在一种策略使得最少数量的搜捕者能够成
功围捕入侵者,该最少数量即为搜捕者数量。

定义2上界:指某一环境中所需搜捕者数量的最大值。

本发明的基于树分解的智能搜捕方法包括以下步骤:

步骤一,获取目标环境,根据搜捕者的感知能力将监测环境转换为拓扑图;

获取目标环境,根据搜捕者的感知能力和移动速度将环境离散化为有限图,根据
智能体的感知能力将环境离散化为单元,使得每个搜捕者能够监测环境离散化后的每一个
单元,若入侵者进入此单元,搜捕者能够及时对其进行捕获,用顶点代替单元,相邻的单元
之间插入一条边,目标环境离散化为图G=(V,E)表示,其中图G为无向连通,V表示顶点集,|
V|表示顶点的个数,E表示边集。

步骤二,环境拓扑图的树分解;

在图G=(V,E)中选取路径L,且L中包含顶点集V中的两个端点,对图G按如下方式
进行树分解:

图G=(V,E)的一个树分解为(TL,X),X={Xi|i∈I},其中I是V的一个子集族,TL是
指以I为顶点集的树,TL中的节点是X的子集,路径L为图G中端点v1到vK的连接路径,路径L中
包含K个节点v1,v2,...,vK,并且满足:

(1)∪Xi=V;

(2)对于任意的i∈L,Xi至少包含一个vi,1≤i≤K;

(3)对于任意一条边(u,v)∈E,存在一个i∈L使得

(4)对于树的节点Xi,Xj以及Xk,如果树节点Xk是树节点Xi到Xj路径上的一个树节
点,则图G中存在一个节点属于Xi∩Xj,且有

分解后的每一个树的子节点Xi,j包含路径L上的至少一个图的节点i,j表示图G中
的任一顶点,J是V的一个子集族。

步骤三,求解拓扑图树宽;

依据步骤二对图G求得的树分解(TL,X),求取树的宽度为

步骤四,求解基于树分解的搜捕算法;

对于图G的最优树分解为(TL,X),最优树分解中的树节点Xi,j,j=1,2,...,mi并包
含相应的vi。若树节点中包含vi和vi',且i'>i,则该节点记为Xi,j。则图G的最优树分解中对
于任意一个树节点Xi,j,至多需要[tw(G)/2]+1个搜捕者就能对其进行监视和安全防护。令
Xi,j中搜捕者数量为q,b1,b2,...,bq-1表示Xi,j/vi中的顶点。下面是对树节点Xi,j的搜索方
法。首先,将树节点Xi,j根据下面的规则重新构造为一个类二叉树的形状;具体包括以下步
骤:

(1)令vi为树中的第0层顶点;

(2)将vi的相邻顶点定义为第1层顶点;

(3)依此类推,将第h层顶点的相邻顶点定义为第h+1层顶点;

(4)若顶点j的相邻顶点为j1,j2,...,jk,且j1,j2,...,jk分别属于不同的层l1,
l2,...,lk,则定义顶点j为第min{l1,l2,...,lk}+1层的顶点。

根据以上定义,偶数层的顶点数量为N。若N≤q/2,则考虑偶数层的顶点,若N>q/
2,则考虑奇数层的顶点。下面证明N个搜捕者能对Xi进行监测以及安全防护。首先,令搜捕
者P1停留在顶点vi处,剩余的N-1个搜捕者对Xi进行搜寻,直到这些搜捕者停留在Xi的偶数
层,搜寻过程中,搜捕者到达某一偶数层时,则这些搜捕者停在该层的顶点上,其余搜捕者
继续搜寻,直到Xi,j中所有的偶数层顶点都有搜捕者停留并监视。由于N≤q/2又根据树宽
[tw(G)/2]的定义,因此[tw(G)/2]+1个搜捕者即能对节点Xi,j进行搜寻和监视。用这种方
法,入侵者在有限步数后就会被限定到X/Xi,j的范围内。

搜捕者从顶点v1开始沿着路径L进行搜索。为了对相邻的树节点进行搜索和监视,
搜捕者按照下面的运动策略进行从Xi,1到Xi,2的移动;具体包括以下步骤:

(1)对于监视Xi,1∩Xi,j或者Xi,1∩Xi',j的搜捕者,j=2,...,mi,i'>i,令其继续保
持在相同的边不动;

(2)对于监视bh'bh,bh'bh∈E,bh'∈Xi,1∩Xi,2且bh∈Xi,1\Xi,2的搜捕者,令其沿着边
bh'bh移动到顶点bh',然后监视边bh'bh”,其中bh”∈Xi,2\Xi,1;

(3)对于其它的搜捕者,令它们监视Xi,2\Xi,1中未被监视的边。

按照上述方式,[tw(G)/2]+1+ni,1个搜捕者即能够搜索和监视Xi,1∪Xi,2,其中ni,1
=|Yi,1|且Yi,1=∑jXi,1∩(∪i'>iXi',j)。重复上面的步骤,能够得出
个搜捕者能够搜索和监视其中ni,j=|Yi,j|且Yi,j=∑jXi,j∩(∪i'>iXi',j)。

在所有的树节点Xi,j,j=1,2,...,mi都被搜索和监视后,令保持对
的监视。然后令搜捕者P1移动到vi+1进行监视。对于其它搜捕者的移动
策略,需要考虑以下两种情况:

(1)若存在2≤j'≤mi使得则令搜捕者通过vi监视
Xi,j'∩(∪i'>iXi',j)\{vi,vi-1};

(2)若则令[tw(G)/2]+1个搜捕者按照上面的
方式并沿着Xi,1到Xi+1,1的最短路径搜索并监视Xi+1,1。

步骤五,求解搜捕者数量最小上界;

依据基于树分解的搜捕算法,得出网络中所需搜捕者数量的最小上界
[.]为floor函数,mi表示包含vi的树节点中图顶点的个数,ni,j=|
∑j'Xi,j∩(∪i'>iXi',j')|。

本发明的优点是提出了以最小搜捕者数量及追捕的有效性为优化目标的移动传
感网搜捕的技术方案,本发明基于树分解的方法对环境进行搜素,避免了搜索过程中入侵
者的重复侵入,能提高搜索效率并减少了搜捕过程中的能量开销。

附图说明

图1是本发明所述的基于树分解的智能搜捕方法的流程示意图;

图2是本发明所述的基于树分解的智能搜捕方法的监测环境示意图;

图3是本发明所述的基于树分解的智能搜捕方法的监测环境离散化后的图G示意
图;

图4是本发明所述的基于树分解的智能搜捕方法的图G的树分解示意图。

具体实施方式

下面结合附图对本发明的实施方式进行详细描述。本实施例在以本发明为前提下
进行实施,给出了详细的实施方式和具体的操作过程,但本发明的保护范围不限于下述实
施例。

如图1所示,以室内追捕应用为例,具体基于树分解的多智能体搜捕算法包括以下
步骤:

步骤100:环境拓扑图的刻画;

在追捕问题中,对于室内环境的描述,一种常见的方法就是将其离散化成有限图。
如图2中的监测环境,根据搜捕者的监测能力将环境离散化,将监测环境分成小的单元,使
得每个搜捕者能够监测每一个单元,若攻击者进入此单元,搜捕者能够及时对其进行捕获,
用顶点代替单元,相邻的单元之间插入一条边,则目标环境用G=(V,E)表示,其中V表示顶
点集,E表示边集,如图3所示。

步骤200:拓扑图的树分解;

对于图G选择路径;

L=A-D-G-I-L-O-P-M-J-H-E-B;

对图G进行树分解,得出G的最优分解树(TL,X)如图4所示,分解后的树中有19个树
节点,图G中每一条边连接两个节点,这两个节点在树(TL,X)的节点中也列在一起。树(TL,X)
中的每个节点都包含路径L中的节点。

步骤300:拓扑图树宽的求解;

对上面的最优分解树(TL,X)进行树宽的求解,每一个树的节点包含两个顶点,故
树宽从图4中看出X3,2∩X10,1={H},X4,2∩X9,1={J}。故

步骤400:基于树分解的多智能体搜捕算法求解;

由上述步骤可得,该环境安全防护所需的搜捕者的数量为3,假设三个搜捕者,搜
捕者从顶点A开始沿着路径L进行搜索,得出3个搜捕者的移动策略为


步骤500:搜捕者数量最小上界的求解;

根据上面的树分解及算法得出,该环境安全防护所需的搜捕者数量的最小上界为

本发明的基于树分解的智能搜捕方法的求解思想用于应急环境救援、室内环境安
防、战场环境探测,因此基于树分解的搜索算法既能够为监测环境的入侵搜索提供理论基
石,也能够为监测环境安全防护提供解决方案。

以上所述,仅为本发明的具体实施方式,但本发明的保护范围并不局限于此,任何
熟悉本技术领域的技术人员在本发明公开的范围内,能够轻易想到的变化或替换,都应涵
盖在本发明权利要求的保护范围内。

关 键 词:
一种 基于 分解 智能 搜捕 方法
  专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
太阳城集团本文
本文标题:一种基于树分解的智能搜捕方法.pdf
链接地址:http://zh228.com/p-6019836.html
太阳城集团我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2017-2018 zhuanlichaxun.net网站版权所有
经营许可证编号:粤ICP备17046363号-1 
 


收起
展开
葡京赌场|welcome document.write ('');