专利摘要

一种基于多智能体协同的三维未知区域快速探测方法，属于人工智能领域。本发明方法基于在对三维未知区域进行探测的时候，DFS算法的计算复杂效率低下的问题，提出了一种基于多智能体协同的三维未知区域快速探测方法，通过构建多个智能体，协同对未知区域进行三维搜索，提高探测效率。

权利要求

1.一种基于多智能体协同的三维未知区域快速探测方法，其特征在于：包括如下步骤：

S1，准备一个总机和若干智能体，所述智能体为探测机器体，所述总机接收、发送智能体探测的结果并生成探测区域图；

S2，按探测精度和障碍的先验信息将目标区域划分为若干立方体，将智能体的起点设置为任一不是障碍的立方体，并将起点立方体的坐标发送给总机，总机将该立方体标记为可行路径；设定智能体探测的方向优先级，并设定每个智能体的起点均不相同，进入S3；

S3，每个智能体从当前立方体进入下一个立方体之前，按所述方向优先级的顺序获取前进方向，并访问总机，获取前进方向上的立方体的标记；若前进方向上的立方体未被标记，则对该前进方向上的立方体进行探测；若探测到该前进方向上的立方体为障碍，则将障碍立方体的坐标发送给总机，总机实时将对应立方体标记为障碍，随后智能体按所述方向优先级的顺序获取新的前进方向，探测新的前进方向上的立方体；若探测到该新的前进方向上的立方体不是障碍，则将该立方体的坐标发送给总机，总机实时将对应立方体标记为可行路径，随后智能体进入该立方体探测下一个前进方向上的相邻立方体，进入S4；

S4，重复S3，当且仅当全部立方体均已被标记完成后，探测结束；总机根据全部立方体的坐标和对应标记形成探测区域图；

所述每个智能体从当前立方体进入下一个立方体之前，对将要探测的立方体添加进程锁，阻止探测过程中其他智能体进入该立方体。

2.根据权利要求1所述的一种基于多智能体协同的三维未知区域快速探测方法，其特征在于：所述每个智能体从当前立方体进入下一个立方体之前，若智能体每个前进方向均已被标记时，则该智能体退回上一个不是每个前进方向均已被标记的立方体，选择方向优先级中低一级的前进方向进行探测。

3.根据权利要求1或2所述的一种基于多智能体协同的三维未知区域快速探测方法，其特征在于：所述方向优先级的顺序依次为上、下、左、右、前、后。

4.根据权利要求1或2所述的一种基于多智能体协同的三维未知区域快速探测方法，其特征在于：所述每个智能体的起点立方体在六个方向均不相邻。

5.根据权利要求1或2所述的一种基于多智能体协同的三维未知区域快速探测方法，其特征在于：所述智能体个数为四。

6.根据权利要求5所述的一种基于多智能体协同的三维未知区域快速探测方法，其特征在于：所述智能体的起点分别为目标区域的四个角处的立方体。

说明书

技术领域

本发明涉及一种基于多智能体协同的三维未知区域快速探测方法，属于人工智能领域。

背景技术

在战场环境中，不仅要保证完成作战任务，还要最大限度的保护作战人员的人身安全。而战场环境错综复杂，且目标十分隐蔽，如果需要对隐蔽好的目标进行精确打击，通过高空手段已经无法准确探测出目标所在的环境和目标的准确位置，必须深入到敌方内部，进行准确的环境探测。

为了保护人员的安全，以无人智能体替代人完成部分工作，无人智能体的外观可以制作成苍蝇、蜜蜂、虫子等自然环境中可能出现的生物，以此执行任务既能够有效的避免被敌方发现，又能够在复杂的未知的作战环境中完成区域探测任务。在实际作战环境中，讲究的是“兵贵神速”，为了保证能够快速获得敌方的战场环境，采用多个智能体协同工作，降低了单一智能体在敌方区域遍历过程中被发现的可能性，尤其是极大的提高了对敌方区域探测的效率。

DFS(深度优先遍历)算法可以用来进行未知区域的遍历，对目标探测区域内每一个可能的分支路径进行深度遍历搜索，直到不能再深入为止，且每个节点只遍历一次。《基于有向图理论的循环水系检测方法研究与制图试验》一文中，用DFS算法解决了水系中的特征遍历问题，对水系中的各个节点进行遍历，得出各个节点的出度和入度，具体运用了“当节点v的所有边都被已经被遍历过，搜索将回到发现节点v的那条边的起始点，这一过程一直进行到已发现从源节点可达的所有节点，如果还存在未被发现的节点，则选择其中一个作为源点并重复以上过程，整个过程反复进行直到所有节点都被访问为止”的方法，但是该方法在采用DFS的时候，需要结合回溯机制，将其用于未知的广阔的战场环境探测时，需要量化出大量的节点实施DFS算法，其时间复杂度为n2(n为目标区域节点数)，效率方面亟待提高。

因此，需要提出一种优化算法，在进行未知区域探测的过程中，对遍历的过程进行优化改进，既能完成对三维空间的目标区域的遍历，又能够提高遍历的效率，更好的完成三维未知区域快速探测任务。

发明内容

本发明解决的技术问题是：克服现有技术的不足，提供了一种基于多智能体协同的三维未知区域快速探测方法，在对三维未知区域进行探测的时候，解决DFS算法的计算复杂效率低下的问题，提出了一种基于多智能体协同的三维未知区域快速探测方法，通过构建多个智能体，协同对未知区域进行三维搜索，提高探测效率。

本发明的技术解决方案是：一种基于多智能体协同的三维未知区域快速探测方法，包括如下步骤：

S1，准备一个总机和若干智能体，所述智能体为探测机器体，所述总机接收、发送智能体探测的结果并生成探测区域图；

S2，按探测精度和障碍的先验信息将目标区域划分为若干立方体，将智能体的起点设置为任一不是障碍的立方体，并将起点立方体的坐标发送给总机，总机将该立方体标记为可行路径；设定智能体探测的方向优先级，并设定每个智能体的起点均不相同，进入S3；

S3，每个智能体从当前立方体进入下一个立方体之前，按所述方向优先级的顺序获取前进方向，并访问总机，获取前进方向上的立方体的标记；若前进方向上的立方体未被标记，则对该前进方向上的立方体进行探测；若探测到该前进方向上的立方体为障碍，则将障碍立方体的坐标发送给总机，总机实时将对应立方体标记为障碍，随后智能体按所述方向优先级的顺序获取新的前进方向，探测新的前进方向上的立方体；若探测到该新的前进方向上的立方体不是障碍，则将该不是障碍的立方体的坐标发送给总机，总机实时将对应立方体标记为可行路径，随后智能体进入该立方体探测下一个前进方向上的相邻立方体，进入S4；

S4，重复S3，当且仅当全部立方体均已被标记完成后，探测结束；总机根据全部立方体的坐标和对应标记形成探测区域图。

进一步地，所述每个智能体从当前立方体进入下一个立方体之前，若智能体每个前进方向均已被标记时，则该智能体退回上一个不是每个前进方向均已被标记的立方体，选择方向优先级中低一级的前进方向进行探测。

进一步地，所述每个智能体从当前立方体进入下一个立方体之前，对将要探测的立方体添加进程锁，阻止探测过程中其他智能体进入该立方体。

进一步地，所述方向优先级的顺序依次为上、下、左、右、前、后。

进一步地，所述每个智能体的起点立方体在六个方向均不相邻。

进一步地，所述智能体个数为四。

进一步地，所述智能体的起点分别为目标区域的四个角处的立方体。

本发明与现有技术相比的优点在于：

(1)本发明方法与现有的区域探测方法相比，采用了多进程并发机制，以多个智能体为主体，协同对目标区域进行遍历，避免智能体对重复区域的探测。极大地减少了DFS算法在面对大规模节点时产生大量回溯以及冗余路径的缺陷，节省了宝贵的作战资源，提高了遍历探测的效率；

(2)本发明采用了多进程并发来控制智能体同时进行遍历而产生的重复探测的问题。为避免多智能体对同一区域进行同时操作造成探测节点冲突，对当前正在探测区域加入了进程锁，阻止其他智能体的探测介入请求，降低冗余节点的产生概率保证了多智能体对作战区域的有效协同探测；

(3)将改进的DFS算法探测维度扩展到三维空间，以量化出更加精准的作战环境模型，为下一阶段作战策略的分析和拟定提供更加完善的信息。

附图说明

图1为本发明方法流程框图。

具体实施方式

一种基于多智能体协同的三维未知区域快速探测方法，包括步骤如下：

(1)对目标区域进行划块操作，将目标三维区域划分为多个立方体；

(2)建立多个智能体，为每一个智能体建立探测的入口，即分配探测起始点；

(3)为每个智能体配置多进程并发DFS改进算法，从起始位置开始，每个智能体并发进行遍历探测，具体过程是，规定探测方向顺序及起始访问立方体V，依次从其相邻的未被访问的邻接点出发，对三维区域进行深度优先遍历，直到区域中和V相连通的立方体区域都被访问。

(4)在进行探测过程中，加入进程锁的机制，判断预探测区域符合探测开始的条件后，在探测进行前为该区域加进程锁，阻止自己在探测过程中其他智能体的介入。以减少冗余节点的产生，造成不必要的回溯。

(5)在探测过程中，需要多智能体与总机间相互通信，避开已被其他智能体探测完毕的区域，保证自己的探测区域是尚未被探测的区域，

从而减少遍历过程中产生的不必要回溯及冗余路径。缩短探测时间，

提高探测效率。

(6)如果当前智能体经判断其周围不存在合法的可行区域，即其下一步所能访问的区域均已被其他智能体标记，或探测得知为障碍区域，

则该智能体进入结束状态；

多智能体协同探测后生成带有探测标记的三维区域即为本次遍历的最终结果。

下面结合附图进一步说明。

如图1，一种基于多智能体协同的三维未知区域快速探测方法具体步骤包括：

(1)对目标区域进行划块操作，将目标三维区域划分为多个立方体，如划分为200个立方体(10*10*2)；

(2)建立多个智能体，例如建立4个智能体，为每一个智能体建立探测的入口，即分配探测起始点，分别为(0，0，0)(0，9，0)(0，9，9)(0，0，9)；规定探测方向为上、下、左、右、前、后；

(3)所有智能体同时从自己的起始位置开始，如智能体1的起始位置(0，0，0)开始，按照规定的探测方向从其相邻的未被访问的邻接点出发，对三维区域进行DFS探测：探测前首先检查该区域是否已被其他智能体探测结束，若状态已知，则改变探测方向，若状态未知，则开始探测；当探测区域为障碍区域时，进行标记并通知给其余智能体；当探测区域为正常状态时，则前进至该区域并循环上述探测过程，直到其周围不存在合法的可行区域，即其下一步所要探测的区域均已被其他智能体标记，或探测得知为障碍区域，则该智能体进入结束状态

(4)在进行探测过程中，加入进程锁的机制，判断预探测区域符合探测开始的条件后，在探测进行前为该区域加进程锁，阻止自己在探测过程中其他智能体的介入。以减少冗余节点的产生，造成不必要的回溯。若当所有智能体均进入结束状态，但作战区仍存在未被探测到的区域时，则将其标记为障碍。多智能体协同探测后生成带有探测标记的三维区域即为本次遍历的最终结果。

多智能体协同探测后生成带有探测标记的三维区域即为本次遍历的最终结果。

本发明说明书中未作详细描述的内容属本领域技术人员的公知技术。

一种基于多智能体协同的三维未知区域快速探测方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。