TAMP:面向区域覆盖的层次化多机器人任务分配方法  

TAMP:A Hierarchical Multi-robot Task Assignment Method for Area Coverage

作　　者：安浩嘉 史殿习[1,2,3] 李林 孙亦璇 杨绍武 陈旭灿 AN Haojia;SHI Dianxi;LI lin;SUN Yixuan;YANG Shaowu;CHEN Xucan(School of Computer Science,National University of Defense Technology,Changsha 410073,China;National Innovation Institute of Defense Technology,Academy of Military Sciences,Beijing 100166,China;Tianjin Artificial Intelligence Innovation Center,Tianjin 300457,China)

机构地区：[1]国防科技大学计算机学院,长沙410073 [2]军事科学院国防科技创新研究院,北京100166 [3]天津(滨海)人工智能创新中心,天津300457

出　　处：《计算机科学》2023年第9期269-277,共9页Computer Science

基　　金：国家自然科学基金(91948303)。

摘　　要：作为诸多移动机器人应用的基础,完全覆盖旨在为机器人规划出一条访问目标区域所有点且耗时最短的无碰撞路径。此类覆盖应用中,利用多台机器人协同覆盖可以有效缩短覆盖时间并提升系统的鲁棒性,同时也增加了算法设计复杂度和机器人协同管理难度。因此,文中研究了已知环境下的多机器人覆盖问题,该问题已被证明是一个NP难题。文中提出了一种启发式的基于多层次图划分的多机器人任务分配方法(Multi-robot Task Assignment Based on Multi-level Graph Partitioning,TAMP),该方法包含一种粗化任务分配算法和一种精细任务分配算法。粗化任务分配算法采用分层粗化的方法,通过图的极大匹配实现了节点融合以降低图的规模,并基于均匀种子的图增长方式获取了一个接近均衡的初始任务分配结果,提高算法效率;精细任务分配算法在粗化任务分配算法的基础上,提出了一种基于边界节点交换的Lazy&Lock策略,用于实现任务细分,提高求解精度。文中在不同规模的随机图和真实世界的治安巡逻场景下进行了仿真验证。仿真结果表明,相比经典的任务分配方法,TAMP方法将可求解的最大计算规模从千级扩大到百万级,小规模图(3000以内)的计算速度加快了20倍,距离最优解偏差均优于经典方法;能够在60 s内解决大规模图(3000~1000000)的任务分配问题,同时将距离最优解偏差控制在0.3%以内。As the foundation of many mobile robot applications,complete coverage aims to plan a collision-free path for robot to visit all points in the target area quickly.Using multiple robots for cooperative coverage can significantly reduce coverage time and improve system robustness.However,it increases the algorithm’s complexity and makes cooperative robot management more challenging.Therefore,the multi-robot coverage problem in a given environment is studied in this paper,which has been proven to be an NP problem.This work proposes a heuristic multi-robot task assignment based on multi-level graph partitioning(TAMP)method,which consists of a coarse task assignment algorithm and a fine task assignment algorithm.The coarse task assignment algorithm reduces the size of the graph by the strategies of multi-level coarsening and graph maximal matching and then obtains a roughly balanced task assignment by the graph growth strategy.The fine task assignment algorithm proposes a Lazy&Lock strategy to achieve task subdivision,which improves the solution accuracy.Simulations validate the performance of the TAMP approach under different scales of random graphs and real-world policing patrol scenarios.Compared to the conventional task assignment method,TAMP expands the maximum computational scale from thousands to millions.For small-scale graphs(within 3000),TAMP accelerates computation time by 20 times and outperforms the conventional method in terms of the deviation from the optimal solution for different small-scale graphs.For large-scale graphs(3000~1 million),TAMP can solve the task assignment problem in 60 s while keeping the deviation of the optimal solution within 0.3%.

关 键 词：多机器人系统 区域覆盖 任务分配 多层次图划分 最小最大平衡连通q分割 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]