TAMP:面向区域覆盖的层次化多机器人任务分配方法
作为诸多移动机器人应用的基础,完全覆盖旨在为机器人规划出一条访问 目标区域所有点且耗时最短的无碰撞路径.此类覆盖应用中,利用多台机器人协同覆盖可以有效缩短覆盖时间并提升系统的鲁棒性,同时也增加了算法设计复杂度和机器人协同管理难度.因此,文中研究了已知环境下的多机器人覆盖问题,该问题已被证明是一个NP难题.文中提出了一种启发式的基于多层次图划分的多机器人任务分配方 法(Multi-robot Task Assignment Based on Multi-level Graph Partitioning,TAMP),该方法包含一种粗化任务分配算法和一种精细任务分配算法.粗化任务分配算法采用分层粗化的方法,通过图的极大匹配实现了节点融合以降低图的规模,并基于均匀种子的图增长方式获取了一个接近均衡的初始任务分配结果,提高算法效率;精细任务分配算法在粗化任务分配算法的基础上,提出了一种基于边界节点交换的Lazy & Lock策略,用于实现任务细分,提高求解精度.文中在不同规模的随机图和真实世界的治安巡逻场景下进行了仿真验证.仿真结果表明,相比经典的任务分配方法,TAMP方法将可求解的最大计算规模从千级扩大到百万级,小规模图(3000以内)的计算速度加快了20倍,距离最优解偏差均优于经典方法;能够在60s内解决大规模图(3 000～1 000 000)的任务分配问题,同时将距离最优解偏差控制在0.3％以内.
多机器人系统、区域覆盖、任务分配、多层次图划分、最小最大平衡连通q分割
50
TP391(计算技术、计算机技术)
2023-09-20（万方平台首次上网日期，不代表论文的发表时间）
共9页
269-277
