引用本文

陈锦涛, 李鸿一, 任鸿儒, 鲁仁全. 基于RRT森林算法的高层消防多无人机室内协同路径规划. 自动化学报, 2023, 49(12): 2615−2626 doi: 10.16383/j.aas.c210368

Chen Jin-Tao, Li Hong-Yi, Ren Hong-Ru, Lu Ren-Quan. Cooperative indoor path planning of multi-UAVs for high-rise fire fighting based on RRT-forest algorithm. Acta Automatica Sinica, 2023, 49(12): 2615−2626 doi: 10.16383/j.aas.c210368

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c210368

关键词

高层消防多无人机，协同路径规划，RRT森林算法，动态规划，障碍物接近检测 

摘要

在多无人机 (Multi-unmanned aerial vehicles, Multi-UAVs) 协同执行高层消防救援任务的场景中, 室内复杂火场环境下路径规划是亟待解决难题之一. 针对快速搜索随机树算法 (Rapidly-exploring random tree, RRT) 搜索区域受限、耗时较长、结果可行性差等问题, 提出RRT森林算法. 通过随机选取根节点、生成随机树、连接合并随机树, 使高层消防多无人机在复杂室内环境下协同路径规划效率显著提高. 此外, 采用两次动态规划(Dynamic programming, DP)以及改进障碍物接近检测方法, 进一步提高路径的可行性. 最终, 通过仿真验证算法的有效性.

文章导读

随着城市化进程加速, 高层建筑数量急剧增加, 而高层建筑火灾事故给现有的消防救援技术与设备带来了新的挑战[1-2]. 现有的消防举高设备通常无法触及高于18层的起火楼层, 消防官兵负重登楼代价大[3-4], 建筑内部环境复杂, 充满高温烟尘, 人员疏散极其困难[5]. 此时, 基于多无人机 (Multi-unmanned aerial vehicles, Multi-UAVs) 协同控制技术的高层消防救援方法, 在高层建筑消防灭火中的应用愈发广泛[6-8]. 多无人机可通过破窗, 迅速进入高层火灾现场, 尝试扑灭初期火灾[9]; 在室内飞行时实现自主避障、自主探测火点及被困人员; 可通过扬声器、照明灯等辅助设备协助被困人员撤离[10]. 多无人机协同控制现已成为控制领域的研究热点[11]. 在高层火灾现场的室内环境进行多无人机协同路径规划、协同救援的研究, 其难点在于规划空间小、避障裕度低、限制条件多[12]等.

无人机路径规划算法主要有可视图法、栅格法、快速遍历随机树法(Rapidly-exploring random tree, RRT)等[13]. 其中, RRT算法因不需要对环境进行精确建模, 搜索性较强, 以及对时变环境适应性良好等优势[14], 在路径规划领域中有着广泛的应用. 对于RRT算法及其改进型算法, 文献[15]在前人的研究成果上对RRT算法进行了总结, 主要包括双向RRT (Bidirectional RRT, Bi-RRT)、偏向目标RRT (RRT-Goalbiasing)以及RRT-Connect算法, 并以此为基础提出了基于人工势场法的改进RRT算法, 一定程度上提高了算法的路径规划效率, 减少了路径规划时间. 文献[16-17]研究了动态步长RRT路径规划算法, 提高了随机树扩展的效率. 然而, 上述改进算法为提高到达终点的速度, 倾向于采用降低搜索广度的方法对RRT算法进行优化, 这样的优化对于复杂的高层室内火灾环境来讲是难以适用的. 有学者[18-21]曾提出在确定的位置上增加少量随机树以解决此问题, 但该方法更倾向于通过人工干预的形式选择辅助随机树根节点的位置, 不适合根据高层火灾室内环境变化频繁重规划. 针对以上问题, 本文提出一种改进的插入随机中间树的多树RRT算法, 下称RRT森林算法.

考虑路径的可行性, 现有的RRT算法普遍存在路径与障碍物距离过近的问题.目前常见的解决方法是把地图进行膨胀处理再进行路径规划[22], 但对于需要实时进行路径规划的复杂高层消防环境, 对地图进行预处理会降低规划效率. 文献[23]提出一种人工势场优化的RRT算法, 但这种方法需要计算地图中的势场, 需要反复计算微分, 运算效率仍不高. 因此, 研究一种能确保无人机与障碍物之间保持安全距离的碰撞检测程序十分有意义.

此外, RRT算法得到的路径通常不是最优路径[15], 而是一条有冗余点的路径. 在文献[24]中, Jeong等提出Quick-RRT* 算法, 在每一次产生子节点时都在给定的深度范围内, 寻找无障碍物相隔的父节点进行连接, 减少冗余点的产生, 但其路径受制于RRT生成的节点, 易出现不合理的拐角. 针对这一问题, 本文提出两次动态规划(Dynamic programming, DP)对路径进行优化的方法, 采取“规划−插值−规划”的策略取得可行性更高的路径.

基于对上述国内外研究现状的调研与分析, 综合考虑高层消防多无人机路径规划时间紧迫、环境复杂、需要频繁对未执行的局部路径进行重规划[25], 以及需要同时规划多条路径的特性, 本文提出RRT森林算法, 并通过改进的障碍物接近检测方法, 以及动态规划的两次优化, 提高算法的可行性. 主要工作归纳如下.

1) 提出RRT森林算法. 通过提升随机树森林的搜索广度, 提升算法搜索效率. 与文献[18-21]不同, RRT森林算法以树间连接优先的策略, 降低搜索后期节点数量对遍历效率的影响, 从而适应高层火灾救援任务中频繁的路径重规划; 同时, RRT森林算法通过多树连接进行寻路的设计, 实现多起点多终点的多无人机协同路径规划.

2) 提出障碍物接近检测方法. 通过检测包络线控制点以及包络线内部的随机点, 考虑无人机的体积, 使得路径更远离障碍物.

3) 提出基于动态规划的冗余点移除方法. 通过对路径中的节点以最优的方式重新连接, 删除其中的冗余点, 分离多无人机重合的路径, 并得到节点稀疏且路程最短的路径.

本文算法流程如图1所示. 第1节分析了基本RRT算法及双向RRT算法的优缺点; 第2节和第3节分别阐述了RRT森林算法和基于动态规划的冗余点移除方法; 第4节为RRT森林算法的仿真研究; 第5节为结论.

图 1  基于RRT森林算法的多无人机路径规划方法流程图

图 2  基本RRT算法采样及搜索过程

图 3  双向RRT连接过程

考虑到多无人机协同执行高层室内消防救援任务时的高度紧迫性, 在路径规划方面本文提出RRT森林算法, 提高了路径搜索的速度以及结果可行性. 通过在RRT算法中增加中间树, 解决了RRT算法在前期搜索范围受限的问题, 提高了复杂环境下的路径搜索效率、搜索速度及鲁棒性, 并且为多无人机进行协同路径规划提供了重要支撑. 通过设计新型碰撞检测算法, 使得路径与障碍物始终保持安全距离. 应用两次动态规划和参数方程拟合方法, 移除了路径上的冗余节点, 增强了规划结果的实用性. 实验结果表明, RRT森林算法可实现复杂环境下快速规划多条安全可行的路径, 并能满足高层消防救援中路径频繁重规划的需求.

关于高层消防多无人机室内协同路径规划, 本文提出的RRT森林算法能在较短时间内得到可行性较高的路径, 但在无人机数量较多、任务分配复杂的情况下, 在协同能力方面仍有提升空间. 因此将来的工作可以致力于提高多无人机协同路径规划的能力.

作者简介

陈锦涛

广东工业大学自动化学院博士研究生. 2023年获得广东工业大学自动化学院硕士学位. 主要研究方向为高层消防救援多无人机协同路径规划. E-mail: jintao0104@126.com

李鸿一

广东工业大学自动化学院教授. 主要研究方向为智能控制, 协同控制及其应用. 本文通信作者. E-mail: lihongyi2009@gmail.com

任鸿儒

广东工业大学自动化学院讲师. 2013年与2019年分别获中国科学技术大学自动化系控制科学与工程专业学士和博士学位. 主要研究方向为无人自主系统智能控制与协同控制. E-mail: renhongru2019@gdut.edu.cn

鲁仁全

广东工业大学自动化学院教授. 主要研究方向为无人自主系统协同控制理论与应用. E-mail: rqlu@gdut.edu.cn