基于随机采样的高层消防无人机协同搜索规划

李鸿一, 陈锦涛, 任鸿儒, 鲁仁全. 基于随机采样的高层消防无人机协同搜索规划. 中国科学: 信息科学, DOI: 10.1360/SSI-2022-0038

研究意义

高层建筑消防救援任务中, 由于地面消防举高设备难以到达, 消防官兵不仅需人力背负装备登楼救援, 而且无法获得室外支援, 严重影响救援效率, 因而极易引发次生事故, 造成遇险人员伤亡甚至消防官兵伤亡. 

无人机参与高层建筑消防救援任务具有众多优势, 它飞行灵活, 可携带灯光、扬声器、灭火弹等多种消防救援装备, 可以从空中进入室内参与高层消防救援. 

多无人机同时进入室内参与协同搜救, 可有效提高无人机执行消防救援任务的可靠性和容错性, 节省搜救时间. 

高层消防多无人机的任务是进入室内协助消防官兵实时侦察火场情况, 地毯式搜索被困人员. 然而, 高层室内火场环境狭窄复杂, 消防救援时间紧迫, 因此, 为了安全快速地完成室内搜索任务, 需要设计高效的多无人机覆盖搜索规划方法.

现有多无人机路径规划工作或仅适用于高层消防任务中点到点的路径规划, 非覆盖搜索路径规划; 或使用“Z”字形搜索路径的规划方法, 更适用于室外的空旷环境, 难以满足在复杂狭窄环境下的避障要求; 或规划时间较长, 不适用于紧张的消防救援任务.

本文工作

本文考虑高层消防场景下任务规划时间的紧迫性、路径规划空间的复杂性, 以及单机算力的有限性, 受树状采样搜索方法的启发, 提出一种高层消防多无人机协同搜索规划方法. 

主要工作归纳如下:

（1）提出基于树状采样搜索方法的搜索点选取及分配方法, 称莲叶展开法（LLU）, 不同于将路径点选取与路径点分配分成两步处理, LLU同时解决复杂环境下多无人机路径点选取以及搜索任务分配问题, 简化了规划过程.

（2）不同于大多数多智能体路径规划方法中将所有智能体的指标合并考虑的做法, 本文在莲叶展开法的基础上提出莲叶交易机制, 解决了多无人机路径点选取的优化问题, 进一步提升了搜索空间的覆盖率.

（3）采用改进的和声搜索算法（HS）, 配合改进的RRT* 算法求解复杂环境中的TSP, 最终得到无人机飞行路径. 其中, 通过广度优先算法（BFS）产生随机搜索序列, 通过对随机选取序列局部翻转得到新路径序列, 简化了TSP求解过程, 降低了对算力的需求.

实验结果

考虑高层火灾室内环境是一个复杂环境, 本文仿真实验采用迷宫作为待搜索的环境, 地图为边长256像素的正方形区域, 由4架无人机参与搜救任务. 

通过统计分析莲叶展开法搜索点分配、基于RRT*的距离矩阵计算以及和声搜索算法求解TSP的运算时长和运算结果指标, 研究算法的运行效率.

如表1所示, 莲叶展开法及莲叶交易求解多无人机搜索点选取问题的过程中, 其覆盖率从0增加到95%以上所需时间集中在25到30秒之间; 最终莲叶展开覆盖率中位数达到98.013%, 剩下少部分空间可被无人机传感器实际探测范围覆盖; 莲叶交易过程发生次数为10架次.

图6为其中一次实验结果. 从莲叶展开法开始运行到30秒的时间段中, 算法以展开新莲叶为主, 这个时间段覆盖率会快速上升. 而在30秒后, 部分无人机展开莲叶的数量已经达到限制值, 因此这部分无人机开始寻求莲叶交易, 通过莲叶交易使得覆盖率继续缓慢上升. 当各无人机已无法继续展开新莲叶, 且难以通过交易进一步提高覆盖率时, 算法结束运行.

得到各无人机所需经过的节点集合后, 采用改进的单起点多终点RRT*算法模块搜索距离矩阵中某一行中受障碍物阻挡节点对的路径, 其结果如图7所示. 图8为基于改进和声搜索算法和RRT*的协同路径规划仿真效果.

另外, 本文采用实际高层建筑平面图进行了仿真实验, 实验中使用7架无人机, 多初始节点方式, 路径规划结果如图11所示. 

本文内容可能会与最终出版文章有微小差异，点击下方阅读原文按钮，快速获取文章最新版本。

《中国科学：信息科学》| SCIENCE CHINA Information Sciences

及时报道计算机科学与技术、控制科学与控制工程、通信与信息系统、微电子与固体电子学等领域基础与应用研究方面的原创性成果.

英文版投稿：https://mc03.manuscriptcentral.com/scis

中文版投稿：https://www.scicloudcenter.com/SSI/login/index

快速访问：http://scis.scichina.com/