基于行为树调度的多无人机未知室内空间探索方法

doi:10.11896/jsjkx.210900083

摘要/Abstract

摘要： 文中提出了一种在无GPS信号的未知室内空间中利用行为树框架调度多无人机和路径规划算法进行协作探索的方法。该方法的核心是提出了一种未知区域动态目标追踪算法Tracking-D*Lite对未知地形中的运动目标进行跟踪,同时结合基于Bug算法的Wall-Around算法在未知室内空间中导航无人机,最后利用行为树对多架无人机以及这两种算法进行调度和切换。该方法基于ROS,使用 Gazebo 进行模拟和可视化。设计并实现该方法与其他未知室内空间探索方法的对比实验,结果表明它可以有效地完成探索任务并最终绘制出整个未知室内空间的边界轮廓图。一旦扩展到现实世界中,该方法可以应用于地震后的危险建筑、危险气体工厂、地下矿井或其他搜救场景。

关键词: 多无人机, 行为树, 无GPS信号, 协同探索, 路径规划

Abstract: This paper proposes a method of using behavior tree framework to schedule multiple UAVs and path planning algorithms for collaborative exploration in a large unknown indoor space without GPS signals.The core of this method is to use the Tracking-D*Lite algorithm to track moving targets in unknown terrain,combined with the Wall-Around algorithm based on the Bug algorithm to navigate the UAV in the unknown indoor environment.Finally,the behavior tree is used to schedule and switch multiple UAVs and these two algorithms.This method is based on ROS and uses Gazebo for simulation and visualization.It designs and implements comparative experiments with other unknown indoor environment exploration methods.Experimental results show that it can effectively complete the exploration task and finally draw the boundary contour map of the entire unknown indoor environment.Once extended to the real world,this method can be applied to dangerous buildings after earthquakes,hazar-dous gas factories,underground mines,or other search and rescue scenarios.

Key words: Multi-UAV, Behavior tree, GPS-denied environment, Collaborative exploration, Path planning

中图分类号:

TP391

史殿习, 苏雅倩文, 李宁, 孙亦璇, 张拥军. 基于行为树调度的多无人机未知室内空间探索方法[J]. 计算机科学, 2022, 49(11A): 210900083-11. https://doi.org/10.11896/jsjkx.210900083

SHI Dian-xi, SU Ya-qian-wen, LI Ning, SUN Yi-xuan, ZHANG Yong-jun. Multi-UAV Cooperative Exploring for Large Unknown Indoor Environment Based on Behavior Tree[J]. Computer Science, 2022, 49(11A): 210900083-11. https://doi.org/10.11896/jsjkx.210900083

参考文献

[1]FLOREANO D,WOOD R J.Science,technology and the future of small autonomous drones[J].Nature,2015,521(7553):460-466.
[2]CADENA C,CARLONE L,CARRILLO H,et al.Past,present,and future of simultaneous localization and mapping:Toward the robust-perception age[J].IEEE Transactions on Robotics,2016,32(6):1309-1332.
[3]FLÓREZ-PUGA G,GOMEZ-MARTIN M,DIAZ-AGUDO B,et al.Dynamic expansion of behaviour trees[C]//Proceedings of Artificial Intelligence and Interactive Digital Entertainment Conference.AAAI Press,2008:36-41.
[4]LIU R F,WANG J S,ZHANG Y L,et al.Research progress and application of behavioral tree technology[J].Computer and Modernization,2020(2):76-82,88.
[5]ROBERTSON G,WATSON I.Building behavior trees from observations in real-time strategy games[C]//2015 International Symposium on Innovations in Intelligent Systems and Applications(INISTA).IEEE,2015:1-7.
[6]MCGUIRE K N,DE CROON G C H E,TUYLS K.A comparative study of bug algorithms for robot navigation.Robotics and Autonomous Systems,2019,121:103261.
[7]KOENIG S,LIKHACHEV M.Fast replanning for navigation in unknown terrain[J].IEEE Transactions on Robotics,2005,21(3):354-363.
[8]SUN X,URAS T,KOENIG S,et al.Incremental ARA* an incremental anytime search algorithm for moving-target search[C]//Proceedings of the Twenty-Second International Conference on International Conference on Automated Planning and Scheduling.2012:243-251.
[9]HE R,PRENTICE S,ROY N.Planning in information space for a quadrotor helicopter in a GPS-denied environment[C]//2008 IEEE International Conference on Robotics and Automation.IEEE,2008.
[10]PRENTICE S,ROY N.The belief roadmap:Efficient planning in linear pomdps by factoring the covariance[C]//Proc.ISRR.2007.
[11]PRAVITRA C,CHOWDHARY G,JOHNSON E.A compactexploration strategy for indoor flight vehicles[C]//2011 50th IEEE Conference on Decision and Control and European Control Conference.IEEE,2011:3572-3577.
[12]STIRLING T,ROBERTS J,ZUFFEREY J C,et al.Indoor navigation with a swarm of flying robots[C]//2012 IEEE International Conference on Robotics and Automation.IEEE,2012:4641-4647.
[13]GRZONKA S,GRISETTI G,BURGARD W.A fully autono-mous indoor quadrotor[J].IEEE Transactions on Robotics,2012,28(1):90-100.
[14]BI Y,QIN H,SHAN M,et al.An autonomous quadrotor for indoor exploration with laser scanner and depth camera[C]//IEEE International Conference on Control and Automation(ICCA).2016:50-55.
[15]SAMPEDRO C,RODRIGUEZ-RAMOS A,BAVLE H,et al.A Fully-Autonomous Aerial Robot for Search and Rescue Applications in Indoor Environments using Learning-Based Techniques[J].Journal of Intelligent and Robotic Systems:Theory and Applications,2019,95(2):601-627.
[16]PHAM H X,LA H M,FEIL-SEIFER D,et al.Autonomous uav navigation using reinforcement learning[J].arXiv:1801.05086,2018.
[17]WALKER O,VANEGAS F,GONZALEZ F,et al.A deep reinforcement learning framework for uav navigation in indoor environments[C]//2019 IEEE Aerospace Conference.IEEE,2019:1-14.
[18]WALKER O,VANEGAS F,GONZALEZ F,et al.Multi-UAVTarget-Finding in Simulated Indoor Environments using Deep Reinforcement Learning[C]//2020 IEEE Aerospace Confe-rence.IEEE,2020:1-9.
[19]MCGUIRE K N,DE WAGTER C,TUYLS K,et al.Minimal navigation solution for a swarm of tiny flying robots to explore an unknown environment[J].Science Robotics,2019,4(35):eaaw9710.
[20]COLLEDANCHISE M,ÖGREN P.Behavior trees in roboticsand AI:An introduction[M].CRC Press,2018.
[21]COLLEDANCHISE M,ÖGREN P.How behavior trees modu-larize robustness and safety in hybrid systems[C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems.IEEE,2014:1482-1488.
[22]GHZOULI R,BERGER T,JOHNSEN EB,et al.Behavior trees in action:a study of robotics applications[C]//Proceedings of the 13th ACM SIGPLAN International Conference on Software Language Engineering.2020:196-209.
[23]IOVINO M,SCUKINS E,STYRUD J,et al.A survey of behavior trees in robotics and ai[J].arXiv:2005.05842,2020.
[24]MARZINOTTO A,COLLEDANCHISE M,SMITH C,et al.Towards a unified behavior trees framework for robot control[C]//2014 IEEE International Conference on Robotics and Automation(ICRA).IEEE,2014:5420-5427.
[25]JONES S,STUDLEY M,HAUERT S,et al.Evolving behaviour trees for swarm robotics[M]//Distributed Autonomous Robotic Systems.Cham:Springer,2018:487-501.
[26]KUCKLING J,LIGOT A,BOZHINOSKI D,et al.Behaviortrees as a control architecture in the automatic modular design of robot swarms[C]//International Conference on Swarm Intelligence.Cham:Springer,2018:30-43.
[27]XU J,LIU W,LANG F,et al.Distance measurement modelbased on RSSI in WSN[J].Wireless Sensor Network,2010,2(8):606.
[28]KAMON I,RIVLIN E,RIMON E.A new range-sensor basedglobally convergent navigation algorithm for mobile robots[C]//Proceedings of IEEE International Conference on Robo-tics and Automation.1996:429-435.
[29]HART P E,NILSSON N J,RAPHAEL B.A formal basis for the heuristic determination of minimum cost paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[30]HARABOR D,GRASTIEN A.Online graph pruning for pathfinding on grid maps[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2011.
[31]STENTZ A.The focussed d^* algorithm for real-time replanning[C]//IJCAI.1995:1652-1659.

相关文章 15

[1]	王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[2]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery 计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[3]	谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms 计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300
[4]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[5]	陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm 计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002
[6]	杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170
[7]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[8]	赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform 计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[9]	曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193
[10]	陈继清, 谭成志, 莫荣现, 王志奎, 吴家华, 赵超阳. 基于人工势场的A^算法的移动机器人路径规划 Path Planning of Mobile Robot with A^ Algorithm Based on Artificial Potential Field 计算机科学, 2021, 48(11): 327-333. https://doi.org/10.11896/jsjkx.200900170
[11]	赵晓薇, 朱小军, 韩周卿. 面向定位应用的无人机的悬停位置和飞行路径优化 Hover Location Selection and Flight Path Optimization for UAV for Localization Applications 计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105
[12]	王梓强, 胡晓光, 李晓筱, 杜卓群. 移动机器人全局路径规划算法综述 Overview of Global Path Planning Algorithms for Mobile Robots 计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114
[13]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[14]	姜辰凯, 李智, 盘书宝, 王勇军. 基于改进Dijkstra算法的AGVs无碰撞路径规划 Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm 计算机科学, 2020, 47(8): 272-277. https://doi.org/10.11896/jsjkx.190700138
[15]	赵学远, 周绍磊, 王帅磊, 闫实. 切换拓扑条件下的多无人机系统编队包含控制 Formation Containment Control of Multi-UAV System Under Switching Topology 计算机科学, 2020, 47(6A): 577-582. https://doi.org/10.11896/JsJkx.190700064

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed