面对通信链路中断、地形发生变化的应急场景，采用群组机器人建立救援支撑系统进行救援工作，可为后续救援人员进入降低人身风险、提高救援保障能力和救援效率。群组机器人通信网络构建是救援支撑系统建立的关键问题，而通信基站布放是通信网络实现的必要步骤，因此，本文针对应急场景下通信基站布放的路径规划问题，依据突现障碍物有无，构建静态应急场景和动态应急场景环境模型，依据两种场景提出了两种改进快速搜索随机树（Rapidly-exploring Random Tree，RRT）的机器人路径规划算法，主要工作如下：

      首先，针对静态应急场景的路径规划问题，提出了一种改进RRT的机器人路径规划算法。该算法将目标偏置采样和剪枝采样方法相结合，以一定的概率将目标点作为采样点进行随机采样，并结合新节点生成位置对采样范围进行约束，减少RRT算法的采样盲目性，在此基础上引入变步长扩展方法，利用随机点引力和目标点引力来改变局部节点扩展步长和方向，并利用权重距离系数实时调整两力引导时的比例，提升路径生成效率，对生成路径进行3次B样条拟合，增加机器人行驶的稳定性。最后基于Matlab仿真平台对该算法进行验证，实验结果表明，该算法在能量消耗上比RRT算法减少了14.2%，在内存利用率上比RRT算法增加了72.2%，在寻路时间代价上，比RRT算法减少了77.6%。

其次，针对静态应急场景改进算法并未改变RRT算法不适用变化场景的问题，提出了基于动态场景的改进RRT机器人路径规划算法。算法结合障碍物膨胀法，以机器人半径膨胀化障碍物，为机器人行驶预留边界，减少行驶过程中的磨损情况，提出了变概率目标偏置采样方法，在保持以一定概率将目标点作为随机采样点的基础上，根据生长节点与障碍物距离实时调整下一次采样的目标偏置概率，降低障碍区域随机树扩展缓慢问题，减少算法迭代时间，加入变范围剪枝采样方法，减少路径规划时的冗余节点和冗余路径并重新约束重规划的节点采样范围，最后利用重规划新节点选取策略和改进的RRT算法在碰到突现障碍物时对路径进行重规划。实验结果表明，与原始RRT算法比较，改进算法在能量消耗上减少了10.6%，在内存利用率上提高了82.8%，在寻路时间代价上减少了76.3%。

       综上所述，静态改进RRT算法和动态改进RRT算法分别能够实现静态应急场景和动态应急场景下的路径规划，为救援支撑系统搭建奠定了一定的基础。

     In the emergency scenario where communication links are interrupted and terrain changes occur, using group robots to establish rescue support system for rescue work can reduce personal risks for subsequent rescue workers and improve rescue support ability and efficiency. The construction of group robot communication network is a key issue in the establishment of rescue support system, and the laying of communication base stations is a necessary step for the realization of communication networks. Therefore, aiming at the path planning of communication base stations in emergency scenarios, this paper constructs static emergency scenario and dynamic emergency scenario environment models according to the presence or absence of emergent obstacles. Based on two scenarios, two improved Rapidly-exploring Random Tree (RRT) robot path planning algorithms are proposed. The main work is as follows:

      First, a robot path planning algorithm with improved RRT is proposed for the path planning problem of static emergency scenarios. The algorithm combines target bias sampling and pruning sampling methods to randomly sample target points as sampling points with a certain probability, and combines the new node generation position to constrain the sampling range to reduce the sampling blindness of the RRT algorithm, and introduces a variable step extension method on this basis to use random point gravity and target point gravity to change the local node extension step length and direction, and uses the weight distance coefficient The ratio between the two forces when guiding is adjusted in real time to improve the efficiency of path generation, and 3 times B-sample fitting is performed on the generated path to increase the stability of the robot driving. Finally, the algorithm is validated based on the Matlab simulation platform, and the experimental results show that the algorithm reduces 14.2% in energy consumption, increases 72.2% in memory utilisation and reduces 77.6% in path finding time cost compared to the RRT algorithm.

      Secondly, the improved RRT robot path planning algorithm based on dynamic scenarios is proposed to address the problem that the static emergency scenario improvement algorithm does not change the problem that the RRT algorithm is not applicable to changing scenarios. The algorithm combines the obstacle expansion method to expand the obstacles with the robot radius to reserve the boundary for robot driving and reduce the wear and tear during driving, proposes a variable probability target bias sampling method, and on the basis of keeping the target point as a random sampling point with a certain probability, adjusts the target bias probability of the next sampling in real time according to the distance between the growing node and the obstacle, reduces the slow expansion of the random tree in the obstacle region The problem of slow expansion of the random tree in the obstacle region is reduced, the iteration time of the algorithm is reduced, a variable range pruning sampling method is incorporated to reduce the redundant nodes and redundant paths in path planning and to re-bound the sampling range of nodes for replanning, and finally the path is replanned when a sudden obstacle is encountered using the replanning new node selection strategy and the improved RRT algorithm. Experimental results show that the improved algorithm reduces energy consumption by 10.6%, improves memory utilisation by 82.8% and reduces pathfinding time cost by 76.3% compared to the original RRT algorithm.

      In summary, static improved RRT algorithm and dynamic improved RRT algorithm can realize path planning in static emergency scenarios and dynamic emergency scenarios respectively, which lays a certain foundation for the construction of rescue support system.

[1]徐雪松,杨胜杰,陈荣元.复杂环境移动群机器人最优路径规划方法[J].电子测量与仪器学报,2016,30(02): 274-282.

[2]王玉鑫.机器人在灾难现场救援中的策略研究[D].华北电力大学,2021.

[3]Yu J. Control System of Fire Rescue Robot for High-Rise Building Design[J]. Advances in Civil Engineering, 2022, 2022.

[4]徐少波,王子幼.消防救援多机器人系统研究进展及关键技术综述[J].科技创新与应用,2022,12(09):155-157+161.

[5]Zhou Z, Liu J, Yu J. A survey of underwater multi-robot systems[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 9(1): 1-18.

[6]Feng Z, Hu G, Sun Y, et al. An overview of collaborative robotic manipulation in multi-robot systems[J]. Annual Reviews in Control, 2020, 49: 113-127.

[7]Queralta J P, Taipalmaa J, Pullinen B C, et al. Collaborative multi-robot search and rescue: Planning, coordination, perception, and active vision[J]. Ieee Access, 2020, 8: 191617-191643.

[8]Dorigo M, Theraulaz G, Trianni V. Swarm robotics: Past, present, and future [point of view][J]. Proceedings of the IEEE, 2021, 109(7): 1152-1165.

[9]Otte M, Kuhlman M J, Sofge D. Auctions for multi-robot task allocation in communication limited environments[J]. Autonomous Robots, 2020, 44: 547-584.

[10]Zou L, Wang Z, Hu J, et al. Communication-protocol-based analysis and synthesis of networked systems: Progress, prospects and challenges[J]. International Journal of Systems Science, 2021, 52(14): 3013-3034.

[11]邵壮,祝小平,周洲等.无人机编队机动飞行时的队形保持反馈控制[J].西北工业大学学报,2015(1):26-32.

[12]雷金辉,潘虹.基于Ad Hoc网络的多机器人通信协议改进[J].计算机测量与控制,2017,25(09):191-193+199.

[13]韩宝虎,赵亮,韩希君.应用巡检机器人的分布式基站布局及网络互联[J].粘接,2022,49(08):155-159.

[14]徐东辉,傅晓宁,康凯.典型地貌条件下无线宽带通信站点布设规划设计与实现[J].信息通信,2020(10):6-9.

[15]张丹萌,甄子洋,陈棪.基于改进RRT-Connect的协同航迹规划[J].电光与控制,2021,28(09):25-29.

[16]江洪,蒋潇杰.基于RRT改进的路径规划算法[J].重庆理工大学学报(自然科学),2021,35(07):10-16+124.

[17]Luo M, Hou X, Yang J. Surface optimal path planning using an extended Dijkstra algorithm[J]. IEEE access, 2020, 8: 147827-147838.

[18]Tang G, Tang C, Claramunt C, et al. Geometric A-star algorithm: An improved A-star algorithm for AGV path planning in a port environment[J]. IEEE access, 2021, 9: 59196-59210.

[19]秦旭,黄晓华,马东明等.基于改进D*算法的巡检机器人路径规划[J].组合机床与自动化加工技术,2022(06):10-13.

[20]Li Q, Xu Y, Bu S, et al. Smart vehicle path planning based on modified PRM algorithm[J]. Sensors, 2022, 22(17): 6581.

[21]Wang J, Li B, Meng M Q H. Kinematic Constrained Bi-directional RRT with Efficient Branch Pruning for robot path planning[J]. Expert Systems with Applications, 2021, 170: 114541.

[22]陈秋莲,蒋环宇,郑以君.机器人路径规划的快速扩展随机树算法综述[J].计算机工程与应用,2019,55(16):10-17.

[23]Zong C, Han X, Zhang D, et al. Research on local path planning based on improved RRT algorithm[J]. Proceedings of the Institution of Mechanical Engineers, Part D: Journal of Automobile Engineering, 2021, 235(8): 2086-2100.

[24]Zhang H, Wang Y, Zheng J, et al. Path planning of industrial robot based on improved RRT algorithm in complex environments[J]. IEEE Access, 2018, 6: 53296-53306.

[25]Zhang Z, Wu D, Gu J, et al. A path-planning strategy for unmanned surface vehicles based on an adaptive hybrid dynamic stepsize and target attractive force-RRT algorithm[J]. Journal of Marine Science and Engineering, 2019, 7(5): 132.

[26]杜传胜,高焕兵,侯宇翔等.同根双向扩展的贪心RRT路径规划算法[J/OL].计算机工程与应用:1-9[2023-04-21].http://kns.cnki.net/kcms/detail/11.2127.TP.20221104.1523.012.html

[27]姚智龙,张小俊,王金刚.改进Bi-RRT*算法的自动泊车路径规划[J/OL].机械科学与技术:1-10[2023-04-21].https://doi.org/10.13433/j.cnki.1003-8728.20220310.

[28]Qian K, Liu Y, Tian L, et al. Robot path planning optimization method based on heuristic multi-directional rapidly-exploring tree[J]. Computers & Electrical Engineering, 2020, 85: 106688.

[29]彭君,庞宗强,陆昂.改进RRT算法在机器人路径规划中的应用[J].信息与电脑(理论版),2021,33(18):37-41.

[30]Zhang X, Zhu T, Xu Y, et al. Local path planning of the autonomous vehicle based on adaptive improved RRT algorithm in certain lane environments[C]//Actuators. MDPI, 2022, 11(4): 109.

[31]Liu B, Liu C. Path planning of mobile robots based on improved RRT algorithm[C]//Journal of Physics: Conference Series. IOP Publishing, 2022, 2216(1): 012020.

[32]Kyprianou G, Doitsidis L, Chatzichristofis S A. Towards the achievement of path planning with multi-robot systems in dynamic environments[J]. Journal of Intelligent & Robotic Systems, 2022, 104(1): 15.

[33]Marcotte R J, Wang X, Mehta D, et al. Optimizing multi-robot communication under bandwidth constraints[J]. Autonomous Robots, 2020, 44(1): 43-55.

[34]孙弋,宋冬冬.群组机器人系统资源分配策略研究[J].西安科技大学学报,2022,42(04):818-825.

[35]万成.面向基站的边缘缓存策略研究[D].南京邮电大学,2022.

[36]Kiani F, Seyyedabbasi A, Nematzadeh S, et al. Adaptive metaheuristic-based methods for autonomous robot path planning: sustainable agricultural applications[J]. Applied Sciences, 2022, 12(3): 943.

[37]Eshtehardian S A, Khodaygan S. A continuous RRT*-based path planning method for non-holonomic mobile robots using B-spline curves[J]. Journal of Ambient Intelligence and Humanized Computing, 2022: 1-10.

[38]张跃明,薛奇,纪姝婷.满足曲率约束的B样条曲线连续路径平滑方法[J].华中科技大学学报(自然科学版),2022,50(05):59-65+72.

[39]Netek R, Masopust J, Pavlicek F, et al. Performance testing on vector vs. raster map tiles—comparative study on load metrics[J]. ISPRS International Journal of Geo-Information, 2020, 9(2): 101.

[40]徐源正.多移动机器人系统中路径规划算法的研究[D].电子科技大学,2019.

[41]李霜琳,何家皓,敖海跃等.基于鸽群优化算法的火星飞行器智能可视图法[J].飞行力学,2020,38(05):90-94.

[42]樊永生,连云霞,杨臻.改进烟花算法在虚拟士兵路径规划中的应用[J].计算机工程,2018,44(12):228-232.

[43]Kuipers B, Byun Y T. A Robust, Qualitative Method for Robot Spatial Learning[C]//AAAI. 1988, 88: 774-779.

[44]Luo M, Hou X, Yang J. Surface optimal path planning using an extended Dijkstra algorithm[J]. IEEE access, 2020, 8: 147827-147838.

[45]Erke S, Bin D, Yiming N, et al. An improved A-Star based path planning algorithm for autonomous land vehicles[J]. International Journal of Advanced Robotic Systems, 2020, 17(5): 1729881420962263.

[46]Gan Y, Zhang B, Ke C, et al. Research on robot motion planning based on RRT algorithm with nonholonomic constraints[J]. Neural Processing Letters, 2021, 53: 3011-3029.

[47]Eshtehardian S A, Khodaygan S. A continuous RRT*-based path planning method for non-holonomic mobile robots using B-spline curves[J]. Journal of Ambient Intelligence and Humanized Computing, 2022: 1-10.