基于RRT森林算法的高层消防多无人机室内协同路径规划

陈锦涛; 李鸿一; 任鸿儒; 鲁仁全

doi:10.16383/j.aas.c210368

基于RRT森林算法的高层消防多无人机室内协同路径规划

doi: 10.16383/j.aas.c210368

陈锦涛^{1, 2,},
李鸿一^{1, 2,},
任鸿儒^{1, 2,},
鲁仁全^{1, 2,}

1.
广东工业大学自动化学院广州 510006
2.
广东省智能决策与协同控制重点实验室广州 510006

基金项目: 国家自然科学基金(62033003, 62121004, 62003093), 广东特支计划本土创新创业团队项目(2019BT02X353), 广东省重点领域研发计划(2021B0101410005), 广东省研究生教育创新计划项目(2020SFKC028)资助

详细信息

作者简介:
陈锦涛：广东工业大学自动化学院博士研究生. 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

计量
- 文章访问数: 1885
- HTML全文浏览量: 919
- PDF下载量: 396
- 被引次数: 0
出版历程
- 收稿日期: 2021-04-27
- 录用日期: 2021-11-17
- 网络出版日期: 2021-12-19
- 刊出日期: 2023-12-27

Cooperative Indoor Path Planning of Multi-UAVs for High-rise Fire Fighting Based on RRT-forest Algorithm

CHEN Jin-Tao^{1, 2
,},
LI Hong-Yi^{1, 2
,},
REN Hong-Ru^{1, 2
,},
LU Ren-Quan^{1, 2
,}

1.
School of Automation, Guangdong University of Technology, Guangzhou 510006
2.
Guangdong Province Key Laboratory of Intelligent Decision and Cooperative Control, Guangzhou 510006

Funds: Supported by National Natural Science Foundation of China (62033003, 62121004, 62003093), Local Innovative and Research Teams Project of Guangdong Special Support Program (2019BT02X353), Key Area Research and Development Program of Guangdong Province (2021B0101410005), and Graduate Education Innovation Program of Guangdong Province (2020SFKC028)

More Information

Author Bio:
CHEN Jin-Tao　Ph.D. at the School of Automation, Guangdong University of Technology. He received his master degree from the School of Automation, Guangdong University of Technology in 2023. His research interest covers collaborative path planning for multi-UAVs in high-rise fire fighting and rescue scenarios

LI Hong-Yi　Professor at the School of Automation, Guangdong University of Technology. His research interest covers intelligent control, and cooperative control and its applications. Corresponding author of this paper

REN Hong-Ru　Lecturer at the School of Automation, Guangdong University of Technology. He received his bachelor and Ph.D. degrees in control science and engineering from University of Science and Technology of China in 2013 and 2019, respectively. His research interest covers intelligent control and cooperative control of unmanned autonomous system

LU Ren-Quan　Professor at the School of Automation, Guangdong University of Technology. His research interest covers cooperative control theory and application of unmanned autonomous system

摘要

摘要: 在多无人机 (Multi-unmanned aerial vehicles, Multi-UAVs) 协同执行高层消防救援任务的场景中, 室内复杂火场环境下路径规划是亟待解决难题之一. 针对快速搜索随机树算法 (Rapidly-exploring random tree, RRT) 搜索区域受限、耗时较长、结果可行性差等问题, 提出RRT森林算法. 通过随机选取根节点、生成随机树、连接合并随机树, 使高层消防多无人机在复杂室内环境下协同路径规划效率显著提高. 此外, 采用两次动态规划(Dynamic programming, DP)以及改进障碍物接近检测方法, 进一步提高路径的可行性. 最终, 通过仿真验证算法的有效性.
- 高层消防多无人机 /
- 协同路径规划 /
- RRT森林算法 /
- 动态规划 /
- 障碍物接近检测
Abstract: In the scene of multi-unmanned aerial vehicles (Multi-UAVs) cooperating in high-rise fire fighting mission, path planning in indoor complex fire environment is one of the difficult problems to be solved. This paper proposes the RRT-forest algorithm which aims at the problems existing in traditional rapidly-exploring random tree (RRT) algorithm, such as repeated exploration in the same area, large time consumption and poor feasibility of the results. By adding and developing intermediate random trees, connecting and merging random trees, the RRT-forest algorithm can significantly improve the efficiency of cooperative path planning in complex indoor environment with multi-UAVs for high-rise fire fighting. Moreover, by utilizing dynamic programming (DP) for twice and a novel obstacle proximity detection approach, this method can further improve the feasibility of the result. Finally, simulation is conducted to prove the effectiveness of the proposed algorithm.
- High-rise fire fighting multi-UAVs /
- cooperative path planning /
- RRT-forest algorithm /
- dynamic programming (DP) /
- obstacle proximity detection

HTML全文

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

Fig. 1 Workflow of multi-UAVs path planning approach based on RRT-forest

下载: 全尺寸图片幻灯片

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

Fig. 2 Sampling and exploring process of basic RRT

下载: 全尺寸图片幻灯片

图 3 双向RRT连接过程

Fig. 3 Connecting process of bidirection-RRT

下载: 全尺寸图片幻灯片

图 4 RRT森林算法两种工作模式

Fig. 4 Two working modes of RRT-forest algorithm

下载: 全尺寸图片幻灯片

图 5 多路径的导出方法

Fig. 5 Export method for multiple paths

下载: 全尺寸图片幻灯片

图 6 改进的障碍物接近检测示意图

Fig. 6 Schematic diagram of the improved obstacle proximity detection

下载: 全尺寸图片幻灯片

图 7 各算法在复杂环境下的运行结果

Fig. 7 Performance of algorithms in complex environment

下载: 全尺寸图片幻灯片

图 8 各算法在复杂环境中的实验数据

Fig. 8 Statistics among algorithms in complex environment

下载: 全尺寸图片幻灯片

图 9 RRT森林算法多路径规划

Fig. 9 Multi-path planning by RRT-forest

下载: 全尺寸图片幻灯片

图 10 单路径优化过程

Fig. 10 Optimization of single path

下载: 全尺寸图片幻灯片

图 11 多路径优化过程

Fig. 11 Optimization of multi-paths

下载: 全尺寸图片幻灯片

图 12 复杂环境下原碰撞检测与改进碰撞检测对比

Fig. 12 Comparison between novel and original obstacle checking

下载: 全尺寸图片幻灯片

图 13 实际环境下改进碰撞检测效果

Fig. 13 Result of novel obstacle checking in practical environment

下载: 全尺寸图片幻灯片

表 1 各算法搜索用时数据(s)

Table 1 Statistics of time used in exploring of each algorithm (s)

基本 RRT 双向 RRT RRT森林 (N_Tree = 20)

上四分位数 11.0064 3.5425 0.69081
中位数 7.9990 2.5683 0.48464
下四分位数 6.1111 1.8900 0.36128

下载: 导出CSV

参考文献(27)

[1]	乔萍, 张树平, 万杰, 李华. 基于ISM高层建筑消防救援影响因素研究. 消防科学与技术, 2016, 35(9): 1294-1297 Qiao Ping, Zhang Shu-Ping, Wan Jie, Li Hua. Study on affecting factors of high-rise building fire rescue based on ISM. Fire Science and Technology, 2016, 35(9): 1294-1297
[2]	牛小强. 大型商业综合体灭火救援思考. 消防科学与技术, 2013, 32(7): 778-780 Niu Xiao-Qiang. Fire fighting and rescue on large commercial complex. Fire Science and Technology, 2013, 32(7): 778-780
[3]	Pecho P, Magdolenová P, Bugaj M. Unmanned aerial vehicle technology in the process of early fire localization of buildings. Transportation Research Procedia, 2019, 40: 461-468 doi: 10.1016/j.trpro.2019.07.067
[4]	王莹. 建筑火灾扑救与应急救援. 北京: 中国人民公安大学出版社, 2015. Wang Ying. Building Fire Fighting and Emergency Rescue. Beijing: People＇s Public Security University of China Press, 2015.
[5]	胡玉玲, 王飞跃, 刘希未. 基于ACP方法的高层建筑火灾中人员疏散策略研究. 自动化学报, 2014, 40(2): 185-196 Hu Yu-Ling, Wang Fei-Yue, Liu Xi-Wei. ACP-based Research on Evacuation Strategies for High-rise Building Fire. ACTA AUTOMATICA SINICA, 2014, 40(2): 185-196
[6]	孟祥港, 徐鹏程, 董作峰. 无人机在高层灭火中的实际应用. 百科论坛, 2018, (19): 206 Meng Xiang-Gang, Xu Peng-Cheng, Dong Zuo-Feng. Practical Application of UAV in High-rise Fire Extinguishing. Encyclopedia Forum, 2018, (19): 206
[7]	刘永军, 刘卓斌, 王大勇. 面向高层建筑的消防无人机应用探讨. 科技创新导报, 2020, 17(3): 4-7 Liu Yong-Jun, Liu Zhuo-Bin, Wang Da-Yong. Discussion on the Application of Fire Fighting UAV for High-rise Buildings. Science and Technology Innovation Herald, 2020, 17(3): 4-7
[8]	周锐, 吴雯漫, 罗广文. 自主多无人机的分散化协同控制. 航空学报, 2008, (S1): 26-32 Zhou Rui, Wu Wen-Man, Luo Guang-Wen. Decentralized coordination control of multiple autonomous UAVs. Acta Aeronautica et Astronautica Sinica, 2008, (S1): 26-32
[9]	温卫敏. 一种最优路径规划的灭火机器人系统设计. 四川理工学院学报(自然科学版), 2018, 31(3): 21-28 Wen Wei-Min. Design of a fire-fighting robot system based on optimal path planning. Journal of Sichuan University of Science & Engineering (Natural Science Edition), 2018, 31(3): 21-28
[10]	卢伊. 基于用户心理模型研究的高层消防产品设计实践——以消防无人机为例 [硕士学位论文], 湖北工业大学, 中国, 2019. Lu Yi. Design Practice of High-rise Fire Protection Products Based on User Psychology Model-taking Fire Man Machine as an Example [Master thesis], Hubei University of Technology, China, 2019.
[11]	杜永浩, 邢立宁, 蔡昭权. 无人飞行器集群智能调度技术综述. 自动化学报, 2020, 46(2): 222-241 Du Yong-Hao, Xing Li-Ning, Cai Zhao-Quan. Survey on Intelligent Scheduling Technologies for Unmanned Flying Craft Clusters. ACTA AUTOMATICA SINICA, 2020, 46(2): 222-241
[12]	Wang Gai-Ge, Chu Hai-Cheng, Eric, Mirjalili, Seyedali. Three-dimensional path planning for UCAV using an improved bat algorithm. Aerospace science and technology, 2016, 49: 231-238 doi: 10.1016/j.ast.2015.11.040
[13]	韩忠华, 毕开元, 杨丽英. 室内复杂环境下多旋翼无人机动态路径规划. 中国惯性技术学报, 2019, 27(3): 366-377 Han Zhong-Hua, Bi Kai-Yuan, Yang Li-Ying. Dynamic path planning of multi-rotor unmanned aerial vehicle in indoor complex environment. Journal of Chinese Inertial Technology, 2019, 27(3): 366-377
[14]	王赟. 基于 RRT 轮式机器人路径规划方法研究 [硕士学位论文], 天津工业大学, 中国, 2019. Wang Yun. Research on Path Planning Method of Wheeled Robot Based on RRT [Master thesis], Tianjin Polytechnic University, China, 2019.
[15]	刘恩海, 高文斌, 孔瑞平, 刘贝野, 董瑶, 陈媛媛. 改进的RRT路径规划算法. 计算机工程与设计, 2019, 40(8): 2253-2258 Liu En-Hai, Gao Wen-Bin, Kong Rui-Ping, Liu Bei-Ye, Dong Yao, Chen Yuan-Yuan. Improved RRT path planning algorithm. Computer Engineering and Design, 2019, 40(8): 2253-2258
[16]	武晓晶, 许磊, 甄然, 吴学礼. 动态步长BI-RRT的无人机航迹规划算法. 河北科技大学学报, 2019, 40(5): 414-422 Wu Xiao-Jing, Xu Lei, Zhen Ran, Wu Xue-Li. Dynamicstep BI-RRT UAV path planning algorithm. Journal of Hebei University of Science and Technology, 2019, 40(5): 414-422
[17]	王道威, 朱明富, 刘慧. 动态步长的RRT路径规划算法. 计算机技术与发展, 2016, 26(3): 105-112 Wang Dao-Wei, Zhu Ming-Fu, Liu Hui. Rapidly-exploring random tree algorithm based on dynamic step. Computer Technology and Development, 2016, 26(3): 105-112
[18]	钟建冬. 基于狭窄通道识别的机器人路径规划研究 [博士学位论文], 上海交通大学, 中国, 2012. Zhong Jian-Dong. Robot Path Planning Based on Narrow Passage Reconition [Ph.D. dissertation], Shanghai Jiao Tong University, China, 2012.
[19]	Amin J, Bokovic J, Mehra R. A fast and effificient approach to path planning for unmanned vehicles. In: Proceedings of AIAA Guidance, Navigation, and Control Conference and Exhibit. Colorado, USA: AIAA, 2006.
[20]	Devaurs D, Siméon T, Cortés J. A multi-tree extension of the transition-based RRT: Application to ordering-and-pathfinding problems in continuous cost spaces. In: Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago, USA: IEEE, 2014. 2991−2996
[21]	Wong C B, Yang E F, Yan X T, Gu D B. Optimal path planning based on a multi-tree T-RRT* approach for robotic task planning in continuous cost spaces. In: Proceedings of the 12th France-Japan and the 10th Europe-Asia Congress on Mechatronics. Tsu, Japan: IEEE, 2018. 242−247
[22]	沈刚, 邵金菊, 谭德荣. 基于改进A$^$算法的智能车路径规划研究. 汽车实用技术, 2020, (2): 28-30 Shen Gang, Shao Jin-Ju, Tan De-Rong. Research on global path planning for intelligent vehicles based on improved A$^$ algorithm. Automobile Applied Technology, 2020, (2): 28-30
[23]	司徒华杰, 雷海波, 庄春刚. 动态环境下基于人工势场引导的RRT路径规划算法. 计算机应用研究, 2020, 38(3): 1-5 Situ Hua-Jie, Lei Hai-Bo, Zhuang Chun-Gang. Artificial potential field based RRT algorithm for path planning in dynamic environment. Application Research of Computers, 2020, 38(3): 1-5
[24]	Jeong In-Bae, Lee Seung-Jae, Kim Jong-Hwan. Quick-RRT$^$: triangular inequality-based implementation of RRT$^$ with improved initial solution and convergence Rate. Expert Systems with Applications, 2019, 123: 82-90 doi: 10.1016/j.eswa.2019.01.032
[25]	朱庆保. 复杂环境下的机器人路径规划蚂蚁算法. 自动化学报, 2006, 32(4): 586-593 Zhu Qing-Bao. Ant Algorithm for Path Planning of Mobile Robot in a Complex Environment. ACTA AUTOMATICA SINICA, 2006, 32(4): 586-593
[26]	袁静妮, 杨林, 唐晓峰, 陈傲文. 基于改进RRT$^$与行驶轨迹优化的智能汽车运动规划. 自动化学报, 2020, 46(x): 1-10 Yuan Jing-Ni, Yang Lin, Tang Xiao-Feng, Chen Ao-Wen. Autonomous Vehicle Motion Planning based on Improved RRT$^$ Algorithm and Trajectory Optimization. Acta Automatica Sinica, 2020, 46(x): 1-10
[27]	张化光, 张欣, 罗艳红, 杨珺. 自适应动态规划综述. 自动化学报, 2013, 39(4): 303-311 doi: 10.1016/S1874-1029(13)60031-2 Zhang Hua-Guang, Zhang Xin, Luo Yan-Hong, Yang Jun. An Overview of Research on Adaptive Dynamic Programming. ACTA AUTOMATICA SINICA, 2013, 39(4): 303-311 doi: 10.1016/S1874-1029(13)60031-2