未知环境应用OSPGB的清洁机器人全覆盖路径规划

doi:10.3778/j.issn.1002-8331.2406-0128

摘要/Abstract

摘要： 针对多机器人在未知环境下执行清洁任务路径重复率高以及转弯次数多的问题，提出了一种障碍物与起始点引导并融合回溯机制（OSPGB）的全覆盖算法，算法中添加了局部栅格活性值（LRA）函数辅助决策，应用于清洁机器人路径规划中。利用栅格地图表示需要清洁的区域，并通过障碍物与起始点的引导对工作环境进行覆盖，在算法中添加了回溯机制，用于帮助机器人脱离“死区”，同时避免机器人之间回溯区域冲突以及较长回溯路径的出现。引入LRA函数进行优化，减少机器人的转弯次数和路径覆盖的长度。在不同环境下进行仿真实验，得到的路径长度与生物激励神经网络算法（BINN）和牛耕式A*算法（BA*）相比分别减少了17.9%、17.6%，转弯次数与BA*算法和分散捕食者猎物模型算法（R-DPPCPP）相比分别减少了18.0%、34.7%，验证了所提算法在清洁机器人全覆盖路径规划中的有效性。

关键词: 多机器人, 未知环境, 全覆盖算法, 回溯机制, 活性值函数, 路径规划

Abstract: Aiming at the problem of high repetition rate and high number of turns of the paths of multiple robots performing cleaning tasks in unknown environments, a coverage algorithm guided by obstacles and starting points and fused with a backtracking mechanism (OSPGB) is proposed, and a local raster activity value (LRA) function is added to the algorithm to assist decision-making, which is applied to the path planning of cleaning robots. Firstly, the raster map is used to represent the area to be cleaned, and the working environment is covered by the guidance of obstacles and starting points, and a backtracking mechanism is added to the algorithm to help the robot to get out of the “dead zone”, and at the same time to avoid backtracking area conflicts between the robots as well as the emergence of long backtracking paths. Secondly, the LRA function is introduced to optimize the algorithm to reduce the number of turns and the length of the path covered by the robot. Finally, simulation experiments are conducted in different environments, and the obtained path lengths are reduced by 17.9% and 17.6% compared with the biologically inspired neural network (BINN) algorithm and the boustrophedon A* (BA*) algorithm, respectively, and the number of turns is reduced by 18.0% and 34.7% compared with the BA* algorithm and the decentralized predator-prey modeling algorithm (R-DPPCPP), respectively. This verifies the effectiveness of the proposed algorithm in the full-coverage path planning of cleaning robots.

Key words: multi-robot, unknown environment, full coverage algorithm, backtracking mechanism, activity value function, path planning

张方方, 蔡一飞, 辛健斌, 彭金柱, 刘艳红. 未知环境应用OSPGB的清洁机器人全覆盖路径规划[J]. 计算机工程与应用, 2025, 61(20): 105-113.

ZHANG Fangfang, CAI Yifei, XIN Jianbin, PENG Jinzhu, LIU Yanhong. Full Coverage Path Planning for Cleaning Robots with Unknown Environment Application of OSPGB[J]. Computer Engineering and Applications, 2025, 61(20): 105-113.

参考文献

[1] 何丽, 张恒, 袁亮, 等. 服务机器人社会意识导航方法综述[J]. 计算机工程与应用, 2022, 58(11): 1-11.
HE L, ZHANG H, YUAN L, et al. Review of socially-aware navigation methods of service robots[J]. Computer Engineering and Applications, 2022, 58(11): 1-11.
[2] 简毅, 张月. 移动机器人全局覆盖路径规划算法研究进展与展望[J]. 计算机应用, 2014, 34(10): 2844-2849.
JIAN Y, ZHANG Y. Complete coverage path planning algorithm for mobile robot: progress and prospect[J]. Journal of Computer Applications, 2014, 34(10): 2844-2849.
[3] TRAN V P, GARRATT M A, KASMARIK K, et al. Frontier-led swarming: robust multi-robot coverage of unknown environments[J]. Swarm and Evolutionary Computation, 2022, 75: 101171.
[4] LUO C M, YANG S X, LI X D, et al. Neural-dynamics-driven complete area coverage navigation through cooperation of multiple mobile robots[J]. IEEE Transactions on Industrial Electronics, 2017, 64(1): 750-760.
[5] XU P F, DING Y X, LUO J C. Complete coverage path planning of an unmanned surface vehicle based on a complete coverage neural network algorithm[J]. Journal of Marine Science and Engineering, 2021, 9(11): 1163.
[6] 周林娜, 汪芸, 张鑫, 等. 矿区废弃地移动机器人全覆盖路径规划[J]. 工程科学学报, 2020, 42(9): 1220-1228.
ZHOU L N, WANG Y, ZHANG X, et al. Compete coverage path planning of mobile robot on abandoned mine land[J]. Journal of Engineering Science, 2020, 42(9): 1220-1228.
[7] LIN H Y, HUANG Y C. Collaborative complete coverage and path planning for multi-robot exploration[J]. Sensors (Basel), 2021, 21(11): 3709.
[8] 阮贵航, 陈教料, 胥芳. 基于滚动优化和分散捕食者猎物模型的全覆盖路径规划算法[J]. 控制与决策, 2023, 38(9): 2545-2553.
RUAN G H, CHEN Q L, XU F. Compete coverage path planning algorithm based on rolling optimization and decentralized predator prey model[J]. Control and Decision Making, 2023, 38(9): 2545-2553.
[9] 孔滕广, 高焕兵, 陈修贤. 基于改进RRT的清扫机器人全覆盖路径规划[J]. 计算机工程与应用, 2024, 60(13): 311-318.
KONG T G, GAO H B, CHEN X X. Full-coverage path planning for cleaning robot based on improved RRT[J]. Computer Engineering and Applications, 2024, 60(13): 311-318.
[10] CHOI S, LEE S, VIET H H, et al. B-Theta*: an efficient online coverage algorithm for autonomous cleaning robots[J]. Journal of Intelligent & Robotic Systems, 2017, 87(2): 265-290.
[11] CAI C, CHEN J F, YAN Q L, et al. A multi-robot coverage path planning method for maritime search and rescue using multiple AUVs[J]. Remote Sensing, 2023, 15(1): 93.
[12] KIM J, BONADIES S, EGGLETON C D, et al. Cooperative robot exploration strategy using an efficient backtrac-king method for multiple robots[J]. Journal of Mechanisms and Robotics, 2018, 10(6): 064502.
[13] COLLINS L, GHASSEMI P, ESFAHANI E T, et al. Scalable coverage path planning of multi-robot teams for monitoring non-convex areas[C]//Proceedings of the IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2021: 7393-7399.
[14] ZHAO W W, LIN R, DONG S, et al. A study of the global topological map construction algorithm based on grid map representation for multirobot[J]. IEEE Transactions on Automation Science and Engineering, 2023, 20(4): 2822-2835.
[15] EDWARDS G T C, HINGE J, SKOU-NIELSEN N, et al. Route planning evaluation of a prototype optimised infield route planner for neutral material flow agricultural operations[J]. Biosystems Engineering, 2017, 153: 149-157.
[16] PIRE T H, FISCHER T, CIVERA J, et al. Stereo parallel tracking and mapping for robot localization[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway: IEEE, 2015: 1373-1378.
[17] 王宁, 韩雨晓, 王雅萱, 等. 农业机器人全覆盖作业规划研究进展[J]. 农业机械学报, 2022, 53(1): 1-19.
WANG N, HAN Y X, WANG Y X, et al. Research progress on full-coverage operation planning of agricultural robots[J]. Journal of Agricultural Machinery, 2022, 53(1): 1-19.
[18] 曹勇, 肖人彬. 蜂群激发抑制与刺激响应相结合的群机器人区域覆盖算法[J]. 复杂系统与复杂性学, 2019, 16(4): 1-12.
CAO Y, XIAO R B. Swarm excitation inhibition combined with stimulus response for swarm robot area coverage algorithm[J]. Complex Systems and Complexity Science, 2019, 16(4): 1-12.
[19] CHEN B, ZHANG W L, ZHANG F F, et al. A multirobot cooperative area coverage search algorithm based on bioinspired neural network in unknown environments[J]. IEEE Systems Journal, 2023, 17(2): 1995-2006.
[20] VIET H H, DANG V H, CHOI S, et al. BoB: an online coverage approach for multi-robot systems[J]. Applied Intelligence, 2015, 42(2): 157-173.
[21] 辛煜, 梁华为, 杜明博, 等. 一种可搜索无限个邻域的改进 A*算法[J]. 机器人, 2014, 36(5): 627-633.
XIN Y, LIANG H W, DU M B, et al. An improved A* algorithm for searching infinite neighborhoods[J]. Robotics, 2014, 36(5): 627-633.