亲爱的研友该休息了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!身体可是革命的本钱,早点休息,好梦!

Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction

运动规划 路径(计算) 机器人 计算机科学 比例(比率) 任意角度路径规划 移动机器人 人工智能 地理 计算机网络 地图学
作者
Jingtao Tang,Zining Mao,Hang Ma
出处
期刊:IEEE Transactions on Robotics [Institute of Electrical and Electronics Engineers]
卷期号:41: 3348-3367 被引量:23
标识
DOI:10.1109/tro.2025.3567476
摘要

We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid$G$, which aims to compute paths for multiple robots to cover all cells of$G$. Traditional approaches are limited as they first compute coverage trees on a quadrant coarsened grid$\mathcal {H}$and then employ the Spanning Tree Coverage (STC) paradigm to generate paths on$G$, making them inapplicable to grids with partially obstructed$2 \times 2$blocks. To address this limitation, we reformulate the problem directly on$G$, revolutionizing grid-based MCPP solving and establishing new NP-hardness results. We introduce Extended-STC (ESTC), a novel paradigm that extends STC to ensure complete coverage with bounded suboptimality, even when$\mathcal {H}$includes partially obstructed blocks. Furthermore, we present LS-MCPP, a new algorithmic framework that integrates ESTC with three novel types of neighborhood operators within a local search strategy to optimize coverage paths directly on$G$. Unlike prior grid-based MCPP work, our approach also incorporates a versatile post-processing procedure that applies Multi-Agent Path Finding (MAPF) techniques to MCPP for the first time, enabling a fusion of these two important fields in multi-robot coordination. This procedure effectively resolves inter-robot conflicts and accommodates turning costs by solving a MAPF variant, making our MCPP solutions more practical for real-world applications. Extensive experiments demonstrate that our approach significantly improves solution quality and efficiency, managing up to 100 robots on grids as large as$256 \times 256$within minutes of runtime. Validation with physical robots confirms the feasibility of our solutions under real-world conditions.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
4秒前
斯文败类的应助被纯情的阁采纳,获得10
7秒前
科研通AI6.3的应助被纯情的阁采纳,获得10
7秒前
真的不会完成签到,获得积分10
7秒前
笙笙的应助被纯情的阁采纳,获得10
7秒前
科研通AI6.3的应助被纯情的阁采纳,获得10
7秒前
7秒前
KKIII发布了新的文献求助10
10秒前
雉鸥完成签到 ,获得积分10
10秒前
Ming完成签到 ,获得积分10
11秒前
Richard完成签到,获得积分10
14秒前
17秒前
香蕉觅云的应助被纯情的阁采纳,获得30
17秒前
科研通AI6.4的应助被纯情的阁采纳,获得10
18秒前
科研通AI6.3的应助被纯情的阁采纳,获得10
18秒前
科研通AI6.3的应助被纯情的阁采纳,获得10
18秒前
笙笙的应助被纯情的阁采纳,获得10
18秒前
王占雪完成签到 ,获得积分10
18秒前
Maestro_S的应助被纯情的阁采纳,获得30
18秒前
顺利夏云完成签到,获得积分10
23秒前
only完成签到 ,获得积分10
29秒前
英俊的未来完成签到 ,获得积分10
31秒前
32秒前
年轻靖巧完成签到,获得积分10
32秒前
35秒前
xl的应助被科研通管家采纳,获得10
36秒前
36秒前
36秒前
ldxghh发布了新的文献求助10
36秒前
37秒前
37秒前
37秒前
37秒前
脑洞疼的应助被2589采纳,获得10
43秒前
48秒前
欣喜香菇发布了新的文献求助10
53秒前
坦率黑米完成签到,获得积分10
53秒前
reece完成签到 ,获得积分10
53秒前
科研通AI6.4的应助被KKIII采纳,获得10
53秒前
芜湖发布了新的文献求助10
56秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
plantTFDB 508
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8172954
求助须知:如何正确求助?哪些是违规求助? 9565447
关于积分的说明 21780029
捐赠科研通 7764817
什么是DOI,文献DOI怎么找? 3431496
关于科研通互助平台的介绍 2555519
邀请新用户注册赠送积分活动 2476571