Fast Multi-Agent Collaborative Exploration Algorithm Based on Boundary Point Filtering

doi:10.3969/j.issn.1671-1122.2023.11.007

Abstract

Abstract:

In this research, the optimization problem of autonomous cooperative exploration tasks for multiple agents in an unknown environment without prior knowledge was addressed. To tackle this problem, an optimization model for multiple agents’ cooperative exploration in an unknown environment was constructed, and a novel algorithm called multiple agent obstacle frontier point filter (MAOFPF) was proposed. The MAOFPF algorithm tooks into account the relative distribution between boundary points and obstacles, explored the distance threshold for filtering boundary points, and consequently improved the selection of exploration tasks and resource allocation for multiple agents. Simulation results demonstrate that the proposed algorithm effectively filters out interference data from boundary points in various scenarios, ensuring smooth system operation. As a result, the optimized system exhibits enhanced disturbance resistance and generalization ability. Furthermore, the algorithm achieves a higher map coverage rate compared to the original algorithm, with an average efficiency improvement of 25.22%.

Key words: autonomous explore, multi-agent, MAOFPF algorithm, collaborative exploration

CLC Number:

TP309

YAO Changhua, XU Hao, FU Shu, LIU Xin. Fast Multi-Agent Collaborative Exploration Algorithm Based on Boundary Point Filtering[J]. Netinfo Security, 2023, 23(11): 58-68.

Figures/Tables 19

References 20

[1]	YIN Rui, SHEN Yineng, ZHU Huawei, et al. Time-Critical Tasks Implementation in MEC Based Multi-Robot Cooperation Systems[J]. China Communications, 2022, 19(4): 199-215.
[2]	XIE Jun, LYU Haonan, ZHU Zeya. Research on the Method of Multi-Robots Autonomous Collaborative Map Construction in Unknown Environment[C]// ACM. Proceedings of the 2020 the 4th International Conference on Innovation in Artificial Intelligence (ICIAI 2020). New York: ACM, 2020: 229-235.
[3]	LIU Jie, LYU Yong, YUAN Yuan, et al. An Efficient Robot Exploration Method Based on Heuristics Biased Sampling[J]. IEEE Transactions on Industrial Electronics, 2023, 70(7): 7102-7112. doi: 10.1109/TIE.2022.3203762 URL
[4]	PALACIOS-GASOS J M, TARDIOLI D, MONTIJANO E, et al. Equitable Persistent Coverage of Non-Convex Environments with Graph-Based Planning[J]. International Journal of Robotics Research, 2019, 38 (14): 1674-1694. doi: 10.1177/0278364919882082 URL
[5]	YU Tianyou, DENG Baosong, YAO Wen, et al. Market-Based Robots Cooperative Exploration in Unknown Indoor Environment[C]// IEEE. IEEE International Conference on Unmanned Systems (ICUS). New York: IEEE, 2021: 414-419.
[6]	MARTIN B, EFSTATHIOS B. Greedy Decentralized Auction-Based Task Allocation for Multi-Agent Systems[J]. IFAC-PapersOnLine, 2021, 54(20): 675-680.
[7]	ZHENG Shujian, ZHAO Wenjie. A Consensus-Based Joint Optimization Algorithm for Multi-Agent Collaborative Dynamic Task Allocation[C]// ACM. 4th International Conference on Robotics. New York: ACM, 2023, 1213-1219.
[8]	BURGARD W, MOORS M, STACHNISS C, et al. Coordinated Multi-Robot Exploration[J]. Transactions on Robotics, 2005, 21(3): 376-386.
[9]	DENG Liyuan, GONG Wei, LI Li. Multi-Robot Exploration in Unknown Environments via Multi-Agent Deep Reinforcement Learning[C]// IEEE. 2022 China Automation Congress (CAC). New York: IEEE, 2022: 6898-6902.
[10]	CHEN Jianping, WANG Jianbin, XIAO Qijun, et al. A Multi-Robot Task Allocation Method Based on Multi-Objective Optimization[C]// IEEE. 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV). New York: IEEE, 2018: 1868-1873.
[11]	ZHONG Ping, CHEN Bolei, LU Siyi, et al. Information-Driven Fast Marching Autonomous Exploration with Aerial Robots[J]. IEEE Robotics and Automation Letters, 2022, 7(2): 810-817. doi: 10.1109/LRA.2021.3131754 URL
[12]	CAO Junjie, WANG Yujie, LIU Yong, et al. Multi-Robot Learning Dynamic Obstacle Avoidance in Formation with Information-Directed Exploration[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2022, 6(6): 1357-1367. doi: 10.1109/TETCI.2021.3127925 URL
[13]	LAU B P L, ONG B J Y, LOH L K Y, et al. Multi-AGV’s Temporal Memory-Based RRT Exploration in Unknown Environment[J]. IEEE Robotics and Automation Letters, 2022, 7(4): 9256-9263. doi: 10.1109/LRA.2022.3190628 URL
[14]	UMARI H, MUKHOPADHYAY S. Autonomous Robotic Exploration Based on Multiple Rapidly-Exploring Randomized Trees[C]// IEEE. 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). New York: IEEE, 2017: 1396-1402.
[15]	LI Xiaoqiang, QIU Lei, AZIZ S, et al. Control Method of UAV Based on RRT for Target Tracking in Cluttered Environment[C]// IEEE. 2017 7th International Conference on Power Electronics Systems and Applications-Smart Mobility, Power Transfer &Security (PESA). New York: IEEE, 2017: 1-4.
[16]	CHEN Yuzhu, JIA Qingzhong, ZHAO Yong. Rough Waypoint Extraction Algorithm Based on Mean Shift Clustering Saliency Analysis[C]// IEEE. 2020 IEEE 4th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). New York: IEEE, 2020: 1345-1349.
[17]	JIN Yikang. Multi-Robot Exploration and Path Planning Algorithms of Mobile Robots[D]. Xi’an: Xidian University, 2020.
	金毅康. 移动机器人多机探索与路径规划算法研究[D]. 西安: 西安电子科技大学, 2020.
[18]	KUMAR NT S, GAWANDE M, BABU M N P, et al. Mobile Robot Terrain Mapping for Path Planning Using Karto Slam and Gmapping Technique[C]// IEEE. 2022 IEEE Global Conference on Computing, Power and Communication Technologies (GlobConPT). New York: IEEE, 2022: 1-4.
[19]	HESS W, KOHLER D, RAPP H, et al. Real-Time Loop Closure in 2D LIDAR SLAM[C]// IEEE. International Conference on Robotics and Automation. New York: IEEE, 2016: 1271-1278.
[20]	HORNER J. Map-Merging for Multi-Robot System[EB/OL]. (2016-06-16)[2023-07-01]. https://is.cuni.cz/webapps/zzp/detail/174125/.

参数名称	数据设置
随机树步长增长率	$\eta $=1.0
均值漂移聚类半径宽度/m	bandwidth=0.3
MAOFPF算法过滤半径/m	${{r}_{filter}}$=0.25
栅格图分辨率/(m/pix)	resolution=0.05
增益半径/m	${{r}_{info}}$=30
信息增益权重参数	${{\omega }_{I}}$=3.0
代价权重参数	${{\omega }_{C}}$=1.0
滞回半径/m	${{r}_{h}}=3$
滞回增益	${{h}_{earn}}$=2.0