一种消防机器人智能路径规划方法

摘要

本发明涉及一种消防机器人智能路径规划方法，包括：根据消防机器人所在的火场空间环境信息进行预处理；根据所述扩展型MAKLINK图论构建凹‑凸多边形障碍物火场空间环境模型；根据所述消防机器人的驻守点和火灾扑救点，采用Dijkstra算法规划初始路径；基于所述火场空间环境模型和所述初始路径，引入信息素与启发值的自适应动态调整策略，利用改进型蚁群算法对蚂蚁转移过程中的路径节点进行迭代搜索，最终获取最优规划路径。本发明结合了扩展型MAKLINK图论与改进型蚁群算法的优点，能够在含有凹‑凸多边形障碍物的复杂火场空间环境中实现最优路径规划，算法收敛速度快，路径规划能力强；另外，本发明通过仿真试验验证了所提供技术方案的可行性与有效性。

说明书

技术领域

本发明涉及消防机器人路径规划领域，尤其是涉及一种消防机器人智能路径规划方法。

背景技术

消防机器人作为一种特殊的消防设备，可以进入到危险性大、环境恶劣等消防员不易接近的火灾现场执行各类火灾侦察任务，并进行相应的消防救援作业。消防机器人的投入使用，能够显著提高消防部门扑灭重大恶性火灾的能力，在减少国家财产损失和消防人员伤亡等方面发挥重要的作用。近年来，随着人工智能、信息处理、智能控制等专业技术的快速发展，消防机器人已呈现出自动化与智能化的发展趋势，逐渐成为能够在火场环境中自主导航并完成灭火任务的机器人综合系统。

路径规划是消防机器人自主导航研究中的重要组成部分，其任务是在有障碍物的火场环境中，构建一条从驻守点到火灾扑救点、无碰撞地绕过所有障碍物的最优火灾扑救路径。在传统路径规划方法中，最常用的是栅格地图法、人工势场法和拓扑图法。栅格地图法虽然简单实用，但是栅格的尺寸直接影响着环境信息存储量和规划路径所用的时间。人工势场法在路径规划的过程中，可能会出现合力为零的情况，导致机器人停止运动。拓扑图法的缺点是算法复杂度与障碍物数目成正比，规划出的路径质量不高。

随着智能算法的不断发展，模糊控制、遗传算法、粒子群算法等智能算法也在解决路径规划问题中发挥着重要作用。然而，模糊控制的规则表通常建立在专家经验的基础上，不能实时修改，对路径规划的结果可能产生影响。遗传算法、粒子群算法等也存在运算量大、效率低、编码复杂等缺点，影响火灾救援，实用价值有限。

发明内容

本发明的目的在于提供一种消防机器人智能路径规划方法，以克服上述现有技术中存在的运算资源耗费较大，自我调节能力较差，同时无法保证耗时最短路径规划的缺陷。

本发明的目的可以通过以下技术方案来实现，包括：

环境信息预处理步骤：根据消防机器人所在的火场空间环境信息建立世界坐标系，采用多边形对障碍物边缘进行描述，获取所述障碍物在所述火场空间环境中的顶点坐标，在所述世界坐标系中确定消防机器人的驻守点和火灾扑救点；

火场空间环境建模步骤：采用扩展型MAKLINK图论构建火场空间环境模型，所述火场空间环境模型包括消防机器人的可移动路径；

初始路径规划步骤：基于所述火场空间环境模型，根据确定的驻守点和火灾扑救点，以最短路径长度为目标，采用Dijkstra算法规划初始路径；

最优路径规划步骤：基于所述火场空间环境模型和所述初始路径，初始化预先建立的改进型蚁群算法，通过引入的信息素与启发值自适应动态调整策略，对蚂蚁转移过程中的路径节点进行迭代搜索，直至达到预设的最大迭代次数，最终获取最优规划路径。

进一步地，所述火场空间环境建模中，采用所述扩展型MAKLINK图论构建火场空间环境模型具体为，对于凸多边形障碍物，根据传统MAKLINK图论直接进行所述火场空间环境模型的构建；根据凹多边形障碍物的几何特征，将其分为独立外凹多边形障碍物，以及组合内凹多边形障碍物；对于独立外凹多边形障碍物，将其填补为凸多边形进行处理，并将填补的辅助连接线中点设置为路径节点；对于组合内凹多边形障碍物，将其缺口进行延展密封，再将延展连接线的中点设置为路径节点，其余内部结构按照传统MAKLINK图论进行处理。

进一步地，所述改进型蚁群算法在迭代搜索过程中，采用改进后的启发值重要程度因子定义公式，实现启发值的自适应动态更新。在算法迭代搜索的初期，为了提高效率，避免盲目随机性的自由探索，增大启发值重要程度因子；在迭代搜索中期，部分较短路径上信息素的浓度开始逐渐高于其他路径，此时减小启发值重要程度因子；在迭代搜索的后期，由于长时间信息素的积累，较短路径上信息素的浓度已经远远高于其他路径，为防止局部最优，再次增大启发值重要程度因子。所述改进后的启发值重要程度因子定义公式的表达式为：

式中，

进一步地，所述改进型蚁群算法在迭代搜索过程中，采用改进后的信息素挥发参数定义公式，进行信息素的自适应动态更新。算法初期，各条路径上的信息素浓度都较低，为了使得蚂蚁能够更快地找到较优路径，加快算法的收敛速度，信息素挥发参数的数值应该较大；在算法后期，随着时间的积累，信息素浓度不断增加，为了防止全局搜索能力降低，数值应该较小。所述改进后的信息素挥发参数定义公式的表达式为：

式中，

进一步地，所述改进型蚁群算法在迭代搜索过程中，根据信息素与启发值确定下一路径节点的位置，所述节点位置确定方法的表达式为：

式中，

进一步地，所述改进型蚁群算法在迭代搜索过程中，每只蚂蚁对某个路径节点进行选择后，都需对该节点的信息素进行局部更新，所述改进后的局部信息素更新公式的表达式为：

式中，ε

进一步地，所述改进型蚁群算法在完成一次迭代搜索后，选择所有蚂蚁进行过路径中长度最小的一条路径，更新该路径上所有节点的信息素，以增大再次被选择的概率，强化正反馈机制，所述改进后的全局信息素更新公式的表达式为：

Δε

式中，L

与现有技术相比，本发明具有以下优点：

(1)通过扩展与补充MAKLINK图论，使其能够适用于同时含有凹-凸多边形障碍物的复杂火场空间环境；

(2)改进后的启发值重要程度因子定义公式，在蚁群算法迭代初期，增大启发值重要程度因子，提高了优化效率；在迭代中期，减小启发值重要程度因子，控制了较短路径上信息素浓度的稳定性；在迭代后期，再次增大启发值重要程度因子，有效防止出现局部最优的情况，提高了路径规划结果的准确性；

(3)改进后的信息素挥发参数定义公式，在蚁群算法迭代初期，增大信息素挥发参数数值，使得蚂蚁能够更快地找到较优路径，加快算法的收敛速度；在迭代后期，减小信息素挥发参数数值，防止了全局搜索能力的降低；

(4)本发明消防机器人智能路径规划方法采用扩展型MAKLINK图论建立火场空间环境模型，利用Dijkstra算法粗略地规划出一条初始路径，再基于改进型蚁群算法迭代搜索所有优化路径，规划出消防机器人从驻守点到火灾扑救点的最短长度路径，算法收敛速度快，跳过局部最优结果，路径规划能力强。

附图说明

图1为本发明消防机器人智能路径规划方法的流程示意图；

图2为本实施例中凹-凸多边形障碍物火场空间环境的MAKLINK线及其中点；

图3为本实施例中凹-凸多边形障碍物火场空间环境的扩展型MAKLINK图；

图4为本实施例中蚁群算法与Dijkstra算法的对比结果；

图5为本实施例中改进型蚁群算法和蚁群算法的对比结果。

具体实施方式

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

实施例1

本实施例提供一种消防机器人智能路径规划方法，包括以下步骤：

环境信息预处理步骤：根据消防机器人所在的火场空间环境信息建立世界坐标系，采用多边形对障碍物边缘进行描述，获取障碍物在火场空间环境中的顶点坐标，在世界坐标系中确定消防机器人的驻守点和火灾扑救点；

火场空间环境建模步骤：根据火场空间环境信息，采用扩展型MAKLINK图论构建火场空间环境模型，火场空间环境模型包括消防机器人的可移动路径；

初始路径规划步骤：基于火场空间环境模型，根据确定的驻守点和火灾扑救点，以最短路径长度为目标，采用Dijkstra算法规划初始路径；

最优路径规划步骤：基于火场空间环境模型和初始路径，初始化预先建立的蚁群算法，对蚂蚁转移过程中的路径节点进行迭代搜索，直至达到预设的最大迭代次数，最终获取最优规划路径。

作为一种优选的实施方式，火场空间环境建模中，采用扩展型MAKLINK图论构建火场空间环境模型具体为，对于凸多边形障碍物，根据传统MAKLINK图论直接进行火场空间环境模型的构建；根据凹多边形障碍物的几何特征，将其分为独立外凹多边形障碍物，以及组合内凹多边形障碍物；对于独立外凹多边形障碍物，通过辅助连接线将其填补为凸多边形进行处理，并将辅助连接线的中点设置为路径节点；对于组合内凹多边形障碍物，通过延展连接线将其缺口进行延展密封，并将延展连接线的中点设置为路径节点，其余内部结构按照传统MAKLINK图论进行处理。

作为一种优选的实施方式，独立外凹多边形障碍物为单一的凹多边形障碍物，组合内凹多边形障碍物由多个障碍物组合构成。

作为一种优选的实施方式，蚁群算法采用改进型蚁群算法，该改进型蚁群算法在迭代搜索过程中，采用改进后的启发值重要程度因子定义公式，实现启发值的自适应动态更新；

改进后的启发值重要程度因子定义公式使得启发值重要程度因子随着改进型蚁群算法的迭代搜索过程呈先增大，然后减小，最后再增大的变化趋势。

作为一种优选的实施方式，改进后的启发值重要程度因子定义公式的表达式为：

式中，

作为一种优选的实施方式，蚁群算法采用改进型蚁群算法，该改进型蚁群算法在迭代搜索过程中，采用改进后的信息素挥发参数定义公式，进行信息素的自适应动态更新；

改进后的信息素挥发参数定义公式使得信息素挥发参数随着改进型蚁群算法的迭代搜索过程呈先变大后变小的变化趋势。

作为一种优选的实施方式，改进后的信息素挥发参数定义公式的表达式为：

式中，

作为一种优选的实施方式，蚁群算法采用改进型蚁群算法，该改进型蚁群算法在迭代搜索过程中，根据信息素与启发值确定下一路径节点的位置，下一路径节点位置的确定方法的表达式为：

式中，

式中，

作为一种优选的实施方式，蚁群算法采用改进型蚁群算法，该改进型蚁群算法采用改进后的局部信息素更新公式进行局部信息素的更新，改进后的局部信息素更新公式的表达式为：

式中，ε

作为一种优选的实施方式，蚁群算法采用改进型蚁群算法，该改进型蚁群算法采用改进后的全局信息素更新公式进行全局信息素的更新，改进后的全局信息素更新公式的表达式为：

Δε

式中，L

本实施例还提供一种最优的实施方式，其具体实施过程如下：

基于扩展型MAKLINK图论和改进型蚁群算法的消防机器人智能路径规划方法流程如图1所示，具体包括以下步骤：

S1：构建火场空间环境模型

S11：MAKLINK图论是一种构造自由空间的环境建模方法，将障碍物定义为凸多边形；

S12：构建空间环境内的MAKLINK线，MAKLINK线应该是两个多边形障碍物的顶点之间的连线，或者是一个多边形障碍物顶点到空间环境边界的垂直连接线；

S13：针对传统MAKLINK图论仅适用于含有凸多边形障碍物的火场空间环境的缺陷，对其进行必要的扩展与补充。将独立外凹多边形(例如图2中部的六边形)填补成凸多边形处理；针对组合内凹多边形(例如图2右下角的组合多边形)将其缺口处进行延展密封，再将延展线的中心设置为路径节点，其余内部结构按照传统MAKLINK图论方法进行处理；

独立外凹多边形障碍物为单一的凹多边形障碍物，组合内凹多边形障碍物由多个所述障碍物组合构成。

S14：将所有MAKLINK线的中点、所述驻守点S和所述火灾扑救点T进行相连，即将火场空间环境表现为扩展型MAKLINK图，如图3所示。每条自由连接线都代表消防机器人的可移动路径。

S2：初步规划火灾扑救路径

利用Dijkstra算法在扩展型MAKLINK图中粗略规划出一条依次通过路径节点S,U

S21：建立集合V包含所有待确定最短路径节点，集合U包含所有已确定最短路径节点；设置所述驻守点到自身的初始路径长度为零，到其他节点的初始路径长度为无穷大，并将初始值存储在起点邻接路径长度数组Len中。

S22：从集合V中选取出路径长度最短的节点i，将其设置为当前节点。

S23：根据扩展型MAKLINK图查找出当前节点i的相邻连通节点j，计算出节点i到节点j的距离l

S24：将当前节点i设置为已确定最短路径节点，并将其从集合V中取出，放入集合U中。

S25：判断集合V是否为空集：若是，则算法终止；若不是，则返回S22。

算法运行完毕后，即可从数组Len中获得消防机器人从所述驻守点到所有其他节点的最短路径长度；通过反向追踪最短路径长度的计算过程，即可得到初始路径规划结果。

S3：火灾扑救路径优化

各路径节点所在的MAKLINK线依次为L

式中，β

使用改进型蚁群算法寻得一组比例因子组合(β

S31：初始化改进型蚁群算法并设置参数，包括基准系数R、信息素选择阈值q

S32：改进型蚁群算法开始搜索，在当前节点上的蚂蚁根据下列公式选择下一条MAKLINK线上的节点：

S33：根据下列公式局部更新当前路径节点的信息素浓度：

S34：判断当前路径节点是否达到所述火灾扑救点，若是则进行步骤S35，否则返回步骤S32；

S35：统计当前m只蚂蚁搜索到的所有优化路径，选择长度最短的路径规划结果，并根据下列公式全局更新信息素浓度：

Δε

S36：判断是否达到预设的最大迭代次数；若是则进行步骤S37，否则返回步骤S32；

S37：获取全局最优规划路径。

为了验证本发明所提供的消防机器人智能路径规划方法的可行性与有效性，本实施例利用MATLAB 2016b搭建了一个200m×200m的正方形二维火场空间环境，在已知障碍环境下观察消防机器人能否从左上角的驻守点S通过最短距离运动到右下角的火灾扑救点T，并且无碰撞地绕过火场空间环境中的凹-凸多边形障碍物。改进型蚁群算法的初始化参数设置如表1所示。

表1改进型蚁群算法初始化参数

在第一个试验中，分别使用蚁群算法(ant colony optimization，简称ACO)和改进型蚁群算法(improved ant colony optimization，简称IACO)在火场空间环境中进行路径规划。试验结果显示，对比Dijkstra算法和蚁群算法，本实施例提供的改进型蚁群算法分别缩短了路径长度32.1335m和22.0853m。

从图4和图5的对比中可以看出，改进型蚁群算法在每条MAKLINK线上选择下一个路径节点时，减小了当前节点与下一节点之间的夹角，所规划的路径更加贴近多边形障碍物的边缘，尤其体现在最后阶段节点的选择上，最终促使消防机器人的火灾扑救路径长度变短，实现最优路径规划。这表明，引入的自适应调整信息素更新策略能够帮助算法跳过局部最优解，增强路径规划能力。

在第二个试验中，设置50、100、150和200四种不同的最大迭代次数，其余初始化参数与试验一中所使用的完全相同，分别使用蚁群算法和改进型蚁群算法进行路径规划，观察最大迭代次数对路径规划结果的影响，并对两者的规划结果进行对比分析。两种算法的试验结果对比数据如表2所示。

从表2中可以看出，在最大迭代次数相同的情况下，改进型蚁群算法所获得的优化路径数量明显更多，路径长度明显缩短；而蚁群算法的优化路径数量虽然随着迭代次数的增加略有提高，但数量还相对较低，进一步说明改进型蚁群算法拥有更强的路径规划能力；此外，从优化路径长度的变化规律也可以看出，当最大迭代次数由50变为100时，改进型蚁群算法的数值变化最大，随后增幅明显减小且逐渐接近最优解；而蚁群算法的优化路径长度虽然始终都在逐渐缩短，但是还不能确定所需的最优路径。这表明，改进型信息素挥发参数

表2算法试验结果对比数据

综合上述内容可以看出，本实施例所提供的基于扩展型MAKLINK图论和改进型蚁群算法的消防机器人智能路径规划方法，能够在含有凹-凸多边形障碍物的复杂火场空间环境中实现最优路径规划，且规划结果明显优于Dijkstra算法和蚁群算法，路径规划能力更强，算法收敛速度更快。

以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思做出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。