计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (9): 269-277.doi: 10.11896/jsjkx.220800094

• 人工智能 • 上一篇    下一篇

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

安浩嘉1, 史殿习1,2,3, 李林1, 孙亦璇1, 杨绍武1, 陈旭灿1,2   

  1. 1 国防科技大学计算机学院 长沙 410073
    2 军事科学院国防科技创新研究院 北京 100166
    3 天津(滨海)人工智能创新中心 天津 300457
  • 收稿日期:2022-08-10 修回日期:2022-12-03 出版日期:2023-09-15 发布日期:2023-09-01
  • 通讯作者: 史殿习(dxshi@nudt.edu.cn)
  • 作者简介:(ahj20@alumni.nudt.edu.cn)
  • 基金资助:
    国家自然科学基金(91948303)

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

AN Haojia1, SHI Dianxi1,2,3, LI lin1, SUN Yixuan1, YANG Shaowu1, CHEN Xucan1,2   

  1. 1 School of Computer Science,National University of Defense Technology,Changsha 410073,China
    2 National Innovation Institute of Defense Technology,Academy of Military Sciences,Beijing 100166,China
    3 Tianjin Artificial Intelligence Innovation Center,Tianjin 300457,China
  • Received:2022-08-10 Revised:2022-12-03 Online:2023-09-15 Published:2023-09-01
  • About author:AN Haojia,born in 1991,postgraduate.His main research interests include robotics and artificial intelligence.
    SHI Dianxi,born in 1966,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include distributed object middleware technology,adaptive software technology,artifıcial intelligence,and robot operating systems.
  • Supported by:
    National Natural Science Foundation of China(91948303).

PDF (PC)

2047

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

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

Abstract: 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 3 000),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(3 000~1 million),TAMP can solve the task assignment problem in 60 s while keeping the deviation of the optimal solution within 0.3%.

Key words: Multi-robot system, Area coverage, Task assignment, Multi-level graph partitioning, Min-max balanced connected q-partition problem

中图分类号: 

  • TP391
[1]SHEN Z,SONG J,MITTAL K,et al.CT-CPP:Coverage Path Planning for 3D Terrain Reconstruction Using Dynamic Cove-rage Trees[J].IEEE Robotics and Automation Letters,2022,7(1):135-142.
[2]CARBONE C,ALBANI D,MAGISTRI F,et al.Monitoring and mapping of crop fields with UAV swarms based on information gain[C]//International Symposium Distributed Autonomous Robotic Systems.Cham:Springer,2021:306-319.
[3]CABREIRA T M,DI FRANCO C,FERREIRA P R,et al.Ener-gy-aware spiral coverage path planning for uav photogrammetric applications[J].IEEE Robotics and Automation Letters,2018,3(4):3662-3668.
[4]HAYAT S,YANMAZ E,BROWN T X,et al.Multi-objectiveUAV path planning for search and rescue[C]//IEEE International Conference on Robotics and Automation.IEEE,2017:5569-5574.
[5]GALCERAN E,CARRERAS M.A surveyon coverage pathplanning for robotics[J].Robotics and Autonomous Systems,2013,61(12):1258-1276.
[6]REKLEITIS I,NEW A P,RANKIN E S,et al.Efficient bous-trophedon multi-robot coverage:an algorithmic approach[J].Annals of Mathematics and Artificial Intelligence,2008,52(2):109-142.
[7]MATIĆD.A mixed integer linear programming model and va-riable neighborhood search for maximally balanced connected partition problem[J].Applied Mathematics and Computation,2014,237:85-97.
[8]ZHOU X,WANG H,DING B,et al.Balanced connected task al-locations for multi-robot systems:An exact flow-based integer program and an approximate tree-based genetic algorithm[J].Expert Systems with Applications,2019,116:10-20.
[9]MIYAZAWA F K,MOURA P F S,OTA M J,et al.Partitioning a graph into balanced connected classes:Formulations,separation and experiments[J].European Journal of Operational Research,2021,293(3):826-836.
[10]KRATICA J.Solving the maximally balanced connected partition problem in graphs by usinggenetic algorithm[J].Computing and Informatics,2008,27(3):341-354.
[11]ZHOU X,WANG H,DING B.How many robots are enough:a multi-objective genetic algorithm for the single-objective time-limited complete coverage problem[C]//IEEE International Conference on Robotics and Automation(ICRA).IEEE,2018:2380-2387.
[12]AGMON N,HAZON N,KAMINKA G A.Constructing span-ning trees for efficient multi-robot coverage[C]//Proceedings 2006 IEEE International Conference on Robotics and Automation.IEEE,2006:1698-1703.
[13]KARAPETYAN N,BENSON K,MCKINNEY C,et al.Efficient multi-robot coverage of a known environment[C]//2017 IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS).IEEE,2017:1846-1852.
[14]AZPÚRUA H,FREITAS G M,MACHARET D G,et al.Multi-robot coverage path planning using hexagonal segmentation for geophysical surveys[J].Robotica,2018,36(8):1144-1166.
[15]CHOSET H.Coverage for robotics－a survey of recent results[J].Annals of Mathematics and Artificial Intelligence,2001,31(1):113-126.
[16]SHIVASHANKAR V,JAIN R,KUTER U,et al.Real-timeplanning for covering an initially-unknown spatial environment[C]//Twenty-Fourth International FLAIRS Conference.2011.
[17]HAZON N,KAMINKA G A.Redundancy,efficiency and ro-bustness in multi-robot coverage[C]//Proceedings of the 2005 IEEE International Conference on Robotics and Automation.IEEE,2005:735-741.
[18]FREDERICKSON G N,ZHOU S.Optimal parametric search for path and tree partitioning[J].arXiv:1711.00599,2017.
[19]CHEN G,CHEN Y,CHEN Z Z,et al.Approximation algo-rithms for the maximally balanced connected graph tripartition problem[J].Journal of Combinatorial Optimization,2022,
44(3):1753-1773.
[20]CHEN Y,CHEN Z Z,LIN G,et al.Approximation algorithms for maximally balanced connected graph partition[J].Algorithmica,2021,83(12):3715-3740.
[21]WANG S H.Graph Theory,2nd ed[M].Science Press,2009.
[22]KARYPIS G,KUMAR V.A fast and high quality multilevelscheme for partitioning irregular graphs[J].SIAM Journal on scientific Computing,1998,20(1):359-392.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发