Two-dimensional mapping of swarm robot based on random walk

doi:10.11772/j.issn.1001-9081.2020081239

Abstract

Abstract: Robots need to quickly and accurately obtain environmental map information when exploring unknown environments autonomously. For the problems of efficient exploration and map construction of unknown environments, the random walk algorithm was applied to the exploration of swarm robots, which simulate Brownian motion and build maps of the searched area. Then, the Brownian motion algorithm was improved to avoid the robot to search a region repeatedly by setting the maximum rotation angle when the robot walks randomly, so that the robot was able to explore more areas in the same time and the search efficiency of the robot was improved. Finally, simulation experiments were carried out through a group of mobile robots equipped with lidar, the influences of maximum rotation angle increment, the number of robots and movement steps of robot on the search area were analyzed.

Key words: swarm robot, random walk, mapping, Brownian motion, mobile robot

摘要： 机器人在未知环境自主探索时，需要快速准确地获取环境地图信息。针对高效探索和未知环境的地图构建问题，将随机行走算法应用于群机器人的探索中，机器人模拟布朗运动，对搜索区域建图。然后，改进了布朗运动算法，通过设置机器人随机行走时的最大旋转角度，来避免机器人重复性地搜索一个区域，使机器人在相同时间内探索更多的区域，提高机器人的搜索效率。最后，通过搭载激光雷达的多个移动机器人进行了仿真实验，实验分析了最大转角增量、机器人数量以及机器人运动步数对搜索区域的影响。

关键词: 群机器人, 随机行走, 地图构建, 布朗运动, 移动机器人

CLC Number:

TP242

LU Guoqing, SUN Hao. Two-dimensional mapping of swarm robot based on random walk[J]. Journal of Computer Applications, 2021, 41(7): 2121-2127.

陆国庆, 孙昊. 基于随机行走的群机器人二维地图构建[J]. 计算机应用, 2021, 41(7): 2121-2127.

References

[1] MENDONÇA M,KONDO H S,BOTONI DE SOUZA L,et al. Semi-unknown environments exploration inspired by swarm robotics using fuzzy cognitive maps[C]//Proceedings of the 2019 IEEE International Conference on Fuzzy Systems. Piscataway:IEEE, 2019:1-8.
[2] 梁璨, 房芳, 马旭东. 一种多机器人协作探索未知环境与地图构建的系统设计[J]. 工业控制计算机,2019,32(5):82-84,87. (LIANG C,FANG F,MA X D. Multi-robots exploration system for unknown environment and map construction[J]. Industrial Control Computer,2019,32(5):82-84,87.)
[3] FORSTER C,LYNEN S,KNEIP L,et al. Collaborative monocular SLAM with multiple micro aerial vehicles[C]//Proceedings of the 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway:IEEE,2013:3962-3970.
[4] 张航, 姚敏茹, 曹凯, 等. 改进粒子群优化算法的多机器人地图构建[J]. 计算机应用与软件,2019,36(10):162-167,174. (ZHANG H,YAO M R,CAO K,et al. Multi-robot mapping based on improved particle swarm optimization[J]. Computer Applications and Software,2019,36(10):162-167,174.)
[5] HOWARD A. Multi-robot simultaneous localization and mapping using particle filters[J]. International Journal of Robotics Research,2006,25(12):1243-1256.
[6] KEGELEIRS M,RAMOS D G,BIRATTARI M. Random walk exploration for swarm mapping[C]//Proceedings of the 2019 Annual Conference Towards Autonomous Robotic Systems,LNCS 11650. Cham:Springer,2019:211-222.
[7] PANG B,SONG Y,ZHANG C,et al. A swarm robotic exploration strategy based on an improved random walk method[J]. Journal of Robotics,2019,2019:No. 6914212.
[8] RAMACHANDRAN R K,KAKISH Z,BERMAN S. Information correlated Lévy walk exploration and distributed mapping using a swarm of robots[J]. IEEE Transactions on Robotics,2020,36(5):1422-1441.
[9] TURNAGE D M. Simulation results for localization and mapping algorithms[C]//Proceedings of the 2016 Winter Simulation Conference. Piscataway:IEEE,2016:3040-3051.
[10] JIANG Z,ZHU J,JIN C,et al. Simultaneously merging multirobot grid maps at different resolutions[J]. Multimedia Tools and Applications,2020,79(21/22):14553-14572.
[11] 黄宜庆, 王正刚, 王徽, 等. 基于边缘梯度算法的多移动机器人协作地图构建[J]. 信息与控制,2020,49(1):62-68.(HUANG Y Q,WANG Z G,WANG H,et al. Cooperative mapping for multiple mobile robots via edge gradient algorithm[J]. Information and Control,2020,49(1):62-68.)
[12] 马树军, 杨磊, 白昕晖, 等. 多机器人同步定位与地图构建的地图融合算法的改进[J]. 控制理论与应用,2019,36(8):1345-1350.(MA S J,YANG L,BAI X H,et al. Improvement of map fusion algorithm for multi-robot simultaneous localization and mapping[J]. Control Theory and Applications,2019,36(8):1345-1350.)
[13] RENSHAW E,HENDERSON R. The correlated random walk[J]. Journal of Applied Probability,1981,18(2):403-414.
[14] 邹洵, 张帆, 张国胜, 等. 基于ROS的协作机器人控制系统[J]. 计算机系统应用,2019,28(7):96-100.(ZOU X,ZHANG F, ZHANG G S,et al. ROS-based collaborative robot control system[J]. Computer Systems and Applications, 2019, 28(7):96-100.)
[15] RINCON J L S,CARPIN S. Map merging of oriented topological semantic maps[C]//Proceedings of the 2019 International Symposium on Multi-Robot and Multi-Agent Systems. Piscataway:IEEE,2019:202-208.
[16] PEARSON K. The problem of the random walk[J]. Nature, 1905,72(1865):No. 294.
[17] DIMIDOV C,ORIOLO G,TRIANNI V. Random walks in swarm robotics:an experiment with Kilobots[C]//Proceedings of the 2016 International Conference on Swarm Intelligence, LNCS 9882. Cham:Springer,2016:185-196.
[18] LI X,LI S,JIA S,et al. Mobile robot map building based on laser ranging and Kinect[C]//Proceedings of the 2016 IEEE International Conference on Information and Automation. Piscataway:IEEE,2016:819-824.
[19] KATADA Y,NISHIGUCHI A,MORIWAKI K,et al. Swarm robotic network using Lévy flight in target detection problem[J]. Artificial Life and Robotics,2016,21(3):295-301.
[20] SYED R U N J,AMJAD H,SULTAN M,et al. Low cost 2D laser scanner based indoor mapping and classification system[C]//Proceedings of the 2019 International Conference on Robotics and Automation in Industry. Piscataway:IEEE,2019:1-6.
[21] CARPIN S. Fast and accurate map merging for multi-robot systems[J]. Autonomous Robots,2008,25(3):305-316.
[22] 雷碧波, 曾文彬, 李晨曦. 基于ROS二维地图构建的方法[J]. 工业控制计算机,2017,30(9):42-43,45.(LEI B B,ZENG W B,LI C X. A method of mapping based on ROS[J]. Industrial Control Computer,2017,30(9):42-43,45.)
[23] 常皓, 杨巍. 基于全向移动模型的GMapping算法[J]. 计量与测试技术,2016,43(10):1-4. (CHANG H,YANG W. GMapping based on omni-directional wheeled mobile robot[J]. Metrology and Measurement Technique,2016,43(10):1-4.)
[24] 顾俊, 张宇, 樊东. 群体机器人研究综述[J]. 化工自动化及仪表,2018,45(2):95-99.(GU J,ZHANG Y,FAN D. A summary of research on swarm robotics[J]. Control and Instruments in Chemical Industry,2018,45(2):95-99.)
[25] JUNIOR L S, NEDJAH N. Efficient strategy for collective navigation control in swarm robotics[J]. Procedia Computer Science,2016,80:814-823.
[26] 鄢文浩, 贺赛先, 沈婷婷. 基于随机运动障碍避碰规则的机器人路径规划[J]. 电光与控制,2017,24(5):73-76.(YAN W H,HE S X,SHEN T T. Path planning of robots based on rules for avoiding random moving obstacle[J]. Electronics Optics and Control,2017,24(5):73-76.)
[27] 王权, 胡越黎, 张贺. 基于ROS与Kinect的移动机器人同时定位与地图构建[J]. 计算机应用研究,2017,34(10):3184-3187. (WANG Q, HU Y L, ZHANG H. Mobile robot simultaneous localization and mapping based on ROS and Kinect[J]. Application Research of Computers,2017,34(10):3184-3187.)
[28] 张辉, 渠瀛, 海丹, 等. 基于聚类匹配的移动机器人地图实时创建算法[J]. 计算机应用,2009,29(8):2116-2119,2123. (ZHANG H,QU Y,HAI D,et al. Real-time map building based on clustering for mobile robots[J]. Journal of Computer Applications,2009,29(8):2116-2119,2123.)