一种堵控规划方法及装置、围捕系统

摘要

本发明提供了一种堵控规划方法及装置、围捕系统，包括：根据目标位置确定逃逸范围圈；根据逃逸范围圈和路网的道路拓扑地图确定可能的逃逸出口；根据目标位置和可能的逃逸出口确定逃逸路线，选择逃逸路线上的路口作为堵控的锚点；计算目标到达各个锚点的时间和警力到达各个锚点的最快到位时间；遍历所有锚点，比较目标到达锚点的时间和警力到达锚点的最快到位时间；选择警力先到的锚点作为堵控点，在堵控点部署相应的警力。本发明通过找到较优堵控点，实现警力资源的精准投放。

说明书

技术领域

本发明涉及计算机技术领域，尤指一种堵控规划方法及装置、围捕系统。

背景技术

为了实现对嫌疑人的抓捕，需要协作多警员运动到若干堵控点(即嫌疑人大概率出现的地点)，再对其进行抓捕。

有效的堵控点规划和合理的警力部署是影响围捕成功的重要因素。现有技术，主要依据人工经验规划堵控点和堵控点的警力部署，没有借助先进的技术手段和定位数据，围捕效果不佳，也无法得到保证。

如何合理规划堵控点，做到警力资源的精准投放，尤其是在警力资源不足下，是一个值得研究的问题。

发明内容

本发明提供了一种堵控规划方法及装置、围捕系统，用于解决现有技术中依据人工经验进行堵控规划，围捕效果无法得到保证的问题。

本发明提供的技术方案如下：

一种堵控规划方法，包括：根据目标位置确定逃逸范围圈；根据所述逃逸范围圈和路网的道路拓扑地图确定可能的逃逸出口；根据所述目标位置和所述可能的逃逸出口确定逃逸路线，选择逃逸路线上的路口作为堵控的锚点；计算目标到达各个锚点的时间和警力到达各个锚点的最快到位时间；遍历所有锚点，比较目标到达所述锚点的时间和警力到达所述锚点的最快到位时间；选择警力先到的锚点作为堵控点，在堵控点部署相应的警力。

进一步地，所述的根据所述目标位置和所述可能的逃逸出口确定逃逸路线，选择逃逸路线上的路口作为堵控的锚点，包括：计算所述目标位置到各个可能的逃逸出口的最快逃逸路线；获取所有最快逃逸路线上的路口，将其作为堵控的锚点。

进一步地，计算警力到达一个锚点的最快到位时间，包括：获取路网的警力定位信息；将每个警力的定位信息生成R树空间索引；通过R树空间索引搜索法获取所述锚点附近的警力定位信息；根据所述锚点附近的警力定位信息，计算警力到达所述锚点的最快到位时间。

进一步地，所述的选择警力先到的锚点作为堵控点，之后包括：若存在至少一条最快逃逸路线上无法设置堵控点或存在绕路出圈的路线，则使用遗传算法确定补充观察点。

进一步地，所述的使用遗传算法确定补充观察点，包括：将逃逸范围圈内所有未设为堵控点的路口的开关状态组合作为染色体；初始化种群；评估种群中每条染色体的个体适应度；选择高适应度的染色体，进行交叉生成新的染色体,并淘汰低适应度的染色体,得到新的种群，如此重复预设迭代次数；从最后得到的种群中提取适应度最高的染色体，根据所述染色体中各个位的取值确定补充观察点。

进一步地，每条染色体的个体适应度计算包括：根据以下公式计算所述染色体的警力适应度：

Fp(i)＝(Psum-Dsum(i))/Psum；

其中，Fp(i)为第i条染色体的警力适应度，Psum为逃逸范围圈内总警力数，Dsum(i)为第i条染色体分配的警力数；

计算经所述染色体从目标位置到由逃逸出口点构成的汇聚点的等效电阻，根据以下公式计算所述染色体的密闭适应度：Fc(i)＝1-1/R

本发明还提供一种动态堵控装置，包括：逃逸出口确定模块，用于根据目标位置确定逃逸范围圈；根据所述逃逸范围圈和路网的道路拓扑地图确定可能的逃逸出口；锚点确定模块，用于根据所述目标位置和所述可能的逃逸出口确定逃逸路线，选择逃逸路线上的路口作为堵控的锚点；计算模块，用于计算目标到达各个锚点的时间和警力到达各个锚点的最快到位时间；堵控点确定模块，用于在每个锚点上，比较目标到达所述锚点的时间和警力到达所述锚点的最快到位时间；选择警力先到的锚点作为堵控点，在堵控点部署相应的警力。

进一步地，所述锚点确定模块，用于计算所述目标位置到各个可能的逃逸出口的最快逃逸路线；获取所有最快逃逸路线上的路口，将其作为堵控的锚点。

进一步地，还包括：补充点确定模块，用于若存在至少一条最快逃逸路线上无法设置堵控点或存在绕路出圈的路线，则使用遗传算法确定补充观察点。

本发明还提供一种围捕系统，包括指挥中心和终端设备；所述指挥中心包括前述的动态堵控装置和任务启动模块；所述动态堵控装置，用于根据需要参与的警种和堵控范围要求，自动计算堵控点和周边警力的任务要求；所述任务启动模块，用于在收到启动命令后，将任务下发到参与行动的终端设备中；所述终端设备，用于接收所述任务，并向警员呈现所述任务。

通过本发明提供的一种堵控规划方法及装置、围捕系统，至少能够带来以下有益效果：本发明通过找到较优堵控点，实现警力资源的精准投放。

附图说明

下面将以明确易懂的方式，结合附图说明优选实施方式，对一种堵控规划方法及装置、围捕系统的上述特性、技术特征、优点及其实现方式予以进一步说明。

图1是本发明的一种堵控规划方法的一个实施例的流程图；

图2是本发明的的一种动态堵控装置的一个实施例的结构示意图；

图3是本发明的一种围捕系统的一个实施例的结构示意图；

图4是图1中步骤S200的一种示意图；

图5是图1中最快逃逸路线的一种示意图；

图6是图1中围捕圈的一种示意图；

图7是图1中未闭合围捕圈的一种示意图；

图8是图1中第N代种群的一种示意图；

图9是图1中根据遗传算法补充观察点的一种示意图；

图10是图1中一种染色体密闭适应度的示意图。

附图标号说明：

100.动态堵控装置，110.逃逸出口确定模块，120.锚点确定模块，130.计算模块，140.堵控点确定模块，150.补充点确定模块，10.指挥中心，20.终端设备，200.任务启动模块。

具体实施方式

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对照附图说明本发明的具体实施方式。显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图，并获得其他的实施方式。

为使图面简洁，各图中只示意性地表示出了与本发明相关的部分，它们并不代表其作为产品的实际结构。另外，以使图面简洁便于理解，在有些图中具有相同结构或功能的部件，仅示意性地绘制了其中的一个，或仅标出了其中的一个。在本文中，“一个”不仅表示“仅此一个”，也可以表示“多于一个”的情形。

本发明的一个实施例，如图1所示，一种堵控规划方法，包括：

步骤S100根据目标位置确定逃逸范围圈。

具体地，在公安抓捕任务中，目标即嫌疑人，目标位置即嫌疑人所在位置。一般可根据报警案发地，或人像预警/技防推送的案发位置，确定目标位置。

逃逸范围圈指示了目标在抓捕前大概率所在的范围。

获取目标位置后，以目标位置为中心，按堵控半径确定逃逸范围圈。堵控半径可根据经验设置，或根据案发开始时间和预设逃逸速度计算，逃逸时间越长，堵控半径越大。

步骤S200根据逃逸范围圈和路网的道路拓扑地图确定可能的逃逸出口。

具体地，可以从第三方软件(比如高德地图、百度地图等)上获取路网的道路拓扑地图。在道路拓扑地图上确定目标位置和逃逸范围圈。逃逸范围圈与路网的道路拓扑地图相交，其交点为逃逸出口，即对象可能的出逃点。逃逸出口一般有多个。如图4所示，虚线圈为逃逸范围圈，虚线圈与路网相交的交点为逃逸出口。

步骤S300根据目标位置和可能的逃逸出口确定逃逸路线，选择逃逸路线上的路口作为堵控的锚点。

逃逸路线可根据经验设置，根据路网数据可获取逃逸路线上的各个路口，选择一些路口作为锚点。锚点即可能的堵控点。优选地，结合路网的道路拓扑地图，计算目标位置到各个可能的逃逸出口的最快逃逸路线；获取所有最快逃逸路线上的路口，将其作为堵控的锚点。

针对每个可能的逃逸出口，可采用现有的最优寻路算法，进行路径规划,得到目标位置到该逃逸出口的最快逃逸路线。如图5所示，有4个逃逸出口，目标位置到每个逃逸出口都有一条最快逃逸路线。

将每条最快逃逸路线上的路口(即道路交叉点)作为锚点。

步骤S400计算目标到达各个锚点的时间和警力到达各个锚点的最快到位时间。

根据预设目标逃跑速度，计算目标到达各个锚点的时间。可按最快逃逸路线和预设目标逃跑速度，计算目标到达最快逃逸路线上各个锚点的时间。

可选地，获取锚点附近的警力定位信息，根据每个锚点附近的警力定位信息计算警力到达锚点的最快到位时间。具体地，获取路网的警力定位信息；将每个警力的定位信息生成R树空间索引；通过R树空间索引搜索法获取锚点附近的警力定位信息。这样可以优化搜索过程,缩短搜索时间，防止遍历所有警力定位信息，以最快的方式搜索就近周边警力。

R树空间索引建立每个实体的外接矩形(又称为虚拟矩形)，对这些虚拟矩形建立空间索引，它包含指向所包围实体的指针。R树空间索引还将空间位置相近的实体外接矩形重新组织为更大的虚拟矩形，形成多级空间索引。利用R树空间索引可提高对特定实体的检索效率。本实施例通过将警力的实时定位信息生成R树空间索引，可快速搜索到锚点附近范围(比如，以锚点为中心预设边长的方形区域)的警力定位信息。根据该锚点附近范围的警力定位信息计算警力到达锚点的最快到位时间。

步骤S500遍历所有锚点，比较目标到达锚点的时间和警力到达锚点的最快到位时间。

在每个锚点上，比较目标和警力到达该锚点的时间。

步骤S600选择警力先到的锚点作为堵控点，在堵控点部署相应的警力。

具体地，若在同一条最快逃逸路线上存在多个警力先到的锚点，则选择距离目标位置最近的锚点作为堵控点。这样可以缩小围捕圈，尽早抓住目标。

若警力不足，且至少两条最快逃逸路线上存在警力先到的共同锚点，则选择该警力先到的共同锚点作为堵控点。这样可以减少警力部署，同时又兼顾了多条最快逃逸路线。

堵控点部署的警力，包括人员的配置、人员的数量和工具装备，必须具备抓捕目标的能力。可以根据目标的恶性程度，区分不同的警种进行堵控点调派。

当有富余警力时，可将目标先到的锚点设为观察点，安排警力到观察点进行监察任务。观察点的警力人员较少，一般为一人，不实施抓捕任务，在目标路过观察点时，对其进行跟随和上报。如果没有富余警力，则放弃该锚点。

如此，将所有锚点和警力完成匹配，形成闭合的围捕圈。如图6所示，有4个逃逸出口，在目标位置4到达每个逃逸出口的最快逃逸路线上设置了一个堵控点2，4个堵控点2形成了闭合的围捕圈1，在围捕圈内设置了一些观察点3。

如果在所有的最快逃逸路线上都有堵控点，则由堵控点形成的围捕圈为闭合的。

步骤S700若存在至少一条最快逃逸路线上无法设置堵控点或存在绕路出圈的路线，则使用遗传算法确定补充观察点。

有可能在某一路线上无法抢先闭合，即无法在最快逃逸路线上设置堵控点，此时可在路线上设观察点，可使用遗传算法进一步确定在什么位置设置补充观察点。

另外，由于前述是基于最快逃逸路径算法进行堵控点部署，目标有可能采用绕路出圈的路线，比如图7中，7-8-3-4-5-9-14-19路线，或11-10-16-15的路线，即使全部的最快逃逸路线都设置了堵控点，目标也有可能绕过堵控点，逃出围捕圈。针对这种情况，也可使用遗传算法进一步确定补充观察点。

首先将圈内的每个路口假想成可以开关的阀门，以目标位置为水源，为防止水流出圈外，在原有堵控基础上，设置每个路口的开关状态，开设为0，闭合为1，以现有实时警力数据为基础，以部署最少警力，堵控效率高为目标进行遗传算法迭代。

具体做法如下:

步骤1、初始化种群，种群第一代中有随机条染色体。

以所有未设为堵控点的路口的开关状态组合作为染色体，每个非堵控点的路口的开关状态作为染色体的位。

针对图7示例，得到图8，其中，将非堵控点的路口的开关状态组合作为染色体。图8为第N代种群，染色体4的第7位为1，第8位为0，表示7号路口设卡(设观察点)，8号路口不设卡(不设观察点)。第一代种群类似。

步骤2、计算染色体i的个体适应度。

根据以下公式计算染色体i的警力适应度：

Fp(i)＝(Psum-Dsum(i))/Psum；

其中，Fp(i)为第i条染色体的警力适应度，Psum为逃逸范围圈内总警力数，Dsum(i)为第i条染色体分配的警力数。调派警力越少，则警力适应度越高。

如图8的染色体4，其在1-4-5-7-9-10-16-17-18各个路口均设卡，即需要分配一个警力，所以染色体4分配的警力数为9，即Dsum(4)＝9。

计算经染色体i从目标位置到由逃逸出口点构成的汇聚点的等效电阻R

Fc(i)＝1-1/R

电阻量越高，说明密闭性越高，密闭适应度越高。

如图8的染色体4，其在1-4-5-7-9-10-16-17-18各个路口均设卡，把这些点删除，如图10所示，把圈外连通逃逸出口点15、19汇聚于点Destiny，可以看出，从目标位置出发到点Destiny(此例即为路口19)，有两条离散路线，分别是11-12-8-3、14-19，这两条离散路线没有连通，导致目标位置与点Destiny之间无法形成一通路，所以目标位置到点Destiny的等效电阻为无穷大，根据上述公式得到染色体4的密闭适应度为1。

根据染色体i的警力适应度和密闭适应度，比如采用加权求和的方式，得到染色体i的个体适应度F(i)，比如：F(i)＝Cc*Fc(i)+Cp*Fp(i)。

C

步骤3、计算当代所有染色体的个体适应度。

步骤4、选择高适应度的染色体，比如取一半适应度高染色体，进行交叉生成新的染色体，并淘汰低适应度的染色体，得到新的种群。如此重复迭代，经过预设迭代次数，取得较优方案。

在计算前,为了让结果可以快速收敛,可随机选取已有堵控点附近的路口设为1,加入初生代中。种群数量越大,迭代代数越多,结果越逼近最优解。

经过多轮迭代,取得适应度最高的染色体,根据该染色体中各个位的取值确定补充观察点。

图9是对图7示例的遗传算法计算结果的示例，在原有堵控点基础上补充了两个观察点(路口3和路口16)。

本实施例，通过推算目标所有可能的逃跑线路，对抓捕对象的位置和逃跑出口逐个进行最速路径规划，计算最速路径必经的路口点位；获取路口周边的警力实时定位信息，再对警力到各个路口点位进行路径规划，逐层筛选满足警力到最优路口，形成围捕圈，做到警力资源的精准投放，大概率堵住嫌疑人。

针对未闭合情况或绕路出圈的漏洞路口，通过遗传算法，以非堵控点的路口开关状态组合作为染色体，以警力数量少、堵控效率高为目标，进行迭代优化，结合路口周边警力以堵控和观察相结合的方式，形成近似最优方案。

本发明的一个实施例，如图2所示，一种动态堵控装置100，包括：

逃逸出口确定模块110，用于根据目标位置确定逃逸范围圈；根据逃逸范围圈和路网的道路拓扑地图确定可能的逃逸出口。

具体地，在公安抓捕任务中，目标即嫌疑人，目标位置即嫌疑人所在位置。一般可根据报警案发地，或人像预警/技防推送的案发位置，确定目标位置。

获取目标位置后，以目标位置为中心，按堵控半径确定逃逸范围圈。堵控半径可根据经验设置，或根据案发开始时间和预设逃逸速度计算，逃逸时间越长，堵控半径越大。

可以从第三方软件(比如高德地图、百度地图等)上获取路网的道路拓扑地图。在道路拓扑地图上确定目标位置和逃逸范围圈。逃逸范围圈与路网的道路拓扑地图相交，其交点为逃逸出口，即对象可能的出逃点。

锚点确定模块120，用于根据目标位置和可能的逃逸出口确定逃逸路线，选择逃逸路线上的路口作为堵控的锚点。

逃逸路线可根据经验设置，根据路网数据可获取逃逸路线上的各个路口，选择一些路口作为锚点。锚点即可能的堵控点。优选地，结合路网的道路拓扑地图，计算目标位置到各个可能的逃逸出口的最快逃逸路线；获取所有最快逃逸路线上的路口，将其作为堵控的锚点。

针对每个可能的逃逸出口，可采用现有的最优寻路算法，进行路径规划,得到目标位置到该逃逸出口的最快逃逸路线。将每条最快逃逸路线上的路口(即道路交叉点)作为锚点。

计算模块130，用于计算目标到达各个锚点的时间和警力到达各个锚点的最快到位时间。

根据预设目标逃跑速度，计算目标到达各个锚点的时间。可按最快逃逸路线和预设目标逃跑速度，计算目标到达最快逃逸路线上各个锚点的时间。

可选地，获取锚点附近的警力定位信息，根据每个锚点附近的警力定位信息计算警力到达锚点的最快到位时间。具体地，获取路网的警力定位信息；将每个警力的定位信息生成R树空间索引；通过R树空间索引搜索法获取锚点附近的警力定位信息。这样可以优化搜索过程,缩短搜索时间，防止遍历所有警力定位信息，以最快的方式搜索就近周边警力。

R树空间索引建立每个实体的外接矩形(又称为虚拟矩形)，对这些虚拟矩形建立空间索引，它包含指向所包围实体的指针。R树空间索引还将空间位置相近的实体外接矩形重新组织为更大的虚拟矩形，形成多级空间索引。利用R树空间索引可提高对特定实体的检索效率。本实施例通过将警力的实时定位信息生成R树空间索引，可快速搜索到锚点附近范围(比如，以锚点为中心预设边长的方形区域)的警力定位信息。根据该锚点附近范围的警力定位信息计算警力到达锚点的最快到位时间。

堵控点确定模块140，用于遍历所有锚点，比较目标到达锚点的时间和警力到达锚点的最快到位时间；选择警力先到的锚点作为堵控点，在堵控点部署相应的警力。

在每个锚点上，比较目标和警力到达该锚点的时间。选择警力先到的锚点作为堵控点，目标先到的锚点设为观察点。

若在同一条最快逃逸路线上存在多个警力先到的锚点，则选择距离目标位置最近的锚点作为堵控点。这样可以缩小围捕圈，尽早抓住目标。

若警力不足，且至少两条最快逃逸路线上存在警力先到的共同锚点，则选择该警力先到的共同锚点作为堵控点。这样可以减少警力部署，同时又兼顾了多条最快逃逸路线。

堵控点部署的警力，包括人员的配置、人员的数量和工具装备，必须具备抓捕目标的能力。可以根据目标的恶性程度，区分不同的警种进行堵控点调派。

当有富余警力时，可将目标先到的锚点设为观察点，安排警力到观察点进行监察任务。观察点的警力人员较少，一般为一人，不实施抓捕任务，在目标路过观察点时，对其进行跟随和上报。如果没有富余警力，则放弃该锚点。

如此，将所有锚点和警力完成匹配，形成闭合的围捕圈。

补充点确定模块150，用于若存在至少一条最快逃逸路线上无法设置堵控点或存在绕路出圈的路线，则使用遗传算法确定补充观察点。

有可能在某一路线上无法抢先闭合，即无法在最快逃逸路线上设置堵控点，此时可在路线上设观察点，可使用遗传算法进一步确定在什么位置设置补充观察点。

另外，由于前述是基于最快逃逸路径算法进行堵控点部署，目标有可能采用绕路出圈的路线，即使全部的最快逃逸路线都设置了堵控点，目标也有可能绕过堵控点，逃出围捕圈。针对这种情况，也可使用遗传算法进一步确定补充观察点。

首先将圈内的每个路口假想成可以开关的阀门，以目标位置为水源，为防止水流出圈外，在原有堵控基础上，设置每个路口的开关状态，开设为0，闭合为1，以现有实时警力数据为基础，以部署最少警力，堵控效率高为目标进行遗传算法迭代。

补充点确定模块还用于：初始化种群；计算当代所有染色体的个体适应度；选择高适应度的染色体，比如取一半适应度高染色体，进行交叉生成新的染色体，并淘汰低适应度的染色体，得到新的种群；如此重复迭代，经过预设迭代次数，取得较优方案；从最后得到的种群中获取适应度最高的染色体,根据该染色体中各个位的取值确定补充观察点。

本实施例，通过推算目标所有可能的逃跑线路，对抓捕对象的位置和逃跑出口逐个进行最速路径规划，计算最速路径必经的路口点位；获取路口周边的警力实时定位信息，再对警力到各个路口点位进行路径规划，逐层筛选满足警力到最优路口，形成围捕圈，做到警力资源的精准投放，大概率堵住嫌疑人。

针对绕路出圈的漏洞路口，通过遗传算法，以路口开关状态组合作为染色体，以警力数量少、堵控效率高为目标，进行迭代优化，结合路口周边警力以堵控和观察相结合的方式，形成近似最优方案，在节省警力资源的情况，推荐相对平衡抓捕圈方案。

需要说明的是，本发明提供的用于动态堵控装置的实施例与前述提供的应用于堵控规划方法的实施例均基于同一发明构思，能够取得相同的技术效果。因而，用于动态堵控装置的实施例的其它具体内容可以参照前述应用于堵控规划方法的实施例内容的记载。

本发明的一个实施例，如图9所示，一种围捕系统，包括：

指挥中心10和终端设备20。

指挥中心10包括动态堵控装置100和任务启动模块200。

动态堵控装置100，用于根据需要参与的警种和堵控范围要求，自动计算堵控点和周边警力的任务要求。

任务启动模块200，用于在收到启动命令后，将任务下发到参与行动的终端设备中。

终端设备20，用于接收任务，并向警员呈现任务。

本发明还提供了具体实施场景示例，将本申请提供的围捕系统应用于公安部门。具体如下：

1、指挥中心一张图

日常针对重大突发事件，指挥中心随时可在接处警“一张图”上启动抓捕任务。根据需要参与的警种和堵控范围要求，自动计算堵控点和周边警力的任务要求。

指挥员在AI计算结果上，可进行标绘和拖拽修正，包括增加堵控点，改变警力目标位置等。

完成预设堵控点后，可一键启动任务，下发图文指令到参与行动的民警终端。同时自动加入无线预设频道，进入组呼状态。实现语音和图文，双管下达行动任务。

任务启动后，所有警力位置变化，任务签收情况，各堵控点人员和装备到位情况，均在图上实时展示。

启动对象人像卡口布控，结合一线警力观察汇报，警车实时视频等，可自动或手动标绘对象位置，修正堵截点，调整任务分配，一键下发。所有信息在民警终端上实时共享。

按最大3层堵控圈设计要求，外圈为市郊常设堵控点，中圈为市内预设管控点，内圈为动态堵控点。在合计50个堵控点，100名警力参与行动的情况下，计算时长小于10秒。

2、民警移动终端设计

民警个人终端上，分为“抓捕任务”，和“抓捕处置群”。

(1)抓捕任务主要描述：【对象】特征，案由，历史触网信息等；【任务】地点，装备，时间，各堵控点位置警力信息等。

(2)参与行动的所有警力，除收到“抓捕任务”外，会和指挥员自动加入“抓捕处置群”。群内指挥员可督促警力签收和到场。

警力到达现场后，可手工签到或根据坐标自动签到。指挥中心一张图可实时显示各点人员，装备到位情况。

对象有任何新的触网信息，由系统自动在群内推送。

所有警力均可图文汇报现场情况，便于指挥中心和周边警力掌握现场信息。

应当说明的是，上述实施例均可根据需要自由组合。以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。